TWI898775B - Ldpc decoder and minimum value searching method - Google Patents

Abstract

An LDPC decoder and a minimum value searching method are provided. The LDPC decoder includes a storage unit and one or more computing engine. The storage unit stores an LDPC matrix. The computing engine performs an LDPC decoding algorithm to estimate a decoding result for a codeword based on the LDPC matrix. The computing engine includes a minimum value searching unit to output a minimum value searching result based on a plurality of input values when the LDPC decoding algorithm performs a minimum value searching operation.

Description

LDPC decoder and minimum value search method

The present invention relates to communication decoding technology, and more particularly to an LDPC decoder and a minimum value search method.

Low-Density Parity-Check (LDPC) coding is used as an error-correcting code in Passive Optical Networks (PONs), Ethernet, and other data communication protocols because its error correction capability is very close to the theoretical maximum, known as the Shannon limit. A common algorithm used for decoding and error correction is the min-sum algorithm.

One way to implement a min-sum engine is to compare the current minimum value with a value to be compared, and then iterate over all the values to be compared. However, this approach (using linear minimum comparison/multiplexers) is quite slow because each comparison requires a comparator and a multiplexer to complete the calculation, thus requiring a number of comparators and multiplexers that scales linearly with the number of values to be compared.

Another way to implement a min-sum engine is to compare every two values to find a minimum (the first level), then compare every other pair of these minimums again (the second level), and so on, reducing the tree to the final result. While this method (using a tree-like minimum comparison/multiplexer) is faster than the first method (using a linear minimum comparison/multiplexer), the tree structure requires a number of layers equal to the log-base-2 number of values to be compared. For example, 17 to 32 values to be compared would require five layers of comparators and multiplexers. Pipelining between layers does not speed up the operation, as the final result must be used in the next round of calculations. If the tree is pipelined, the first stage of the tree must wait until the last stage of the tree completes its first iteration before it can start its second iteration. Therefore, the overall computation time remains the same.

In view of this, an embodiment of the present invention proposes an LDPC decoder and a method (using linear minimum comparison/multiplexer) that performs calculations through a flat structure to increase the calculation speed.

In light of this, one embodiment of the present invention proposes an LDPC decoder and LDPC decoding method (using a flattened min-sum computation engine). This method reduces overall computation time by flattening all values in a set into one-hot vectors, selecting all values at once and prioritizing decoding the minimum value. This solves the problem of excessively long computation time caused by iteratively comparing two values using a linear or tree-like approach.

The LDPC decoder includes a storage unit and at least one computation engine. The storage unit stores an LDPC matrix. The computation engine executes an LDPC decoding algorithm to estimate a decoding result for a codeword based on the LDPC matrix. The computation engine includes a minimum search unit that outputs a minimum search result based on multiple input values when the LDPC decoding algorithm performs a minimum search operation. The minimum search unit performs the following operations: converting the input values into a plurality of Sudoku vectors, each Sudoku vector having a plurality of Sudoku bits, wherein the Sudoku bits in the same Sudoku vector correspond to non-repeating one-hot bit indices; creating a plurality of first vectors, each of which corresponds to a target bit index in the one-hot bit indices, and each of which represents the result of performing or operating on the one-hot bits at the target bit indices in the one-hot vectors; and decoding the first vectors, based on the one-hot bit indices, from low bit to high bit, to obtain a minimum value. The minimum value is the target bit index corresponding to the first first vector whose value is "1", wherein the minimum search result includes the minimum value.

A minimum search method is performed by an LDPC decoder and is suitable for outputting a minimum search result based on multiple input values. The minimum search method includes: converting these input values into multiple Sudoku vectors, each of which has multiple Sudoku bits, and these unique bits in the same Sudoku vector correspond to non-repeating one-hot bit indices; creating multiple first vectors, each of which corresponds to a target bit index in these one-hot bit indices, and each first vector represents the result of performing or operating on these one-hot bits at the target bit indices in these one-hot vectors; and first decoding these first vectors from low bit to high bit based on these one-hot bit indices to obtain a minimum value. This minimum value is the target bit index corresponding to the first first vector whose value is "1", and the minimum search result includes this minimum value.

