Reed Muller Codes in 5G

The Reed Muller codes are used in 5G to encode the small payload of control information having a block length between 3 to 11. These codes are linear block codes which generalizes the Reed–Solomon codes and the Walsh–Hadamard code. These codes are - locally testable, - locally decodable, and - list decodable.

In this tutorial, we will analyze the bit error rate performance of Reed Muller Codes for different link conditions characterized by signal to noise ratio(SNR). We further will demonstrate the variation in performance with block-length. The content of the tutorial is as follows:

Table of content:

Import Libraries

Python Libraries

[1]:

# %matplotlib widget
import matplotlib.pyplot as plt

import os
os.environ["CUDA_VISIBLE_DEVICES"] = "-1"
os.environ['TF_CPP_MIN_LOG_LEVEL'] = '3'

import matplotlib as mpl
from mpl_toolkits.axes_grid1.inset_locator import zoomed_inset_axes
from mpl_toolkits.axes_grid1.inset_locator import mark_inset

import numpy as np

5G Toolkit Libraries

[2]:

from toolkit5G.SymbolMapping import Demapper
from toolkit5G.SymbolMapping import Mapper
from toolkit5G.ChannelCoder  import ReedMullerEncoder5G
from toolkit5G.ChannelCoder  import ReedMullerDecoder5G

[3]:

# from IPython.display import display, HTML
# display(HTML("<style>.container { width:100% !important; }</style>"))

Mapper and Demapper Parameters

Symbol mapping/Demapping is performed for:

  • BPSK constellation defined by constellation_type which encodes

  • 1 bit per contellation symbol defined by num_bits_per_symbol.

  • The demapper generates log likelihood ratios configured by hard_out

  • using a Log-Map (“app”) decoder defined using demapping_method.

[4]:

constellation_type  = "bpsk"
num_bits_per_symbol = 1
hard_out            = False
demapping_method    = "app"

mapper  = Mapper(constellation_type, num_bits_per_symbol)
demapper= Demapper(demapping_method, constellation_type,  num_bits_per_symbol, hard_out = hard_out)

Simulation Parameters

The simulations parameters are:

  • K defines block-length.

  • SNRdB defines Signal to noise ratio (SNR) in dB.

  • numBatches defines number of batches to compute average BER.

[5]:

K          = np.arange(1,12)
SNRdB      = np.linspace(-10,0,5)
SNR        = 10**(SNRdB/10)
numBatches = 5000

Simulation

This subsection performs the simulation which involve following steps:

  • Bits generation of length k

  • Reed Muller Encoding

  • BPSK Symbol Mapping of encoded bits

  • Passing through the AWGN Channel

    • Adding noise to BPSK symbols with a given SNR

  • Symbol De-mapping using Log Map Demapper defined by "app".

    • Generates Log likelihood values as hard_out is set to False.

  • Reed Muller Decoding

  • BER computation

The flow of the implementation can be understood using folowing diagram: ReedMuller

The bit error rate (BER) is computed for every combination of K \(= \{1,2,3,\dots,11\}\) and SNR \(= \{-10, -8, -6, -4, -2, 0\}\) dB and averaged over \(500000\) batches (monteCarloIterations).

[6]:

BER      = np.zeros((K.size, SNR.size))
kIndex   = 0
snrIndex = 0

for k in K:
    #######################################################
    ################ Generate UCI Payload #################
    #######################################################
    bits     = np.random.randint(2, size = (numBatches, k))

    #######################################################
    ################ Reed Muller Encoder ##################
    #######################################################
    codeword = ReedMullerEncoder5G()(bits)

    #######################################################
    ################### Symbol Mapping ####################
    #######################################################
    symbols  = mapper(codeword)

    decoder  = ReedMullerDecoder5G(k, hard_out)
    snrIndex = 0
    for snr in SNR:

        #######################################################
        ################ Add Noise at Receiver ################
        #######################################################
        symbs    = symbols + np.sqrt(0.5/snr)*(np.random.standard_normal(size=symbols.shape)+1j*np.random.standard_normal(size=symbols.shape)).astype(np.complex64)

        #######################################################
        ################## Symbol Demapping ###################
        #######################################################
        llrEst   = demapper([symbs,  np.float32(1/snr)])

        #######################################################
        ################ Reed Muller Decoder ##################
        #######################################################
        rxBits   = decoder(llrEst)

        #######################################################
        ############## Key Performance Metrics ################
        #######################################################
        BER[kIndex, snrIndex] = np.mean(np.abs(rxBits-bits))

        print("For K="+str(k)+", At SNR(dB): "+str(SNRdB[snrIndex])+" | Bit Error Rate: "+str(BER[kIndex, snrIndex]))

        snrIndex = snrIndex + 1
    kIndex = kIndex + 1

