TWI552533B - Low density parity check decoding method performing on general graphic processing unit - Google Patents

Description

Low density parity check decoding method performed on a flux graphics processor

The present invention relates to a parallel data processing technique, and more particularly to a low density parity check decoding method and decoding apparatus implemented in a flux graphics processor.

Since the Low Density Parity Check (LDPC) code is an error correction code that can achieve a performance level similar to that of the Shannon channel, LDPC codes are widely used in many communication system standards today. , such as the IEEE 802.11n-based WiFi system, the IEEE 802.3-based Ethernet system, the IEEE 802.16e-based WiMAX system, or the Digital Video Broadcasting-Satellite Transmission 2nd generation (DVB-S2) system. and many more. Although LDPC has relatively good channel error checking and correction capability in channel coding, the LDPC decoding process requires repetitive iterative loop operations to obtain decoding results. Therefore, in the case of using a large parity check matrix to assist in decoding operations, the decoding process of the LDPC requires a large amount of hardware computing power and hardware resources to support.

General-purpose computing on graphics processing units (GPGPUs) utilize graphics processors that process graphics tasks to compute general-purpose computing tasks that would otherwise be handled by the central processing unit, and these general-purpose calculations often have nothing to do with graphics processing. Further, the flux graphics processor is a multi-core architecture that provides powerful computing power and high data throughput by simultaneously executing a large number of threads. It is expected that performing low density parity check decoding on a flux graphics processor will greatly improve decoding performance.

However, in conventional practice, flux graphics processors typically only support regular low density parity check decoding. For irregular low-density parity check decoding, decoding performance is often limited by the difficulty and complexity of data structure and memory access design. Accordingly, those skilled in the art are directed to developing a design architecture that is more widely used and that can improve the decoding performance of a flux graphics processor to perform low density parity check decoding.

In view of this, the present invention provides a low-density parity check decoding method and a decoding apparatus performed on a flux graphics processor, which can obtain greater parallelism of operations and further improve decoding performance, and can support irregular low-density parity check. decoding.

The present invention provides a low density parity check code decoding method performed by a flux graphics processor, the stream multiprocessor of the flux graphics processor comprising a plurality of thread processing cores and shared memory. The method includes the following steps. Based on the M edges in the Tanner graph associated with the parity check matrix, each edge is mapped to one of the plurality of threads, such that each thread corresponds to one of the plurality of edge identifiers . M is an integer greater than 1 and these edges are connected between a plurality of check nodes and a plurality of bit nodes. When one of the threads is executed, the data in the shared memory is accessed according to the side identification code of one of the threads to update the plurality of delivery messages respectively stored in the shared memory corresponding to the sides.

In an embodiment of the present invention, the step of accessing the data in the shared memory by the side identification code according to one of the threads to update the transfer message respectively corresponding to the plurality of edges stored in the shared memory includes: Reading at least one target value index value from the M value index values according to one of the thread identification codes, and transmitting from the M first directions stored in the shared memory according to the target value index value At least one first target delivery message is read from the message.

In an embodiment of the present invention, the value index array stored in the shared memory stores value index values respectively corresponding to the plurality of edges, and the bit points stored in the shared memory are stored in the checkpoint message array. There are messages in the first direction corresponding to the edges respectively.

In an embodiment of the present invention, the array storage location of the value index value in the value index array is determined according to the connection state of the map, and the bit point to the checkpoint message array corresponds to the same Check the first direction of the node to pass the message adjacent to the array.

In an embodiment of the present invention, the edge identification code according to one of the foregoing threads reads the target value index value from the value index value, and stores the value in the shared memory according to the target value index value. The step of reading the first target delivery message in the first direction delivery message comprises: reading the target extraction from the i-th index value in the value index array according to the edge identification code of one of the threads A value index, where i is equal to the side identifier of one of the threads. According to the ith value index value, the first target delivery message is read from the bit point to the jth first direction delivery message in the checkpoint message array, where j is equal to the ith value index value. Retrieving the first target delivery message from the bit point to the checkpoint message array continuously in response to sequentially reading the array of index indexes until one of the value index values meeting the preset condition is read to stop The bit direction is read to the first direction in the checkpoint message array to deliver the message. One of the value index values that meet the preset condition is equal to one of the thread's side identifiers.

