Τρίτη , Σεπτέμβριος 26, 2017

Εισαγωγή

 

Οι συνελικτικοί κώδικες διαφέρουν από τους μπλοκ κώδικες στο ότι ο κωδικοποιητής διαθέτει μνήμη και οι έξοδοί του σε κάποια χρονική στιγμή δεν εξαρτώνται μόνο από τις εισόδους του εκείνη τη χρονική στιγμή, αλλά και από έναν αριθμό προηγούμενων εισόδων. Ένας συνελικτικός κωδικοποιητής ρυθμού  με τάξη μνήμης  μπορεί να υλοποιηθεί ως ένα γραμμικό ακολουθιακό κύκλωμα  εισόδων και  εξόδων με μνήμη εισόδου . Αυτό σημαίνει ότι οι είσοδοι παραμένουν στον κωδικοποιητή για  επιπλέον χρονικές στιγμές αφότου εισέλθουν σ’ αυτόν. Συνήθως τα  και  παίρνουν μικρές τιμές, η ακολουθία πληροφορίας διαιρείται σε μπλοκ μήκους  και η κωδική λέξη σε μπλοκ μήκους . Στη σημαντική ειδική περίπτωση όπου , η ακολουθία πληροφορίας δε διαιρείται σε μπλοκ και υπόκειται συνεχή επεξεργασία. Σε αντίθεση με τους μπλοκ κώδικες, μεγάλες ελάχιστες αποστάσεις κωδικών λέξεων και μικρές πιθανότητες σφάλματος δεν επιτυγχάνονται με αύξηση των  και , αλλά με αύξηση της τάξης μνήμης .

 

 

Ιστορική Ανασκόπηση

 

Οι συνελικτικοί κώδικες εισάχθηκαν από τον Elias το 1955 ως εναλλακτική επιλογή έναντι των μπλοκ κωδίκων. Λίγο αργότερα, οι Wozencraft και Reiffen πρότειναν την ακολουθιακή αποκωδικοποίηση ως αποδοτική μέθοδο αποκωδικοποίησης συνελικτικών κωδίκων με μεγάλα μήκη εξαναγκασμού και σύντομα έκαναν την εμφάνισή τους πειραματικές μελέτες. Το 1963 ο Massey πρότεινε μια λιγότερο αποδοτική αλλά ευκολότερα υλοποιήσιμη μέθοδο αποκωδικοποίησης, την καλούμενη αποκωδικοποίηση κατωφλίου (threshold decoding). Αυτή η εξέλιξη αποτέλεσε αφορμή για μια σειρά από πρακτικές εφαρμογές των συνελικτικών κωδίκων στην ψηφιακή μετάδοση σε τηλεφωνικά, δορυφορικά και ασύρματα κανάλια. Αργότερα, το 1967, ο Viterbi πρότεινε έναν αλγόριθμο αποκωδικοποίησης μέγιστης πιθανοφάνειας (maximum likelihood, ML), σχετικά εύκολα υλοποιήσιμο για αποκωδικοποιητή soft-απόφασης συνελικτικών κωδίκων με μικρά μήκη εξαναγκασμού. Ο αλγόριθμος Viterbi παράλληλα με εκδοχές soft-απόφασης της ακολουθιακής αποκωδικοποίησης οδήγησαν στην εφαρμογή των συνελικτικών κωδίκων σε διαστημικά και δορυφορικά συστήματα επικοινωνιών τη δεκαετία του ’70. Το 1974 οι Bahl, Cocke, Jelinek και Raviv (BCJR) εισήγαγαν έναν αλγόριθμο αποκωδικοποίησης μέγιστης εκ των υστέρων πιθανότητας (maximum a posteriori  probability, MAP) για συνελικτικούς κώδικες με άνισες εκ των προτέρων (a priori) πιθανότητες για τα bits πληροφορίας. Ο αλγόριθμος BCJR έχει βρει εφαρμογή πρόσφατα σε σχήματα αποκωδικοποίησης soft-απόφασης όπου οι εκ των προτέρων πιθανότητες των bits πληροφορίας μεταβάλλονται από υλοποίηση σε υλοποίηση.

 

Ο κωδικοποιητής

 

Στο σχήμα 1 βλέπουμε τη γενική μορφή ενός συνελικτικού κωδικοποιητή.

