TWI895029B - Low density parity check decoder - Google Patents

Abstract

A low-density parity check (LDPC) decoder includes a parity check code storage block and a plurality of computing engines. The parity check code storage block is configured to store a parity check code matrix. The parity check code matrix includes a plurality of columns. Each of the columns includes a plurality of submatrices. The parity check code storage block includes a plurality of column group storage blocks. Each of the column group storage blocks is configured to store a column group including one or more columns. The column group storage block which stores the column group including more of the columns is disposed closer to the center of the parity check code storage block. The computing engines are disposed on two sides of the parity check code storage block.

Description

LDPC decoder

This application relates to a low-density parity check decoder that can reduce clock speed and power consumption.

Low-density parity-check (LDPC) codes are widely used as error-correcting codes for passive optical networks (PONs), Ethernet, and other data communication protocols because their error correction capability is very close to the theoretical maximum (i.e., the Shannon limit). A common algorithm for decoding and correcting LDPC codes is the log-likelihood ratio (LLR) minimum-sum algorithm.

A common hardware implementation for LDPC code decoding and error correction uses a min-sum engine to perform LLR min-sum operations on the LDPC code. However, using only a single min-sum engine to perform operations on the LDPC code requires an extremely fast clock speed for the decoding circuitry. For example, the 25G PON LDPC code is a 17664x3072 sparse matrix composed of 69x12 arrays of 256x256 sub-matrices. To operate LDPC check codes using a single min-sum computing engine for 25G PON, the decoding circuit would require an extremely fast clock speed of around 50 GHz, which is impossible to achieve with current or foreseeable future integrated circuit technology.

Therefore, in practice, decoding operations are implemented through multiple parallel min-sum computing engines. Logically, 25G PON can use 256 parallel min-sum computing engines. However, since using 256 min-sum computing engines will result in too many circuit signals (signal connection lines), when the computer-aided design (CAD) tools used for layout and routing (Place and Route) discover that the circuit has too many signals, the CAD tools will not be able to layout and route this circuit. Therefore, for 25G PON, the current practical upper limit of the number of parallel min-sum computing engines is now 64. However, when using 64 min-sum computing engines, the clock speed required to implement the decoding circuit is still close to 1GHz, which is still difficult to implement and consumes a lot of power.

In some embodiments, a low-density parity-check (LDPC) decoder includes a parity-check code storage block and multiple computing engines. The parity-check code storage block is used to store a parity-check code matrix. The parity-check code matrix includes multiple rows, each row including multiple sub-matrices. The parity-check code storage block includes multiple row group storage blocks. Each row group storage block is used to store a row group including at least one row. The row group storage block storing a row group including more rows is located closer to the center of the parity-check code storage block. The multiple computing engines are coupled to the parity-check code storage block. Multiple computing engines are used to perform LLR minimum sum operations on the parity check code matrix. The multiple computing engines are set on both sides of the parity check code storage block.

In some embodiments, multiple computing engines are arranged in a checkerboard pattern on both sides of the parity check code storage block.

In some embodiments, the computing engine that is farther away from the parity check code storage block has a faster computing speed.

In some embodiments, a buffer is provided between some adjacent computing engines. The buffer includes one or more buffer units.

In some embodiments, a buffer area that is farther away from the parity check code storage block includes more buffer units and has a stronger buffering capacity.

In some embodiments, the number of the plurality of computing engines disposed on one side and the other side of the parity code storage block is the same.

In some embodiments, the LDPC decoder is a 25G passive optical network (PON) decoder.

In some embodiments, the number of the plurality of computing engines is 256, and the number of the plurality of computing engines disposed on one side and the other side of the parity code storage block is both 128.

In some embodiments, multiple computing engines are arranged in a 16x8 checkerboard pattern on both sides of the parity check code storage block.

In some embodiments, each column group storage block includes 6 precision bits.

In some embodiments, the 6 precision bits include 1 sign bit and 5 value bits.

In some embodiments, the number of row group storage blocks is 24.

In some embodiments, each row group includes a number of rows ranging from 1 to 4.

In some embodiments, each row is assigned to only a single row group.

In some embodiments, each row includes multiple columns, each sub-matrix is located in the corresponding column, each sub-matrix is a zero matrix or a shifted unit matrix, and the zero matrices in the same column of all multiple rows in each row group are merged.

In some embodiments, multiple computing engines are symmetrically arranged on both sides of the parity check code storage block.

