CN106569906B - Code writing method and device based on sparse matrix - Google Patents

Abstract

The invention discloses a code writing method and device based on a sparse matrix, which can reduce the complexity of a capacity reaching scheme. The method comprises the following steps: s1, calculating a coset leader v corresponding to the information m to be written_mWherein, in the step (A),m＝(m₁,m₂,…,m_k) The (n, k) block code corresponding to m is C, v_m＝(v₁,v₂,…,v_n) (ii) a S2 sparse matrix-basedA vector b is calculated in which, among other things,i₁,i₂,…,i_sindicating the location of stuck cells, a₁,a₂,…,a_sFixed value, H, representing stuck cells_zTo take the ith from the check matrix H of C₁,i₂,…,i_sA (n-k) x s order sub-matrix composed of columns; s3, writing m 'as a storage value into the storage unit, wherein m' is v_m+bH。

Description

Code writing method and device based on sparse matrix

technical field

The invention relates to the field of encoding technology, in particular to a sparse matrix-based encoding writing method and device.

Background technique

Memory is a memory storage device used to store information and plays an important role in modern information technology. Memory is widely used in various systems, such as solid-state drives, mobile phones, flash memory cards, U disks, tablet computers, etc. It is ubiquitous and inseparable from our daily life.

However, most storage systems (such as flash memory (flash memory), phase change memory (PCM)) have defects because of the production process: the value of some storage cells in the memory is fixed, that is, these storage The storage value of the cell does not change with the change of the written value. This type of error is the stuck cell error we are going to study. The stuck cell error is constant and is a hard error. Stuck cell errors greatly affect storage reliability. A stuck cell error will lead to problems such as low memory yield, low yield, and short life.

