Polar codes were invented as the first error-correcting codes to achieve the capacity for the discrete channels with relatively low-complexity for encoding and decoding. However, this is only possible with significantly large code lengths which are not practical for many systems. Meanwhile, the performance of the finite-lengths polar codes is not competitive with other modern error-correcting codes. This can be attributed to the suboptimality of the decoding process and the relatively poor minimum Hamming distances. This thesis aims to improve the performance of polar codes. The contributions include improving the performance of the conventional successive cancellation decoder. This is based on a novel technique, namely one-step decision delay, which incorporates some extra computational nodes to the code tree. Also, this thesis presents two methods for increasing the Hamming distances of polar codes; in the first, the code rate remains unchanged, while in the second, that produces superior performance, a modest reduction in the code rate occurs. Both methods enhance the performance with using belief propagation decoder. In addition, the latency of the decoding process is reduced by applying the fast Hadamard transform decoder on polar codes for the first time. In this regard, a method to modify the encoder is presented for some lengths that are not normally compatible with the proposed decoder. Interestingly, this modification method has another advantage that in the sense that it increases the minimum Hamming distances of the codes. Furthermore, this thesis presents the utilisation of polar codes in some practical communication systems. Firstly, polar codes are examined over power line communication systems. In this respect, the construction of polar codes is analysed by using three different methods. Additionally, the practical performance of polar codes is illustrated for both single-carrier and multi-carrier channels. Secondly, this thesis explores polar codes for unequal error protection by partitioning the information sets into a number of subsets with different reliabilities. JPEG2000, which is an image compression method, is used for validating the advantages of the proposed technique. Moreover, a new joint source channel decoding is proposed from the combination of the polar decoder and JPEG2000 decoder in order to enhance the quality of the compressed images. Finally, polar codes are investigated for the energy transfer by presenting new subcodes that are chosen according to the weights of the produced codewords. In this context, two modes of energy transfer are presented. The proposed modes can successfully extend the lifetime of the receiver's battery.

In today’s society the ability to communicate with one another has grown, were a lot of focus is aimed towards speed in the telecommunication industry. For transmissions to become even faster, there are many ways to enhance transmission speeds of which error correction is one. Padding messages such that they are protected from noise, while using as few bits as possible and ensuring safe transmit is handled by error correction codes. Short codes with low complexity is a solution to faster transmission speeds. An error correction code which has gained a lot of attention since its first appearance in 2009 is Polar Codes. Polar Codes was chosen as the 3GPP standard for 5G control channel. The goal of the thesis is to develop and implement Polar Codes and rate matching according to the 3GPP standard 38.212. Polar Codes are then to be evaluated with different block sizes and rate matching settings. Finally Polar Code is compared with Convolutional code in a LTE-simulation environment. The performance evaluations are presented using BLER/(Eb/N0)-graphs. In this thesis a Polar encoder, rate matching and a Polar decoder (with Successive Cancellation algorithm) were successfully implemented. The simulation results show that Polar Codes performs better with longer block sizes and also has a better BLER-performance than Convolutional Codes when given the same message lengths.

