Contribution to the construction and the decoding of polar codes

Dans un monde où les flux de données sont toujours plus intenses et omniprésents, les codes correcteurs d’erreurs constituent une composante essentielle aux systèmes de télécommunications, en permettant de compenser l’altération inévitable du message lors de la transmission, grâce à l’ajout de redondance. Dernière famille de codes à avoir été découverte, en 2008, les codes polaires ont rapidement attiré l’attention des chercheurs par leur aptitude à garantir une probabilité d’erreur arbitrairement faible pour tout rendement inférieur ou égal à la capacité du canal de propagation – la limite théorique, définie par Shannon en 1948. Tout récemment, ces codes ont été adoptés pour être utilisés dans la Cinquième génération de standards pour la téléphonie mobile 5G. Cette thèse porte sur l’étude de cette famille de codes face aux contraintes applicatives rencontrées en pratiques, et notamment dans la 5G, à travers les deux axes principaux que sont la construction des codes et leur décodage en longueur finie.Après avoir passé en revue la définition et la caractérisation des codes polaires, ainsi que les aspects relatifs au spectre des distances, cette thèse explore la question de la flexibilité des codes en termes de longueurs, à l’aide des techniques de poinçonnage et de raccourcissement, et développe une méthodes pour optimiser le choix des motifs de sorte à minimiser le taux d’erreur pour le décodeur par annulation successive (SC, pour successive cancellation, en anglais). Dans un deuxième temps, un nouvel algorithme de décodage à inversion est introduit, permettant une amélioration significative des performances par rapport à l’état de l’art pour une complexité moyenne réduite et proche de celle du simple décodeur SC. Finalement, la question de l’utilisation des codes polaires avec les modulations d’ordre supérieur est abordée. Tout d’abord, les deux principales approches de modulations codées utilisant un code binaire, à savoir la modulation à entrelacement de bit et la modulation multi-niveaux, sont considérées, et il est mis en évidence le net avantage de la deuxième citée. Par suite, l’utilisation de codes polaires non-binaires est envisagée et il est montré qu’au prix d’une complexité de décodage supérieure, ceux-ci sont en mesure de surpasser leurs homologues binaires.In a world of intensive and widespread numeric datafow, the use of error correcting codes has become an essential aspect of telecommunication systems, by allowing to compensate the unavoidable alteration of the messages during the transmission, by means of additionnal redundancy to the initial message. Last family of codes to be discovered, in 2008, polar codes have soon experienced a large interest of the community, due to their ability to achieve the Shannon capacity, namely the theoretical limit of the information rate, defned by Shannon in 1948. Very recently, these codes have been adopted in the fifth generation of cellular mobile communications 5G. This thesis concentrates on the analysis of this family of codes regarding constraints of practical systems, including in 5G, through the two major isues of the construction of the code and the decoding in finite length.After reviewing the definition and the caracterisation of polar codes, and addressing the question of the spectrum distance, this thesis considers the issue of the flexibility of the codes as function of the codelength, using either puncturing or shortening techniques, andd escribes a new method to select the pattern so as to minimize the error rate under succssive cancellation decoding (SC). Secondly, a new bit-fipping decoding algorithm is proposed, improving signifcantly the performance compared to state-of-the-art approach,while offering a reduced average complexity, which stays close to the one of the SC decoder. Thirdly, the issue of the use of polar codes with high order modulation is considered. On the one hand, the case of coded modulations, where a high order modulation is combined with binary codes, is considered throughthe bit-interleaved coded modulation and the multilevel coded modulation, and it is shown that the second one is very well suitable for polar codes. On the other hand, the case of non-binary codes, which can be mapped directly to the constellation, are considered and it is revealed they are able to surpass their binary counterpart at the cost of additionnal decoding complexity