For the stuck cell problem, a solution generally adopted by researchers is to make a mapping for the information m to be written, F:m→m′, where m and m' can be written as m=(m ₁ ,m ₂ ,...,m _k ), m'=(m' ₁ ,m' ₂ ,...,m' _n ), so that m' corresponds to stuck cells The value of the position is the same as the fixed value of stuck cells, namely

i ₁ , i ₂ ,..., i _s represent the position of stuck cells, and a ₁ , a ₂ ,..., a _s represent the fixed values of stuck cells.

This mapping process is the process of encoding and writing.

Traditional channel coding can map the information m to be written into m', but this is a one-to-one mapping process, and m' cannot get all the vectors in the n-dimensional vector space on the binary domain.

Mahdavifar and Vardy proposed a capacity-achieving scheme to solve the stuck cell problem, and the capacity-achieving scheme will be introduced next.

Code C is a (n,k) linear code, its generation matrix is G _k×n , and its parity check matrix is H _(nk)×n , meanwhile, matrix H can also be regarded as the generation of dual code C ^⊥ of code C matrix.

All coset leaders of code C ^⊥ are denoted as v ₁ ,v ₂ ,…, Although it does not matter which vector is selected from each coset as the coset capital, if we want to store all the coset leaders, it will take up exponential storage space, so in order to avoid storing all the coset leaders, we will select k coset heads in the form of row vectors as a matrix The elements of are stored in the matrix , so that the linear combination of row vectors in Hc can generate a set containing all coset heads of code ^C⊥ . The linear combination of H ^c and all row vectors of H can form an n-dimensional linear space on the entire binary domain.

The information that needs to be encoded is i ₁ , i ₂ ,..., i _s represent the position of stuck cells, a ₁ , a ₂ ,..., a _s represents the fixed value of stuck cells, z represents the index set of the position of stuck cells, take the i ₁ from the matrix H ,i ₂ ,…,i _s columns constitute the (nk)×s order sub-matrix H _z of matrix H. v _m =(v ₁ ,v ₂ ,...,v _n ) represents the coset head corresponding to the information, that is, v _m =mH ^C . Then, solve the following equation to find the vector

If equation (2.2) has a solution, then the solution is not necessarily unique, so we only need to give one solution of vector b. Finally, we write m′=v _m +bH as the storage value into the storage unit. At this time, the value of the i ₁ , i ₂ ,…,i _s position in m′ is a ₁ , a ₂ ,…,a _s . In this way, the stuck cell problem can be solved.

According to the knowledge of linear algebra, it can be known that a linear equation system has a solution, which is equivalent to the rank of its coefficient matrix and the augmented matrix being equal.

The coefficient matrix of equation (2.2) is an augmented matrix as

because the vector All vectors in the s-dimensional space on the binary field can be taken, so when When the rank is full, equation (2.2) must have a solution.

The main idea of the decoding algorithm in the capacity-achieving scheme is adjoint decoding. Suppose the decoder reads the codeword from memory Decoding is equivalent to calculating the adjoint formula of r with respect to code C ^⊥ , therefore, the decoded message is rG ^T .

There are two main parts in the coding algorithm in the capacity attainment scheme. The first part is to calculate v _m =mH ^C , and the second part is to solve equation (2.2) to obtain a solution of vector b.

The computational complexity of the first part is O(nlogn); in the second part, the Gaussian elimination method is adopted in the capacity attainment scheme, so the computational complexity of the second part is O(n ³ ).

The decoding algorithm involves vector multiplication, which can be done in complexity O(nlogn).

Based on the above analysis, the computational complexity of the entire capacity attainment scheme is O(n ³ ).

The capacity-reaching scheme uses cosets to provide a complete coding scheme. However, the complexity of O(n ³ ) is still too high, which makes this scheme unable to be applied in practice, and cannot really solve the stuck cell problem from a practical point of view.

Contents of the invention

Aiming at the deficiencies and defects of the prior art, the present invention provides a code writing method and device based on a sparse matrix.

On the one hand, the embodiment of the present invention proposes a coding writing method based on a sparse matrix, including:

S1. Calculate the coset leader v _m corresponding to the information m to be written, where, m=(m ₁ ,m ₂ ,...,m _k ), the (n,k) block code corresponding to m is C, v _m =(v ₁ ,v ₂ ,...,v _n );

S2, based on sparse matrix Compute the vector b, where, i ₁ , i ₂ ,…,i _s represent the position of stuck cells, a ₁ , a ₂ ,…, a _s represent the fixed values of stuck cells, H _z is the i ₁ , i ₂ ,...,i s sub-matrix composed of _s columns;

S3. Write m' as a storage value into the storage unit, where m'=v _m +bH.

Preferably, said S2 includes:

S210, from the parity check matrix The check node cn _k with the smallest selectivity in the corresponding Tanner graph;

S211. Assign the value c _k of cn _k to a variable node vn _t connected to cn _k ;

S212. Determine whether the value v _t of the variable node vn _t is 1, if v _t is 1, flip the values of all check nodes connected to the variable node vn _t , that is, change 0 to 1, and 1 to 0 ;

S213. Remove the variable node vn _t and all edges connected thereto, and remove all check nodes whose degree becomes 0 in the Tanner graph;

S214. If it is determined that a check node has been removed, check whether the value of the removed check node is 0, and if the value of all the removed check nodes is 0, and determine that the Tanner graph is known If there is still a check node in the Tanner graph, return to step S210; otherwise, if it is judged that there is no check node in the Tanner graph, then jump to step S215;

S215. Obtain the values of the variable nodes, and determine a vector composed of the values of the variable nodes as a vector b.

Preferably, said S2 includes a deconstruction part and a solution part, wherein,

The deconstruction part includes:

S220. Initialize y=m ₀ , where m ₀ is the parity check matrix The number of check nodes in the corresponding Tanner graph;

S221. If it is determined that there is a variable node with a degree of 1 in the Tanner graph, mark the check node connected to the variable node as y, update y to y-1, and remove the check node and the check node connected to the check node. Check the edges related to the nodes, and remove the variable nodes with degree 0;

S222. Judging whether there is a variable node with a degree of 1 in the Tanner graph, if there is a variable node with a degree of 1 in the Tanner graph, then perform step S221, otherwise, perform step S223;

S223. If it is judged that there is no check node in the Tanner graph, jump to the solution part;

The solving part includes:

S224. For each check node that is marked from small to large, assign a value to the variable node connected to it, so that the sum of the values of the variable nodes connected to it is equal to the value of the check node;

S225. If it is determined that there is a variable node with a value of 1 among the variable nodes connected to it, flip the values of the check nodes connected to the variable node with a value of 1 among the variable nodes connected to it, Change 0 to 1 and 1 to 0, remove the variable node connected to it and the edges related to the variable node connected to it, and remove all check nodes with a degree of 0, and check the moved Whether the value of the check node to be divided is 0, if the value of all check nodes is 0, then perform step S226;

S226. If it is determined that there is a check node with a degree of 1 in the Tanner graph, assign the value of the check node to the variable node connected to it, and if it is determined that the value of the variable node connected to it is 1, the value of all check nodes connected to the variable node connected to it will be reversed, that is, 0 will be changed to 1, and 1 will be changed to 0, and the variable node connected to it and the variable node connected to it will be removed. The edges related to the connected variable nodes, and remove all check nodes with a degree of 0, check whether the value of the removed check node is 0, if the value of all check nodes is 0, continue to check the graph Other check nodes with a degree of 1 are processed until there is no check node with a degree of 1 in the figure, and then go to S227;

S227. Acquire the values of the variable nodes, and determine a vector composed of the values of the variable nodes as a vector b.

On the other hand, an embodiment of the present invention proposes a coding writing device based on a sparse matrix, including:

The first calculation unit is used to calculate the coset leader v _m corresponding to the information m to be written, wherein, m=(m ₁ ,m ₂ ,...,m _k ), the (n,k) block code corresponding to m is C, v _m =(v ₁ ,v ₂ ,...,v _n );

The second computing unit is used for sparse matrix based Compute the vector b, where, i ₁ , i ₂ ,…,i _s represent the position of stuck cells, a ₁ , a ₂ ,…, a _s represent the fixed values of stuck cells, H _z is the i ₁ , i ₂ ,...,i s sub-matrix composed of _s columns;

The writing unit is used for writing m' as a storage value into the storage unit, wherein, m'=v _m +bH.

Preferably, the second computing unit is specifically configured to perform the following steps:

S210, from the parity check matrix The check node cn _k with the smallest selectivity in the corresponding Tanner graph;

S211. Assign the value c _k of cn _k to a variable node vn _t connected to cn _k ;

S212. Determine whether the value v _t of the variable node vn _t is 1, if v _t is 1, flip the values of all check nodes connected to the variable node vn _t , that is, change 0 to 1, and 1 to 0 ;

S213. Remove the variable node vn _t and all edges connected thereto, and remove all check nodes whose degree becomes 0 in the Tanner graph;

S214. If it is determined that a check node has been removed, check whether the value of the removed check node is 0, and if the value of all the removed check nodes is 0, and determine that the Tanner graph is known If there is still a check node in the Tanner graph, return to step S210; otherwise, if it is judged that there is no check node in the Tanner graph, then jump to step S215;

S215. Obtain the values of the variable nodes, and determine a vector composed of the values of the variable nodes as a vector b.

Preferably, the second calculation unit is specifically configured to perform the deconstruction step and the solution step, wherein,

The deconstruction steps include:

S220. Initialize y=m ₀ , where m ₀ is the parity check matrix The number of check nodes in the corresponding Tanner graph;

S221. If it is determined that there is a variable node with a degree of 1 in the Tanner graph, mark the check node connected to the variable node as y, update y to y-1, and remove the check node and the check node connected to the check node. Check the edges related to the nodes, and remove the variable nodes with degree 0;

S222. Judging whether there is a variable node with a degree of 1 in the Tanner graph, if there is a variable node with a degree of 1 in the Tanner graph, then perform step S221, otherwise, perform step S223;

S223. If it is judged that there is no check node in the Tanner graph, jump to the solution part;

The solving steps include:

S224. For each check node that is marked from small to large, assign a value to the variable node connected to it, so that the sum of the values of the variable nodes connected to it is equal to the value of the check node;

S225. If it is determined that there is a variable node with a value of 1 among the variable nodes connected to it, flip the values of the check nodes connected to the variable node with a value of 1 among the variable nodes connected to it, Change 0 to 1 and 1 to 0, remove the variable node connected to it and the edges related to the variable node connected to it, and remove all check nodes with a degree of 0, and check the moved Whether the value of the check node to be divided is 0, if the value of all check nodes is 0, then perform step S226;

S226. If it is determined that there is a check node with a degree of 1 in the Tanner graph, assign the value of the check node to the variable node connected to it, and if it is determined that the value of the variable node connected to it is 1, the value of all check nodes connected to the variable node connected to it will be reversed, that is, 0 will be changed to 1, and 1 will be changed to 0, and the variable node connected to it and the variable node connected to it will be removed. The edges related to the connected variable nodes, and remove all check nodes with a degree of 0, check whether the value of the removed check node is 0, if the value of all check nodes is 0, continue to check the graph Other check nodes with a degree of 1 are processed until there is no check node with a degree of 1 in the figure, and then go to S227;

S227. Acquire the values of the variable nodes, and determine a vector composed of the values of the variable nodes as a vector b.

The present invention has following beneficial effect:

Starting from the second part of the capacity attainment scheme, using the sparsity of the sparse matrix, only focusing on the adjacency relationship between the check node and the variable node, so as to achieve the operation of the node and reduce the computational complexity of the algorithm.

Description of drawings

Fig. 1 is that row weight of the present invention is 2, and column weight is the Tanner diagram of (10,5) linear block code of 4;

Fig. 2 is a schematic flow chart of an embodiment of the encoding writing method based on a sparse matrix in the present invention;

Fig. 3 is a schematic diagram of a specific Tanner diagram;

Fig. 4 is a schematic diagram of another specific Tanner diagram;

Fig. 5 is the figure that S2 one embodiment deconstruction process produces in Fig. 2;

Fig. 6 is a schematic diagram of the performance comparison curve of the C1 code of the check node minimum algorithm and the Gaussian elimination method;

Fig. 7 is a schematic diagram of the performance comparison curve of the C2 code of the check node minimum algorithm and the Gaussian elimination method;

Figure 8 is a schematic diagram of the performance comparison curves of the C2 code based on the three algorithms of the check node minimum algorithm, the graph division algorithm, and the Gaussian elimination method based on the C2 code, the C3 code, and the C4 code;

Figure 9 is a schematic diagram of the performance comparison curves of the C3 code based on the three algorithms of the minimum check node algorithm, the graph division algorithm and the Gaussian elimination method based on the C2 code, the C3 code and the C4 code;

Figure 10 is a schematic diagram of the performance comparison curves of the C4 codes of the three algorithms of the check node minimum algorithm, the graph division algorithm, and the Gaussian elimination method;

FIG. 11 is a schematic structural diagram of an embodiment of a sparse matrix-based code writing device according to the present invention.

Detailed ways

In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly described below in conjunction with the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are the Some, but not all, embodiments are invented. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

A sparse matrix is a matrix in which the number of elements with a value of 0 is much greater than the number of non-zero elements. All the research in this paper is on the binary field, that is, GF(2), so the non-zero elements in the sparse matrix in this paper are 1. This article is based on a sparse matrix, and the check matrix of the Low Density Parity Check Code (LDPC) is sparse, and we will also use the LDPC code in the simulation. The LDPC code is one of the linear block codes, so we will first introduce the linear block codes next.

The output of the source is a sequence consisting of binary values 0 and 1. Such a string of binary data is grouped according to a fixed length k, and each message group is marked as u, and the fixed length k represents k information bits. From the permutations and combinations, we know that there are ^2k different messages in total. Then do a mapping to u and convert it into an n-dimensional vector v on the binary domain, where n>k, so we can get a (n,k) block code, and v is called the code vector or code word of u . It can be seen that these 2 ^k different messages correspond to 2 ^k code words, therefore, the set of these 2 ^k code words constitutes the code word space of the block code, only when the code word v and the message u exist one by one Corresponding relationship, the block code is available, otherwise if multiple messages correspond to the same code word, then the code word cannot be translated back to the exact message. Therefore, the ^2k codewords must be different at this time.

For a (n,k) block code, when it has linear features, the codeword space is closed, and a set of bases can be selected, so that there is no need to store all codewords of length n in the encoder, which can be greatly improved Reduce storage space and coding complexity, so the structure of linear code is an ideal structure.

A (n,k) block code is a (n,k) linear block code if and only if its 2 ^k codewords form a k-dimensional subspace of an n-dimensional vector space over a binary field .

Because a linear code is a vector space, we can describe it in terms of its set of basis. A set of bases of the linear code is formed into a matrix in the form of row vectors, and this matrix can be called the generator matrix of the linear code. If the code C is a k-dimensional subspace of the n-dimensional vector space V _n on the binary domain, let g ₁ , g ₂ ,…,g _k be a group of linearly independent vectors in C, then each The code word v is a linear combination of this group of linearly independent vectors, that is, v=l ₁ g ₁ +l ₂ g ₂ +…+l _k g _k , therefore, the definition matrix G=[g ₁ g ₂ …g _k ] ^T is the generator matrix of the linear code C, satisfying v=uG.

For a linear block code, its code word is generally divided into two parts: message and redundancy check, and this code word also has a systematic structure. Among them, the k bit is the message part, which is composed of the original information bits, and the remaining nk bits are the redundancy check part, which is the parity bit and also the linear sum of the information bits. Therefore, for each linear block code, there is another matrix related to it besides the generator matrix, that is, the parity check matrix of the linear code, represented by matrix H, which satisfies vH ^T =0.

Let x=x ₁ x ₂ ... x _n ∈ V(n,2), y = y ₁ y ₂ ... y _n ∈ V(n,2), V(n,2) represents an n-dimensional vector on a binary field space, then

x y＝x ₁ y ₁ +x ₂ y ₂ +…+x _n y _n (2.1)

Called the inner product of x and y, sometimes also denoted <x, y>.

If C is a binary (n,k) linear code, then it is called as its dual code.

Properties of dual codes:

Let C be a binary (n,k) linear code,

Property 1 If the generator matrix of the linear code C is G, then C ^⊥ ={x∈V(n,2)|xG ^T =0};

The dual code C ^⊥ of property 2C is a binary (n,k) linear code;

Property 3C ^⊥ The generator matrix H is the parity check matrix of the linear code C.

Suppose C is a binary (n, k) linear code, its parity check matrix is H, for any Define the syndrome of x as xH ^T .

The process of syndrome decoding can be described as: suppose the codeword x is received at the receiving end of the channel, then calculate its syndrome xH ^T , and find the coset leader a _i with the same syndrome, then x can be decoded is c=xa _i .

A very sparse check matrix can uniquely describe a corresponding LDPC code, and the check matrix plays a very important role in describing and reflecting the properties of LDPC codes. According to the check matrix, the Tanner diagram of the corresponding LDPC code can be drawn. Like the check matrix, the Tanner diagram is also a basic and important representation of the LDPC code. These two representations play a very important role in the research, proposal and analysis of the algorithm in this paper. Therefore, we will introduce these two representations in turn below.

A binary LDPC code with a length of n can be defined by a sparse parity check matrix H (m×n order matrix) on a binary field. The check matrix H has the following properties:

(1) Each column has γ 1s (the column weight is γ), γ<<m;

(2) Each row has ρ 1s (row weight is ρ), ρ<<n;

(3) The number of 1s (indicated by λ) at the same position between any two columns is not more than 1, that is to say, λ=0 or λ=1.

The code defined by the parity check matrix that satisfies the above properties is the binary regular LDPC code. The dimension of the LDPC code can be determined by the rank of the check matrix. When the rank of the check matrix is full, the dimension of the LDPC code is nm, and its code rate is

If the sparse parity check matrix satisfies the property (3), but its row weight or column weight is not constant, it is a binary irregular LDPC code.

Tanner graph is a graph representation method introduced by Tanner to effectively represent LDPC codes. Although the essence of the Tanner graph is a bipartite graph, we generally call it a Tanner graph when used in LDPC codes.

The Tanner graph consists of two types of nodes and edges connecting different types of nodes. These two types of nodes are check nodes and variable nodes, which are respectively denoted as CNs and VNs. The Tanner graph has m check nodes, corresponding to the m rows of the check matrix; the Tanner graph has n variable nodes, respectively corresponding to the n columns of the check matrix. The drawing rules of the Tanner graph: when the value of the element h _ji in the check matrix H is 1, the jth check node is connected to the i-th variable node. Therefore, the i-th column in the check matrix corresponds to the connection relationship between the i-th variable node and all check nodes, and the j-th row in the check matrix corresponds to the connection relationship between the j-th check node and all variable nodes . According to the drawing rules of the Tanner graph, the number of edges in the graph is equal to the number of 1s in the check matrix.

In the Tanner graph, given two nodes u and v, the sequence starting from u through a series of interacting edges and nodes and returning to v is called a path. If the starting point and the ending point of the path are the same, that is, u and v are the same point, the path is called a cycle.

For ease of understanding, a specific example will be given below:

Example 2.1 For a (10,5) linear block code with a row weight of 2 and a column weight of 4, the corresponding check matrix H is as follows:

Then the Tanner diagram corresponding to the parity check matrix is shown in FIG. 1 .

The storage value of some storage units in the memory is a fixed value, and its state will not change, independent of the written value, that is, its storage value will not change with the change of the written value. Storage units with such properties It is a defective memory cell. For example, if the value of a memory cell is fixed at 0, an error will occur when attempting to write a 1 to this memory cell.

After carefully testing the memory, you can get defect information, such as the location and fixed value of the defect. Therefore, during the research process, researchers generally assume that the position and fixed value of stuck cells are known during the encoding and writing process, but unknown during the decoding and reading process. This research will also be based on this assumption.

Referring to Fig. 2, the present embodiment discloses a coding writing method based on a sparse matrix, including:

S1. Calculate the coset leader v _m corresponding to the information m to be written, where, m=(m ₁ ,m ₂ ,...,m _k ), the (n,k) block code corresponding to m is C, v _m =(v ₁ ,v ₂ ,...,v _n );

S2, based on sparse matrix Compute the vector b, where, i ₁ , i ₂ ,…,i _s represent the position of stuck cells, a ₁ , a ₂ ,…, a _s represent the fixed values of stuck cells, H _z is the i ₁ , i ₂ ,...,i s sub-matrix composed of _s columns;

S3. Write m' as a storage value into the storage unit, where m'=v _m +bH.

The invention adopts the sparse matrix to realize the capacity attainment scheme and improves the capacity attainment scheme. The capacity attainment solution cannot be applied in practice, and cannot really solve the stuck cell problem from a practical point of view. If you want to reduce the complexity of the whole program, you must start with the second part of the program.

The present invention mainly focuses on proposing a new algorithm to solve the second part in the capacity attainment scheme. Using the Gaussian elimination method to solve equation (2.2) has reached the limit of obtaining the correct solution, so there is no room for improvement in designing a new algorithm to improve the probability of obtaining the correct solution. Then, the design of a new algorithm must focus on reducing the computational complexity of the algorithm. At the same time, although the probability that the new algorithm can give a correct solution cannot exceed the Gaussian elimination method, efforts must be made to narrow the gap between the two. gap. Therefore, the goal of designing a new algorithm is to reduce the computational complexity of the algorithm and increase the probability of getting the correct solution, trying to make it close to the Gaussian elimination method.

The present invention will analyze the characteristics of the parity check matrix from the perspective of graphs and design a new algorithm to solve equation (2.2). In order to conform to the consistent narrative habit of coding, we will make an adjustment to the equation and convert it into

make

The following descriptions are based on the fact that H _t is a check matrix, and the vector c can be regarded as a set of check node values.

For the convenience of the following description, I will give a description of some symbols:

Table 3.1 Symbol description

The corresponding Tanner diagram can be drawn from the check matrix H _t , then the problem of giving a solution to equation (2.2) can be transformed into a given set of check node values, and a set of variable nodes that meet the conditions can be obtained The value of , the condition to be met is: the sum of the values of the variable nodes connected to any check node is equal to the value of this check node, that is, for any check node cn _i , 1≤i≤m ₀ , i∈N, set The degree of cn _i is k and the variable nodes connected to cn _i are So There may be multiple sets of v ₁ , v ₂ ,…, The value of satisfies the condition, but we only need to give a set.

Because ordinary matrices have the same properties, sparse matrices must also have them, so for the convenience of explanation, the matrices used in the examples given in this article are not very large, and the matrices do not necessarily satisfy the sparse properties. A specific example is given below.

Example 3.1 Find a set of solutions for b.

From the parity check matrix H _t , we can draw the corresponding Tanner graph (as shown in FIG. 3 ).

Find a set of solutions of b, that is, find a set of values of v ₁ , v ₂ , and v ₃ that satisfy v ₁ +v ₂ +v ₃ =c ₁ , v ₃ =c ₂ .

The graph-based algorithm will not perform a linear combination of each specific equation, and it will not change the adjacency relationship between the original check node and the variable node. Solving equation (2.2) from the perspective of the graph essentially gives a rule that specifies the order in which check nodes are processed. To process a check node is to give the value of the variable node connected to it.

If there is a check node with a degree of 1 in the graph, the check node must be processed first, because there is only one variable node connected to it, and the value of the variable node connected to it must be equal to the value of the check node To satisfy this check node. The same is true in the equation system. Therefore, no matter how the order of processing check nodes is given by the design rules, check nodes with a degree of 1 must be given priority.

In this section, based on the characteristics of the degree of check nodes, a minimum algorithm for check nodes is proposed.

Table 3.2 Check node minimum algorithm rules

It can be seen from the description of the above rules that in the check node minimum algorithm, we determine the priority of processing check nodes according to the degree of the check nodes. The smaller the degree, the higher the priority. In the check node minimum algorithm, we do not distinguish between check nodes with the same degree, and similarly, when it comes to a specific check node, we do not distinguish the variable nodes connected to it.

The description of the minimum algorithm for check nodes given above is to directly operate on the graph. In fact, we don’t need to use the structure of the graph when we program. We only need to use the adjacency relationship between variable nodes and check nodes. Will not do node and edge removal, but will mark. Because only one variable node will be processed in each round of operation, that is, the value of a variable node is given; after the value of a variable node is given, the values of the check nodes connected to this variable node and their degrees will be updated, and The number of check nodes connected to variable nodes is the degree of variable nodes, which we denote as ω _v . So, each round does 2ω _v additions. We set the maximum degree of variable nodes in the original graph as d _v , because there are n ₀ variable nodes in total, so the minimum algorithm for check nodes will perform at most 2n ₀ d _v addition operations without multiplication operations. There is no multiplication operation in the whole algorithm, and d _v << m ₀ , so asymptotically, the computational complexity of the minimum algorithm for check nodes is O(n).

The computational complexity of the check node minimum algorithm is much lower than the Gaussian elimination method, but it will inevitably lose the probability of giving a set of correct solutions. In this section, I will give the effect of the check node minimum algorithm analyze.

The check node minimum algorithm rules given above can have corresponding operations on the matrix. The corresponding matrix changes to:

(1) The variable node is assigned a value, the value of the check node is flipped, and there is no change to the matrix;

(2) Remove the variable node vn _t and all edges connected to it, and delete the corresponding column of the removed variable node in the matrix;

(3) Remove all check nodes whose degrees become 0 in the graph, that is, delete the corresponding rows in the matrix.

Theorem 3.1 When there is no cycle in the graph, the check node minimum algorithm is equivalent to the Gaussian elimination method. The equivalent effect means that if the Gaussian elimination method can give a set of correct solutions, then the check node minimum algorithm can also give a set of correct solutions. Of course, the solutions given by the two algorithms are not necessarily equal.

Proof: 1. Process check nodes with degree 1 first (if there is no check node with degree 1 in the graph at the beginning, the processing process is the same as a graph with check nodes with degree 1 at the beginning , after solving the problem that there is no check node with degree 1 in the graph). The effect of this step is equivalent to solving a system of equations, and the minimum algorithm of check nodes that can be solved by a system of equations can also be solved.

2. There is no check node with degree 1 in the graph. When the degrees of the check nodes in the graph are all greater than 2, after solving a check node, there will be no check nodes with a degree of 1, let alone k (k≥2) check nodes with a degree of 1 and The situation that the same variable node is connected (for the convenience of analysis, k=2 is taken below), so we don’t need to consider the situation that the degree of the verification nodes in the figure is greater than 2.

a) (1 case of degree 2→2 cases of degree 1) After processing a check node with degree 2, two check nodes with degree 1 are connected to the same variable node, then in the processing The matrix of the three check nodes before the check node with degree 2 must be

