Fibonacci coding

Ο Κωδικός Fibonacci είναι ένας καθολικός κωδικός στα μαθηματικά και την πληροφορική, ο οποίος κωδικοποιεί τους θετικούς ακεραίους σε δυαδικές λέξεις κωδικού. Είναι ένα παράδειγμα αναπαράστασης ακεραίων βασισμένης στους αριθμούς Fibonacci. Κάθε λέξη κωδικού τελειώνει με "11" και δεν περιέχει άλλες εμφανίσεις του "11" πριν από το τέλος.

Ορισμός[επεξεργασία]

Για έναν αριθμό $N\!$ , αν $d(0),d(1),\ldots ,d(k-1),d(k)\!$ αντιπροσωπεύουν τα ψηφία της λέξης κωδικού που αντιπροσωπεύει τον $N\!$ , τότε έχουμε:

N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ and }}d(k-1)=d(k)=1.\!

όπου $F (i)$ είναι ο $i$ ος αριθμός Fibonacci, και έτσι ο $F (i +2)$ είναι ο $i$ ος ξεχωριστός αριθμός Fibonacci ξεκινώντας με $1,2,3,5,8,13,\ldots$ . Το τελευταίο βίτ $d(k)$ είναι πάντα ένα προστιθέμενο βίτ του 1 και δεν φέρει τιμή θέσης.

Μπορεί να αποδειχθεί ότι μια τέτοια κωδικοποίηση είναι μοναδική, και η μόνη εμφάνιση του "11" σε οποιαδήποτε λέξη κωδικού είναι στο τέλος (δηλαδή, d(k−1) και d(k)). Το προτελευταίο βίτ είναι το πιο σημαντικό βίτ και το πρώτο βίτ είναι το λιγότερο σημαντικό βίτ. Επίσης, οι αρχικοί μηδένικοι δεν μπορούν να παραλειφθούν όπως μπορούν να γίνει στους δεκαδικούς αριθμούς.

Οι πρώτες λέξεις Fibonacci παρουσιάζονται παρακάτω, καθώς και η λεγόμενη υπονοούμενη πιθανότητα για κάθε αριθμό που έχει ένα κωδικό μικρότερου μεγέθους στην κωδικοποίηση Fibonacci.

Σύμβολο	Αναπαράσταση Fibonacci	Λέξη κωδικού Fibonacci	Υπονοούμενη πιθανότητα
1	$F(2)$	11	1/4
2	$F(3)$	011	1/8
3	$F(4)$	0011	1/16
4	$F(2)+F(4)$	1011	1/16
5	$F(5)$	00011	1/32
6	$F(2)+F(5)$	10011	1/32
7	$F(3)+F(5)$	01011	1/32
8	$F(6)$	000011	1/64
9	$F(2)+F(6)$	100011	1/64
10	$F(3)+F(6)$	010011	1/64
11	$F(4)+F(6)$	001011	1/64
12	$F(2)+F(4)+F(6)$	101011	1/64
13	$F(7)$	0000011	1/128
14	$F(2)+F(7)$	1000011	1/128

Για να κωδικοποιήσουμε έναν ακέραιο $N$ :

Βρείτε τον μεγαλύτερο αριθμό Fibonacci ίσο ή μικρότερο από το $N$ ; αφαιρέστε αυτόν τον αριθμό από το $N$ , κρατώντας το υπόλοιπο.
Αν ο αριθμός που αφαιρέθηκε ήταν ο $i$ ος αριθμός Fibonacci $F (i)$ , βάλτε ένα 1 στη θέση $i - 2$ στη λέξη κωδικού (μετρώντας το αριστερότερο ψηφίο ως θέση 0).
Επαναλάβετε τα προηγούμενα βήματα, αντικαθιστώντας το υπόλοιπο για $N$ , έως ότου φτάσετε σε υπόλοιπο 0.
Βάλτε ένα επιπλέον 1 μετά από το δεξιότερο ψηφίο στη λέξη κωδικού.

Για να αποκωδικοποιήσετε μια λέξη κωδικού, αφαιρέστε το τελικό "1", αναθέστε στα υπόλοιπα τις τιμές 1,2,3,5,8,13... (οι αριθμοί Fibonacci) στα βίτ στη λέξη κωδικού, και προσθέστε τις τιμές των βίτ "1".

