[Ground-station] Polar Codes - join the fun! - recommended reading

[Michelle Thompson]

Here are some recommendations for reading about Polar Codes.

Ahmet Inan has started some work here. Please see
https://github.com/xdsopl/polar

Please feel free to join the discussion, ask questions, and make some
progress.

Ahmet has requested a copy of "A Simplified Successive-Cancellation Decoder
for Polar Codes" by Amin Alamdar Yazdi and Frank R. Kschischang. If you
have access to this paper and can legally provide a copy to Ahmet, then
please let me know. Otherwise I will purchase it for him at $15 individual
member price.

I can and will loan him the readings from Transactions on Information
Theory in the list below.

>From an IEEE perspective, here are the recommended readings in this area.

Books:

P. Giard, C. Thibeault, and W. J. Gross, High-Speed Decoders for Polar
Codes, Springer International Publishing, 2017.
This book focuses on the implementation of fast-SSC-based polar decoders.
In particular, the authors consider the hardware and software
implementation of standard fast-SSC decoding, as well as the hardware
implementation of ultra-high-speed unrolled decoders enabled by fast-SSC
decoding.

E. Şaşoğlu, Polarization and Polar Codes, Now Publishers Inc, 2012.
This monograph starts with an explanation of channel polarization and how
it is used to construct polar codes. The concept of channel polarization is
then generalized to non-binary input channels and to polarization kernels
of sizes larger than the 2x2 kernel used by Arıkan in his seminal work on
channel polarization. Finally, some discussion is provided on the joint
polarization of multiple random variables with applications to multi-user
channels.

O. Gazi, Polar Codes: A Non-Trivial Approach to Channel Coding, Springer,
2018.
This book explains the philosophy behind the idea of polar encoding from an
information-theoretic perspective. It then discusses the
successive-cancellation decoding algorithm and associated operations in 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.

Overviews and Tutorials:

E. Arıkan, “On the Origin of Polar Coding,” IEEE Journal on Selected Areas
in Communications, vol. 34, no. 2, pp. 209-223, February 2016.
This paper gives a historical overview of the steps that lead to the
discovery of polar codes. Several pre-existing techniques and their
relation to polar coding are described in detail, giving readers very
useful intuition.

K. Niu, K. Chen, J. Lin, and Q. T. Zhang, “Polar Codes: Primary Concepts
and Practical Decoding Algorithms,” IEEE Communications Magazine, vol. 52,
no. 7, pp. 60-69, July 2014.
This tutorial paper provides a simple discussion of the main principles
behind polar coding. The authors discuss the notion of channel polarization
and how it is used in order to construct polar codes. A wide range of
decoding algorithms is explained, including successive-cancellation
decoding, improved and fast successive-cancellation decoding algorithms,
and belief-propagation decoding. Finally, the authors provide a comparison
of the error-correcting performance of polar codes with WCDMA and LTE turbo
codes, as well as WiMax LDPC codes.

A. Balatsoukas-Stimming, P. Giard, and A. Burg, “Comparison of Polar
Decoders with Existing Low-Density Parity-Check and Turbo Decoders,” in
Proc. IEEE Wireless Communications and Networking Conference (WCNC)
Workshops, San Francisco, USA, March 2017.
This survey paper compares polar codes with the LDPC codes used in the
WiGig, Wi-Fi, and 10GE standards, and the Turbo codes used in the LTE
standard. The decoder parameters are selected so that the polar codes match
the error-correcting performance of the LDPC and turbo codes, and a
hardware implementation complexity comparison is performed by scaling the
implementation complexity of polar decoders in the literature accordingly.

P. Giard, G. Sarkis, A. Balatsoukas-Stimming, Y. Fan, C.-Y. Tsui, A. Burg,
C. Thibeault, and W. J. Gross, “Hardware Decoders for Polar Codes: An
Overview,” in Proc. IEEE International Symposium on Circuits and Systems
(ISCAS), Montreal, Canada, May 2016.
This survey paper provides an overview of hardware implementations of
successive-cancellation, successive-cancellation list, and
belief-propagation decoders for polar codes. The main techniques employed
in the literature for each type of decoder are discussed and implementation
results for all decoders are summarized and compared.

