Utility Functions

This module provides utility functions for the FEC package. It also provides serval functions to simplify EXIT analysis of iterative receivers.

(Binary) Linear Codes

Several functions are provided to convert parity-check matrices into generator matrices and vice versa. Please note that currently only binary codes are supported.

# load example parity-check matrix
pcm, k, n, coderate = load_parity_check_examples(pcm_id=3)

Note that many research projects provide their parity-check matrices in the alist format [MacKay] (e.g., see [UniKL]). The follwing code snippet provides an example of how to import an external LDPC parity-check matrix from an alist file and how to set-up an encoder/decoder.

# load external example parity-check matrix in alist format
al = load_alist(path=filename)
pcm, k, n, coderate = alist2mat(al)

# the linear encoder can be directly initialized with a parity-check matrix
encoder = LinearEncoder(pcm, is_pcm=True)

# initalize BP decoder for the given parity-check matrix
decoder = LDPCBPDecoder(pcm, num_iter=20)

# and run simulation with random information bits
no = 1.
batch_size = 10
num_bits_per_symbol = 2

source = BinarySource()
mapper = Mapper("qam", num_bits_per_symbol)
channel = AWGN()
demapper = Demapper("app", "qam", num_bits_per_symbol)

u = source([batch_size, k])
c = encoder(u)
x = mapper(c)
y = channel([x, no])
llr = demapper([y, no])
c_hat = decoder(llr)

load_parity_check_examples

sionna.fec.utils.load_parity_check_examples(pcm_id, verbose=False)[source]

Utility function to load example codes stored in sub-folder LDPC/codes.

The following codes are available

0 : (7,4)-Hamming code of length k=4 information bits and codeword length n=7.
1 : (63,45)-BCH code of length k=45 information bits and codeword length n=63.
2 : (127,106)-BCH code of length k=106 information bits and codeword length n=127.
3 : Random LDPC code with regular variable node degree 3 and check node degree 6 of length k=50 information bits and codeword length n=100.
4 : 802.11n LDPC code of length of length k=324 information bits and codeword length n=648.

Input

pcm_id (int) – An integer defining which matrix id to load.
verbose (bool) – Defaults to False. If True, the code parameters are printed.

Output

pcm (ndarray of zeros and ones) – An ndarray containing the parity check matrix.
k (int) – An integer defining the number of information bits.
n (int) – An integer defining the number of codeword bits.
coderate (float) – A float defining the coderate (assuming full rank of parity-check matrix).

alist2mat

sionna.fec.utils.alist2mat(alist, verbose=True)[source]

Convert alist [MacKay] code definition to full parity-check matrix.

Many code examples can be found in [UniKL].

About alist (see [MacKay] for details):

1. Row defines parity-check matrix dimension m x n

2. Row defines int with max_CN_degree, max_VN_degree

3. Row defines VN degree of all n column

4. Row defines CN degree of all m rows

Next n rows contain non-zero entries of each column (can be zero padded at the end)

Next m rows contain non-zero entries of each row.

Input

alist (list) – Nested list in alist-format [MacKay].
verbose (bool) – Defaults to True. If True, the code parameters are printed.

Output

(pcm, k, n, coderate) – Tuple:
pcm (ndarray) – NumPy array of shape [n-k, n] containing the parity-check matrix.
k (int) – Number of information bits.
n (int) – Number of codewords bits.
coderate (float) – Coderate of the code.

Note

Use load_alist to import alist from a textfile.

For example, the following code snippet will import an alist from a file called filename:

al = load_alist(path = filename)
pcm, k, n, coderate = alist2mat(al)

load_alist

sionna.fec.utils.load_alist(path)[source]

Read alist-file [MacKay] and return nested list describing the parity-check matrix of a code.

Many code examples can be found in [UniKL].

Input: path (str) – Path to file to be loaded.
Output: alist (list) – A nested list containing the imported alist data.

generate_reg_ldpc

sionna.fec.utils.generate_reg_ldpc(v, c, n, allow_flex_len=True, verbose=True)[source]

Generate random regular (v,c) LDPC codes.