According to some embodiments of the present invention, an LDPC decoder and a minimum search method can quickly find the minimum value, the second minimum value, and/or the minimum value after offset processing through a flat design, which can meet the efficient decoding requirements of high-speed communication.

Referring to Figure 1, a schematic diagram of the architecture of an LDPC decoder 100 according to an embodiment of the present invention is shown. LDPC decoder 100 includes a storage unit 110 and a flattened minimum sum calculation engine 120 for executing an LDPC decoding method. Storage unit 110 stores an LDPC matrix 200 (as shown in Figure 2). Flattened minimum sum calculation engine 120 is a block having multiple computation engines 130. After obtaining a codeword 140, computation engines 130 execute an LDPC decoding algorithm to estimate a decoding result 150 for codeword 140 based on LDPC matrix 200. A minimum search unit 131 in the computation engine 130 flattens all values in the set into a one-hot vector 300 (as shown in FIG5 ) to select and decode all values at once to find the minimum value, rather than iteratively comparing two values in a linear or tree-like manner.

Refer to Figure 2, which is a partial schematic diagram of an LDPC matrix 200 according to an embodiment of the present invention. Taking the LDPC matrix 200 used in 25G PON (Passive Optical Network) as an example, LDPC matrix 200 is a 17664x3072 sparse matrix composed of 69x12 arrays of 256x256 sub-matrices. Each grid in Figure 2 represents a sub-matrix. These sub-matrices are either zero matrices or shifted identity matrices. The blank grids in LDPC matrix 200 shown in Figure 2 represent zero matrices. The numbered cells in LDPC matrix 200 shown in Figure 2 represent a shifted unit matrix, and the numbers indicate the amount of shift within the unit matrix. For example, a "0" indicates that the sub-matrix is the unit matrix, while a "5" indicates that the sub-matrix is a unit matrix with each row of the sub-matrix circularly shifted to the right by five elements. Figure 2 merely provides a specific example to illustrate LDPC matrix 200 according to one embodiment of the present invention. LDPC matrix 200 is not limited to the number of rows and columns shown in this example, nor is it limited to the positions and shift amounts of the sub-matrices shown in this example.

Each row of LDPC matrix 200 is considered a variable node, corresponding to each bit of codeword 140. Each column of LDPC matrix 200 is considered a check node, each corresponding to a check equation. A "1" element in LDPC matrix 200 indicates that the check node in its row is linked to the variable node in its row. The LDPC decoding algorithm is based on an iterative belief propagation algorithm, where variable nodes and check nodes communicate updated information through links.

Refer to Figure 3, which shows a flow chart of an LDPC decoding algorithm according to an embodiment of the present invention. Step S31 is an initialization step, which initializes the information of the variable node and the check node. Step S32 is a check node update step, in which the check node is updated based on the information of its linked variable node. Step S33 is a variable node update step, in which the variable node is updated based on the information of its linked check node. Step S34 is a termination determination step, which determines whether the termination condition is met. If so, the process ends; if not, the process returns to step S32 and continues to the next iteration.

Refer to Equations 1 and 2 for the initialization equations of step S31. Variable nodes perform information initialization according to Equation 1, and verification nodes perform information initialization according to Equation 2. Here, i represents the number of iterations. N is the total number of variable nodes, and M is the total number of verification nodes. n represents the number of the nth variable node, and m represents the number of the mth verification node. _Nm represents the set of all variable nodes connected to the mth verification node. _Mn represents the set of all verification nodes connected to the nth variable node. Represents the information passed from the nth variable node to the mth verification node in the kth iteration. represents the information transmitted by the mth check node to the nth variable node in the kth iteration. _In represents the intrinsic information of the nth variable node, which is used to express the posterior probability that the bit of codeword 140 corresponding to this variable node is 1 or 0. ∀ represents any, and ∈ represents belongs to. In some embodiments, the intrinsic information is a log-likelihood ratio (LLR).