The zero vector in the middle has been omitted, and the rows and columns can be exchanged. Obviously this graph has a ring, and under our problem setting, this situation will not occur.

b) (1 degree is 2 → 1 degree is 1 → 2 degrees are 1) After processing a check node with a degree of 2, two check nodes with a degree of 1 appear. The node is not connected to the same variable node, and then one of the check nodes with degree 1 is arbitrarily processed, and two check nodes with degree 1 are connected to the same variable node, then the check node with degree 2 is processed. The matrix of these four check nodes before the check node must be

or

The zero vector in the middle has been omitted, and the rows and columns can be exchanged. Obviously this graph has a ring, and under our problem setting, this situation will not occur.

The rest of the cases are nothing more than adding some processes in the chain of cases a and b, but the essence remains the same. Therefore, when there is no check node with a degree of 1 in the graph, the minimum check node algorithm can definitely give a set of correct solutions.

In summary, when the Tanner graph generated by the check matrix is acyclic, the check node minimum algorithm has the same effect as the Gaussian elimination method.

Although the check node minimum algorithm is equivalent to the Gaussian elimination method when the Tanner graph has no loops, but when the Tanner graph has loops, the check node minimum algorithm is powerless. Because for check nodes with the same degree, the check node minimum algorithm does not distinguish, that is to say, for check nodes with the same degree, who should be processed first, the check node minimum algorithm is not specified, but in fact , the order of processing check nodes with the same degree has a great influence on whether a set of correct solutions can be obtained. Below we give an example to illustrate.