S. Shao, P. Hailes, T.-Y. Wang, J.-Y. Wu, R. G. Maunder, B. M. Al-Hashimi,
and L. Hanzo, “Survey of Turbo, LDPC and Polar Decoder ASIC
Implementations,” IEEE Communications Surveys & Tutorials, early access,
January 2019.
This paper is a survey that covers all the codes that were candidates for
the 5G standard, including polar codes. The authors first provide a
high-level discussion on the requirements of the 5G standard and the main
principles behind each coding scheme. Moreover, ASIC decoders for the
various coding schemes are compared in terms of several key
characteristics, such as throughput, hardware-efficiency, and
error-correcting performance. The authors conclude the survey with useful
design recommendations as well as some future research directions.

Standards-Related

D. Hui, S. Sandberg, Y. Blankenship, M. Andersson, and L. Grosjean,
“Channel Coding in 5G New radio: A Tutorial Overview and Performance
Comparison with 4G LTE,” IEEE Vehicular Technology Magazine, vol. 13, no.
4, pp. 60-69, December 2018.
This tutorial article describes the specific polar and LDPC codes adopted
by the 5G NR standard. The purpose of each key component in these codes and
the associated operations are explained, and the performance and
implementation advantages of these new codes are compared with those of 4G
LTE.

V. Bioglio, C. Condo, and I. Land, “Design of Polar Codes in 5G New Radio,”
 arXiv:1804.04389v2, January 2019.
This tutorial provides a description of the encoding chain of polar codes,
as specified in the 5G NR standard (3GPP 38.212). While the standard
specification provides all details, this tutorial aims at assisting the
reader’s comprehension by restructuring the presentation, highlighting the
underlying polar coding principles, and relating these principles to the
literature.

3rd Generation Partnership Project (3GPP), “Multiplexing and Channel
Coding,” 3GPP 38.212 V.15.5.0 (2019-03).
This document is the official technical specification produced by the 3rd
Generation Partnership Project (3GPP). It provides the full specification
of the polar codes for the 5G NR control channels. The document may be
updated and new versions may be made available by the TSG.

Foundations of Polar Codes

E. Arıkan, “Channel Polarization: A Method for Constructing
Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels,”
IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051-3073,
July 2009.
This is the seminal paper in which polar codes were first introduced. The
paper introduces the concept of channel polarization for memoryless
channels with binary input. It proves that, if the underlying channel is
symmetric, then the code rate tends to the channel capacity while the
probability of error tends to zero, assuming the use of an efficient
successive-cancellation decoder that the paper introduces.

E. Arıkan and E. Telatar, “On the Rate of Channel Polarization," in Proc.
IEEE International Symposium on Information Theory (ISIT), Seoul, South
Korea, June 2009.
This paper considers the same channel polarization setting as Arıkan’s
seminal paper, but it contains an improved asymptotic analysis of the
probability of incorrect decoding. Specifically, it shows that the error
probability is approximately 2-√N, where N is the blocklength of the polar
code.

E. Arıkan, “Source Polarization,” in Proc. IEEE International Symposium on
Information Theory (ISIT), Austin, USA, June 2010.
This paper shows how polar codes can be generalized to a source coding
setting in order to losslessly compress a binary independent and
identically distributed source with side information. Since the realization
of the side information is only needed by the decoder, this scheme can be
used in a Slepian-Wolf setting.

Information Theory Basis

S. B. Korada and R. Urbanke, "Polar Codes are Optimal for Lossy Source
Coding," IEEE Transactions on Information Theory, vol. 56, no. 4, pp.
1751-1768, April 2010.
This paper shows how polar codes can be used for lossy source coding. The
coding rate achieved is optimal, provided that the source is symmetric. By
incorporating ideas from the fourth paper in this topic, the proposed
scheme can also lead to an optimal compression rate for non-symmetric
sources.

S. H. Hassani, K. Alishahi, and R. Urbanke, “Finite-Length Scaling of Polar
Codes,” IEEE Transactions on Information Theory, vol. 60, no. 10, pp.
5875-5898, October 2014.
This paper was the first to explore the scaling of polar codes, which is
the relation between the code rate R and the blocklength N for a fixed
probability of error. Specifically, the paper gives upper and lower bounds
for N as a function of the code rate R, the channel capacity I(W), and two
constants α and β that depend only on the fixed probability of error and on
the transmission channel.

