Decoder, and memory system for obtaining an updated posterior messages corresponding to a non-zero sub-matrix

1 . A decoder, comprising:

a first memory; and

a message updating circuit,

wherein the first memory is configured to store posterior probability messages, and wherein the message updating circuit is configured to:

sequentially read a posterior probability message corresponding to each non-zero sub-matrix of a current layer from the first memory in a first reading order, the first reading order being determined according to a position of each non-zero sub-matrix of the current layer;

obtain an updated posterior probability message corresponding to each non-zero sub-matrix of the current layer based on the posterior probability message corresponding to each non-zero sub-matrix of the current layer in a current iteration; and

sequentially write the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer into the first memory in a first writing order, the first writing order being determined according to the first reading order.

2 . The decoder of claim 1 , wherein the first reading order is determined according to a position relationship between each non-zero sub-matrix of the current layer and non-zero sub-matrices of a previous layer of the current layer and a layer before the previous layer of the current layer.

3 . The decoder of claim 2 , wherein the first writing order is determined according to the first reading order and a position relationship between each non-zero sub-matrix of the current layer and a non-zero sub-matrix of a next layer of the current layer.

4 . The decoder of claim 3 , wherein:

according to a position relationship between the non-zero sub-matrix of each layer and the non-zero sub-matrices of a previous layer and a layer before the previous layer of each layer, the non-zero sub-matrices of each layer are divided into a first category, a second category, and a third category,

in a column where a non-zero sub-matrix in the first category of the current layer is located, both a sub-matrix of the previous layer of the current layer and a sub-matrix of the layer before the previous layer of the current layer are zero sub-matrices,

in a column where a non-zero sub-matrix in the second category of the current layer is located, a sub-matrix of the previous layer of the current layer is a zero sub-matrix, and a sub-matrix of the layer before the previous layer of the current layer is a non-zero sub-matrix,

in a column where a non-zero sub-matrix in the third category of the current layer is located, a sub-matrix of the previous layer of the current layer is a non-zero sub-matrix, and

the message updating circuit is configured to:

sequentially read posterior probability messages corresponding to non-zero sub-matrices belonging to the first category in the non-zero sub-matrices of the current layer, posterior probability messages corresponding to non-zero sub-matrices belonging to the second category in the non-zero sub-matrices of the current layer, and posterior probability messages corresponding to non-zero sub-matrices belonging to the third category in the non-zero sub-matrices of the current layer from the first memory in the first reading order.

5 . The decoder of claim 4 , wherein:

when the posterior probability messages corresponding to the non-zero sub-matrices belonging to the second category in the non-zero sub-matrices of the current layer are read, the message updating circuit is configured to:

sequentially read posterior probability messages corresponding to a first portion of the non-zero sub-matrices, posterior probability messages corresponding to a second portion of the non-zero sub-matrices, and posterior probability messages corresponding to a third portion of the non-zero sub-matrices from the first memory,

in columns where the first portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the layer before the previous layer of the current layer belong to the first category,

in columns where the second portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the layer before the previous layer of the current layer belong to the second category,

in columns where the third portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the layer before the previous layer of the current layer belong to the third category,

when the posterior probability messages corresponding to the non-zero sub-matrices belonging to the third category in the non-zero sub-matrices of the current layer are read, the message updating circuit is configured to:

sequentially read posterior probability messages corresponding to a fourth portion of the non-zero sub-matrices, posterior probability messages corresponding to a fifth portion of the non-zero sub-matrices, and posterior probability messages corresponding to

a sixth portion of the non-zero sub-matrices from the first memory,

in columns where the fourth portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the previous layer of the current layer belong to the first category,

in columns where the fifth portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the previous layer of the current layer belong to the second category, and

in columns where the sixth portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the previous layer of the current layer belong to the third category.

6 . The decoder of claim 1 , wherein:

the message updating circuit is configured to sequentially write, into the first memory, a message, and

the message including:

posterior probability messages corresponding to non-zero sub-matrices of the current layer for which in columns where the non-zero sub-matrices of the current layer is located, sub-matrices in a next layer of the current layer are non-zero sub-matrices, and

posterior probability messages corresponding to non-zero sub-matrices of the current layer for which in columns where the non-zero sub-matrices of the current layer are located, sub-matrices in the next layer of the current layer are zero sub-matrices.

7 . The decoder of claim 1 , wherein the message updating circuit is configured to:

obtain the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer based on the posterior probability message corresponding to each non-zero sub-matrix of the current layer in the current iteration and a check node message corresponding to each non-zero sub-matrix of the current layer in a previous iteration.

8 . The decoder of claim 7 , wherein:

the message updating circuit comprises:

a variable node message processing circuit,

a check node message processing circuit, and

a posterior probability message processing circuit,

the variable node message processing circuit is configured to:

sequentially read the posterior probability message corresponding to each non-zero sub-matrix of the current layer from the first memory in the first reading order; and

obtain a variable node message corresponding to each non-zero sub-matrix of the current layer based on the posterior probability message corresponding to each non-zero sub-matrix of the current layer in the current iteration and the check node message corresponding to each non-zero sub-matrix of the current layer in the previous iteration,

the check node message processing circuit is configured to:

obtain the check node message corresponding to each non-zero sub-matrix of the current layer based on the variable node message corresponding to each non-zero sub-matrix of the current layer and a first algorithm, and

the posterior probability message processing circuit is configured to:

obtain the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer based on the variable node message corresponding to each non-zero sub-matrix of the current layer and the check node message corresponding to each non-zero sub-matrix of the current layer; and

sequentially write the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer into the first memory in the first writing order.

9 . The decoder of claim 8 , wherein the first algorithm comprises a Sum-Product Algorithm and a Min-Sum Algorithm.

10 . The decoder of claim 8 , further comprising:

a second memory,

wherein the variable node message processing circuit comprises a first control circuit, a third memory, and a variable node message updating circuit,

wherein the first control circuit is configured to:

obtain a reading order table from the second memory; and

sequentially read a posterior probability message corresponding to each non-zero sub-matrix of the current layer from the first memory in the first reading order in the reading order table,

wherein the variable node message updating circuit is configured to:

perform a first operation on the posterior probability message corresponding to each non-zero sub-matrix of the current layer in the current iteration and the check node message corresponding to each non-zero sub-matrix of the current layer in the previous iteration, to obtain the variable node message corresponding to each non-zero sub-matrix of the current layer, and

wherein the third memory is configured to:

store the variable node message corresponding to each non-zero sub-matrix of the current layer.

11 . The decoder of claim 10 , wherein:

the second memory is further configured to store flag bit information,

the flag bit information is configured to indicate in a column where each non-zero sub-matrix of the current layer is located, whether a sub-matrix of a next layer of the current layer is a non-zero sub-matrix,

the posterior probability message processing circuit comprises an address updating circuit, a second control circuit, a posterior probability updating circuit and a third control circuit,

the address updating circuit is configured to:

generate a second reading order based on the first reading order and the flag bit information, wherein in the second reading order, variable node messages corresponding to non-zero sub-matrices of the current layer for which in columns where the non-zero sub-matrices of the current layer are located sub-matrices of the next layer of the current layer are non-zero sub-matrices are read first, and then variable node messages corresponding to non-zero sub-matrices of the current layer for which in columns where the non-zero sub-matrices of the current layer are located sub-matrices of the next layer of the current layer are zero sub-matrices are read,

the second control circuit is configured to:

read the variable node message corresponding to each non-zero sub-matrix of the current layer stored in the third memory based on the second reading order,

the posterior probability updating circuit is configured to:

obtain the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer based on the check node message corresponding to each non-zero sub-matrix of the current layer and the variable node message corresponding to each non-zero sub-matrix of the current layer, and

the third control circuit is configured to:

write the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer into the first memory based on the first writing order; the first writing order is the same as the second reading order.

12 . The decoder of claim 1 , further comprising:

a hard decision circuit configured to:

generate a decoding output vector based on the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer;

obtain a decoding result after decoding the current layer in the current iteration based on the decoding output vector and a check matrix; and

determine whether to stop decoding based on the decoding result, whether the current layer is the last layer of the check matrix, and whether a number of iterations exceeds an iteration number threshold.

13 . The decoder of claim 12 , wherein the hard decision circuit is configured to:

determine, based on a first posterior probability message in the updated posterior probability messages corresponding to each non-zero sub-matrix of the current layer being greater than or equal to 0, that an element in the decoding output vector corresponding to the first posterior probability message is 0;

determine, according to the first posterior probability message in the posterior probability messages corresponding to each non-zero sub-matrix of the current layer being less than 0, that an element in the decoding output vector corresponding to the first posterior probability message is 1;

perform a second operation on the decoding output vector and a transposed matrix of the check matrix to obtain a decoding result after decoding the current layer in the current iteration; and

stop decoding based on the decoding result being 0 or a current number of iterations being equal to the iteration number threshold and the current layer being the last layer of the check matrix.

14 . A memory system, comprising:

a memory device configured to output read data; and

a decoder, comprising:

