Channel coding, decoding and MATLAB simulation

Article directory

Preface
1. What is channel coding?
2. Basic logic of channel coding-redundant data
- 1. Parity check code
- 2. Repeat code
3. Coding rate
4. Channel coding of 4G and 5G
- 1. Convolutional code
- 2. Viterbi decoding (Viterbi)-probabilistic decoding
- 3. LTE tail-biting convolutional code
- 4. LTE turbo code
5. MATLAB simulation
- 1.ploy2trellis function
- - ①. Function calling method without negative feedback
  - ②. Function calling method with negative feedback
- 2. convenc() function
- 3. vitdec() function
- 4. MATLAB simulation

Foreword

This article studies and records channel coding and decoding in digital communication technology.

Digital communication is to turn all sounds, images, and text into 0, 1 this binary code, this converted data, we can call it 0,1 strong>Original data bit So, can this original bit be directly modulated, converted into electromagnetic waves and sent out? The answer is No, because during the transmission of electromagnetic waves, there will definitely be interference and noise, resulting in errors.

The figure below shows the digital communication system model

Digital communication system model

1. What is channel coding?

First, we will explain channel coding by citing the definition in the book:

The function of channel coding is error control. Digital signals will be affected by noise and other errors during transmission. In order to reduce errors, the channel encoder adds protection components (supervision symbols) to the transmitted information symbols according to certain rules to form the so-called “anti-interference coding”. The channel decoder at the receiving end decodes according to the corresponding inverse rules to discover or correct errors and improve the reliability of the communication system.

Let’s give an example to describe it vividly.
Assume that we convert the two words “Hello” into 0 and 1 codes. For example, 00 and 01 represent your reconciliation respectively. When we send 00, due to interference, the data we send becomes 01. Then the information we sent should originally be “you”, but was recognized as “good” by the receiving end, as shown in the figure below:

In order to anti-interference, we need to add a step to make our data “certainly “The ability to correct errors caused by interference”, this step is called channel coding.

2. Basic logic of channel coding-redundant data

When performing channel coding, redundant data needs to be added to achieve the anti-interference effect. Take the following figure as an example. When transporting vases, in order to prevent the vases from being broken during transportation, we add a foam box, package it and send it via express delivery. The foam boxes and SF express boxes here can be similar to redundant data.

Here we list some commonly used redundant data.

1. Parity check code

Raw data 100101100

Odd parity: 1001011001, the check digit is 1, making the total number of 1 become odd number 5
Even parity: 1001011000, the parity bit is 0, keeping the total number of 1’s as even 4

The added 1bit is the check bit, which is the redundant bit

Assume odd parity is used: 1001011001

During the transmission, 1 bit is wrong: 1011011001, the error can be found
During the transmission, 2 bits were wrong: 0011011001, No error found

The parity check code only has the ability to error detection but not Error correction ability

2. Repeat code

Original information 1 or 0
coding

1 –> 111
0 –> 000

When interference causes a bit error, the error correction effect can be achieved.

When interference causes 2 bit errors, the error correction effect cannot be achieved.

3. Coding rate

R=K/N

K: useful bit data

N: encoded bit data

Taking the previous code as an example, the original data is 100101100, a total of 9 bits, odd parity: 1001011001, a total of 10 bits, encoding rate

0.9

R=9/10=0.9

Repeat code coding rate

R=1/3

1/3 encoding means that 3 encoded bits include 1 valid bit;
1/4 encoding means that 4 encoded bits include 1 valid bit;

The lower the coding rate, the more residual information it contains, the stronger the error correction ability, the stronger the anti-interference ability, and the smaller the effective data transmitted

4. Channel coding for 4G and 5G

The channel coding of 4G includes convolutional codes and turbo codes, and the channel coding of 5G includes polar and ldpc codes.

1. Convolutional code

Convolutional codes generally use（

n,K,N

n, K, N)represents a convolutional encoder.

K

K

K means: input K bits (original bit number that needs to be encoded)
n

n