(Formula 1)

(Formula 2)

Refer to Equation 3, which is the update equation for the check node in step S32. Here, π is the product symbol. sgn() is a sign function that returns 0, 1, or -1, depending on whether the value within the function is 0, positive, or negative. min() is the minimum function. _Nm\n represents the set of all variable nodes connected to the mth check node, excluding variable node n.

(Formula 3)

Refer to Equation 4, which is the update equation for the variable node in step S33. Here, ∑ is the summation symbol. _Mn\m represents the set of all verification nodes connected to the nth variable node, excluding verification node m.

(Formula 4)

In step S34, a hard decision is performed to decode and determine whether the termination condition is met. If the condition is met, the process ends. The termination condition is that the decoding result 150 is correct or the number of iterations exceeds the threshold. Refer to Equation 5 and Equation 6, which are the calculation formulas for the hard decision. Among them, Equation 5 calculates the posterior probability of each variable node. Based on the calculation result of Equation 5, Equation 6 is used to determine the bit value z _n corresponding to each variable node, and the decoding result 150 (sequence z ₁ , z ₂ , …, z _n ) is obtained. Equation 7 is used to confirm whether the decoding result 150 is correct (if it satisfies Equation 7, it is correct), where H represents the LDPC matrix 200, Represents the transpose of the decoded result 150 (sequence z ₁ , z ₂ , …, z _n ).

(Formula 5)

(Formula 6)

(Equation 7)

According to the above description (such as Equation 3 and Equation 4), the iterative process will calculate The sum of information ( ) and finds the minimum value therefrom. Therefore, the LDPC decoding algorithm described herein is called the min-sum algorithm. During the check node update operation (Equation 3), a minimum search operation is required to find the minimum value within the intrinsic information corresponding to the variable node set N _m\n . Therefore, as shown in Figure 1, each computation engine 130 includes a minimum search unit 131. When the LDPC decoding algorithm reaches a minimum search operation, these minimum search units 131 execute a minimum search process based on multiple input values (here, the intrinsic information corresponding to the variable node set N _m\n ) and output a minimum search result. In some embodiments, each input value is the intrinsic information corresponding to the variable node (e.g., the log-likelihood ratio).

In some embodiments, the number of computation engines 130 is determined by the number of rows in the sub-matrix. As shown in the example of FIG. 2 , there are 256 computation engines 130. Each computation engine 130 corresponds to a row (check node) in the sub-matrix and performs the corresponding update operation (Equation 3). Therefore, these computation engines 130 can process operations on 256 rows (also called one layer) in parallel at a time. After processing all layers of the LDPC matrix 200 (12 layers as shown in FIG. 2 ), one iteration of the check node update is completed. There are multiple minimum search units 131 to process the minimum search process corresponding to each row in the same layer of the LDPC matrix 200 in parallel. That is, a minimum value search unit 131 processes a minimum value search operation corresponding to a row.

Similarly, in some embodiments, the flattened minimum sum calculation engine 120 further includes other calculation engines (not shown in FIG. 2 ) to process all variable node updates in parallel in batches, which will not be repeated here.

In some embodiments, multiple rows in the LDPC matrix 200 are combined into a row group. For example, as shown in FIG2 , rows 67 and 68 have at most one non-zero matrix in each horizontal column, so they can be combined into a row group. Similarly, rows 65 and 66 can also be combined into another row group. Due to the sparse nature of the LDPC matrix 200, the number of rows can be significantly reduced after being combined into row groups. Generally speaking, after being combined into row groups, the number of rows can be reduced to about 20 (mid-twenties), for example, 23 to 27. In this way, the number of input values to be executed for the minimum search operation can be reduced, but the present invention does not require the number of input values to be less than 30. Because a shifted unit matrix only has one "1" in each column, each row group corresponds to at most one input value for a minimum search unit 131. That is, the number of input values processed by the minimum search unit 131 in a single minimum search operation is at most equal to the number of row groups. In some embodiments, the number of input values processed by a minimum search unit 131 is in the range of 23 to 69.