In summary, in any embodiment, the CAD tool can layout and route an LDPC decoder comprising up to 256 parallel computing engines, such that the LDPC decoder can have the slowest possible clock speed while still meeting the target decoding throughput.

The following detailed description of the features and advantages of the present invention is sufficient to enable anyone skilled in the art to understand the technical content of the present invention and implement it accordingly. Based on the contents disclosed in this specification, the scope of the patent application, and the drawings, anyone skilled in the art can easily understand the relevant objectives and advantages of the present invention.

Please refer to Figures 1A through 1C. The parity-check code matrix M1 comprises multiple rows (columns) C, each of which contains multiple sub-matrices M2. The parity-check code matrix M1 shown in Figures 1A through 1C is an LDPC parity check code suitable for 25G PON. This parity-check code matrix M1 is a 17664x3072 sparse matrix composed of 69x12 arrays of 256x256 sub-matrices M2. That is, this parity-check code matrix M1 includes 69 rows C, each of which contains twelve 256x256 sub-matrices M2. Each sub-matrix M2 is either a zero matrix or a shifted unit matrix. In Figures 1A through 1C , if a number is displayed in the grid representing sub-matrix M2, it indicates that sub-matrix M2 is a unit matrix and the number in the grid represents the unit matrix's translation. If no number is displayed in the grid representing sub-matrix M2, it indicates that sub-matrix M2 is a zero matrix. For ease of explanation, the following example uses a 7x7 unit matrix to illustrate the unit matrix's translation. The 7x7 unit matrix is shown in Table 1. 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 Table 1

In some embodiments, the translation of the unit matrix is a rightward translation. When the translation is 1 (i.e., the number in the grid of the sub-matrix M2 is 1), the translated unit matrix is as shown in Table 2 below. 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 Table 2

When the translation amount is 2 (i.e., the number in the grid representing sub-matrix M2 is 2), the unit matrix of the translation is shown in Table 3 below. 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 Table 3

As shown in Tables 1 through 3, when the shift is 1, all 1 values in the unit matrix are shifted right by one row, and the 1 values in the rightmost row of the unit matrix are shifted to the leftmost row. When the shift is 2, all 1 values in the unit matrix are shifted right by two rows, and the 1 values in the two rightmost rows of the unit matrix are shifted to the two leftmost rows. The examples in Tables 1 through 3 can be extrapolated to the case of a shift of 2 or greater and a 256x256 unit matrix. In some embodiments, the unit matrix shift is a left shift.

In Figures 1A to 1C , for ease of explanation, the 69 rows C included in the parity-check code matrix M1 are referred to as rows C0 to C68, and the multiple sub-matrices M2 included in each row C are the 12 sub-matrices M2 located directly below the row C. Taking row C0 as an example, the multiple sub-matrices M2 included in row C0 are the 12 sub-matrices M2 located directly below row C0, from the sub-matrix M2 with a translation amount of 27 to the sub-matrix M2 with a translation amount of 88.

In Figures 1A to 1C , parity-check code matrix M1 is an LDPC code suitable for 25G PON, but the present invention is not limited to this. In some embodiments, parity-check code matrix M1 can be an LDPC code suitable for any rate PON (e.g., APON, BPON, EPON, and GPON), Ethernet, or other data communication protocols.

In Figures 1A to 1C , the parity-check code matrix M1 includes 69 rows C, and each row C includes twelve 256x256 sub-matrices M2, but the present invention is not limited to this. In some embodiments, the parity-check code matrix M1 may include any number of rows C, each row C may include any number of sub-matrices M2, and the sub-matrices M2 may be of any size.

In some embodiments, the multiple rows C included in the parity-check code matrix M1 are grouped into multiple row groups G, each row group G including at least one row C. See FIG2 . Rows C0 through C68 included in the parity-check code matrix M1 shown in FIG1A through FIG1C are grouped into multiple row groups G shown in FIG2 . For ease of explanation, the multiple row groups G are referred to herein as row groups G0 through G23, and the at least one row C included in each row group G is at least one row C located directly below the row group G. Taking row groups G0-G3 as an example, the at least one row C included in row group G0 is row C0 located directly below row group G0. The at least one row C included in row group G1 is row C1 located directly below row group G1. The at least one row C included in row group G2 is row C2, row C8, and row C52 located directly below row group G2. The at least one row C included in row group G3 is row C3, row C12, row C23, and row C49 located directly below row group G3. In some embodiments, the number of rows C included in each row group G ranges from 1 to 4, but the present invention is not limited thereto. The number of rows C included in each row group G can be any number.

