Codificación de Fibonacci

En matemáticas e informática, la codificación de Fibonacci es un código universal ^{[ 1 ]} que codifica números enteros positivos en palabras binarias. Es un ejemplo de representación de números enteros basada en los números de Fibonacci . Cada palabra termina con "11" y no contiene ninguna otra instancia 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 determinado es exactamente la representación de Zeckendorf de ese número entero con el orden de sus dígitos invertido y un "1" adicional al final.

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

${\displaystyle N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ y }}d(k-1)=d(k)=1.\!}$

donde F ( i ) es el i -ésimo número de Fibonacci , y por lo tanto F ( i +2) es el i -ésimo número de Fibonacci distinto comenzando con${\displaystyle 1,2,3,5,8,13,\ldots }$. El último trozo${\displaystyle d(k)}$Siempre es un bit añadido de 1 y no lleva valor posicional.

Se puede demostrar que dicha codificación es única, y la única aparición de "11" en cualquier palabra clave se encuentra al final (es decir, d ( k − 1) y d ( k )). El penúltimo bit es el más significativo y el primero es el menos significativo. Además, no se pueden omitir los ceros iniciales, como ocurre, por ejemplo, en los números decimales.

A continuación se muestran los primeros códigos de Fibonacci, así como su denominada probabilidad implícita , que es el valor para cada número que tiene un código de tamaño mínimo en la codificación de Fibonacci.

Para codificar un número entero N :

1. Encuentra el mayor número de Fibonacci igual o menor que N ; resta este número de N , anotando el resto.
2. Si el número restado fue el i -ésimo número de Fibonacci F ( i ) , coloque un 1 en el lugar i − 2 en la palabra clave (contando el dígito más a la izquierda como lugar 0).
3. Repita los pasos anteriores, sustituyendo el resto por N , hasta que se obtenga un resto de 0.
4. Coloca un 1 adicional después del último dígito de la derecha en la palabra clave.

Para decodificar una palabra clave, elimine el último "1", asigne a los bits restantes los valores 1, 2, 3, 5, 8, 13... (los números de Fibonacci ) a los bits de la palabra clave y sume los valores de los bits "1".

La codificación de Fibonacci posee una propiedad útil que a veces la hace atractiva en comparación con otros códigos universales: es un ejemplo de código autosincronizado , lo que facilita la recuperación de datos de una secuencia dañada. Con la mayoría de los demás códigos universales, si se altera un solo bit , ninguno de los datos posteriores se leerá correctamente. En cambio, con la codificación de Fibonacci, un bit modificado puede provocar que un token se lea como dos, o que dos tokens se lean incorrectamente como uno, pero leer un "0" de la secuencia detendrá la propagación de los errores. Dado que la única secuencia que no contiene "0" es una secuencia de tokens "11", la distancia de edición total entre una secuencia dañada por un error de un solo bit y la secuencia original es, como máximo, de tres.

Este enfoque, que codifica mediante una secuencia de símbolos en la que algunos patrones (como "11") están prohibidos, puede generalizarse libremente. ^{[ 2 ]}

La siguiente tabla muestra que el número 65 se representa en la codificación de Fibonacci como 0100100011, ya que 65 = 2 + 8 + 55. Los dos primeros números de Fibonacci (0 y 1) no se utilizan, y siempre se añade un 1.

${\displaystyle {\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{adicional}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}}$

Las codificaciones de Fibonacci para los enteros positivos son cadenas binarias que terminan con "11" y no contienen otras instancias de "11". Esto se puede generalizar a cadenas binarias que terminan con N unos consecutivos y no contienen otras instancias de N unos consecutivos. Por ejemplo, para N  =  3, los enteros positivos se codifican como 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. En este caso, el número de codificaciones en función de la longitud de la cadena viene dado por la secuencia de números de Tribonacci .

Para restricciones generales que definen qué símbolos están permitidos después de un símbolo dado, la tasa de información máxima se puede obtener encontrando primero las probabilidades de transición óptimas mediante un paseo aleatorio de entropía máxima y luego utilizando un codificador de entropía (con codificador y decodificador conmutados) para codificar un mensaje como una secuencia de símbolos que cumplan las probabilidades de transición óptimas encontradas.

• base de la proporción áurea
• Codificación de Negafibonacci
• numeración de Ostrowski
• Código universal
• Varicode , una aplicación práctica
• Teorema de Zeckendorf
• Paseo aleatorio de máxima entropía

• Allouche, Jean-Paul; Shallit , Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations . Cambridge University Press . p. 105. ISBN  978-0-521-82332-6. Zbl 1086.11015 . 
• Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). "Códigos completos universales robustos para transmisión y compresión". Matemáticas Aplicadas Discretas . 64 (1): 31– 55. CiteSeerX 10.1.1.37.3064 . doi : 10.1016/0166-218X(93)00116-H . ISSN 0166-218X . Zbl 0874.94026 .   

• Stakhov, AP (2009). Las matemáticas de la armonía: de Euclides a las matemáticas y la informática contemporáneas . Singapur: World Scientific Publishing .