Referring to FIG4 , there is a flowchart (I) of the minimum value search algorithm of an embodiment of the present invention. Step S41 is a one-hot vector 300 conversion step, which converts multiple input values G into one-hot vectors 300, as shown in FIG5 . FIG5 is a schematic diagram of the one-hot vector 300 conversion of an embodiment of the present invention. In some embodiments, the bit width of each input value G is 4 bits or 5 bits to achieve a balance between error correction capability and logic quantity. FIG5 is illustrated using 24 5-bit input values G[0]~G[23], but the number of input values G and their bit number are not limited to this. Each one-hot vector 300 has a plurality of bits (hereinafter referred to as "one-hot bits 310"). These one-hot bits 310 in the same one-hot vector 300 correspond to non-repeating one-hot bit indices 400. Here, the one-hot bit indices 400 are "0" to "31", which are equivalent to the numbers represented in the one-hot vector 300. Taking the input value G[0] as an example, it is converted into a one-hot vector 300 composed of one-hot bits 310 such as F[744], ...F[168], F[144], F[120], F[96], F[72], F[48], F[24], and F[0]. The one-hot bits 310 marked with a solid bold frame have a value of 1, and the one-hot bits 310 not marked with a bold frame have a value of "0". For example, the value of the input value G[4] is "6". After it is converted into the one-hot vector 300, the value of the one-hot bit 310 of F[148] is "1", and the one-hot bit index 400 corresponding to the one-hot bit 310 of F[148] is "6".

Refer to Code 1, which is an implementation of the one-hot vector 300 conversion. The input values G[0]-G[23] are compared with the one-hot bit index 400 one by one. If the two are the same, the corresponding one-hot bit 310 is set to "1".

Code 1: F[0] = (G[0] == 0); F[1] = (G[1] == 0); … F[23] = (G[23] == 0); F[24] = (G[0] == 1); … F[767] = (G[23] == 31);

It should be noted that although Figure 5 expresses the relationship between the input value G and the unique-hot vector 300 in the form of a two-dimensional array, F[0]~F[767] is actually a one-dimensional array, that is, a flattened vector. For the convenience of subsequent explanation, "0"~"767" are defined here as flattened bit indices. These flattened bit indices correspond one-to-one to the unique-hot bits 310 of the unique-hot vector 300. The flattened vector has a plurality of connected sequences 500, each sequence 500 corresponding to each row shown in Figure 5. Each sequence 500 includes the unique bits 310 at the same unique-hot bit index 400 in these unique-hot vectors 300. For example, the sequence 500 shown in FIG5 includes the unique bits 310 (F[96] to F[119]) corresponding to the unique bit index 400 of 4 in each unique-hot vector 300. The unique bits 310 included in these sequences 500 are arranged in the same arrangement order. As shown in FIG5, the unique bits 310 included in these sequences 500 are arranged in order from top to bottom, and the arrangement order of these sequences 500 is consistent with the index order of the input values G[0] to G[23]. These sequences 500 are arranged in ascending order according to their corresponding unique bit index 400. For example, the sequence 500 including the unique bits 310 from F[0] to F[23] has a corresponding unique bit index 400 of “0”; the sequence 500 including the unique bits 310 from F[24] to F[47] has a corresponding unique bit index 400 of “1”, and so on.