For K=1, At SNR(dB): -10.0 | Bit Error Rate: 0.2138
For K=1, At SNR(dB): -7.5 | Bit Error Rate: 0.085
For K=1, At SNR(dB): -5.0 | Bit Error Rate: 0.012
For K=1, At SNR(dB): -2.5 | Bit Error Rate: 0.0002
For K=1, At SNR(dB): 0.0 | Bit Error Rate: 0.0
For K=2, At SNR(dB): -10.0 | Bit Error Rate: 0.2157
For K=2, At SNR(dB): -7.5 | Bit Error Rate: 0.0908
For K=2, At SNR(dB): -5.0 | Bit Error Rate: 0.0116
For K=2, At SNR(dB): -2.5 | Bit Error Rate: 0.0005
For K=2, At SNR(dB): 0.0 | Bit Error Rate: 0.0
For K=3, At SNR(dB): -10.0 | Bit Error Rate: 0.2242
For K=3, At SNR(dB): -7.5 | Bit Error Rate: 0.08566666666666667
For K=3, At SNR(dB): -5.0 | Bit Error Rate: 0.0122
For K=3, At SNR(dB): -2.5 | Bit Error Rate: 0.0006
For K=3, At SNR(dB): 0.0 | Bit Error Rate: 0.0
For K=4, At SNR(dB): -10.0 | Bit Error Rate: 0.21985
For K=4, At SNR(dB): -7.5 | Bit Error Rate: 0.0873
For K=4, At SNR(dB): -5.0 | Bit Error Rate: 0.0141
For K=4, At SNR(dB): -2.5 | Bit Error Rate: 0.00025
For K=4, At SNR(dB): 0.0 | Bit Error Rate: 0.0
For K=5, At SNR(dB): -10.0 | Bit Error Rate: 0.21676
For K=5, At SNR(dB): -7.5 | Bit Error Rate: 0.08864
For K=5, At SNR(dB): -5.0 | Bit Error Rate: 0.00996
For K=5, At SNR(dB): -2.5 | Bit Error Rate: 0.0004
For K=5, At SNR(dB): 0.0 | Bit Error Rate: 0.0
For K=6, At SNR(dB): -10.0 | Bit Error Rate: 0.21003333333333332
For K=6, At SNR(dB): -7.5 | Bit Error Rate: 0.08703333333333334
For K=6, At SNR(dB): -5.0 | Bit Error Rate: 0.013533333333333333
For K=6, At SNR(dB): -2.5 | Bit Error Rate: 0.0001
For K=6, At SNR(dB): 0.0 | Bit Error Rate: 0.0
For K=7, At SNR(dB): -10.0 | Bit Error Rate: 0.41942857142857143
For K=7, At SNR(dB): -7.5 | Bit Error Rate: 0.30994285714285713
For K=7, At SNR(dB): -5.0 | Bit Error Rate: 0.12808571428571427
For K=7, At SNR(dB): -2.5 | Bit Error Rate: 0.015
For K=7, At SNR(dB): 0.0 | Bit Error Rate: 0.0005142857142857143
For K=8, At SNR(dB): -10.0 | Bit Error Rate: 0.42665
For K=8, At SNR(dB): -7.5 | Bit Error Rate: 0.308025
For K=8, At SNR(dB): -5.0 | Bit Error Rate: 0.13095
For K=8, At SNR(dB): -2.5 | Bit Error Rate: 0.01465
For K=8, At SNR(dB): 0.0 | Bit Error Rate: 0.0003
For K=9, At SNR(dB): -10.0 | Bit Error Rate: 0.41573333333333334
For K=9, At SNR(dB): -7.5 | Bit Error Rate: 0.31122222222222223
For K=9, At SNR(dB): -5.0 | Bit Error Rate: 0.12635555555555555
For K=9, At SNR(dB): -2.5 | Bit Error Rate: 0.0156
For K=9, At SNR(dB): 0.0 | Bit Error Rate: 0.0006222222222222223
For K=10, At SNR(dB): -10.0 | Bit Error Rate: 0.42352
For K=10, At SNR(dB): -7.5 | Bit Error Rate: 0.31212
For K=10, At SNR(dB): -5.0 | Bit Error Rate: 0.13612
For K=10, At SNR(dB): -2.5 | Bit Error Rate: 0.01516
For K=10, At SNR(dB): 0.0 | Bit Error Rate: 0.0001
For K=11, At SNR(dB): -10.0 | Bit Error Rate: 0.43065454545454546
For K=11, At SNR(dB): -7.5 | Bit Error Rate: 0.3102909090909091
For K=11, At SNR(dB): -5.0 | Bit Error Rate: 0.1298
For K=11, At SNR(dB): -2.5 | Bit Error Rate: 0.015181818181818182
For K=11, At SNR(dB): 0.0 | Bit Error Rate: 0.00021818181818181818

