Referring back to FIG. 3B, peripheral circuits 302 may be coupled to memory array 301 through bit lines 316, word lines 318, source lines 314, BSL 315, and TSL 313. Peripheral circuits 302 may include any suitable analog, digital, and mixed-signal circuits for facilitating the operations of memory array 301 by applying and sensing at least one of voltage signals or current signals to and from each target memory cell 306 through bit lines 316, word lines 318, source lines 314, BSL 315, and TSL 313. Peripheral circuits 302 may include various types of peripheral circuits formed using metal-oxide-semiconductor technologies. For example, FIG. 5 illustrates some example peripheral circuits, the peripheral circuits 302 including a page buffer/sense amplifier 504, a column decoder/bit line driver 506, a row decoder/word line driver 508, a voltage generator 510, control logic circuit 512, registers 514, an interface 516, and a data bus 518. It is understood that in some examples, additional peripheral circuits not shown in FIG. 5 may be included as well.

Page buffer/sense amplifier 504 may be configured to read and program (write) data from and to memory array 301 according to the control signals from control logic circuit 512. In one example, page buffer/sense amplifier 504 may store one page of program data (write data) to be programmed into one page 320 of memory array 301. In another example, page buffer/sense amplifier 504 may perform program verify operations to ensure that the data has been properly programmed into memory cells 306 coupled to selected word lines 318. In still another example, page buffer/sense amplifier 504 may also sense the low power signals from bit line 316 that represents a data bit stored in memory cell 306 and amplify the small voltage swing to recognizable logic levels in a read operation. Column dedecoder/bit line driver 506 may be configured to be controlled by control logic circuit 512 and select one or more memory strings 308 by applying bit line voltages generated from voltage generator 510.

Row decoder/word line driver 508 may be configured to be controlled by control logic circuit 512 and select/deselect blocks 304 of memory array 301 and select/deselect word lines 318 of block 304. Row decoder/word line driver 508 may be further configured to drive word lines 318 using word line voltages generated from voltage generator 510. In some examples, row decoder/word line driver 508 may also select/deselect and drive BSL 315 and TSL 313 as well. As described below in detail, row decoder/word line driver 508 is configured to perform program operations on the memory cells 306 coupled to the selected word line(s) 318. Voltage generator 510 may be configured to be controlled by control logic circuit 512 and generate the word line voltages (e.g., read voltage, program voltage, pass voltage, local voltage, verification voltage, etc.), bit line voltages, and source line voltages to be supplied to memory array 301.

Control logic circuit 512 may be coupled to each peripheral circuit described above and configured to control operations of each peripheral circuit. Registers 514 may be coupled to control logic circuit 512 and include status registers, command registers, and address registers for storing status information, command operation codes (OP codes), and command addresses for controlling the operations of each peripheral circuit. Interface 516 may be coupled to control logic circuit 512 and act as a control buffer to buffer and relay control commands received from a host (not shown) to control logic circuit 512, and to buffer and relay status information received from control logic circuit 512 to the host. Interface 516 may further be coupled to column decoder/bit line driver 506 via data bus 518 and act as a data I/O interface and data buffer to buffer and relay data to or from memory array 301.

The memory devices in implementations of the present disclosure include, but are not limited to, a three-dimensional NAND memory. For ease of understanding, taking the three-dimensional NAND memory as an example to explain the present disclosure.

As a kind of memory device which is more stable and more quick and convenient in terms of data reading and writing as compared to traditional disk storage, three-dimensional NAND memory has penetrated into every corner of daily life. In order to meet the increasing demand for storage, the size of three-dimensional NAND memory is shrinking, and the number of information bits in a single flash memory unit is increasing, the type of the memory cell is changing from SLC to MLC. TLC, QLC. As a result, the error probability of flash memory is increasing. The traditional BCH (Bosc Chaudhuri Hocquenghem) error correction code is not enough to ensure the safety of data. The LDPC (Low Density Parity Check), as an error correction method whose error correction ability approaches Shannon limit, is gradually replacing BCH as an error correction coding method in the new generation of flash memory controllers.

FIG. 6 is a schematic diagram of the framework structure of a decoder proposed in the examples of the present disclosure. As shown in FIG. 6, the decoder includes a posterior probability storing circuit, a permutating circuit, a message updating circuit, an inverse permutating circuit, a node message storing circuit. During coding, a posterior probability message in the posterior probability storing circuit may be permutated by the permutating circuit, and then check node messages may be updated in the message updating circuit and permutated by the inverse permutating circuit to get the updated check node messages.

LDPC codes may be classified into several types according to their construction, one of which is based on Euclidcan Geometry (EG) and Projective Geometry (PG) over finite fields, collectively referred to as Finite Geometry (FG) codes. These codes are known to have excellent error correction performance and relatively large minimum distances. However, the EG-LDPC codes have higher row weight and column weight, so that it is not conducive to be implemented using the coding architecture shown in FIG. 6 or using algorithms such as method of successive algorithm (MSA). At present, the coding of Euclidcan Geometry Low Density Parity Check (EG-LDPC) codes mainly relates to the improvement on algorithm, and the improvement on decoder architecture is generally uncommon. How to improve the decoder architecture to improve the throughput and reduce the resource utilization has become an urgent problem to be solved.