In some embodiments, the grouping of the multiple rows C included in the parity-check code matrix M1 into multiple row groups G requires that the number of non-zero matrices in the same column (row) of all rows C in each row group G cannot exceed one. See Figures 1A to 1C and Figure 2. Taking row groups G0 to G3 as an example, among the 1st to 12th columns of row C0, only the second column contains a zero matrix; the remaining columns contain non-zero matrices. Furthermore, among rows C1 to C68, there is no row C with only the second column containing a non-zero matrix. Therefore, row C0 cannot be grouped with any other row C. Therefore, row group G0 only contains row C0. Similarly, all columns of row C1 are nonzero matrices, making row C1 impossible to group with any other row C. Therefore, row group G1 contains only row C1. The 1st, 5th, and 9th columns of row C2 are nonzero matrices, and the remaining columns are zero matrices. The 2nd, 7th, and 12th columns of row C8 are nonzero matrices, and the remaining columns are zero matrices. The 3rd, 4th, 6th, 8th, 10th, and 11th columns of row C52 are nonzero matrices, and the remaining columns are zero matrices. Rows C2, C8, and C52 all have no more than one nonzero matrix in the same column, making them possible to group together. Therefore, row group G2 contains rows C2, C8, and C52. The 7th, 9th, and 10th columns of row C3 are non-zero matrices, and the remaining columns are zero matrices. The 2nd, 5th, and 11th columns of row C12 are non-zero matrices, and the remaining columns are zero matrices. The 1st, 8th, and 12th columns of row C23 are non-zero matrices, and the remaining columns are zero matrices. The 3rd, 4th, and 6th columns of row C49 are non-zero matrices, and the remaining columns are zero matrices. Rows C3, C12, C23, and C49 all have no more than one non-zero matrix in the same column, so rows C3, C12, C23, and C49 can be grouped together. Therefore, row group G3 includes rows C3, C12, C23, and C49. The above example of row group G0 to row group G3 can be used to analogously promote the grouping of row group G4 to row group G23.

By grouping the multiple rows C included in the parity-check code matrix M1 into multiple row groups G, the zero matrices located in the same row across all rows C of each row group G are merged, and the number of sub-matrices M2 included in each row group G (i.e., the number of columns in the sub-matrix M2 included in each row group G) is equal to the number of columns in the sub-matrix M2 included in row C. For example, see Figure 3. Since row groups G0 and G1 each contain only one row C, no zero matrices located in the same row in row groups G0 and G1 are merged. Since row group G2 includes rows C2, C8, and C52, the zero matrices located in the same column in rows C2, C8, and C52 are merged. Because row group G3 includes rows C3, C12, C23, and C49, the zero matrices in the same column of rows C3, C12, C23, and C49 are merged. The number of sub-matrices M2 contained in row groups G0, G1, G2, and G3 is equal to the number of columns in sub-matrix M2 contained in row C, i.e., 12. The above example of row groups G0 through G3 can be applied analogously to the situation of rows G4 through G23.

See Figure 4. In some embodiments, the method for grouping the multiple rows C included in the parity-check code matrix M1 into multiple row groups G is as follows: an initial row C is assigned to a current row group G and the initial row C is set as the current row C (step S01), and the first row C after the current row C that can be assigned to the current row group G is found (step S02). After the row C that can be assigned to the current row group G is found, the row C that can be assigned to the current row group G is assigned to the current row group G (step S03), and the row C that can be assigned to the current row group G is set as the current row C (step S04), and then step S02 is executed again. When no row C can be found that can be added to the current row group G, the current row group G is considered full, and the row C next to the current row C is added to a new row group G (step S05). The new row group G is set as the current row group G, and the row C next to the current row C is set as the current row C (step S06). Then, step S02 is executed again.