D. Goldin and D. Burshtein, “Improved Bounds on the Finite Length Scaling
of Polar Codes,” IEEE Transactions on Information Theory, vol. 60, no. 11,
pp. 6966-6978, November 2014.
This paper also deals with the scaling of polar codes. In particular, the
authors provide an improved bound on the required blocklength N to
communicate reliably at a given rate R. The improved results are also
extended to the case of lossy source coding.

J. Honda and H. Yamamoto, "Polar Coding without Alphabet Extension for
Asymmetric Channels," IEEE Transactions on Information Theory, vol. 59, no.
12, pp. 7829-7838, December 2012.
This paper shows how polar codes can be used to produce an input
distribution that is not symmetric. Thus, it shows a polar coding scheme
that extends Arıkan’s original scheme and is capacity achieving for
memoryless channels that are not symmetric.

V. Guruswami and P. Xia, “Polar Codes: Speed of Polarization and Polynomial
Gap to Capacity,” IEEE Transactions on Information Theory, vol.  61, no. 1,
pp. 3-16, January 2015.
This paper shows that, for binary-input memoryless symmetric channels, the
blocklength N of a polar code grows polynomially in the reciprocal of the
difference between the code rate and the channel capacity when imposing a
particular constraint on the error probability. Moreover, the paper tracks
the polarization of channels without resulting to limiting arguments on
martingales.

E. Şaşoğlu and I. Tal, “Polar Coding for Processes with Memory,” IEEE
Transactions on Information Theory, vol.  65, no. 4, pp. 1994-2003, April
2019.
This paper extends polar codes to a setting in which either the channel or
the input distribution (or both) have memory. Slow polarization is proved
for both the low-entropy and high-entropy sets, while fast polarization is
proved only for the low-entropy set.

B. Shuval and I. Tal, “Fast Polarization for Processes with Memory,” IEEE
Transactions on Information Theory, vol. 65, no. 4, pp. 2004-2020, April
2019.
This paper closes the gap left by the previous paper. Specifically, it
shows that if we assume that the input/output process is governed by an
underlying regular and hidden Markov process, then we have fast
polarization of both the low-entropy and the high-entropy sets. It is also
shown that the resulting coding scheme has the same asymptotic probability
of error as in the memoryless case, i.e., approximately 2-√N.

Construction and Encoding

I. Tal and A. Vardy, “How to Construct Polar Codes,” IEEE Transactions on
Information Theory, vol. 59, no. 10, pp. 6562-6582, October 2013.
This paper introduces a method for the construction of polar codes. The bit
subchannels induced by Arıkan’s polarizing transformation have an output
alphabet whose size grows exponentially with the code length. Channel
upgrading and degrading transformations are presented, which allow faithful
approximations of a subchannel with an intractably large alphabet by
another channel having a manageable alphabet size. This enables the
construction of polar codes with complexity growing linearly with the
blocklength.

R. Mori and T. Tanaka, “Performance of Polar Codes with the Construction
Using Density Evolution,” IEEE Communications Letters, vol. 13, no. 7, pp.
519-521, July 2009.
The authors of this paper were among the first to explicitly state the
problem of construction of polar codes. Density evolution was suggested to
solve this problem. Furthermore, a partial order is identified on bit
subchannels that can be exploited to simplify the construction process.

P. Trifonov, “Efficient Design and Decoding of Polar Codes,” IEEE
Transactions on Communications, vol. 60, no. 11, pp. 3221-3227, November
2012.
This paper introduces a method for the construction of polar codes for the
AWGN channel. The subchannels induced by Arıkan’s polarizing transformation
are approximated with Gaussian ones, and their reliability is characterized
by the mean values of the corresponding log-likelihood ratios. An improved
decoding algorithm is also presented, which exploits the representation of
a polar code as a generalized concatenated code.

S. N. Hong, D. Hui, and I. Marić, “Capacity-Achieving Rate-Compatible Polar
Codes,” IEEE Transactions on Information Theory, vol. 63, no. 12, pp.
7620-7632, December 2017.
This work introduces a method of constructing rate-compatible polar codes
that are capacity-achieving at multiple code rates, and have low-complexity
decoders. The proposed codes consist of a parallel concatenation of
multiple polar codes with an information-bit divider at the input of each
polar encoder. It is shown that the proposed codes are capacity achieving
for an arbitrary sequence of rates and for any class of degraded channels.

