Codifica di Fibonacci

Questa voce sugli argomenti teorie dell'informatica e matematica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

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	F ( 2 ) {\displaystyle F(2)}
2	011	F ( 3 ) {\displaystyle F(3)}
3	0011	F ( 4 ) {\displaystyle F(4)}
4	1011	F ( 2 ) + F ( 4 ) {\displaystyle F(2)+F(4)}
5	00011	F ( 5 ) {\displaystyle F(5)}
6	10011	F ( 2 ) + F ( 5 ) {\displaystyle F(2)+F(5)}
7	01011	F ( 3 ) + F ( 5 ) {\displaystyle F(3)+F(5)}
8	000011	F ( 6 ) {\displaystyle F(6)}
9	100011	F ( 2 ) + F ( 6 ) {\displaystyle F(2)+F(6)}
10	010011	F ( 3 ) + F ( 6 ) {\displaystyle F(3)+F(6)}

• (EN) Aviezri S. Fraenkel, Shmuel T. Klein, Robust universal complete codes for transmission and compression, in Discrete Applied Mathematics, vol. 64, n. 1, 4 gennaio 1996, pp. 31–55, DOI:10.1016/0166-218X(93)00116-H.
• (EN) Khalid Sayood, Fibonacci codes, in Lossless Compression Handbook, Academic Press, 4 dicembre 2002, ISBN 978-0123907547.

• Teorema di Zeckendorf

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