Código Fibonacci

A codificação Fibonacci é um código binário universal que associa a cada inteiro positivo uma string de bits única que sempre termina em dois uns consecutivos. A construção usa o teorema de Zeckendorf: todo inteiro positivo é a soma de números de Fibonacci não consecutivos da sequência que começa em um, dois, três, cinco, oito, e assim por diante. Coloque um um para cada parcela, um zero para cada termo da base omitido a partir de F dois, e acrescente um bit terminador final para o código terminar em onze. Estudantes de teoria da informação, tarefas de compressão e projetistas de protocolos que precisam de codificação auto-delimitada de inteiros usam este conversor para conferir exemplos sem montar a tabela de Fibonacci à mão.

O que é a codificação Fibonacci e por que termina em 11

A codificação Fibonacci pertence à família de códigos universais para inteiros positivos: todo n maior ou igual a um recebe uma palavra binária, e nenhuma palavra-código é prefixo de outra, de modo que um fluxo de códigos pode ser analisado sem prefixos de comprimento. O fato matemático central é o teorema de Zeckendorf.

Usando a sequência de Fibonacci escrita como F dois igual a um, F três igual a dois, F quatro igual a três, F cinco igual a cinco, e assim por diante (a sequência usual sem a primeira duplicação do um), todo inteiro positivo tem uma representação única como soma de termos não consecutivos dessa sequência. A codificação coloca um bit sob cada valor da base de F dois até a maior parcela que aparece: o bit é um quando aquele número de Fibonacci é usado e zero caso contrário.

Como Zeckendorf proíbe dois uns consecutivos nos bits da base, o bit mais alto usado é sempre um e nunca é seguido de outro um dentro da base. Acrescentar um único um terminador produz, portanto, um final distintivo de dois uns consecutivos. Esse padrão é o sinal de parada do decodificador: leia bits até ver onze, remova o um final e recupere a soma de Zeckendorf.

Valores clássicos pequenos tornam o padrão concreto. Um codifica-se como onze, dois como zero um um, três como zero zero um um, quatro como um zero um um, cinco como zero zero zero um um e seis como um zero zero um um. Um n maior apenas estende a tabela de Fibonacci até o maior Fk no máximo n, executa a seleção gulosa de cima e emite a mesma string terminada.

O comprimento do código cresce como O do logaritmo na base phi de n, de modo que mesmo inteiros seguros grandes permanecem strings de bits curtas adequadas a demos, vetores de teste e slides sobre códigos de inteiros livres de prefixo.

Onde a codificação Fibonacci é útil

Cursos de teoria da informação e compressão usam a codificação Fibonacci como código universal concreto ao lado de Elias gamma e delta; um conversor ao vivo permite que os estudantes confiram codificações de tarefa para inteiros positivos arbitrários sem montar uma planilha de Fibonacci a cada vez. Programação competitiva e blogs de algoritmos que discutem representações de Zeckendorf, sistemas de numeração Fibonacci ou fluxos auto-delimitados precisam de um oráculo determinístico que devolva a string de bits e as parcelas para testes unitários.

Projetistas de protocolos que avaliam codificações de inteiros de comprimento variável podem comparar comprimentos do código Fibonacci com esquemas de largura fixa e no estilo LEB128 em sequências de ID de amostra antes de fixar um formato de fio. Validação falha não consome saldo.