Based on one or more of the above problems, a decoder is provided by an implementation of present disclosure, as shown in FIG. 7. A check matrix corresponding to a frame of code words comprises a*a sub-matrices, a plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, and a plurality of sub-matrices located in the same column constitute a column of the check matrix, the decoder comprising:

- a check node updating circuit 701 that comprises first updating units of a levels, wherein the first updating unit of each level is connected sequentially; and a variable node updating circuit 702 that is connected with the check node updating circuit 701, the variable node updating circuit 702 comprises second updating units of a levels, wherein the second updating unit of each level is connected sequentially; wherein,
- in a first time period, the check node updating circuit 701 is configured to cause: the first updating unit of each level except the first updating unit of a first level sequentially receive variable node messages corresponding to each column of the check matrix, and sequentially calculate the received variable node messages with messages in the first updating unit of a previous level, to obtain the check node messages corresponding to different layers of the check matrix in the first updating units of different levels in the first updating units of a levels;
- in the first time period, the variable node updating circuit 702 is configured to cause: the second updating unit of the a-th level sequentially receive the variable node messages corresponding to each column of the check matrix, and the second updating unit of each level except the second updating unit of the a-th level sequentially receive the messages of the second updating unit of a next level and performing calculation, to obtain corresponding intermediate calculation values in the second updating units of different levels in the second updating units of a levels; and
- in a second time period after the first time period, the variable node updating circuit 702 is configured to cause: the second updating unit of each level except the second updating unit of the a-th level sequentially receive the check node messages corresponding to each layer of the check matrix, and sequentially calculate the received check node messages with the intermediate calculation values of the second updating unit of the next level, to obtain the variable node messages corresponding to different columns of the check matrix in the second updating units of different levels in the second updating units of a levels.

In some specific examples, the first updating unit of each level is connected with both the first updating unit of a previous level and the first updating unit of a next level, and the first updating unit of a-th level is connected with the first updating unit of the first level; the second updating unit of each level of the variable node updating circuit 702 is connected with both the second updating unit of a previous level and the second updating unit of a next level, and the second updating unit of a-th level is connected with the second updating unit of the first level. Here, a and n below are positive integers greater than zero.

Table 1 exemplarily illustrates a check matrix. The following is explained by taking the check matrix in Table 1 as an example. The check matrix shown in Table 1 includes 5*5 sub-matrices. A plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, with a total of 5 layers; and a plurality of sub-matrices located in the same column constitute a column of the check matrix, with a total of 5 columns. B; represents a circulated permutation matrix, and the value of i corresponds to the number of columns in which non-zero elements are located in the first row of the circulated permutation matrix, wherein −1 represents an all-zero matrix. Here, the variable node messages corresponding to the first column to the fifth column of the check matrix are sequentially L₀, L₁, L₂, L₃, L₄, and the check node messages corresponding to the first layer to the fifth layer of the check matrix are sequentially C₀, C₁, C₂, C₃, C₄.

H
^

=

[

-
1

B
0

B
1

B
2

B
3

B
3

-
1

B
0

B
1

B
2

B
2

B
3

-
1

B
0

B
1

B
1

B
2

B
3

-
1

B
0

B
0

B
1

B
2

B
3

-
1

]

Table
⁢

1

Taking the check matrix illustrated in Table 1 as an example below, the operations of the decoder of the above implementation during a first iteration will be described.

In the case where the check matrix includes 5*5 sub-matrices, the check node updating circuit 701 of the decoder includes first updating units of 5 levels, and the variable node updating circuit 702 includes second updating units of 5 levels. The first time period includes five first sub-time periods, and the second time period includes five second sub-time periods. The duration of each of the five first sub-time periods is equal, and the duration of each of the five second sub-time periods is equal, wherein the duration of the first sub-time period is equal to that of the second sub-time period.

It should be noted that the number of levels of the check matrix and the corresponding first updating unit and the second updating unit listed herein is only an example and is not intended to limit the number of levels of the check matrix and the first updating unit and the second updating unit in the implementations of the present disclosure.

In the j-th first sub-time period, the first updating units of the second to fifth levels receive an initial channel message L_j−1, and compare it with the message of the first updating unit of the previous level in the previous time period to obtain the minimum value, so that the intermediate calculation value is obtained. In the next first sub-time period, the value obtained after permutating the intermediate calculation value of the first updating unit of the previous level is passed to the first updating unit of the next level and participates in the calculation of the first updating unit of the next level, to obtain the intermediate calculation value of the first updating unit of the next level in the next sub-time period. After five first sub-time periods, the check node message corresponding to the fifth layer of the check matrix is obtained in the first updating unit of the first level, the check node message corresponding to the fourth layer of the check matrix is obtained in the first updating unit of the second level, the check node message corresponding to the third layer of the check matrix is obtained in the first updating unit of the third level, the check node message corresponding to the second layer of the check matrix is obtained in the first updating unit of the fourth level, and the check node message corresponding to the first layer of the check matrix is obtained in the first updating unit of the fifth level.