n means: output

n

n

The number of bits encoded by n bits
Coding rate
R

=

K

/

n

R=K/n

R=K/n
N

N

N: encoding constraint (actually the number of registers)

The convolutional code will

K information symbols are coded as

When there are n code elements, this

n code elements are not only related to the current

K pieces of information are related, and also related to the previous

N-1

N?1 pieces of information related to

Refer to the following example:

2. Viterbi decoding (Viterbi) – Probabilistic decoding

Viterbi decoding is based on the received sequence and finds a line on the grid diagram that is consistent with the received sequence color=”red”>An algorithm for minimizing Hamming distance

Hamming distance: Different binary code elements on the corresponding code points of the two code groups =”red”>digits, which is the distance between two code groups, referred to as code distance
for example:
Code 1:000
Code 2:101
The code distance between these two codes is 2

Let’s continue with an example:

Assume that the sending information bit is 1101
The encoded sequence sent is 111 110 010 100
Receive sequence: 111 010 010 110

Note: The above received sequence has errors due to interference. Now let’s take a look at how Viterbi decoding corrects errors

Each sequence is a path on the grid diagram, with 0 as a solid line and 1 as a dotted line.

Therefore, the final decoding sequence is: 111 110 010 100, achieving the error correction effect.

If it is more complex, there may be two Hamming distances, then we will randomly select it as its decoding, resulting in an error. This is why Viterbi decoding is called probabilistic decoding.

3. LTE tail-biting convolutional code

4. LTE turbo code

5. MATLAB simulation

In the process of convolutional encoding, the functions used are the convenc() function and the vitdec() function, and the poly2trellis() function is also required. .

1.ploy2trellis function

Let’s first look at the poly2trellis() function, which is used to generate the netlist required for convolutional coding. The ploy2trellis function has two calling forms:

trellis=poly2trellis(ConstraintLength,CodeGenerator);
trellis=poly2trellis(ConstraintLength,CodeGenerator,...FeedbackConnection)

The latter should be used in situations with negative feedback

This function is equivalent to defining the structure of the register in the encoder. Generally speaking, when viewing relevant information on convolutional coding, the structure is similar to (2,1,3), but this function only requires two parameters:

The ConstraintLength parameter represents the constraint length
CodeGenerator code generator, specified as K times N matrices of octal numbers, K times polynomial character vectorsN cell array or K multiplied by N string array. CodeGenerator specifies N output connections for each of the encoder's K input bitstreams.


A common understanding of the meaning and function of these two parameters is that the constraint length determines the lookback depth during re-decoding. There are different relationships depending on the encoding rate. This is introduced in the technical documentation:
 
 Determined based on the set n, k, and L values, such as for (2,1,3) Structural type convolutional encoder, where rate = k/n = 1/2, corresponds to the first calculation method, then the backtracking depth is 5*(L-1) code>, the result is 10. Use this value to align or truncate when decoding. This will be seen in the following use process.
Back to the function itself, if you design an encoder of type (2,1,7), you can use:
L = 7;
trellis = poly2trellis(L,[171 133]);

The second parameter is the representation of octal data, and the corresponding binary value is [111_1111, 101_1011]. It can be understood as entering 1bit data and outputting 2bit data, so this is 2-dimensional, and each bit of this 7bit represents the tap of the register. The connection form of the encoder can be drawn based on this.
ploy2treliis As the name suggests: polynomial ploy to grid plot trellis
 The generating polynomial of the convolutional code can be described by a series of polynomials. We convert the polynomials into a trellis structure, which can be used as the input of the linear convolution encoding function convenc in matalb and its decoding (such as the Viterbi decoding function vitdec).
①. Function calling method without negative feedback