Please refer to Figures 1A through 1C and Figure 4. The method shown in Figure 4 is illustrated by grouping the multiple rows C included in the parity-check code matrix M1 shown in Figures 1A through 1C into multiple row groups G. First, row C0 (i.e., the initial row C) is assigned to row group G0 (i.e., the current row group G) and is set as the current row C (step S01). The first row C after row C0 that can be assigned to row group G0 is then found (step S02). When no row C that can be assigned to row group G0 is found, row group G0 is considered full, and row C1 (i.e., the row C next to row C0) is assigned to row group G1 (i.e., the new row group G) (step S05), row group G1 is set as the current row group G, and row C1 is set as the current row C (step S06). Then, the first row C after row C1 that can be assigned to row group G1 is found (step S02). If no row C can be found that can be split into row group G1, row group G1 is considered full, and row C2 (i.e., the row C following row C1) is split into row group G2 (i.e., the new row group G) (step S05). Row group G2 is set as the current row group G, and row C2 is set as the current row C (step S06). The first row C after row C2 that can be split into row group G2 is then searched for (step S02). If row C6 that can be split into row group G2 is found, row C6 is split into row group G2 (step S03), and row C6 is set as the current row C (step S04). The first row C after row C6 that can be split into row group G2 is then searched for (step S02). After finding row C8 that can be split into row group G2, row C8 is split into row group G2 (step S03) and row C8 is set as the current row C (step S04). Next, the first row C after row C8 that can be split into row group G2 is searched for (step S02). After finding row C49 that can be split into row group G2, row C49 is split into row group G2 (step S03) and row C49 is set as the current row C (step S04). Next, the first row C after row C49 that can be split into row group G2 is searched for (step S02).

When the method shown in FIG4 is used to group the multiple rows C included in the parity-check code matrix M1 shown in FIG1A through FIG1C into multiple row groups G, rows C0 and C1 are grouped separately. Rows C2, C6, C8, and C49 are grouped together in the same row group G. Rows C3, C4, and C5 are grouped together in the same row group G. The grouping results for the remaining rows C are not described here. In the above example, row C0 is used as the initial row C, but the present invention is not limited to this. In some embodiments, any row C included in the parity-check code matrix M1 can be used as the initial row C.

See Figure 5. In some embodiments, the method for grouping the multiple rows C included in the parity-check code matrix M1 into multiple row groups G is as follows: an initial row C is assigned to a current row group G and the initial row C is set as the current row C (step S11). Then, a determination is made as to whether the row C following the current row C can be assigned to the current row group G (step S12). If the row C following the current row C can be assigned to the current row group G, the row C following the current row C is assigned to the current row group G (step S13), the row C following the current row C is set as the current row C (step S14), and step S12 is then repeated. When the row C next to the current row C cannot be added to the current row group G, the current row group G is considered full, and the row C next to the current row C is added to a new row group G (step S15). The new row group G is set as the current row group G, and the row C next to the current row C is set as the current row C (step S16). Then, step S12 is executed again.

Please refer to Figures 1A to 1C and Figure 5. The method shown in Figure 5 is illustrated by grouping the multiple rows C included in the parity-check code matrix M1 shown in Figures 1A to 1C into multiple row groups G. First, row C0 (i.e., the initial row C) is assigned to row group G0 (i.e., the current row group G) and is set as the current row C (step S11). A determination is then made as to whether row C1 (i.e., the row C following row C0) can be assigned to row group G0 (step S12). When row C1 cannot be assigned to row group G0, row group G0 is considered full, and row C1 (i.e., the next row C after row C0) is assigned to row group G1 (i.e., the new row group G) (step S15). Row group G1 is set as the current row group G, and row C1 is set as the current row C (step S16). Then, it is determined whether row C2 (i.e., the next row C after row C1) can be assigned to row group G1 (step S12). When row C2 cannot be added to row group G1, row group G1 is considered full, and row C2 (i.e., the next row C after row C1) is added to row group G2 (i.e., the new row group G) (step S15). Row group G2 is set as the current row group G, and row C2 is set as the current row C (step S16). Then, it is determined whether row C3 (i.e., the next row C after row C2) can be added to row group G2 (step S12). If row C3 cannot be added to row group G2, row group G2 is considered full, and row C3 (i.e., the row C following row C2) is added to row group G3 (i.e., the new row group G) (step S15). Row group G3 is set as the current row group G, and row C3 is set as the current row C (step S16). A determination is then made as to whether row C4 (i.e., the row C following row C3) can be added to row group G3 (step S12). If row C4 can be added to row group G3, row C4 is added to row group G3 (step S13), and row C4 is set as the current row C (step S14). A determination is then made as to whether row C5 (i.e., the row C following row C4) can be added to row group G3 (step S12). When row C5 can be assigned to row group G3, row C5 is assigned to row group G3 (step S13) and row C5 is set as the current row C (step S14). Then, it is determined whether row C6 (i.e., the next row C after row C5) can be assigned to row group G3 (step S12).