In the j-th first sub-time period, the second updating unit of the fifth level receives the initial channel message L_j−1, and in the next first sub-time period, the intermediate calculation value in the second updating unit of the next level is passed to the second updating unit of the previous level and participates in the calculation of the second updating unit of the previous level, to obtain the intermediate calculation value of the second updating unit of the previous level in the next first sub-time period. In the j-th first sub-time period, the second updating units of the first to fourth levels receive the all-zero message, and compute it with the message passed by the second updating unit of the next level.

In the j-th second sub-time period, the second updating unit of the fifth level receives the message after being permutated of the second updating unit of the first level, and the second updating unit of each level in the second updating units of the first to fourth levels receives the message of the second updating unit of the next level and the message passed by the first updating unit of the fifth level, and calculate both messages. After five second sub-time periods, the variable node message corresponding to the fifth column of the check matrix is obtained in the second updating unit of the first level, the variable node message corresponding to the fourth column of the check matrix is obtained in the second updating unit of the second level, the variable node message corresponding to the third column of the check matrix is obtained in the second updating unit of the third level, the variable node message corresponding to the second column of the check matrix is obtained in the second updating unit of the fourth level, and the variable node message corresponding to the first column of the check matrix is obtained in the second updating unit of the fifth level.

In some implementations, the decoder further comprises: a first selector 703 comprising a first input 709, a second input 710 and a first output 706, the first input 709 is connected with the first updating unit of the a-th level, the second input 710 is used for receiving all-zero messages, and the first output 706 is connected with each of the second updating units of the first to a-1-th levels;

- the first selector 703 is configured to: in a first time period, select a message at the second input 710 as an output message at the first output 706; in a second time period, select a message at the first input 709 as an output message at the first output 706.

In some implementations, the decoder further comprises: a second selector 704 comprising a third input 711, a fourth input 712 and a second output 707; the third input 711 is used for receiving variable node messages corresponding to each column of the check matrix, the fourth input 712 is connected with the second updating unit of the first level, and the second output 707 is connected with the second updating unit of the a-th level;

- the second selector 704 is configured to: in the first time period, select a message at the third input 711 as an output message at the second output 707; and in the second time period, select a message at the fourth input 712 as an output message at the second output 707.

In some implementations, the decoder further comprises:

- a third selector 705 comprising a fifth input 713, a sixth input 714 and a third output 708, the fifth input 713 is used for receiving initial channel messages corresponding to each column of the check matrix, the sixth input 714 is connected with the second updating unit of the first level, and the third output 708 is connected with each of the first updating units of the second to a-th levels;
- the third selector 705 is configured to: in a first time period of a first iteration, select a message at the fifth input 713 as an output message at the third output 708; and
- in a first time period of a next iteration, select a message at the sixth input 714 as an output message at the third output 708.

It can be understood that each iteration is divided into the first time period and the second time period. In the first iteration, the variable node messages received in the variable node updating circuit 702 and the check node updating circuit 701 are the initial channel messages (L₀L₁L₂L₃L₄), where Li is the initial channel message corresponding to the i-th layer of the check matrix. In the first iteration, in the first time period, the first selector 703 selects the all-zero message (00000) at the second input 710 as the output message at the first output 706, and the second selector 704 selects the message (L₀L₁L₂L₃L₄) at the third input 711 as the output message at the second output 707, and the third selector 705 selects the message (L₀L₁L₂L₃L₄) at the fifth input 713 as the output message at the third output 708. In the first iteration, in the second time period, the first selector 703 receives the message of the first updating unit of a-th level in the check node updating circuit 701 as the output message at the first output 706, the second selector 704 receives the message of the second updating unit of the first level in the variable node updating circuit 702 as the output message at the second output 707, and the third output 708 of the third selector 705 does not output a message. The difference between the second iteration and the first iteration is that in the second iteration, in the first time period, the third selector 705 selects the message at the sixth input 714 as the output message at the third output 708, that is, the variable node message updated in the last iteration is selected as the output message at the third output 708.

In some implementations, the first updating unit of each level comprises a first delaying unit, and the first updating units of the first to a-1-th levels also comprise a first shifting unit, the first updating units of the second to a-th levels also each comprises a comparing unit; the first delaying unit is configured to delay outputting the messages updated in the first updating unit of each level, the first shifting unit is configured to shift the message updated in the first updating unit, and the comparing unit is used for comparing the message shifted in the first updating unit of the previous level with the received variable node message to obtain a minimum value.

Here, the comparing unit includes, but is not limited to, a comparator. The comparing unit may perform comparing to obtain the minimum value or sub-minimum value. The updating units of the first to fourth levels in the variable node updating circuit 702 may also include a selection unit for selecting a corresponding minimum value or sub-minimum value. In FIG. 7, the comparing unit is represented by comp and the selection units are represented by sel₀-sel₃.

In some implementations, the check node updating circuit 701 is configured to:

- in the second time period, close the comparing unit in the first updating units of the second to a-th levels.

It is understood that the comparing unit in the check node updating circuit 701 does not work in the second time period. That is, in the second time period, the values in the first updating unit of the previous level are not compared after being passed to the first updating unit of the next level.

In some implementations, the second updating unit of each level comprises a second delaying unit, and the second updating units of the first to a-1-th levels also comprise an addition unit and a second shifting unit; the second delaying unit is configured to delay outputting the message updated in the second updating unit of each level, the second shifting unit is configured to shift the message updated in the second updating unit, and the addition unit is configured to add the message in the second updating unit of the next level and the received variable node message. The addition unit herein includes, but is not limited to, an adder.

