This dissertation contains three topics: Polar codes with optimal exponents based on linear and nonlinear binary kernels of sizes up to 16, a design of rate-compatible polar codes, and a new proposed structure of joint source and channel coding based on low-density-parity-check (LDPC) codes. Polar codes are proposed by Arıkan with construction based on a linear kernel of dimension 2 with polarizing properties. The performance of a polar code is characterized asymptotically in terms of the exponent of its kernel. In this dissertation, constructions of linear and nonlinear binary kernels of dimensions up to 16 are presented. The constructed kernels are proved to have maximum exponents except in the case of nonlinear kernels of dimension 12 where we show that there exists only one possible exponent greater than that of the presented construction. From the results, the minimum dimension where a linear kernel with exponent greater than 0.5, the exponent of the linear kernel proposed by Arıkan, is 15, while this minimum dimension is 14 for nonlinear kernels. We also found that there is a linear kernel with maximum exponent up to dimension 11. The kernels of dimensions 13, 14, 15 with maximum exponents, although nonlinear over GF(2), are shown to be Z4-linear or Z2Z4-linear. In addition to exploring the asymptotic behavior of polar codes, we propose a design of finite block length rate-compatible polar codes suitable for HARQ communications. The central feature of the proposed design is established on the puncturing order chosen with low complexity on a base code of short length, which is then extended to the desired length. With the designed puncturing order, a practical rate-matching system which can be adjusted to any desired rate through puncturing or repetition under polarization is suggested. The proposed rate-matching system combines a channel interleaver and a bit-mapping procedure to preserve the polarization of the rate-compatible polar code family under bit-interleaved coded modulation systems. Simulation results on AWGN and fast fading channels with different modulation orders in both Chase combining and incremental redundancy HARQ communications are listed. For the third topic, we investigate a joint source and channel LDPC coding scheme in which the source compression and the channel coding matrices are designed jointly as two submatrices of a sparse matrix H. The sparse matrix H is constructed algebraically with a structure free of cycles of length 4 and serves as the parity-check matrix for joint decoding of the channel output symbols and untransmitted source symbols. The integrated design of the source and channel coding matrices strengthens the information exchange between the source symbols and the channel output parity-check symbols, which provides a good waterfall error performance of the coded system and low error-foor.

Polar codes are the first family of error-correcting codes that was proved to achieve the capacity of binary memoryless symmetric (BMS) channels with efficient encoding and decoding algorithms. They have been drawing increasing interests in both industrial and academic research, especially after being adopted by the 3rd generation partnership project (3GPP) group as the channel codes for the control channel of the 5th generation (5G) wireless systems. The main goal of this dissertation is to explore polar coding techniques, as well as improve the current state-of-the-art, thereby broadening the applications of polar codes. We begin by studying partial orders (POs) for the synthesized bit-channels of polar codes. We give an alternative proof of an existing PO for bit-channels with the same Hamming weight and use the underlying idea to extend the bit-channel ordering to some additional cases. The bit-channels with universal ordering positions for binary erasure channel (BEC), which are independent of the channel erasure probability, are verified for all of the code blocklengths. We also show the threshold behavior of the Bhattacharyya parameters of some bit-channels by approximating the threshold values. Then, we move on to the decoding algorithms and improved polar codes. Despite the impressive asymptotic behavior by channel polarization, empirical results indicate less impressive performance of the successive cancellation (SC) decoder for polar codes of short blocklengths, e.g., compared to low-density parity-check (LDPC) codes. We consider belief propagation list (BPL) decoding with a special family of factor-graph layer permutations called stable permutations (SPs) that preserve a specified information set when the corresponding bit permutations are applied to message bit indices. Then, we propose a new code construction methodology to interpolate between Reed-Muller (RM) and polar codes. The new family of hybrid RM-polar codes has superior performance under several decoding algorithms, including SC list (SCL), belief propagation (BP), BPL, and soft-cancellation list (SCANL). By taking advantage of an existing PO on bit-channels whose corresponding indices share the same Hamming weight, we analyze the complexity of the new construction method. Furthermore, we propose an algorithm of BP decoding for polar codes with a special family of large kernels called permuted kernels, in which the leftmost messages over the factor graph need to be permuted accordingly.