Performance Evaluation

The script plots SNR in dB vs BER performance for block-length \(\in \{1,2,3,\dots,11\}\). It can be observed that the Reed Muller codes can provide the reliablilty of

  • \(99.99990 \text{ or BER = } 10^{-4}\) for block-length \(\in \{1,2,3,4,5\}\) and,

  • \(99.99999 \text{ or BER = } 10^{-5}\) for block-length \(\in \{1,2,3,\dots,11\}\) at an SNR value of 0 dB. Furthermore, the larger codeblock-lengths perform poorer compare to the small block-lengths.

Performance Plot

[7]:

fig, ax = plt.subplots()

color_tuple     = ['blue', 'orange', 'green',   'red',    'purple', 'brown',       'pink',  'gray', 'olive', 'cyan', 'black']
markcolor_tuple = ['gold', 'navy',   'crimson', 'yellow', 'line',   'springgreen', 'black', 'aqua', 'royalblue', 'red', 'green']
linestyle_tuple = ['-', '--', '-.', ':', 'solid', 'dashed', 'dashdot', 'dotted']
marker_tuple    = [".", "o", ">", "2", "8", "s", "p", "*", "P", "X", "D"]


# Make the zoom-in plot:
axins  = zoomed_inset_axes(ax, 100, loc="upper right") # zoom = 100
axins2 = zoomed_inset_axes(ax, 100, loc="lower center") # zoom = 100

kIndex = 10
for k in np.flip(K):
    ax.semilogy(SNRdB, BER[kIndex], color=color_tuple[kIndex%len(color_tuple)],
                linestyle=linestyle_tuple[kIndex%len(linestyle_tuple)], lw = 3,
                marker=marker_tuple[kIndex%len(marker_tuple)], markersize = 9, label="K = "+str(k))
    axins.semilogy(SNRdB, BER[kIndex], color=color_tuple[kIndex%len(color_tuple)],
                   linestyle=linestyle_tuple[kIndex%len(linestyle_tuple)],
                   marker=marker_tuple[kIndex%len(marker_tuple)], markersize = 9, label="K = "+str(k))
    axins2.semilogy(SNRdB, BER[kIndex], color=color_tuple[kIndex%len(color_tuple)],
                    linestyle=linestyle_tuple[kIndex%len(linestyle_tuple)],
                    marker=marker_tuple[kIndex%len(marker_tuple)], markersize = 9, label="K = "+str(k))

    kIndex = kIndex -1

ax.legend(loc="lower left")
ax.set_xlabel("Signal to Noise Ratio (dB)", fontsize = 9)
ax.set_ylabel("Bit Error Rate", fontsize = 9)
ax.set_title("[Reed Muller Codes]: SNR(dB) vs BER for various block-length")
#I want to select the x-range for the zoomed region. I have figured it out suitable values
# by trial and error. How can I pass more elegantly the dates as something like
# select y-range for zoomed region
x1 = -4.99
x2 = -5.01

# select y-range for zoomed region
y1 = 0.1295
y2 = 0.13375
axins.set_xlim(x1, x2)
axins.set_ylim(y1, y2)
plt.xticks(visible=False)
plt.yticks(visible=False)
mark_inset(ax, axins, loc1=2, loc2=3, fc="none", ec="0.5")

# select y-range for zoomed region
x1 = -4.99
x2 = -5.01

# select y-range for zoomed region
y1 = 0.0127
y2 = 0.01325

axins2.set_xlim(x1, x2)
axins2.set_ylim(y1, y2)
plt.xticks(visible=False)
plt.yticks(visible=False)
mark_inset(ax, axins2, loc1=1, loc2=2, fc="none", ec="0.5")
plt.draw()


plt.show()
../../../_images/api_Tutorials_Tutorial2_Tutorial2_ReedMullerCodes_15_0.png 
[ ]: