Introduction of LDPC codes
Low density check code (LDPC code) is a kind of forward error correction code. LDPC code was first proposed by Gallager in his doctoral thesis in the 1960s, but due to the technical conditions at that time, there was no feasible decoding algorithm, and it was largely ignored in the following 35 years. Meanwhile, Tanner promoted LDPC code in 1981 and gave the graph representation of LDPC code, which was later called Tanner diagram. In 1993, Berrou et al. discovered Turbo codes. On this basis, MacKay and Neal et al. re-studied LDPC codes around 1995 and proposed a feasible decoding algorithm, thus further discovering the good performance of LDPC codes, which quickly aroused strong response and great attention. After more than ten years of research and development, researchers have made breakthrough progress in all aspects, THE related technology of LDPC code is becoming increasingly mature, and even has begun to have commercial application results, and entered the standard of wireless communication and other related fields.
1.1.1 Characteristics of LDPC code
LDPC code is a block code whose check matrix contains only a few non-zero elements. It is the sparsity of the checksum matrix that ensures that the decoding complexity and the minimum code spacing increase linearly with the code length. The code itself is no different from any other block code except that the check matrix is a sparse matrix. In fact, if the existing block code can be expressed by sparse matrix, then the iterative decoding algorithm used for code can also be successfully transplanted to it. In general, however, it is not practical to find a sparse matrix for an existing block code. The difference is that the code design starts with the construction of a checksum matrix, and then determines a generation matrix for subsequent encoding. The coding of LDPC is the main content to be discussed in this paper.
The decoding method is the biggest difference between LDPC code and classical block code. Classical block codes are usually decoded by ML class decoding algorithm, so they are generally small in code length, and algebraic design to reduce the complexity of decoding. However, LDPC code is long and iteratively decodes through the image representation of its checksum matrix H, so its design takes the characteristics of the checksum matrix as one of the core considerations.
1.1.2 LDPC code construction
The construction of binary LDPC code is actually to find a sparse matrix H as the check matrix of the code. The basic method is to replace a small part of the elements of an all-zero matrix with 1, so that the rows and columns of the matrix after replacement have the required number of non-zero elements. In order to make the constructed code usable, several conditions must be met, namely, no short ring, no low code weight code word, and the minimum distance between codes should be as large as possible.
1.1.3 Tanner graph
LDPC codes are often represented by graphs, and the Tanner diagram represents the check matrix of LDPC codes. The Tanner graph contains two types of vertices :n codeword bit vertices (called bit nodes) corresponding to the columns of the check matrix and M check equation vertices (called check nodes) corresponding to the rows of the check matrix. Each row of the check matrix represents a check equation, and each column represents a codeword bit. Therefore, if a codeword bit is included in the corresponding check equation, a line connects the involved bit nodes to the check nodes, so that the number of lines in Tanner’s diagram is the same as the number of ones in the check matrix. The following figure is a matrix
In the Tanner diagram, the bit nodes are represented by circular nodes, the check nodes are represented by square nodes, and the black line shows a 6 cycle:
A loop in a Tanner graph consists of a group of connected vertices in the graph. The loop starts and ends with one of these vertices and passes through each vertex only once. The length of a loop is defined as the number of wires it contains, and the circumference of the graph, also known as the size of the graph, is defined as the minimum length of the loop in the graph. As shown in the figure above, the dimension of the graph, namely the circumference is 6, as shown by adding black lines.
1.2 LDPC encoding
Method one: H = (A | B), available for gaussian elimination H H = [I | P], code complete, the code word for u = | s [c], including c for supervision, s for bits of information. Because H * u ‘= u * H = 0, can get the I’ s + P * * c = 0, namely I * c ‘= P * s’ (in GF (2)), to ask for c’ = P * s’. If a column exchange occurs during Gaussian elimination, it is only necessary to record the column exchange and do the same for the encoded code word in reverse order. When decoding and u first, and then to the column exchange for u1 = | s [c], the back part of information is wanted.
Method 1 Example:
Method two: Firstly, derive the equation directly encoded according to the check matrix. Will size for m * n check matrix H written form as follows: H = [H1 | H2], including the size of the H1 matrix for m * k, H2 for m * m, the size of the set code complete code word for u = | p [s], s for information, p for supervision. Because H*u’ =u*H’ = 0, we get p*H2’=s*H1′, and we get p=s* H1′ (H2′)-
The above two methods can be directly encoded by the check matrix without generating the matrix, and all the coding relying only on the check matrix is realized by these two formulas. But method two is about whether H2 is full rank (invertible).
1.3 Construction of LDPC code H matrix
Regular LDPC code and irregular LDPC code
If the checksum matrix has the same number of non-zero elements in each row and the same number of non-zero elements in each column, the LDPC code is called the regular code. By contrast, if the checksum matrix has different numbers of non-zero elements in each row or different numbers of non-zero elements in each column, the LDPC code is called the irregular LDPC code.
1.3.1 Irregular LDPC Code
Construction method: the bit rate R=M/N=0.5, the constructed H-matrix column weight is fixed, but the row weight is random. The following is illustrated by an H matrix of size 6*12 and column weight 2. Because the column is fixed to 2, the set of column coordinates is [1,1,2,2,3,3,4,4… 12,12], and the row coordinates can be constructed randomly.
1. Construct a 6*12 matrix onesInCol randomly arranged from 1 to 6 for each column.
2. Select the first two rows of onesInCol, as shown in the figure above.
3. Arrange the selected matrices in order of columns as follows
4. Construct the TMP matrix
5. The matrix TMP is rearranged into C1
6. Full converts sparse matrix to full matrix display. Sparse creates sparse matrix and generates the corresponding element value of M*N order sparse matrix H at coordinates of vector R1 and C1 as the corresponding value of vector 1.
1.3.2 LDPC code of a rule
For the regular LDPC code with bit rate R=0.5, the row weight is related to the column weight, and the row weight is two times of the column weight. Take the 6*12 H matrix as an example, assume that its column weight is 2, the number of 1 in each column is 2, and the total number of 1 is 2*12=24. The H matrix has 6 rows, and if the row weight is the same, the number of 1 in each row is 24/6=4, that is, the row weight is 4. Let’s say its column weight is 3 and its row weight is 6.
Construction method: similar to the construction of row weight, after row weight is fixed, the coordinate set of its position in the matrix is fixed, such as column weight is 2, row weight is 4, and column coordinate set is [1,1,2,2,3,3… , the row coordinate set is [1,1,1,1,2,2,2,2, 2,3,3,3,3, 3… The next thing to consider is how to combine row and column coordinates without repeating them. The idea here is to keep the row coordinate set constant, and the column coordinate set scrambled and rearranged. Take constructing H matrix with size 5*10, column weight 2 and row weight 4 as an example.
1. Construct a 5*10 matrix onesInCol randomly arranged from 1 to 5 for each column.
2. Select the first two rows of onesInCol (the same as the column weight) to form a 1*20 matrix
3. Arrange r in ascending order to obtain
4. Record the position index before ranking
5. Because the column coordinate set is [1,1,2,2,3,3,4,4… 9,9,10,10], rearrange the column coordinate set according to the position index above to get c
6. The set of row coordinates is as follows, corresponding to the column coordinates one by one, to determine the position of 1 in matrix H.
7. Final results
1.3.3 Loop of LDPC code
In the Tanner graph of LDPC code, a loop consisting of some “edges” that start from one vertex and return to the same vertex after passing through different vertices is called a “loop”. The number of edges that go through is called the length of the ring. The ring with the smallest circumference is called the GIRth of the LDPC code (LDPC code).
The rings in Tanner’s diagram inevitably interfere with the result of decoding. Because iterative probabilistic decoding will make information transfer among nodes interactively, if there is a ring, the information starting from a node of the ring will be continuously transmitted along the nodes on the ring and eventually return to the node itself, thus making the information of the node itself accumulate continuously, and thus increasing the probability of failure of the final result of decoding. Obviously, the smaller the ring length, the shorter the path the message needs to take back to itself, and the higher the probability of decoding failure becomes. A Tanner graph requires at least four nodes to form four connected edges to form a ring, that is, the ring length is at least 4, and this kind of short ring has the largest interference to the decoding results of code words. The row and column (RC) constraint that defines the LDPC code is: there is more than one identical position in two rows or columns where there is no element 1. Obviously, LDPC codes that meet the RC constraint are at least 6-loop, and the interference of 4-loop is removed. Since 4-ring detection and avoidance are the easiest and most necessary, most constructors satisfy the RC constraint. Constructing large loop-length codewords requires precise design.
1.4 LDPC decoding
When Gallager describes LDPC code, he puts forward two kinds of hard decision decoding algorithm and soft decision decoding algorithm respectively. Through continuous development, today’s hard decision algorithms have made much progress on the basis of Gallager algorithm, including many weighted bit-flipping decoding algorithms and their improved forms. Both hard and soft judgments have their advantages and disadvantages and can be applied to different applications.
1.4.1 Bit Flipping Algorithm (BF)
The hard decision decoding algorithm is a supplement to the soft decision algorithm of LDPC code proposed by Gallager. The basic assumption of hard decision decoding is that when the check equation is not standing, it means that some bits must be wrong, and the bits that do not satisfy the most check equations have the highest probability of error. At each iteration, the bit with the highest error probability is flipped and the updated code word is re-decoded. The specific steps are as follows:
1. Set the initial iteration number k1 and its upper limit kmax. For the obtained code word y= (y1, y2… Yn) the hard decision sequence Zn of the receiving code word is obtained by expanding the binary hard decision sequence as follows.
2. If k1=kmax, the decoding is complete. Otherwise, calculate the adjoint s=(s0,s1… Sm-1), sm represents the value of the MTH check equation. If the values of the adjoint are all 0, it indicates that the code word is correct and the decoding is successful. Otherwise, there is a bit error. Go to Step 3.
3. For each bit, count the number fn (1<=n<= n) that does not conform to the check equation.
4. Flip the bits corresponding to the maximum FN, and then k=k+1, and return to Step 2.
The theoretical hypothesis of BF algorithm is that if a certain bit does not satisfy the maximum number of check equations, then this bit is the most likely to make mistakes. Therefore, this bit is selected for flipping. BF algorithm abandons the reliability information of each bit and simply makes a hard decision on the code word. The theory is the simplest and the implementation is the easiest, but the performance is also the worst. When the same bit is judged as the most error-prone bit by the iterated rollover function for two consecutive times, BF algorithm will fall into an infinite loop, which greatly reduces the decoding performance.
1.4.2 Confidence Propagation Algorithm (BP)
Belief Propagation decoding algorithm is the application of Message Passing algorithm in LDPC decoding. Message passing algorithm is an algorithm class, which was originally used in the field of artificial intelligence. People applied it to the decoding algorithm of LDPC code, and proposed the confidence propagation algorithm of LDPC code. Confidence propagation algorithm is an iterative decoding algorithm based on Tanner graph. During iteration, reliability information, i.e., “messages”, was passed back and forth between variable nodes and check nodes through the edges of Tanner graph. After several iterations, the value reached a stable value, and then the optimal decision was made based on it.
The basic flow of confidence propagation decoding algorithm is as follows:
Before iteration, the decoder receives the real value sequence y=(y1,y2… .yn), and all variable nodes BI receive the corresponding received value yi.
The first iteration: Each variable node sends a reliability message to all adjacent check nodes, and the reliability message is the value transmitted by the channel. After receiving the reliability message sent by the variable node, each check node processes it, and then returns a new reliability message to the variable node adjacent to it, thus completing the first iteration. At this point, the judgment can be made. If the verification equation is satisfied, the judgment result is directly output without iteration; otherwise, the second iteration can be made.
The second iteration: Each variable node processes the reliability message sent by the check node at the completion of the first iteration, and the new message is sent to the check node after the completion of the processing. Similarly, the check node returns to the variable node after the processing, thus completing the second iteration. If the verification equation is satisfied, the decoding will be finished. Otherwise, the decoding will be repeated for several times until the maximum number of iterations is reached and the decoding fails. During each iteration, neither the information transmitted by the variable node to the check node nor the check node to the variable node should include the information sent by the receiver to the sender in the previous iteration, in order to ensure that the sent information is contradictory to the information already obtained by the receiving node.
%clear all; %clc; tic %rows=128; %cols=256; rows=3000; cols=4000; s=round(rand(1, cols-rows)); % generate H matrix H=genH(rows,cols); % LDPC encoding using H matrix [U,P, rearranged_COLs]= LDPC_encode (s,H); SNR=10; amp=1; tx_waveform=bpsk(u,amp); rx_waveform=awgn(tx_waveform,SNR); scale(1:length(u))=1; % % No fading. The LDPC decoding [uhat vhat] = ldpc_decode (rx_waveform, SNR, amp, scale, H, rearranged_cols);Copy the codeReferences and codes for private message bloggers