When the method shown in FIG5 is used to group the multiple rows C included in the parity-check code matrix M1 shown in FIG1A through FIG1C into multiple row groups G, rows C0, C1, and C2 are grouped independently. Rows C3, C4, and C5 are grouped together in the same row group G. Row C6 is grouped independently. Rows C7 and C8 are grouped together in the same row group G. Row C9 is grouped independently. The grouping results for the remaining rows C are not described here. In the above example, row C0 is used as the initial row C, but the present invention is not limited to this. In some embodiments, any row C included in the parity-check code matrix M1 can be used as the initial row C.

In some embodiments, the columns C included in the parity-check code matrix M1 can be grouped into a plurality of column groups G using a trial-and-error method. In some embodiments, a computer program executes the trial-and-error method to group the columns C included in the parity-check code matrix M1 into the plurality of column groups G. The grouping of the plurality of column groups G shown in FIG2 is the result of the trial-and-error method. In the embodiment of FIG2 , the number of the plurality of column groups G is 24, but the present invention is not limited to this. In some embodiments, the number of the plurality of column groups G can be any number. Since each row C is assigned to only one row group G, the parity check code matrix M1 can be divided into multiple tile layout groups without being reused between the row groups G.

See Figure 6. Parity-check code storage block B1 includes multiple row group storage blocks B2. Parity-check code storage block B1 is used to store parity-check code matrix M1. Each row group storage block B2 is used to store a row group G. The multiple row groups G stored in the multiple row group storage blocks B2 in Figure 6 correspond to the multiple row groups G in Figure 2. The row group storage block B2 storing the row group G containing more rows C is positioned closer to the center of parity-check code storage block B1. Taking the parity-check code storage block B1 shown in Figure 6 as an example, each row group G contains between one and four rows C. Row group storage block B2, which stores row group G15, row group G10, row group G12, row group G7, row group G9, row group G5, row group G6, row group G3, and row group G4, each containing four rows C, is located in the center of parity code storage block B1. Row group storage block B2, which stores row group G2, row group G8, row group G11, row group G13, and row group G14, each containing three rows C, is located farther from the center of parity code storage block B1 than row group storage block B2, which stores row group G, each containing four rows C. Row group storage block B2, which stores row groups G16, G17, G18, G19, G20, G21, G22, and G23, each containing two rows C, is located further from the center of parity code storage block B1 than row group storage block B2, which stores row group G, which contains three rows C. Row group storage block B2, which stores row group G0 and row group G1, each containing only one row C, is located at the edge of parity code storage block B1.

See Figure 7. A low-density parity-check (LDPC) decoder 1 includes a parity-check code storage block B1 and a plurality of computing engines E. In some embodiments, the plurality of computing engines E are arranged in a checkerboard pattern on both sides of the parity-check code storage block B1. In the LDPC decoder 1 shown in Figure 7, the number of the plurality of computing engines E is 256. However, the present invention is not limited to this, and the number of the plurality of computing engines E can be any number. In some embodiments, the number of the plurality of computing engines E arranged on one side and the other side of the parity-check code storage block B1 is the same, taking the LDPC decoder 1 in Figure 7 as an example. When the number of the plurality of computing engines E is 256, the number of the plurality of computing engines E disposed on one side and the other side of the parity-check code storage block B1 is 128. However, the present invention is not limited thereto; the number of the plurality of computing engines E disposed on one side and the other side of the parity-check code storage block B1 may be different. In some embodiments, when the number of the plurality of computing engines E disposed on one side and the other side of the parity-check code storage block B1 is 128, the plurality of computing engines E are arranged in a 16x8 checkerboard pattern on both sides of the parity-check code storage block B1. However, the present invention is not limited to this. Multiple computation engines E can be arranged in a matrix of any size and placed on both sides of the parity-check code storage block B1. In some embodiments, LDPC decoder 1 is a 25G PON decoder, but the present invention is not limited to this. In some embodiments, LDPC decoder 1 can be a decoder for any rate PON (e.g., APON, BPON, EPON, and GPON), Ethernet, or other data communication protocols. In some embodiments, multiple computation engines E are symmetrically placed on both sides of the parity-check code storage block B1.

