Method, apparatus, computer program product and device providing semi-parallel low density parity check decoding using a block structured parity check matrix
View Patent ↗The invention relates to low density parity check decoding. A method for decoding an encoded data block is described. Encoded data block comprising data sub-blocks are stored. Decoding is performed in a pipelined manner using an irregular, block-structured parity check matrix, where at least two data sub-block matrices of the parity check matrix are read from and written in each of a plurality of clock cycles. The reading and writing of the data sub-blocks is evenly distributed between at least two area of a memory. The decoding is performed with shift values which eliminate cycles at or below a predetermined threshold length. An apparatus, computer program product and device are also described.
1. A method comprising:
storing an encoded data block comprising data sub-blocks; and
decoding the data block in a pipelined manner using an irregular, block-structured parity check matrix,
where at least two data sub-block matrices of the parity check matrix are read from and written in each of a plurality of clock cycles,
where the reading and writing of the data sub-blocks are evenly distributed between at least two areas of a memory, and
where the decoding is performed with shift values which eliminate cycles at or below a predetermined threshold length.
2. The method of claim 1 , where a pipeline comprises at least three layers.
3. The method of claim 1 , where the decoding is performed with a permuter that uses shift value memory modules to store the position of non-zero sub-block matrices and the shift value/relative offsets.
4. The method of claim 3 , where the shift value memory modules comprise read only memory.
5. The method of claim 1 , where the threshold length is 8.
6. The method of claim 1 , where there is full processing parallelism for one layer.
7. The method of claim 1 , where a first area of memory stores data from odd block columns of the parity check matrix and a second area of memory stores data from even block columns of the parity check matrix.
8. The method of claim 1 , where data throughput is at least 1 Gbits/sec.
9. An apparatus comprising:
memory configured to store an encoded data block comprising data sub-blocks;
processors configured to decode the data block in a pipelined manner using an irregular, block-structured parity check matrix,
where at least two data sub-block matrices of the parity check matrix are read from and written in each of a plurality of clock cycles,
where the reading and writing of the data sub-blocks are evenly distributed between at least two areas of the memory, and
where the decoding is performed with shift values which eliminate cycles at or below a predetermined threshold length.
10. The apparatus of claim 9 , where a pipeline comprises at least three layers.
11. The apparatus of claim 9 , where the decoding is performed with a permuter that uses shift value memory modules to store the position of non-zero sub-block matrices and the shift value/relative offsets.
12. The apparatus of claim 11 , where the shift value memory modules comprise read only memory.
13. The apparatus of claim 9 , where the threshold length is 8.
14. The apparatus of claim 9 , where there is full processing parallelism for one layer.
15. The apparatus of claim 9 , where a first area of memory stores data from odd block columns of the parity check matrix and a second area of memory stores data from even block columns of the parity check matrix.
16. The apparatus of claim 9 , where data throughput is at least 1 Gbits/sec.
17. The apparatus of claim 9 , where the apparatus is embodied in at least one integrated circuit.
18. A non-transitory computer readable medium tangibly embodied with a program of machine-readable instructions executable by a digital processing apparatus to perform operations comprising:
storing an encoded data block comprising data sub-blocks; and
decoding the data block in a pipelined manner using an irregular, block-structured parity check matrix,
where at least two data sub-block matrices of the parity check matrix are read from and written in each of a plurality of clock cycles,
where the reading and writing of the data sub-blocks are evenly distributed between at least two areas of a memory, and
where the decoding is performed with shift values which eliminate cycles at or below a predetermined threshold length.
19. The medium of claim 18 , where a pipeline comprises at least three layers.
20. The medium of claim 18 , where the decoding is performed with a permuter that uses shift value memory modules to store the position of non-zero sub-block matrices and the shift value/relative offsets.
21. The medium of claim 20 , where the shift value memory modules comprise read only memory.
22. The medium of claim 18 , where there is full processing parallelism for one layer.
23. The medium of claim 18 , where a first area of memory stores data from odd block columns of the parity check matrix and a second area of memory stores data from even block columns of the parity check matrix.
24. A device comprising:
at least two means for storing data sub-blocks of an encoded data block;
means for decoding the data block in a pipelined manner using an irregular, block-structured parity check matrix,
where at least two data sub-block matrices of the parity check matrix are read from and written in each of a plurality of clock cycles,
where the reading and writing of the data sub-blocks are evenly distributed between the at least two storing means, and
where the decoding is performed with shift values which eliminate cycles at or below a predetermined threshold length.
25. The device of claim 24 , where a pipeline comprises at least three layers.