In FIG. 7, the addition unit is denoted by + and the first delaying unit and the second delaying unit are denoted by D.

In some implementations, the shift value of the first shifting unit in the first updating unit of the n-th level is equal to the shift value of the second shifting unit in the second updating unit of the n-th level; n is less than or equal to a.

In FIG. 7, P₀-P₃represent the first shifting unit in the first updating units of the first to fourth levels, respectively, and P₀-P₃represent the second shifting unit in the second updating units of the first to fourth levels, respectively.

Here, the first shifting unit of the first updating unit of the n-th level is represented by P_n−1and the second shifting unit of the second updating unit of the n-th level is represented by P_n−1, wherein n-1 represents the shift value of the shifting unit. The shift value of the first shifting unit of the first updating unit of the n-th level is equal to the shift value of the second shifting unit of the second updating unit of the n-th level.

In some implementations, the delay duration of the first delaying unit of the first updating unit of each level is h1, and the delay duration of the second delaying unit of the second updating unit of each level is h2, and h1=h2.

In some specific examples, the delay duration of the first delaying unit is equal to the duration of the first sub-time period and the duration of the second sub-time period. The delay duration of the second delaying unit is equal to the duration of the first sub-time period and the duration of the second sub-time period, and the duration of the first sub-time period is equal to the duration of the second sub-time period.

In some specific examples, in the first iteration, and at the initial time before the first time period, the value after the first delaying unit in the check node updating circuit 701 is set to the maximum value and the value after the second delaying unit in the variable node updating circuit 702 is set to 0.

The situations about the intermediate computation values in the first updating unit of each level and the second updating unit of each level in the first iteration of coding will be described in detail below.

In the first one of the first sub-time periods of the first iteration, the initial channel message L₀is passed into the first updating units of the second to fifth levels in the check node updating circuit 701 through the third output 708 of the third selector 705. In the first updating unit of each level in the first updating units of the second to fifth levels, L₀, after being compared with the value after the respective first delaying unit (the maximum value initially set), respectively, is temporarily donated as D_i. At the same time, in the first one of the first sub-time periods of the first iteration, the initial channel message L₀is passed into the second updating unit of the fifth level in the variable node updating circuit 702 through the second output 707 of the second selector 704, and the all-zero message at the second input 710 of the first selector 703 is passed into the second updating units of the first to fourth levels through the first output 706 and is added to the value (initially set to 0) after the second delaying unit in the second updating units of the first to fourth levels. In the second one of the first sub-time periods to the fifth one of the first sub-time periods, the initial channel messages L_m−1is passed into the check node updating circuit 701 sequentially, and be compared with the value obtained after the intermediate calculation value updated in the last first sub-time period in the first updating unit of the previous level is permutated. to obtain the updated intermediate calculation value in the second updating unit of each level. At the same time, the initial channel message L_m−1is passed into the variable node updating circuit 702 and is added to 0.

The values after the first delaying unit in the first updating units of the first to fifth levels are denoted as D₀-D₄, respectively, and the values after in the second delaying unit in the second updating units of the first to fifth levels are denoted as D₅-D₉, respectively. Taking D₄in the fifth one of the first sub-time periods as an example for illustration, in the first one of the first sub-time periods, L₀is passed into the check node updating circuit 701, and L0 is obtained after being compared with the maximum value Max, D_i=L₀(0<i<5), D₀=Max. In the second one of the first sub-time periods, L1 is passed in to the check node updating circuit 701, and after being compared with value of D₀by the permutation matrix P₀, D₁=min(L₁Max⁰) is obtained, wherein the upper 0 indicates the permutation unit identification. In the third one of the first sub-time periods, L₂is passed into the check node updating circuit 701, and after being compared with the value of D₁by the permutation unit P₁, D₂=min(L₂L₁¹) is obtained. In the fourth one of the first sub-time periods, L₃is passed into the check node updating circuit 701, and after being compared with the value of D₂by the permutation unit P₂, D₃=min(L₃(L₂L₁¹)²) is obtained. In the fifth one of the first sub-time periods, L₄is passed into the check node updating circuit 701, and after being compared with the value of D₃by the permutation unit P₃, D₄=min(L₄(L₃(L₂L₁¹)²)³) is obtained. Similarly, the values in other first updating units in the fifth one of the first sub-time periods may be derived. Table 2 shows the values of D_icorresponding to the initial period, the first one of the first sub-time periods to the fifth one of the first sub time-periods.

TABLE 2

The

The first
second

one of the
one of the
The third

Initial
first sub-
first sub-
one of the
The fourth one of
The fifth one

Time
time
time
time
first sub-
the first sub-time
of the first sub-

period
period
periods
period
time periods
periods
time periods

D₀
Max
Max
min(L₀Max³)
min(L₁L₀³)
min(L₂(L₁L₀²)³)
min(L₃(L₂(L₁L₀¹)²)³)

D₁
Max
min(L₀Max⁰)
min(L₁Max⁰)
min(L₂L₀⁰)
min(L₃(L₁,L₀³)⁰)
min(L₄(L₂(L₁L₀²)³)⁰)