This functions generates a random LDPC parity-check matrix of length n where each variable node (VN) has degree v and each check node (CN) has degree c. Please note that the LDPC code is not optimized to avoid short cycles and the resulting codes may show a non-negligible error-floor. For encoding, the LinearEncoder layer can be used, however, the construction does not guarantee that the pcm has full rank.

Input

v (int) – Desired variable node (VN) degree.
c (int) – Desired check node (CN) degree.
n (int) – Desired codeword length.
allow_flex_len (bool) – Defaults to True. If True, the resulting codeword length can be (slightly) increased.
verbose (bool) – Defaults to True. If True, code parameters are printed.

Output

(pcm, k, n, coderate) – Tuple:
pcm (ndarray) – NumPy array of shape [n-k, n] containing the parity-check matrix.
k (int) – Number of information bits per codeword.
n (int) – Number of codewords bits.
coderate (float) – Coderate of the code.

Note

This algorithm works only for regular node degrees. For state-of-the-art bit-error-rate performance, usually one needs to optimize irregular degree profiles (see [tenBrink]).

make_systematic

sionna.fec.utils.make_systematic(mat, is_pcm=False)[source]

Bring binary matrix in its systematic form.

Input

mat (ndarray) – Binary matrix to be transformed to systematic form of shape [k, n].
is_pcm (bool) – Defaults to False. If true, mat is interpreted as parity-check matrix and, thus, the last k columns will be the identity part.

Output

mat_sys (ndarray) – Binary matrix in systematic form, i.e., the first k columns equal the identity matrix (or last k if is_pcm is True).
column_swaps (list of int tuples) – A list of integer tuples that describes the swapped columns (in the order of execution).

Note

This algorithm (potentially) swaps columns of the input matrix. Thus, the resulting systematic matrix (potentially) relates to a permuted version of the code, this is defined by the returned list column_swap. Note that, the inverse permutation must be applied in the inverse list order (in case specific columns are swapped multiple times).

If a parity-check matrix is passed as input (i.e., is_pcm is True), the identity part will be re-arranged to the last columns.

gm2pcm

sionna.fec.utils.gm2pcm(gm, verify_results=True)[source]

Generate the parity-check matrix for a given generator matrix.

This function brings gm \(\mathbf{G}\) in its systematic form and uses the following relation to find the parity-check matrix \(\mathbf{H}\) in GF(2)

\[\mathbf{G} = [\mathbf{I} | \mathbf{M}] \Leftrightarrow \mathbf{H} = [\mathbf{M} ^t | \mathbf{I}]. \tag{1}\]

This follows from the fact that for an all-zero syndrome, it must hold that

\[\mathbf{H} \mathbf{c}^t = \mathbf{H} * (\mathbf{u} * \mathbf{G})^t = \mathbf{H} * \mathbf{G} ^t * \mathbf{u}^t =: \mathbf{0}\]

where \(\mathbf{c}\) denotes an arbitrary codeword and \(\mathbf{u}\) the corresponding information bits.

This leads to

\[\mathbf{G} * \mathbf{H} ^t =: \mathbf{0}. \tag{2}\]

It can be seen that (1) fulfills (2), as it holds in GF(2) that

\[[\mathbf{I} | \mathbf{M}] * [\mathbf{M} ^t | \mathbf{I}]^t = \mathbf{M} + \mathbf{M} = \mathbf{0}.\]

Input

gm (ndarray) – Binary generator matrix of shape [k, n].
verify_results (bool) – Defaults to True. If True, it is verified that the generated parity-check matrix is orthogonal to the generator matrix in GF(2).

Output

ndarray – Binary parity-check matrix of shape [n-k, n].

Note

This algorithm only works if gm has full rank. Otherwise an error is raised.

pcm2gm

sionna.fec.utils.pcm2gm(pcm, verify_results=True)[source]

Generate the generator matrix for a given parity-check matrix.

This function brings pcm \(\mathbf{H}\) in its systematic form and uses the following relation to find the generator matrix \(\mathbf{G}\) in GF(2)

\[\mathbf{G} = [\mathbf{I} | \mathbf{M}] \Leftrightarrow \mathbf{H} = [\mathbf{M} ^t | \mathbf{I}]. \tag{1}\]