Example 3.2 The Tanner diagram of the matrix is shown in Figure 4.

From the Tanner diagram, we can find that (cn ₁ ,vn ₁ ,cn ₂ ,vn ₂ ) and (cn ₃ ,vn ₄ ,cn ₄ ,vn ₅ ) form rings respectively.

The degrees of cn ₁ and cn ₄ are both 2, which is the smallest check node in the graph. At this time, in the check node minimum algorithm, there is no difference in processing cn ₁ or cn ₄ first, but the order of processing them It has a decisive influence on whether the correct solution can be obtained.

If cn ₁ is processed first, according to the check node minimum algorithm, v ₁ =1, v ₂ =0 can be given;

Then the degree of cn ₂ becomes 1, and v ₃ =1 can be given;

The rest of cn ₃ and cn ₄ are the same, however, if v ₄ and v ₅ must satisfy c ₃ , then v ₄ ⁺ v ₅ =1;

And if v ₄ and v ₅ must satisfy c ₄ , then v ₄ +v ₅ =0, which is obviously contradictory, so a set of correct solutions cannot be obtained. Of course, if the values of v ₁ and v ₂ are reversed at the beginning, a correct set of solutions can be obtained, but the minimum check node algorithm cannot guarantee that v ₁ and v ₂ are assigned values according to this idea, so cn ₁ is processed first A correct set of solutions may not necessarily be obtained.

