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].