Parity check matrix storing method, block LDPC coding method, and apparatus using parity check matrix storing method

• US 8,190,967 B2
• Filed: 09/26/2007
• Issued: 05/29/2012
• Est. Priority Date: 12/08/2006
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute, Samsung Electronics Co. Ltd.
• Original Assignee: Electronics and Telecommunications Research Institute, Samsung Electronics Co. Ltd.
• Inventors: Hong, Eon-Young, Park, Youn-Ok, Choi, Jung-Pil
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): GANDHI, DIPAKKUMAR B
• Application Number:
  US11/861,884
• Publication Number:
  US 20080140686A1
• Time in Patent Office: 1,707 Days
• Field of Search: None
• US Class Current: 714/758
• CPC Class Codes: H03M 13/1185 wherein the parity-check matrix comprises a part with a double-diagonal
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

The present invention relates to a low density parity check (LDPC) encoding method and an apparatus thereof. In the LDPC encoding method, a matrix multiplication corresponding to ET⁻¹ and T⁻¹ is eliminated according to a structural characteristic in an encoding process. Accordingly, shift weights that are not −1 among shift weights corresponding to partial blocks A, B, and C of a parity check matrix are used to perform an encoding operation, and a cyclic shift operation of an information unit block is performed in parallel so that a first parity block and a second parity block may be simultaneously generated.

Claims

1. A block low density parity check encoding method comprising:

cyclically shifting an information unit block included in an information block by using partial blocks A and C that are divided from a parity check matrix according to a structural characteristic of a block low density parity check code;

accumulatively adding the cyclically shifting results to generate at least one parity partial block corresponding to the partial block A and a first parity block corresponding to the partial blocks A and C;

adding a cyclically shifting result of the first parity block to the parity partial block in correspondence to a shift weight of a partial block B, and generating a second parity block by arranging the added results; and

combining the information block, the first parity block, and the second parity block to generate a codeword.

2. The block low density parity check encoding method of claim 1,

further comprising storing a shift weight of the parity check matrix in a memory before cyclically shifting the information unit block,

wherein the storing the shift weight of the parity check matrix in the memory comprises:

generating the parity check matrix according to an encoding rate;

expressing the parity check matrix as a shift weight matrix;

classifying the shift weight matrix as at least one partial block; and

storing location information of shift weights corresponding to the partial blocks A, B, and C among shift weights corresponding to an unitary matrix that is not a zero matrix in the shift weight matrix and the shift weights.

3. The block low density parity check encoding method of claim 1,

wherein the cyclically shifting of the information unit block comprises reading shift weights of the partial blocks A and C and cyclically shifting the information unit block according to the shift weights of the partial blocks A and C, and

the generating of the parity partial block and the first parity partial block comprises accumulatively adding cyclic shift results for each row of the partial block A to generate the parity partial block and adding cyclic shift results of the information unit block according to the shift weights of the partial blocks A and C to generate the first parity block.

4. The block low density parity check encoding method of claim 3,

wherein the reading of the shift weight comprises reading location information corresponding to the shift weight, and

the cyclically shifting of the information unit block comprises cyclically shifting the information unit block corresponding to the location information by using the shift weight.

5. The block low density parity check encoding method of claim 3, wherein, in the generating of the parity partial block, a shift weight and location information of a row corresponding to the parity partial block among the rows of the partial blocks A are used, the cyclic shift results of the information unit blocks corresponding to the location information are accumulatively added, cyclic shift results up to a row before the row corresponding to the parity partial block are added to a value obtained by accumulatively adding, and therefore the parity partial block is generated.

6. The block low density parity check encoding method of claim 3, further comprising:

reading of the shift weight of the partial block B;

cyclically shifting the first parity block according to the shift weight of the partial block B;

adding cyclic shift results of the parity partial block and the first parity block; and

arranging adding results of the cyclic shift results and generating a second parity block.

7. The block low density parity check encoding method of claim 3, wherein an exclusive OR is used in a block low density parity check encoding process.

8. The block low density parity check encoding method of claim 6, wherein an arrangement order of the added results of the cyclic shift results of the parity partial block and the first parity block corresponds to an order of the parity partial block.

9. A block low density parity check encoding device comprising:

a first memory for classifying shift weights of a parity check matrix of a block low density parity check code for each of partial blocks that are divided from the parity check matrix according to structural characteristics of the block low density parity check code, and storing the shift weights;

a first encoder for cyclically shifting and accumulatively adding information unit blocks by using shift weights of partial blocks A and C read from the first memory and outputting at least one parity partial block and a first parity block, the information unit block formed by dividing an information block into predetermined sizes;

a second encoder for adding and arranging cyclic shift results of the first parity block and the parity partial block by using a shift weight corresponding to a partial block B read from the first memory, and outputting a second parity block; and

a combination unit for combining the information unit block, the first parity block received from the first encoder, and the second parity block received from the second encoder, and outputting a codeword.

10. The block low density parity check encoding device of claim 9,

further comprising a second memory for dividing the information block into the information unit blocks and storing the information unit blocks,

wherein the first encoder uses the information unit block read from the second memory to generate the parity partial block and the first parity block.

11. The block low density parity check encoding device of claim 9, wherein the first encoder comprises:

a first cyclic shift unit for outputting a result obtained by cyclically shifting the information unit block by using the shift weight of the partial block A;

a second cyclic shift weight unit for outputting a result obtained by cyclically shifting the information unit block by using the shift weight of the partial block C;

a first adding unit for outputting the parity partial block generated by accumulatively adding the result output from the first cyclic shift unit for each row of the partial block; and

a first parity block generator for adding the parity partial block corresponding to an added result of the results output from the first cyclic shift unit to the result output from the second cyclic shift unit and outputting the first parity block.

12. The block low density parity check encoding device of claim 11, wherein:

the first memory stores location information corresponding to the shift weight;

the first encoder comprises an address generator for reading the location information corresponding to the shift weight to be used to perform a cyclic shift operation from the first memory, and reading and outputting the information unit block according to the location information from the second memory; and

the first cyclic shift unit reads the information unit block output from the address generator and cyclically shifts the information unit block by the shift weight corresponding to the location information.

13. The block low density parity check encoding device of claim 11, wherein the second encoder comprises:

a third cyclic shift unit for outputting a result obtained by cyclically shifting the information unit block by using the shift weight of the partial block B; and

a second parity generator for outputting the second parity block obtained by adding and arranging the result output from the third cyclic shift unit and the parity partial block.

14. The block low density parity check encoding device of claim 11, wherein the first memory stores the shift weights except for the shift weights corresponding to a zero matrix among the shift weights corresponding to the partial blocks A, B, and C.

15. The block low density parity check encoding device of claim 11, wherein the first cyclic shift unit independently performs a cyclic shifting operation for each row of the partial block A, and the cyclic shift operation corresponding to each row of the partial block A is performed in parallel.

16. The block low density parity check encoding device of claim 15, wherein the second cyclic shift unit independently performs the cyclic shifting operation with respect to the cyclic shifting operation performed by the first cyclic shift unit, and performs the cyclic shifting operation in parallel to the cyclic shifting operation performed by the first cyclic shift unit.