After the multiple rows C included in the parity-check code matrix M1 are grouped into multiple row groups G, the zero matrices located in the same row in all rows C of each row group G are merged. Therefore, the multiple computing engines E do not need to perform operations on the merged zero matrices, thereby reducing the number of signals required by the multiple computing engines E and thereby improving the computing speed of the multiple computing engines E. Therefore, computer-aided design (CAD) tools used for place and route can successfully place and route the LDPC decoder 1 in FIG. 7 without the problem of the CAD tool being unable to place and route the LDPC decoder 1 due to the use of too many computing engines E. Because LDPC decoder 1 can use 256 computing engines E to perform operations on parity-check code matrix M1 stored in parity-check code storage block B1 to decode and correct parity-check code matrix M1, the clock speed required by LDPC decoder 1 can be significantly reduced, thereby significantly reducing the power consumption of LDPC decoder 1.

In the LDPC decoder 1 shown in FIG7 , for the convenience of explanation, the plurality of computing engines E are referred to as computing engines E0 to E255. The distance d2 between the row group storage block B2 (hereinafter referred to as row group storage block B20) for storing the row group G1 and the computing engine E15 is the farthest vertical distance from the row group storage block B20 to the plurality of computing engines E. The distance d1 between the row group storage block B2 (hereinafter referred to as row group storage block B22) for storing the row group G15 and the computing engine E15 is the farthest vertical distance from the row group storage block B22 to the plurality of computing engines E. The distance d4 between the row group storage block B2 storing row group G0 (hereinafter referred to as row group storage block B21) and computing engine E240 is the maximum vertical distance from row group storage block B21 to multiple computing engines E. The distance d3 between the row group storage block B2 storing row group G12 (hereinafter referred to as row group storage block B23) and computing engine E240 is the maximum vertical distance from row group storage block B23 to multiple computing engines E. In some embodiments, distance d2 and distance d4 are equal in length, and distance d1 and distance d3 are equal in length, but the present invention is not limited thereto.

In some embodiments, multiple computation engines E utilize a log-likelihood ratio (LLR) minimum-sum algorithm to perform operations on the parity-check code matrix M1 stored in the parity-check code storage block B1 to decode and correct the parity-check code matrix M1. In some embodiments, the log-likelihood ratio represents precision using precision bits. In some embodiments, each row group storage block B2 includes six precision bits. However, the present invention is not limited to this, and each row group storage block B2 may include any number of precision bits. In some embodiments, the six precision bits include one sign bit and five value bits. In some embodiments, the number of bits of precision is determined through extensive experimentation on a large field-programmable gate array (FPGA) testbed. In some embodiments, each computation engine E includes 288 signals (24 (number of row group storage blocks B2) * 6 (number of bits of precision) * 2 (inputs and outputs) = 288).

Please refer to Figures 8A and 8B. In some embodiments, multiple computing engines E are arranged in a checkerboard pattern on the upper and lower sides of the parity check code storage block B1 (as shown in Figure 8A). In some embodiments, multiple computing engines E are arranged in a checkerboard pattern on the left and right sides of the parity check code storage block B1 (as shown in Figure 8B). In some embodiments, the layout of the LDPC decoder 1 shown in Figure 8B is a layout of the LDPC decoder 1 shown in Figure 8A rotated 90 degrees. In some embodiments, if there are more horizontal wiring than vertical wiring available in the IC process, the layout of the LDPC decoder 1 shown in Figure 8B is more suitable than the layout of the LDPC decoder 1 shown in Figure 8A.

9A and 9B . In some embodiments, the plurality of computing engines E in the same row of the plurality of computing engines E arranged in a checkerboard pattern on one side and the other side of the parity check code storage block B1 include a plurality of wires. Taking the eight computing engines E arranged in the same row at the bottom side of the parity check code storage block B1 shown in Figure 9A and the eight computing engines E arranged in the same row at the top side of the parity check code storage block B1 shown in Figure 9B as examples, when the number of multiple row group storage blocks B2 is 24 and each row group storage block B2 includes 6 precision bits, the number of wires included in the eight computing engines E shown in Figure 9A and the eight computing engines E shown in Figure 9B are both 2304 (8 (number of computing engines E) * 24 (number of multiple row group storage blocks B2) * 6 (number of precision bits) * 2 (input and output) = 2304). The width w1 of the eight computation engines E shown in FIG9A and the width w2 of the eight computation engines E shown in FIG9B are 92.16 μm (2304 (number of wires) * 0.08 μm (wire width) / 2 (number of wire layers) = 92.16 μm) when the LDPC decoder 1 is manufactured using TSMC's 12 nm process. The wire width and number of wire layers are determined by TSMC's 12 nm process. In some embodiments, the wire width and number of wire layers are determined by the process used by the LDPC decoder 1.