D₂
Max
min(L₀Max¹)
min(L₁L₀⁰)
min(L₂L¹)
min(L₃(L₂L₀⁰)¹)
min(L₄(L₃(L₁L₀³)⁰)¹)

D₃
Max
min(L₀Max²)
min(L₁L₀²)
min(L₂(L₁L₀¹)²)
min(L₃(L₂L₁¹)²)
min(L₄(L₃(L₂L₀⁰)¹)²)

D₄
Max
min(L₀Max³)
min(L₁L₀³)
min(L₂(L₁L₀²)³)
min(L₃(L₂(L₁L₀¹)²)³)
min(L₄(L₃(L₂L₁¹)²)³)

After the fifth one of the first sub-time periods, the first updating unit of each level in the check node updating circuit 701 completes the minimization and comparison processes corresponding to a layer of the check matrix, to obtain the updated check node message in each layer of the check matrix. In the next second time period, the check node updating circuit 701 only transmits the updated check node message obtained in the first updating unit of each level, after being permutated by the permutation unit, to the variable node updating circuit 702 to participate in the calculation.

The specific shift in P_iis analyzed below with Table 2 and taking the fifth one of the first sub-time periods as an example for analyzing. In the fifth one of the first sub-time periods, the value corresponding to D₄is D₄=min(L₄(L₃(L₂L₁¹)²)³) The variable node message corresponding to the first column of the check matrix is L₀, wherein L₀does not exist in D₄. It can be seen from the check matrix that D₄is the check node message of the first layer (the first column block of the first layer is 0); the check node message corresponding to the second column block B₀of the first layer is L₁, and after passing P₁in D₄, (L₁¹) is obtained; the check node message corresponding to the third column block B₀is Z₂, and by being compared with (L₁¹), min(L₂L₁¹) is obtained, thus at this time, the message sequence B₀in the second column block needs to be converted into message sequence B₁in the third column block. The size of the small matrix in this example is 3*3, so the shift value of B₁is r(P₁)=(r(B₀)−r(B₁)+3), wherein r(P₁) is the shift value of P₁, and 3 is the rank of the small matrix. The check node message corresponding to the fourth column block B₂is L₃, and by being compare with ((L₂L₁¹)²), min(L₃(L₂L₁¹)²) is obtained, at this time the message sequence B₁in the third column block needs to be converted into message sequence B₂in the fourth column block, and thus the shift value of P₂is r(P₂)=(r(B₁)−r(B₂)+3); and so on, the shift value of P_xis r(P_x)=(r(B_x−1)−r(B_x)+3).

Based on the check node message is the message sequence of B₃obtained as described above, i.e. the message sequence of the last column, the second layer of the check matrix is then taken into account, which is the message value of D₃at the fifth one of the first sub-time periods. At this time, the sequence is that of B₂, and the sequence is changed into B₃after being permutated by P₃in the sixth second sub-time period and is passed into the variable node updating circuit 702. The remaining layers likewise become sequence B3 after several permutations and are passed into the variable node update circuit 702. At the same time, it should also be noted that during the first one to the fifth one of the second sub-time periods, the check node updating circuit 701 outputs only the calculated check node messages in sequence. In order to prevent the comparing unit from comparing the message corresponding to the following layers with the message passing through the first selector 703 again to get wrong result when outputting the check node message corresponding to the previous layers, the comparing unit be suspended at this time should and directly pass the permutated data to the first updating unit of the next level.

Next, the values corresponding to D_iin the variable node updating circuit 702 are described in detail. The message obtained in the check node updating circuit 701 is denoted as C_i(i is the number of layers):

In the first one of the first sub-time periods, the output of the first selector 703 is 0, and the output of the second selector 704 is L₀, at this time D_i=0(4<i<9), D₉=L₀. In the second one of the first sub-time periods, the output of the first selector 703 is 0, and the output of the second selector 704 is L₁, at this time D_i=0(4<i<8), D₈=L₀, D₉=L₁. In the third one of the first sub-time periods, the output of the first selector 703 is 0, and the output of the second selector 704 is L₂, at this time D_i=0(4<i<7), D₇=L₀³, D₈=L₁, D₉=L₂. In the fourth one of the first sub-time periods, the output of the first selector 703 is 0, and the output of the second selector 704 is L₃, at this time D_i=0(4<i<6), D₆=L₀³², D₇=L₁³, D₈=L₂, D₉=L₃. In the fifth one of the first sub-time periods, the output of the first selector 703 is 0, and the output of the second selector 704 is L₄, at this time D₅=L₀³²¹, D₆=L₁³², D₇=L₂³, D₈=L₃, D₉=L₄.

In the first one of the second sub-time periods, the updated check node message C0 (i.e., min (L₄(L₃(L₂L₁¹)²)³)) corresponding to the first layer of the check matrix in the first updating unit of the fifth level is passed directly into the second updating units of the first to fourth levels of the variable node updating circuit 702, and then is added to the value obtained with the intermediate calculation value updated in the previous sub-time period in the second updating unit of the next level in the variable node updating circuit 702 after being permutated. In the second one to the fifth one of the second sub-time periods, the check node messages of the second to fifth layers of the check matrix updated in the first updating units of the first to the fourth levels pass through the comparing unit (closed in the second time period) and the permutation unit, then into second updating unit of the first to fourth levels of the variable node updating unit sequentially, and are added to the value obtained with the intermediate calculation value updated in the previous sub-time period in the second updating unit of the next level in the variable node updating circuit 702 after being permutated.