G. He,  J.-C. Belfiore, I. Land, G. Yang, X. Liu, Y. Chen, R. Li, J. Wang,
Y. Ge, R. Zhang, and W. Tong, “Beta-Expansion: A Theoretical Framework for
Fast and Recursive Construction of Polar Codes”, in Proc. IEEE Global
Communications Conference (GLOBECOM), Singapore, December 2017.
This paper presents a polarization weight algorithm, which is a simple
method for the evaluation of the reliability of polar code subchannels. The
authors show that polar codes can be recursively constructed by
continuously solving several polynomial equations at each recursive step.
The sequences derived from the polarization weight algorithm are shown to
satisfy the universal partial order for polar codes.

P. Trifonov and V. Miloslavskaya, “Polar Subcodes,” IEEE Journal on
Selected Areas in Communications, vol. 34, no. 2, pp. 254-266, February
2016.
The paper introduces a generalization of polar codes, where some input
symbols of a polarizing transformation, called dynamic frozen or
parity-check frozen symbols, are set to linear combinations of other
symbols instead of fixed values. This enables generic linear block codes to
be decoded using the techniques developed for polar codes. A method for the
construction of subcodes of extended BCH codes is presented, which
outperform polar codes with CRC under successive-cancellation list decoding.

H. Vangala, Y. Hong, and E. Viterbo, “Efficient Algorithms for Systematic
Polar Encoding,” IEEE Communications Letters, vol. 20, no. 1, pp. 17-20,
January 2016.
This paper presents three systematic encoding algorithms for polar codes.
These encoders work for any arbitrary choice of frozen bit indices, and
they allow a tradeoff between the number of binary computations and the
number of bits of memory required by the encoder. The complexity of the
best of these encoders is shown to be exactly equal to that of a
non-systematic encoding algorithm.

Improved and Low-Complexity Decoding

I. Tal and A. Vardy, “List Decoding of Polar Codes,” IEEE Transactions on
Information Theory, vol. 61, no. 5, pp. 2213-2226, May 2015.
This paper introduces a successive-cancellation list decoder for polar
codes, which is a generalization of the classic successive-cancellation
decoder proposed by Arıkan. Simulations show that the proposed algorithm
provides near maximum-likelihood decoding, even for moderate values of the
list size. The paper also presents a construction of polar codes with a
CRC, which far outperforms classical polar codes under
successive-cancellation list decoding.

K. Chen, K. Niu, and J. Lin, “Improved Successive Cancellation Decoding of
Polar Codes,” IEEE Transactions on Communications, vol. 61, no. 8, pp.
3100-3107, August 2013.
This paper introduces the successive-cancellation stack decoding algorithm,
which enables reduced-complexity decoding of polar codes. Moreover, unified
descriptions of the successive-cancellation, successive-cancellation list,
and successive-cancellation stack decoding algorithms are given as
path-search procedures on the code tree of polar codes.

P. Trifonov, “A Score Function for Sequential Decoding of Polar Codes,” in
Proc. IEEE International Symposium on Information Theory (ISIT), Vail, USA,
June 2018.
This paper introduces a score function for sequential (stack) decoding of
polar codes. A significant reduction of the average decoding complexity is
achieved by biasing the path metrics in the min-sum version of the stack
successive-cancellation decoding algorithm with its expected value for the
correct path. The proposed approach can also be used for near
maximum-likelihood decoding of short extended BCH codes.

O. Afisiadis, A. Balatsoukas-Stimming, and A. Burg, “A low-Complexity
Improved Successive Cancellation Decoder for Polar Codes,” in Proc.
Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA,
November 2014.
This paper describes successive-cancellation flip decoding, where
successive-cancellation decoding failures are detected using a CRC and
additional successive-cancellation decoding attempts are made by flipping
some bit-decisions. The error-correcting performance of
successive-cancellation flip decoding is significantly improved with
respect to successive-cancellation decoding with a negligible average
complexity overhead, at the cost of a variable running time.

M. Rowshan and E. Viterbo, “Stepped List Decoding for Polar Codes,” in
Proc. IEEE International Symposium on Turbo Codes & Iterative Information
Processing, Hong Kong, December 2018.
This paper investigates the list decoding process by introducing a new
parameter named path metric range. The paper proposes a stepwise adaptation
of the list size based on the path metric range. This approach preserves
the error-correction performance of conventional successive-cancellation
list decoding, while significantly reducing the memory requirements and the
computational complexity.

