TWI854675B - Method for improving parallelization of an ldpc shuffle decoder by reordering an ldpc code - Google Patents

Abstract

The LDPC shuffle decoder has two cores and two memories, processing all the fields of an LDPC matrix in sequence. When processing each field, the reading and writing of its non-zero elements are evenly distributed to the two memories. With this distribution method, the LDPC shuffle decoder can complete the reading and writing of the LDPC matrix in the least number of cycles.

Description

Method for improving LDPC recombinant decoder parallelism by rearranging LDPC codes

The present invention relates to an LDPC reorganization decoder, and more particularly to a method for improving the parallel operation of an LDPC reorganization decoder by re-arranging LDPC codes.

In LDPC shuffle decoding, the decoder processes the above matrix in columns.

In view of the above problems of the prior art, the purpose of the present invention is to provide a method for rearranging LDPC code fields to shorten the delay of LDPC reorganization decoder.

To achieve the above purpose, the above method includes: providing two memories for the above LDPC recombinant decoder, evenly allocating the non-zero elements of the matrix of the above LDPC code to the above two memories, reading the above non-zero elements from the above two memories according to the above allocation method, and writing the above non-zero elements to the above two memories, updating the allocation method, and judging whether the maximum recursion number is reached. If the maximum recursion number is not reached, returning to the step of evenly allocating the above non-zero elements to the above two memories. If the maximum recursion number is reached, judging whether the allocation is successful. If the allocation is successful, generating a scheduling file, otherwise ending.

S20: The first stage of allocation

S21: Accumulate the number of non-zero elements in a column from two memories respectively

S23: Temporarily save the current overall allocation status as the optimal allocation status

S25: Is the amount read from the two memories balanced?

S27: Has the number of backtrackings reached the upper limit?

S29: Execution backtracking

S31: Restore the previously saved best state

S33: Randomly allocate to memory based on balanced write conditions

S35: Reached the last field of the matrix?

S37: Handle unconfirmed memory read information in the beginning field

S39: Is the read quantity of each field balanced or has the maximum number of repetitions been reached?

S40: Second stage of allocation

S41: Read non-zero elements from the corresponding memory in sequence according to the memory allocation method

S43: Read all non-zero elements in this column?

S45: Is the destination memory full?

S47: According to the memory allocation method, write a non-zero element into the corresponding memory

S49: Finish writing the non-zero elements of this column?

S51: Reached the last column?

S53: Execute Surround

S55: Was there any coverage during this orbit?

S57: Reached the maximum number of loops?

S59: Record failure once

S60: Update best results

S70: Determine whether the maximum number of repetitions has been reached

S80: Determine whether the allocation is successful

S90: Generate command file for reorganizing the decoder

〔Figure 1〕A LDPC code is shown;

[Figure 2] shows a typical LDPC parallel decoder;

[Figure 3] is a flow chart of the method of rearranging LDPC codes to improve the parallel operation of LDPC reorganization decoders of the present invention;

[Figure 4] is a flow chart of a subroutine of the method for improving the parallel operation of LDPC reorganization decoder by rearranging LDPC codes shown in Figure 3;

[Figure 5] shows a simplified LDPC code and its balanced read and write allocation;

[Figure 6] shows another unbalanced allocation of LDPC codes;

[Figure 7] shows a balanced distribution after the LDPC code in Figure 6 is traced back;

[Figure 8] shows another unbalanced distribution after LDPC code backtracking in Figure 6;

[Figure 9] shows the nested traceback allocation that may be generated by the LDPC code in Figure 6;

[Figure 10] is a flow chart of another subroutine of the method for improving the parallel operation of LDPC reorganization decoder by rearranging LDPC codes shown in Figure 3;

[Figure 11] shows the processing of an LDPC code with a certain memory capacity;

[Figure 12] shows the first pass of processing the LDPC code shown in Figure 11;

[Figure 13] shows the second round of processing the LDPC code shown in Figure 11; and

[Figure 14] shows the first pass of the LDPC code in Figure 11 processed with another memory capacity.

The following reference figures further illustrate the preferred embodiments of the present invention. To facilitate understanding of the present invention, the same symbols are used to indicate the same components.

Referring to Figure 1, LDPC (low-density parity check) codes exist in the form of a matrix. This matrix has M rows*N columns, and each element is a smaller circulant. If the circulant contains only the value 0, then this element is a "zero element" (in the figure, it is represented by X). If the circulant contains the value 1, then this element is a "non-zero element" (in the figure, the circulant shift value is represented by a number). In practice, only non-zero elements are required when calculating LDPC codes. Due to the hardware limitations of the decoder, LDPC reorganization decoding operates backwards in "column" units.

