A brief introduction to LDPC code
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.
2. DCT transform
DCT is the equivalent of a Discrete Fourier Transform of about twice the length of the DCT, which is performed on a real even function. Through the study of digital signal processing we know that the spectrum obtained by the Fourier transform of real functions is mostly complex, while the Fourier transform of even functions results in real functions. On this basis, it is one of the characteristics of cosine transformation to make the signal function even and remove the imaginary part of the spectral function. It can convert a set of light intensity data into frequency data in order to know how the intensity changes. If the high-frequency data is modified, it is obviously different from the original data when it is converted back to the original form, but it is not easily recognized by the human eye. During compression, the original image data is divided into 8*8 data element matrix, such as the first matrix of brightness value.
2. Engineering background of DCT generation:
The spectrum line of video signal is in the range of 0-6mhz, and most of the frequency spectrum lines contained in a video image are low-frequency spectrum lines, and only the video signal at the edge of the image, which accounts for a very low proportion of the image area, contains high-frequency spectrum lines. Therefore, in the digital processing of video signal, the number of bits can be allocated according to the spectrum factors: more bits can be allocated to the low spectrum region containing large amount of information, and less bits can be allocated to the high frequency spectrum region containing low amount of information, and the image quality has no perceptible damage, so as to achieve the purpose of bit rate compression. However, all of this requires a low Entropy value for efficient coding. The ability to encode a string of data effectively depends on the probability of each data occurrence. The large difference in the probability of occurrence of each data indicates that the entropy value is low and this string of data can be efficiently coded. On the contrary, the probability difference is small and the entropy value is high, so efficient coding cannot be carried out. The digitalization of the video signal is converted to the video level by A/D converter at A specified sampling frequency. The amplitude of the video signal of each pixel changes periodically with the time of each layer. The sum of the average information content of each pixel is the total average information content, namely the entropy value. Since each video level has almost equal probability, the entropy value of video signal is very high. The entropy value is a parameter that defines the compression rate of the bit rate. The compression rate of the video image depends on the entropy value of the video signal. In most cases, the video signal has a high entropy value. How do I get low entropy? This requires analysis of the characteristics of the video spectrum. In most cases, the amplitude of the video spectrum decreases as the frequency increases. Where the low frequency spectrum acquires zero to the highest level with almost equal probability. In contrast, the high frequency spectrum usually yields low levels and rare high levels. Obviously, the low frequency spectrum has a higher entropy value and the high frequency spectrum has a lower entropy value. Accordingly, the low frequency and high frequency components of video can be processed separately to obtain the compression value of high frequency.
Since Ahmed and Rao gave the definition of discrete cosine transform (DCT) in 1974, discrete cosine transform (DCT) and improved discrete cosine transform (MDCT) have become an important tool and technology widely used in signal processing and image processing, especially for image compression and speech compression codec. It has been the research hotspot of international academic circle and high-tech industry. Many image and video coding standards (e.g. Mpeg-1, MPG-2, and part 2 of MPG-4) require integer 8×8 DCT and IDCT, while MDCT and IMDCT are mainly used in audio signal codec (e.g. Mpeg-1, Mpg-2 and AC-] and other standard audio coding parts). Because this kind of transformation is widely used, it is very important to study the fast algorithm of this kind of transformation. In particular, the research of fast algorithms under specific application conditions is of great help to improve the performance of the whole system. As can be seen from the above reference, bit rate compression is based on transformation coding and entropy coding. The former is used to reduce entropy, while the latter transforms data into efficient encoding that reduces the number of bits. In MPEG standard, DCT is used for transformation coding. Although the transformation process itself does not produce bit-rate compression, the frequency coefficient after transformation is very conducive to bit-rate compression. In fact, the whole process of compression digital video signal is divided into block sampling, DCT, quantization and coding four main processes —– First, the original image is divided into N(horizontal)×N (vertical) sampling blocks in the time domain, and 4×4, 4×8, 8×8, 8×16, 16×16 blocks can be selected according to the need. These sampled pixel blocks represent the gray value of each pixel of the original image frame, which ranges from 139 to 163, and are sequentially fed into the DCT encoder to convert the sample blocks from the time domain to DCT coefficient blocks in the frequency domain. The conversion of the DCT system is carried out separately in each sample block, in which each sample is a digitized value representing the amplitude value of the corresponding pixel of the video signal in a field
3. Realization of DCT:
There are many ways to realize DCT, the most direct is to calculate according to the definition of DCT. In the case of two-dimensional 8xSDCT, 4096 multiplications and 3584 additions are required. The realization of this algorithm requires a huge amount of calculation and has no practical value. In application, it is necessary to find fast and accurate algorithm. The more commonly used method is to make use of the separable characteristics of DCT. Similarly, taking two-dimensional 8xSDCT as an example, eight one-dimensional DCT rows need 64xS multiplication and 56xS addition first, and the next eight one-dimensional DCT rows need 64xS multiplication and 56xS addition. A total of 64x8xZ=1024 multiplications and 56x8xZ=896 additions are required, greatly reducing the amount of computation.
In addition, DCT has many fast algorithms that are publicly available. Fast algorithms reduce computation time mainly by reducing the number of operations, which is very effective for designing fast hardware systems. The fast algorithm of two-dimensional DCT generally adopts the DCT algorithm of column and column separation, that is, the DCT algorithm is converted into two one-dimensional transformations, which are connected by transpose matrix. The most classic and commonly used fast algorithms are THE AAN algorithm proposed by Arai et al in 1988 and the LLM algorithm proposed by Loeffier et al in 1989. However, because the DCT algorithm for row and column separation can reuse the one-dimensional transformation structure, it has more advantages in practical implementation, especially in hardware.
Complete code or write to add QQ1575304183