A. Alamdar-Yazdi and F. R. Kschischang, “A Simplified
Successive-Cancellation Decoder for Polar Codes,” IEEE Communications
Letters, vol. 15, no. 12, pp. 1378-1380, December 2011.
This paper describes a modification on the successive-cancellation decoder
for polar codes, in which local decoders for rate-one constituent codes at
any depth are simplified. This modification reduces the decoding latency
and algorithmic complexity of the conventional SC decoder, while preserving
the error-correcting performance.

S. Cammerer, M. Ebada, A. Elkelesh, S. ten Brink, “Sparse Graphs for Belief
Propagation Decoding of Polar Codes,” in Proc. IEEE International Symposium
on Information Theory (ISIT), Vail, USA, June 2018.
This paper considers belief-propagation decoding of polar codes. The
authors show how to interpret a polar code as a low-density parity-check
(LDPC)-like code with an underlying sparse decoding graph. As a result,
iterative polar decoding can be conducted on a sparse graph using a fully
parallel sum-product algorithm. The proposed iterative polar decoder has a
negligible performance loss for short-to-intermediate code lengths compared
to Arıkan’s original belief-propagation decoder, while having lower
complexity.

Hardware and Software Implementation

C. Leroux, A. J. Raymond, G. Sarkis, and W. J. Gross, “A Semi-Parallel
Successive-Cancellation Decoder for Polar Codes,” IEEE Transactions on
Signal Processing, vol. 61, no. 2, pp. 289-299, January 2013.
This paper describes a semi-parallel hardware architecture for
successive-cancellation decoding that uses the available hardware resources
efficiently. In particular, it is shown how re-using computational logic
and memory can significantly reduce the implementation complexity. Most
subsequent hardware implementations of decoders based on successive
cancellation in the literature use semi-parallel architectures.

Y. Fan and C.-Y. Tsui, “An Efficient Partial-Sum Network Architecture for
Semi-Parallel Polar Codes Decoder Implementation,” IEEE Transactions on
Signal Processing, vol. 62, no. 12, pp., 3165-3179, June 2014.
This paper describes efficient hardware architectures for the computation
of the partial sums in SC-based decoders. The authors explain how a partial
sum architecture can be constructed that scales particularly well to large
blocklengths, and also how the proposed architecture can be incorporated
into a semi-parallel SC decoder. FPGA and ASIC results show significant
improvements with respect to previous partial sum architectures.

G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross, “Fast Polar
Decoders: Algorithm and Implementation,” IEEE Journal on Selected Areas in
Communications, vol. 32, no. 5, pp. 946-957, May 2014.
This paper presents an improved version of simplified
successive-cancellation decoding by introducing three new corresponding
node types: a single-parity-check-code node, a repetition-code node, and a
special node whose left child corresponds to a repetition code and its
right to a single-parity-check code. The paper also proposes an algorithm,
hardware architecture, and FPGA implementation for the so-called “fast-SSC”
decoder.

A. Balatsoukas-Stimming, M. Bastani Parizi, and A. Burg, “LLR-Based
Successive Cancellation List Decoding of Polar Codes,” IEEE Transactions on
Signal Processing, vol. 63, no. 19, pp. 5165-5179, October 2015.
This work re-formulates successive-cancellation list decoding using
log-likelihood ratios (LLRs) by introducing an LLR-based path metric.
LLR-based successive-cancellation list decoding is equivalent to the
original successive-cancellation list decoding algorithm, but hardware
implementation results show that the LLR-based formulation leads to a
significant improvement in the area and operating frequency of
successive-cancellation list decoders. All subsequent hardware
implementations of successive-cancellation list decoding in the literature
use LLR-based formulation.

A. Balatsoukas-Stimming, M. Bastani Parizi, and A. Burg, “On Metric Sorting
for Successive Cancellation List Decoding of Polar Codes,” in Proc. IEEE
International Symposium on Circuits and Systems (ISCAS), Lisbon, Portugal,
May 2015.
This paper was the first to focus on the critical task of path metric
sorting in successive-cancellation list decoding. Some properties of the
LLR-based path metric are exploited in order to significantly simplify
several well-known sorting architectures. ASIC synthesis results show
significant improvements in area and operating frequency with respect to
existing sorting architectures.