In an embodiment of the present invention, the step of accessing the data in the shared memory by the edge identification code according to one of the threads to update the transfer message respectively corresponding to the plurality of edges stored in the shared memory further includes Reading the target location index value from the M location index values according to the identifier of one of the threads, and updating the second of the M second direction delivery messages with the target location index value and the first target delivery message described above The target delivers the message. This target location index value indicates the array storage location of the second target delivery message.

In an embodiment of the invention, the location index array stores location index values respectively corresponding to the edges, and the checkpoint-to-bit dot message array stores second direction transfer messages respectively corresponding to the edges.

In an embodiment of the present invention, the array storage location of the location index value in the location index array is determined according to the connection state of the graph, and the checkpoint to the bitpoint message array corresponds to the same bit node. The second direction passes the messages adjacent to each other.

In an embodiment of the present invention, the step of reading the target location index value from the location index value according to the identifier of one of the threads according to the thread includes: reading the location index according to the edge identifier of one of the threads The i-th position index value in the array is taken as the target position index value, where i is equal to one of the thread's side identification codes.

In an embodiment of the present invention, the step of updating the second target delivery message in the second direction delivery message by using the target location index value and the first target delivery message comprises: calculating an update message according to the first target delivery message, And replacing the kth second direction delivery message indicated by the target location index value in the checkpoint to the bit point message array by using the update message to update the second target delivery message. k is equal to the target position index value.

Based on the above, by mapping each side of the Tanner map to one of the plurality of threads, respectively, the flux graphics processor can process the update operation of the message in the low density parity check code decoding process in parallel. The plurality of thread processing cores of the flux graphics processor can pass the first element in the checkpoint array to read the message by reading a value index array. In other words, each thread processing core can access the data in the shared memory according to the side identifier of the thread to update the plurality of delivery messages respectively stored in the shared memory corresponding to the edges. Thus, the present invention can obtain greater computational parallelism than conventional methods of assigning data nodes (including bit nodes and check nodes) to different threads to perform iterative operations, respectively. In addition, the data processing method based on the edge on the Tanner map of the present invention can simultaneously support the decoding of rules and irregular low density parity check codes.

The above described features and advantages of the invention will be apparent from the following description.

Based on the characteristics that the number of edges on the Tanner graph is larger than the number of nodes, the present invention proposes an edge-based arithmetic processing architecture. Compared with the node-based processing method on the current flux graphics processor, the present invention can further improve the parallelism of performing low-density parity check decoding on the flux graphics processor to improve decoding performance. .

FIG. 1 is a schematic diagram of a decoding apparatus according to an embodiment of the invention. The decoding device 100 can be configured in a wireless communication receiving device, for example, a receiver using the IEEE 802.11n standard, but the invention is not limited thereto. When the decoding device 100 receives the received data from the communication channel, the decoding device 100 may perform decoding based on the low density parity check algorithm to perform a correction procedure on the received data received from the communication channel. In the present exemplary embodiment, the decoding device 100 includes a flux graphics processor 20 and a storage unit 30.

In the present exemplary embodiment, the flux graphics processor 20 includes a plurality of stream multiprocessors SM_1~SM_P (P is a positive integer), a cache memory 21, and a dynamic random access memory 22. Each of the stream multiprocessors SM_1~SM_P is configured to process a plurality of threads, and each of the stream multiprocessors SM_1~SM_P includes a respective shared memory 25_1~25_P. In addition, the stream multiprocessors SM_1~SM_P respectively comprise a plurality of thread processing cores, and the thread processing cores belonging to the same stream multiprocessor can communicate or transfer data through the shared memory. For example, the stream multiprocessor SM_1 includes a thread processing core C1_1~C1_Q, and the thread processing cores C1_1~C1_Q can jointly access the shared memory 25_1. Similarly, the stream multiprocessor SM_2 includes a thread processing core C2_1~C2_Q, and the thread processing cores C2_1~C2_Q can jointly access the shared memory 25_1.

In addition, although not shown in FIG. 1, the stream multiprocessors SM_1~SM_P may further include other components such as a warp scheduler, which is not limited by the present invention. In addition, the stream multiprocessors SM_1~SM_P can share the cache memory 21, and the cache memory 21 can be used to transfer data between threads. The thread processing cores in the stream multiprocessors SM_1~SM_P are configured to execute a large number of threads in parallel. In the present exemplary embodiment, the flux graphics processor 20 can parallelize a large number of threads according to the same instruction using a single-instruction multiple thread (SIMT) technique.

