TWI867624B - Method for improving LDPC decoder parallelism by dividing LDPC code - Google Patents

Abstract

To use an LDPC layer decoder, an LDPC H matrix is converted into instructions readable by the decoder, and an order of the circulants of the matrix is processed to enhance decoding performance. To this end, at first, an H_ab generator is used to preprocess the matrix to achieve high throughput. Secondly, a circulant scheduler is used to optimize circulant order to implement parallelization and further enhance hardware performance.

Description

Method for improving LDPC decoder parallelism by splitting LDPC codes

The present invention relates to LDPC (low density parity check) min-sum decoding, and more particularly to a method for improving the parallelism of LDPC decoders by segmenting LDPC codes.

Usually, when processing matrices, the minimum sum decoder uses row-based entries. For example, the LDPC minimum sum decoding matrix shown in Figure 1 is processed row-by-row. The data flow in the hardware also follows this row-based rule, and a row of data to be read uses the same memory space as the previous row of data to be written.

The typical way to convert LDPC matrices into hardware instructions is in matrix order. However, read before write conflicts often occur between adjacent columns. To resolve conflicts, the hardware must pause the reading of an element until the previous element in the same column is processed and written back to memory. This conflict resolution behavior causes a lot of delays.

In view of the problems in the prior art, the purpose of the present invention is to provide a method for efficiently segmenting LDPC codes to improve the parallelism of LDPC decoders.

To achieve the purpose, in this method of improving the parallelism of LDPC decoders by segmenting LDPC codes, the entire matrix is first divided into several segments. Each column in the matrix is randomly assigned to a segment in sequence, and the current demand of each segment is used as a weight during the assignment. After all columns are assigned, the weighted swap score is calculated. If this weighted swap score is less than the weighted swap score stored earlier, it is updated to this weighted swap score and the swap assignment method is recorded. It is determined whether the number of swap assignments of the matrix reaches the maximum recurrence number. If the number of swap assignments of the matrix does not reach the maximum recurrence number, the above step of dividing the entire matrix into several segments is returned. If the number of matrix swaps has reached the maximum recurrence number, the reorganized matrix and reorganized vector are generated according to the swap distribution method with the minimum weighted swap score recorded above.

S10: Swap the rows of the matrix to produce a different row order

S11: Calculate the number of conflicts between any two columns

S12: Select a row in order as the first row in the sequence

S13: Select the row with the least conflicts and has not been used as the next row

S14: Complete a row sequence?

S15: Update the column order with the minimum total number of conflicts

S16: Have all possible column sequences starting with the same column been explored?

S17: Start from the current row and select another candidate to be the next row

S18: Has every row been the first in the column sequence?

S20: Select a column order in sequence

S30: Swap columns and split the matrix

S31: Process each column of the original matrix in sequence

S32: Calculate weighted swap scores

S33: Has the number of matrix swaps reached the maximum number of recursions?

S34: Generate reorganization matrix and reorganization vector

S40: Scheduling elements in each core

S41: Calculate conflict markers and risk scores

S42: Sort elements by risk score, from high to low

S43: Read non-zero elements from memory

S44: Write the processed non-zero element data into memory

S45: Complete the entire matrix?

S50: Generate multiple lines of CMEM instructions

S55: Find the minimum number of CMEM instruction lines

S60: Reached the upper limit of repetition times?

S70: Have all row sequences been processed?

S75: Generate a scheduling file according to the CMEM instruction and add CRC32 check bits

S80: Use the checker and C model to test the scheduling file

[Figure 1] shows an LDPC matrix;

[Figure 2] Block diagram of an LDPC minimum sum decoding system;

[Figure 3] Flowchart of the method of the present invention for rearranging the LDPC decoding matrix to shorten the LDPC minimum sum decoding delay;

[Figure 4] is a flow chart of the steps of the method of Figure 3 in reverse order;

[Figure 5] shows a way to partition the columns of the matrix in Figure 1;

[Figure 6] is a flow chart of the steps of swapping columns in the method of Figure 3;

[Figure 7] Stage (I) of presenting the allocation column;

[Figure 8] Stage (II) of presenting the allocation column;

[Figure 9] Stage (III) of presenting the allocation column;

〔Figure 10〕The stage of matrix calculation of conflict markers and risk scores (I);

〔Figure 11〕The stage of matrix calculation of conflict markers and risk scores (II);

[Figure 12] Flowchart of the scheduling steps of the method shown in Figure 3;