The dissertation provides polar coding techniques for a variety of source and channel models with applications to storage and communication networks. We first provide universal polar codes for asymmetric compound channels that avoid common randomness. A staircase alignment of polar blocks is considered in the code construction. An MDS code is used in each column achieving the universality and a scrambling technique is implemented for each column helping avoid common randomness. These compound asymmetric channels are used for modelling flash-memories, such as MLCs (multi-level cell flash memories), and TLCs (three-level cell flash memories) memories. Hence the proposed universal polar codes for asymmetric channels can be used for flash memory error correction. The costly noiseless channel model was used to model a flash memory device. Each of the voltage levels to which a flash memory cell can be programmed has an associated wear cost which reflects the damage caused to the cell by repeated programming to that level. Shaping codes that minimize the average cost per channel symbol for a specified rate and shaping codes that minimize the average cost per source symbol (i.e., the total cost) have been shown to reduce cell wear and increase the lifetime of the memory. Hence, we study polar shaping codes for costly noiseless channels minimizing total cost. We also study polar shaping codes for costly noisy channels for the design of efficient codes that combine wear reduction and error correction for use in a noisy flash memory device. A novel scheme based on polar codes is proposed to compress a uniform source when a side information correlated with the source is available at the receiver while the conditional distribution of the side information given the source is symmetric and unknown to the source. An adaptation of universal polar codes with an incorporation of the linear code duality between channel coding and Slepian-Wolf coding is used in the design of those codes. Optimal rate is achieved through the proposed codes for the source model. These codes can be used in a wireless sensor network where the measurements tracked at two different nodes are correlated and the correlation may not always be fixed due to environmental changes such as weather. The nodes communicate the information sensed or measured by them to a central location. Finally, we provide a capacity-achieving polar coding strategy on a multi-level 3-receiver broadcast channel in which the second receiver is degraded (stochastically) from the first receiver for the transmission of a public message intended for all the receivers and a private message intended for the first receiver. A chaining strategy, translating the ideas of superposition coding, rate-splitting and indirect coding into polar coding, is used in the construction. The codes designed for such a channel model and setting can be used for video and audio file transfer in a client-server network where the individual clients are a computer and two mobile phones. The two mobile phone clients just support audio application where the computer supports both audio and video applications.

The discovery of channel polarization and polar codes is universally recognized as an historic breakthrough in coding theory. Polar codes provably achieve the capacity of any memoryless symmetric channel, with low encoding and decoding complexity. Moreover, for short block lengths, polar codes under specific decoding algorithms are currently the best known coding scheme for binary-input Gaussian channels. Due to this and other considerations, 3GPP has recently decided to incorporate polar codes in the 5G wireless communications standard. Soon enough, a remarkably short time after their invention, we will be all using polar codes whenever we make a phone call or access the Internet on a mobile device. Our goal in this dissertation is to explore new frontiers in polar coding, thereby fundamentally advancing the current state-of-the-art in the field. Parts of the results are immediately relevant for successful deployment of polar codes in wireless systems, whereas other parts will focus on key theoretical problems in polar coding that have a longer time-horizon. We begin by studying the effect of the polarization kernels in the asymptotic behavior of polar codes. We show that replacing the conventional 2×2 kernel in the construction of polar codes with that of a larger size can reduce the gap to the capacity if the larger kernel is carefully selected. A heuristic algorithm is proposed that helps to find such kernels. Furthermore, we prove that a near-optimal scaling behavior is achievable if one is allowed to increase the kernel size as needed. We also study the computational complexity of decoding algorithms for polar codes with large kernels, which are viewed as their main implementation obstacle. Moving on to the decoding algorithms, we carefully analyze the performance of the successive cancellation decoder with access to the abstract concept of Arikan's genie. The CRC-aided successive-cancellation list decoding, the primary decoding method of polar codes, is commonly viewed as an implementation of the Arikan's genie. However, it comes short at completely simulating the genie since the auxiliary information (CRC) comes to the help only at the end of the decoding process. We overcome this problem by introducing the convolutional decoding algorithm of polar codes that is based on a high-rate convolutional pre-coder and utilizes Viterbi Algorithm to mimic the genie all the way through the SC decoding process. Lastly, we look into channels with deletions. A key assumption in the traditional polar coding is to transmit coded symbols over independent instances of the communication channel. Channels with memory and in particular, deletion channels, do not follow this rule. We introduce a modified polar coding scheme for these channels that depend on much less computational power for decoding than the existing solutions. We also extend the polarization theorems to provide theoretical guarantee and to prove the correctness of our algorithms.

