En matemáticas e informática, la codificación de Fibonacci es un código universal [ cita requerida ] que codifica enteros positivos en palabras de código binario . Es un ejemplo de representaciones de números enteros basadas en números de Fibonacci . Cada palabra de código 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 de código de Fibonacci para un entero en particular es exactamente la representación de Zeckendorf del entero con el orden de sus dígitos invertido y un "1" adicional agregado al final.
Definición
Por un numero , Si representar los dígitos de la palabra de código que representa entonces nosotros tenemos:
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 ultimo bit es siempre un bit de 1 agregado y no tiene valor posicional.
Se puede demostrar que tal codificación es única, y la única aparición de "11" en cualquier palabra de código 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 ocurre en, por ejemplo, números decimales.
Los primeros códigos de Fibonacci se muestran a continuación, y también su supuesta 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.
Símbolo | Representación de Fibonacci | Palabra de código de Fibonacci | Probabilidad implícita |
---|---|---|---|
1 | 11 | 1/4 | |
2 | 011 | 1/8 | |
3 | 0011 | 1/16 | |
4 | 1011 | 1/16 | |
5 | 00011 | 1/32 | |
6 | 10011 | 1/32 | |
7 | 01011 | 1/32 | |
8 | 000011 | 1/64 | |
9 | 100011 | 1/64 | |
10 | 010011 | 1/64 | |
11 | 001011 | 1/64 | |
12 | 101011 | 1/64 | |
13 | 0000011 | 1/128 | |
14 | 1000011 | 1/128 |
Para codificar un número entero N :
- Encuentre el mayor número de Fibonacci igual o menor que N ; reste este número de N , haciendo un seguimiento del resto.
- 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 de código (contando el dígito más a la izquierda como el lugar 0).
- Repita los pasos anteriores, sustituyendo el resto por N , hasta alcanzar un resto de 0.
- Coloque un 1 adicional después del dígito situado más a la derecha en la palabra de código.
Para decodificar una palabra de código, elimine el "1" final, asigne los valores restantes 1, 2, 3, 5, 8, 13 ... (los números de Fibonacci ) a los bits en la palabra de código y sume los valores de los bits "1".
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 demás códigos universales, si se modifica 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 hacer que dos tokens se lean incorrectamente como uno, pero leer un "0" de la secuencia evitará que los errores se propaguen más. Dado que el único flujo que no tiene "0" es un flujo de "11" tokens, la distancia total de edición 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 utilizando una secuencia de símbolos, en la que algunos patrones (como "11") están prohibidos, se puede generalizar libremente. [1]
Ejemplo
La siguiente tabla muestra que el número 65 está representado en la codificación 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 agrega un 1 adicional.
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 consecutivos y no contienen otras instancias de N 1 consecutivos. Por ejemplo, para N = 3, los números 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 encontrando primero las probabilidades de transición óptimas usando la caminata aleatoria de entropía máxima , luego use el codificador de entropía (con codificador conmutado con decodificador) para codificar un mensaje como un secuencia de símbolos que cumplen las probabilidades de transición óptimas encontradas.
Ver también
Referencias
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Prensa de la Universidad de Cambridge . pag. 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 .
Otras lecturas
- 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 .