Next, the values corresponding to Dⁱin the first one to the fifth one of the second sub-time periods in the variable node updating circuit 702 are described in detail. The message obtained in the check node updating circuit 701 is denoted as C_i(i is the number of layers), taking D₅in the fifth one of the second sub-time periods as an example:

In the first one of the second sub-time periods, C₀is passed into the variable node updating circuit 702, and is added to the value of D_i(5<i≤9), at this time D_i=D_i+1+C₀(5≤i<9), D₉=L₀³²¹⁰. In the second one of the second sub-time periods, C₁is passed into the variable node updating circuit 702, and is added to the value of D₉, to get D₈=C₁+L₀³²¹⁰. In the third one of the second sub-time periods, C₂is passed into the variable node updating circuit 702, and is added to the value of D₈, to get D₇=C₂+(C₁+L₀³²¹⁰)³. In the fourth one of the second sub-time periods, C₃is passed into the variable node updating circuit 702, and is added to the value of D₇, to get D₆=C₃+(C₂+(C₁+L₀³²¹⁰)³)². In the fifth one of the second sub-time periods, C₄is passed into the variable node updating circuit 702, and is added to the value of D₆, to get D₅=C₄+(C₃+(C₂+(C₁+L₀³²¹⁰)³)²)¹.

Table 3 shows the values of corresponding D_iin the first one of the second sub-time periods to the fifth one of the second sub-time periods.

TABLE 3

The fifth one of
The first one of
The second one of
The third one of

Time
the first sub-time
the second sub-time
the second sub-time
the second sub-time

period
periods
periods
periods
periods

D₅
L₀³²¹
C₀+ (L₁³²)¹
C₁+ (C₀+ (L₂³)²)¹
C₂+ (C₁+ (C₀+ L₃³)²)¹

D₆
L₁³²
C₀+ (L₂³)²
C₁+ (C₀+ L₃³)²
C₂+ (C₁+ (C₀+ L₄)³)²

D₇
L₂³
C₀+ L₃³
C₁+ (C₀+ L₄)³
C₂+ (C₁+ L₀³²¹⁰)³

D₈
L₃
C₀+ L₄
C₁+ L₀³²¹⁰
C₂+ (C₀+ (L₁³²)¹)⁰

D₉
L₄
L₀³²¹⁰
(C₀+ (L₁³²)¹)⁰
(C₁+ (C₀+ (L₂³)²)¹)⁰

Time
The fourth one of the second
The fifth one of the second

period
sub-time periods
sub-time periods

D₅
C₃+ (C₂+ (C₁+ (C₀+ L⁴)³)²)¹
C₄+ (C₃+ (C₂+ (C₁+ L₀³²¹⁰)³)²)¹

D₆
C₃+ (C₂+ (C₁+ L₀³²¹⁰)³)²
C₄+ (C₃+ (C₂+ (C₀+ (L₁³²)¹)⁰)³)²

D₇
C₃+ (C₂+ (C₀+ (L₁³²)¹)⁰)³
C₄+ (C₃+ (C₁+ (C₀+ (L₂³)²)¹)⁰)³

D₈
C₃+ (C₁+ (C₀+ (L₂³)²)¹)⁰
C₄+ (C₂+ C₁+ (C₀+ (L₃³)²)¹)⁰

D₉
(C₂+ C₁+ (C₀+ (L₃³)²)¹)⁰
(C₃+ (C₂+ (C₁+ (C₀+ L₄)³)²)¹)⁰

Similarly, the specific shift value in the variable node updating circuit 702 is analyzed, the principle of which is substantially the same as that in the check node updating circuit 701. Also, taking the D₉in the fifth one of the second sub-time periods as an example for brief illustration, at this time, D₉=(C₃+(C₂+(C₁+(C₀+L₄)³)²)¹)⁰. The first layer check node message (C₀) passed from the check node updating circuit 701 is accumulated with the corresponding initial channel message (L₄), and then after passing P₃, accumulated with the check node message (C₁) of next layer. Here, the sequence of the check node message passed from the check node updating circuit 701 is the sequence of B₃, but the sequence of the second layer is B₂. When accumulated, (C₀+L₄) needs to be changed into the sequence of B₂by passing P₃, and then accumulated with C₁, thus r(P₃)=(r(B₂)−r(B₃)+3), which is consistent with the shift value in the check node updating circuit 701.

In some implementations, the decoder further comprises a parity check circuit connected with the variable node updating circuit 702;

- the parity check circuit is configured to: receive the variable node messages of the variable node updating circuit 702, and substitute the received variable node message into check equations for checking, if all the check equations are fulfilled, it is determined that the coding is successful; otherwise if not all the check equations are fulfilled, it is determined that the coding fails, and a next iteration is needed to update the check node messages and the variable node messages until the coding is successful or a maximum iteration count is reached.

Here, the parity check circuit may specifically be connected to the second delaying unit in the second updating unit of the first level in the variable node updating circuit 702.

