Linear Codes
This package provides generic support for binary linear block codes.
For encoding, a universalLinearEncoder is available and can be initialized with either a generator or parity-check matrix. The matrix must be binary and of full rank.
For decoding,OSDecoder implements theordered-statistics decoding (OSD) algorithm[Fossorier] which provides close tomaximum-likelihood (ML) estimates for a sufficiently large order of the decoder.Please note that OSD is highly complex and not feasible for all code lengths.
Remark: As this package provides support for generic encoding and decoding(including Polar and LDPC codes), it cannot rely on code specificoptimizations. To benefit from an optimized decoder and keep the complexity as low as possible, please use the code specific enc-/decoders whenever available.
The encoder and decoder can be set up as follows:
pcm,k,n,coderate=load_parity_check_examples(pcm_id=1)# load example code# or directly import an external parity-check matrix in alist formatal=load_alist(path=filename)pcm,k,n,coderate=alist2mat(al)# encoder can be directly initialized with the parity-check matrixencoder=LinearEncoder(enc_mat=pcm,is_pcm=True)# decoder can be initialized with generator or parity-check matrixdecoder=OSDecoder(pcm,t=4,is_pcm=True)# t is the OSD order# or instantiated from a specific encoderdecoder=OSDecoder(encoder=encoder,t=4)# t is the OSD order
We can now run the encoder and decoder:
# u contains the information bits to be encoded and has shape [...,k].# c contains codeword bits and has shape [...,n]c=encoder(u)# after transmission LLRs must be calculated with a demapper# let's assume the resulting llr_ch has shape [...,n]c_hat=decoder(llr_ch)
- classsionna.phy.fec.linear.LinearEncoder(enc_mat,*,is_pcm=False,precision=None,**kwargs)[source]
Linear binary encoder for a given generator or parity-check matrix.
If
is_pcmisTrue,enc_matis interpreted as parity-checkmatrix and internally converted to a corresponding generator matrix.- Parameters:
enc_mat ([k,n] or[n-k,n],ndarray) – Binary generator matrix of shape[k, n]. If
is_pcmisTrue,enc_matis interpreted as parity-check matrix of shape[n-k, n].is_pcm (bool, (defaultFalse)) – IfTrue, theenc_mat is interpreted as parity-check matrix instead ofa generator matrix
precision (None (default) | ‘single’ | ‘double’) – Precision used for internal calculations and outputs.If set toNone,
precisionis used.
- Input:
info_bits ([…,k], tf.float or tf.int) – Binary tensor containing the information bits.
- Output:
[…,n], same dtype as info_bits – Binary tensor containing codewords with same shape as inputs,except the last dimension changes to[…,n].
Note
If
is_pcmisTrue, this block usespcm2gmto find the generator matrix forencoding. Please note that this imposes a few constraints on theprovided parity-check matrix such as full rank and it must be binary.Note that this encoder is generic for all binary linear block codesand, thus, cannot implement any code specific optimizations. As aresult, the encoding complexity is\(O(k^2)\). Please consider codespecific encoders such as the
Polar5GEncoderorLDPC5GEncoderfor an improvedencoding performance.- propertycoderate
Coderate of the code
- propertygm
Generator matrix used for encoding
- propertyk
Number of information bits per codeword
- propertyn
Codeword length
- classsionna.phy.fec.linear.OSDecoder(enc_mat=None,t=0,is_pcm=False,encoder=None,precision=None,**kwargs)[source]
Ordered statistics decoding (OSD) for binary, linear block codes.
This block implements the OSD algorithm as proposed in[Fossorier] and,thereby, approximates maximum likelihood decoding for a sufficiently largeorder\(t\). The algorithm works for arbitrary linear block codes, buthas a high computational complexity for long codes.
The algorithm consists of the following steps:
1. Sort LLRs according to their reliability and apply the same columnpermutation to the generator matrix.
2. Bring the permuted generator matrix into its systematic form(so-calledmost-reliable basis).
3. Hard-decide and re-encode the\(k\) most reliable bits anddiscard the remaining\(n-k\) received positions.
4. Generate all possible error patterns up to\(t\) errors in the\(k\) most reliable positions find the most likely codeword withinthese candidates.
This implementation of the OSD algorithm uses the LLR-based distance metricfrom[Stimming_LLR_OSD] which simplifies the handling of higher-ordermodulation schemes.
- Parameters:
enc_mat ([k,n] or[n-k,n],ndarray) – Binary generator matrix of shape[k, n]. If
is_pcmisTrue,enc_matis interpreted as parity-check matrix of shape[n-k, n].t (int) – Order of the OSD algorithm
is_pcm (bool, (defaultFalse)) – IfTrue,
enc_matis interpreted as parity-check matrix.encoder (Block |None) – Sionna block that implements a FEC encoder.If not None,
enc_matwill be ignored and the code as specified bythe encoder is used to initialize OSD.precision (None (default) | ‘single’ | ‘double’) – Precision used for internal calculations and outputs.If set toNone,
precisionis used.
- Input:
llr_ch ([…,n], tf.float) – Tensor containing the channel logits/llr values.
- Output:
[…,n], tf.float – Tensor of same shape as
llr_chcontainingbinary hard-decisions of all codeword bits.
Note
OS decoding is of high complexity and is only feasible for small values of\(t\) as\({n \choose t}\) patterns must be evaluated. Theadvantage of OSD is that it works for arbitrary linear block codes andprovides an estimate of the expected ML performance for sufficiently large\(t\). However, for some code families, more efficient decodingalgorithms with close to ML performance exist which can exploit certaincode specific properties. Examples of such decoders are the
ViterbiDecoderalgorithm for convolutional codesor thePolarSCLDecoderfor Polar codes(for a sufficiently large list size).It is recommended to run the decoder in XLA mode as itsignificantly reduces the memory complexity.
- propertygm
Generator matrix of the code
- propertyk
Number of information bits per codeword
- propertyn
Codeword length
- propertyt
Order of the OSD algorithm
- References:
- [Fossorier](1,2)
M. Fossorier, S. Lin, “Soft-Decision Decoding of LinearBlock Codes Based on Ordered Statistics”, IEEE Trans. Inf.Theory, vol. 41, no.5, 1995.
[Stimming_LLR_OSD]A.Balatsoukas-Stimming, M. Parizi, A. Burg,“LLR-Based Successive Cancellation List Decodingof Polar Codes.” IEEE Trans Signal Processing, 2015.