This follows from the fact that for an all-zero syndrome, it must hold that

\[\mathbf{H} \mathbf{c}^t = \mathbf{H} * (\mathbf{u} * \mathbf{G})^t = \mathbf{H} * \mathbf{G} ^t * \mathbf{u}^t =: \mathbf{0}\]

where \(\mathbf{c}\) denotes an arbitrary codeword and \(\mathbf{u}\) the corresponding information bits.

This leads to

\[\mathbf{G} * \mathbf{H} ^t =: \mathbf{0}. \tag{2}\]

It can be seen that (1) fulfills (2) as in GF(2) it holds that

\[[\mathbf{I} | \mathbf{M}] * [\mathbf{M} ^t | \mathbf{I}]^t = \mathbf{M} + \mathbf{M} = \mathbf{0}.\]

Input

pcm (ndarray) – Binary parity-check matrix of shape [n-k, n].
verify_results (bool) – Defaults to True. If True, it is verified that the generated generator matrix is orthogonal to the parity-check matrix in GF(2).

Output

ndarray – Binary generator matrix of shape [k, n].

Note

This algorithm only works if pcm has full rank. Otherwise an error is raised.

verify_gm_pcm

sionna.fec.utils.verify_gm_pcm(gm, pcm)[source]

Verify that generator matrix \(\mathbf{G}\) gm and parity-check matrix \(\mathbf{H}\) pcm are orthogonal in GF(2).

For an all-zero syndrome, it must hold that

\[\mathbf{H} \mathbf{c}^t = \mathbf{H} * (\mathbf{u} * \mathbf{G})^t = \mathbf{H} * \mathbf{G} ^t * \mathbf{u}^t =: \mathbf{0}\]

where \(\mathbf{c}\) denotes an arbitrary codeword and \(\mathbf{u}\) the corresponding information bits.

As \(\mathbf{u}\) can be arbitrary it follows that

\[\mathbf{H} * \mathbf{G} ^t =: \mathbf{0}.\]

Input

gm (ndarray) – Binary generator matrix of shape [k, n].
pcm (ndarray) – Binary parity-check matrix of shape [n-k, n].

Output

bool – True if gm and pcm define a valid pair of parity-check and generator matrices in GF(2).

EXIT Analysis

The LDPC BP decoder allows to track the internal information flow (extrinsic information) during decoding. This can be plotted in so-called EXIT Charts [tenBrinkEXIT] to visualize the decoding convergence.

This short code snippet shows how to generate and plot EXIT charts:

# parameters
ebno_db = 2.5 # simulation SNR
batch_size = 10000
num_bits_per_symbol = 2 # QPSK

pcm_id = 4 # decide which parity check matrix should be used (0-2: BCH; 3: (3,6)-LDPC 4: LDPC 802.11n
pcm, k, n , coderate = load_parity_check_examples(pcm_id, verbose=True)

noise_var = ebnodb2no(ebno_db=ebno_db,
                      num_bits_per_symbol=num_bits_per_symbol,
                      coderate=coderate)

# init components
decoder = LDPCBPDecoder(pcm,
                        hard_out=False,
                        cn_type="boxplus",
                        trainable=False,
                        track_exit=True, # if activated, the decoder stores the outgoing extrinsic mutual information per iteration
                        num_iter=20)

# generates fake llrs as if the all-zero codeword was transmitted over an AWNG channel with BPSK modulation
llr_source = GaussianPriorSource()


# generate fake LLRs (Gaussian approximation)
llr = llr_source([[batch_size, n], noise_var])

# simulate free running decoder (for EXIT trajectory)
decoder(llr)

# calculate analytical EXIT characteristics
# Hint: these curves assume asymptotic code length, i.e., may become inaccurate in the short length regime
Ia, Iev, Iec = get_exit_analytic(pcm, ebno_db)

# and plot the analytical exit curves

plt = plot_exit_chart(Ia, Iev, Iec)

# and add simulated trajectory (requires "track_exit=True")
plot_trajectory(plt, decoder.ie_v, decoder.ie_c, ebno_db)

Remark: for rate-matched 5G LDPC codes, the EXIT approximation becomes inaccurate due to the rate-matching and the very specific structure of the code.

