Convolutional Codes

This module supports encoding of convolutional codes and provides layers for Viterbi[Viterbi] and BCJR[BCJR] decoding.

While theViterbiDecoder decoding algorithm produces maximum likelihoodsequence estimates, theBCJRDecoder produces the maximum a posterior (MAP) bit-estimates.

The following code snippet shows how to set up a rate-1/2, constraint-length-3ConvEncoder in two alternate ways and a correspondingViterbiDecoder orBCJRDecoder. You can find further examples in theChannel Coding Tutorial Notebook.

Setting-up:

encoder=ConvEncoder(rate=1/2,# rate of the desired codeconstraint_length=3)# constraint length of the code# orencoder=ConvEncoder(gen_poly=['101','111'])# or polynomial can be used as input directly# --- Viterbi decoding ---decoder=ViterbiDecoder(gen_poly=encoder.gen_poly)# polynomial used in encoder# or just reference to the encoderdecoder=ViterbiDecoder(encoder=encoder)# the code parameters are infered from the encoder# --- or BCJR decoding ---decoder=BCJRDecoder(gen_poly=encoder.gen_poly,algorithm="map")# polynomial used in encoder# or just reference to the encoderdecoder=BCJRDecoder(encoder=encoder,algorithm="map")# the code parameters are infered from the encoder

Running the encoder / decoder:

# --- encoder ---# u contains the information bits to be encoded and has shape [...,k].# c contains the convolutional encoded codewords and has shape [...,n].c=encoder(u)# --- decoder ---# y contains the de-mapped received codeword from channel and has shape [...,n].# u_hat contains the estimated information bits and has shape [...,k].u_hat=decoder(y)

classsionna.phy.fec.conv.ConvEncoder(gen_poly=None,rate=0.5,constraint_length=3,rsc=False,terminate=False,precision=None,**kwargs)[source]

Encodes an information binary tensor to a convolutional codeword.

Currently, only generator polynomials for codes of rate=1/n for n=2,3,4,…are allowed.

Parameters:

• gen_poly (tuple) – Sequence of strings with each string being a 0,1 sequence. IfNone,rate andconstraint_length must be provided.

• rate (float) – Valid values are 1/3 and 0.5. Only required ifgen_poly isNone.

• constraint_length (int) – Valid values are between 3 and 8 inclusive. Only required ifgen_poly isNone.

• rsc (boolean) – Boolean flag indicating whether the Trellis generated is recursivesystematic or not. IfTrue, the encoder is recursive-systematic.In this case first polynomial ingen_poly is used as thefeedback polynomial. Defaults toFalse.

• terminate (boolean) – Encoder is terminated to all zero state ifTrue.If terminated, thetrue rate of the code is slightly lower thanrate.

• precision (None (default) | ‘single’ | ‘double’) – Precision used for internal calculations and outputs.If set toNone,precision is used.

Input:

bits ([…,k], tf.float) – Binary tensor containing the information bits wherek is theinformation length

Output:

[…,k/rate], tf.float – Binary tensor containing the encoded codeword for the given inputinformation tensor whererate is\(\frac{1}{\textrm{len}\left(\textrm{gen_poly}\right)}\)(ifgen_poly is provided).

Note

The generator polynomials from[Moon] are available for variousrate and constraint lengths. To select them, use therate andconstraint_length arguments.

In addition, polynomials for any non-recursive convolutional encodercan be given as input viagen_poly argument. Currently, onlypolynomials with rate=1/n are supported. When thegen_poly argumentis given, therate andconstraint_length arguments are ignored.

Various notations are used in the literature to represent the generatorpolynomials for convolutional codes. In[Moon], the octal digitsformat is primarily used. In the octal format, the generator polynomial10011 corresponds to 46. Another widely used formatis decimal notation with MSB. In this notation, polynomial10011corresponds to 19. For simplicity, theConvEncoder only accepts the bitformat i.e.10011 asgen_poly argument.

Also note thatconstraint_length andmemory are two differentterms often used to denote the strength of a convolutional code. In thissub-package, we useconstraint_length. For example, thepolynomial10011 has aconstraint_length of 5, however itsmemory is only 4.

Whenterminate isTrue, the true rate of the convolutionalcode is slightly lower thanrate. It equals\(\frac{r*k}{k+\mu}\) wherer denotesrate and\(\mu\) isconstraint_length - 1. For example whenterminate isTrue,k=100,\(\mu=4\) andrate =0.5, true rate equals\(\frac{0.5*100}{104}=0.481\).

propertycoderate

Rate of the code used in the encoder

propertygen_poly

Generator polynomial used by the encoder

propertyk

Number of information bits per codeword

propertyn

Number of codeword bits

propertyterminate

Indicates if the convolutional encoder is terminated

propertytrellis

Trellis object used during encoding

classsionna.phy.fec.conv.ViterbiDecoder(*,encoder=None,gen_poly=None,rate=0.5,constraint_length=3,rsc=False,terminate=False,method='soft_llr',return_info_bits=True,precision=None,**kwargs)[source]

Applies Viterbi decoding to a sequence of noisy codeword bits

Implements the Viterbi decoding algorithm[Viterbi] that returns anestimate of the information bits for a noisy convolutional codeword.Takes as input either LLR values (method =soft_llr) or hard bit values(method =hard) and returns a hard decided estimation of the informationbits.

Parameters:

• encoder (ConvEncoder) – Ifencoder is provided as input, the following input parametersare not required and will be ignored:gen_poly,rate,constraint_length,rsc,terminate. They will be inferredfrom theencoder object itself. Ifencoder isNone, theabove parameters must be provided explicitly.

• gen_poly (tuple |None) – tuple of strings with each string being a 0, 1 sequence. IfNone,rate andconstraint_length must be provided.

• rate (float,1/2 |1/3) – Valid values are 1/3 and 0.5. Only required ifgen_poly isNone.

• constraint_length (int,3....8) – Valid values are between 3 and 8 inclusive. Only required ifgen_poly isNone.

• rsc (bool, (defaultFalse)) – Boolean flag indicating whether the encoder is recursive-systematic forgiven generator polynomials.True indicates encoder is recursive-systematic.False indicates encoder is feed-forward non-systematic.

• terminate (bool, (defaultFalse)) – Boolean flag indicating whether the codeword is terminated.True indicates codeword is terminated to all-zero state.False indicates codeword is not terminated.

• method (str,soft_llr |hard) – Valid values aresoft_llr orhard. In computing pathmetrics,soft_llr expects channel LLRs as inputhard assumes abinary symmetric channel (BSC) with 0/1 values areinputs. In case ofhard,inputs will be quantized to 0/1 values.

• return_info_bots (bool, (defaultTrue)) – Boolean flag indicating whether only the information bits or allcodeword bits are returned.

• precision (None (default) | ‘single’ | ‘double’) – Precision used for internal calculations and outputs.If set toNone,precision is used.

Input:

inputs ([…,n], tf.float) – Tensor containing the (noisy) channel output symbols wherendenotes the codeword length

Output:

[…,rate*n], tf.float – Binary tensor containing the estimates of the information bit tensor

Note

A full implementation of the decoder rather than a windowed approachis used. For a given codeword of durationT, the path metric iscomputed from time0 toT and the path with optimal metric at timeT is selected. The optimal path is then traced back fromT to0to output the estimate of the information bit vector used to encode.For larger codewords, note that the current method is sub-optimalin terms of memory utilization and latency.

propertycoderate

Rate of the code used in the encoder

propertygen_poly

Generator polynomial used by the encoder

propertyk

Number of information bits per codeword

propertyn

Number of codeword bits

propertyterminate

Indicates if the encoder is terminated during codeword generation

propertytrellis

Trellis object used during encoding

classsionna.phy.fec.conv.BCJRDecoder(encoder=None,gen_poly=None,rate=0.5,constraint_length=3,rsc=False,terminate=False,hard_out=True,algorithm='map',precision=None,**kwargs)[source]

Applies BCJR decoding to a sequence of noisy codeword bits

Implements the BCJR decoding algorithm[BCJR] that returns anestimate of the information bits for a noisy convolutional codeword.Takes as input either channel LLRs and a priori LLRs (optional).Returns an estimate of the information bits, either output LLRs (hard_out =False) or hard decoded bits (hard_out =True),respectively.

Parameters:

• encoder (ConvEncoder) – Ifencoder is provided as input, the following input parametersare not required and will be ignored:gen_poly,rate,constraint_length,rsc,terminate. They will be inferredfrom theencoder object itself. Ifencoder isNone, theabove parameters must be provided explicitly.

• gen_poly (tuple |None) – tuple of strings with each string being a 0, 1 sequence. IfNone,rate andconstraint_length must be provided.

• rate (float,None (default)|1/3 |1/2) – Valid values are 1/3 and 1/2. Only required ifgen_poly isNone.

• constraint_length (int,3...8) – Valid values are between 3 and 8 inclusive. Only required ifgen_poly isNone.

• rsc (bool, (defaultFalse)) – Boolean flag indicating whether the encoder is recursive-systematic forgiven generator polynomials.True indicates encoder isrecursive-systematic.False indicates encoder is feed-forwardnon-systematic.

• terminate (bool, (defaultFalse)) – Boolean flag indicating whether the codeword is terminated.True indicates codeword is terminated to all-zero state.False indicates codeword is not terminated.

• hard_out (bool, (defaultTrue)) – Boolean flag indicating whether to output hard or soft decisions onthe decoded information vector.True implies a hard-decoded information vector of 0/1’s as output.False implies output is decoded LLR’s of the information.

• algorithm (str,map (default) |log |maxlog) – Indicates the implemented BCJR algorithm,wheremap denotes the exact MAP algorithm,log indicates theexact MAP implementation, but in log-domain, andmaxlog indicates the approximated MAP implementation in log-domain,where\(\log(e^{a}+e^{b}) \sim \max(a,b)\).

• precision (None (default) | ‘single’ | ‘double’) – Precision used for internal calculations and outputs.If set toNone,precision is used.

Input:

• llr_ch ([…,n], tf.float) – Tensor containing the (noisy) channelLLRs, wheren denotes the codeword length

• llr_a ([…,k], None (default) | tf.float) – Tensor containing the a priori information of each information bit.Implicitly assumed to be 0 if onlyllr_ch is provided.

Output:

tf.float – Tensor of shape[…,coderate*n] containing the estimates of theinformation bit tensor

propertycoderate

Rate of the code used in the encoder

propertygen_poly

Generator polynomial used by the encoder

propertyk

Number of information bits per codeword

propertyn

Number of codeword bits

propertyterminate

Indicates if the encoder is terminated during codeword generation

propertytrellis

Trellis object used during encoding