Codificación de Negafibonacci

En matemáticas , la codificación negafibonacci es un código universal que codifica números enteros distintos de cero en palabras binarias. Es similar a la codificación Fibonacci , con la diferencia de que permite representar tanto números enteros positivos como negativos. Todos los códigos terminan en "11" y no tienen ningún "11" antes del final.

Los siguientes pasos describen cómo codificar un número entero distinto de cero.${\displaystyle x}$. Tenga en cuenta que${\displaystyle f}$denota la secuencia de negafibonacci.

1. Si${\displaystyle x}$es positivo, calcula el mayor entero negativo impar${\displaystyle n}$de tal manera que la suma de los términos negativos impares de la secuencia de negafibonacci de −1 a${\displaystyle n}$con un paso de −2, es mayor o igual que${\displaystyle x}$: ${\displaystyle n\in \{-\left(2k+1\right),k\in [0,\infty [\},\quad \sum _{i=-1,\;i\;odd}^{n-2}f(i)<x\leq \sum _{i=-1,\;i\;odd}^{n}f(i).}$ Si${\displaystyle x}$Si es negativo, calcula el mayor entero negativo par.${\displaystyle n}$de tal manera que la suma de los términos pares negativos de la secuencia de negafibonacci de 0 a${\displaystyle n}$con un paso de −2, es menor o igual que${\displaystyle x}$: ${\displaystyle n\in \{-2k,k\in [2,\infty [\},\quad \sum _{i=-2,\;i\;even}^{n-2}f(i)>x\geq \sum _{i=-2,\;i\;even}^{n}f(i)}$
2. Agregue un 1 en el${\displaystyle |n|^{\text{th}}}$bit de la palabra binaria. Restar${\displaystyle f(n)}$de${\displaystyle x}$.
3. Repita el proceso desde el paso 1 con el nuevo valor de x , hasta que llegue a 0.
4. Para finalizar la codificación, añade un 1 a la izquierda de la palabra binaria resultante.

Para decodificar una palabra binaria codificada, elimine el 1 situado más a la izquierda de la palabra binaria, ya que solo se utiliza para indicar el final del número codificado. A continuación, asigne a los bits restantes los valores de la secuencia de Negafibonacci desde −1 (1, −1, 2, −3, 5, −8, 13...) y sume todos los valores asociados a un 1.

La codificación negafibonacci está estrechamente relacionada con la representación negafibonacci , un sistema de numeración posicional que a veces utilizan los matemáticos. El código negafibonacci de un entero distinto de cero es exactamente igual a su representación negafibonacci, salvo que el orden de sus dígitos está invertido y se le añade un "1" al final. El código negafibonacci de 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.

El código para los números enteros desde -11 hasta 11 se muestra a continuación.

• Números de Fibonacci
• base de la proporción áurea
• Teorema de Zeckendorf