(3, 2, 4) convolutional code, 2 in and 3 out, memory length (constraint length) L=max{4, 3} + 1=5
There are two input data corresponding to two rows of registers. The first row has 4 shift registers and the second row has 3, corresponding to the constraint length (4 + 1, 3 + 1) = (5, 4). Then ConstraintLength should be [5,4].
The "contribution" (generated sequence) of the first row of registers to the output of the first bit is (10,011) = 23
The second bit output from the first row of registers' "contribution" (generated sequence) is (11, 101) = 35
The third bit output is "contributed" (generated sequence) by the first row of registers to (00,000) = 0

================================================== ========

The first bit of output is "contributed" (generated sequence) by the second row of registers to (0,000) = 0
The "contribution" (generated sequence) of the second row of registers to the second bit output is (0, 101) = 5
The third bit output from the second row register's "contribution" (generated sequence) is (1,011) = 13

Then CodeGenerator is [23,35,0; 0,5,13]
run
trellis=poly2trellis([5,4],[23,35,0;0,05,13])

The output is as follows:
trellis =

  A struct containing the following fields:

     numInputSymbols: 4
    numOutputSymbols: 8
           numStates: 128
          nextStates: [128×4 double]
             outputs: [128×4 double]


numInputSymbols: 4

Enter the number of states
Indicates that the two inputs have a total of 4 (
             2 
             k
           2^k
       2k,
            k
           k
       k is the number of input channels) and the states are 00, 01, 10, 11 respectively


numOutputSymbols: 8

Number of output states
Indicates a total of 8 outputs (
             2 
             n
           2^n
       2n,
            n
           n
       n is the number of output channels) the states are 000, 001, 010, 011, 100, 101, 110, 111 respectively


numStates: 128

Register status number
The current number of states is 128 (
             2 
             7
           2^7
       27, 7 is the total number of registers) The status is 7 which is a binary number


nextStates: [128x4 double]

next state
nextState is a numStates-by-2k matrix. It represents the next state produced by all combinations of the current state and the current input. A state transition table equivalent to a Markov chain. Rows represent various current states, ranging from all 0s to all 1s.


outputs: [128x4 double]

output
outputs are also numStates-by-2k matrices. He represents the output (octal representation) produced by all combinations of the current state and the current input. The meaning of nextState is the same for rows and columns.



>> trellis.nextStates(1:5,:)

ans =

     0 64 8 72
     0 64 8 72
     1 65 9 73
     1 65 9 73
     2 66 10 74

Above we have listed lines 1-5 of nextStates

The elements of (1, 1) indicate that when the state is all 0s (0000000), the next state when 00 is entered is still all 0s (0000000), that is, the results of all registers are still 0;
The elements of (1, 2) indicate that when in the all-0 state (0000000), the next state when 01 is entered is 64 (1000000)
 …
The elements of (2, 1) represent that in the 1 state (0000001), when the input is 00, the next state is all 0 (0000000)
 …

②. Function calling method with negative feedback
Consider the following convolutional code generation diagram
 

In the same way, the memory length (constraint length) L=4 + 1=5, generate
The "contribution" (generated sequence) of the first bit output by the register is (11, 111) = 37
The "contribution" (generated sequence) of the second bit output from the register is (11,011) = 33
Then CodeGenerator is [37, 33]
The negative feedback polynomial is (11, 111) = 37

run
trellis = poly2trellis(5,[37 33],37)

The output is as follows:
trellis =

  A struct containing the following fields:

     numInputSymbols: 2
    numOutputSymbols: 4
           numStates: 16
          nextStates: [16×2 double]
             outputs: [16×2 double]

The meaning of the variables in the structure is consistent with the first section.
2. convenc() function
Let’s look at the convenc() function again
codedout = convenc(msg,trellis)
codedout = convenc(msg,trellis,puncpat)

To simply use convolutional coding, just use the first calling method, where

The msg parameter is the information that needs to be encoded. This requires input of 0,1 binary data.
The trellis parameter is the result generated by the above function and is transferred here.