Referring to Figure 2, to increase the efficiency of LDPC decoding, the LDPC decoder can be expanded. In this case, the decoder has two memories (A and B) and two cores (1 and 2). Cores 1 and 2 are both processors. Ideally, when core 1 reads data from memory A (or B), core 2 reads data from memory B (or A). Then, the LDPC decoder processes the data. Then, when core 1 writes the processed data back to memory A (or B), core 2 writes the processed data back to memory B (or A). The simultaneous operation of core 1 and core 2 is called "parallelization." However, non-zero elements in different columns of the same row have dependencies, that is, the data required to process each non-zero element is to read the content of the previous column in the same row (because the memory location must be the same). In addition, the distribution of non-zero elements in the LDPC matrix is sparse and irregular, so when calculating each column, two cores may need to read (or write) a single memory A (or B) at the same time. At this time, only one core is working, and the other core must be idle, causing the entire system to delay.

FIG3 shows a method of improving the LDPC reorganization decoder by rearranging the LDPC code according to a preferred embodiment of the present invention. The method of the present invention rearranges the above LDPC code to improve the parallelism of the above LDPC reorganization decoder. In other words, the method of the present invention avoids one core (1 or 2) being idle while the other core (2 or 1) is operating. Specifically, the method of the present invention sorts or distributes the data reading and writing of the non-zero elements of each field, so as to parallelize and balance the processing of these non-zero elements and optimize the performance of the above LDPC reorganization decoder.

In step S20, the first phase of allocation is performed. Check the entire matrix, mark and arrange some non-zero elements of each column to memory A, mark and arrange other non-zero elements of each column to memory B, and ensure that the two memories have the most appropriate balance. Repeat this step until the two memories are balanced or the maximum number of recursions is reached (the two memories are unbalanced).

In step S40, the second phase of allocation is performed. This is used to detect whether memory A or B has caused a memory overflow error due to the above allocation, and the error flag is passed to step S60.

In step S60, the best result is updated according to the restrictions and hardware requirements. Only one result is retained as the final result. To this end, the result of this recursion is compared with the previously stored result. If the result of this recursion is better than the previously stored result, the previously stored result is replaced by the result of this recursion, otherwise the previously stored result is retained.

In step S70, determine whether the maximum number of loops has been reached. If so, go to step S80, otherwise return to step S20. Therefore, repeat steps S20, S40 and S60 until the maximum number of loops has been reached.

In step S80, determine whether the allocation is successful. If so, go to step S90, otherwise end.

In step S90, a command file for reorganizing the decoder is generated when the data is finally output. This command file is called a "scheduling file".

Referring to FIG. 4 , step S20 is described in detail. The goal of step S20 is to put non-zero elements into memory A and memory B in a balanced manner. Step S20 includes steps S21, S23, S25, S27, S29, S31, S33, S35, S37, and S39. Steps S21, S23, S25, S27, S29, and S31 belong to the reading stage, step S33 belongs to the writing stage, and steps S35, S37, and S39 belong to the subsequent processing stage.

In step S21, as the first step of reading, the number of non-zero elements in a certain column from memory A and B is accumulated. To do this, it is necessary to check whether the non-zero elements in the previous one or several columns in the same column are written into memory A or memory B. It should be noted that the first few columns of the matrix may not have previous memory information at this time, so the number of elements in this column is not accumulated temporarily, but it is assumed that the number from the two memories is balanced, so that the condition is met in step S25 and enters step S33 to continue writing into the memory. These unconfirmed read memory information will be processed later in step S37.

In step S23, if the current field is a new field (indicating that the allocation has proceeded to the new field), the current overall allocation status is temporarily saved as the optimal allocation status, and the current maximum field sequence number is recorded. This maximum field sequence number record can be used to determine whether the current field is a new field. If the current field sequence number is greater than the previous maximum field sequence number, then this field is a new field.

In step S25, the result of step S21 is used to determine whether the amount read from the two memories A and B is balanced. In other words, determine whether the amount of non-zero elements in this field read from memory A is equal to the amount read from memory B (if the total number of non-zero elements is an odd number, the condition for balance is a difference of 1). If so, go to step S33, otherwise go to step S27.

In step S27, it indicates that the amount read from the two memories is unbalanced, and rolling back is required to correct it. First, determine whether the number of rollbacks has reached the upper limit. If so, go to step S31, otherwise go to step S29 to perform rollback. The number of rollbacks is the number of times rollbacks are performed within the fixed field range (without executing to any new field). That is, within this range, each time rollback is performed, the rollback number is increased by 1. At the same time, the upper limit of the rollback number is defined to avoid falling into an infinite rollback loop when no balanced allocation state is found. This backtracking may be in the previous backtracking, that is, when executing the backtracking, it may trigger another backtracking, but as long as it occurs within this fixed range, the triggering count should be increased by 1 for each backtracking.