plot_exit_chart

sionna.fec.utils.plot_exit_chart(mi_a=None, mi_ev=None, mi_ec=None, title='EXIT-Chart')[source]

Utility function to plot EXIT-Charts [tenBrinkEXIT].

If all inputs are None an empty EXIT chart is generated. Otherwise, the mutual information curves are plotted.

Input

mi_a (float) – An ndarray of floats containing the a priori mutual information.
mi_v (float) – An ndarray of floats containing the variable node mutual information.
mi_c (float) – An ndarray of floats containing the check node mutual information.
title (str) – A string defining the title of the EXIT chart.

Output

plt (matplotlib.figure) – A matplotlib figure handle

Raises

AssertionError – If title is not str.

get_exit_analytic

sionna.fec.utils.get_exit_analytic(pcm, ebno_db)[source]

Calculate the analytic EXIT-curves for a given parity-check matrix.

This function extracts the degree profile from pcm and calculates the variable (VN) and check node (CN) decoder EXIT curves. Please note that this is an asymptotic tool which needs a certain codeword length for accurate predictions.

Transmission over an AWGN channel with BPSK modulation and SNR ebno_db is assumed. The detailed equations can be found in [tenBrink] and [tenBrinkEXIT].

Input

pcm (ndarray) – The parity-check matrix.
ebno_db (float) – The channel SNR in dB.

Output

mi_a (ndarray of floats) – NumPy array containing the a priori mutual information.
mi_ev (ndarray of floats) – NumPy array containing the extrinsic mutual information of the variable node decoder for the corresponding mi_a.
mi_ec (ndarray of floats) – NumPy array containing the extrinsic mutual information of the check node decoder for the corresponding mi_a.

Note

This function assumes random parity-check matrices without any imposed structure. Thus, explicit code construction algorithms may lead to inaccurate EXIT predictions. Further, this function is based on asymptotic properties of the code, i.e., only works well for large parity-check matrices. For details see [tenBrink].

plot_trajectory

sionna.fec.utils.plot_trajectory(plot, mi_v, mi_c, ebno=None)[source]

Utility function to plot the trajectory of an EXIT-chart.

Input

plot (matplotlib.figure) – A handle to a matplotlib figure.
mi_v (float) – An ndarray of floats containing the variable node mutual information.
mi_c (float) – An ndarray of floats containing the check node mutual information.
ebno (float) – A float denoting the EbNo in dB for the legend entry.

Miscellaneous

GaussianPriorSource

class sionna.fec.utils.GaussianPriorSource(specified_by_mi=False, dtype=tf.float32, **kwargs)[source]

Generates fake LLRs as if the all-zero codeword was transmitted over an Bi-AWGN channel with noise variance no or mutual information (if specified_by_mi is True). If selected, the mutual information denotes the mutual information associated with a binary random variable observed at the output of a corresponding AWGN channel (cf. Gaussian approximation).

The generated LLRs are drawn from a Gaussian distribution with

\[\sigma_{\text{llr}}^2 = \frac{4}{\sigma_\text{ch}^2}\]

and

\[\mu_{\text{llr}} = \frac{\sigma_\text{llr}^2}{2}\]

where \(\sigma_\text{ch}^2\) is the channel noise variance as defined by no.

If specified_by_mi is True, this class uses the of the so-called J-function (relates mutual information to Gaussian distributed LLRs) as proposed in [Brannstrom].

Parameters

specified_by_mi (bool) – Defaults to False. If True, the second input parameter no is interpreted as mutual information instead of noise variance.
dtype (tf.DType) – Defaults to tf.float32. Defines the datatype for internal calculations and the output. Must be one of the following (tf.float16, tf.bfloat16, tf.float32, tf.float64).

Input

(output_shape, no) – Tuple:
output_shape (tf.int) – Integer tensor or Python array defining the shape of the desired output tensor.
no (tf.float32) – Scalar defining the noise variance or mutual information (if specified_by_mi is True) of the corresponding (fake) AWGN channel.

Output

dtype, defaults to tf.float32 – 1+D Tensor with shape as defined by output_shape.

Raises