〔Figure 13〕The stage of selecting elements from the reorganized matrix (I).

〔Figure 14〕The stage of selecting elements from the reorganized matrix (II).

〔Figure 15〕The stage of selecting elements from the reorganized matrix (III).

[Figure 16] The stage of selecting elements from the reorganized matrix (IV).

The following reference figures further illustrate a preferred embodiment of the method of rearranging the LDPC decoding matrix to shorten the LDPC minimum sum decoding delay. To facilitate understanding of the present invention, the same symbols are used to indicate the same elements.

Referring to FIG. 2 , a decoding system includes hardware (in the lower dashed box) and the method of the present invention (in the upper dashed box). The hardware (e.g., LDPC minimum sum decoder) processes matrices on a column basis. The hardware includes a memory and a plurality of cores. The memory stores a row of circulants. Each core is a processor.

When processing a matrix in hardware, in order to solve the problem of sharing memory space among the elements (circulants) in the columns of the matrix and improve the parallel speed, the method of the present invention includes a matrix reorganization program ( _Hab generator) and an element scheduling program (circulant scheduler). Each element is a circulant, that is, a smaller matrix.

The matrix reshuffling procedure preprocesses an original matrix (e.g., a matrix of LDPC) to produce a reshuffled matrix (with fields swapped) and a reshuffled vector (indicating the order of the swapped fields). The preprocessing includes splitting, reordering, and combining. Under a feasible number of splits, this method can split the original matrix into two or more smaller matrices. In this way, the matrix reshuffling procedure preprocesses the original matrix to achieve high yield.

The element scheduler uses the reorganized matrix and reorganized vector to generate a CMEM file. Here, the elements in each core are split and reordered to achieve better performance. In each core, the element scheduler optimizes the element order for parallelization. In this way, each core and the entire system have less idle time, which enhances hardware performance.

Referring to Figure 3, steps S10, S20 and S30 constitute a matrix reorganization procedure.

In step S10, the positions of the rows of the matrix are swapped to generate row sequences of different permutations.

In step S20, select one from these columns in sequence.

In step S30, the matrix is divided into different cores by swapping the columns according to the selected row order, and the results are integrated into a reorganized matrix ( _Hab matrix).

Steps S40, S50 and S55 constitute the element scheduling procedure.

In step S40, the elements in each core are scheduled. In other words, all cores execute step S40 simultaneously.

In step S50, multiple lines of CMEM instructions are generated.

In step S55, find the minimum number of CMEM instruction lines.

According to a row order, swapping the position of the column in different ways means swapping the column to different cores, and after being arranged by the element scheduler, it finally leads to different combinations and numbers of CMEM instructions. Therefore, executing steps S30, S40, S50, S55 and S60 to reach the maximum number of loops to find the best result under a specific row order. Executing steps S30, S40, S50, S55, S60 and S70 to find the best result of all row orders. The best result is the minimum number of CMEM instruction lines.

In step S75, the final decoder scheduling file is generated according to the above CMEM instruction, and a CRC32 check bit is added at the end of the file.

In step S80, a checker and C model (decoder model written in C language) are used to execute the decoder scheduling file to complete the verification test.

In step S10, the columns are swapped. In other words, the columns of the original matrix are rearranged to reduce the read-before-write conflicts caused by the columns. This helps the element scheduler to arrange the elements in step S40. Referring to FIG. 4, step S10 is subdivided into steps S11 to S18.

In step S11, when elements are in the same column of the original matrix, if they are in adjacent columns (e.g., adjacent 2 columns, adjacent 3 columns, adjacent 4 columns, ...), they may have a read-before-write conflict. Calculate the number of conflicts between any two columns and create a conflict table as follows. Based on this conflict table, subsequent steps can be quickly performed.

Refer to Table 1, which describes the situation of two columns. There are no conflicts between columns 1 and 2. There are 15 conflicts between columns 1 and 3. There are 2 conflicts between columns 2 and 3. The conflict table helps to find the next column with the minimum number of conflicts.

In step S12, to find all the row sequence combinations, select a row from the original matrix in order, for example, row K as the first row sequence.

In step S13, for the current row (e.g. row K), select the row with the least conflicts and available as the next row. "Minimum conflicts" means having the minimum number of conflicts. "Available" means not included in the current or previously generated row sequence (from step S17 back to step S13). There may be more than one row (e.g. row L and row M) with the minimum number of conflicts, and these rows are the following candidates. Select a row (e.g. row L) from these candidates to be the next row.

