En matemáticas , la codificación negaFibonacci es un código universal que codifica enteros distintos de cero en palabras de código binario . Es similar a la codificación de Fibonacci , excepto que permite representar tanto números enteros positivos como negativos. Todos los códigos terminan con "11" y no tienen "11" antes del final.
El código de Fibonacci está estrechamente relacionado con la representación negaFibonacci , un sistema de numeración posicional que a veces utilizan los matemáticos. El código negaFibonacci para un entero distinto de cero en particular es exactamente el de la representación negaFibonacci del entero, excepto con el orden de sus dígitos invertido y un "1" adicional agregado al final. El código negaFibonacci para todos los números negativos tiene un número impar de dígitos, mientras que los de todos los números positivos tienen un número par de dígitos.
Método de codificación
Para codificar un entero X distinto de cero :
- Calcular la más grande (o más pequeño) número encodeable con N bits de sumando los impares (o incluso) negafibonacci números de 1 a N .
- Cuando se determina que N bits es suficiente para contener X , reste el N - ésimo número negaFibonacci de X , haciendo un seguimiento del resto, y coloque un uno en el N-ésimo bit de la salida.
- Trabajando hacia abajo desde el enésimo bit hasta el primero, compare cada uno de los números negaFibonacci correspondientes con el resto. Réstelo del resto si el valor absoluto de la diferencia es menor, Y si el siguiente bit más alto aún no tiene uno. Se coloca un uno en el bit apropiado si se realiza la resta, o un cero en caso contrario.
- Ponga uno en el bit N + 1th para terminar.
Para decodificar un token en el código, elimine el último "1", asigne a los bits restantes los valores 1, −1, 2, −3, 5, −8, 13 ... (los números de negafibonacci ) y agregue el "1" bits.
Mesa
El código para los números enteros de −11 a 11 se proporciona a continuación.
número | Representación negaFibonacci | código negaFibonacci |
---|---|---|
−11 | 101000 | 0001011 |
−10 | 101001 | 1001011 |
−9 | 100010 | 0100011 |
−8 | 100000 | 0000011 |
−7 | 100001 | 1000011 |
−6 | 100100 | 0010011 |
−5 | 100101 | 1010011 |
−4 | 1010 | 01011 |
−3 | 1000 | 00011 |
−2 | 1001 | 10011 |
−1 | 10 | 011 |
0 | 0 | (no se puede codificar) |
1 | 1 | 11 |
2 | 100 | 0011 |
3 | 101 | 1011 |
4 | 10010 | 010011 |
5 | 10000 | 000011 |
6 | 10001 | 100011 |
7 | 10100 | 001011 |
8 | 10101 | 101011 |
9 | 1001010 | 01010011 |
10 | 1001000 | 00010011 |
11 | 1001001 | 10010011 |
Ver también
Referencias
- Knuth, Donald (2008), Negafibonacci Numbers and the Hyperbolic Plane , artículo presentado en la reunión anual de la Asociación Matemática de América, San José, California.
- Knuth, Donald (2009), El arte de la programación informática , Volumen 4, Fascículo 1: Trucos y técnicas de bit a bit; Diagramas de decisión binaria , ISBN 0-321-58050-8. En el borrador previo a la publicación de la sección 7.1.3, véanse en particular las págs. 36–39.
- Margenstern, Maurice (2008), Autómatas celulares en espacios hiperbólicos , Avances en computación no convencional y autómatas celulares, 2 , Archives contemporaines, p. 79, ISBN 9782914610834.