The storage unit 30 is, for example, any type of fixed or removable random access memory (RAM), read-only memory (ROM), flash memory (Flash memory), hard A disc or other similar device or a combination of these devices, but the invention is not limited thereto. The storage unit 30 is coupled to the flux graphics processor 20 and stores a plurality of instructions that the flux graphics processor 20 executes to provide a low density parity check decoding function.

In the present exemplary embodiment, flux graphics processor 20 executes the instructions to perform the following steps. Each of the sides corresponds to one of the plurality of threads based on the M edges in the tannogram associated with the parity check matrix, such that each thread corresponds to one of the plurality of side identification codes. When one of the threads is executed, the data in the shared memory is accessed according to the side identifier of one of the threads to update the plurality of delivery messages respectively stored in the shared memory corresponding to the edges.

The low density parity check decoding method of the present invention will be described in further detail below. 2A is a schematic diagram of a parity check matrix 210, and FIG. 2B is a schematic diagram of a relationship between bit nodes and check nodes in the parity check matrix 210. As shown in FIG. 2A, 8 rows of the parity check matrix 210 respectively correspond to the bit nodes B0, B1, B2, B3, B4, B5, B6, B7; and 4 columns of the parity check matrix 210 respectively correspond to the check node C0. , C1, C2, C3. The decoding process of the low density parity check performs matrix multiplication of the probability information and the parity check matrix 210 to obtain a decoding result.

Referring to FIG. 2B, in general, the parity check matrix 210 can be represented as a Tanner graph, and the Tanner graph also includes bit nodes B0 B B7 and check nodes C0 C C3. As shown in FIG. 2B, when there is an edge between the bit nodes B0 B B7 and the check nodes C0 C C3 (that is, there is a connection between the bit node and the check node), the bit node and the check are performed. The nodes take turns to perform operations. For example, bit node B0 is connected to check node C0 via edge E1. After the respective operations of the bit nodes B0 to B7 and the check nodes C0 to C3 (which are connected to each other in FIG. 2B) shown in FIG. 2B are completed, the respective operation results are temporarily stored in the same Memory unit or memory location.

In the present exemplary embodiment, the flux graphics processor 20 performs a low density parity check decoding procedure according to the link state of the graph, wherein the low density parity check decoding program includes a horizontal decoding program and a vertical decoding program. Specifically, in the horizontal decoding process, the flux graphics processor 20 calculates a delivery message transmitted by the check nodes C0 to C3 to the bit nodes B0 to B7. In the vertical decoding process, the flux graphics processor 20 calculates the delivery messages that the bit nodes B0-B7 pass to the check nodes C0-C3. These delivery messages are transmitted along the edges in the tanner. For example, based on the link of the edge E1, it is the transfer message M12 that the check node C0 transfers to the bit node B0, and the transfer message M11 that the bit node B0 transmits to the check node C0.

Based on the above description of the low density parity check decoding process, in the decoding process, the flux graphics processor 20 must use two arrays to store a plurality of first direction transfer messages and a plurality of second direction transfer messages, respectively. These iterative operations are performed using these delivery messages in accordance with the decoding algorithm. For example, the flux graphics processor 20 may employ a Sum-Product Algorithm, a Min-Sum Algorithm, or a bit-flipping algorithm. The invention does not limit which algorithm is used.

It should be noted that, in an exemplary embodiment of the present invention, the first direction delivery message is a delivery message transmitted by the bit node to the check node, and may also be referred to as a bit-to-check massage. ). The second direction delivery message is a delivery message that the inspection node transmits to the bit node, which may also be referred to as a check-to-bit massage. In addition, the array storing the first direction transfer message is referred to as a bit point to checkpoint array, and the array storing the second direction transfer message is referred to as a checkpoint to bit point array. It is worth mentioning that in the exemplary embodiment of the present invention, the calculation of the message passing by each side corresponds to a different thread. Accordingly, if the low-density parity check decoding is performed using the flux graphics processor 20 as shown in FIG. 1, the respective thread processing cores of the flux graphics processor 20 can separately calculate the transfer messages on the different sides.