In some embodiments, computing engines E that are farther from parity-check code storage block B1 have larger circuit areas and faster computing speeds. For example, in Figure 9A , computing engine E96 has a larger circuit area and faster computing speed than computing engine E112 , while computing engine E80 has a larger circuit area and faster computing speed than computing engine E96 . Similarly, computing engine E0 has the largest circuit area and the fastest computing speed among the multiple computing engines E shown in Figure 9A . Similarly, computing engine E240 has the largest circuit area and the fastest computing speed among the multiple computing engines E shown in Figure 9B . In some embodiments, the circuit area of the computing engine E with the largest circuit area among the multiple computing engines E arranged in the same row (i.e., computing engine E0 in FIG. 9A or computing engine E240 in FIG. 9B ) may be, but is not limited to, 3000 square nanometers (squm). Taking FIG. 9A as an example, assuming that the width w1 of the eight computing engines E is 92.16 µm and the circuit area of computing engine E0 is 3000 squm, the height of computing engine E0 is 32.55 μm (3000 (squm) / 91.6 (μm) = 32.55 μm). In some embodiments, the circuit area of the computing engine E with the smallest circuit area among the multiple computing engines E arranged in the same row (i.e., computing engine E112 in FIG. 9A or computing engine E128 in FIG. 9B ) may be, but is not limited to, 2000 squm. Taking FIG. 9A as an example, assuming that the width w1 of the eight computing engines E is 92.16 µm and the circuit area of computing engine E112 is 2000 squm, the height of computing engine E112 is 21.7 μm (2000 (squm) / 91.6 (μm) = 21.7 μm).

Since the distance from the parity-check code storage block B1 to the farthest computing engine E (i.e., the total height h1 of the eight computing engines E in FIG. 9A and the total height h2 of the eight computing engines E in FIG. 9B ) is quite long (taking the total height h1 and the total height h2 as examples, it is approximately 217 (um) (21.7 (um) + 32.55 (um) / 2 * 8 = 217 (um) )), in some embodiments, a buffer needs to be set between some adjacent computing engines E to segment the multiple computing engines E in the same row, so as to enhance the signal strength from the parity-check code storage block B1, thereby preventing the time required for the signal from the parity-check code storage block B1 to propagate to some computing engines E from being too long.

See Figure 10 . In some embodiments, a buffer 10 is provided between two adjacent computing engines E in the same row, and multiple buffers 10 are provided within multiple computing engines E in the same row. For ease of explanation, the multiple buffers 10 shown in Figure 10 are referred to as buffer 11, buffer 12, and buffer 13. Signals from parity check code storage block B1 must be propagated to computing engines E112, E96, E80, E64, E48, E32, E16, and E0. Signals passing through buffer 11 must be propagated to computing engines E80, E64, E48, E32, E16, and E0. Signals passing through buffer 12 must be propagated to computing engines E48, E32, E16, and E0. Signals passing through buffer 13 must only be propagated to computing engines E16 and E0. Therefore, the buffering capacity (i.e., the ability to boost signal strength) of buffer 11 must be greater than the buffering capacity of buffers 12 and 13, and the buffering capacity of buffer 12 must also be greater than the buffering capacity of buffer 13. In some embodiments, buffer 10 includes one or more buffer cells. The more buffer cells buffer 10 includes, the stronger its buffering capability. Therefore, the number of buffer cells included in buffer 11 is greater than the number of buffer cells included in buffer 12 and buffer 13, and the number of buffer cells included in buffer 12 is also greater than the number of buffer cells included in buffer 13. Furthermore, the more buffer cells buffer 10 includes, the larger its circuit area. Therefore, the circuit area of buffer 11 is larger than the circuit areas of buffer 12 and buffer 13, and the circuit area of buffer 12 is also larger than the circuit area of buffer 13. In some embodiments, the location of the plurality of buffers 10 and the number of buffer cells included in each buffer 10 are determined based on the resistance (R), inductance (L), and capacitance (C) values of the wires. In some embodiments, the buffer cells may be, but are not limited to, buffer gates. In some embodiments, the plurality of computing engines E and the plurality of buffer cells are symmetrically arranged on both sides of the parity check code storage block B1.

