1 Digital Communications 4/M: Forward Error Correction
1.1 Introduction
This laboratory project will introduce you to some issues that occur in digital communication channels. In particular we will study Forward Error Correction (FEC)as atechnique to overcome the detrimental efects of noise on the communication channel. In your previous laboratories on this course you will have studied modulation formats. Here we will circumvent some of the low-level coding by using the komm Python library https://pypi.org/project/komm/ to provide the appropriate functionality. If you are using your own computer, make sure the Python libraries scipy, numpy, matplotlib and pillow as well as komm version 0.16.2 or later are installed, and your python version is 3.10 or later. It is recommended that you use a suitable IDE for your project, such as Spyder.
Eachprojectwillbescheduledoveratwoweekperiod, withinwhichtherewillbe2scheduled consultation sessions where you will be able to ask teaching staf for guidance. The project should be written up as a short report describing what you’ve done and the results you have taken along with any conclusions that you draw. Include your python code(s) in the appendices. Make sure your name and student ID number is on the report. The report should be uploaded to the Moodle assignment by the stated deadline, either using Moodle’s inbuilt html editor, or as a single PDF file.
1.2 Block Coding: BCH codes
Block codes work on fixed-size blocks (packets) of bits or symbols of predetermined size. Practical block codes can generally be hard-decoded in polynomial time to their block length. Bose-Chaudhuri-Hocquenghem (BCH) codes form. a class of cyclic error-correcting codes that are constructed using polynomials over a finite field (also called Galois field). One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding. This simplifies the design of the decoder for these codes, using small low-power electronic hardware. BCH codes are used in applications such as satellite communications, compact disc players, DVDs, disk drives, solid-state drives and QR codes.
Table 1.2 lists indexes for a sample of some short primitive narrow-sense BCH binary codes which can correct up to t bit errors, and which will be used in this laboratory project. The parameters for the code require a code word length n = 2μ - 1 and number of added parity bits (n - k) ≤ μt . The parameter δ = 2t + 1 is known as the Bose distance (essentially, dmin). The setup to use the BCH code class in python is on providing suitable values for μ and δ:
Table 1.2: indexes for a sample of some short primitive narrow-sense BCH binary codes
import komm
code = komm.BCHCode(mu=3, delta=3)
n,k = code .length, code.dimension
#decoder = komm.BerlekampDecoder(code)
#decoder = komm.ExhaustiveSearchDecoder(code, input_type="hard")
#decoder = komm.SyndromeTableDecoder(code)
1.2.1 (7,4) code alphabet
The (n =7,k =4) BCH code (top line of table 1.2) is equivalent to the Hamming (7,4) code. First, generate the alphabet of valid 7-bit codewords by examining code.codewords(). Confirm that cyclic permutations of valid 7-bit codewords, and bitwise XOR of two valid 7-bit codewords result in other valid 7-bit codewords. The corresponding generator polynomial can be obtained from code.generator_polynomial
1.2.2 Forward error correction using BCH codes
A number of 8 bit depth grayscale images of various sizes have been provided for you to use in this laboratory project. You may also consider the use of the numpy .random library to create random binary streams for testing purposes. As the runtime depends on the size of the data, you should generally use the smallest data set first, although in terms of accuracy it maybe advisable to use the larger datasets where the smallest images result in a small number of bit errors, say < 25, to improve your accuracy in determining the bit-error-rate.
In this laboratory project, use quadrature phase shift keying (QPSK) with unit average power per symbol. Begin with your python code from the previous laboratory for noisy channel simulation. There is a choice of 3 possible decoders in the komm library as shown above. Uncomment the one you wish to use; I recommend the ExhaustiveSearchDecoder as I found it to be generally faster for this set of BCH codes. Having set up the code as shown above, coding and decoding are done with:
coded_word = code.encode(message_word)
...
message_word = decoder(coded_word)
where the message_word is a fixed length k bits and coded_word is a fixed length n bits. You will therefore need a program loop to code (and decode) your entire binary data, and, if necessary, add dummy bits to ensure the input data is a whole number times k bits. You will also need to ensure your encoded data stream corresponds to a whole number of modulation format symbols.
Plot ber (logarithmic axis) vs snr (in dB) over a suitable range of signal-to-noise (e.g. -3 to 9dB) for the BCH codes listed in table 1.2.
snr=10**(snr_db/10.)
awgn = komm.AWGNChannel(snr=snr, signal_power=1.0)
Compare your results with your measurements/theory for the bit error ratio with QPSK without error correction, as you investigated in the previous laboratory project.
1.3 Convolutional Coding
Convolutional codes work on bit or symbol streams of arbitrary length. They are most often soft decoded with the Viterbi algorithm, though other algorithms are sometimes used. Viterbi decoding allows asymptotically optimal decoding efficiency with increasing constraint length of the convolutional code, but at the expense of exponentially increasing complexity.
The komm library provides functions for encoding and decoding convolutional codes. There area number of options. In particular the best convolutional code performance is normally with soft-decision decoding on the real values returned from the demodulator based on the euclidean distance from the symbol, thus providing a confidence level to the Viterbi decoder.
Figure 1.3: A simple rate convolutional encoder.
The constraint length L is the number of shift registers, including the input. Taking the simple rate convolutional encoder shown schematically in figure 1.3 as an example, this has a constraint length of 3. The code generator represents the connections to the modulo 2 adders. In this case the code generator is
where the right expression is the equivalent octal representation.
import komm
code = komm.ConvolutionalCode(feedforward_polynomials=[[0o7, 0o5]])
tblen = 18
encoder = komm.ConvolutionalStreamEncoder(code)
decoder = komm.ViterbiStreamDecoder(code,
traceback_length=tblen, input_type="hard") # change for soft decoding
...
rx_enc = psk.demodulate_hard(rx_data) # for hard decoding
rx_enc = psk.demodulate_soft(rx_data, snr=snr) # for soft decoding
tblen is a positive integer scalar that specifies the traceback depth in the Viterbi algorithm. When used in stream (continuous) form, the decoder has a delay (latency) equal to tblen for a single input stream code. Therefore you should append tblen zeros to the input binary stream, and discard the first tblen bits of the output stream. Typical values for atraceback depth tblen are about five or six times the constraint length L. Remember, you will also need to ensure your encoded data stream corresponds to a whole number of modulation format symbols. With "hard" decoding, rx_enc should contain strict binary data. However with "soft" decoding, rx_enc should contain real values.
Again, take your python code from the previous laboratory for noisy channel simulation and adapt it to use convolutional coding. Plot ber (logarithmic axis) vs snr (in dB) over a suitable range of signal-to-noise for both "hard" and "soft" decoding. Compare your results with your measurements/theory for the bit error ratio with QPSK without error correction from the previous laboratory project.
The Jet Propulsion Laboratory developed constraint length 7 convolutional codes for the Voyager missions. The rate code uses feedforward_polynomials=[[0o155, 0o117]] and the rate code uses feedforward_polynomials=[[0o155, 0o117, 0o127]]. Again, plot ber (logarithmic axis) vs snr (in dB) over a suitable range of signal-to-noise for each of these using "soft" decoding.
1.4 Comparing Codes
Compare the various error-correction techniques (simple parity check and ARQs, BCH block codes, Convolutional Code with hard/soft decision) you examined for the configurations given in the lab descriptor. Which of these provides the best error correcting for the data provided in cases of values for snr =3dB using QPSK? What is the code rate in each optimal case?
1.5 Concatenated Codes - Mandatory for ENG5336/ Optional for ENG4052
Many implementations of FEC can tolerate even lower signal-to-noise ratio by concatenating two diferent FEC code methods. Now adapt your code to use a convolutional code as an inner code, modulating as QPSK and passing the result through an AWGN channel, demodulate and decode using the soft-decision Viterbi method. Now use this as an efective transmission channel and apply a BCH code as the outer code. What is the lowest ber you can obtain with the codes listed here for the case where the signal power is equal to the noise, i.e. snr = 0dB?
1.6 Documentation
Python 3 https://docs.python.org/3/
komm https://komm.readthedocs.io/en/latest/ numpy and scipy https://docs.scipy.org/doc/
matplotlib https://matplotlib.org/contents.html pillow https://pillow.readthedocs.io
spyder https://docs.spyder-ide.org/
Getting the python libraries
If you are using your own computer, make sure the Python libraries scipy, numpy, matplotlib and pillow are installed. These libraries are installed by default with the Anaconda python distribution. It is recommended that you use a suitable IDE for your project, such as Spyder. The komm Python library is available from PyPI repository and, if required, can be installed using pip. From a python-activated command line (such as Anaconda prompt), use the following command to install in your user App config
pip install komm --user