# US 2005/0240853 A1 · Decoding device, decoding method, and program

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

- Number: US 2005/0240853 A1
- Document ID: US20050240853A1
- Status: Published application
- Kind: A1
- Application number: 10/521,054
- Filed: 2004-04-19
- Published: 2005-10-27
- Earliest claimed: 2003-05-13
- Assignees: Sony Corporation
- Inventors: Takashi Yokokawa; Toshiyuki Miyauchi; Yasuhiro IIida
- Web page: https://patentgrep.com/patent/US20050240853A1

## CPC

- H03M 13/1168: {wherein the sub-matrices have column and row weights greater than one, e.g. multi-diagonal sub-matrices}
- H03M 13/11: using multiple parity bits
- H03M 13/1114: {Merged schedule message passing algorithm with storage of sums of check-to-bit node messages or sums of bit-to-check node messages, e.g. in order to increase the memory efficiency}
- H03M 13/1134: {Full parallel processing, i.e. all bit nodes or check nodes are processed in parallel}
- H03M 13/1137: {Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel}
- H03M 13/1145: {Pipelined decoding at code word level, e.g. multiple code words being decoded simultaneously}
- H03M 13/1188: {wherein in the part with the double-diagonal at least one column has an odd column weight equal or greater than three}
- H03M 13/6505: {Memory efficient implementations}
- H03M 13/6566: {Implementations concerning memory access contentions}
- H03M 13/6577: {Representation or format of variables, register sizes or word-lengths and quantization}
- 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 present invention relates to a decoding apparatus and a decoding method for realizing the decoding of LDPC codes, in which, while the circuit scale is suppressed, the operating frequency can be suppressed within a sufficiently feasible range, and control of memory access can be performed easily, and to a program therefor. A check matrix of LDPC codes is formed by a combination of a (P×P) unit matrix, a matrix in which one to several 1s of the unit matrix are substituted with 0, a matrix in which they are cyclically shifted, a matrix, which is the sum of two or more of them, and a (P×P) 0-matrix. A check node calculator 313 simultaneously performs p check node calculations. A variable node calculator 319 simultaneously performs p variable node calculations.

## Claims

### Claim 1

A decoding apparatus for decoding LDPC (Low Density Parity Check) codes, when using as a sub-matrix, a (P×P) unit matrix, a quasi-unit matrix in which one or more is, which are elements of the unit matrix, are substituted with 0, a shift matrix in which said unit matrix or said quasi-unit matrix is cyclically shifted, a sum matrix, which is the sum of two or more of said unit matrix, said quasi-unit matrix, and said shift matrix, or a (P×P) 0-matrix, a check matrix of said LDPC codes is represented by a combination of a plurality of said sub-matrices, said decoding apparatus comprising:
first computation means for simultaneously performing P check node computations for decoding said LDPC codes; and
second computation means for simultaneously performing P variable node computations for decoding said LDPC codes.

### Claim 2 (depends on 1)

The decoding apparatus according to claim 1, wherein said first computation means has P check node calculators for performing check node computations, and
said second computation means has P variable node calculators for performing variable node computations.

### Claim 3 (depends on 1)

The decoding apparatus according to claim 1, further comprising:
message storage means for simultaneously reading and writing message data corresponding to P edges, which is obtained as a result of said P check node computations or said P variable node computations.

### Claim 4 (depends on 3)

The decoding apparatus according to claim 3, wherein said message storage means stores message data corresponding to the edges, which are read during the check node computation in such a manner that 1s of the check matrix are packed closer in the row direction.

### Claim 5 (depends on 3)

The decoding apparatus according to claim 3, wherein said message storage means stores message data corresponding to edges, which are read during the variable node computation in such a manner that 1s of the check matrix are packed closer in the column direction.

### Claim 6 (depends on 3)

The decoding apparatus according to claim 3, wherein said message storage means stores, at the same address, messages corresponding to P edges belonging to a unit matrix whose weight is 1, a quasi-unit matrix, or a shift matrix when the sub-matrices whose weight is 2 or more from among the sub-matrices representing said check matrix are represented in the form of the sum of the unit matrix whose weight is 1, the quasi-unit matrix, or the shift matrix.

### Claim 7 (depends on 3)

