Codificación de Fibonacci

En matemáticas y computación, la codificación de Fibonacci es un código universal ^{[ cita requerida ]} que codifica números enteros positivos en palabras de código binario . Es un ejemplo de representaciones de números enteros basados en números de Fibonacci . Cada palabra clave termina con "11" y no contiene otras instancias de "11" antes del final.

El código de Fibonacci está estrechamente relacionado con la representación de Zeckendorf , un sistema de numeración posicional que utiliza el teorema de Zeckendorf y tiene la propiedad de que ningún número tiene una representación con unos consecutivos. La palabra clave de Fibonacci para un número entero en particular es exactamente la representación de Zeckendorf del número entero con el orden de sus dígitos invertido y un "1" adicional agregado al final.

Para un número , si representa los dígitos de la palabra clave que representa , entonces tenemos: ${\ estilo de visualización N \!}$ $d(0),d(1),\ldots,d(k-1),d(k)\!$ ${\ estilo de visualización N \!}$

donde $F (i)$ es el $i$ ésimo número de Fibonacci , por lo que $F (i +2 )$ es el $i$ ésimo número de Fibonacci distinto que comienza con . El último bit siempre es un bit adjunto de 1 y no tiene valor posicional. $1,2,3,5,8,13,\ldots$ ${\ estilo de visualización d (k)}$

Puede demostrarse que dicha codificación es única, y que la única aparición de "11" en cualquier palabra de código es al final, es decir , d ( k - 1) y d ( k ). El penúltimo bit es el bit más significativo y el primer bit es el bit menos significativo. Tampoco se pueden omitir los ceros a la izquierda como se puede hacer, por ejemplo, en números decimales.

Los primeros códigos de Fibonacci se muestran a continuación, y también su llamada probabilidad implícita , el valor de cada número que tiene un código de tamaño mínimo en la codificación de Fibonacci.