A new class of provably capacity achieving error-correction codes, polar codes are suitable for many problems, such as lossless and lossy source coding, problems with side information, multiple access channel, etc. The first comprehensive book on the implementation of decoders for polar codes, the authors take a tutorial approach to explain the practical decoder implementation challenges and trade-offs in either software or hardware. They also demonstrate new trade-offs in latency, throughput, and complexity in software implementations for high-performance computing and GPGPUs, and hardware implementations using custom processing elements, full-custom application-specific integrated circuits (ASICs), and field-programmable-gate arrays (FPGAs). Presenting a good overview of this research area and future directions, High-Speed Decoders for Polar Codes is perfect for any researcher or SDR practitioner looking into implementing efficient decoders for polar codes, as well as students and professors in a modern error correction class. As polar codes have been accepted to protect the control channel in the next-generation mobile communication standard (5G) developed by the 3GPP, the audience includes engineers who will have to implement decoders for such codes and hardware engineers designing the backbone of communication networks.

- Treats joint source and channel decoding in an integrated way - Gives a clear description of the problems in the field together with the mathematical tools for their solution - Contains many detailed examples useful for practical applications of the theory to video broadcasting over mobile and wireless networks Traditionally, cross-layer and joint source-channel coding were seen as incompatible with classically structured networks but recent advances in theory changed this situation. Joint source-channel decoding is now seen as a viable alternative to separate decoding of source and channel codes, if the protocol layers are taken into account. A joint source/protocol/channel approach is thus addressed in this book: all levels of the protocol stack are considered, showing how the information in each layer influences the others. This book provides the tools to show how cross-layer and joint source-channel coding and decoding are now compatible with present-day mobile and wireless networks, with a particular application to the key area of video transmission to mobiles. Typical applications are broadcasting, or point-to-point delivery of multimedia contents, which are very timely in the context of the current development of mobile services such as audio (MPEG4 AAC) or video (H263, H264) transmission using recent wireless transmission standards (DVH-H, DVB-SH, WiMAX, LTE). This cross-disciplinary book is ideal for graduate students, researchers, and more generally professionals working either in signal processing for communications or in networking applications, interested in reliable multimedia transmission. This book is also of interest to people involved in cross-layer optimization of mobile networks. Its content may provide them with other points of view on their optimization problem, enlarging the set of tools which they could use. Pierre Duhamel is director of research at CNRS/ LSS and has previously held research positions at Thomson-CSF, CNET, and ENST, where he was head of the Signal and Image Processing Department. He has served as chairman of the DSP committee and associate Editor of the IEEE Transactions on Signal Processing and Signal Processing Letters, as well as acting as a co-chair at MMSP and ICASSP conferences. He was awarded the Grand Prix France Telecom by the French Science Academy in 2000. He is co-author of more than 80 papers in international journals, 250 conference proceedings, and 28 patents. Michel Kieffer is an assistant professor in signal processing for communications at the Université Paris-Sud and a researcher at the Laboratoire des Signaux et Systèmes, Gif-sur-Yvette, France. His research interests are in joint source-channel coding and decoding techniques for the reliable transmission of multimedia contents. He serves as associate editor of Signal Processing (Elsevier). He is co-author of more than 90 contributions to journals, conference proceedings, and book chapters. - Treats joint source and channel decoding in an integrated way - Gives a clear description of the problems in the field together with the mathematical tools for their solution - Contains many detailed examples useful for practical applications of the theory to video broadcasting over mobile and wireless networks

This book explains the philosophy of the polar encoding and decoding technique. Polar codes are one of the most recently discovered capacity-achieving channel codes. What sets them apart from other channel codes is the fact that polar codes are designed mathematically and their performance is mathematically proven. The book develops related fundamental concepts from information theory, such as entropy, mutual information, and channel capacity. It then explains the successive cancellation decoding logic and provides the necessary formulas, moving on to demonstrate the successive cancellation decoding operation with a tree structure. It also demonstrates the calculation of split channel capacities when polar codes are employed for binary erasure channels, and explains the mathematical formulation of successive cancellation decoding for polar codes. In closing, the book presents and proves the channel polarization theorem, before mathematically analyzing the performance of polar codes.