In step S29, backtracking is actually performed. A non-zero element that causes an imbalance is randomly selected, and the previous non-zero element in the same column is returned, and the column where it is located is processed again from step S21. When reprocessing this column, since writing to memory A or memory B is randomly allocated according to the balanced writing condition in step S33, there will be an opportunity to redistribute the read quantity of subsequent columns (including the above-mentioned column that causes an imbalance) to achieve a parallel state.

In step S31, if no better combination is found during the backtracking and the backtracking times have reached the upper limit, the previously saved best state (stored in step S23) is restored.

In step S33, based on the balanced writing condition, the data of non-zero elements are randomly allocated to be written to memory A or memory B.

In step S35, determine whether the last field of the matrix has been reached. If so, go to step S37, otherwise return to step S21 to continue processing the next field.

In step S37, the unconfirmed memory read information in the beginning field is processed. The memory where the data is stored is known by referring to the write information of the last few fields, and then the corresponding memory read is filled in the beginning field. In other words, the last few fields are regarded as the previous memory information before the first few fields.

In step S39, determine whether the read quantity of each field is balanced (no need to determine the write, because the write is based on the balanced quantity) or the maximum number of loops has been reached. If so, go to step S40, otherwise return to step S21.

Referring to FIG. 5 , an example is given to describe how to implement the method of the present invention.

In step S21, the data reading of column 1 is temporarily not processed because it is unknown whether the writing of the preceding data of columns 2, 3, 5 or 6 is allocated to memory A or memory B. In step S23, the current status is recorded, and it is assumed that the reading quantity is balanced and jumps from step S25 to step S33. In step S33, the non-zero element data is written into memory A and memory B according to the balanced quantity.

In step S21, the data reading of column 2 is temporarily not processed because it is unknown whether the writing of the preceding data of columns 1 and 4 is allocated to memory A or memory B. In step S23, the current status is recorded, and it is assumed that the read quantity is balanced and jumps from step S25 to step S33. In step S33, the non-zero element data is written into memory A and memory B according to the balanced quantity.

In step S21, processing column 3, it can be seen that the data of row 1 must be read from memory A (written from column 2, row 1), the data of row 2 must be read from memory A (written from column 1, row 2), the data of row 3 must be read from memory B (written from column 2, row 3), and the data of row 4 must be read from memory B (written from column 2, row 4).

In step S23, it is determined that field 3 is a new field, and therefore the current allocation state is saved as the optimal state.

In step S25, from the result of step S21, it is determined that the two memories are balanced, and thus the process goes to step S33.

In step S33, non-zero element data is written to the memory in a balanced amount. At this time, rows 1 and 2 are allocated to be written to memory A, and rows 3 and 4 are allocated to be written to memory B.

In step S35, it is determined that field 3 is not the last field, and therefore the process returns to step S21.

In step S21, column 4 is processed. It can be seen that the data of row 2 must be read from memory A (written from column 3 column 2), the data of row 4 must be read from memory B (written from column 3 column 4), the data of row 5 must be read from memory A (written from column 2 column 5), and the data of row 6 must be read from memory B (written from column 1 column 6).

In step S23, it is determined that field 4 is a new field, and therefore the current allocation state is saved as the optimal state.

In step S25, from the result of step S21, it is determined that the two memories are balanced, and thus the process goes to step S33.

In step S33, the non-zero element data is randomly allocated and written into the memory according to the balanced quantity. At this time, rows 2 and 5 are allocated to be written into memory A, and rows 4 and 6 are allocated to be written into memory B.

In step S35, it is determined that field 4 is not the last field, and therefore the process returns to step S21.

In step S21, column 5 is processed. It can be seen that the data of row 2 must be read from memory A (written from column 4 column 2), the data of row 3 must be read from memory B (written from column 3 column 3), the data of row 5 must be read from memory A (written from column 4 column 5), and the data of row 6 must be read from memory B (written from column 4 column 6).

In step S23, it is determined that field 5 is a new field, and therefore the current allocation state is saved as the optimal state.

In step S25, from the result of step S21, it is determined that the two memories are balanced, and thus the process goes to step S33.

In step S33, non-zero element data is written to the memory in a balanced amount. At this time, rows 2 and 3 are allocated to be written to memory A, and rows 5 and 6 are allocated to be written to memory B.

In step S35, it is determined that field 5 is the last field, and therefore the process goes to step S37.

In step S37, the subsequent wraparound allocation begins, filling in the missing read information starting from field 1. At this point, it can be seen that the data in row 2 must be read from memory A (written from field 5 row 2), the data in row 3 must be read from memory A (written from field 5 row 3), the data in row 5 must be read from memory B (written from field 5 row 5), and the data in row 6 must be read from memory B (written from field 5 row 6).

Continue filling in the missing read information in field 2 in this way. It can be seen that the data in row 1 must be read from memory A (written from field 3 row 1), the data in row 3 must be read from memory A (written from field 1 row 3), the data in row 4 must be read from memory B (written from field 4 row 4), and the data in row 5 must be read from memory B (written from field 1 row 5).