B. Yuan and K. K. Parhi, “Early Stopping Criteria for Energy-Efficient
Low-Latency Belief-Propagation Polar Code Decoders,” IEEE Transactions on
Signal Processing, vol. 62, no. 24, pp. 6496-6506, December 2014.
This paper describes several heuristic techniques for early stopping in
belief-propagation decoding of polar codes. Each technique works best for a
different SNR regime, so an adaptive SNR-dependent early stopping method is
also presented. Hardware implementation results show that the early
stopping techniques can significantly improve the average throughput and
energy-efficiency of belief-propagation decoders.

B. Le Gal, C. Leroux, and C. Jego, “Multi-Gb/s Software Decoding of Polar
Codes,” IEEE Transactions on Signal Processing, vol. 63, no. 2, pp.
349-359, January 2015.
This paper shows how the parallelism capabilities of modern CPUs can be
used to implement very high-speed SC decoders in software, which are of
great interest in software-defined radio applications. It is also explained
how existing algorithmic simplifications for hardware SC decoders can be
beneficial in software implementations. The implemented software decoders
achieve throughputs of more than 1 Gb/s for a wide range of blocklengths
and code rates.

Polar Coding for General Channels

U. U. Fayyaz and J. R. Barry, “Polar Codes for Partial Response Channels,”
in Proc. IEEE International Conference on Communications (ICC), Budapest,
Hungary, June 2013.
The paper deals with polar codes for partial-response channels using turbo
equalization at the receiver side. The original successive-cancellation
decoder for polar codes does not produce soft-outputs for code bits. The
authors propose a soft-input soft-output variant of the
successive-cancellation decoder, called “soft cancellation (SCAN)” decoder,
which is suitable for such turbo receiver architectures and keeps the
computational complexity low.

E. Şaşoğlu, E. Telatar, and E. M. Yeh, “Polar Codes for the Two-User
Multiple-Access Channel,” IEEE Transactions on Information Theory, vol. 59,
no. 10, pp. 6583-6592, October 2013.
This paper extends Arıkan’s polar coding method to two-user multiple-access
channels. Using Arıkan’s construction for each of the two users of the
channel results in a coding scheme whose sum rate is the one that
corresponds to uniform input distributions. The asymptotic encoding and
decoding complexities and the error-correcting performance of these codes
are shown to be the same as in the single-user case.

N. Goela, E. Abbe, and M. Gastpar, “Polar Codes for Broadcast Channels,”
 IEEE Transactions on Information Theory, vol. 61, no. 2, pp. 758-782,
February 2015.
This paper introduces polar codes for discrete memoryless broadcast
channels. For m-user deterministic broadcast channels, the
polarization-based codes are shown to achieve rates on the boundary of the
private-message capacity region. For two-user noisy broadcast channels,
polar implementations are presented for two information-theoretic schemes,
namely Cover’s superposition codes and Marton’s codes.

M. Mondelli, S. H. Hassani, I. Sason, and R. Urbanke, “Achieving Marton's
Region for Broadcast Channels Using Polar Codes,” IEEE Transactions on
Information Theory, vol. 61, no. 2, pp. 783-800, February 2015.
This paper presents polar coding schemes for the two-user discrete
memoryless broadcast channel, which achieve Marton’s region with both
common and private messages. This is the best achievable rate region known
to date, and it is tight for all classes of two-user discrete memoryless
broadcast channels whose capacity regions are known.

M. Seidl, A. Schenk, C. Stierstorfer, and J. B. Huber, “Polar-Coded
Modulation,” IEEE Transactions on Communications, vol. 61, no. 10, pp.
4108-4119, October 2013.
A framework is proposed that allows for a joint description and
optimization of binary polar coding and pulse-amplitude modulation schemes.
Multilevel coding and bit-interleaved coded modulation are considered, the
conceptual equivalence of polar coding and multilevel coding is detailed,
and rules for the optimum choice of the labelling are developed.

