Codifica di Fibonacci

sistema di codifica

La codifica di Fibonacci è una codificazione entropica per la rappresentazione dei numeri interi basata sulla successione di Fibonacci.

La successione di Fibonacci è completa, ovvero qualsiasi numero intero può essere espresso come somma di numeri di Fibonacci distinti. Per il teorema di Zeckendorf, inoltre, esiste una rappresentazione unica degli interi come somma di numeri di Fibonacci distinti. La rappresentazione di Zeckendorf ha inoltre la proprietà che non sono presenti due cifre consecutive uguali ad uno.

Si codifica quindi il numero in maniera inversa rispetto alla rappresentazione binaria polinomiale rispetto alla base φ, aggiungendo una cifra "1" in modo che termini con "11", ottenendo un codice prefisso.

Numero Codifica di Fibonacci Rappresentazione di Zeckendorf
1 11
2 011
3 0011
4 1011
5 00011
6 10011
7 01011
8 000011
9 100011
10 010011

Bibliografia

modifica

Voci correlate

modifica
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica