Codifica di Fibonacci

La codifica di Fibonacci è un codice binario universale che associa a ogni intero positivo una stringa di bit unica che termina sempre con due uni consecutivi. La costruzione si fonda sul teorema di Zeckendorf: ogni intero positivo è la somma di numeri di Fibonacci non consecutivi della successione che inizia con uno, due, tre, cinque, otto, e così via. Collocate un uno per ogni addendo, uno zero per ogni termine di base omesso a partire da F due, poi aggiungete un bit terminatore finale affinché il codice termini con undici. Studenti di teoria dell'informazione, compiti di compressione e progettisti di protocolli che necessitano di una codifica auto-delimitata di interi usano questo convertitore per verificare esempi senza costruire a mano la tabella di Fibonacci.

Cos'è la codifica di Fibonacci e perché termina con 11

La codifica di Fibonacci appartiene alla famiglia dei codici universali per interi positivi: ogni n maggiore o uguale a uno riceve una parola binaria, e nessuna parola codice è prefisso di un'altra, cosicché un flusso di codici può essere analizzato senza prefissi di lunghezza. Il fatto matematico centrale è il teorema di Zeckendorf.

Usando la successione di Fibonacci scritta come F due uguale a uno, F tre uguale a due, F quattro uguale a tre, F cinque uguale a cinque, e così via (la successione usuale senza la prima duplicazione dell'uno), ogni intero positivo ha una rappresentazione unica come somma di termini non consecutivi di quella successione. La codifica colloca un bit sotto ogni valore di base da F due fino al massimo addendo che compare: il bit è uno quando quel numero di Fibonacci è usato e zero altrimenti.

Poiché Zeckendorf vieta due uni consecutivi nei bit di base, il bit più alto usato è sempre uno e non è mai seguito da un altro uno all'interno della base. L'aggiunta di un unico uno terminatore produce quindi una fine distintiva di due uni consecutivi. Quel motivo è il segnale di stop del decodificatore: leggete i bit finché non vedete undici, togliete l'uno finale e recuperate la somma di Zeckendorf.

I piccoli valori classici rendono il motivo concreto. Uno si codifica come undici, due come zero uno uno, tre come zero zero uno uno, quattro come uno zero uno uno, cinque come zero zero zero uno uno e sei come uno zero zero uno uno. Un n più grande estende semplicemente la tabella di Fibonacci fino al massimo Fk non superiore a n, esegue la selezione avida dall'alto ed emette la stessa stringa terminata.

La lunghezza del codice cresce come O del logaritmo in base phi di n, cosicché anche grandi interi sicuri restano stringhe di bit corte adatte a demo, vettori di test e diapositive sui codici di interi senza prefisso.

Dove serve la codifica di Fibonacci

I corsi di teoria dell'informazione e di compressione usano la codifica di Fibonacci come codice universale concreto accanto a Elias gamma e delta; un convertitore dal vivo consente agli studenti di verificare le codifiche dei compiti per interi positivi arbitrari senza costruire ogni volta un foglio di Fibonacci. La programmazione competitiva e i blog di algoritmi che trattano rappresentazioni di Zeckendorf, sistemi di numerazione di Fibonacci o flussi auto-delimitati necessitano di un oracolo deterministico che restituisca la stringa di bit e gli addendi per i test unitari.

I progettisti di protocolli che valutano codifiche di interi a lunghezza variabile possono confrontare le lunghezze del codice di Fibonacci con schemi a larghezza fissa e in stile LEB128 su sequenze di ID di esempio prima di fissare un formato di rete. La validazione fallita non consuma saldo.