The decoding apparatus according to claim 3, wherein said message storage means comprises number-of-rows/p FIFOs and number-of-columns/p FIFOs, and
said number-of-rows/p FIFOs and said number-of-columns/p FIFOs each have a number of words corresponding to the weight of the row and the weight of the column of said check matrix, respectively.

### Claim 8 (depends on 3)

The decoding apparatus according to claim 3, wherein said message storage means comprises a RAM (Random Access Memory), and
said RAM stores said message data in the read-out sequence in such a manner as to be packed closer and reads said message data in the storage position sequence.

### Claim 9 (depends on 1)

The decoding apparatus according to claim 1, further comprising:
received information storage means for storing received information of LDPC codes and for simultaneously reading P pieces of said received information.

### Claim 10 (depends on 9)

The decoding apparatus according to claim 9, wherein said received information storage means stores said received information in such a manner that the received information can be read in the sequence necessary for said variable node computation.

### Claim 11 (depends on 1)

The decoding apparatus according to claim 1 further comprising:
rearranging means for rearranging messages obtained as a result of said P check node computations or said P variable node computations.

### Claim 12 (depends on 11)

The decoding apparatus according to claim 11, wherein said rearranging means comprises a barrel shifter.

### Claim 13 (depends on 1)

The decoding apparatus according to claim 1, wherein said first computation means and said second computation means determine messages corresponding to P edges.

### Claim 14 (depends on 1)

The decoding apparatus according to claim 1, wherein said first computation means performs some of said P check node computations and said P variable node computations, and
said second computation means performs some of the others of said P variable node computations.

### Claim 15 (depends on 14)

The decoding apparatus according to claim 14, wherein said first computation means comprises P calculators for performing some of said P check node computations and said P variable node computations, and
said second computation means comprises P calculators for performing some of the others of said P variable node computations.

### Claim 16 (depends on 14)

The decoding apparatus according to claim 14, further comprising:
first decoding in-progress result storage means for simultaneously reading and writing first decoding in-progress results corresponding to P edges, which are obtained by said first computation means by performing some of said P check node computations and said P variable node computations.

### Claim 17 (depends on 16)

The decoding apparatus according to claim 16, wherein said first decoding in-progress result storage means stores said first decoding in-progress results corresponding to the edge, which are read when some of the others of said P variable node computations are performed, in such a manner that 1s of the check matrix are packed closer in the row direction.

### Claim 18 (depends on 16)

The decoding apparatus according to claim 16, wherein said first decoding in-progress result storage means are two single-port RAMs (Random Access Memories).

### Claim 19 (depends on 18)

The decoding apparatus according to claim 18, wherein said two single-port RAMs alternately store said first decoding in-progress results in units of said first decoding in-progress results corresponding to edges of P rows of said check matrix.

### Claim 20 (depends on 18)

The decoding apparatus according to claim 18, wherein said two single-port RAMs (Random Access Memories) each read said first decoding in-progress results stored at the same address.

### Claim 21 (depends on 16)

The decoding apparatus according to claim 16, wherein said first decoding in-progress result storage means stores, at the same address, said first decoding in-progress results corresponding to P edges belonging to a unit matrix whose weight is 1, a quasi-unit matrix, or a shift matrix when the sub-matrices whose weight is 2 or more from among the sub-matrices representing said check matrix are represented in the form of the sum of the unit matrix whose weight is 1, the quasi-unit matrix, or the shift matrix.

### Claim 22 (depends on 14)

The decoding apparatus according to claim 14, further comprising:
second decoding in-progress result storage means for simultaneously reading and writing said second decoding in-progress results corresponding to P edges, which are obtained by said second computation means by performing some of the others of said P variable node computations.

### Claim 23 (depends on 14)

The decoding apparatus according to claim 14, further comprising:
received information storage means for storing received information of LDPC codes and simultaneously reading said P pieces of received information.

### Claim 24 (depends on 23)

The decoding apparatus according to claim 23, wherein said received information storage means stores said received information in such a manner that said received information can be read in the sequence necessary for some of the others of said P variable node computations.

### Claim 25 (depends on 14)

The decoding apparatus according to claim 14, further comprising:
rearranging means for rearranging first decoding in-progress results obtained by said first computation means by performing some of said P check node computations and said P variable node computations, or second decoding in-progress results obtained by said second computation means by performing some of the others of said P variable node computations.

