Polar encoding, described by Arikan in IEEE Transactions on Information Theory, Vol. 55, No. 7, July 2009, was a milestone for telecommunications. A Polar code distributes information among high and low-capacity channels, showing the possibility of achieving perfect channel capacity. The high-capacity channels allow almost noiseless transmission of data. When these channels are not high noise, reliability is achieved in the signal transmission. It starts to compete against codes such a Low-Density Parity-Check (LDPC) codes. Polar code can be also considered error correcting, based on the redundancy inherent in its structure. This feature makes polar encoding also applicable to digital quantum-resistant cryptography protocols. This work explores linear decoding at a first or single trial in the case of small losses or small number of bit-flipping, and repeated transmission for medium level losses. This is distinct from Arikans successive probabilistic decoding by application of probabilistic rules. Linear decoding is done directly from solving the linear equations connecting the codewords x and the received signals y after transmission via noisy channels. Numerical examples will be shown. Along with this work, programming in Mathematica language was used. Codes are available for copy-and-paste for Mathematica users to immediately try the described formalism.
Polar encoding, described by Arikan in IEEE Transactions on Information Theory, Vol. 55, No. 7, July 2009, was a milestone for telecommunications. A Polar code distributes information among high and low-capacity channels, showing the possibility of achieving perfect channel capacity. The high-capacity channels allow almost noiseless transmission of data. When these channels are not high noise, reliability is achieved in the signal transmission. It starts to compete against codes such a Low-Density Parity-Check (LDPC) codes. Polar code can be also considered error correcting, based on the redundancy inherent in its structure. This feature makes polar encoding also applicable to digital quantum-resistant cryptography protocols. This work explores linear decoding at a first or single trial in the case of small losses or small number of bit-flipping, and repeated transmission for medium level losses. This is distinct from Arikans successive probabilistic decoding by application of probabilistic rules. Linear decoding is done directly from solving the linear equations connecting the codewords x and the received signals y after transmission via noisy channels. Numerical examples will be shown. Along with this work, programming in Mathematica language was used. Codes are available for copy-and-paste for Mathematica users to immediately try the described formalism.
Holevo, Schumacher, and Westmoreland's coding theorem guarantees the existence of codes that are capacity-achieving for the task of sending classical data over a channel with classical inputs and quantum outputs. Although they demonstrated the existence of such codes, their proof does not provide an explicit construction of codes for this task. The aim of this paper is to fill this gap by constructing near-explicit “polar” codes that are capacity-achieving. The codes exploit the channel polarization phenomenon observed by Arikan for the case of classical channels. Channel polarization is an effect in which one can synthesize a set of channels, by “channel combining” and “channel splitting,” in which a fraction of the synthesized channels are perfect for data transmission, while the other channels are completely useless for data transmission, with the good fraction equal to the capacity of the channel. The channel polarization effect then leads to a simple scheme for data transmission: send the information bits through the perfect channels and “frozen” bits through the useless ones. The main technical contributions of this paper are threefold. First, we leverage several known results from the quantum information literature to demonstrate that the channel polarization effect occurs for channels with classical inputs and quantum outputs. We then construct linear polar codes based on this effect, and the encoding complexity isO(NlogN), whereNis the blocklength of the code. We also demonstrate that a quantum successive cancellation decoder works well, in the sense that the word error rate decays exponentially with the blocklength of the code. For this last result, we exploit Sen's recent “noncommutative union bound” that holds for a sequence of projectors applied to a quantum state.
In 2008, Arikan introduced a powerful family of polar codes, which are the first codes to demonstrably achieve Shannon capacity. Polar codes are built on (and named for) the phenomenon of channel polarization: a mechanism for synthetically increasing and decreasing the reliabilities of a set of channels until some fraction are perfectly noiseless and the remaining channels are completely noisy. In Arikan’s initial publication, this is achieved with a simple recursive binary transform, and shortly thereafter, it was shown by Korada et al. that polarization is a very general phenomenon achieved by many different (not necessarily binary) recursive transforms. Transmission is straightforward once the reliable channels have been identified, but this task is difficult, both computationally and theoretically. Moreover, the guarantees of polar code performance come to fruition only as the code length goes to infinity. Polar codes do not compare favorably to, e.g., low-density parity-check codes at finite block lengths. Motivated by these concerns, this dissertation investigates graph-theoretic properties of polar codes in the context of belief propagation decoding. We first define the class of encoding trellises applicable to the polar coding framework and give a graph- theoretic criterion for polarization. A fundamental contribution is the introduction of the tensor-like join of trellises: a graph product which supplies a direct connection to the matrix construction of polar codes. We leverage the tensor-like join throughout as a mechanism for understanding both graph-theoretic structures and decoding outcomes. We build up a family of acyclic auxiliary graphs, called computation graphs, in order to study belief propagation analytically. In this context, we show that the tensor-like join is sufficient as a construction mechanism and moreover, that such constructions endow computation graphs with powerful structural properties. Following Wiberg, we extend the notion of a deviation as an indicator for decoding failure in the polar computation graph framework. We provide a recursive characterization of the deviation set for Arikan’s polar codes. Finally, looking to the future, we focus on further applications of the tools developed herein.
Shannon, in his seminal work, formalized the transmission of data over a communication channel and determined its fundamental limits. He characterized the relation between communication rate and error probability and showed that as long as the communication rate is below the capacity of the channel, error probability can be made as small as desirable by using appropriate coding over the communication channel and letting the codeword length approach infinity. He provided the formula for capacity of discrete memoryless channel. However, his proposed coding scheme was too complex to be practical in communication systems. Polar codes, recently introduced by Arikan, are the first practical codes that are known to achieve the capacity for a large class of channel and have low encoding and decoding complexity. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length as it goes to infinity. However, it is interesting to investigate their performance in finite length as this is the case in all practical communication schemes. In this dissertation, after a brief overview on polar codes, we introduce a practical framework for simulation of error correcting codes in general. We introduce the importance sampling concept to efficiently evaluate the performance of polar codes with finite bock length. Next, based on simulation results, we investigate the performance of different genie aided decoders to mitigate the poor performance of polar codes in low to moderate block length and propose single-error correction methods to improve the performance dramatically in expense of complexity of decoder. In this context, we also study the correlation between error events in a successive cancellation decoder. Finally, we investigate the performance of polar codes in non-binary channels. We compare the code construction of Sasoglu for Q-ary channels and classical multilevel codes. We construct multilevel polar codes for Q-ary channels and provide a thorough comparison of complexity and performance of two methods in finite length.
In the low-energy high-energy-efficiency regime of classical optical communications - relevant to deep-space optical channels - there is a big gap between reliable communication rates achievable via conventional optical receivers and the ultimate (Holevo) capacity. Achieving the Holevo capacity requires not only optimal codes but also receivers that make collective measurements on long (modulated) codeword waveforms, and it is impossible to implement these collective measurements via symbol-by-symbol detection along with classical postprocessing [1], [2]. Here, we apply our recent results on the classical-quantum polar code [3] - the first near-explicit, linear, symmetric-Holevo-rate achieving code - to the lossy optical channel, and we show that it almost closes the entire gap to the Holevo capacity in the low photon number regime. In contrast, Arikan's original polar codes, applied to the DMC induced by the physical optical channel paired with any conceivable structured optical receiver (including optical homodyne, heterodyne, or direct-detection) fails to achieve the ultimate Holevo limit to channel capacity. However, our polar code construction (which uses the quantum fidelity as a channel parameter rather than the classical Bhattacharyya quantity to choose the “good channels” in the polar-code construction), paired with a quantum successive-cancellation receiver - which involves a sequence of collective non-destructive binary projective measurements on the joint quantum state of the received codeword waveform - can attain the Holevo limit, and can hence in principle achieve higher rates than Arikan's polar code and decoder directly applied to the optical channel. However, even a theoretical recipe for construction of an optical realization of the quantum successive-cancellation receiver remains an open question.
Error correctiong codes (ECC) are widly used in applications to correct errors in data transmission over unreliable or noisy communication channels. Recently, two kinds of promising codes attracted lots of research interest because they provide excellent error correction performance. One is non-binary LDPC codes, and the other is polar codes. This dissertation focuses on efficient decoding algorithms and decoder design for thesetwo types of codes.Non-binary low-density parity-check (LDPC) codes have some advantages over their binary counterparts, but unfortunately their decoding complexity is a significant challenge. The iterative hard- and soft-reliability based majority-logic decoding algorithms are attractive for non-binary LDPC codes, since they involve only finite field additions and multiplications as well as integer operations and hence have significantly lower complexity than other algorithms. We propose two improvements to the majority-logic decoding algorithms. Instead of the accumulation of reliability information in the ex-isting majority-logic decoding algorithms, our first improvement is a new reliability information update. The new update not only results in better error performance and fewer iterations on average, but also further reduces computational complexity. Since existing majority-logic decoding algorithms tend to have a high error floor for codes whose parity check matrices have low column weights, our second improvement is a re-selection scheme, which leads to much lower error floors, at the expense of more finite field operations and integer operations, by identifying periodic points, re-selectingintermediate hard decisions, and changing reliability information.Polar codes are of great interests because they provably achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes an explicit construction. Most existing decoding algorithms of polar codes are based on bit-wise hard or soft decisions. We propose symbol-decision successive cancellation (SC) and successive cancellation list (SCL) decoders for polar codes, which use symbol-wise hard or soft decisions for higher throughput or better error performance. Then wepropose to use a recursive channel combination to calculate symbol-wise channel transition probabilities, which lead to symbol decisions. Our proposed recursive channel combination has lower complexity than simply combining bit-wise channel transition probabilities. The similarity between our proposed method and Arıkan's channel transformations also helps to share hardware resources between calculating bit- and symbol-wise channel transition probabilities. To reduce the complexity of the list pruning, atwo-stage list pruning network is proposed to provide a trade-off between the error performance and the complexity of the symbol-decision SCL decoder. Since memory is a significant part of SCL decoders, we also propose a pre-computation memory-saving technique to reduce memory requirement of an SCL decoder.To reduce the complexity of the recursive channel combination further, we propose an approximate ML (AML) decoding unit for SCL decoders. In particular, we investigate the distribution of frozen bits of polar codes designed for both the binary erasure and additive white Gaussian noise channels, and take advantage of the distribution to reduce the complexity of the AML decoding unit, improving the throughput-area efficiency of SCL decoders.Furthermore, to adapt to variable throughput or latency requirements which exist widely in current communication applications, a multi-mode SCL decoder with variable list sizes and parallelism is proposed. If high throughput or small latency is required, the decoder decodes multiple received words in parallel with a small list size. However, if error performance is of higher priority, the multi-mode decoder switches to a serialmode with a bigger list size. Therefore, the multi-mode SCL decoder provides a flexible tradeoff between latency, throughput and error performance at the expense of small overhead.
Quantum Key Distribution (QKD) enables two parties to establish a common secret key that is information-theoretically secure by transmitting random bits that are encoded as qubits and sent over a quantum channel, followed by classical information processing steps known as information reconciliation and key extraction. Transmission of information over a quantum channel introduces errors that are generally considered to be due to the adversary's tempering with the quantum channel and needs to be corrected using classical communication over an (authenticated) public channel. Commonly used error-correcting codes in the context of QKD include cascade codes, low-density parity check (LDPC) codes, and more recently polar codes. In this work, we explore the applicability of designing of a polar code encoder based on a channel reliability sequence. We show that the reliability sequence can be derived and used to design an encoder independent of the choice of decoder. We then implement our design and evaluate its performance against previous implementations of polar code encoders for QKD as well as other typical error-correcting codes. A key advantage of our approach is the modular design which decouples the encoder and decoder design and allows independent optimization of each. Our work leads to more versatile polar code-based error reconciliation in QKD systems that would result in deployment in a broader range of scenarios.