Refer to Figures 4, 5 and Code 2. Step S42 is to create a plurality of first vectors. Each first vector corresponds to one of these unique bit indices 400 (hereinafter referred to as "target bit index") without duplication. For example, the unique bit index 400 corresponding to the first vector First_vector[0] is "0", the unique bit index 400 corresponding to the first vector First_vector[1] is "1", and so on. Each first vector presents the result of performing an OR operation between these unique bits 310 at the target bit index in these unique vectors 300. For example, the first vector First_vector[0] presents the result of the OR operation between the unique bits 310 (F[0]~F[23]) whose unique bit index 400 is 0. Therefore, if a first vector is “1”, it means that there is at least one one-hot vector 300 whose one-hot bit 310 corresponding to the target bit index is “1”.

Code 2: First_vector[0] = F[0] || F[1] || … F[23]; First_vector[1] = F[24] || F[25] || … F[47]; … First_vector[31] = F[744] || F[755] || … F[767]

Refer to Figures 4 and 5, along with Code 3. Step S43 prioritizes decoding the minimum value from these first vectors. Specifically, based on the unique bit indices 400, from low to high bits (here, from "0" to "31"), the minimum value is prioritized. The minimum value is the target bit index corresponding to the first first vector whose value is "1." For example, in Figure 5, the unique bit index 400 corresponding to the first first vector whose value is "1" is "1," so the minimum value included in the minimum search result is "1."

Code 3: foreach bit (0..31) last if(First_vector[bit]); Min_value = bit;

Refer to Figures 5, 6 and program code 4. Figure 6 is a flow chart (II) of the minimum value search algorithm of an embodiment of the present invention. This process is used to find out which of the input values G is the aforementioned minimum value. In step S61, a second vector is established. Each second vector corresponds to one of the unique hot vectors 300 (hereinafter referred to as the "target unique hot vector") without duplication. Each second vector presents the result of executing or operating between multiple judgment results generated by performing a logical judgment on each unique hot bit 310 in the target unique hot vector. Among them, the logical judgment is the intersection of a first condition and a second condition. The first condition is that the unique hot bit 310 subjected to the logical judgment is "1". The second condition is that, in the flattened vector, all the unique bits 310 at flattened bit indices smaller than the flattened bit index of the unique bit 310 being logically judged are "0". Taking the second vector Second_vector[0] as an example, a logical judgment is performed on each unique bit 310 (F[0], F[24], F[48], ..., F[744]) in the corresponding unique vector 300. For example, for F[24], the first condition is to judge whether F[24] is "1", and the second condition is to judge whether F[23:0] are all "0". If both conditions are true, it means that F[24] is the first unique bit 310 in F[24:0] that is "1". The input value G[0] corresponding to the unique-hot vector 300 containing this unique bit 310 is the input value with the minimum value. To add, since there is no flattened bit index smaller than the flattened bit index of F[0], only the first condition is determined for F[0]: whether F[0] is 1.

Code 4: Second_vector[0] = F[0] || F[24] && (F[23:0]==0) || F[48] && (F[47:0]==0)… F[744]&&(F[743:0]==0); Second_vector[1] = F[1] || F[25] && (F[24:0]==0) || F[49] && (F[48:0]==0)… F[745]&&(F[744:0]==0); Second_vector[2] = F[2] || F[26] && (F[25:0]==0) || F[50] && (F[49:0]==0)… F[746]&&(F[745:0]==0); … Second_vector[23] = F[23] || F[47]&&(F[46:0]==0)|| F[71] &&(F[70:0]==0)…F[767]&&F[766:0]==0;

Refer to Figures 5 and 6, and Code 5. Step S62 preferentially decodes the index of the input value G corresponding to the minimum value from these second vectors (hereinafter referred to as the "input value index"), so that this input value index is included in the minimum value search result. Specifically, based on the arrangement order of the unique bits 310 in sequence 500 (i.e., the arrangement order of the input value G), the input value index corresponding to the minimum value is preferentially decoded from these second vectors. The input value index is a sequence index corresponding to the arrangement order of the second vector for which the first logical judgment is true. As shown in Figure 5 , the unique bit 310 of F[24] is the minimum value. Therefore, after step S61 , the logical judgment of the second vector Second_vector[0] is true (indicated by "1"), and this is the first second vector for which the logical judgment is true. Therefore, the input value index of the minimum value is "0" (i.e., the index value of this second vector is also the same as the corresponding input value index).

