High-Speed decoding of convolutional Turbo Codes
Institution:
LorientDisciplines:
Directors:
Abstract EN:
Turbo codes are built as a concatenation of several convolutional codes separated by interleavers. In 1993, they have revolutionized error correcting coding by approaching within a few tenths of a decibel the Shannon limit. This performance is even more astonishing because the iterative decoding principle enables the decoder to be implemented in hardware with a relative low complexity. Due to their success, they are now widely used in practical systems and open standards. The increasing demand for high throughput applications in broadband applications is strong)y calling for high-speed decoder implementations, thus leading to new challenges. The objective of this thesis is to study high-throughput decoding architectures offering the best throughput versus complexity trade-off. We first laid down a simple expression to evaluate the benefits of an architecture in terms of throughput and efficiency. The application of this model to turbo decoding highlighted three typical parameters influencing the throughput and efficiency of the decoder : the degree of parallelism, the ratio of utilization (activity) of the processing units and the clock frequency. We tackled each of these points by investigating a large spectrum of possibilities of the design space, ranging from the joint code and decoder design to the optimization of the decoder architecture for a given code or set of codes. We first proposed a new coding scheme called Multiple Slice Turbo Codes making possible to minimize the memory requirements of the decoder using the parallel decoding of a the received codeword by several soft-input soft-output processors. In order to solve the resulting concurrent accesses to the memory, we designed a novel hierarchical interleaver. Second, we explored several solutions for improving the activity of the processors including the usage of a hybrid parallel/serial architecture and the introduction of two new schedules for parallel decoding: one schedule internal to the processors, and another at a more global level in association with an adapted constrained interleaver. Finally, thanks to an original method to reduce the critical path in the recursive computation of state metrics, we obtained, at no cost on a FPGA circuit, a doubling of the maximal clock frequency of the decoder. Most of the w techniques developed in this thesis were validated by designing a turbo decoder for the wireless broadband access standard WiMAX (IEEE 802. 16) that achieves excellent error decoding performance reaching a throughput of 100Mbit/s on a single FPGA.
Abstract FR:
Les turbocodes sont des codes obtenus par une concaténation de plusieurs codes convolutifs séparés par des entrelaceurs. En 1993, ils ont révolutionné le domaine du codage correcteur d’erreurs en s’approchant à quelques dixièmes de décibels de la limite théorique de Shannon. Ces performances sont d'autant plus remarquables que le principe itératif permet d'en effectuer le décodage avec une complexité matérielle limitée. Le succès des turbocodes s'est traduit par leur introduction dans plusieurs standards de communication. Les besoins croissants dans le domaine des réseaux large bande, nécessitent des implantations hauts débits qui posent de nouvelles problématiques L'objectif de cette thèse est d'étudier des architectures de décodage à haut débit offrant le meilleur compromis en terme de débit sur complexité. Dans un premier temps, nous avons proposé un modèle simple permettant d'exprimer le débit et l'efficacité d'une architecture. Ce modèle appliqué au turbo décodage met en évidence trois paramètres caractéristiques ayant un impact sur le débit et l'efficacité du décodeur : le degré de parallélisme, le taux d'utilisation (activité) des unités de calcul cl la fréquence d'horloge. Nous avons abordé chacun de ces points en explorant un large spectre de possibilités de l'espace de conception allant de la construction conjointe du code et du décodeur à l'optimisation directe des architectures de décodage pour un code ou un ensemble de codes prédéfinis. Nous avons tout d'abord proposé un nouveau schéma de codage appelé turbocodes à roulettes permettant de minimiser la memoire du décodeur par un décodage en parallèle d'un mot de code reçu par plusieurs processeurs à entrée et sortie souples. Afin de résoudre le problème des accès concurrents aux mémoires qui en résulte, nous avons conçu un nouvel entrelaceur hiérarchique. Nous avons ensuite exploré plusieurs solutions permettant d'améliorer l'activité des processeurs utilisation d'une architecture hybride série/parallèle et proposition de nouveaux séquencements au niveau interne des processeurs, et aussi au niveau global en association avec la construction d'entrelaceurs contraints adaptés. Enfin grace à méthode originale de réduction du chemin critique du calcul récursif des métriques de nœuds, nous avons obtenu, sans coût matériel supplémentaire pour un circuit FPGA, un doublement de la fréquence d'horloge du décodeur. La plupart des techniques développées dans cette thèse ont été validées par la réalisation d'un turbo-décodeur pour le standard d'accès sans-fil large bande WiMAX (IEEE 802. 16) qui atteint des performances de correction d'erreur excellentes pour un débit atteignant 100 Mbit/s sur un seul circuit FPGA.