In step S39, it is determined that all fields are balanced in terms of read quantity (the read from memory A is balanced with the read from memory B), and thus step S20 is terminated.

Refer to Figures 6 and 7 to describe the backtracking once, from an unbalanced distribution state to a balanced distribution state.

In Figure 6, in columns 1 to k+2, the amount of data read from the two memories for each column is balanced. When reading data from column k+3, the amount of data read from the two memories is unbalanced. It can be seen that the data from columns 1 to 3 are read from memory A, and only column 4 is read from memory B.

In step S21, it is found that 3 non-zero elements in column k+3 are read from memory A, and 1 non-zero element is read from memory B.

In step S23, it is determined that field k+3 is a new field, and therefore the current allocation state is considered the optimal state.

In step S25, from the result of step S21, it is determined that the amount read from the two memories is unbalanced, and thus the process goes to step S27.

In step S27, it is determined that the number of backtracking times has not reached the upper limit, and therefore the process goes to step S29.

In step S29, randomly select row 1 (Figure 7), return to column k+2, and return to step S21. At this time, the number of backtracking times must be increased by 1.

Referring to Figure 7, in step S21, it is found that 2 non-zero elements in column k+2 are read from memory A, and 2 non-zero elements are read from memory B.

In step S23, it is determined that field k+2 is an old field, and therefore the current allocation state is not the best state.

In step S25, from the result of step S21, it is determined that the amount read from the two memories is balanced, and thus proceeds to step S33.

In step S33, non-zero element data is written into the memory in a balanced and randomly distributed manner. At this time, rows 3 and 5 are allocated to be written into memory A, and rows 1 and 4 are allocated to be written into memory B.

In step S35, it is determined that field k+2 is not the last field, and therefore the process returns to step S21.

In step S21, it is found that the reads of 2 non-zero elements in column k+3 are allocated to memory A, and the reads of 2 non-zero elements are allocated to memory B.

In step S23, it is determined that field k+3 is an old field, and therefore the current allocation state is not the best state.

In step S25, based on the result of step S21, it is determined that the amount of data read from the two memories is balanced, and thus the data writing step is performed in step S33. At this point, the data reading has changed from the original unbalanced distribution state to a balanced distribution state.

Refer to Figures 6 and 8 to describe the possible situations and subsequent treatment methods of backtracking once from one unbalanced allocation state to another unbalanced allocation state.

Referring to Figure 6, in step S21, it is found that 3 non-zero elements of column k+3 are read from memory A, and 1 non-zero element is read from memory B.

In step S23, it is determined that field k+3 is a new field, and the current allocation state is considered the optimal state.

In step S25, from the result of step S21, it is determined that the amount read from the two memories is unbalanced, and thus the process goes to step S27.

In step S27, it is determined that the number of backtracking times has not reached the upper limit, and therefore the process goes to step S29.

In step S29, randomly select row 3, return to column k+2, and return to step S21. At this time, the number of backtracking must be increased by 1.

Referring to Figure 8, in step S21, it is found that 2 non-zero elements in column k+2 are read from memory A, and 2 non-zero elements are read from memory B.

In step S23, it is determined that field k+2 is an old field, and therefore the current allocation state is not the best state.

In step S25, from the result of step S21, it is determined that the amount read from the two memories is balanced, and thus proceeds to step S33.

In step S33, non-zero element data is written into the memory in a balanced and randomly distributed manner, with rows 1 and 4 being written into memory A, and rows 3 and 5 being written into memory B.

In step S35, it is determined that field k+2 is not the last field, and therefore the process returns to step S21.

In step S21, it is found that 3 non-zero elements in column k+3 are read from memory A, and 1 non-zero element is read from memory B.

In step S23, it is determined that field k+3 is an old field, and therefore the current allocation state is not the best state.

In step S25, based on the result of step S21, it is determined that the amount read from the two memories is still unbalanced, and therefore the process goes to step S27. In this unbalanced state, it is necessary to determine in step S27 whether the upper limit of the backtracking number has been reached, and perform backtracking again based on the result (the backtracking number must be increased by 1) or perform recovery in S31 as described later.

If the allocation state cannot be changed from imbalance to balance, then at step S27 of a certain backtracking, it is determined that the backtracking times have reached the upper limit, and therefore the process goes to step S31. In step S31, since no better allocation state can be found, the previously stored best allocation state is used as a recovery (field k+3 in this case). Then, the process goes to step S33 to execute the data writing part, and in step S35, it is determined whether the next field is processed or the processing has been completed.

Refer to Figures 6 and 9 to describe the possible situation from one unbalanced allocation state to another unbalanced allocation state after backtracking once, and the need for a second and nested (multiple covering) backtracking, and describe the relevant subsequent disposal.