If cn ₄ is processed first, it is given that v ₄ =0, v ₅ =0;

Then the degree of cn ₃ becomes 1, then given v ₂ =1;

The degree of cn ₁ becomes 1, given v ₁ =0;

Finally v ₃ =1 is given.

Even if v ₄ =1 and v ₅ =1 are given initially, we can still get a set of correct solutions in the end, that is, we can definitely get a set of correct solutions by processing cn ₄ first.

The structure of the ring in this example is still very simple, but the ring in the actual application is far more complicated than this, so it is very important to solve the problem of the ring.

The graph division algorithm is based on the characteristics of the degree of variable nodes, and sets certain rules to deconstruct the graph bit by bit. During the process of deconstruction, some rings are opened.

The graph division algorithm is mainly divided into two parts. The first part is to deconstruct the graph and give a set of order for processing check nodes; the second part is to solve the problem according to the order of processing check nodes given in the first part and combine the rest of the rules. The value of the variable node.

Table 3.3 graph division algorithm rules

The following will give a specific example to explain the graph division algorithm. In order to easily reflect the partial effectiveness of the graph division algorithm for the ring and the difference from the minimum algorithm for the check node, the following example will continue to use Example 3.2.

Example 3.3

Deconstruction process:

(a) in Figure 5 is the Tanner graph of the original matrix. We can set the degree of vn ₃ to 1, so mark the check node cn ₂ connected to vn ₃ as 4, and then do some shifts on the nodes and edges in the graph. In addition, the figure (b) in Figure 5 has been obtained by the work, and the ring formed by (cn ₁ , vn ₁ , cn ₂ , vn ₂ ) has been opened at this time;