D. Zhou, K. Niu, and C. Dong, “Construction of Polar Codes in Rayleigh
Fading Channel,” IEEE Communications Letters, vol. 23, no. 3, pp. 402-405,
March 2019.
This paper addresses the construction of polar codes for the Rayleigh
fading channel. Two algorithms are proposed to determine an AWGN channel
that is equivalent to the actual Rayleigh fading channel. For this
equivalent AWGN channel, the frozen set is determined using density
evolution under a Gaussian approximation.

Generalized Polar Codes

S. B. Korada, E. Şaşoğlu, and R. Urbanke, “Polar Codes: Characterization of
Exponent, Bounds, and Constructions,” IEEE Transactions on Information
Theory, vol. 56, no. 12, pp. 6253-6264, December 2010.
This paper shows that any ℓ × ℓ matrix with the property that none of its
column permutations is upper triangular polarizes binary-input memoryless
channels. Then, it characterizes the exponent of a given square matrix and
provides upper and lower bounds on the achievable exponents. Using these
bounds, the authors show that there are no matrices of size smaller than
15×15 with exponents exceeding 1/2. Furthermore, a general construction
based on BCH codes which achieves exponents arbitrarily close to 1 for
large ℓ is given. Specifically, for size 16×16, this construction yields an
exponent greater than 1/2.

R. Mori and T. Tanaka, “Source and Channel Polarization Over Finite Fields
and Reed–Solomon Matrices,” IEEE Transactions on Information Theory, vol.
60, no. 5, pp. 2720-2736, May 2014.
This paper generalizes Arıkan’s channel polarization for the binary field
alphabet to polarization over any finite field, with the field size q being
a power of a prime. A necessary and sufficient condition for a matrix over
a finite field is shown under which any source and channel are polarized.
Additionally, the polarization speed result for binary alphabets is
generalized to arbitrary finite fields. This paper also provides an
explicit construction of an ℓ×ℓ matrix, based on a Reed-Solomon matrix,
with the asymptotically fastest polarization for ℓ ≤ q.

A. Fazeli, H. Hassani, M. Mondelli, and A. Vardy, “Binary Linear Codes with
Optimal Scaling: Polar Codes with Large Kernels,” in Proc. IEEE Information
Theory Workshop (ITW), Guangzhou, China, November 2018.
This paper shows that for the binary erasure channel, there exist ℓ × ℓ
binary kernels with quasi-linear encoding and decoding complexity, such
that polar codes constructed from these kernels achieve capacity with a
scaling exponent that tends to the optimal value of 2 as ℓ grows.

V. Bioglio, I. Land, F. Gabry, and J.-C. Belfiore, “Flexible Design of
Multi-Kernel Polar Codes by Reliability and Distance Properties,” in Proc.
International Symposium on Turbo Codes & Iterative Information Processing
(ISTC), Hong Kong, December 2018.
This paper proposes a polar code construction for multi-kernel polar codes
by taking into account both reliability and distance. The new design
provides a framework to optimize the code design for
successive-cancellation list decoding, allowing performance to trade
against decoding complexity.

N. Presman, O. Shapira, S. Litsyn, T. Etzion, and A. Vardy, “Binary
Polarization Kernels from Code Decompositions,” IEEE Transactions on
Information Theory, vol. 61, no. 5, pp. 2227–2239, May 2015.
This paper proposes designing binary kernels with a large exponent by using
code decompositions. The proposed kernels are generally nonlinear, but they
provide a better polarization exponent than the previously known kernels of
the same dimensions. In particular, nonlinear kernels of dimensions 14, 15,
and 16 are constructed and are shown to have optimal asymptotic
error-correcting performance.

G. Trofimiuk and P. Trifonov, “Efficient Decoding of Polar Codes with Some
16×16 Kernels,” in Proc. IEEE Inf. Theory Workshop (ITW), Guangzhou, China,
November 2018.
This paper presents reduced complexity decoding algorithms for 16×16
polarization kernels with polarization rate 0.51828 and scaling exponents
3.346 and 3.450. It shows that, with these kernels, increasing the list
size in the successive-cancellation list decoder provides a significant
performance gain compared to the case of Arıkan’s 2×2 kernel. The proposed
approach results in lower decoding complexity compared to polar decoding
with Arıkan’s kernel at the same performance level.

-Michelle W5NYV

"Potestatem obscuri lateris nescis."
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openresearch.institute/pipermail/ground-station-openresearch.institute/attachments/20200630/534c1268/attachment-0001.html>