Referring to Figure 6, in step S21, it is found that 3 non-zero elements of column k+3 are read from memory A, and 1 non-zero element is read from memory B.

In step S23, it is determined that field k+3 is a new field, and the current allocation state is considered the optimal state.

In step S25, from the result of step S21, it is determined that the number of non-zero elements read from the two memories is unbalanced, and thus the process goes to step S27.

In step S27, it is determined that the number of backtracking times has not reached the upper limit, and therefore the process goes to step S29.

In step S29, randomly select row 2, return to column k+2, and return to step S21. At this time, the number of backtracking times must be increased by 1.

Referring to Figure 9, in step S21, it is found that 2 non-zero elements of column k+1 are read from memory A, and 2 non-zero elements are read from memory B.

In step S23, it is determined that field k+1 is an old field, and therefore the current allocation state is not the best state.

In step S25, from the result of step S21, it is determined that the amount read from the two memories is balanced, and thus proceeds to step S33.

In step S33, non-zero element data is written into the memory in a balanced and randomly distributed manner, with rows 3 and 5 being written into memory A, and rows 2 and 6 being written into memory B.

In step S35, it is determined that field k+1 is not the last field, and therefore the process returns to step S21.

In step S21, it is found that 3 non-zero elements in column k+2 are read from memory A, and 1 non-zero element is read from memory B.

In step S23, it is determined that field k+2 is an old field, and therefore the current allocation state is not the best state.

In step S25, from the result of step S21, it is determined that the amount read from the two memories is still unbalanced, and therefore step S27 is reached. In this unbalanced state, it is necessary to determine in step S27 whether the upper limit of the backtracking number has been reached, and perform backtracking again according to the result (the number of backtracking must be increased by 1), or perform recovery in S31. If it is determined that backtracking can be performed, since it is still in the previously unfinished backtracking, performing backtracking at the same time is nested backtracking. Backtracking can be performed repeatedly until the upper limit of the backtracking number is reached, or the subsequent field is successfully advanced (in step S23, the current field is determined to be a new field).

The second phase of allocation (step S40) is to further arrange the corresponding memory address to check the availability of the memory when the memory A (or B) allocation has been completed in the previous phase. Referring to Figure 10, step S40 includes steps S41, S43, S45, S47, S49, S51, S53, S55, S57, and S59. Steps S41 and S43 belong to the read phase, steps S45, S47, and S49 belong to the write phase, and steps S53, S55, and S57 are the subsequent wrap around phase.

Step S41, in a certain field, read the data of a non-zero element from the corresponding memory in sequence according to the memory allocation method determined in step S20, and remove the element data from the memory after reading.

In step S43, determine whether all non-zero elements in this column have been read. If so, go to step S45 to execute the step of arranging writing, otherwise return to step S41 to continue reading.

In step S45, first determine whether the destination memory is full. If so, it means that the memory space is insufficient to implement this allocation method, and immediately go to step S59 to end the second stage, otherwise go to step S47 to continue writing.

In step S47, according to the memory allocation method determined in step S20, the data of a non-zero element in the above field is sequentially written into an available address in the corresponding memory (it is advisable to randomly select addresses from the available space to increase allocation diversity).

In step S49, determine whether the non-zero element data of this field has been written. If so, go to step S51, otherwise return to step S45 to continue writing.

In step S51, determine whether the last field has been reached. If so, go to step S53, otherwise return to step S41 to process the next field.

In step S53, wrap around is executed to process the memory read and write of the entire matrix. If a conflict occurs during writing (the previously specified write address is already occupied), a random address is specified from the currently available memory space to overwrite the previous allocation. In addition, when this conflict occurs, it is noted that this wrap has been overwritten.

In step S55, determine whether there has been any coverage during this wrap (step S53). If so, go to step S57 to determine whether another wrap is required. Otherwise, it means that the second stage is completed and the allocation is correct and can be ended directly to step S60.

In step S57, determine whether the maximum number of wraps has been reached. If so, proceed to step S59 to prepare for termination, otherwise return to step S53 to execute wrap again.

In step S59, it is found that the memory space cannot implement this allocation method in the second stage, and the failure of the allocation in the two stages S20 and S40 is recorded once, and the subsequent work is performed in step S60.

Refer to Figure 11 to describe the execution of step S40. Assume that both memory A and B have 3 memory spaces. Process field 1, field 2, and field 3 in sequence.

When processing field 1, steps S41 and S43 are not executed because there is no information about the memory address.

In step S45, it is determined that the memory to be written is not full, so step S47 is performed to write a non-zero element of data into an address in the corresponding memory.

Repeat steps S45, S47 and S49 until all data corresponding to the elements in column 1 are written into the memory. Referring to the result at the bottom of Figure 11, the data in row 1 is written to address 1 of memory A, the data in row 2 is written to address 2 of memory A, the data in row 3 is written to address 1 of memory B, and the data in row 5 is written to address 2 of memory B.