Code 5: foreach bit (0..23) last if(Second_vector[bit]); Min_index = bit;

In some embodiments, the LDPC decoding algorithm uses a variation of the aforementioned minimum-sum algorithm, such as a normalized min-sum algorithm, an offset min-sum algorithm, etc., which uses not only the minimum value but also the second minimum value. In one example, when the input values G[2] and G[5] are both "3" and the other input value G is "4", the minimum value is "3" and the second minimum value is also "3". In another example, when the input value G[1] is "2", when the input value G[0] is "4", and the other input value G is greater than "4", the minimum value is "2" and the second minimum value is "4". The following describes how to obtain the second minimum value through the aforementioned flattened vector to provide a minimum value search result including the second minimum value.

Referring to Figures 5, 7, and Program Code 6, Figure 7 is a flowchart of the second minimum search algorithm of an embodiment of the present invention. In step S71, a plurality of third vectors are established. Each third vector corresponds to a unique bit index 400 (i.e., a target bit index) without duplication. The third vector represents the intersection of the multiple results generated by performing a logical judgment on the unique bit 310 at the target bit index of the unique bit vector 300. The logical judgment is the intersection of a third condition and a fourth condition. The third condition is that the unique bit 310 subjected to the logical judgment is "1." The fourth condition is that, in the flattened vector, the unique bits 310 at the flattened bit indices smaller than the flattened bit index of the unique bit 310 being logically judged are not all "0". Taking the third vector Third_vector[2] as an example, a logical judgment is performed on each unique bit 310 (F[48]~F[71]) in the unique vector 300 at its corresponding unique bit index 400 ("2"). For example, for F[50], the third condition is to judge whether F[50] is "1", and the fourth condition is to judge whether F[49:0] are not all "0". If both conditions are true, it means that F[49] in F[50:0] is the second unique bit 310 that is "1". In addition, since there is no flattened bit index smaller than the flattened bit index of F[0], the judgment of F[0] is omitted in the third vector Third_vector[0].

Code 6: Third_vector[0] = F[1] &&!(F[0]==0) || F[2] && !(F[1:0]==0) || … F[23] &&!(F[22:0]==0); Third_vector[1] = F[24] && !(F[23:0]==0) || F[25] && !(F[24:0]==0) … F[47] &&!(F[46:0]==0); … Third_vector[31] = F[744] && !(F[743:0]==0) || F[745] && !(F[744:0]==0) || … F[767] &&!(F[766:0]==0);

Combined reference to Figures 5, 7 and Code 7. Step S72 is to preferentially decode the second minimum value from these third vectors. Specifically, based on these unique bit indices 400, from low bit to high bit, these third vectors are preferentially decoded to obtain the second minimum value. This second minimum value is the target bit index corresponding to the third vector whose first logical judgment is true. As shown in Figure 5, the unique bit 310 of F[50] is the second minimum value, so after the aforementioned step S71, the logical judgment of the third vector Third_vector[2] is true (indicated as "1"), and it is the third vector whose first logical judgment is true. Therefore, the second minimum value is "2" (that is, the corresponding target bit index is also the same as the index value of this third vector).

Code 7: foreach bit (0..31) last if(Third_vector[bit]); Third_min_value = bit;

In some embodiments, variations of the min-sum algorithm (such as the compensated min-sum algorithm described above) use an offset to determine the minimum value. That is, the minimum value included in the minimum search result is the offset-processed minimum value. The following describes how to apply the offset to the minimum value found above.