From the (b) figure in Figure 5, the cn ₁ is marked as 3, and then the figure becomes the (c) figure in Figure 5;

From the figure (c) in Figure 5, the cn ₃ is marked as 2, and then the figure becomes the figure (d) in Figure 5;

According to (d) in Fig. 5, mark cn ₄ as 1.

Therefore, we can obtain a group of check nodes arranged in a new order, the new order is: (cn ₄ , cn ₃ , cn ₁ , cn ₂ ).

Solving process:

Process cn ₄ first, give v ₄ = 0, v ₅ = 0, and complete the removal of related nodes and degrees (every time a check node is processed, the removal will be done, and will not be described in detail later);

The degree of cn ₃ becomes 1, then cn ₃ is processed first, and v ₂ =1 is given;

The degree of cn ₁ becomes 1, then cn ₁ is processed, giving v ₁ =0;

This finally gives v ₃ =1.

Similar to the minimum algorithm of the check node, although the description of the given graph division algorithm directly operates on the graph, in fact, we don’t need to use the structure of the graph when we program and implement, just use variable nodes and check nodes The adjacency relationship of the node and edge will not be removed, but it will be marked.

Because the graph division algorithm is mainly divided into two parts: deconstruction and solution, the analysis of the computational complexity of the graph division algorithm will also be divided into two parts.

If the graph cannot be completely deconstructed, the algorithm will not proceed to the solving part at all. Therefore, in order to calculate the maximum number of addition operations that the graph division algorithm will perform, we assume that the graph can be completely deconstructed and the solving process can proceed smoothly.

Deconstruction process:

Each round will remove a check node and its related edges, which means that the degree of the variable nodes connected to this check node will be reduced by 1. If the degree of this check node is ω _c , then each round Will perform _ωc addition operations. However, there are m ₀ check nodes in the original graph, and the maximum degree of the check nodes in the original graph is d _c . Therefore, in the process of deconstruction, there will be at most m ₀ d _c addition operations and no multiplication operations.

Solving process:

The place where the addition operation will occur is that when the value of a variable node is given, the value of the check node connected to it will be updated, and the degree of the check node connected to it will be reduced by 1 accordingly. Set this variable node The degree of is ω _v , so, every time a value of a variable node is given, 2ω _v addition operations will be performed. We set the maximum degree of variable nodes in the initial graph as d _v , because there are n ₀ variable nodes in total, so the solution part will perform at most 2n ₀ d _v addition operations without multiplication operations.

To sum up, the graph division algorithm will perform at most m ₀ d _c +2n ₀ d _v addition operations. And because d _c << n ₀ , d _v << m ₀ , so asymptotically, the computational complexity of the graph division algorithm is O(n).

Compared with the minimum algorithm of the check node, the graph division algorithm has an increase in the total number of addition operations, but the total number of calculations is still on the order of O(n). From the perspective of the order of magnitude of computational complexity, there is no difference between the two algorithms .

In this section, for the convenience of algorithm analysis and description, I will give another way of expressing graph deconstruction.

Another description of the algorithm of the deconstruction part in Table 3.4graph division algorithm

Lemma 3.1 The value of vn _k must be given when cn _k is processed.

Proof: when deg(vn _k )=1, obviously established;

When deg(vn _k )≥1, it is assumed that the value of vn _k is the first given when cn _k is not processed, that is, the value of vn _k has already been given when cn _k has not been processed.

From the method of deconstructing the graph, it can be concluded that except for cn _k , the number of rows corresponding to the check nodes connected to vn _k is greater than k, that is, if the check nodes connected to vn _k are processed, they must be in the process of solving If it is processed in the third step of , it is advisable to set the processed check node as cn _k+t , then when it is processed, deg(c _k+t )=1, when deg(c _k+t )=1 , obviously vn _k has not been given a value, then vn _k+t must have been given a value at this time, that is, the value of vn _k+t is not given when cn _k+t is processed, which is different from the assumption "The value of vn _k is the first given when cn _k is not processed" contradicts, so, the assumption does not hold.

And because k in the assumption can take any value among 1, 2,..., m, the value of vn _k must be given when cn _k is processed.

Certificate completed.

Theorem 3.2 If the graph can be completely deconstructed, that is, a complete set of check node sequences can be given, then the graphdivision algorithm must be able to give a set of correct solutions.

Proof: According to Lemma 3.1, when any check node cn _k is processed, there is at least one variable node vn _k that has not been given a value, that is, by giving the rank of vn _k , we must be able to give a set of The values of _k connected variable nodes satisfy cn _k . Therefore, if the graph can be completely deconstructed, that is, a complete set of check node sequences can be given, then the graphdivision algorithm must be able to give a set of correct solutions.

Certificate completed.

After proposing a new algorithm, it needs to realize its performance through simulation. The simulation experiment can provide us with detailed data on the performance of the new algorithm. Through the analysis and comparison of the data, we can find out the potential problems of the algorithm and the areas that need to be improved.

In this chapter, we will first introduce the design of the simulation experiment, and then conduct Monte Carlo simulations on the binary defect channel (Binary Defective Channel, BDC) for the check node minimum algorithm, graphdivision algorithm and Gaussian elimination method, and for the three The simulation results of the algorithms are used to compare and analyze the three algorithms.

Design of BDC Channel Model and Monte Carlo Simulation

Heegard and ElGamal considered a probabilistic channel model, which Mahdavifar and Vardy called in their paper a binary defect channel with defect probability q, denoted as BDC(q).

BDC channel model

Let q be the defect probability, that is, the storage unit with the probability of 1-q may become a perfect storage unit, and the one with the probability of q may become a stuck cell, where the fixed value of the stuck cell is may be 0, there are may be 1; let Ψ={0,1} be a binary character set, λ is an element not in the set Ψ, z represents the character set Any element in , and has the following probability distribution:

Define BDC channel for:

In actual operation, we use the random number generator 'MersenneTwister' designed by M.Matsumoto&T.Nishimura to generate a string of binary random numbers of length n, where the number at each position has the possibility of q being 0, and 1- The probability of q is 1. We take the position of value 1 in this string of binary random numbers as the position of the stuck cell.