In step S51, it is determined that field 1 is not the last field, and the process returns to step S41.

When processing column 2, repeat steps S41 and S43 until column 2 is read (column 4 does not execute steps S41 and S43 temporarily because there is no information about the memory address). Refer to the result at the bottom of Figure 11, column 1 reads from address 1 of memory A, column 3 reads from address 1 of memory B, and column 5 reads from address 2 of memory B. When reading, the data is also removed from the corresponding memory address, and at this time, address 2 of memory A still has data.

In step S45, it is determined that the memory to be written is not full, and therefore the process goes to step S47 to write a non-zero element of data into an address in the corresponding memory.

Repeat steps S45, S47 and S49 until all data corresponding to the elements in column 2 are written into the memory. Refer to the result at the bottom of Figure 11, the data in row 1 is written to address 1 of memory A, the data in row 3 is written to address 3 of memory A (because address 2 already has data), the data in row 4 is written to address 1 of memory B, and the data in row 5 is written to address 2 of memory B. If both memory A and B have only 2 memory spaces, then before writing row 3, step S45 will determine that memory A is full and cannot perform writing, and directly go to step S59 to record the error and end the sorting.

In step S51, it is determined that field 2 is not the last field, and the process returns to step S41.

When processing column 3, repeat steps S41 and S43 until column 2 is read. Refer to the result at the bottom of Figure 11, column 1 reads from address 1 of memory A, column 2 reads from address 2 of memory A, column 4 reads from address 2 of memory B, and column 5 reads from address 2 of memory B. During reading, the data is also removed from the corresponding memory address, and at this time, address 3 of memory A still has data.

Repeat steps S45, S47 and S49, first determine the corresponding memory space and then write, until the data in column 3 is written. Refer to the result at the bottom of Figure 11, the data in row 1 is written to address 1 of memory A, the data in row 2 is written to address 1 of memory B, the data in row 4 is written to address 2 of memory A, and the data in row 5 is written to address 2 of memory B.

In step S51, it is determined that field 3 is the last field, and therefore the process goes to step S53.

Referring to Figure 12, in step S53, the first loop is performed, which is to go back to the beginning to recheck the entire matrix, fill in the missing information, and handle any overlap situations.

Check the reading of column 1. Column 1 reads from address 1 of memory A, column 2 reads from address 1 of memory B, column 3 reads from address 3 of memory A (because column 3 in Figure 11 is the last to be written to address 3 of memory A), and column 5 reads from address 2 of memory B. When reading, the data is also removed from the corresponding memory address, and at this time, address 2 of memory A still has data.

Next, check the writing of column 1. The data in row 1 is written to address 1 of memory A. The data in row 2 conflicts and cannot be written to address 2 of memory A. The data in row 3 is written to address 1 of memory B. The data in row 5 is written to address 2 of memory B. Note that because the address 2 of memory A originally specified by the data in row 2 is occupied, it is written to address 3. An overwrite occurs and is recorded.

Check the reading of column 2. Row 1 reads from address 1 of memory A, row 3 reads from address 1 of memory B, row 4 reads from address 2 of memory A, and row 5 reads from address 2 of memory B. During the reading, the data is also removed from the corresponding memory address, and the data is still left at address 3 of memory A.

Next, check the writing of column 2. The data in row 1 is written to address 1 of memory A, the data in row 3 is written to address 2 of memory A, the data in row 4 is written to address 1 of memory B, and the data in row 5 is written to address 2 of memory B.

Check the reading of column 3. Row 1 reads from address 1 of memory A, row 3 reads from address 3 of memory A, row 4 reads from address 1 of memory B, and row 5 reads from address 2 of memory B. During the reading, the data is also removed from the corresponding memory address, and the data is still left at address 2 of memory A.

Next, check the writing of column 3. The data in row 1 is written to address 1 of memory A, the data in row 2 is written to address 1 of memory B, the data in row 4 conflicts and cannot be written to address 2 of memory A, and the data in row 5 is written to address 2 of memory B. Note that the data in row 4 is written to address 3 because the originally specified address 2 of memory A is occupied. An overwrite occurs and is recorded. The first loop ends and exits step S53.

In step S55, it is determined from the above records that this wraparound has coverage, and the process goes to step S57.

In step S57, the maximum number of loops is set to 10. The current number of loops is 1, which is less than 10, so return to step S53 and loop again.

Referring to Figure 13, in step S53, the second loop is performed, which is to go back to the beginning to recheck the entire matrix, fill in the missing information, and handle any overlap situations.