In summary, in some embodiments, the LDPC decoder 1 can use 256 computing engines E to perform operations on the parity-check code matrix M1 stored in the parity-check code storage block B1 to decode and correct the parity-check code matrix M1. Therefore, the clock speed required by the LDPC decoder 1 can be significantly reduced, thereby significantly reducing the power consumption of the LDPC decoder 1.

Although the technical content of this case has been disclosed above through the preferred embodiments, it is not intended to limit this case. Any slight changes and embellishments made by anyone skilled in the art without departing from the spirit of this case should be included in the scope of this case. Therefore, the scope of protection of this case shall be determined by the scope of the attached patent application.

M1: Parity check code matrix M2: Submatrix C, C0-C68: Rows G, G0-G23: Row groups S01-S06, S11-S16: Steps B1: Parity check code storage block B2, B20-B23: Row group storage block 1: Low-density parity check decoder E, E0-E255: Calculation engine d1-d4: Distance A1, A2: Area w1, w2: Width h1, h2: Height 10-13: Buffer

Figures 1A to 1C are schematic diagrams of an embodiment of a parity-check code matrix. Figure 2 is a schematic diagram of an embodiment of multiple row groups. Figure 3 is another schematic diagram of an embodiment of multiple row groups. Figure 4 is a flow chart of an embodiment of a method for grouping multiple rows of a parity-check code matrix into multiple row groups. Figure 5 is a flow chart of another embodiment of a method for grouping multiple rows of a parity-check code matrix into multiple row groups. Figure 6 is a schematic diagram of an embodiment of a parity-check code storage block. Figure 7 is a schematic diagram of an embodiment of an LDPC decoder. Figure 8A is another schematic diagram of an embodiment of an LDPC decoder. Figure 8B is a schematic diagram of another embodiment of an LDPC decoder. Figure 9A is an enlarged view of one embodiment of the multiple computing engines in area A1 of Figure 8A. Figure 9B is an enlarged view of one embodiment of the multiple computing engines in area A2 of Figure 8A. Figure 10 is an enlarged view of another embodiment of the multiple computing engines in area A1 of Figure 8A.

1: Low-density parity check decoder

B1: Parity check code storage block

B2, B20~B23: Row group storage block

C, C0~C68: Row

G, G0~G23: Row Group

E, E0~E255: Calculation Engine

d1~d4: distance

Claims (11)

A low-density parity-check (LDPC) decoder comprises: A parity-check code storage block for storing a parity-check code matrix, the parity-check code matrix comprising a plurality of rows, each row comprising a plurality of sub-matrices, wherein the parity-check code storage block comprises a plurality of row group storage blocks, each row group storage block being configured to store a row group comprising at least one row, wherein the row group storage block storing a row group comprising a greater number of rows is positioned closer to the center of the parity-check code storage block; and Multiple computation engines are coupled to the parity-check code storage block, wherein the computation engines are configured to perform LLR minimum sum operations on the parity-check code matrix. The computation engines are disposed on at least two sides of the parity-check code storage block. Each row includes multiple columns, each sub-matrix is located in the corresponding column, and each sub-matrix is a zero matrix or a shifted unit matrix. In each row group, the zero matrices located in the same column of all rows are merged. The LDPC decoder of claim 1, wherein the computing engines are arranged in a checkerboard pattern on at least two sides of the parity check code storage block. The LDPC decoder of claim 1, wherein the operation speed of the operation engine farther from the parity check code storage block is higher than the operation speed of the operation engine closer to the parity check code storage block. In the LDPC decoder of claim 1, a buffer is provided between two adjacent operation engines, and the buffer includes one or more buffer units. The LDPC decoder as described in claim 4, wherein the buffer area farther away from the parity check code storage block contains more buffer units and has a stronger buffering capacity. The LDPC decoder of claim 2, wherein the number of the computing engines disposed on one side and the other side of the parity check code storage block is the same. The LDPC decoder of claim 1, wherein each of the column group storage blocks includes 6 precision bits. The LDPC decoder of claim 7 , wherein the 6 precision bits include 1 sign bit and 5 value bits. The LDPC decoder of claim 1, wherein the number of the row group storage blocks is 24. The LDPC decoder of claim 1, wherein the number of rows included in each row group ranges from 1 to 4. The LDPC decoder of claim 1, wherein each of the rows is assigned to only a single row group.