For the performance of the algorithm, this paper uses the probability of not getting the correct solution, that is, the error rate, to measure it. The error rate of the algorithm is defined as: under a certain defect probability q, the ratio of the number of times that the algorithm cannot get a set of correct solutions to the total number of times. To calculate the ratio, the termination condition of the designed simulation can be either the total number of times or the number of error frames. The termination condition we choose is to reach a certain number of error frames, because before the simulation, we do not know how much its error rate will reach under a certain defect probability, plus the randomness of the error position, once the simulation total The number of times, it is very likely that the number of error frames will be small, and the error rate will fluctuate greatly and be inaccurate.

The value of the check node in equation (3.2) can be taken over the n-dimensional vector on the binary domain, so during simulation, we can generate a set of non-zero check node values according to a certain rule.

Algorithm performance simulation

In this section, we will choose four binary LDPC codes for simulation. The first type of code is an irregular LDPC code with a code word length of 548 and an information bit length of 274. The maximum row weight of this code is 8, and the maximum column weight is 11, which is denoted as C1 code; the second type of code is the code word length 800, the regular LDPC code with the information bit length of 400, the row weight of the code is 6, the column weight is 3, which is denoted as C2 code; the third code is the irregular code with the code word length of 1000 and the information bit length of 500 LDPC code, the maximum row weight of this code is 7, and the maximum column weight is 3, which is recorded as C3 code; the fourth code is a regular LDPC code with a code word length of 3780 and an information bit length of 252, and the row weight of this code is 60, column weight is 4, recorded as C4 code. The first three codes are code rate code, the fourth is a high code rate code rate of 0.933 code.

Simulation results and analysis of checkpoint minimum algorithm

The performance comparison curves of the check node minimum algorithm and the Gaussian elimination method based on the C1 code and the C2 code are shown in Figure 6 and Figure 7, and Figure 6 is the performance comparison curve of the check node minimum algorithm and the Gaussian elimination method of the C1 code. 7 is the performance comparison curve of the C2 code of the check node minimum algorithm and the Gaussian elimination method. From the two figures, we can see that although different codes have the same defect probability, the error rates of the two algorithms are different, but the overall trend is the same. In fact, we not only simulated the two codes in the above figure, but also simulated the other two codes. The trend is consistent with these two figures, and the performance curves of the other two codes will also be shown in the next section, so here will no longer be displayed.

It can be seen from Figure 7 that when the C2 code is used, when the defect probability is around 0.44, the error rate of the Gaussian elimination method has dropped to the order of 10 ^-3 , while the error rate of the check node minimum algorithm has to be reduced to 10 ^{- 3} , the defect probability is less than 0.27, and the performance loss is greater than 17%.

It can also be seen from Figure 6 that compared with the Gaussian elimination method, the performance loss of the minimum algorithm of the check node is nearly 17%.

Although using C1 code, the performance loss of the minimum algorithm for check nodes is reduced to a certain extent compared with C2 code, but overall the difference is not big. It can be seen that although there are certain differences in performance between codes, the trend is the same, and the same The difference between the codes of the code rate is not large.

Because the codes of the above two pictures are The code rate, so the performance limit of the algorithm is 0.5, that is, when the defect probability is greater than 0.5, the Gaussian elimination method and the check node minimum algorithm will fail at the same time.

Simulation results and analysis of graph division algorithm

The performance comparison curves of the check node minimum algorithm, graph division algorithm and Gaussian elimination method based on C2 code, C3 code and C4 code are shown in Figures 8, 9 and 10, and Figure 8 is the performance comparison curve of the C2 code of the three algorithms , Fig. 9 is the performance comparison curve of the C3 code of the three algorithms, and Fig. 10 is the performance comparison curve of the C4 code of the three algorithms.

Figure 8 and Figure 9 still use two code rate, so the performance limit of the algorithm is 0.5.

Figure 10 uses a code with a high code rate of 0.933, so the performance limit of the algorithm is 0.066.

From the above three performance comparison diagrams, it can be seen that although the C2 code, C3 code and C4 code have many differences in code rate, whether they are regular LDPC codes, code length, and row and column weights, the algorithms of the three graphs are different. The trend of the performance curve is consistent.

It can be seen from Figure 9 that when the C3 code is used, when the defect probability is around 0.44, the error rate of the Gaussian elimination method drops to the order of 10 ^-3 , and when the error rate of the graph division algorithm drops to the order of 10 ^-3 , the defect The probability is around 0.37, so compared to the Gaussian elimination method, the performance loss of the graph division algorithm is about 7%.

It can also be seen from Figure 8 that the same The performance loss of the code rate C2 code is also about 7%.

It is not difficult to see from Figure 10 that, as a high code rate C4 code, the performance loss of the graph division algorithm is about 1%.

In summary, it can be found that the performance of the graph division algorithm has been greatly improved compared with the minimum algorithm of the check node, and compared with the Gaussian elimination method, although there is a performance loss, the loss is acceptable, especially when using a high bit rate When coding, and the computational complexity of the graph division algorithm is two orders of magnitude lower than that of the Gaussian elimination method.

Referring to Fig. 11, this embodiment discloses a coding writing device based on a sparse matrix, including:

The first calculation unit 1 is used to calculate the coset leader v _m corresponding to the information m to be written, wherein, m=(m ₁ ,m ₂ ,...,m _k ), the (n,k) block code corresponding to m is C, v _m =(v ₁ ,v ₂ ,...,v _n );

The second calculation unit 2 is used for sparse matrix based Compute the vector b, where, i ₁ , i ₂ ,…,i _s represent the position of stuck cells, a ₁ , a ₂ ,…, a _s represent the fixed values of stuck cells, H _z is the i ₁ , i ₂ ,...,i s sub-matrix composed of _s columns;

The writing unit 3 is used for writing m' as a storage value into the storage unit, wherein, m'=v _m +bH.

Although the embodiments of the present invention have been described in conjunction with the accompanying drawings, those skilled in the art can make various modifications and variations without departing from the spirit and scope of the present invention. within the bounds of the requirements.

Claims (4)

1. A sparse matrix-based code writing method is characterized by comprising the following steps:

s1, calculating a coset leader v corresponding to the information m to be written_mWherein, in the step (A),m＝(m₁,m₂,…,m_k) The (n, k) block code corresponding to m is C, v_m＝(v₁,v₂,…,v_n)；

S2 sparse matrix-basedA vector b is calculated in which, among other things,i₁,i₂,…,i_sindicating the location of stuck cells, a₁,a₂,…,a_sFixed value, H, representing stuck cells_zTo take the ith from the check matrix H of C₁,i₂,…,i_sA (n-k) x s order sub-matrix composed of columns;

s3, writing m 'as a storage value into the storage unit, wherein m' is v_m+bH；

The S2, including:

s210, secondary check matrixCheck node cn with minimum selectivity in corresponding Tanner graph_k；

S211, giving cn_kConnected variable node vn_tEndowing cn with specific amino group_kValue c of_k；

