Polar codes

This repository provides C and MATLAB implementations for polar codes.

For the seminal work on polar codes, please refer to: Erdal Arikan, "Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels", http://arxiv.org/abs/0807.3917

Overview of what is provided

Encoding for polar codes
Decoding for polar codes including
- Successive cancellation (SC) decoding (See Arikan)
- Successive cancellation list (SCL) decoding (See Tal)
- LLR based SCL decoding (See Stimming)
Code construction:
- Bhattacharya parameter based construction
- Monte Carlo code construction (BPSK, 4-ASK, 8-ASK, 16-ASK)
  - PolarM only (Update Nov, 2016)
- Gaussian Approximation code construction (BPSK, 4-ASK, 8-ASK, 16-ASK)
  - PolarM only (Update Nov, 2016)
AWGN simulations
- Support for BPSK
- Support for 4-ASK, 8-ASK, 16-ASK
  - Both Bit interleaved coded modulation (BICM) and multi-level coding (MLC) approaches are supported
  - See Mathis for a summary of these approaches.
  - PolarM only (Update Nov, 2016)
  - Note the List decoder is not supported for MLC approaches in the current version

Decoding performance

The figure above shows the performance comparison between PolarC and Tal Fig. 1. A close comparison reveals that the performance for CRC aided polar code is about 0.1 dB worse. Note that the two key differences are (i) code construction method (ii) LLR based decoder with hardware-friendly (see Stimming) LLR updates for large values of LLRs.

** Update Nov, 2016 **

The figure above shows the results for modulation specific polar codes using the Gaussian approximation code construction for block length 1024 across a variety of rates and constellations. The results are close to the results given in Mathis.

The figure above shows the results for for modulation specific polar codes using the Monte Carlo code construction for block length 1024 and info length 512 codes. The results use link level simulations for AWGN channel using the SCD algorithm. The results for 4-ASK + PBP (Gray Labeling) are close to the results in Mahdavifar though there are some differences in the approach itself.

Runtime performance C and MATLAB

Runtime is mainly dominated by the decoder. The run time comparison for rate 1/2 code is as follows (run on a single macbook pro 2015):

Comparison of number of iterations per second

Parameters	PolarC	PolarM	Speedup C/M
N = 2048, L = 1	250	51	5x
N = 2048, L = 4	67	3.2	20x
N = 2048, L = 32	10.1	0.65	15x
N = 512, L = 1	890	204	4.5x
N = 512, L = 4	287	14	20x
N = 512, L = 32	44	2.8	16x

Code Interface

The key code is in class PolarCode (C and MATLAB). The interface to this class is as follows:

constructor
- Input: N or n, K, epsilon, CRC
- Output: None
- Function: create polar code with specified parameters.
  - Bhattacharya parameter based construction is used.
encode (MATLAB code modified from Pfister)
- Inputs: info bits (length = K)
- Output: coded bits (length = N)
decode_SC_P1 (only for MATLAB - code modified from Pfister)
- Input: vector of probability of a bit being '1' (length = N)
- Output: decoded info bits (length = K)
- Function: SC decoder (see Arikan)
decode_SCL_P1
- Input: p1, p0, L
  - p1 = vector of probability of output given bit = 1,
  - p0 = vector of probability of output given bit = 0,
  - L = list size
- Output: decoded info bits
- Function: SCL decoder (see Tal)
decode_SCL_LLR
- Input: LLR, L
  - LLR = vector of log likelihood ratios
  - L = list size
- Output: decoded info bits
- Function: LLR based SCL decoder (see Stimming)
get_bler_quick (helper function)
- Input: EbNo_vec, list_size_vec
- Output: BLER estimate
- Function: get BLER estimate.

Note that for speed up of simulation, get_bler_quick assumes that if a given run (as in info bit and noise realizations) is decoded for a lower EbNo value, then it will be decoded for a higher EbNo value.

Bugs and support

The PolarC code will not compile with libstdc++. The code only works with libc++.

The code is provided as is without any warranty (implicit or explicit) and without guarantee of correctness.

References

E. Arikan, "Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels", http://arxiv.org/abs/0807.3917
Ido Tal and Alexander Vardy, "List Decoding of Polar Codes", https://arxiv.org/abs/1206.0050
Alexios Balatsoukas-Stimming, Mani Bastani Parizi, Andreas Burg, "LLR-based Successive Cancellation List Decoding of Polar Codes", https://arxiv.org/abs/1401.3753
Henry D. Pfister, "A Brief Introduction to Polar Codes", http://pfister.ee.duke.edu/courses/ecen655/polar.pdf
Mathis Seidl, Polar Coding: Finite-Length Aspects, Phd Thesis
Hessam Mahdavifar, Mostafa El-Khamy, Jungwon Lee and Inyup Kang, Compound Polar Codes, https://arxiv.org/pdf/1302.0265v1.pdf