Referring to Figures 5, 8, and Codes 8-10, Figure 8 is a flowchart (3) of a minimum search algorithm according to an embodiment of the present invention. After obtaining the first vector in step S43, the offset processing of steps S44 through S46 is performed. The offset is set to 1 as an example, but the present invention is not limited to this.

In step S44, for the first vector (here, First_vector[1:0]) whose unique bit index 400 is below the offset, the first value (bit_no_offset) is first decoded, as shown in code 8. The first value (bit_no_offset) is the unique bit index 400 corresponding to the first vector whose value is "1". If the first vector First_vector[0] is "1", the first value (bit_no_offset) is "0". If the first vector First_vector[0] is "0" and the first vector First_vector[1] is "1", the first value (bit_no_offset) is "1".

Code 8: foreach bit_no_offset (0..1) last if(First_vector[bit_no_offset]);

In step S45, for the other first vectors of unique bit indexes 400, that is, the first vectors whose unique bit indexes 400 are not below the offset (here, First_vector[31:2]), the second value (bit_offset) is preferentially decoded, as shown in Code 9. The second value (bit_offset) is the unique bit index 400 corresponding to the first first vector whose value is "1" minus the offset. For example, when the first vector First_vector[2] is "0" and the first vector First_vector[3] is "1", the second value (bit_offset) is 2.

Code 9: foreach bit_offset (1..30) last if(First_vector[bit_offset+1]);

In step S46 , an OR operation is performed on the first vector (First_vector[1:0]) whose unique bit index 400 is below the offset. If the operation result is "1," indicating that the minimum value occurs in these first vectors, the first value is used as the minimum value after the offset processing. If the operation result is "0," indicating that the minimum value occurs in another first vector, the second value is used as the minimum value after the offset processing.

Code 10: Min_value_with_offset = (First_vector[0] || First_vector[1]) ? bit_no_offset : bit_offset;

Compared to using a more logical approach as in code 11, FIG8 performs offset processing based on the first vector created by the flattened vector, thereby utilizing a flattened structure to improve processing speed.

Code 11: Min_value_with_offset = Min_value > 1 ? Min_value – 1 : Min_value;

Some embodiments of the present invention propose an LDPC decoder and minimum search method that can quickly find the minimum, second minimum, and/or offset minimum through a flattened design without requiring iterative comparisons in a linear or tree-based manner, thereby meeting the efficient decoding requirements of high-speed communications.

100: LDPC decoder 110: Storage unit 120: Flattened minimum sum calculation engine 130: Calculation engine 131: Minimum search unit 140: Codeword 150: Decoded result 200: LDPC matrix 300: One-hot vector 310: One-hot bit 400: One-hot bit index 500: Sequence G, G[0]~G[23]: Input value S31~S34: Steps S41~S46: Steps S61~62: Steps S71~72: Steps

Figure 1 is a schematic diagram of the architecture of an LDPC decoder according to an embodiment of the present invention. Figure 2 is a partial schematic diagram of an LDPC matrix according to an embodiment of the present invention. Figure 3 is a flow chart of the LDPC decoding algorithm according to an embodiment of the present invention. Figure 4 is a flow chart (I) of the minimum search algorithm according to an embodiment of the present invention. Figure 5 is a schematic diagram of the unique-hot vector conversion according to an embodiment of the present invention. Figure 6 is a flow chart (II) of the minimum search algorithm according to an embodiment of the present invention. Figure 7 is a flow chart of the second minimum search algorithm according to an embodiment of the present invention. Figure 8 is a flow chart (III) of the minimum search algorithm according to an embodiment of the present invention.

S41~S43: Steps

Claims (11)

