Les codes polaires constituent une classe de codes correcteurs d’erreurs inventés récemment qui suscite l’intérêt des chercheurs et des industriels, comme en atteste leur sélection pour le codage des canaux de contrôle dans la prochaine génération de téléphonie mobile (5G). Un des enjeux des futurs réseaux mobiles est la virtualisation des traitements numériques du signal, et en particulier les algorithmes de codage et de décodage. Afin d’améliorer la flexibilité du réseau, ces algorithmes doivent être décrits de manière logicielle et être déployés sur des architectures programmables. Une telle infrastructure de réseau permet de mieux répartir l’effort de calcul sur l’ensemble des noeuds et d’améliorer la coopération entre cellules. Ces techniques ont pour but de réduire la consommation d’énergie, d’augmenter le débit et de diminuer la latence des communications. Les travaux présentés dans ce manuscrit portent sur l’implémentation logicielle des algorithmes de décodage de codes polaires et la conception d’architectures programmables spécialisées pour leur exécution.Une des caractéristiques principales d’une chaîne de communication mobile est l’instabilité du canal de communication. Afin de remédier à cette instabilité, des techniques de modulations et de codages adaptatifs sont utilisées dans les normes de communication.Ces techniques impliquent que les décodeurs supportent une vaste gamme de codes : ils doivent être génériques. La première contribution de ces travaux est l’implémentation logicielle de décodeurs génériques des algorithmes de décodage "à Liste" sur des processeurs à usage général. En plus d’être génériques, les décodeurs proposés sont également flexibles.Ils permettent en effet des compromis entre pouvoir de correction, débit et latence de décodage par la paramétrisation fine des algorithmes. En outre, les débits des décodeurs proposés atteignent les performances de l’état de l’art et, dans certains cas, les dépassent.La deuxième contribution de ces travaux est la proposition d’une nouvelle architecture programmable performante spécialisée dans le décodage de codes polaires. Elle fait partie de la famille des processeurs à jeu d’instructions dédiés à l’application. Un processeur de type RISC à faible consommation en constitue la base. Cette base est ensuite configurée,son jeu d’instructions est étendu et des unités matérielles dédiées lui sont ajoutées. Les simulations montrent que cette architecture atteint des débits et des latences proches des implémentations logicielles de l’état de l’art sur des processeurs à usage général. La consommation énergétique est réduite d’un ordre de grandeur. En effet, lorsque l’on considère le décodage par annulation successive d’un code polaire (1024,512), l’énergie nécessaire par bit décodé est de l’ordre de 10 nJ sur des processeurs à usage général contre 1 nJ sur les processeurs proposés.La troisième contribution de ces travaux est également une architecture de processeur à jeu d’instructions dédié à l’application. Elle se différencie de la précédente par l’utilisation d’une méthodologie de conception alternative. Au lieu d’être basée sur une architecture de type RISC, l’architecture du processeur proposé fait partie de la classe des architectures déclenchées par le transport. Elle est caractérisée par une plus grande modularité qui permet d’améliorer très significativement l’efficacité du processeur. Les débits mesurés sont alors supérieurs à ceux obtenus sur les processeurs à usage général. La consommation énergétique est réduite à environ 0.1 nJ par bit décodé pour un code polaire (1024,512) avec l’algorithme de décodage par annulation successive. Cela correspond à une réduction de deux ordres de grandeur en comparaison de la consommation mesurée sur des processeurs à usage général. / Polar codes are a recently invented class of error-correcting codes that are of interest to both researchers and industry, as evidenced by their selection for the coding of control channels in the next generation of cellular mobile communications (5G). One of the challenges of future mobile networks is the virtualization of digital signal processing, including channel encoding and decoding algorithms. In order to improve network flexibility, these algorithms must be written in software and deployed on programmable architectures.Such a network infrastructure allow dynamic balancing of the computational effort across the network, as well as inter-cell cooperation. These techniques are designed to reduce energy consumption, increase through put and reduce communication latency. The work presented in this manuscript focuses on the software implementation of polar codes decoding algorithms and the design of programmable architectures specialized in their execution.One of the main characteristics of a mobile communication chain is that the state of communication channel changes over time. In order to address issue, adaptive modulationand coding techniques are used in communication standards. These techniques require the decoders to support a wide range of codes : they must be generic. The first contribution of this work is the software implementation of generic decoders for "List" polar decoding algorithms on general purpose processors. In addition to their genericity, the proposed decoders are also flexible. Trade-offs between correction power, throughput and decodinglatency are enabled by fine-tuning the algorithms. In addition, the throughputs of the proposed decoders achieve state-of-the-art performance and, in some cases, exceed it.The second contribution of this work is the proposal of a new high-performance programmable architecture specialized in polar code decoding. It is part of the family of Application Specific Instruction-set Processors (ASIP). The base architecture is a RISC processor. This base architecture is then configured, its instruction set is extended and dedicated hardware units are added. Simulations show that this architecture achieves through puts and latencies close to state-of-the-art software implementations on generalpurpose processors. Energy consumption is reduced by an order of magnitude. The energy required per decoded bit is about 10 nJ on general purpose processors compared to 1nJ on proposed processors when considering the Successive Cancellation (SC) decoding algorithm of a polar code (1024,512).The third contribution of this work is also the design of an ASIP architecture. It differs from the previous one by the use of an alternative design methodology. Instead of being based on a RISC architecture, the proposed processor architecture is part of the classof Transport Triggered Architectures (TTA). It is characterized by a greater modularity that allows to significantly improve the efficiency of the processor. The measured flowrates are then higher than those obtained on general purpose processors. The energy consumption is reduced to about 0.1 nJ per decoded bit for a polar code (1024,512) with the SC decoding algorithm. This corresponds to a reduction of two orders of magnitude compared to the consumption measured on general purpose processors.