When using it, it should be noted that the length of msg data must be an integer multiple of k. At the same time, the above constraint length is used to calculate the backtracking depth, and the backtracking depth is used to add after the information. 0.
3. vitdec() function
Finally, look at the decoding function
decodedout = vitdec(codedin,trellis,tbdepth,opmode,dectype)
decodedout = vitdec(codedin,trellis,tbdepth,opmode,'soft',nsdec)
decodedout = vitdec(codedin,trellis,tbdepth,opmode,dectype,puncpat)

The decoding function has relatively many parameters, mainly the mode needs to be set:

The codedin parameter is the result that needs to be decoded. When the hard decision mode is selected, an integer must be entered. When the soft decision mode is selected, a decimal can be entered.
The trellis parameters are consistent with those of the encoding function.
tbdepthThis parameter parameter is the backtracking depth, which is the result of the previous calculation using the constraint length.
opmode This parameter has three different options, namely cont, term and trunc.
The dectype parameter is used to set whether it is hard decoding hard or soft decoding soft. The input data for hard decoding is all 0 and 1, soft decoding can be said to input decimals.

One thing to note is that for term and trunk modes, the backtracking depth tbdepth must be a positive integer and less than or equal to the input encoding The number of input symbols, to put it bluntly, the length of the information msg before encoding must be greater than or equal to the backtracking depth, otherwise it will not be enough for decoding.
The difference between these three parameters is that there is no delay in term mode, that is, the first data decoded is the first data encoded. The trunc parameter has no delay, and the cont parameter has a delay, which is the backtracking depth. Another difference is the difference between continuous encoding.
4. MATLAB simulation
Use the (2,1,7) structure to perform convolution encoding and decoding. The following is the test code. Select the cont and hard modes.
close all;
clear;
clc;

msg_source = [randi([0 1],1,50),zeros([1,30])]; % This line of code generates a random binary message sequence of length 80. It uses the randi function to randomly generate 50 bits between 0 and 1, and adds 30 zeros at the end.

% These variables define the coding rate of the convolutional code. In this example, n represents the number of output bits and k represents the number of input bits, so the encoding rate is 1/2.
n = 2;
k = 1;
rate = k/n; % rate is 1/2

% These variables define the constraint length and traceback depth of the convolutional code. In this example, the constraint length is 7 and the backtracking depth is 5*(7-1)=30.
L = 7;
tblen = 5*(L-1); % backtracking depth

trellis = poly2trellis(L,[171 133]); % Use the poly2trellis function to generate a Trellis structure of a convolutional code with a constraint length of 7. The generator polynomial is [171 133], which defines the generation process of the convolutional code.
code_data = convenc(msg_source,trellis); % Use the convenc function to encode the message sequence with convolutional code. It inputs msg_source into the convolutional code encoder, uses the previously generated Trellis structure, and obtains the encoded data sequence code_data.
zero=zeros(1,2*tblen); % generates a zero vector of length 2*tblen.
code_data=[code_data(:,1:end),zero]; % Added zero at the end of the encoded data to increase the buffer size for the decoding process
d = vitdec(code_data,trellis,tblen,'cont','hard'); % Use the vitdec function to decode the encoded data with convolutional code. It uses the previously generated Trellis structure and backtracking depth, uses a hard decision method to decode, and obtains the decoded data sequence d.
d = d(tblen*k + 1:end); % Remove the redundant part from the decoded data and retain the length of the original message sequence.
figure(1);
stairs(msg_source(1:end),':*r'); % Draw a ladder diagram of the original message sequence, represented by red asterisks
hold on; % Keeps the current contents of the graphics window so that subsequent drawing commands are displayed in the same window.
stairs(d,': + b'); % Draw a staircase diagram of the decoded message sequence, represented by a blue plus sign.
ylim([-0.1,1.1]);
grid on;
legend('Original information','Restored information');

Simulation results:
 
 You can see that the encoded 80bit data corresponds to the original data one-to-one after decoding.
references:
 1. [Newbies can also understand] Channel coding - convolutional codes and other related content
 2. The plot2trellis function implemented in matlab for convolutional codes
 3. Channel coding: MATLAB uses convolution encoding and decoding functions
My qq: 2442391036, welcome to communicate!