Low density parity check decoding method performing on general graphic processing unit and decoding appratus
AssigneeWinbond Electronics Corp.
InventorsBo-Cheng Lai, Tsou-Han Chiu
Life of this patent
Estimating the term…
Abstract
A low density parity check (LDPC) decoding method and a decoding apparatus are provided. The method includes following steps. Based on M edges of a Tanner graph related to a parity check matrix, each of the edges is associated with one of a plurality of threads, such that each of the threads is corresponding to one of a plurality of edge identifies. When executing one of the threads, data in a shared memory is accessed according to the edge identifier of the one of the threads, so as to update a plurality of passing massages respectively corresponding to the edges in the shared memory. Thereby, high computation parallelism and fully-coalesced data accesses can be achieved.
Claims20
A low density parity check (LDPC) decoding method performed on a general-purpose computing on graphics processing unit (GPGPU), wherein a streaming multiprocessor of the GPGPU comprises a plurality of thread computing cores and a shared memory, the method comprising:
- based on M edges of a Tanner graph related to a parity check matrix, associating each of the edges with one of a plurality of threads, such that each of the threads is corresponding to one of a plurality of edge identifiers, wherein M is an integer greater than 1, and the edges are connected between a plurality of check nodes and a plurality of bit nodes;
- and
- when executing one of the threads, accessing data in the shared memory according to an edge identifier of the one of the threads, so as to update a plurality of passing massages which are respectively corresponding to the edges and stored in the shared memory.
A decoding apparatus, comprising:
- a general-purpose computing on graphics processing unit (GPGPU), comprising a plurality of streaming multiprocessors, wherein each of the streaming multiprocessors comprises a plurality of thread computing cores and a shared memory;
- and
- a storage unit, coupled to the GPGPU and storing a plurality of instructions, wherein the GPGPU executes the instructions to:
- based on M edges of a Tanner graph related to a parity check matrix, associate each of the edges with one of a plurality of threads, such that each of the threads is corresponding to one of a plurality of edge identifiers, wherein M is an integer greater than 1, and the edges are connected between a plurality of check nodes and a plurality of bit nodes;
- and
- when executing one of the threads, access data in the shared memory according to an edge identifier of the one of the threads, so as to update a plurality of passing massages which are respectively corresponding to the edges and stored in the shared memory.
Dependencies are inferred from the claim text.