Les réseaux de 5ème génération se caractérisent par la communication directe entre machines (M2M) et l’Internet des Objets, un réseau unifié d’objets connectés. Dans ce contexte, les appareils communicants sont des décideurs autonomes qui coopérent, coordonnent leurs actions et se reconfigurent de manière dynamique enfonction de leur environnement. L’enjeu est de développer des algorithmes efficaces pour coordonner les actions des appareils autonomes constituant le réseau.La théorie de l’information nous permet d’étudier le comportement de long-terme des appareils grâce aux distributions de probabilité conjointes. En particulier, nous sommes intéressés par la coordination forte, qui exige que la distribution induite sur les suites d’actions converge en distance L^1 vers une distribution i.i.d. cible.Nous considérons un model point-à-point composé d’une source d’information, d’un encodeur, d’un canal bruité, d’un décodeur, d’une information commune et nous cherchons à coordonner les signaux en entrée et en sortie du canal avec la source et sa reconstruction.Nos premiers résultats sont des bornes intérieures et extérieure pour la région de coordination forte, c’est-à-dire l’ensemble des distributions de probabilité conjointes réalisables et la quantité d’information commune requise.Ensuite, nous caractérisons cette région de coordination forte dans trois cas particuliers: lorsque le canal est parfait, lorsque le décodeur est sans perte et lorsque les variables aléatoires du canal sont indépendantes des variables aléatoires de la source. L’étude de ce dernier cas nous permet de remettre en cause le principe de séparation source-canal pour la coordination forte. Nous démontrons également que la coordination forte offre “gratuitement” des garanties de sécurité au niveau de la couche physique.Par ailleurs, nous étudions la coordination sous l’angle du codage polaire afin de développer des algorithmes de codage implémentables. Nous appliquons la polarisation de la source de manière à créer un schéma de codage explicite qui offre une alternative constructive aux preuves de codage aléatoires. / 5G networks will be characterized by machine to machine communication and the Internet of Things, a unified network of connected objects. In this context, communicating devices are autonomous decision-makers that cooperate, coordinate their actions, and reconfigure dynamically according to changes in the environment.To do this, it is essential to develop effective techniques for coordinating the actions of the nodes in the network.Information theory allows us to study the long-term behavior of the devices through the analysis of the joint probability distribution of their actions. In particular, we are interested in strong coordination, which requires the joint distribution of sequences of actions to converge to an i.i.d. target distribution in L^1 distance.We consider a two-node network comprised of an information source and a noisy channel, and we require the coordination of the signals at the input and at the output of the channel with the source and the reconstruction. We assume that the encoder and decoder share a common source of randomness and we introduce a state capturing theeffect of the environment.The first objective of this work is to characterize the strong coordination region, i.e. the set of achievable joint behaviors and the required minimal rates of common randomness. We prove inner and outer bounds for this region. Then, we characterize the exact coordination region in three particular cases: when the channel is perfect, when the decoder is lossless and when the random variables of the channel are separated from the random variables of the source.The study of the latter case allows us to show that the joint source-channel separation principle does not hold for strong coordination. Moreover, we prove that strong coordination offers “free” security guarantees at the physical layer.The second objective of this work is to develop practical codes for coordination: by exploiting the technique of source polarization, we design an explicit coding scheme for coordination, providing a constructive alternative to random coding proofs.

The objective of the proposed research is to develop and analyze coding schemes for information-theoretic security, which could bridge a gap between theory an practice. We focus on two fundamental models for information-theoretic security: secret-key generation for a source model and secure communication over the wire-tap channel. Many results for these models only provide existence of codes, and few attempts have been made to design practical schemes. The schemes we would like to propose should account for practical constraints. Specifically, we formulate the following constraints to avoid oversimplifying the problems. We should assume: (1) computationally bounded legitimate users and not solely rely on proofs showing existence of code with exponential complexity in the block-length; (2) a rate-limited public communication channel for the secret-key generation model, to account for bandwidth constraints; (3) a non-uniform and rate-limited source of randomness at the encoder for the wire-tap channel model, since a perfectly uniform and rate-unlimited source of randomness might be an expensive resource. Our work focuses on developing schemes for secret-key generation and the wire-tap channel that satisfy subsets of the aforementioned constraints.

Polar codes, recently invented by Arikan, are the first class of codes known to achieve the symmetric capacity for a large class of channels. The symmetric capacity is the highest achievable rate subject to using the binary input letters of the channel with equal probability. Polar code construction is based on a phenomenon called channel polarization. The encoding as well as the decoding operation of polar codes can be implemented with O(N logN) complexity, where N is the blocklength of the code. In this work, we study the factor graph representation of finite-length polar codes and their effect on the belief propagation (BP) decoding process over Binary Erasure Channel (BEC). Particularly, we study the parity-check-based (H-Based) as well as the generator based (G-based) factor graphs of polar codes. As these factor graphs are not unique for a code, we study and compare the performance of Belief Propagation (BP) decoders on number of well-known graphs. Error rates and complexities are reported for a number of cases. Comparisons are also made with the Successive Cancellation (SC) decoder. High errors are related to the so-called stopping sets of the underlying graphs. we discuss the pros and cons of BP decoder over SC decoder for various code lengths. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2012-01-31 17:10:59.955

