# US 2012/0240003 A1 · Method, Apparatus, Computer Program Product and Device Providing Semi-Parallel Low Density Parity Check Decoding Using a Block Structured Parity Check Matrix

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0240003 A1
- Document ID: US20120240003A1
- Status: Published application
- Kind: A1
- Application number: 13/479,745
- Filed: 2012-05-24
- Published: 2012-09-20
- Earliest claimed: 2007-10-24
- Assignees: Core Wireless Licensing S.a.r.l.
- Inventors: Predrag Radosavljevic; Marjan Karkooti; Alexandre de Baynast; Joseph R. Cavallaro
- Web page: https://patentgrep.com/patent/US20120240003A1

## CPC

- H03M 13/1148: {Structural properties of the code parity-check or generator matrix}
- H03M 13/1137: {Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel}
- H03M 13/114: {Shuffled, staggered, layered or turbo decoding schedules}
- H03M 13/6566: {Implementations concerning memory access contentions}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

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.

## Claims

### Claim 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,
wherein shift values used in the data sub-blocks are optimized by minimizing a cost function to at least reduce a number of cycles of a predetermined length, 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, and the reading and writing of the data sub-blocks are evenly distributed between at least two areas of a memory.

### Claim 2 (depends on 1)

The method of claim 1, where a pipeline comprises at least three layers.

### Claim 3 (depends on 1)

The method of claim 1, wherein 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.

### Claim 4 (depends on 3)

The method of claim 3, wherein the shift value memory modules comprise read only memory.

### Claim 5 (depends on 1)

The method of claim 1, where the predetermined length is one of 4, 6, and 8.

### Claim 6 (depends on 1)

The method of claim 1, wherein there is full processing parallelism for one layer.

### Claim 7 (depends on 1)

The method of claim 1, wherein 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.

### Claim 8 (depends on 1)

The method of claim 1, wherein data throughput is at least 1 Gbits/sec.

### Claim 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,
wherein 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,
wherein the reading and writing of the data sub-blocks are evenly distributed between at least two areas of the memory, and
wherein shift values used in the data sub-blocks are optimized by minimizing a cost function to at least reduce a number of cycles of a predetermined length.

### Claim 10 (depends on 9)

The apparatus of claim 9, wherein a pipeline comprises at least three layers.

### Claim 11 (depends on 9)

The apparatus of claim 9, wherein 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.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the shift value memory modules comprise read only memory.

### Claim 13 (depends on 9)

The apparatus of claim 9, wherein the predetermined length is one of 4, 6, and 8.

### Claim 14 (depends on 9)

The apparatus of claim 9, wherein there is full processing parallelism for one layer.

### Claim 15 (depends on 9)

The apparatus of claim 9, wherein 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.

### Claim 16 (depends on 9)

The apparatus of claim 9, wherein data throughput is at least 1 Gbits/sec.

### Claim 17 (depends on 9)

The apparatus of claim 9, wherein the apparatus is embodied in at least one integrated circuit.

### Claim 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,
wherein 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,
wherein the reading and writing of the data sub-blocks are evenly distributed between at least two areas of a memory, and
wherein shift values used in the data sub-blocks are optimized by minimizing a cost function to at least reduce a number of cycles of a predetermined length.

### Claim 19 (depends on 18)

The medium of claim 18, wherein a pipeline comprises at least three layers.

### Claim 20 (depends on 18)

The medium of claim 18, wherein 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.

### Claim 21 (depends on 20)

The medium of claim 20, wherein the shift value memory modules comprise read only memory.

### Claim 22 (depends on 18)

The medium of claim 18, wherein there is full processing parallelism for one layer.

### Claim 23 (depends on 18)

The medium of claim 18, wherein 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.

### Claim 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,
wherein 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,
wherein the reading and writing of the data sub-blocks are evenly distributed between the at least two storing means, and
wherein shift values used in the data sub-blocks are optimized by minimizing a cost function to at least reduce a number of cycles of a predetermined length.

### Claim 25 (depends on 24)

The device of claim 24, wherein a pipeline comprises at least three layers.

### Claim at position 26

26-29. (canceled)