The definition of polar codes given by Arikan is explicit, but the construction complexity is an issue. This is due to the exponential growth in the size of the output alphabet of the bit-channels as the codeword length increases. Tal and Vardy recently presented a method for constructing polar codes which controls this growth. They approximated each bit-channel with a “better” channel and a “worse” channel while reducing the alphabet size. They constructed a polar code based on the “worse” channel and used the “better” channel to measure the distance from the optimal channel. This thesis considers the knowledge gained from the perspective of the “better” channel. A method is presented using iterative upgrading of the bit-channels which successively results in a channel closer to the original one. It is shown that this approach can be used to obtain a channel arbitrarily close to the original channel, and therefore to the optimal construction of a polar code. / Graduate / 0984 / 0544 / arash.ghayoori@gmail.com

[pt] Erdal Arıkan introduziu os códigos polares em 2009. Trata-se de uma nova classe de códigos de correção de erros capaz de atingir o limite de Shannon. Usando decodificação de cancelamento sucessivo em lista, concatenada por verificação de redundância cíclica e a construções rápida de código, os códigos polares tornaram-se um código de correção de erros atraente e de alto desempenho para uso prático. Recentemente, códigos polares foram adotados para o padrão de geração 5th para sistemas celulares, mais especificamente para as informações de controle dos canais reverso e direto para os serviços de comunicação eMBB. No entanto, os códigos polares são limitados a comprimentos de bloco a potências de dois, devido a um produto Kronecker recursivo do kernel polarizador 2x2. Para aplicações práticas, é necessário fornecer técnicas de construção de código polar de comprimento flexível. Outro aspecto a ser analisado é o obtenção de uma técnica de construção de códigos polares de baixa complexidade e que tenha um ótimo desempenho em canal de ruído aditivo gaussiano branco, principalmente para blocos longos, inspirada na otimização da construção da aproximação gaussiana. Outro aspecto relevante é o poder de decodificação paralela do decodificador de propagação de crenças. Esta é uma alternativa para atender aos novos critérios de velocidade e latência previstos para o padrão de próxima geração para sistemas celulares. No entanto, ele precisa de melhorias de desempenho para tornar-se operacionalmente viável, tanto para 5G quanto para as gerações futuras. Nesta tese, três aspectos dos códigos polares são abordados: a construção de códigos com comprimentos arbitrários que visam maximizar a flexibilidade e eficiência dos códigos polares, o aprimoramento do método de construção por métodos gaussianos aproximação e a decodificação de códigos usando um algoritmo adaptativo de propagação de crenças reponderadas, bem como analisar quaisquer compromissos que afetem o desempenho da correção de erros. / [en] Erdal Arikan introduced the polar codes in 2009. This is a new class of error correction codes capable of reaching the Shannon limit. Using cyclic redundancy check concatenated list successive cancellation decoding and fast code constructs, polar codes have become an attractive, high-performance error correction code for practical use. Recently, polar codes have been adopted for the 5th generation standard for cellular systems, more specifically for the uplink and downlink control information for the extended Mobile Broadband (eMBB) communication services. However, polar codes are limited to block lengths to powers of two, due to a recursive Kronecker product of the 2x2 polarizing kernel. For practical applications, it is necessary to provide flexible length polar code construction techniques. Another aspect analyzed is the development of a technique of construction of polar codes of low complexity and that has an optimum performance on additive white Gaussian noise channels, mainly for long blocks, inspired by the optimization of the Gaussian approximation construction. Another relevant aspect is the parallel decoding power of the belief propagation decoder. This is an alternative to achieve the new speed and latency criteria foreseen for the next generation standard for cellular systems. However, it needs performance improvements to become operationally viable, both for 5G and for future generations. In this thesis, three aspects of polar codes are addressed: the construction of codes with arbitrary lengths that are intended for maximizing the flexibility and efficiency of polar codes, the improvement of the construction method by Gaussian approximation and the decoding of codes using an adaptive reweighted belief propagation algorithm, as well as the analysis of trade-offs affecting error correction performance.