A minimum search method is suitable for outputting a minimum search result based on multiple input values. The minimum search method includes: converting the input values into multiple Sudoku vectors, each of the multiple Sudoku vectors having multiple Sudoku bits, wherein the unique bits in the same Sudoku vector correspond to non-repeating one-hot bit indices; establishing multiple first vectors, each of the first vectors non-repeatingly corresponding to a target bit index in the one-hot bit indices, and each of the first vectors presenting the result of performing or operating between the unique bits at the target bit index in the one-hot vectors; and preferentially decoding the first vectors from low bit to high bit based on the unique bit indices to obtain a minimum value, wherein the minimum value is the target bit index corresponding to the first first vector whose value is "1", wherein the minimum search result includes the minimum value. The minimum search method as described in claim 1, wherein the one-hot vectors are in a flattened vector, the flattened vector has a plurality of flattened bit indices, the flattened bit indices correspond one-to-one to the one-hot bits of the one-hot vectors, the flattened vector includes a plurality of connected sequences, each of the sequences includes the one-hot bits at the same one-hot bit index in the one-hot vectors, the one-hot bits included in the sequences are arranged in the same arrangement order, and the sequences are arranged in ascending order according to their corresponding one-hot bit indices. The minimum value search method as described in claim 2 further includes: establishing a plurality of second vectors, wherein each of the second vectors corresponds to a target one-hot vector among the one-hot vectors without duplication, and each of the second vectors presents a result of executing or operating between a plurality of judgment results generated by performing a logical judgment on each one-hot bit in the target one-hot vector, wherein the logical judgment is the intersection of a first condition and a second condition, and the first condition is the one-hot bit for which the logical judgment is performed. is "1", the second condition is that the unique bits at the flattened bit indices smaller than the flattened bit index of the unique bit for which the logical judgment is performed in the flattened vector are all "0"; and according to the arrangement order, the second vectors are preferentially decoded to obtain an input value index corresponding to the minimum value, the input value index being a sequence index of the arrangement order corresponding to the first second vector for which the logical judgment is true, wherein the minimum value search result also includes the input value index. The minimum value search method as described in claim 2 further includes: establishing a plurality of third vectors, wherein each of the third vectors corresponds to the target bit index in the one-hot bit indexes without duplication, and the third vector presents the intersection of a plurality of results generated by performing a logical judgment on the one-hot bit at the target bit index of the one-hot vectors, wherein the logical judgment is the intersection of a third condition and a fourth condition, and the third condition is that the one-hot bit on which the logical judgment is performed is "1". ", the fourth condition is that the unique bits at the flattened bit indices smaller than the flattened bit index of the unique bit for performing the logical judgment in the flattened vector are not all "0"; and according to the unique bit indices, from low bit to high bit, a second minimum value is preferentially decoded for the third vectors, and the second minimum value is the target bit index corresponding to the third vector for which the first logical judgment is true, wherein the minimum value search result also includes the second minimum value. The minimum value search method as described in claim 1 further includes: performing an offset processing on the minimum value, wherein the minimum value included in the minimum value search result is the minimum value after the offset processing. A minimum value search method as described in claim 5, wherein the offset processing includes: for the first vectors whose unique bit index is below an offset, preferentially decoding a first value, the first value being the unique bit index corresponding to the first first vector whose value is "1"; for the other first vectors, preferentially decoding a second value, the second value being the unique bit index corresponding to the first first vector whose value is "1" minus the offset; and executing or operating the first vectors whose unique bit index is below the offset, wherein, if the operation result is "1", the first value is used as the minimum value after the offset processing, and if the operation result is "0", the second value is used as the minimum value after the offset processing. The minimum search method of claim 1, wherein each of the input values is a log-likelihood ratio. The minimum value search method as described in claim 1, wherein each of the input values is 4 bits or 5 bits. The minimum value search method as described in claim 1, wherein the number of the input values is in the range of 23 to 69. The minimum value search method as claimed in claim 1, wherein the minimum value search method is executed by a plurality of minimum value search units respectively, and parallel processing is performed corresponding to each column at the same level in an LDPC matrix. An LDPC decoder performs the minimum search method as described in any one of claims 1 to 10.