# US 2006/0190271 A1 · Method for forming rate compatible code using high dimensional product codes

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

- Number: US 2006/0190271 A1
- Document ID: US20060190271A1
- Status: Published application
- Kind: A1
- Application number: 10/547,236
- Filed: 2003-12-30
- Published: 2006-08-24
- Earliest claimed: 2003-02-27
- Assignees: Electronics and Telecommunications Research Institute
- Inventors: Soo Kim; Deock-Gil Oh; Jae-Moung Kim
- Web page: https://patentgrep.com/patent/US20060190271A1

## CPC

- H03M 13/2963: {Turbo-block codes, i.e. turbo codes based on block codes, e.g. turbo decoding of product codes}
- H03M 13/033: {Theoretical methods to calculate these checking codes}
- H03M 13/29: combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M 13/2909: {Product codes}
- H03M 13/2918: {with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube}
- H03M 13/47: Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37
- H03M 13/635: {Error control coding in combination with rate matching}
- H03M 13/6368: {using rate compatible puncturing or complementary puncturing}
- H03M 13/6381: {Rate compatible punctured turbo [RCPT] codes}
- H04L 1/0057: {Block codes (H04L1/0061, H04L1/0064 take precedence)}
- H04L 1/0069: {Puncturing patterns}
- H04L 1/1819: {with retransmission of additional or different redundancy}
- H03M 13/152: {Bose-Chaudhuri-Hocquenghem [BCH] codes}
- H04L 1/0009: {by adapting the channel coding (H04L1/1812 takes precedence)}
- 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)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Provided is a method for forming a rate compatible code using high dimensional product codes and a computer-readable recording medium for recording a program that implements the program. The rate compatible code, which can provide various encoding rates, is formed by discriminating parity blocks and determining a punctured pattern for each parity block, m being more than two. The method includes the steps of: a) forming an m dimensional product code by using a systematic block code; b) dividing the m dimensional product code into an information block and 2m-1 parity blocks; c) allocating indices to the divided blocks of the information block and 2m-1 parity blocks; d) finding all combinations of the information block and the parity blocks which are adjacent to the information block; e) estimating a first weighting factor of w1 for the all combinations; f) if there are first combinations having the same weighting factor w1, estimating a second weighting factor of w2 for the first combinations having the same weighting factor w1 as second combinations; g) selecting a combination having largest weighting factor among the second combinations having the second weighting factor w2; and h) forming rate compatible codes by using the selected combinations based on the w1 and w2.

## Claims

### Claim 1

A method for forming a rate compatible code using high dimensional product codes, comprising the steps of:
a) forming an m dimensional product code by using a systematic block code in a predetermined number of axes, wherein the m is a positive integer number;
b) dividing the m dimensional product code into an information block and 2m-1 parity blocks;
c) allocating indices to the divided blocks of the information block and 2m-1 parity blocks;
d) obtaining combinations of the information block and corresponding parity blocks which are adjacent to the information block;
e) estimating a first weighting factor w1 for the combinations;
f) finding combinations having the same first weighting factor w1 as identical combinations;
h) if there is no combinations having the same first weighting factor w1, forming rate compatible codes by using the combinations; and
g) if there is combinations having the same first weighting factor w1, obtaining second combinations of the combinations and parity blocks adjacent to the combinations and forming rate compatible codes by using the second combinations.

### Claim 2 (depends on 1)

The method as recited in claim 1, wherein the step g) includes the steps of:
g-1) estimating a second weighting factor of w2 for the identical combinations;
g-2) selecting a third combination having largest weighting factor w2 among the identical combinations; and
g-3) obtaining second combinations of the combinations excepting identical combinations and corresponding new parity blocks which is adjacent to the combination and obtaining second combinations of the third combination and corresponding new parity blocks adjacent to the third combination.

### Claim 3 (depends on 1)

The method as recited in claim 1, wherein the steps e) to g) are repeatedly performed for obtaining the second combinations by additionally including new parity blocks adjacent to the combinations until obtaining second combinations including m parity blocks.

### Claim 4 (depends on 1)

The method as recited in claim 1, wherein, in the step b), the m dimensional product code has an information block and parity blocks that are formed in m-dimensional axes.

### Claim 5 (depends on 1)

The method as recited in claim 1, wherein the information word block of the step b) has axes whose size is the same as the length of an information word of a code that forms the axes of the m dimensional product code.

### Claim 6 (depends on 1)

The method as recited in claim 1, wherein the parity block of the step b) has axes whose size is the same as the length of an information word or the length of parity of codes that form the axes of the m dimensional product code, except the information block.

### Claim 7 (depends on 1)

The method as recited in claim 1, wherein the index of a block is assigned as a binary number which is expressed in m bits by assigning ‘0’ when the size of axes that form the block is equal to the size of the information word, and assigning ‘1’ when the size of axes that form the block is equal to the size of a parity.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein, in the step d), it is determined whether the m blocks for forming the information word block and the one-dimensional code include m-1 ‘0’ in the identifier of a block.

### Claim 9

A computer-readable recording medium for recording a program that implements a method for forming a rate compatible code using high dimensional product codes, the method comprising the steps of:
a) forming an m dimensional product code by using a systematic block code in a predetermined number of axes, wherein the m is a positive integer number;
b) dividing the m dimensional product code into an information block and 2m-1 parity blocks;
c) allocating indices to the divided blocks of the information block and 2m-1 parity blocks;
d) finding first combinations of the information block and corresponding parity blocks which are adjacent to the information block;
e) estimating a first weighting factor of w1 for the first combinations;
f) finding first combinations having the same first weighting factor w1 as identical combinations;
h) if there is not first combinations having the same first weighting factor w1, forming rate compatible codes by using the first combinations; and
g) if there is first combinations having the same first weighting factor w2, finding second combinations and forming rate compatible codes by using the second combinations.

### Claim 10 (depends on 10)

The computer-readable recording medium as recited in claim 10, wherein the step g) includes the steps of:
g-1) estimating a second weighting factor of w2 for the identical combinations;
g-2) selecting a largest combination having largest weighting factor w2 among the identical combinations; and
g-3) finding second combinations of first combinations excepting identical combinations and corresponding parity blocks which is adjacent to the largest combination, finding second combinations of the largest combination and corresponding parity blocks, which is adjacent to the largest combination.