It can be understood that after five first sub-time periods and five second sub-time periods, updating of the check node messages and the variable node messages are completed once. The outputs in the variable node updating circuit 702 will be divided into two paths, one for hard decision to check whether the coding is successful, and the other is output to the check node updating circuit 701 for the next iterative coding. In another iteration, the third output 708 of the third selector 705 selects the message of the sixth input 714 to input into the check node updating circuit 701, and the rest operations remain unchanged until the whole coding is completed.

It can be understood that the implementations of the present disclosure provide a new architecture of the decoder, which utilizes the first shifting unit, the second shifting unit, a first delaying unit, a second delaying unit, a comparing unit and an addition unit in different first updating unit and second updating unit to adjust the duration of the first delaying unit and the second delaying unit by using a simple shift delay function to update the information.

In the implementations of the present disclosure, the check node messages corresponding to each layer of the check matrix are updated by using the first updating units of a levels in the first time period, and the variable node messages corresponding to each column of the check matrix are updated by the second updating units of a levels in the first time period and the second time period, which can increase throughput and reduce resource utilization.

Based on the above-described decoder, the examples of the present disclosure also provide a memory controller, which include the decoder according to any one of above examples.

Based on the above-described memory controller, the examples of the present disclosure also provide a memory system, which includes the memory controller of the above examples and a memory device coupled to the memory controller.

FIG. 8 illustrates a block diagram of a memory system 601 comprising a memory controller 602 and a memory device 603. The memory controller 602 controls the memory device 603 to perform read and write operations. Here, the memory controller 602 may be coupled in any way to the memory device 603. The memory controller 602 includes a control unit (e.g. central processing unit) 608, a data buffer 609, an error correction module 606, a host I/F 605, and a memory I/F 607. The memory device 603 in the examples of the present disclosure may be semiconductor memory for storing data in a non-volatile way, such as a NAND memory. The memory system 601 is connected to a host 604. The host I/F 605 outputs command received from the host 604, valid data (write data) and so on to the internal bus 610, and transmits the valid data (read data) read from the memory device 603, the response from the control unit 608 to the host 604.

The control unit 608 may instruct the memory I/F 607 to write the valid data and the parity data, check matrix to the memory device 603 according to the command from the host 604. In addition, the control unit may instruct the memory I/F 607 to read the valid data and the parity data, check matrix from the memory device according to the command from the host 604.

The error correction module 606 herein includes an encoding unit and a decoding unit. The encoding unit encodes the written valid data of a predetermined size to generate parity data (e.g., a low density parity check code) and the corresponding parity check matrix. The parity check data and the corresponding parity check matrix generated by the encoding unit may be stored in the memory device. The decoding unit performs decoding by using the parity check data and the corresponding parity check matrix. The decoding unit herein includes the decoder. The parity check code and the corresponding parity check matrix used in coding may be obtained from the memory device.

Based on the above-described memory system, the examples of present disclosure also provide an electronic device, which includes the decoder according to any one of the above examples and a memory device coupled to the decoder.

The decoder may be built into the memory controller, or may be not built into the memory controller and but provided outside the memory controller.

The specific structure and composition of the memory controller, memory system, electronic device may be referred to the foregoing detailed description of FIG. 1. FIG. 2A, FIG. 2B, FIG. 3A, FIG. 3B, FIG. 4 and FIG. 5, which is not repeated for the sake of brevity.

Based on the above-described decoder, the examples of present disclosure also provide a coding method, wherein during coding a frame of code words with a check matrix including a*a sub-matrices, a plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, and a plurality of sub-matrices located in the same column constitute a column of the check matrix, as shown in FIG. 9, the method comprising:

- in a first time period, first updating unit of each level except the first updating unit of a first level sequentially receiving variable node messages corresponding to each column of the check matrix, and sequentially calculating the received variable node messages with messages in the first updating unit of a previous level, to obtain the check node messages corresponding to different layers of the check matrix in the first updating units of different levels in the first updating units of a levels:
- in the first time period, the second updating unit of the a-th level sequentially receiving the variable node messages corresponding to each column of the check matrix, and the second updating unit of each level except the second updating unit of the a-th level sequentially receiving the messages of the second updating unit of a next level and performing calculation, to obtain corresponding intermediate calculation values in the second updating units of different levels in the second updating units of a levels:
- in a second time period, the second updating unit of each level except the second updating unit of the a-th level sequentially receiving the check node messages corresponding to each layer of the check matrix, and sequentially calculating the received check node messages with the intermediate calculation values of the second updating unit of the next level, to obtain the variable node messages corresponding to different columns of the check matrix in the second updating units of different levels in the second updating units of a levels.

In some implementations, the first updating unit of each level comprises a first delaying unit, and the first updating unit of the first level to a-1-th level also each comprises a first shifting unit, the first updating unit of a second level to a-th level also each comprises a comparing unit;

- the method comprises: the first delaying unit delaying outputting of the messages updated in the first updating unit of each level, the first shifting unit shifting the messages updated in the first updating unit, and the comparing unit comparing the messages shifted in the first updating unit of the previous level with the received variable node messages to obtain a minimum value.

In some implementations, the method further comprises:

