Ανάλυση επίδοσης σφάλματος σχημάτων τούρμπο κωδίκων με αναδιατάκτες άρτιων-περιττών θέσεων, βάσει του φάσματος αποστάσεών τους

Abstract

In the year 1948 "A Mathematical Theory of Communication" is formulated by Claude E. Shannon, overturning the common belief of engineers that transmission rate and error performance are antagonistic. According to the new theory, both the transmission rate can be arbitrarily close to its maximum, channel capacity, and the error rate arbitrarily low; suffice it for the communication system to employ channel codes. Despite the marked progress since then towards the realization of this twofold promise, operating close to capacity started establishing itself as practically infeasible. In 1993 this second belief is overturned as well via the presentation—by another Claude—of an encoder/decoder operating within 0.5 dB of the capacity; turbo codes. The present doctoral thesis constitutes a theoretical treatment on the subject of interleaver design for turbo codes. We consider the odd-even constraint, which makes information symbols at even (odd) positions lie at even (odd) positions after the interleaver as well, and perform an analytical comparison of the error performance of three turbo-coded schemes when they do and do not adopt it. These schemes are symmetric unpunctured turbo codes, punctured turbo codes, and turbo trellis-coded modulation. The analysis is based on the mathematical and experimental computation of the average distance spectrum of these schemes’ random ensembles, it is exemplified—for the first two ones—via union bounds, and it is validated through extensive Monte Carlo simulations over the assumed channels. Concretely, regarding the first scheme we introduce new weight enumerators in order to capture the effects of the constraint upon the lower part of its spectrum. We thus show that the constraint does not affect the interleaver gain—as is believed by a part of the literature—, but the multiplicities. As for the second scheme, we highlight weaknesses of the "uniform error protection conjecture" stated in the literature, which causally relates the constraint with the performance improvement, and replace it by the distance spectrum theory. The theory’s power, as compared to the conjecture’s one, is exemplified for three interleaver structures: random, S-random and block interleavers. Regarding the third scheme, we discover a phenomenon that takes place upon the removal of the constraint, which we call "probability leakage," tending to make the spectrum of the underlying turbo code densen. Probability leakage offers a new understanding of the constraint’s operation. The thesis is completed with a fourth scheme, turbo space-time coded modulation, for which the constraint’s behavior is examined via simulations over two multiple-input multiple-output channels. On the one hand, the odd-even constraint enjoys popularity within the turbo codes lying in a number of modern communication standards, on the other hand it has attracted controversies or misconceptions over the literature. The present thesis resolves some of them and paves the way for the resolution of others.

Το έτος 1948 διατυπώνεται «Μια Μαθηματική Θεωρία Επικοινωνίας» από τον Claude E. Shannon, η οποία ανατρέπει τη διάχυτη πεποίθηση των μηχανικών πως ρυθμός μετάδοσης και επίδοση σφάλματος είναι μεγέθη αντικρουόμενα. Για τη νέα θεωρία, και ο ρυθμός μετάδοσης μπορεί να είναι οσοδήποτε κοντά στον μέγιστο, τη χωρητικότητα καναλιού, και ο ρυθμός σφαλμάτων οσοδήποτε μικρός· αρκεί το σύστημα επικοινωνίας να χρησιμοποιεί κώδικες καναλιού. Παρά τη σημειούμενη πρόοδο, έκτοτε, προς την πραγματοποίηση της διπλής αυτής υπόσχεσης, η λειτουργία κοντά στη χωρητικότητα άρχισε να παγιώνεται ως πρακτικά ανέφικτη. Το 1993 σημειώνεται η ανατροπή της δεύτερης αυτής πεποίθησης με την παρουσίαση —από έναν έτερο Claude— ενός (απο)κωδικοποιητή που λειτουργούσε μεταξύ 0.5 dB από τη χωρητικότητα: των κωδίκων τούρμπο. Η παρούσα διδακτορική διατριβή αποτελεί μια θεωρητική εργασία στο αντικείμενο της σχεδίασης αναδιατάκτη για τούρμπο κώδικες. Θεωρούμε τη συνθήκη «άρτια-περιττά», η οποία επιβάλλει στα σύμβολα πληροφορίας των άρτιων (περιττών) θέσεων να βρίσκονται σε άρτιες (περιττές) θέσεις και μετά τον αναδιατάκτη, και πραγματοποιούμε μιαν αναλυτική σύγκριση της επίδοσης σφάλματος τριών σχημάτων τούρμπο κωδίκων χωρίς και με αυτήν: των συμμετρικών μη διάτρητων τούρμπο κωδίκων, των διάτρητων, και της τούρμπο τρέλις κωδικοποιημένης διαμόρφωσης. Η ανάλυση βασίζεται στον μαθηματικό και πειραματικό υπολογισμό του μέσου φάσματος αποστάσεων τυχαίων χώρων των σχημάτων, καταγράφεται —για τα δύο πρώτα— σε φράγματα ένωσης, κι επαληθεύεται από εκτενείς Monte Carlo προσομοιώσεις στα εκάστοτε θεωρούμενα κανάλια. Συγκεκριμένα, για το πρώτο σχήμα εισάγουμε καινούριους απαριθμητές βάρους με σκοπό την αποτύπωση των επιπτώσεων της συνθήκης στο χαμηλότερο τμήμα του φάσματός του. Δείχνουμε, έτσι, ότι η συνθήκη δεν επηρεάζει το κέρδος αναδιατάκτη —όπως πιστεύεται από μερίδα της αρθρογραφίας—, αλλά τις πολλαπλότητες. Για το δεύτερο σχήμα αναδεικνύουμε αδυναμίες της εκεί διατυπωθείσας «εικασίας της ομοιόμορφης προστασίας», η οποία συνδέει αιτιακά τη συνθήκη με τη βελτίωση της επίδοσης, και την αντικαθιστούμε με τη θεωρία του φάσματος αποστάσεων. Η ισχύς της δεύτερης έναντι της πρώτης αναδεικνύεται για τρεις δομές αναδιατακτών: τους τυχαίους, S-τυχαίους και μπλοκ. Για το τρίτο σχήμα ανακαλύπτουμε ένα φαινόμενο που λαμβάνει χώρα με την αφαίρεση της συνθήκης, το οποίο ονομάζουμε «διαρροή πιθανότητας», με τάσεις πύκνωσης του φάσματος του υποκείμενου τούρμπο κώδικα. Η διαρροή πιθανότητας προσφέρει μια καινούρια κατανόηση της λειτουργίας της συνθήκης. Η διατριβή ολοκληρώνεται με ένα τέταρτο σχήμα, την τούρμπο κωδικοποιημένη διαμόρφωση χώρου-χρόνου, για το οποίο μελετάται η συμπεριφορά της συνθήκης μέσω προσομοιώσεων σε δύο κανάλια πολλαπλών εισόδων/εξόδων. Η συνθήκη άρτια-περιττά αφενός είναι δημοφιλής στους τούρμπο κώδικες σύγχρονων προτύπων επικοινωνίας, αφετέρου έχει αποτελέσει πεδίο αντιγνωμιών ή παρανοήσεων στην αρθρογραφία. Με την παρούσα διατριβή ορισμένες από αυτές λύνονται, ενώ άλλες οδηγούνται προς τη λύση τους.