En matemàtiques i informàtica, la codificació de Fibonacci és un codi universal que codifica nombres enters positius en paraules de codi binari. És un exemple de representacions de nombres enters basades en nombres de Fibonacci. Cada paraula de codi acaba amb "11" i no conté cap altra instància de "11" abans del final.
El codi de Fibonacci està estretament relacionat amb la representació de Zeckendorf, un sistema numeral posicional que utilitza el teorema de Zeckendorf i té la propietat que cap nombre té una representació amb uns consecutius. La paraula del codi de Fibonacci per a un enter particular és exactament la representació de Zeckendorf de l'enter amb l'ordre dels seus dígits invertit i un "1" addicional afegit al final. miniatura|Gràfic dels primers membres de la seqüència de Fibonacci.
Definició Per a un nombre , si representen els dígits de la paraula codificada que representa llavors tenim:
on és el nombre de Fibonacci i-èsim, i per tant és el nombre de Fibonacci diferent i-èsim que comença per L'últim tros sempre és un bit afegit d'1 i no té valor posicional.
Es pot demostrar que aquesta codificació és única, i l'única aparició d'"11" en qualsevol paraula de codi és al final (és a dir, d ( k − 1) i d ( k )). El penúltim bit és el bit més significatiu i el primer bit és el bit menys significatiu. A més, els zeros inicials no es poden ometre, ja que sí que es poden ometre, per exemple, en nombres decimals.
A continuació es mostren els primers codis de Fibonacci, i també la seva probabilitat implícita, el valor de cada nombre que té un codi de mida mínima en la codificació de Fibonacci. SímbolRepresentació de FibonacciParaula de codi de FibonacciProbabilitat implícita1111/420111/8300111/16410111/165000111/326100111/327010111/3280000111/6491000111/64100100111/64110010111/64121010111/641300000111/1281410000111/128 Per codificar un enter :
Troba el nombre de Fibonacci més gran igual o menor que ; resteu aquest nombre de i feu un seguiment del residu. Si el nombre restat és el i-èsim nombre de Fibonacci F(i), posa un 1 al lloc i − 2 de la paraula de codi (comptant el dígit més a l'esquerra com a lloc 0). Repeteix els passos anteriors, substituint el residu per , fins que s'arribi a un residu de 0. Col·loca un 1 addicional després del dígit situat més a la dreta de la paraula clau.
Per descodificar una paraula de codi, elimineu l'"1" final, assigneu els valors restants 1, 2, 3, 5, 8, 13... (els nombres de Fibonacci) als bits de la paraula de codi i sumeu els valors dels bits "1".
Referències
Categoria:Codificació