- in the second time period, closing the comparing unit in the first updating unit of the second level to a-th level.

In some implementations, the second updating unit of each level each comprises a second delaying unit, and the second updating unit of the first level to a-1-th level also each comprises an addition unit and a second shifting unit

- the method further comprises: the second delaying unit delaying outputting of the messages updated in the second updating unit of each level, the second shifting unit shifting the messages updated in the second updating units, and the addition unit adding the messages in the second updating unit of the next level and the received variable node messages.

In some implementations, the decoder further comprises: a first selector comprising a first input, a second input and a first output, the first input is connected with the first updating unit of the a-th level, the second input is configured to receive all-zero messages, and the first output is connected with each of the second updating unit of the first level to a-1-th level;

- the method further comprises: in the first time period, selecting a message at the second input as an output message at the first output; and in the second time period, selecting a message at the first input as an output message at the first output.

In some implementations, the decoder further comprises: a second selector comprising a third input, a fourth input and a second output, the third input is configured to receiving the variable node messages corresponding to each column of the check matrix, the fourth input is connected with the second updating unit of the first level, and the second output is connected with the second updating unit of the a-th level;

- the method further comprises: in the first time period, selecting a message at the third input as an output message at the second output; and in the second time period, selecting a message at the fourth input as an output message at the second output.

In some implementations, the decoder further comprises a parity check circuit connected with the variable node updating circuit;

- the method further comprises: receiving the variable node messages of the variable node updating circuit, and substituting the received variable node messages into check equations for checking, if all the check equations are fulfilled, it is determined that the coding is successful; otherwise if not all the check equations are fulfilled, it is determined that the coding fails, and a next iteration is needed to update the check node messages and the variable node messages until the coding is successful or a maximum iteration count is reached.

In some implementations, the decoder further comprises: a third selector comprising a fifth input, a sixth input and a third output, the fifth input is configured to receiving initial channel messages corresponding to each column of the check matrix, the sixth input is connected with the second updating unit of the first level, and the third output is connected with each of the first updating units of the second level to a-th level;

- the method further comprises: in the first time period, selecting a message at a fifth input as an output message at a third output;
- in a next iteration, selecting the message at the sixth input as an output message at the third output.

FIG. 10 is a schematic flow diagram of framework of a coding method according to an example of the present disclosure. The coding method of the example of the present disclosure will be further introduced in conjunction with FIG. 10.

In the first iteration, the initial channel messages are stored in a posterior probability storing circuit, and the check node updating circuit receives the initial channel messages L₀, L₁, L₂, L₃, L₄sequentially in the first time period. The minimum or sub-minimum value is obtained by passing the initial channel messages through the comparing unit. The updated check node messages corresponding to the first layer to the fifth layer of the check matrix after five first sub-time periods. In the variable node updating circuit, the variable node updating circuit accumulates the initial channel messages and the updated check node messages to obtain the updated variable node messages. The updated variable node messages are obtained after five second sub-time periods. After the variable node messages are updated, it is determined whether the maximum iteration count is reached. If the maximum iteration count is reached, output the code word; otherwise, carry out the next iteration.

The above coding method has been described in detail on the decoder side, which is not repeated for the sake of brevity.

It should be understood that references to “one example” or “an example” throughout the specification mean that particular features, structures or characteristics related to the examples are included in at least one example of the present disclosure. Thus, the phrases “in one example” or “in an example” appearing throughout the specification do not necessarily refer to the same example. In addition, these particular features, structures or characteristics may be combined arbitrarily in one or more examples. It should be understood that in various examples of the present disclosure, the sequence numbers of the above-mentioned processes do not mean that the sequence of execution, and the sequence of execution should be determined by their functions and inherent logic and should not constitute any limitation on the implementation of the examples of the present disclosure. The above sequence number of examples of that present disclosure are for description only and do not represent the advantages and disadvantages of the example.

The method disclosed in several examples provided in the present disclosure may be arbitrarily combined without conflict to get other example methods.

According to a first aspect of the examples of the present disclosure, a decoder is provided, wherein a check matrix corresponding to a frame of code words comprises a*a sub-matrices, a plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, and a plurality of sub-matrices located in the same column constitute a column of the check matrix, wherein a is a positive integer greater than 0, the decoder comprises:

- a check node updating circuit that comprises first updating units of a levels, wherein the first updating unit of each level is connected sequentially; and
- a variable node updating circuit that is connected with the check node updating circuit, the variable node updating circuit comprises second updating units of a levels, wherein the second updating unit of each level is connected sequentially; wherein,
- in a first time period, the check node updating circuit is configured to cause: the first updating unit of each level except the first updating unit of a first level sequentially receive variable node messages corresponding to each column of the check matrix, and sequentially calculate the received variable node messages with messages in the first updating unit of a previous level, to obtain the check node messages corresponding to different layers of the check matrix in the first updating units of different levels in the first updating units of a levels;
- in the first time period, the variable node updating circuit is configured to cause: the second updating unit of the a-th level sequentially receive the variable node messages corresponding to each column of the check matrix, and the second updating unit of each level except the second updating unit of the a-th level sequentially receive the messages of the second updating unit of a next level and performing calculation, to obtain corresponding intermediate calculation values in the second updating units of different levels in the second updating units of a levels; and