InvalidArgumentError – If mutual information is not in (0,1).
AssertionError – If inputs is not a list with 2 elements.

bin2int

sionna.fec.utils.bin2int(arr)[source]

Convert binary array to integer.

For example arr = [1, 0, 1] is converted to 5.

Input: arr (int or float) – An iterable that yields 0’s and 1’s.
Output: int – Integer representation of arr.

int2bin

sionna.fec.utils.int2bin(num, len_)[source]

Convert num of int type to list of length len_ with 0’s and 1’s. num and len_ have to non-negative.

For e.g., num = 5; int2bin(num, len_ =4) = [0, 1, 0, 1].

For e.g., num = 12; int2bin(num, len_ =3) = [1, 0, 0].

Input

num (int) – An integer to be converted into binary representation.
len_ (int) – An integer defining the length of the desired output.

Output

list of int – Binary representation of num of length len_.

bin2int_tf

sionna.fec.utils.bin2int_tf(arr)[source]

Converts binary tensor to int tensor. Binary representation in arr is across the last dimension from most significant to least significant.

For example arr = [0, 1, 1] is converted to 3.

Input: arr (int or float) – Tensor of 0’s and 1’s.
Output: int – Tensor containing the integer representation of arr.

int2bin_tf

sionna.fec.utils.int2bin_tf(ints, len_)[source]

Converts (int) tensor to (int) tensor with 0’s and 1’s. len_ should be to non-negative. Additional dimension of size len_ is inserted at end.

Input

ints (int) – Tensor of arbitrary shape […,k] containing integer to be converted into binary representation.
len_ (int) – An integer defining the length of the desired output.

Output

int – Tensor of same shape as ints except dimension of length len_ is added at the end […,k, len_]. Contains the binary representation of ints of length len_.

int_mod_2

sionna.fec.utils.int_mod_2(x)[source]

Efficient implementation of modulo 2 operation for integer inputs.

This function assumes integer inputs or implicitly casts to int.

Remark: the function tf.math.mod(x, 2) is placed on the CPU and, thus, causes unnecessary memory copies.

Parameters: x (tf.Tensor) – Tensor to which the modulo 2 operation is applied.

llr2mi

sionna.fec.utils.llr2mi(llr, s=None, reduce_dims=True)[source]

Implements an approximation of the mutual information based on LLRs.

The function approximates the mutual information for given llr as derived in [Hagenauer] assuming an all-zero codeword transmission

\[I \approx 1 - \sum \operatorname{log_2} \left( 1 + \operatorname{e}^{-\text{llr}} \right).\]

This approximation assumes that the following symmetry condition is fulfilled

\[p(\text{llr}|x=0) = p(\text{llr}|x=1) \cdot \operatorname{exp}(\text{llr}).\]

For non-all-zero codeword transmissions, this methods requires knowledge about the signs of the original bit sequence s and flips the signs correspondingly (as if the all-zero codeword was transmitted).

Please note that we define LLRs as \(\frac{p(x=1)}{p(x=0)}\), i.e., the sign of the LLRs differ to the solution in [Hagenauer].

Input

llr (tf.float32) – Tensor of arbitrary shape containing LLR-values.
s (None or tf.float32) – Tensor of same shape as llr containing the signs of the transmitted sequence (assuming BPSK), i.e., +/-1 values.
reduce_dims (bool) – Defaults to True. If True, all dimensions are reduced and the return is a scalar. Otherwise, reduce_mean is only taken over the last dimension.

Output

mi (tf.float32) – A scalar tensor (if reduce_dims is True) or a tensor of same shape as llr apart from the last dimensions that is removed. It contains the approximated value of the mutual information.

Raises

TypeError – If dtype of llr is not a real-valued float.

j_fun

sionna.fec.utils.j_fun(mu)[source]

Calculates the J-function in NumPy.

The so-called J-function relates mutual information to the mean of Gaussian distributed LLRs (cf. Gaussian approximation). We use the approximation as proposed in [Brannstrom] which can be written as

\[J(\mu) \approx \left( 1- 2^{H_\text{1}(2\mu)^{H_\text{2}}}\right)^{H_\text{2}}\]

