Polar Codes

The Polar code module supports 5G-compliant Polar codes and includes successive cancellation (SC), successive cancellation list (SCL), and belief propagation (BP) decoding.

The module supports rate-matching and CRC-aided decoding.Further, Reed-Muller (RM) code design is available and can be used in combination with the Polar encoding/decoding algorithms.

The following code snippets show how to setup and run a rate-matched 5G compliant Polar encoder and a corresponding successive cancellation list (SCL) decoder.

First, we need to create instances ofPolar5GEncoder andPolar5GDecoder:

encoder=Polar5GEncoder(k=100,# number of information bits (input)n=200)# number of codeword bits (output)decoder=Polar5GDecoder(encoder=encoder,# connect the Polar decoder to the encoderdec_type="SCL",# can be also "SC" or "BP"list_size=8)

Now, the encoder and decoder can be used by:

# --- encoder ---# u contains the information bits to be encoded and has shape [...,k].# c contains the polar encoded codewords and has shape [...,n].c=encoder(u)# --- decoder ---# llr contains the log-likelihood ratios from the demapper and has shape [...,n].# u_hat contains the estimated information bits and has shape [...,k].u_hat=decoder(llr)

classsionna.phy.fec.polar.encoding.Polar5GEncoder(k,n,channel_type='uplink',verbose=False,precision=None,**kwargs)[source]

5G compliant Polar encoder including rate-matching following[3GPPTS38212] for the uplink scenario (UCI) and downlink scenario (DCI).

This block performs polar encoding fork information bits andrate-matching such that the codeword lengths isn. This includes the CRCconcatenation and the interleaving as defined in[3GPPTS38212].

Note:block segmentation is currently not supported (I_seq=False).

We follow the basic structure from Fig. 6 in[Bioglio_Design].

For further details, we refer to[3GPPTS38212],[Bioglio_Design] and[Hui_ChannelCoding].

Parameters:

• k (int) – Defining the number of information bit per codeword.

• n (int) – Defining the codeword length.

• channel_type ('uplink' (default)|'downlink') – Can be ‘uplink’ or ‘downlink’.

• verbose (bool, (defaultFalse)) – IfTrue, rate-matching parameters will be printed.

• 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 to be encoded.

Output:

[…,n], tf.float – Binary tensor containing the codeword bits.

Note

The encoder supports theuplink Polar coding (UCI) scheme from[3GPPTS38212] and thedownlink Polar coding (DCI)[3GPPTS38212],respectively.

For12 <= k <= 19 the 3 additional parity bits as defined in[3GPPTS38212] are not implemented as it would also require amodified decoding procedure to materialize the potential gains.

Code segmentation is currently not supported and, thus,n islimited to a maximum length of 1088 codeword bits.

For the downlink scenario, the input length is limited tok <= 140information bits due to the limited input bit interleaver size[3GPPTS38212].

For simplicity, the implementation does not exactly re-implement theDCI scheme from[3GPPTS38212]. This implementation neglects theall-one initialization of the CRC shift register and the scrambling of the CRC parity bits with theRNTI.

channel_interleaver(c)[source]

Triangular interleaver following Sec. 5.4.1.3 in[3GPPTS38212].

Input:

c (ndarray) – 1D array to be interleaved.

Output:

ndarray – Interleaved version ofc with same shape and dtype asc.

propertyenc_crc

CRC encoder block used for CRC concatenation

input_interleaver(c)[source]

Input interleaver following Sec. 5.4.1.1 in[3GPPTS38212].

Input:

c (ndarray) – 1D array to be interleaved.

Output:

ndarray – Interleaved version ofc with same shape and dtype asc.

propertyk

Number of information bits including rate-matching

propertyk_polar

Number of information bits of the underlying Polar code

propertyk_target

Number of information bits including rate-matching

propertyn

Codeword length including rate-matching

propertyn_polar

Codeword length of the underlying Polar code

propertyn_target

Codeword length including rate-matching

subblock_interleaving(u)[source]

Input bit interleaving as defined in Sec 5.4.1.1[3GPPTS38212].

Input:

u (ndarray) – 1D array to be interleaved. Length ofu must be a multipleof 32.

Output:

ndarray – Interleaved version ofu with same shape and dtype asu.

classsionna.phy.fec.polar.encoding.PolarEncoder(frozen_pos,n,precision=None,**kwargs)[source]

Polar encoder for given code parameters.

This block performs polar encoding for the givenk information bits andthefrozen set (i.e., indices of frozen positions) specified byfrozen_pos.

Parameters:

• frozen_pos (ndarray) – Array ofint defining then-k frozen indices, i.e., informationbits are mapped onto thek complementary positions.

• n (int) – Defining the codeword length.

• 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 to be encoded.

Output:

[…,n], tf.float – Binary tensor containing the codeword bits.

Note

As commonly done, we assume frozen bits are set to0. Please notethat - although its practical relevance is only little - setting frozenbits to1 may result inaffine codes instead of linear code as theall-zero codeword is not necessarily part of the code any more.

propertyfrozen_pos

Frozen positions for Polar decoding

propertyinfo_pos

Information bit positions for Polar encoding

propertyk

Number of information bits

propertyn

Codeword length

classsionna.phy.fec.polar.decoding.Polar5GDecoder(enc_polar,dec_type='SC',list_size=8,num_iter=20,return_crc_status=False,precision=None,**kwargs)[source]

Wrapper for 5G compliant decoding including rate-recovery and CRC removal.

Parameters:

• enc_polar (Polar5GEncoder) – Instance of thePolar5GEncoderused for encoding including rate-matching.

• dec_type ("SC" (default)|"SCL" |"hybSCL" |"BP") – Defining the decoder to be used.Must be one of the following{“SC”, “SCL”, “hybSCL”, “BP”}.

• list_size (int,(default 8)) – Defining the list sizeiff list-decoding is used.Only required fordec_types{“SCL”, “hybSCL”}.

• num_iter (int,(default 20)) – Defining the number of BP iterations. Only required fordec_type“BP”.

• return_crc_status (bool, (defaultFalse)) – IfTrue, the decoder additionally returns the CRC status indicatingif a codeword was (most likely) correctly recovered.

• 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 channel logits/llr values.

Output:

• b_hat ([…,k], tf.float) – Binary tensor containing hard-decided estimations of allkinformation bits.

• crc_status ([…], tf.bool) – CRC status indicating if a codeword was (most likely) correctlyrecovered. This is only returned ifreturn_crc_status is True.Note that false positives are possible.

Note

This block supports the uplink and downlink Polar rate-matching schemewithoutcodeword segmentation.

Although the decodinglist size is not provided by 3GPP[3GPPTS38212], the consortium has agreed on alist size of 8 for the5G decoding reference curves[Bioglio_Design].

All list-decoders applyCRC-aided decoding, however, the non-listdecoders (“SC” and“BP”) cannot materialize the CRC leading to aneffective rate-loss.

propertydec_type

Decoder type used for decoding as str

propertyfrozen_pos

Frozen positions for Polar decoding

propertyinfo_pos

Information bit positions for Polar encoding

propertyk_polar

Number of information bits of mother Polar code

propertyk_target

Number of information bits including rate-matching

propertyllr_max

Maximum LLR value for internal calculations

propertyn_polar

Codeword length of mother Polar code

propertyn_target

Codeword length including rate-matching

propertypolar_dec

Decoder instance used for decoding

classsionna.phy.fec.polar.decoding.PolarSCDecoder(frozen_pos,n,precision=None,**kwargs)[source]

Successive cancellation (SC) decoder[Arikan_Polar] for Polar codes andPolar-like codes.

Parameters:

• frozen_pos (ndarray) – Array ofint defining then-k indices of the frozen positions.

• n (int) – Defining the codeword length.

• 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 channel LLR values (as logits).

Output:

[…,k], tf.float – Tensor containing hard-decided estimations of allkinformation bits.

Note

This block implements the SC decoder as described in[Arikan_Polar]. However, the implementation follows therecursivetree[Gross_Fast_SCL] terminology and combines nodes for increasedthroughputs without changing the outcome of the algorithm.

As commonly done, we assume frozen bits are set to0. Please notethat - although its practical relevance is only little - setting frozenbits to1 may result inaffine codes instead of linear code as theall-zero codeword is not necessarily part of the code any more.

propertyfrozen_pos

Frozen positions for Polar decoding

propertyinfo_pos

Information bit positions for Polar encoding

propertyk

Number of information bits

propertyllr_max

Maximum LLR value for internal calculations

propertyn

Codeword length

classsionna.phy.fec.polar.decoding.PolarSCLDecoder(frozen_pos,n,list_size=8,crc_degree=None,use_hybrid_sc=False,use_fast_scl=True,cpu_only=False,use_scatter=False,ind_iil_inv=None,return_crc_status=False,precision=None,**kwargs)[source]

Successive cancellation list (SCL) decoder[Tal_SCL] for Polar codesand Polar-like codes.

Parameters:

• frozen_pos (ndarray) – Array ofint defining then-k indices of the frozen positions.

• n (int) – Defining the codeword length.

• list_size (int,(default 8)) – Defines the list size of the decoder.

• crc_degree (str,"CRC24A" |"CRC24B" |"CRC24C" |"CRC16" |"CRC11" |"CRC6") – Defining the CRC polynomial to be used. Can be any value from{CRC24A, CRC24B, CRC24C, CRC16, CRC11, CRC6}.

• use_hybrid_sc (bool, (defaultFalse)) – IfTrue, SC decoding is applied and only the codewords with invalidCRC are decoded with SCL. This option requires an outer CRC specifiedviacrc_degree. Remark: hybrid_sc does not support XLA optimization,i.e.,@tf.function(jit_compile=True).

• use_fast_scl (bool, (defaultTrue)) – IfTrue, Tree pruning is used toreduce the decoding complexity. The output is equivalent to thenon-pruned version (besides numerical differences).

• cpu_only (bool, (defaultFalse)) – IfTrue,tf.py_function embedding is used and the decoder runs onthe CPU. This option is usually slower, but also more memory efficientand in particular, recommended for larger blocklengths. Remark: cpu_onlydoes not support XLA optimization@tf.function(jit_compile=True).

• use_scatter (bool, (defaultFalse)) – IfTrue,tf.tensor_scatter_update is used for tensor updates. Thisoption is usually slower, but more memory efficient.

• ind_iil_inv (None or[k+k_crc],int ortf.int) – Defaults to None. If notNone, the sequence is used as inverseinput bit interleaver before evaluating the CRC.Remark: this only effects the CRC evaluation but the outputsequence is not permuted.

• return_crc_status (bool, (defaultFalse)) – IfTrue, the decoder additionally returns the CRC status indicatingif a codeword was (most likely) correctly recovered. This is onlyavailable ifcrc_degree is not None.

• 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 channel LLR values (as logits).

Output:

• b_hat ([…,k], tf.float) – Binary tensor containing hard-decided estimations of allkinformation bits.

• crc_status ([…], tf.bool) – CRC status indicating if a codeword was (most likely) correctlyrecovered. This is only returned ifreturn_crc_status is True.Note that false positives are possible.

Note

This block implements the successive cancellation list (SCL) decoderas described in[Tal_SCL] but uses LLR-based message updates[Stimming_LLR]. The implementation follows the notation from[Gross_Fast_SCL],[Hashemi_SSCL]. If optionuse_fast_scl is activetree pruning is used and tree nodes are combined if possible (see[Hashemi_SSCL] for details).

Implementing SCL decoding as TensorFlow graph is a difficult task thatrequires several design tradeoffs to match the TF constraints whilemaintaining a reasonable throughput. Thus, the decoder minimizesthecontrol flow as much as possible, leading to a strong memoryoccupation (e.g., due to full path duplication after each decision).For longer code lengths, the complexity of the decoding graph becomeslarge and we recommend to use theCPU_only option that uses anembedded Numpy decoder. Further, this function recursively unrolls theSCL decoding tree, thus, for larger values ofn building thedecoding graph can become time consuming. Please consider thecpu_only option if building the graph takes to long.

A hybrid SC/SCL decoder as proposed in[Cammerer_Hybrid_SCL] (using SCinstead of BP) can be activated with optionuse_hybrid_sc iff anouter CRC is available. Please note that the results are not exactlySCL performance caused by the false positive rate of the CRC.

As commonly done, we assume frozen bits are set to0. Please notethat - although its practical relevance is only little - setting frozenbits to1 may result inaffine codes instead of linear code as theall-zero codeword is not necessarily part of the code any more.

propertyfrozen_pos

Frozen positions for Polar decoding

propertyinfo_pos

Information bit positions for Polar encoding

propertyk

Number of information bits

propertyk_crc

Number of CRC bits

propertylist_size

List size for SCL decoding

propertyllr_max

Maximum LLR value for internal calculations

propertyn

Codeword length

classsionna.phy.fec.polar.decoding.PolarBPDecoder(frozen_pos,n,num_iter=20,hard_out=True,precision=None,**kwargs)[source]

Belief propagation (BP) decoder for Polar codes[Arikan_Polar] andPolar-like codes based on[Arikan_BP] and[Forney_Graphs].

Remark: The PolarBPDecoder does currently not support XLA.

Parameters:

• frozen_pos (ndarray) – Array ofint defining then-k indices of the frozen positions.

• n (int) – Defining the codeword length.

• num_iter (int) – Defining the number of decoder iterations (no early stopping usedat the moment).

• hard_out (bool, (defaultTrue)) – IfTrue, the decoder provides hard-decidedinformation bits instead of soft-values.

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

Input:

llr_ch ([…,n], tf.float32) – Tensor containing the channel logits/llr values.

Output:

[…,k], tf.float32 – Tensor containing bit-wise soft-estimates(or hard-decided bit-values) of allk information bits.

Note

This decoder is fully differentiable and, thus, well-suited forgradient descent-based learning tasks such aslearned code design[Ebada_Design].

As commonly done, we assume frozen bits are set to0. Please notethat - although its practical relevance is only little - setting frozenbits to1 may result inaffine codes instead of linear code as theall-zero codeword is not necessarily part of the code any more.

propertyfrozen_pos

Frozen positions for Polar decoding

propertyhard_out

Indicates if decoder hard-decides outputs

propertyinfo_pos

Information bit positions for Polar encoding

propertyk

Number of information bits

propertyllr_max

Maximum LLR value for internal calculations

propertyn

Codeword length

propertynum_iter

Number of decoding iterations