En matemáticas , la codificación negafibonacci es un código universal que codifica números enteros distintos de cero en palabras de código binario . Es similar a la codificación Fibonacci , excepto que permite representar números enteros positivos y negativos. Todos los códigos terminan en "11" y no tienen ningún "11" antes del final.
Método de codificación
Para codificar un entero distinto de cero X :
- Calcule el número codificable más grande (o más pequeño) con N bits sumando los números negafibonacci impares (pares) del 1 al N.
- Cuando se determina que N bits son suficientes para contener X , reste el N-ésimo número negafibonacci de X , manteniendo el registro del resto, y coloque un uno en el N-ésimo bit de la salida.
- Trabajando hacia abajo desde el bit N al primero, compare cada uno de los números de negafibonacci correspondientes con el resto. Réstelo del resto si el valor absoluto de la diferencia es menor, Y si el bit inmediatamente superior no tiene ya un uno. Se coloca un uno en el bit correspondiente si se realiza la resta, o un cero en caso contrario.
- Coloque un uno en el bit N+1 para finalizar.
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 negafibonacci) y agregue los bits "1".
Representación de Negafibonacci
El código negafibonacci 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 número entero distinto de cero es exactamente el de la representación negafibonacci del número entero, excepto que el orden de sus dígitos está invertido y se le añade un "1" adicional al final. El código negafibonacci para todos los números negativos tiene un número impar de dígitos, mientras que el de todos los números positivos tiene un número par de dígitos.
Mesa
El código para los números enteros del −11 al 11 se muestra a continuación.
Véase también
Referencias
Obras citadas
- Knuth, Donald (2008). Números de Negafibonacci y el plano hiperbólico . Reunión anual de la Asociación Matemática de Estados Unidos. San José, California.
- Knuth, Donald (2009). El arte de la programación informática , volumen 4, fascículo 1: trucos y técnicas de cálculo bit a bit; diagramas de decisión binaria . Addison-Wesley. ISBN 978-0-321-58050-4.En el borrador previo a la publicación de la sección 7.1.3, véanse en particular las páginas 36 a 39.
- Margenstern, Maurice (2008). Autómatas celulares en espacios hiperbólicos. Avances en computación no convencional y autómatas celulares. Vol. 2. Archives contemporaines. p. 79. ISBN 9782914610834.