Same as the first loop, check the read and write of field 1, field 2, and field 3 in sequence. Note that when writing data in column 1, address 2 is written because the originally specified memory A address 3 is occupied. If an overwrite occurs, it is recorded. When writing data in column 3, address 2 is written because the originally specified memory A address 3 is occupied. If an overwrite occurs, it is recorded. The second loop ends and exits step S53.

In step S55, it is determined from the above records that this wrap still has coverage, and the process goes to step S57.

In step S57, since the maximum number of loops is 10 and the current number of loops is 2, which is less than 10, it returns to step S53 and loops again.

In this example, when executing step S53, the writing of column 2 in column 1 and column 4 in column 3 will continuously switch between address 2 and address 3 of memory A, so each time it wraps, an overwrite will occur, and the upper limit of the wrapping times is determined through step S55 to step S57, and then it returns to step S53 to execute the next wrapping. The last wrapping reaches the upper limit of 10 times in step S57, so an error is recorded in step S59 and the second stage sorting ends.

In the above description, each memory has 3 memory spaces. In the following description, each memory has 4 memory spaces. The more memory spaces a memory has, the lower the probability of overwriting, and thus the greater the chance of successfully finding a sort.

Refer to Figure 14, which describes an example of using a memory with 4 memory spaces (memory A and B each have 4 memory spaces) to wrap around after the arrangement in Figure 11, and performing verification and overwriting during wrapping, and finally successfully completing the sorting process. During wrapping, field 1, field 2, and field 3 are processed in sequence.

Check the reading of column 1. Column 1 reads from address 1 of memory A, column 2 reads from address 1 of memory B, column 3 reads from address 3 of memory A (because column 3 in Figure 11 is the last to be written to address 3 of memory A), and column 5 reads from address 2 of memory B. When reading, the data is also removed from the corresponding memory address, and at this time, address 2 of memory A still has data.

Next, check the writing of column 1. The data in row 1 is written to address 1 of memory A. The data in row 2 conflicts and cannot be written to address 2 of memory A. The data in row 3 is written to address 1 of memory B. The data in row 5 is written to address 2 of memory B. Note that the data in row 2 is randomly selected from the currently available space because the originally specified address 2 of memory A is occupied. Here, it is assumed that the random assignment result is to use address 4 of memory A. Since row 2 is overwritten here, it is recorded.

Check the reading of column 2. Row 1 reads from address 1 of memory A, row 3 reads from address 1 of memory B, row 4 reads from address 2 of memory A, and row 5 reads from address 2 of memory B. During the reading, the data is also removed from the corresponding memory address, and now there is still data at address 4 of memory A.

Next, check the writing of column 2. The data in row 1 is written to address 1 of memory A, the data in row 3 is written to address 3 of memory A, the data in row 4 is written to address 1 of memory B, and the data in row 5 is written to address 2 of memory B.

Check the reading of column 3. Row 1 reads from address 1 of memory A, row 3 reads from address 4 of memory A, row 4 reads from address 1 of memory B, and row 5 reads from address 2 of memory B. During the reading, the data is also removed from the corresponding memory address, and the data is still left at address 3 of memory A.

Next, check the writing of row 3. The data of row 1 is written to address 1 of memory A, the data of row 2 is written to address 1 of memory B, the data of row 4 is written to address 2 of memory A, and the data of row 5 is written to address 2 of memory B. The first loop ends and exits step S53.

In step S55, it is determined from the above records that this wraparound has coverage, and the process goes to step S57.

In step S57, assuming that the maximum number of loops is 10, the current number of loops is 1, which is less than 10, so return to step S53 to loop again.

In step S53, execute the second loop and use the result of the first loop to check the allocation and confirm that the allocation method has not changed, so any overwrite record is not recorded.

In step S55, it is determined that there is no overlap, the allocation is successful, and thus the second stage sorting is exited.

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 above embodiments, as well as changes known to technicians in this field, are still within the scope of the present invention.

S20: The first stage of allocation

S40: Second stage of allocation

S60: Update best results

S70: Determine whether the maximum number of repetitions has been reached

S80: Determine whether the allocation is successful

S90: Generate command file for reorganizing the decoder

Claims (4)