Σχήμα 1: Γενική μορφή συνελικτικού κωδικοποιητή

 

Συμβολίζουμε την ακολουθία εισόδου με  . Η ακολουθία αποτελείται από δυαδικά ψηφία (0 ή 1). Θα θεωρήσουμε ότι κάθε  μπορεί να είναι 0 ή 1 με ίση πιθανότητα και είναι ανεξάρτητο από τα υπόλοιπα.

Όπως βλέπουμε στο σχήμα, ο κωδικοποιητής αποτελείται από έναν καταχωρητή ολίσθησης  βαθμίδων, όπου  μια παράμετρος που ονομάζεται μήκος εξαναγκασμού, και από  modulo-2 αθροιστές. Το μήκος εξαναγκασμού αντιπροσωπεύει τον αριθμό των μετατοπίσεων κατά  bits για τις οποίες ένα bit πληροφορίας μπορεί να επηρεάσει την έξοδο του κωδικοποιητή. Σε κάθε μονάδα χρόνου,  bits εισέρχονται στις πρώτες  βαθμίδες του καταχωρητή. Παράλληλα, όλα τα bits που βρίσκονται στον καταχωρητή μετατοπίζονται κατάβαθμίδες προς τα δεξιά και οι λαμβάνονται διαδοχικά οι έξοδοι των  αθροιστών, ώστε να δώσουν τα κωδικά bits. Αυτά τα κωδικοποιημένα bits χρησιμοποιούνται έπειτα από το διαμορφωτή για τον καθορισμό των κυματομορφών που θα εκπεμφθούν στο κανάλι. Αφού έχουμε κωδικά bits για κάθε  bits πληροφορίας, ο κωδικός ρυθμός είναι .

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

Χρησιμοποιούνται διάφοροι τρόποι για αναπαράσταση ενός συνελικτικού κωδικοποιητή. Οι πιο δημοφιλείς είναι το διάγραμμα συνδέσεων, τα διανύσματα συνδέσεων, τα γεννήτορα πολυώνυμα, το διάγραμμα καταστάσεων, το διάγραμμα δέντρου και το διάγραμμα trellis. Θα τις περιγράψουμε όλες στη συνέχεια μέσα από ένα παράδειγμα ενός (2,1) συνελικτικού κωδικοποιητή.

Στο σχήμα 2 βλέπουμε το διάγραμμα συνδέσεων ενός (2,1) συνελικτικού κωδικοποιητή με μήκος εξαναγκασμού . Η επιλογή των συνδέσεων είναι αυτή που χαρακτηρίζει τον κάθε κώδικα. Κάθε αλλαγή στις συνδέσεις έχει σαν αποτέλεσμα ένα διαφορετικό κώδικα. Φυσικά οι συνδέσεις δεν επιλέγονται αυθαίρετα. Η επιλογή γίνεται έτσι ώστε να ικανοποιούνται ορισμένα κριτήρια. Θα αναφερθούμε αναλυτικά για αυτό το θέμα σε επόμενη ενότητα.

Σχήμα 2: Διάγραμμα συνδέσεων ενός (2,1) συνελικτικού κωδικοποιητή

 

Αν και οι συνελικτικοί κώδικες θεωρητικά δεν αποτελούν μπλοκ κώδικες, συνήθως εξαναγκάζονται σε μια μπλοκ δομή λόγω περιοδικής αποκοπής. Αυτή απαιτεί την είσοδο  μηδενικών bits στον καταχωρητή μετά το τέλος της ακολουθίας πληροφορίας, για να «καθαριστεί», όπως λέμε, ο καταχωρητής. Εφόσον τα επιπλέον μηδενικά δε συνιστούν επιπλέον πληροφορία, ο ισοδύναμος κωδικός ρυθμός πέφτει κάτω από την τιμή . Για μεγάλες περιόδους αποκοπής όμως, η διαφορά είναι σχεδόν αμελητέα.

 

 

Αναπαράσταση με διανύσματα συνδέσεων

 

