Le principe de calcul stochastique appliqué au décodage des turbocodes : conception, implémentation et prototypage sur circuit FPGA

The publication of turbo codes in 1993 proved that there were error-correcting codes with performance close to the theoretical limit and which can be used in industrial products. Quickly, turbo codes have been adopted in several standards such as DVB-RCS, UMTS, CDMA2000 and 3GPP-LTE. The increasing demand for high throughput applications in broadband applications until 1 Gb/s and beyond is strongly calling for high-speed turbo decoder implementations, thus leading to new challenges. An alternative approach was explored in this thesis: the decoding of error-correcting codes based on a stochastic representation of information. Principles of stochastic computation were first presented in the 1960¿s as a method to carry out complex operations with a low hardware complexity. The main feature of this method is that the probabilities are converted into streams of random bits using Bernoulli sequences, in which the information is given by the statistics of the bits. As a result, complex arithmetic operations on probabilities are transformed into operations on bits using elementary logic gates. The application of stochastic calculation in iterative decoding of error-correcting codes leads tovery simple physical structures of computation nodes. The objective of this thesis is to apply the stochastic decoding approach to the turbo codes. Our first contribution shows that a stochastic turbo decoder architecture can be obtained with no significant loss of performance. However, a major challenge in the implementation of stochastic turbo decoders is to improve the decoding throughput. In order to solve this challenge, we have proposed two efficient solutions: the transformation of stochastic additions into the exponential domain and the exploration of new parallelism schemes. The first technique consists in replacing the stochastic additions by simple operations after exponential transformations. This technique allows to reduce the computational complexity, and to improve the decoding throughput. The second technique is to represent a probability by several parallel stochastic streams. This method also allows us to compensate the correlation problem. These two techniques have resulted in stochastic convolutional decoders and turbo decoders with performances similar to the ones of conventional decoders. Finally, the proposed architectures for stochastic convolutional decoders and stochastic turbo decoders were implemented on programmable devices (FPGAs). The stochastic turbo decoder prototype demonstrates the feasibility of a stochastic turbo decoder in terms of performance and complexity. In addition, it enables many prospects for this alternative integration solution.Depuis leur publication en 1993 et leur exploitation dans le domaine des communications numériques, les turbocodes ont été adoptés dans de nombreux standards de télécommunications (UMTS, CDMA2000, LTE). Avec le développement des services sans-fil, le besoin de turbo- décodeurs à débit jusqu'au Gbits/s devient incontournable. Or, les techniques conventionnelles d'exploitation du parallélisme et de réduction des chemins critiques atteignent leur limite. Une approche alternative a été explorée dans cette thèse : le décodage de codes correcteurs d'erreurs à partir d'une représentation stochastique de l'information. Le calcul stochastique fut proposé dans les années 1960 comme une méthode traitant des opé- rations arithmétiques complexes pour un faible coût matériel. Pour ce faire, les probabilités sont converties en des flux de bits aléatoires dans lesquels l'information est représentée par des statis- tiques de bits. Des opérations arithmétiques complexes sur les probabilités sont transformées en des opérations sur les bits utilisant des portes logiques. Ainsi, l'application du calcul stochastique au décodage itératif de codes correcteurs d'erreurs favorise des structures matérielles simples pour les noeuds de calcul. L'objectif principal de cette thèse fut d'étendre l'approche stochastique au décodage de tur- bocodes. Dans un premier temps, nous avons proposé une première architecture pour un turbo- décodeur stochastique. Le principal défi fut ensuite d'augmenter le débit. Pour ce faire, nous avons considéré deux techniques : le passage dans le domaine exponentiel et l'exploitation du parallélisme. La première technique consiste à remplacer l'addition stochastique par des opérations plus simples dans le domaine exponentiel. Cette technique a permis d'une part de réduire la complexité calculatoire, et d'autre part, d'améliorer le débit de décodage. La deuxième technique est de représenter une probabilité par plusieurs flux stochastiques en parallèle. Cette méthode permet en outre de pro- poser une nouvelle approche pour compenser le problème de corrélation. L'exploitation de ces deux techniques a permis d'aboutir à un décodage stochastique pour les codes convolutifs et les turbocodes ayant des performances similaires à celles de décodeurs classiques. Enfin, les architectures proposées ont été intégrées dans un circuit configurable FPGA. Le prototype de turbo-décodeur stochastique n'a pas pu nous fournir un débit de l'ordre du Gbits/s comme souhaité. Cependant, il a permis de démontrer la faisabilité matérielle d'un turbo-décodeur stochastique en assurant de bonnes performances de décodage. En outre, ce démonstrateur a fait apparaître de nombreuses perspectives pour cette solution d'intégration alternative