[pt] Esta dissertação apresenta uma técnica de puncionamento orientada pela polarização para o projeto de códigos polares puncionados. A estratégia de puncionamento proposta consiste em reduzir a matriz geradora relacionando seu índice de linha com o princípio da polarização do canal. Os códigos puncionados construídos com base na polarização do canal são então considerados para a decodificação por cancelamento sucessivos (SC) com os bits perfurados conhecidos tanto no codificador como no decodificador. A Distância de Espectro (SD) e a Distância de Espectro Conjunta (JSD) são então utilizadas para análise de desempenho. Os resultados das simulações mostram que os códigos polares puncionados propostos superam os códigos polares puncionados existentes. / [en] This thesis presents a polarization-driven puncturing technique for the design of punctured polar codes. The proposed puncturing strategy consists of reducing the generator matrix by relating its row index based on the channel polarization principle. The punctured codes constructed based on channel polarization are then considered with successive cancellation (SC) decoding and punctured bits known to both the encoder and the decoder. The Spectrum Distance (SD) and the Joint Spectrum Distance (JSD) are then used to performance analysis. Simulation results show that the proposed punctured polar codes outperform existing punctured polar codes.

This dissertation has its focus on two different topics: 1. non-asymptotic analysis of polar codes as a new paradigm in error correcting codes with very promising features, and 2. network properties for wireless networks of practical size. In its first part, we investigate properties of polar codes that can be potentially useful in real-world applications. We start with analyzing the performance of finite-length polar codes over the binary erasure channel (BEC), while assuming belief propagation (BP) as the decoding method. We provide a stopping set analysis for the factor graph of polar codes, where we find the size of the minimum stopping set. Our analysis along with bit error rate (BER) simulations demonstrates that finite-length polar codes show superior error floor performance compared to the conventional capacity-approaching coding techniques. Motivated by good error floor performance, we introduce a modified version of BP decoding while employing a guessing algorithm to improve the BER performance. Each application may impose its own requirements on the code design. To be able to take full advantage of polar codes in practice, a fundamental question is which practical requirements are best served by polar codes. For example, we will see that polar codes are inherently well-suited for rate-compatible applications and they can provably achieve the capacity of time-varying channels with a simple rate-compatible design. This is in contrast to LDPC codes for which no provably universally capacity-achieving design is known except for the case of the erasure channel. This dissertation investigates different approaches to applications such as UEP, rate-compatible coding, and code design over parallel sub-channels (non-uniform error correction). Furthermore, we consider the idea of combining polar codes with other coding schemes, in order to take advantage of polar codes' best properties while avoiding their shortcomings. Particularly, we propose, and then analyze, a polar code-based concatenated scheme to be used in Optical Transport Networks (OTNs) as a potential real-world application The second part of the dissertation is devoted to the analysis of finite wireless networks as a fundamental problem in the area of wireless networking. We refer to networks as being finite when the number of nodes is less than a few hundred. Today, due to the vast amount of literature on large-scale wireless networks, we have a fair understanding of the asymptotic behavior of such networks. However, in real world we have to face finite networks for which the asymptotic results cease to be valid. Here we study a model of wireless networks, represented by random geometric graphs. In order to address a wide class of the network's properties, we study the threshold phenomena. Being extensively studied in the asymptotic case, the threshold phenomena occurs when a graph theoretic property (such as connectivity) of the network experiences rapid changes over a specific interval of the underlying parameter. Here, we find an upper bound for the threshold width of finite line networks represented by random geometric graphs. These bounds hold for all monotone properties of such networks. We then turn our attention to an important non-monotone characteristic of line networks which is the Medium Access (MAC) layer capacity, defined as the maximum number of possible concurrent transmissions. Towards this goal, we provide a linear time algorithm which finds a maximal set of concurrent non-interfering transmissions and further derive lower and upper bounds for the cardinality of the set. Using simulations, we show that these bounds serve as reasonable estimates for the actual value of the MAC-layer capacity.

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.