A method for improving the parallelism of LDPC reorganization decoder by re-arranging LDPC codes comprises the following steps: Provide two memories for the above LDPC reassembly decoder; Evenly distribute the non-zero elements of the above LDPC code matrix to the above two memories (S20); According to the above allocation method, write the above non-zero elements to the above two memories (S40); Update allocation method (S60); Determine whether the maximum number of recursions has been reached (S70); If the maximum number of recursions has not been reached, the process returns to the step of evenly allocating the non-zero elements to the two memories (S20); If the maximum number of recursions is reached, it is determined whether the allocation is successful (S80); If the allocation is successful, a scheduling file is generated (S90); and If the allocation fails, then it ends. The method for improving the parallelism of LDPC reorganization decoder by rearranging LDPC code as described in claim 1, wherein after reaching the maximum number of recursions or the data reading of each field is balanced, the method further includes the following steps: According to the above allocation method, in a certain column, a non-zero element is read from the corresponding memory in sequence, and after reading, the element is removed from the memory (S41); Determine whether all non-zero element data of this field have been read (S43); If the non-zero element data of this field has not been read, return to the above step of reading a non-zero element data in a field from the corresponding memory (S41); If all non-zero element data of this field are read, it is determined whether the expected write memory is full (S45); If any of the above memories is full, the allocation failure is recorded once and the process ends (S59); If the expected write memory is not full, then according to the above allocation method, write a non-zero element data in the above field into an available address in the corresponding memory in sequence (S47); Determine whether the non-zero element data of this field has been written (S49); If all non-zero element data of this field have not been written, return to the above step of determining whether any of the above memories is full (S45); If all non-zero element data of this field are written, it is determined whether the last field has been reached (S51); If the last field is not reached, return to the above step of sequentially reading a non-zero element in a field from the corresponding memory (S41); If the last field is reached, a wrap is performed to check whether the entire matrix has any address conflicts and needs to be reallocated (S53); Determine whether there is coverage during this orbit (S55); If there is no coverage during this orbit, it ends; If there is coverage during this orbit, it is determined whether the number of orbits reaches an upper limit (S57); If the number of loops does not reach the upper limit, return to the above loop execution step (S53); and If the number of loops reaches the upper limit, the allocation failure is recorded once and the process ends (S59). A method for improving the parallelism of an LDPC reorganization decoder comprises the following steps: providing two memories for the LDPC reorganization decoder; calculating the amount of non-zero element data in a field of the matrix of the LDPC code, respectively read from the two memories (S21); if the current field is a new field, storing the current overall allocation state as the best state (S23); judging whether the amount of non-zero element data in the field belonging to the two memories is equal (S24); S25); if the amount of non-zero element data read from the two memories is not equal, determine whether the backtracking times have reached the upper limit (S27); if the backtracking times have not reached the upper limit, randomly select a non-zero element that causes the imbalance, return to the previous non-zero element in the same column, and reprocess the column where it is located (S29); if the backtracking times have reached the upper limit, restore the previous best state (S31); if the amount of non-zero elements belonging to the two memories is equal, then Evenly and randomly distribute the data of the non-zero elements to be written into the two memories (S33); determine whether the last field is reached (S35); if the last field is not reached, return to the above method to calculate the non-zero element data in the next field and read the number from the two memories respectively (S21); if the last field is reached, use the writing information of the last few fields to know the memory where the data is stored, and then return to the beginning field to fill in the corresponding memory read, and record the previous The number of reads from the two memories in each field of the surface (S37); determines whether the maximum recursion number is reached, or the data reading of each field is balanced (S39); if the maximum recursion number is not reached, and the data reading of each field is not balanced, then the above calculation of the number of non-zero element data in a field of the LDPC code matrix read from the two memories (S21); and if the maximum recursion number is reached, or the data reading of each field is balanced, then the process ends. The method for improving the parallelism of the LDPC recombinant decoder as described in claim 3, wherein after reaching the maximum number of recursions or the data reading of each field is balanced, further comprises the following steps: in a certain field, a non-zero element is sequentially read from the corresponding memory according to the above allocation method, and the element is removed from the memory after reading (S41); it is determined whether all the non-zero element data of this field have been read (S43); if the non-zero element data of this field has not been read, then return to the above step of reading a non-zero element data in a certain field from the corresponding memory (S41 ...1); if the non-zero element data of this field has not been read, then return to the above step of reading a non-zero element data in a certain field from the corresponding memory (S41); if the non-zero element data of this field has not been read, then return to the After all non-zero element data of this field are written, it is determined whether the expected write memory is full (S45); if any of the above memories are full, the allocation failure is recorded once and the process ends (S59); if the expected write memory is not full, a non-zero element data in the above field is sequentially written into an available address in the corresponding memory according to the above allocation method (S47); it is determined whether the non-zero element data of this field is written (S49); if all non-zero element data of this field are not written, it returns to the step of determining whether any of the above memories is full (S45); If all non-zero element data of this field are written, it is determined whether the last field has been reached (S51); If the last field is not reached, return to the above step of sequentially reading a non-zero element in a certain field from the corresponding memory (S41); If the last field is reached, a wrap is performed to check whether the entire matrix has any address conflicts and needs to be reallocated (S53); Determine whether there is coverage during this orbit (S55); If there is no coverage during this orbit, it ends; If there is coverage during this orbit, it is determined whether the number of orbits reaches an upper limit (S57); If the number of loops does not reach the upper limit, the process returns to the above loop execution step (S53); and If the number of loops reaches the upper limit, the allocation failure is recorded once and the process ends (S59).

Images