Biometrics are widely used in identification systems, such as face, fingerprint, iris, etc. Polar code is the only code that can be strictly proved to achieve channel capacity, and it has been proved to be optimal for channel and source coding. In this degree project, our goal is to apply polar codes algorithms to biometric identification systems, and to design a biometric identification system with high identification accuracy, low system complexity, and good privacy preservation. This degree project has carried out specific and in-depth research in four aspects, following results are achieved: First, idea of polar codes is learnt, for example channel combination, channel splitting, successive cancellation decoding. The successive cancellation and successive cancellation list algorithm are also applied to encoding, which further realizes polar codes for source coding. Second, using autoencoder to process biometrics. Autoencoder is introduced to compress fingerprints into binary sequences of length 1024, it has 5 encoding layers and 12 decoding layers, achieved reconstruction error is 0.03. The distribution is close to Gaussian distribution, and compressed codes are quantized into binary sequences. Properties of sequences are similar with random sequences in terms of entropy, correlation, variance. Third, the identification system under Wyner-Ziv problem is studied with fingerprints. In enrollment phase, encoding algorithms are designed to compress biometrics, and in identification phase, decoding algorithms are designed to estimate the original sequence based on decoded results and noisy sequence. Maximum mutual information method is used to identify users. Results show that with smaller number of users, longer code length, smaller noise, then recognition error rate is lower. Fourth, human faces are used in the generated secret key system. After fully considering the trade off to achieve optimal results, in enrollment phase both public data and secure data are generated, in identification phase user’s index and secret key are estimated. A hierarchical structure is further studied. First, CNN is used to classify the age of faces, and then the generated secret key system is used for identification after narrowing the range. The system complexity is reduced by 80% and the identification accuracy is not reduced. / Biometriska kännetecken används i stor utsträckning i identifieringssystem, kännetecken såsom ansikte, fingeravtryck, iris, etc. Polär kod är den enda koden som strikt bevisats uppnå kanalkapacitet och den har visat sig vara optimal för kanal- och källkodning. Målet med detta examensarbete är att tillämpa polära kodalgoritmer på biometriska identifieringssystem, och att designa ett biometriskt identifieringssystem med hög identifieringsnoggrannhet, låg systemkomplexitet och bra integritetsskydd. Under examensarbetet har det genomförts specifik och djupgående forskning i fyra aspekter, följande resultat har uppnåtts: För det första introduceras idén om polära koder, till exempel kanalkombination, kanaluppdelning, successiv annulleringsavkodning. Algoritmerna för successiv annullering och successiv annulleringslista tillämpas även på kodning,vilket ytterligare realiserar polära koders användning för källkodning. För det andra används autoencoder för att bearbeta biometriska uppgifter. Autoencoder introduceras för att komprimera fingeravtryck till binära sekvenser med längden 1024, den har 5 kodningslager och 12 avkodningslager, det uppnådda rekonstruktionsfelet är 0,03. Fördelningen liknar en normaldistribution och komprimerade koder kvantiseras till binära sekvenser. Egenskaperna för sekvenserna liknar slumpmässiga sekvenser vad gäller entropi, korrelation, varians. För det tredje studeras identifieringssystemet under Wyner-Ziv-problemet med fingeravtryck. I inskrivningsfasen är kodningsalgoritmer utformade för att komprimera biometriska kännetecken, och i identifieringsfasen är avkodningsalgoritmer utformade för att estimera den ursprungliga sekvensen baserat på avkodade resultat och brusiga sekvenser. Maximal ömsesidig informationsmetod används för att identifiera användare. Resultaten visar att med ett mindre antal användare, längre kodlängd och mindre brus så är identifieringsfelfrekvensen lägre. För det fjärde används mänskliga ansikten i det genererade hemliga nyckelsystemet. Efter att noggrant ha övervägt kompromisser fullt ut för att uppnå det optimala resultatet genereras både offentlig data och säker data under registreringsfasen, i identifieringsfasen uppskattas användarens index och säkerhetsnyckel. En hierarkisk struktur studeras vidare. Först används CNN för att klassificera ålder baserat på ansikten och sedan används det genererade hemliga nyckelsystemet för identifiering efter att intervallet har begränsats. Systemkomplexiteten reduceras med 80% men identifieringsnoggrannheten reduceras inte.

Les applications dans le domaine des communications numériques deviennent de plus en plus complexes et diversifiées. En témoigne la nécessité de corriger les erreurs des messages transmis. Pour répondre à cette problématique, des codes correcteurs d’erreurs sont utilisés. En particulier, les Codes Polaires qui font l’objet de cette thèse. Ils ont été découverts récemment (2008) par Arıkan. Ils sont considérés comme une découverte importante dans le domaine des codes correcteurs d’erreurs. Leur aspect pratique va de paire avec la capacité à proposer une implémentation matérielle de décodeur. Le sujet de cette thèse porte sur l’exploration architecturale de décodeurs de Codes Polaires implémentant des algorithmes de décodage particuliers. Ainsi, le sujet gravite autour de deux algorithmes de décodage : un premier algorithme de décodage à décisions dures et un autre algorithme de décodage à décisions souples.Le premier algorithme de décodage, à décisions dures, traité dans cette thèse repose sur l’algorithme par annulation successive (SC) comme proposé originellement. L’analyse des implémentations de décodeurs montre que l’unité de calcul des sommes partielles est complexe. De plus,la quantité mémoire ressort de cette analyse comme étant un point limitant de l’implémentation de décodeurs de taille importante. Les recherches menées afin de palier ces problèmes montrent qu’une architecture de mise à jour des sommes partielles à base de registres à décalages permet de réduire la complexité de cette unité. Nous avons également proposé une nouvelle méthodologie permettant de revoir la conception d’une architecture de décodeur déjà existante de manière relativement simple afin de réduire le besoin en mémoire. Des synthèses en technologie ASIC et sur cibles FPGA ont été effectués pour caractériser ces contributions. Le second algorithme de décodage, à décisions souples, traité dans ce mémoire, est l’algorithme SCAN. L’étude de l’état de l’art montre que le seul autre algorithme à décisions souples implémenté est l’algorithme BP. Cependant, il nécessite une cinquantaine d’itérations pour obtenir des performances de décodages au niveau de l’algorithme SC. De plus, son besoin mémoire le rend non implémentable pour des tailles de codes élevées. L’intérêt de l’algorithme SCAN réside dans ses performances qui sont meilleures que celles de l’algorithme BP avec seulement 2 itérations.De plus, sa plus faible empreinte mémoire le rend plus pratique et permet l’implémentation de décodeurs plus grands. Nous proposons dans cette thèse une première implémentation de cetalgorithme sur cibles FPGA. Des synthèses sur cibles FPGA ont été effectuées pour pouvoir comparer le décodeur SCAN avec les décodeurs BP de l’état de l’art.Les contributions proposées dans cette thèse ont permis d’apporter une réduction de la complexité matérielle du calcul des sommes partielles ainsi que du besoin général du décodeur en éléments de mémorisation. Le décodeur SCAN peut être utilisé dans la chaîne de communication avec d’autres blocs nécessitant des entrées souples. Cela permet alors d’ouvrir le champ d’applications des Codes Polaires à ces blocs. / Applications in the field of digital communications are becoming increasingly complex and diversified. Hence, the need to correct the transmitted message mistakes becomes an issue to be dealt with. To address this problem, error correcting codes are used. In particular, Polar Codes that are the subject of this thesis. They have recently been discovered (2008) by Arikan. They are considered an important discovery in the field of error correcting codes. Their practicality goes hand in hand with the ability to propose a hardware implementation of a decoder. The subject of this thesis focuses on the architectural exploration of Polar Code decoders implementing particular decoding algorithms. Thus, the subject revolves around two decoding algorithms: a first decoding algorithm, returning hard decisions, and another decoding algorithm, returning soft decisions.The first decoding algorithm, treated in this thesis, is based on the hard decision algorithm called "successive cancellation" (SC) as originally proposed. Analysis of implementations of SC decoders shows that the partial sum computation unit is complex. Moreover, the memory amount from this analysis limits the implementation of large decoders. Research conducted in order to solve these problems presents an original architecture, based on shift registers, to compute the partial sums. This architecture allows to reduce the complexity and increase the maximum working frequency of this unit. We also proposed a new methodology to redesign an existing decoder architecture, relatively simply, to reduce memory requirements. ASIC and FPGA syntheses were performed to characterize these contributions.The second decoding algorithm treated in this thesis is the soft decision algorithm called SCAN. The study of the state of the art shows that the only other implemented soft decision algorithm is the BP algorithm. However, it requires about fifty iterations to obtain the decoding performances of the SC algorithm. In addition, its memory requirements make it not implementable for huge code sizes. The interest of the SCAN algorithm lies in its performances which are better than those of the BP algorithm with only two iterations. In addition, its lower memory footprint makes it more convenient and allows the implementation of larger decoders. We propose in this thesis a first implementation of this algorithm on FPGA targets. FPGA syntheses were carried out in order to compare the SCAN decoder with BP decoders in the state of the art.The contributions proposed in this thesis allowed to bring a complexity reduction of the partial sum computation unit. Moreover, the amount of memory required by an SC decoder has been decreased. At last, a SCAN decoder has been proposed and can be used in the communication field with other blocks requiring soft inputs. This then broadens the application field of Polar Codes.

In telecommunication, messages sent through a wireless medium often experience noise interfering with the signal in a way that corrupts the messages. As the demand for high throughput in the mobile network is increasing, algorithms that can detectand correct these corrupted messages quickly and accurately are of interest to the industry. Polar codes have been chosen by the Third Generation Partnership Project as the error correction code for 5G New Radio control channels. This thesis work aimed to investigate whether the polar code Successive Cancellation (SC) could be parallelized and if a graphics processing unit (GPU) can be utilized to optimize the execution time of the algorithm. The polar code Successive Cancellation was enhanced by implementing tree pruning and support for GPUs to leverage their parallelization. The difference in execution time between the concurrent and sequential versions of the SC algorithm with and without tree pruning was evaluated. The tree pruning SC algorithm almost always offered shorter execution times than the SC algorithm that did not employ treepruning. However, the support for GPUs did not reduce the execution time in these tests. Thus, the GPU is not certain to be able to improve this type of enhanced SC algorithm based on these results. / Meddelanden som överförs över ett mobilt nät utsätts ofta för brus som distorterar dem. I takt med att intresset ökat för hög genomströmning i mobilnätet har också intresset för algoritmer som snabbt och tillförlitligt kan upptäcka och korrigera distorderade meddelanden ökat. Polarkoder har valts av "Third Generation Partnership Project" som den klass av felkorrigeringskoder som ska användas för 5G:s radiokontrollkanaler. Detta examensarbete hade som syfte att undersöka om polarkoden "Successive Cancellation" (SC) skulle kunna parallelliseras och om en grafisk bearbetningsenhet (GPU) kan användas för att optimera exekveringstiden för algoritmen. SC utökades med stöd för trädbeskärning och parallellisering med hjälp av GPU:er. Skillnaden i exekveringstid mellan de parallella och sekventiella versionerna av SC-algoritmen med och utan trädbeskärning utvärderades. SC-algoritmen för trädbeskärning erbjöd nästan alltid kortare exekveringstider än SC-algoritmen som inte använde trädbeskärning. Stödet för GPU:er minskade dock inte exekveringstiden. Således kan man med dessa resultat inte med säkerhet säga att GPU-stöd skulle gynna SC-algoritmen.