Ένας τρόπος αναπαράστασης του κωδικοποιητή είναι μέσω μιας ομάδας  διανυσμάτων συνδέσεων, ενός για κάθε modulo-2 αθροιστή. Κάθε διάνυσμα έχει διάσταση  και περιγράφει τη σύνδεση του καταχωρητή με τον εν λόγω αθροιστή. Μια μονάδα στην -στη θέση του διανύσματος υποδεικνύει ότι η αντίστοιχη βαθμίδα του καταχωρητή ολίσθησης είναι συνδεδεμένη στον αθροιστή, ενώ ένα μηδενικό υποδεικνύει ότι δεν υπάρχει σύνδεση της θέσης αυτής του καταχωρητή με τον αθροιστή. Για τον κωδικοποιητή του παραδείγματος μπορούμε να γράψουμε

= 1 1 1

= 1 0 1

Ας υποθέσουμε τώρα ότι η ακολουθία πληροφορίας = 1 0 1 εισέρχεται στον κωδικοποιητή του παραδείγματος. Στο σχήμα 3 φαίνεται η διαδικασία της κωδικοποίησης της ακολουθίας αυτής. Όπως βλέπουμε, τις χρονικές στιγμές ,  και  εισέρχονται διαδοχικά στον καταχωρητή, ένα κάθε φορά, τα bits πληροφορίας. Στη συνέχεια, τις χρονικές στιγμές   και   εισέρχονται  μηδενικά για τον καθαρισμό του καταχωρητή, εξασφαλίζοντας έτσι ότι και το τελευταίο bit πληροφορίας θα περάσει από όλες τις βαθμίδες του καταχωρητή. Η ακολουθία εξόδου είναι η 1 1 1 0 0 0 1 0 1 1, όπου το αριστερότερο σύμβολο αντιστοιχεί στην πρώτη χρονικά εκπομπή. Ολόκληρη η ακολουθία εξόδου είναι απαραίτητη για την αποκωδικοποίηση του μηνύματος, ακόμη και τα κωδικά σύμβολα που προέκυψαν από τη διαδικασία του καθαρισμού.

Σχήμα 3: Διαδικασία συνελικτικής κωδικοποίησης ακολουθίας πληροφορίας

 

Μπορούμε να προσεγγίσουμε τη λειτουργία του κωδικοποιητή μέσα από την έννοια της κρουστικής απόκρισης, της απόκρισης δηλαδή του κωδικοποιητή σε ένα και μοναδικό bit που μετακινείται στις βαθμίδες του. Στον παρακάτω πίνακα βλέπουμε τις εξόδους του κωδικοποιητή του παραδείγματος, καθώς μετακινείται μέσα του μια μονάδα.

 

Περιεχόμενα καταχωρητή

Έξοδοι κωδικοποιητή

1 0 0

1

1

0 1 0

1

0

0 0 1

1

1

 

Η κρουστική απόκριση του κωδικοποιητή είναι λοιπόν η  11 10 11.

Γνωρίζοντας την κρουστική απόκριση ενός κωδικοποιητή, μπορεί κανείς να βρει την ακολουθία εξόδου για μια συγκεκριμένη ακολουθία εισόδου μέσω γραμμικού αθροίσματος μετατοπισμένων κρουστικών αποκρίσεων. Στο παράδειγμά μας, για την ακολουθία εισόδου = 1 0 1, αυτό γίνεται ως εξής:

 

Ακολουθία εισόδου

Ακολουθία εξόδου

1

11

10

11

 

 

0

 

00

00

00

 

1

 

 

11

10

11

Modulo-2 άθροισμα

11

10

00

10

11

 

Παρατηρούμε ότι λάβαμε την ίδια ακολουθία εξόδου όπως και πριν, κάτι που δείχνει ότι οι συνελικτικοί κώδικες είναι γραμμικοί. Η διαδικασία που μόλις είδαμε αποτελεί στην ουσία τη διακριτή συνέλιξη της ακολουθίας εισόδου με την κρουστική απόκριση του κωδικοποιητή. Από εκεί προκύπτει και η ονομασία συνελικτικός κωδικοποιητής.

Εδώ να σημειώσουμε ότι είναι δυνατό να συμβολίσουμε ένα συνελικτικό κώδικα και με τη μορφή ενός ημιάπειρου γεννήτορα πίνακα βασισμένου στην κρουστική απόκριση. Ο πίνακας κατασκευάζεται με τη μετατόπιση της κρουστικής απόκρισης του κώδικα κατά  θέσεις προς τα δεξιά από γραμμή σε γραμμή.

 

User login

Enter your username and password here in order to log in on the website: