Codificación de Fibonacci

En matemáticas e informática, la codificación Fibonacci es un código universal 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 usa el teorema de Zeckendorf y tiene la propiedad de que ningún número tiene una representación con 1s 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" adjunto al final.

Definición

Para un número ${displaystyle ¡No!$, si ${displaystyle d(0),d(1),ldotsd(k-1),d(k)!}$ representan los dígitos de la palabra clave que representa ${displaystyle ¡No!$ entonces tenemos:

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

Donde F()i) es iel número de Fibonacci, y así F()i+2) es in número de Fibonacci distintos empezando por ${displaystyle 1,2,3,5,8,13,ldots }$. La última parte ${displaystyle d(k)}$ es siempre un bit anexado de 1 y no tiene valor de lugar.

Se puede demostrar que tal codificación es única, y la única ocurrencia de "11" en cualquier palabra clave está 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. Además, los ceros iniciales no se pueden omitir como se puede hacer, p. numeros decimales.

Los primeros códigos de Fibonacci se muestran a continuación, y también su denominada 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.

Signatura	Representación de Fibonacci	Fibonacci code word	Probabilidad implícita
1	${displaystyle F(2)}$	11	1/4
2	${displaystyle F(3)}$	011	1/8
3	${displaystyle F(4)}$	0011	1/16
4	${displaystyle F(2)+F(4)}$	1011	1/16
5	${displaystyle F(5)}$	00011	1/32
6	${displaystyle F(2)+F(5)}$	10011	1/32
7	${displaystyle F(3)+F(5)}$	01011	1/32
8	${displaystyle F(6)}$	000011	1/64
9	${displaystyle F(2)+F(6)}$	100011	1/64
10	${displaystyle F(3)+F(6)}$	010011	1/64
11	${displaystyle F(4)+F(6)}$	001011	1/64
12	${displaystyle F(2)+F(4)+F(6)}$	Himmelpfortgasse 11	1/64
13	${displaystyle F(7)}$	0000011	1/128
14	${displaystyle F(2)+F(7)}$	1000011	1/128

Para codificar un número entero N:

1. Encontrar el mayor número de Fibonacci igual o inferior a N; restar este número de NMantener un seguimiento del resto.
2. Si el número restante era el iNúmero de Fibonacci F()i), poner un 1 en su lugar i−2 en la palabra clave (contando el más dígito izquierdo como lugar 0).
3. Repita los pasos anteriores, sustituyendo el resto para N, hasta que se alcance un resto de 0.
4. Coloque un 1 adicional después del dígito más adecuado en la palabra clave.

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

Comparación con otros códigos universales

La codificación de Fibonacci tiene una propiedad útil que a veces la hace atractiva en comparación con otros códigos universales: es un ejemplo de un código de sincronización automática, lo que facilita la recuperación de datos de un flujo dañado. Con la mayoría de los otros códigos universales, si se altera un solo bit, ninguno de los datos que vienen después se leerá correctamente. Con la codificación de Fibonacci, por otro lado, un bit cambiado puede hacer que un token se lea como dos, o que dos tokens se lean incorrectamente como uno solo, pero al leer un "0" de la secuencia evitará que los errores se propaguen más. Dado que la única secuencia que no tiene "0" en él hay una corriente de "11" tokens, la distancia de edición total entre un flujo dañado por un error de un solo bit y el flujo original es como máximo tres.

Este enfoque, la codificación mediante una secuencia de símbolos, en la que algunos patrones (como "11") están prohibidos, se puede generalizar libremente.

Ejemplo

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 adicional.

${displaystyle {begin{array}{ccccccc imperc}hline [0]$

Generalizaciones

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 1's consecutivos y no contienen otras instancias de N 1's 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 las 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 primero encontrando las probabilidades de transición óptimas usando el paseo aleatorio de entropía máxima, luego usando el codificador de entropía (con codificador conmutado con decodificador) para codificar un mensaje como una secuencia de símbolos que cumplen las probabilidades de transición óptimas encontradas.