with \(\mu\) denoting the mean value of the LLR distribution and \(H_\text{1}=0.3073\), \(H_\text{2}=0.8935\) and \(H_\text{3}=1.1064\).

Input: mu (float) – float or ndarray of float.
Output: float – ndarray of same shape as the input.

j_fun_inv

sionna.fec.utils.j_fun_inv(mi)[source]

Calculates the inverse J-function in NumPy.

The so-called J-function relates mutual information to the mean of Gaussian distributed LLRs (cf. Gaussian approximation). We use the approximation as proposed in [Brannstrom] which can be written as

\[J(\mu) \approx \left( 1- 2^{H_\text{1}(2\mu)^{H_\text{2}}}\right)^{H_\text{2}}\]

with \(\mu\) denoting the mean value of the LLR distribution and \(H_\text{1}=0.3073\), \(H_\text{2}=0.8935\) and \(H_\text{3}=1.1064\).

Input: mi (float) – float or ndarray of float.
Output: float – ndarray of same shape as the input.
Raises: AssertionError – If mi < 0.001 or mi > 0.999.

j_fun_tf

sionna.fec.utils.j_fun_tf(mu, verify_inputs=True)[source]

Calculates the J-function in Tensorflow.

The so-called J-function relates mutual information to the mean of Gaussian distributed LLRs (cf. Gaussian approximation). We use the approximation as proposed in [Brannstrom] which can be written as

\[J(\mu) \approx \left( 1- 2^{H_\text{1}(2\mu)^{H_\text{2}}}\right)^{H_\text{2}}\]

with \(\mu\) denoting the mean value of the LLR distribution and \(H_\text{1}=0.3073\), \(H_\text{2}=0.8935\) and \(H_\text{3}=1.1064\).

Input

mu (tf.float32) – Tensor of arbitrary shape.
verify_inputs (bool) – A boolean defaults to True. If True, mu is clipped internally to be numerical stable.

Output

tf.float32 – Tensor of same shape and dtype as mu.

Raises

InvalidArgumentError – If mu is negative.

j_fun_inv_tf

sionna.fec.utils.j_fun_inv_tf(mi, verify_inputs=True)[source]

Calculates the inverse J-function in Tensorflow.

The so-called J-function relates mutual information to the mean of Gaussian distributed LLRs (cf. Gaussian approximation). We use the approximation as proposed in [Brannstrom] which can be written as

\[J(\mu) \approx \left( 1- 2^{H_\text{1}(2\mu)^{H_\text{2}}}\right)^{H_\text{2}}\]

with \(\mu\) denoting the mean value of the LLR distribution and \(H_\text{1}=0.3073\), \(H_\text{2}=0.8935\) and \(H_\text{3}=1.1064\).

Input

mi (tf.float32) – Tensor of arbitrary shape.
verify_inputs (bool) – A boolean defaults to True. If True, mi is clipped internally to be numerical stable.

Output

tf.float32 – Tensor of same shape and dtype as the mi.

Raises

InvalidArgumentError – If mi is not in (0,1).

References:

tenBrinkEXIT(1,2,3): S. ten Brink, “Convergence Behavior of Iteratively Decoded Parallel Concatenated Codes,” IEEE Transactions on Communications, vol. 49, no. 10, pp. 1727-1737, 2001.
Brannstrom(1,2,3,4,5): F. Brannstrom, L. K. Rasmussen, and A. J. Grant, “Convergence analysis and optimal scheduling for multiple concatenated codes,” IEEE Trans. Inform. Theory, vol. 51, no. 9, pp. 3354–3364, 2005.
Hagenauer(1,2): J. Hagenauer, “The Turbo Principle in Mobile Communications,” in Proc. IEEE Int. Symp. Inf. Theory and its Appl. (ISITA), 2002.
tenBrink(1,2,3): S. ten Brink, G. Kramer, and A. Ashikhmin, “Design of low-density parity-check codes for modulation and detection,” IEEE Trans. Commun., vol. 52, no. 4, pp. 670–678, Apr. 2004.
MacKay(1,2,3,4,5): http://www.inference.org.uk/mackay/codes/alist.html
UniKL(1,2,3): https://www.uni-kl.de/en/channel-codes/