FIG. 3 is a flowchart of a low density parity check decoding method according to an embodiment of the invention. In the present exemplary embodiment, the low density parity check decoding method is applicable to the decoding device 100 as illustrated in FIG. 1, but the present invention is not limited thereto. Referring to FIG. 3, in step S301, each side is corresponding to one of the plurality of threads based on the M edges in the tannogram related to the parity check matrix, so that each thread corresponds to the plurality of side identification codes. one. Where M is an integer greater than 1 and the edges are connected between a plurality of check nodes and a plurality of bit nodes. In other words, the calculations for the delivery messages for each edge will be assigned to different threads, respectively. Taking the Tanah diagram of FIG. 2B as an example, there are 12 edges between the check nodes C0~C3 and the bit nodes B0~B7, so the message is transmitted on the 12 sides (including the first direction to transmit the message and the second The calculation of the direction transfer message will be completed by the different thread processing cores simultaneously executing different threads. For example, in the horizontal decoding process, the update calculation of the second direction delivery message will correspond to 12 distinct threads, respectively, and the 12 threads each have a respective side identification code.

Then, in step S302, when one of the threads is executed, the data in the shared memory is accessed according to the side identification code of one of the threads to update the plurality of stored in the shared memory respectively corresponding to the edges. Pass the message. Specifically, in the horizontal decoding process, the thread processing core may read at least one first direction transfer message required to update one of the second direction transfer messages according to the side identifier of the thread.

In order to explain the present invention in detail, another embodiment will be listed below to explain in detail how to access an appropriate delivery message in accordance with the side identifier of the thread for update calculation. FIG. 4 is a flowchart of a low density parity check decoding method according to an embodiment of the invention. In the present exemplary embodiment, the low density parity check decoding method is applicable to the decoding device 100 as illustrated in FIG. 1, but the present invention is not limited thereto.

Referring to FIG. 4, in step S401, each side is corresponding to one of the plurality of threads based on the M edges in the tannogram associated with the parity check matrix, so that each thread corresponds to the plurality of side identification codes. one. Next, in step S402, at least one target value index value is read from the M value index values according to one of the thread identification codes, and is stored in the shared memory according to the target value index value. At least one first target delivery message is read from the M first direction delivery messages.

In the exemplary embodiment, the value index array stored in the shared memory stores the value index corresponding to the plurality of edges, and the bit points stored in the shared memory are stored in the checkpoint message array respectively. The first direction of these edges conveys the message. The value index value is used to indicate that the thread processing core should read the element from the bit point to which array in the checkpoint array. It should be particularly noted that the array storage location of the value index index in the value index array depends on the link state of the map, and the bit direction to the checkpoint message array corresponds to the first direction of the same check node. Pass the message adjacent to the arrangement. Based on the arrangement of the above-mentioned value index array and the array storage location of the index value, each thread can read the transfer message required to calculate a specific edge from the bit point to the checkpoint array.

In more detail, according to the side identifier of one of the threads, the thread processing core can read the target value index from the i-th index value in the value index array, where i is equal to the thread. One of the side identification codes. For example, if the edge identification code of the thread is '1', the thread processing core can read at least one target value index from the first value index value in the value index array. Wherein the side identification code is an integer. Then, according to the ith value index value, the thread processing core can start reading the first target delivery message from the bit point to the jth first direction delivery message in the checkpoint message array, where j is equal to the i th Value index value. Thereafter, the thread processing core can begin reading the first target delivery message from the bit point to the jth first direction delivery message in the checkpoint message array.

The thread processing core responds by sequentially reading the array of index indexes and continuously reading the first target delivery message from the bit point to the checkpoint message array until the value index value corresponding to the preset condition is read. First, the message is transmitted in a first direction by stopping reading the bit point to the checkpoint message array. One of the value index values that meet the preset condition is equal to one of the thread's side identifiers. For example, when the execution thread processing core of the thread whose execution side ID is '1' is read to the value index value of '1', the thread processing core will stop reading the value index array and stop at the same time. Continue to read out the first direction to deliver the message. Thus, when one of the threads is executed, each thread that computes the second direction of each side of the message is readable to retrieve the correct first direction delivery message.

Returning to the flow shown in FIG. 4, in step S403, the target location index value is read from the M location index values according to the identifier of one of the threads, and the target location index value is used to communicate the message with the first target. Updating the second target delivery message in the M second direction delivery messages. This target location index value indicates the array storage location of the second target delivery message.

In the exemplary embodiment, the location index array stores location index values respectively corresponding to the edges, and the checkpoint-to-bit point message array stores a second direction delivery message corresponding to the edges respectively. In addition, the array storage location of the location index values in the location index array is determined according to the connection state of the Tanner diagram, and the second direction delivery message corresponding to the same bit node in the checkpoint-to-bitpoint message array is adjacently arranged. Based on the arrangement of the location index array and the location storage location of the location index value, each thread can write the calculated update delivery message to the correct array storage location to complete the update of the second direction delivery message.

In more detail, according to the side identifier of one of the threads, the thread processing core can read the i-th position index value in the position index array as the target position index value, where i is equal to one of the threads. Side identification code. For example, assuming that the side identifier of the thread is '1', the thread processing core can read the first position index value in the position index array as the target position index value. Wherein the side identification code is an integer. Afterwards, the thread processing core calculates the update message according to the first target delivery message, and replaces the kth second direction delivery message indicated by the target location index value in the checkpoint to the bit point message array by using the update message to update the The second target passes the message, where k is equal to the target location index value.

It is worth mentioning that low-density parity check codes are generally described by a parity check matrix. The number of '1's in each row in the parity check matrix is called the row weight of the row, and the number of '1's in each column is The number is called the column weight of the column. The low-density parity check code of the same parity check matrix with the same row weight and column weight is called a regular low-density parity check code (the parity check matrix is regular), otherwise it is called irregular (irregular) Low density parity check code (parity check matrix is irregular). Since the low density parity check decoding of the present invention is parallelized on an edge basis, the low density parity check decoding method of the present invention is applicable to regular and irregular low density parity check codes without reducing irregularities. Low-density parity check decoding performance.

Compared to the node-based design architecture, the edge-based architecture of the present invention allows a single thread to be responsible for the update operation of the message passing on a single side of the graph. Therefore, since the number of edges on the Tanner map is usually larger than the number of nodes, the operational parallelism of the low-density parity check decoding method of the present invention can be improved, thereby improving decoding performance. Based on the foregoing description, the edge-based processing flow of the present invention requires four arrays, namely an index index array, a bit point to checkpoint array, a position index array, and a checkpoint to bit point array. The value index array is used to control the thread to access the correct first target delivery message from the bit point to the plurality of first direction in the checkpoint array. Each thread will continuously read out at least one first target delivery message from the bit point to the checkpoint array until a value index value equal to its own side identification code is read.

FIG. 5A and FIG. 5B are schematic diagrams showing an example of a data structure of a data structure and a thread according to an embodiment of the invention. It should be noted that FIG. 5A and FIG. 5B are described by taking the Tanah diagram of FIG. 2B as an example, but the present invention is not limited thereto. Referring first to FIG. 5A, the thread t0 is responsible for updating and calculating the message transmitted on the edge E1, and the edge identifier of the thread t0 is '0'. In step 1, according to the side identification code '0', the thread t0 reads out the value index value '1' corresponding to the edge identification code '0' from the array index array a1. In step 2, according to the value index value '1', the thread t0 reads from the bit point to the checkpoint array a2 the first direction transfer message L _B corresponding to the array index position corresponding to the value index value '1'. _{1 → C0} .

Thereafter, in step 3, the thread t0 continues to read the value index value '2' after the value index value '1' from the value index array a1. In step 4, according to the value index value '2', the thread t0 reads from the bit point to the checkpoint array a2 the first direction transfer message L _B corresponding to the array storage location corresponding to the value index value '2'. _{2 → C0} . In step 5, the thread t0 continues to sequentially read the value index array a1 until the value index value '0' is read. In step 6, the thread t0 calculates the update message by using the first direction transfer message L _{B 1 →C0} and the first direction transfer message L _{B 2 →C0} , and reads the position index according to the own side identifier code '0'. The target position index value '0' in the array a3. In step 7, the thread t0 can use the update message to write to the second direction transfer message corresponding to the target position index value '0' of the array storage location, thereby obtaining the updated second direction transfer message L _{C 0 → B0} .

Similarly, FIG. 5B illustrates the flow of the thread t1 calculating the second direction transfer message L _{C 0 →B1} . Referring to FIG. 2B and FIG. 5B, the thread t1 is responsible for updating and calculating the delivery message on the edge E2, and the edge identifier of the thread t1 is '1'. The thread t1 can obtain the updated second direction delivery message L _{C 0 →B4} according to the operation and data access procedure in steps 1 to 7. Those skilled in the art should refer to the foregoing description of FIG. 5A to derive the operation flow of the thread t1, and no further details are provided herein.

FIG. 6 is a schematic diagram showing an example of a data structure of a data structure and a thread according to an embodiment of the invention. It should be noted that FIG. 6 is described by taking the Tanah diagram of FIG. 2B as an example, but the present invention is not limited thereto. Referring to FIG. 6, the threads t0~t9 are respectively responsible for updating and calculating the message transmitted on each side of the Tanner graph of FIG. 2B, and the side identifiers of the threads t0~t9 are respectively '0'~'9. '. According to the connection state of the nodes in the Tanner diagram of FIG. 2B, the arrangement of the value index values is stored in the value index array a1 as shown in FIG. 6, and the position index value is arranged in the position index as shown in FIG. 6. Array a3. Figure 6 shows the data access flow for all threads t0~t9. Those skilled in the art should refer to the foregoing description of FIG. 5A to derive the operation flow of the threads t0~t9, and no further details are provided herein.

It is worth mentioning that, based on the data access process shown in FIG. 6, the memory of the index array, the bit point to the checkpoint array, and the position index array for parallelizing multiple threads is known. Access is very agglomerated, and this memory access aggregation phenomenon can greatly highlight the advantages of using a flux graphics processor to perform the low density parity check decoding method of the present invention. In particular, in an exemplary embodiment, the value index array and the bit point to checkpoint array are well suited for storing L1 cache memory in a streaming multiprocessor. That is to say, the present invention can improve the decoding performance of performing low density parity check decoding on a flux graphics processor.

In summary, the present invention enables the flux graphics processor to parallelize the update of the message transmitted in the low density parity check code decoding process by respectively mapping each side of the graph to one of the plurality of threads. Operation. Compared with the conventional decoding method in which data nodes (including bit nodes and check nodes) are assigned to different threads to respectively perform iterative operations, the present invention can obtain greater parallelism of operations. In addition, the data processing method based on the edge on the Tanner map of the present invention can simultaneously support the decoding of rules and irregular low density parity check codes. Furthermore, based on the setting of the index array and the location index array according to the present invention, the memory accessing coalescing and the large amount of repeated data access characteristics can be achieved without rearranging the transmitted messages to further Reduces the data read time when the flux graphics processor performs low-density parity check decoding.

Although the present invention has been disclosed in the above embodiments, it is not intended to limit the present invention, and any one of ordinary skill in the art can make some changes and refinements without departing from the spirit and scope of the present invention. The scope of the invention is defined by the scope of the appended claims.

100‧‧‧ decoding device
20‧‧‧ flux graphics processor
30‧‧‧ storage unit
21‧‧‧ Cache memory
22‧‧‧ Dynamic Random Access Memory
SM_1~SM_P‧‧‧Streaming Multiprocessor
25_1~25_P‧‧‧Shared memory
C1_1~C1_Q, C2_1~C2_Q‧‧‧Thread Processing Core
210‧‧‧Parity check matrix
B0~B7‧‧‧ bit node
C0~C3‧‧‧Check node
E1, E2‧‧‧
M11, M12‧‧‧ passing the message
S301~S302, S401~S403‧‧‧ steps
T0~t9‧‧‧ thread
A1‧‧‧value index array
A2‧‧‧ bit points to checkpoint array
A3‧‧‧Location Index Array
A4‧‧‧Checkpoint to bit array

FIG. 1 is a schematic diagram of a decoding apparatus according to an embodiment of the invention. 2A is a schematic diagram of a parity check matrix. 2B is a schematic diagram of the relationship between a bit node and a check node in a parity check matrix. FIG. 3 is a flowchart of a low density parity check decoding method according to an embodiment of the invention. FIG. 4 is a flowchart of a low density parity check decoding method according to an embodiment of the invention. FIG. 5A is a schematic diagram showing an example of a data structure of a data structure and a thread according to an embodiment of the invention. FIG. 5B is a schematic diagram showing an example of a data structure of a data structure and a thread according to an embodiment of the invention. FIG. 6 is a schematic diagram showing an example of a data structure of a data structure and a thread according to an embodiment of the invention.

S301~S302‧‧‧Steps

Claims (10)

A low density parity check (LDPC) decoding method performed by a flux graphics processor, the stream multiprocessor of the flux graphics processor comprising a plurality of thread processing cores and a shared memory, the method comprising : based on M edges in a Tanner graph related to a parity check matrix, each of the edges is corresponding to one of the plurality of threads, so that each of the threads corresponds to One of a plurality of side identification codes, wherein M is an integer greater than 1 and the edges are connected between the plurality of check nodes and the plurality of bit nodes; and when one of the threads is executed, according to the execution One of the side identification codes accesses a piece of data in the shared memory to update a plurality of delivery messages stored in the shared memory corresponding to the sides. The low density parity check decoding method according to claim 1, wherein the data in the shared memory is accessed according to the side identification code of one of the threads to be updated and stored in the shared memory. The step of respectively transmitting the message to the edges includes: reading, according to the side identifier of the one of the threads, at least one target value index value from the M value index values, and according to the The at least one target value index value reads at least one first target delivery message from the M first direction delivery messages stored in the shared memory. The low-density parity check decoding method of claim 2, wherein a value index array stored in the shared memory stores the value index values respectively corresponding to the edges, and is stored in the The one-point-to-checkpoint message array of the shared memory stores the first direction-passing messages respectively corresponding to the edges. The low-density parity check decoding method described in claim 3, wherein the array storage position of the value index values in the value index array is determined according to the connection state of the TANNA map, and the bit point is The first direction of the checkpoint message array corresponding to the same check node is transmitted adjacent to the message. The low-density parity check decoding method according to claim 3, wherein the at least one target value index value is read from the value index values according to the side identifier of one of the threads. And the step of reading the at least one first target delivery message from the first direction delivery messages stored in the shared memory according to the at least one target value index value comprises: according to the threads The side identification code, the at least one target value index is read from the ith index index value in the value index array, where i is equal to the side identifier of one of the threads; Determining, according to the i-th index value, the at least one first target delivery message from the bit-point to the j-th first direction delivery message in the checkpoint message array, where j is equal to the i-th value An index value; and continually reading the array of index indexes in sequence, and continuously reading the at least one first target delivery message from the bit point to the checkpoint message array until a predetermined condition is met The value index One of the values to stop reading the bit point to the first direction in the checkpoint message array to deliver the message, wherein one of the value index values is equal to the side of one of the threads Identifier. The low-density parity check decoding method according to claim 2, wherein the data in the shared memory is accessed according to the side identification code of one of the threads to be updated and stored in the shared memory. The step of transmitting the messages corresponding to the edges further includes: reading a target location index value from the M location index values according to the identifier of one of the threads, and using the target location index value and The at least one first target delivery message updates a second target delivery message of the M second direction delivery messages, wherein the target location index value indicates an array storage location of the second target delivery message. The low-density parity check decoding method according to claim 6, wherein a position index array stores the position index values respectively corresponding to the edges, and a check point-to-bit point message array is stored separately. The messages are delivered to the second directions corresponding to the edges. The low-density parity check decoding method of claim 7, wherein the array storage location of the location index values in the location index array is determined according to a connection state of the TAN mapping, the checkpoint to a bit point The second direction of the message array corresponding to the same bit node is adjacent to the message. The low density parity check decoding method according to claim 7, wherein the step of reading the target location index value from the location index values according to the identifier of one of the threads comprises: The side identification code of one of the threads reads the i-th position index value in the position index array as the target position index value, where i is equal to the side identification code of one of the threads. The low density parity check decoding method according to claim 7, wherein the target location index value and the at least one first target delivery message are used to update the second target delivery message in the second direction delivery messages. The step includes: calculating an update message according to the at least one first target delivery message, and replacing the kth second direction delivery message indicated by the target location index value in the checkpoint to bit point message array by using the update message To update the second target delivery message, where k is equal to the target location index value.