### Claim 26 (depends on 25)

The decoding apparatus according to claim 25, wherein said rearranging means comprises a barrel shifter.

### Claim 27 (depends on 1)

The decoding apparatus according to claim 1, wherein said first computation means performs some of said P check node computations, and
said second computation means performs some of the others of said P check node computations, and said P variable node computations.

### Claim 28 (depends on 27)

The decoding apparatus according to claim 27, wherein said first computation means comprises P calculators for performing some of said P check node computations, and
said second computation means comprises P calculators for performing some of the others of said P check node computations, and said P variable node computations.

### Claim 29 (depends on 27)

The decoding apparatus according to claim 27, further comprising:
first decoding in-progress result storage means for simultaneously reading and writing first decoding in-progress results corresponding to P edges, which are obtained by said first computation means by performing some of said P check node computations.

### Claim 30 (depends on 27)

The decoding apparatus according to claim 27, further comprising:
second decoding in-progress result storage means for simultaneously reading and writing second decoding in-progress results corresponding to P edges, which are obtained by said second computation means by performing some of the others of said P check node computations, and said P variable node computations.

### Claim 31 (depends on 30)

The decoding apparatus according to claim 30, wherein said second decoding in-progress result storage means stores said second decoding in-progress results corresponding to edges, which are read when some of the others of said P check node computations, and said P variable node computations are performed, in such a manner that 1s of the check matrix are packed closer in the column direction.

### Claim 32 (depends on 30)

The decoding apparatus according to claim 30, wherein said second decoding in-progress result storage means are two single-port RAMs (Random Access Memories).

### Claim 33 (depends on 32)

The decoding apparatus according to claim 32, wherein said single-port RAMs alternately store said second decoding in-progress results in units of said second decoding in-progress results corresponding to P edges of said check matrix.

### Claim 34 (depends on 32)

The decoding apparatus according to claim 32, wherein said two single-port RAMs (Random Access Memories) each read said second decoding in-progress results stored at the same address.

### Claim 35 (depends on 30)

The decoding apparatus according to claim 30, wherein said second decoding in-progress result storage means stores, at the same address, said second decoding in-progress results corresponding to P edges belonging to a unit matrix whose weight is 1, a quasi-unit matrix, or a shift matrix when the sub-matrices whose weight is 2 or more from among the sub-matrices representing said check matrix are represented in the form of the sum of the unit matrix whose weight is 1, the quasi-unit matrix, or the shift matrix.

### Claim 36 (depends on 27)

The decoding apparatus according to claim 27, further comprising:
received information storage means for storing received information of LDPC codes and for simultaneously reading said P pieces of received information.

### Claim 37 (depends on 36)

The decoding apparatus according to claim 36, wherein said received information storage means stores said received information in such a manner that said received information can be read in the sequence necessary for some of the others of said P check node computations, and said P variable node computations.

### Claim 38 (depends on 27)

The decoding apparatus according to claim 27, further comprising:
rearranging means for rearranging first decoding in-progress results obtained by said first computation means by performing some of said P check node computations, or second decoding in-progress results obtained by said second computation means by performing some of the others of said P check node computations, and said P variable node computations.

### Claim 39 (depends on 38)

The decoding apparatus according to claim 38, wherein said rearranging means comprises a barrel shifter.

### Claim 40

A decoding method for use with a decoding apparatus for decoding LDPC (Low Density Parity Check) codes, when using as a sub-matrix, a (P×P) unit matrix, a quasi-unit matrix in which one or more 1s, which are elements of the unit matrix, are substituted with 0, a shift matrix in which said unit matrix or said quasi-unit matrix is cyclically shifted, a sum matrix, which is the sum of two or more of said unit matrix, said quasi-unit matrix, and said shift matrix, or a (P×P) 0-matrix, a check matrix of LDPC codes is represented by a combination of a plurality of said sub-matrices, said decoding method comprising:
a first computation step of simultaneously performing P check node computations for decoding said LDPC codes; and
a second computation step of simultaneously performing P variable node computations for decoding said LDPC codes.

### Claim 41

A program for enabling a computer to decode LDPC (Low Density Parity Check) codes, said program comprising:
a first computation step of simultaneously performing P check node computations for decoding said LDPC codes; and
a second computation step of simultaneously performing P variable node computations for decoding said LDPC codes.