a first memory; and

a message updating circuit,

wherein the first memory is configured to store posterior probability messages,

wherein the message updating circuit is configured to:

sequentially read a posterior probability message corresponding to each non-zero sub-matrix of a current layer from the first memory in a first reading order, the first reading order being determined according to a position of each non-zero sub-matrix of the current layer;

obtain an updated posterior probability message corresponding to each non-zero sub-matrix of the current layer based on the posterior probability message corresponding to each non-zero sub-matrix of the current layer in a current iteration; and

sequentially write the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer into the first memory in a first writing order, the first writing order being determined according to the first reading order, and

wherein the decoder is configured to decode a codeword to be decoded in the read data.

15 . The memory system of claim 14 , further comprising:

an encoder configured to receive write data and encode the write data,

wherein the memory device is further configured to receive the encoded write data.

16 . A method of decoding, comprising:

sequentially reading a posterior probability message corresponding to each non-zero sub-matrix of a current layer from a first memory in a first reading order, the first reading order being determined according to a position of each non-zero sub-matrix of a current layer;

obtaining an updated posterior probability message corresponding to each non-zero sub-matrix of the current layer based on the posterior probability message corresponding to each non-zero sub-matrix of the current layer in a current iteration; and

sequentially writing the updated posterior probability message corresponding to each non-zero sub-matrix of the current layer into the first memory in a first writing order, the first writing order being determined according to the first reading order.

17 . The method of claim 16 , wherein the first reading order is determined according to a position relationship between each non-zero sub-matrix of the current layer and non-zero sub-matrices of a previous layer of the current layer and a layer before the previous layer of the current layer.

18 . The method of claim 17 , wherein the first writing order is determined according to the first reading order and a position relationship between each non-zero sub-matrix of the current layer and a non-zero sub-matrix of a next layer of the current layer.

19 . The method of claim 18 , wherein:

according to a position relationship between the non-zero sub-matrix of each layer and the non-zero sub-matrices of the previous layer and a layer before the previous layer of each layer, the non-zero sub-matrices of each layer are divided into a first category, a second category, and a third category,

in a column where a non-zero sub-matrix in the first category of the current layer is located, both a sub-matrix of the previous layer of the current layer and a sub-matrix of the layer before the previous layer of the current layer are zero sub-matrices,

in a column where a non-zero sub-matrix in the second category of the current layer is located, a sub-matrix of the previous layer of the current layer is the zero sub-matrix, and a sub-matrix of the layer before the previous layer of the current layer is a non-zero sub-matrix,

in a column where a non-zero sub-matrix in the third category of the current layer is located, a sub-matrix of the previous layer of the current layer is a non-zero sub-matrix, and

the sequentially reading the posterior probability message corresponding to each non-zero sub-matrix of the current layer from the first memory in the first reading order comprises:

sequentially reading posterior probability messages corresponding to non-zero sub-matrices belonging to the first category in the non-zero sub-matrices of the current layer, posterior probability messages corresponding to non-zero sub-matrices belonging to the second category in the non-zero sub-matrices of the current layer, and posterior probability messages corresponding to non-zero sub-matrices belonging to the third category in the non-zero sub-matrices of the current layer from the first memory in the first reading order.

20 . The method of claim 19 , wherein:

reading posterior probability messages corresponding to the non-zero sub-matrices belonging to the second category in the non-zero sub-matrices of the current layer from the first memory comprises:

sequentially reading posterior probability messages corresponding to a first portion of the non-zero sub-matrices, posterior probability messages corresponding to a second portion of the non-zero sub-matrices, and posterior probability messages corresponding to a third portion of the non-zero sub-matrices from the first memory,

in columns where the first portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the layer before the previous layer of the current layer belong to the first category,

in columns where the second portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the layer before the previous layer of the current layer belong to the second category,

in columns where the third portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the layer before the previous layer of the current layer belong to the third category, and

reading posterior probability messages corresponding to the non-zero sub-matrices belonging to the third category in the non-zero sub-matrices of the current layer from the first memory comprises:

sequentially reading posterior probability messages corresponding to a fourth portion of the non-zero sub-matrices, posterior probability messages corresponding to a fifth portion of the non-zero sub-matrices, and posterior probability messages corresponding to a sixth portion of the non-zero sub-matrices from the first memory,

in columns where the fourth portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the previous layer of the current layer belong to the first category,

in columns where the fifth portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the previous layer of the current layer belong to the second category, and

in columns where the sixth portion of the non-zero sub-matrices are located, the non-zero sub-matrices of the previous layer of the current layer belong to the third category.