Codificação Fibonacci (Zeckendorf)

A codificação Fibonacci, também chamada codificação de Zeckendorf, escreve cada inteiro positivo como uma soma única de números de Fibonacci não consecutivos e empacota essa soma em uma cadeia de bits autodlimitada que sempre termina com o terminador 11. Estudantes que encontram códigos universais pela primeira vez, instrutores que montam oráculos de prova e engenheiros que comparam códigos Elias gamma, Golomb e Fibonacci precisam do mesmo mapa determinístico nos dois sentidos: inteiro para bits e bits para inteiro, com falha honesta quando a entrada é zero, negativa, não binária ou não é o layout canônico de Zeckendorf.

O que significam a representação de Zeckendorf e a codificação Fibonacci

O teorema de Zeckendorf afirma que todo inteiro positivo tem uma representação única como soma de números de Fibonacci em que nenhum somando é consecutivo na sequência de Fibonacci. A convenção usual de codificação inicia a sequência utilizável em F2 igual a 1, F3 igual a 2, F4 igual a 3, F5 igual a 5, e assim por diante, omitindo de propósito o F1 duplicado igual a 1 para que a unicidade fique inequívoca.

Para codificar n você escolhe de forma gulosa o maior Fibonacci que não ultrapasse o restante, pula o vizinho inferior seguinte e repete até o resto ser zero. O código Fibonacci é então a máscara de bits desses termos de F2 até o maior usado, escrita do índice baixo ao alto, mais um 1 terminador extra.

Como o termo de maior índice sempre contribui com um 1 final de carga útil, todo código válido termina com o padrão de dois bits 11, o que torna o código autodlimitado em um fluxo sem campo de comprimento separado. Valores clássicos fixam o modelo mental: 1 codifica como 11, 2 como 011, 3 como 0011, 4 como 1011, 5 como 00011 e 6 como 10011.

A decodificação inverte o percurso: remove-se o bit terminador final, somam-se F2, F3, … onde os bits de carga são 1 e, opcionalmente, recodifica-se para provar que a cadeia era o layout canônico de Zeckendorf e não uma soma alternativa com Fibonacci consecutivos. Essa unicidade é exatamente por que a codificação Fibonacci é popular no ensino de códigos universais e em projetos que precisam de prefixos inteiros de comprimento variável sem dicionário.

Onde a codificação Fibonacci se paga na prática

Salas de aula e plataformas MOOC usam uma calculadora de codificação Fibonacci para que alunos verifiquem tarefas de Zeckendorf sem percorrer tabelas longas à mão e sem confundir o código com as ferramentas separadas math.fibonacci do n-ésimo termo. Cursos de programação competitiva e teoria da informação precisam de um oráculo bidirecional que produza a palavra-código e rejeite strings ilegais, alinhado a corretores de contest que marcam errado qualquer codificação não canônica ou com termos consecutivos.

Jobs de qualidade de dados podem guardar prefixos inteiros compactos autodlimitados e verificá-los depois decodificando e recodificando. Em todo fluxo trate um código válido apenas como empacotamento inteiro bem formado, não como autenticação nem segredo: a codificação Fibonacci é um código universal transparente, não criptografia. Mantenha valores no intervalo de inteiros seguros deste worker tier-A, fixe as strings de código esperadas nos testes e obtenha encode e decode determinísticos para ensino, correção e ferramentas leves sem montar um stack de álgebra computacional próprio.