Σύγκριση με άλλους καθολικούς κωδικούς[επεξεργασία]

Η κωδικοποίηση Fibonacci έχει μια χρήσιμη ιδιότητα που κάποιες φορές την καθιστά ελκυστική σε σύγκριση με άλλους καθολικούς κωδικούς: είναι ένα παράδειγμα ενός αυτοσυγχρονιζόμενου κωδικού, καθιστώντας το ευκολότερο να ανακτηθούν δεδομένα από μια κατεστραμμένη ροή. Με τους περισσότερους άλλους καθολικούς κωδικούς, αν ένα μοναδικό βίτ αλλάξει, τότε κανένα από τα δεδομένα που έρχεται μετά από αυτό δεν θα διαβαστούν σωστά. Με την κωδικοποίηση Fibonacci, από την άλλη, ένα αλλαγμένο βίτ μπορεί να προκαλέσει ένα σύμβολο να διαβαστεί ως δύο, ή να προκαλέσει δύο σύμβολα να διαβαστούν λανθασμένα ως ένα, αλλά η ανάγνωση ενός "0" από τη ροή θα σταματήσει τα σφάλματα από το να διαδοθούν περαιτέρω. Επειδή η μόνη ροή που δεν έχει "0" είναι μια ροή από σύμβολα "11", η συνολική απόσταση επεξεργασίας μεταξύ μιας ροής που καταστράφηκε από ένα μοναδικό σφάλμα βίτ και της αρχικής ροής είναι το πολύ τρία.

Αυτή η προσέγγιση, κωδικοποίηση χρησιμοποιώντας ακολουθίες συμβόλων, στην οποία κάποια μοτίβα (όπως το "11") είναι απαγορευμένα, μπορεί να γενικευτεί ελεύθερα.^[1]

Παράδειγμα[επεξεργασία]

Ο παρακάτω πίνακας δείχνει ότι ο αριθμός 65 αναπαρίσταται στην κωδικοποίηση Fibonacci ως 0100100011, αφού 65 = 2 + 8 + 55. Οι δύο πρώτοι αριθμοί Fibonacci (0 και 1) δεν χρησιμοποιούνται, και προστίθεται πάντα ένα επιπλέον 1.

{\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{επιπλέον}}\\\hline *&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}

Γενικεύσεις[επεξεργασία]

Αν κωδικοποιούμε τους θετικούς ακεραίους, τότε οι λέξεις Fibonacci είναι δυαδικές αλυσίδες που τελειώνουν με "11" και δεν περιέχουν άλλες εμφανίσεις του "11". Αυτό μπορεί να γενικευτεί σε δυαδικές αλυσίδες που τελειώνουν με Ν συνεχόμενα 1s και δεν περιέχουν άλλες εμφανίσεις των Ν συνεχόμενα 1s. Για παράδειγμα, για Ν = 3 οι θετικοί ακεραίοι κωδικοποιούνται ως 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. Σε αυτή την περίπτωση, ο αριθμός των κωδικοποιήσεων ως συνάρτηση του μήκους της αλυσίδας δίνεται από την ακολουθία των αριθμών tribonacci.

Για γενικούς περιορισμούς που ορίζουν ποια σύμβολα επιτρέπονται μετά από ένα δεδομένο σύμβολο, η μέγιστη πληροφοριακή ταχύτητα μπορεί να επιτευχθεί βρίσκοντας πρώτα τις οπτιμοποιημένες πιθανότητες μετάβασης χρησιμοποιώντας έναν τυχαίο περίπατο μέγιστης εντροπίας, και μετά χρησιμοποιώντας έναν κωδικοποιητή εντροπίας (με ανταλλαγμένο κωδικοποιητή και αποκωδικοποιητή) για να κωδικοποιήσει ένα μήνυμα ως μια ακολουθία συμβόλων που ικανοποιούν τις βρεθείσες οπτιμοποιημένες πιθανότητες μετάβασης.

Βιβλιογραφία[επεξεργασία]

Script error: No such module "citation/CS1".
Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). «Robust universal complete codes for transmission and compression». Discrete Applied Mathematics 64 (1): 31–55. doi:10.1016/0166-218X(93)00116-H. ISSN 0166-218X. Zbl 0874.94026 Πρότυπο:Only in print.