S212, judging variable node vn_tValue v of_tIf v is 1, if v_t1, all and variable nodes vn_tThe values of the connected check nodes are all turned, namely 0 is changed into 1, and 1 is changed into 0;

s213, removing variable node vn_tAnd all edges connected with the check nodes, and removing all check nodes with the degree of 0 in the Tanner graph;

s214, if the check node is judged to be removed, checking whether the value of the removed check node is 0, if all the values of the removed check node are 0, and judging that the check node exists in the Tanner graph, returning to the step S210, otherwise, if the check node does not exist in the Tanner graph, jumping to the step S215;

s215, obtaining the values of the variable nodes, and determining a vector consisting of the values of the variable nodes as a vector b.

2. The method according to claim 1, wherein the S2 includes a deconstruction part and a solution part, wherein,

the deconstruction portion comprises:

s220, initializing y ═ m₀Wherein m is₀Is a check matrixThe number of check nodes in the corresponding Tanner graph;

s221, if the variable node with the degree of 1 in the Tanner graph is judged and obtained, marking a check node connected with the variable node as y, updating y to be y-1, removing the check node and an edge related to the check node, and removing the variable node with the degree of 0;

s222, judging whether a variable node with the degree of 1 exists in the Tanner graph or not, if so, executing a step S221, otherwise, executing a step S223;

s223, if judging that the Tanner graph does not have check nodes, skipping to a solving part;

the solving section includes:

s224, for each check node from small to large according to the mark, assigning a value to the variable node connected with the check node, so that the sum of the values of the variable node connected with the check node is equal to the value of the check node;

s225, if the variable nodes with the value of 1 in the variable nodes connected with the variable nodes are judged and known, the values of the check nodes connected with the variable nodes with the value of 1 in the variable nodes connected with the variable nodes are all inverted, namely 0 is changed into 1, 1 is changed into 0, the variable nodes connected with the variable nodes and the edges related to the variable nodes connected with the variable nodes are removed, all check nodes with the degree of 0 are removed, whether the values of the removed check nodes are 0 is checked, and if the values of all the check nodes are 0, the step S226 is executed;

s226, if it is determined that there is a check node with a degree of 1 in the Tanner graph, assigning the value of the check node to the variable node connected thereto, if it is determined that the value of the variable node connected thereto is 1, flipping the values of all check nodes connected to the variable node connected thereto, that is, 0 is changed to 1, and 1 is changed to 0, removing the variable node connected thereto and the edge related to the variable node connected thereto, removing all check nodes with a degree of 0, checking whether the value of the removed check node is 0, if all the check nodes are 0, continuing to process the other check nodes with a degree of 1 in the graph until there is no check node with a degree of 1 in the graph, and turning to S227;

and S227, obtaining the values of the variable nodes, and determining a vector consisting of the values of the variable nodes as a vector b.

3. A sparse matrix-based code writing apparatus, comprising:

a first calculation unit for calculating a coset leader v corresponding to the information m to be written_mWherein, in the step (A),m＝(m₁,m₂,…,m_k) The (n, k) block code corresponding to m is C, v_m＝(v₁,v₂,…,v_n)；

A second calculation unit for calculating a second matrix based on the sparse matrixA vector b is calculated in which, among other things,i₁,i₂,…,i_sthe location of the stuck cells is indicated,a₁,a₂,…,a_sfixed value, H, representing stuck cells_zTo take the ith from the check matrix H of C₁,i₂,…,i_sA (n-k) x s order sub-matrix composed of columns;

a write unit for writing m 'as a storage value into the storage unit, wherein m' ═ v_m+bH；

The second computing unit is specifically configured to perform the following steps:

s210, secondary check matrixCheck node cn with minimum selectivity in corresponding Tanner graph_k；

S211, giving cn_kConnected variable node vn_tEndowing cn with specific amino group_kValue c of_k；

S212, judging variable node vn_tValue v of_tIf v is 1, if v_t1, all and variable nodes vn_tThe values of the connected check nodes are all turned, namely 0 is changed into 1, and 1 is changed into 0;

s213, removing variable node vn_tAnd all edges connected with the check nodes, and removing all check nodes with the degree of 0 in the Tanner graph;

s214, if the check node is judged to be removed, checking whether the value of the removed check node is 0, if all the values of the removed check node are 0, and judging that the check node exists in the Tanner graph, returning to the step S210, otherwise, if the check node does not exist in the Tanner graph, jumping to the step S215;

s215, obtaining the values of the variable nodes, and determining a vector consisting of the values of the variable nodes as a vector b.

4. The apparatus according to claim 3, characterized in that the second calculation unit is specifically adapted to perform a deconstruction step and a solution step, wherein,

the deconstruction step comprises:

s220, initialChanging y to m₀Wherein m is₀Is a check matrixThe number of check nodes in the corresponding Tanner graph;

s221, if the variable node with the degree of 1 in the Tanner graph is judged and obtained, marking a check node connected with the variable node as y, updating y to be y-1, removing the check node and an edge related to the check node, and removing the variable node with the degree of 0;

s222, judging whether a variable node with the degree of 1 exists in the Tanner graph or not, if so, executing a step S221, otherwise, executing a step S223;

s223, if judging that the Tanner graph does not have check nodes, skipping to a solving part;

the solving step includes:

s224, for each check node from small to large according to the mark, assigning a value to the variable node connected with the check node, so that the sum of the values of the variable node connected with the check node is equal to the value of the check node;

s225, if the variable nodes with the value of 1 in the variable nodes connected with the variable nodes are judged and known, the values of the check nodes connected with the variable nodes with the value of 1 in the variable nodes connected with the variable nodes are all inverted, namely 0 is changed into 1, 1 is changed into 0, the variable nodes connected with the variable nodes and the edges related to the variable nodes connected with the variable nodes are removed, all check nodes with the degree of 0 are removed, whether the values of the removed check nodes are 0 is checked, and if the values of all the check nodes are 0, the step S226 is executed;

s226, if it is determined that there is a check node with a degree of 1 in the Tanner graph, assigning the value of the check node to the variable node connected thereto, if it is determined that the value of the variable node connected thereto is 1, flipping the values of all check nodes connected to the variable node connected thereto, that is, 0 is changed to 1, and 1 is changed to 0, removing the variable node connected thereto and the edge related to the variable node connected thereto, removing all check nodes with a degree of 0, checking whether the value of the removed check node is 0, if all the check nodes are 0, continuing to process the other check nodes with a degree of 1 in the graph until there is no check node with a degree of 1 in the graph, and turning to S227;

and S227, obtaining the values of the variable nodes, and determining a vector consisting of the values of the variable nodes as a vector b.