In another embodiment, "minimum conflict" can be replaced by the range of minimum conflict number + n. This can find more possibilities but consumes more time. In addition, if there are too many candidates, a random selection mechanism can be used, which helps reduce processing time and find a good row order.

In step S14, check whether a row sequence is completed (this row sequence covers all rows). If so, go to step S15, otherwise return to step S13.

In step S15, the column sequence with the minimum total conflict number is updated. To this end, the total conflict number of the current column sequence is compared with the total conflict number of the earlier stored column sequence. If the current total conflict number is greater than the earlier total conflict number, the earlier stored column sequence is retained. If the current total conflict number is equal to the earlier total conflict number, the current column sequence is stored together with the earlier column sequence. If the current total conflict number is less than the earlier total conflict number, the current column sequence is stored.

In step S16, determine whether all possible column order combinations starting with the same column (e.g., column K) have been explored. If so, go to step S18, otherwise go to step S17.

In step S17, a recursive method is used to search from the back to the front in the currently constructed row sequence to see if a row position can be replaced by another row. If found, this position and the subsequent combination are removed, and the next suitable candidate for this position (such as row M) is selected in step S13, and the entire row sequence under this condition is completed (in step S13, the selected arrangement will be eliminated).

Below, we take row 1 of table 1 (conflict table) as an example to describe how to create a row order.

In step S12, select row 1 as the first row in the current row order. At this time, the row order = [1], and the total number of conflicts = 0.

In step S13, the table is looked up to determine that row 2 and row 1 have the smallest number of conflicts. At this time, the row order = [1,2], and the total number of conflicts = 0.

In step S14, it is determined that the column sequence has only 2 items, and therefore returns to step S13.

In step S13, the table is looked up to determine the minimum number of conflicts between row 3 and row 2. At this time, the row order = [1, 2, 3], and the total number of conflicts = 2.

Repeat the process (steps S13 plus S14) until all rows are written into the row order. At this point, the row order = [1,2,3,4,5,6,7,8], and the total number of conflicts = 5.

Below, we discuss situations where substitutions produce equal or better results.

After completing a row sequence [1,2,3,4,5,6,7,8], in step S16, it is determined that all row sequences starting with row 1 have not been found, and step S17 is performed. In step S17, row sequence positions that have other candidates to replace are searched from back to front. Because there are no other candidates in the row sequence 8, 7, 6, and 5 that meet the original minimum conflict number (conflict number = 0), other candidates are found until position 4. At this time, this position and the subsequent combination are removed to obtain the row sequence [1,2,3], and return to step S13 to select row 8 (because the conflict number between row 3 and row 4 is 0, and the conflict number between row 3 and row 8 is also 0, but row 4 has been previously selected and shaved off). Then, repeat step S13 and step S14. Finally, the new row sequence [1,2,3,8,7,6,5,4] can be completed, and the total number of conflicts is 5.

In step S15, this row sequence is additionally stored because it has the same total conflict count as the row sequence stored earlier. At this point, two row sequences are found.

Below, we discuss the case where substitution does not produce better results.

If "minimum conflict" is expanded to a large range, such as 20, then after completing the initial row sequence [1,2,3,4,5,6,7,8], there is another choice in step S17. When searching from back to front to the row sequence 7, another candidate is found (because the number of conflicts between row 6 and row 8 is 14 and 14 <20), then return to step S13 and select row 8 to replace the original row 7. By repeatedly executing steps S13 and S14, another row sequence is established. At this time, the row sequence = [1,2,3,4,5,6,8,7], and the total number of conflicts = 16.

However, in step S15, since 16>5 (the total number of conflicts stored earlier), this column sequence is skipped and step S17 is performed to recursively explore other column sequences.

In step S18, determine whether each row has been the head of a row sequence. If so, go to step S20, otherwise select the next row (for example, row K+1) and return to step S12.

Below, we describe step S18 as an example. Let the column order found be as follows:

Found Row-Sequences (number = row index)

[1, 3,4, 6,2, 5]

[1, 6, 5, 3, 2, 4]

[2, 5, 1, 3, 4, 6]

[2, 4, 1, 6, 5, 3]

This matrix has 6 columns, and all column sequences starting with column 1 or column 2 have been found, a total of 4 column sequences. In step S18, it is found that not every column has been used as the first column to check its column sequence, so the next column is selected in sequence, that is, column 3 is used as the first column sequence, and step S12 is returned to construct the column sequence under such conditions.

In step S20, one of the column sequences (column sequences with each column as the first and satisfying the minimum number of conflicts) generated in step S10 is selected one by one. Then, steps S30, S40, S50 and S55 are executed for the selected column sequence to generate a reorganization matrix (H _ab matrix), a reorganization vector (ab_vector) and a set of CMEM instructions. Then, in step S60, it is determined whether the upper limit of the number of repetitions is reached. If not, it returns to step S30.

In step S30, a reorganized matrix and a reorganized vector are generated. All rows are processed one by one in the order of the selected rows. Referring to FIG. 5, the original matrix is evenly divided into two or more segments (parts) by swapping according to the number of cores, and the swapped segments are integrated into a reorganized matrix and a reorganized vector (the vector information includes the order of splitting and swapping). Step S30 is performed so that the load (the number of elements to be processed) of each core of the hardware is the same or similar to the load of any other core.

When splitting, use the weighted results to randomly determine which segment each column is assigned to. Taking Figure 5 as an example, range_k represents the number of columns currently missing in segment k, and the total number of column requirements (the sum of all range_k) is the total random range. In this total random range, a random number is generated, and the interval of this random number is used to determine which segment this column should be assigned to. The greater the demand for a segment (the larger the length in the figure), the higher the probability that this random number falls within its range, indicating that this column is more likely to be assigned to this segment. When any segment is filled, it will be naturally removed, and no column will be assigned to this segment.

In addition, to help us evaluate the results after the spin-off, a weighted swap score is defined as follows:

是所有段的平均元素總量，N _jk 是第j列的第k段的元素量，

是第j列的所有段的平均元素量，α+β=1。 In the above formula, M is the total number of columns, L is the total number of segments, j is the column number and ranges from 1 to M , k is the segment number and ranges from 1 to L , N _k is the total number of elements in the kth segment,

is the average total number of elements in all segments, N _jk is the number of elements in the kth segment of the jth column,

is the average number of elements in all segments of the jth column, α + β =1.

Use the weighted swap score to evaluate the result of the column swap, the smaller the better. The weighted swap score considers two factors, one is the total number of elements in each segment, and the other is the number of elements in each segment in each column. Each factor gets a weight (α or β). In actual application, the size of α and β can be adjusted according to the distribution of the original matrix, so that the weighted swap score emphasizes or averages the impact of the two factors.

For the first factor, calculate the absolute value of the difference between the amount of elements in each segment and the split mean (ideal value) and add them together. To balance the effects of the two factors, multiply the first factor by M.

For the second factor, calculate the absolute value of the difference between the amount of each segment of elements in each column and the average value of the splits in this column (ideally, each column may be different), and add them together.

Referring to FIG. 6, step S30 is described in detail with steps S31, S32, S33 and S34, which evenly divide the original matrix into two or more segments and generate a reorganized matrix and a reorganized vector.

In step S31, each column of the original matrix (column 1, column 2, column 3, ..., column n) is processed in sequence. When processing each column, a random number is generated, and according to the size of the random number, its position is matched to the range where the relevant segment is located, and the column is allocated to the corresponding segment.

Refer to Figures 7, 8 and 9 for an example of the method of step S31. Assume that the original matrix is to be divided into four segments, namely segment 1, segment 2, segment 3 and segment 4, and the number of columns required for processing them is 2, 4, 1 and 3 respectively (because the columns are randomly assigned to any segment, the number of columns required to process each segment is likely to be unequal), and the total random range is 10. The longer segment in the figure means that more columns are required and there is a greater chance of obtaining a random number within its range. For example, the current processing is to the kth column, and column k is to be assigned to one of the segments. A number is randomly selected from 1 to 10, and the random number 5 is obtained. Since 5 is in segment 2, column k is assigned to segment 2.

Then, subtract 1 from the required number of segment 2 (range_2), 4-1=3, and we know that segment 2 only needs 3 columns. The number of columns required for each segment is shown in Figure 8. The range of random numbers becomes 1 to 9 (the total random range is 9).

Then, process column k+1 and randomly select a number from 1 to 10. For example, if the random number is 6, column k+1 is assigned to segment 3.

Since segment 3 is filled, it is removed from this demand graph. The number of columns required for each segment changes as shown in Figure 9. At this time, the range of random numbers becomes 1 to 8 (the total random range is 8).

Referring to Figure 6, in step S32, the amount of non-zero (NZ) elements in each segment is observed, and the weighted swap score is calculated according to the equation. If the weighted swap score is less than the weighted swap score stored earlier, the weighted swap score is updated, and the fields and sequence assigned to each segment at this time are recorded.

Refer to the following table for an example of calculating the weighted swap score:

First, observe the total amount of each segment and calculate the first factor. Referring to the table above, the total amount of the 4 segments = {29, 27, 26, 22}, the average value = 26, and the difference between the total amount of each segment and the average value, and the sum of the absolute values is 3+1+0+4=8. Since there are 4 columns in total, multiplying by the total number of columns gives 8x4=32.

Next, observe the total amount of each column and calculate the second factor. The total number of columns in each segment = {5,5,8,6}, the average value is 6, and the sum of the absolute values of the differences is 1+1+2+0=4. The number of columns in 2 = {7,9,7,5}, the average value is 7, and the sum of the absolute values of the differences is 0+2+0+2=4. The number of columns in 3 = {9,5,5,5}, the average value is 6, and the sum of the absolute values of the differences is 3+1+1+1=6. The number of columns in 4 = {8,8,6,6}, the average value is 7, and the sum of the absolute values of the differences is 1+1+1+1=4. Add up the sum of the absolute values of the differences of the four columns to get 20.

If α=β=0.5, it means that the two factors have equal influence, then the weighted swap score is 32*0.5+20*0.5=52.

Each swap (obtained by executing steps S31 and S32) has a weighted swap score. If this weighted swap score is less than the weighted swap score stored earlier, then this weighted swap score is stored as the minimum weighted swap score. This swap is the best way, and the fields and sequence assigned to each segment at this time are recorded.

In step S33, determine whether the number of matrix swap allocations has reached the maximum number of recursions. If it has reached the maximum number of recursions, go to step S34, otherwise return to step S31 to swap the columns of the entire matrix again.

In step S34, a reorganization matrix and a reorganization vector are generated. The reorganization with the minimum weighted reorganization score is the best method. According to the above-mentioned field allocation and sequence of each segment corresponding to the minimum weighted reorganization score, all segments are swapped and integrated into a reorganization matrix and a reorganization vector.

The element scheduler optimizes the order of elements of each reshuffle matrix with a reshuffle vector for two or more cores to run in parallel. The element scheduler organizes the order of matrix elements for each core and reduces system latency by avoiding read-before-write conflicts, because the system uses hardware idling to avoid read-before-write conflicts. The element scheduler runs on all cores and is optimized for each core.

In step S40, the elements are scheduled and CMEM instruction lines are generated. The order in which the elements of each row are handed over to the hardware for processing is determined based on the possibility of conflict between each row and other rows. Referring to Figure 10, two values are defined to determine the possibility of conflict, one is the conflict flag (CF), and the other is the risk score (Risk Score).

The conflict flag (CF) indicates the number of unprocessed elements above (before) the current element in the same column. When each matrix element is processed and written back to the memory, the conflict flag of all matrix elements below (after) the same column is immediately reduced by 1. Therefore, the conflict flag of an element = 0 means that all elements above it have been written back to the memory, and it is a non-conflicting (usable) element.

The risk score indicates the number of elements below (after) the current element in the same column. A higher risk score indicates a greater chance of conflict (indicating that more elements in the same column share the same memory space). To reduce future conflicts, if possible, process elements with higher risk scores first and write them back to memory, which can reduce the probability of future conflicts.

Refer to Figure 11. When calculating the risk score, the hardware processes the matrix elements from the last row back to the first row and wraps around. To handle the conflict caused by wrapping, the first few rows (at least one row) must be copied to the back of the last row as additional rows to approximate the conflict of wrapping. The number of additional rows depends on the length of the hardware processing sequence (pipeline), that is, the maximum number of rows that may be in conflict.

Referring to Figure 12, the processing of step S40 is described in detail using steps S41, S42, S43, S44 and S45. In step S41, the entire reorganized matrix is preprocessed. For each element, two counters are used to calculate the conflict flag and risk score.

Refer to the left side of Figure 13 for an example of step S41. If the conflict only occurs between two adjacent columns, then when using additional columns to calculate the risk score, only column 1 is copied to the bottom as an additional column. Refer to the right side of Figure 13 for the result. At this time, the conflict mark of all elements in column 2 is {1,X,0,X,1}, and the risk score is {1,X,0,X,3}, where X indicates that the position is all zero elements on column 2 and is not calculated.

