Polar Codes

Main Module

class PolarCode(n, frozen=None, name=None, **kwargs)

Bases: lpdec.codes.BinaryLinearBlockCode

Class for representing polar codes (see [Ark09]).

Parameters:
  • n (int) – Exponent of the block length, which will then be \(2^n\).
  • frozen (iterable) – Indices of the frozen input bits.
  • name (str) – Code name. Defaults to PolarCode(n=<n>, frozen=<frozen>).

The code’s information length computes as `2**n-len(frozen)`. The parity-check matrix is generated as described in [GKG10].

factorGraph

Factor graph of the polar code, containing auxiliary variables, as depicted in Fig. 1 of [TS14]. Created on-the-fly on first access. See PolarFactorGraph for details.

computeFrozenIndices(BMSC, n, mu, threshold=None, rate=None)

Compute frozen bit indices by the method presented in [TV13]. There are two ways to determine the set of frozen bits, either by giving a threshold on the bit-channel’s error probability or by specifying a target rate.

Parameters:
  • BMSC (BMSChannel) – Initial BMSChannel to start with
  • n (int) – The blocklength is determined as \(N=2^n\).
  • mu (int) – Granularity of channel degrading. A higher value means higher running time but closer approximation. Must be an even number.
  • threshold (double) – If given, all bit-channels for which the approximate error probability \(P\) satisfies \(P >\) threshold are frozen.
  • rate (double) – If given, the channels with highest error probability are frozen until the target rate is achieved.
class PolarFactorGraph(n)

Bases: lpdec.codes.factorgraph.FactorGraph

Sparse factor graph of a polar code, as defined in e.g. [TS14].

PolarFactorGraph has additional attributes compared to FactorGraph:

polarVars

Array of variable nodes with shape (N, n+1). polarVars[i,j] equals \(s_{i,j}\) in the paper.

polarChecks

Array of check nodes with shape (N, n). polarChecks[i,j] is the check right of \(s_{i,j}\) in the paper.

Nodes in the polar factor graph have additional attributes column and row. The varNodes list is ordered such that the first \(2^n\) nodes correspond to the variable nodes.

sparsify()

Makes the graph smaller by eliminating frozen variables and removing degree-2 checks and degree-1 auxiliary variables. The result is still a sparse graph (each check node has degree at most 3), but usually much smaller than the original one.

See [TS14] for details on the construction.

Compiled helper module

This module contains helpers for the (approximate) construction of polar codes due to Tal and Vardy. Because the construction is time-consuming, it is a compiled Cython module.

class BMSChannel

Bases: object

A binary memoryless symmetric channel. Characterized by the vector Wgiven0 containing the probabilities, for all output symbels y, that y is observed when 0 is sent.

The elements are ordered in such a way that conjugate elements are adjacent, i.e., for an index i, the elements y_i and y_{i^1} are adjacent (^ is bit-wise XOR).

static AWGNC()

Computes a degraded version of the AWGN channel, discretized to \(2\cdot \nu\) values, for given SNR in dB. The SNR value is interpreted wrt. channel symbols; if you want to supply SNR_b value (SNR per information bit), you.ll also have to specify rate.

static BEC()

Create a binary erasure channel. Note that we create two erasure symbols in order to fulfill the assumption of no self-conjugates.

Parameters:eps (float) – erasure probability.
static BSC()

Create a binary symmetric channel.

Parameters:eps (float) – crossover probability.
LR()

Return the likelihood ratio of output element y

arikanTransform1()

Output the channel W[*]W, i.e. Arikan’s first channel transformation fed with two copies of self.

If mu is provided and not 0, the resulting channel will be degrading-merged with parameter mu before being returend.

arikanTransform2()

Output the channel \(W\circledast W\), i.e. Arikan’s second channel transformation.

If mu is provided and not 0, the resulting channel will be degrading-merged with parameter mu before being returend.

bhattacharyya()

Compute and return the Bhattacharyya parameter of this channel.

degradingMerge()

The degrading-merge function, as described in the paper.

errorProbability()

Return the probability of error of this channel, calculated from (13) in Tal and Vardy’s paper on polar code construction.

sortAndChoose()

Performs reordering of output symbols such that * \(LR(y_i) \geq 1\) for all even \(i\), * \(LR(y_i) \leq LR(y_{i+2})\) for all even \(i\).

class DataElement

Bases: object

Data structure for the degrading-merge procedure, as described in [TV13].