Referring to Figure 12, in step S42, the elements are sorted from high to low according to the risk score. All zero elements are filtered out, leaving only non-zero elements as candidates. The purpose of sorting is to search for available (conflict mark = 0) elements from left to right when looking for the available element with the largest risk score in the later step, and stop when the first element that meets the conditions is found, that is, the element with the largest risk score among the available elements.

Refer to the right side of Figure 13 for an example of step S42. The risk scores of column 1 to column 5 in row 2 are {1, X, 0, X, 3} in order, arranged from large to small and after removing all zero elements, they are {3, 1, 0}, which come from column 5, column 1 and column 3 respectively. This is a candidate for row 2.

Referring to Figure 12, steps S43 and S44 use the queue data structure type to simulate the hardware behavior and use the queue characteristics to maintain the time difference between the input and output of elements in the hardware. The depth of the queue depends on the linear length of the hardware's own processing sequence.

In step S43, non-zero element data is read from the memory. In this step, a conflict-free element with the largest risk score must be searched and selected (its conflict flag = 0, indicating that the elements above it are written back to the memory), and this element is placed at the back of the queue simulating its core operation, and an insertion action is performed. This approach will be applied to the operation of all cores. If no available element is found in a core, the core is shut down (stall) for a system cycle. The order of selecting elements is the scheduling result of the reading phase, which is recorded for the subsequent generation of CMEM instructions.

In step S44, the processed non-zero element data is written into the memory. An element is taken from the front of the queue and removed from the queue. The non-zero elements below (after) the column where this element is located are implemented with a write-back mechanism. The write-back mechanism is to reduce the conflict flags of the non-zero elements below (after) the same column by 1, indicating that a non-zero element above (before) this non-zero element has been processed and written back.

In step S45, determine whether the read and write steps have been performed on each element in each core. In other words, determine whether the entire matrix is completed. If so, go to step S50, otherwise return to step S43.

In step S50, the above scheduling results are compiled into CMEM command lines. The total number of these command lines is used to evaluate hardware performance and is considered as an update reference.

Taking row 2 and row 3 of Figure 13 as an example, refer to Figures 14 to 16 to describe the memory read (step S43) and memory write (step S44) under this single core state. This method can be applied to different cores and different sub-matrices under multi-core conditions.

Referring to the left side of Figure 14, after step S42 sorts the non-zero elements of each column, the candidate list of column 2 is column 5, column 1, column 3 in order, because its risk scores are 3, 1, 0, and the conflict marks are 1, 1, 0 in order. In addition, the candidate list of column 3 is column 5, column 2, column 4 in order, because its risk scores are 2, 1, 1, and the conflict marks are 2, 0, 0 in order.

Also refer to the right side of Figure 14. Currently, there are 4 elements in the queue processed by this core, and the front of the queue (the one to be output) is the element in column 5 of a previous row.

In step S43, the step of reading from the memory is executed by selecting the available element with the largest risk score in the candidate list of row 2. Since only the element of column 3 has a conflict flag = 0 when scanning from left to right in the candidate list of row 2, the element of column 3 is selected and input into the rear end (input end) of the right queue of Figure 14, and the element of column 3 of row 2 is recorded as the scheduling result of this step.

In step S44, the step of writing into memory is executed, an element is taken out from the front end (output end) of the queue, and the write-back mechanism is implemented for this element. Because this element comes from column 5 of a previous row, when writing back to memory, the conflict flag of the element below it in the same column needs to be reduced by 1. In this example, the conflict flag of the element from column 5 in the candidate list of row 2 and row 3 is reduced by 1, that is, the conflict flag of the element in column 5 of row 2 is reduced to 0, and the conflict flag of the element in column 5 of row 3 is reduced to 1. The result is shown on the left side of Figure 15.

In step S45, it is determined that the entire matrix is not completed, and the process returns to step S43.

Next, refer to Figure 15, execute step S43, scan from left to right in the candidate list of row 2, only the element of column 5 has a conflict mark of 0 and the risk score is the largest, so select the element of column 5 and input it into the back end (input end) of the right queue of Figure 15, and record the element of column 5 of row 2 as the scheduling result of this step.

In step S44, an element is taken from the front end (output end) of the queue, and a write-back mechanism is implemented for this element. Because this element comes from column 1 of a previous row, the conflict flag of column 1 element of row 2 is reduced to 0, and row 3 does not change because there is no column 1 related element. The result is shown on the left side of Figure 16.

In step S45, it is determined that the entire matrix is not completed, and the process returns to step S43.

Next, refer to Figure 16 and execute step S43. Scan from left to right in the candidate list of row 2. Since only the column 1 element is left in the list and its conflict flag = 0, select the column 1 element and input it to the end (input end) of the right queue of Figure 15, and record the row 2 column 1 element as the scheduling result of this step.

In step S44, an element is taken from the front end (output end) of the queue, and a write-back mechanism is implemented for this element. Because this element comes from column 2 of a previous row, the conflict flag of column 2 of row 3 is reduced to 0, and row 2 is not changed because there is no element.

In step S45, it is determined that the entire matrix is not completed, and the process returns to step S43. Steps S43, S44, and S45 are repeated until all elements of the entire matrix are completed, and the process proceeds to step S50, where the CMEM command line is compiled according to the above recorded scheduling results.

Refer to Figure 3, in step S55, if a better result is found, it is updated. Fewer instruction lines means better results, because the hardware operation time is positively correlated with the number of instructions.

In step S60, determine whether the number of times the command line is generated reaches the maximum number of loops. If so, go to step S70, otherwise return to step S30, and allocate the matrix and schedule the generation of new command lines according to the selected column order.

In step S70, determine whether all row sequences have been processed, that is, generate different command lines for each row sequence and record the best result. If yes, go to step S75, otherwise return to step S20 to select the next row sequence in sequence.

In step S75, the above command line is made into the final decoder scheduling file, and CRC32 check bits are added at the end of the file.

In step S80, the above completed scheduling file is checked. The checking step includes reading the content from the file, rebuilding the matrix according to the instruction format, and checking each restriction. At the same time, the decoder model (C-model) written in C language directly executes the scheduling file and checks whether the decoded output is correct.

The above is only to describe the preferred implementation of the present invention, and is not intended to limit the scope of the present invention. Equal changes made by ordinary technicians in this technical field based on the embodiments, as well as changes known to technicians in this field, are still within the scope of the present invention.

S10: Swap the rows of the matrix to produce a different row order

S20: Select a column order in sequence

S30: Swap columns and split the matrix

S40: Scheduling elements in each core

S50: Generate multiple lines of CMEM instructions

S55: Find the minimum number of CMEM instruction lines

S60: Reached the upper limit of repetition times?

S70: Have all row sequences been processed?

S75: Generate a scheduling file according to the CMEM instruction and add CRC32 check bits

S80: Use the checker and C model to test the scheduling file

Claims (2)

A method for improving LDPC decoder parallelism by segmenting an LDPC code includes the following steps: dividing the entire matrix into a number of segments, randomly assigning each column in the matrix to a segment in sequence, and using the current demand of each segment as a weight during the assignment (S31); calculating a weighted swap score as follows (S32):

Where M is the total number of columns, L is the total number of segments, j is the column number and ranges from 1 to M , k is the segment number and ranges from 1 to L , N _k is the total number of elements in the kth segment,

is the average total number of elements in all segments, N _jk is the number of elements in the kth segment of the jth column,

is the average number of elements of all segments in the j-th column, α + β =1; if this weighted swap score is less than the weighted swap score stored earlier, then update the weighted swap score and record the swap allocation method (S32); determine whether the swap allocation number of the matrix reaches the maximum recurrence number (S33); if the swap allocation number of the matrix does not reach the maximum recurrence number, return to the above step of dividing the entire matrix into several segments (S31); and if the swap allocation number of the matrix has reached the maximum recurrence number, generate a reorganized matrix and a reorganized vector according to the swap allocation method of the minimum weighted swap score recorded above (S34). A method for improving the parallelism of LDPC decoders by dividing LDPC codes as described in claim 1, wherein the step (S31) of equally dividing the entire matrix into segments includes the following steps: calculating the number of columns that can be accommodated in each segment after the matrix is equally divided, and using the number of columns as the requirement of the segment; summarizing all requirements as the total random range; generating a random number, which is 1 to the total random range; selecting a segment from the segments as a middle segment according to the location of the random number; assigning the number of columns to the middle segment; reducing the number of columns required by the middle segment by 1; reducing the total random range by 1; and returning to the step of generating a random number to assign the next column.

Images