# US 2006/0156179 A1 · Construction of LDPC (Low Density Parity Check) codes using GRS (Generalized Reed-Solomon) code

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

- Number: US 2006/0156179 A1
- Document ID: US20060156179A1
- Status: Published application
- Kind: A1
- Application number: 11/190,333
- Filed: 2005-07-27
- Published: 2006-07-13
- Earliest claimed: 2005-01-10
- Assignees: Broadcom Corporation
- Inventors: Ba-Zhong Shen; Scott Powell; Kelly Cameron; Hau Tran
- Web page: https://patentgrep.com/patent/US20060156179A1

## CPC

- H03M 13/255: {with Low Density Parity Check [LDPC] codes}
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M 13/03: Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M 13/033: {Theoretical methods to calculate these checking codes}
- H03M 13/1102: {Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes}
- H03M 13/15: Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes (H03M13/17 takes precedence)
- H03M 13/1515: {Reed-Solomon codes}
- 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

Construction of LDPC (Low Density Parity Check) codes using GRS (Generalized Reed-Solomon) code. A novel approach is presented by which a GRS code may be employed to generate a wide variety of types of LDPC codes. Such GRS based LDPC codes may be employed within various types of transceiver devices implemented within communication systems. This approach may be employed to generate GRS based LDPC codes particular designed for various application arenas. As one example, such a GRS based LDPC code may be specifically designed for use in communication systems that operate in accordance with any standards and/or recommended practices of the IEEE P802.3an (10GBASE-T) Task Force.

## Claims

### Claim 1

A method for constructing an LDPC (Low Density Parity Check) code using a GRS (Generalized Reed-Solomon) code, the method comprising:
selecting a location set that comprises:
a plurality of elements, wherein each element of the plurality of elements may be generated using a primitive element of a Galois field raised to a corresponding exponent, and wherein the Galois field comprises a predetermined finite number of elements;
a first degree 1 polynomial function that is operable to map each element of the plurality of elements of the location set to a corresponding non-zero value; and
a second degree 1 polynomial function that is a non-linear scalar multiple of the first degree 1 polynomial function;
selecting a plurality of non-zero elements from the Galois field;
identifying a first codeword vector of a GRS code, from among a plurality of possible codeword vector values, wherein the first codeword vector may be generated using the plurality of non-zero elements and resultants generated by mapping each element of the plurality of elements of the location set according to the first degree 1 polynomial function;
identifying a second codeword vector of the GRS code, from among the plurality of possible codeword vector values, wherein the second codeword vector may be generated using the plurality of non-zero elements and resultants generated by mapping each element of the plurality of elements of the location set according to the second degree 1 polynomial function;
multiplying the first codeword vector by each scaling factor of a first plurality of scaling factors thereby generating a plurality of scaled first codeword vectors;
multiplying the second codeword vector by each scaling factor of a second plurality of scaling factors thereby generating a plurality of scaled second codeword vectors;
generating a plurality of cosets by adding each scaled first codeword vector of the plurality of scaled first codeword vectors to each plurality of scaled second codeword vectors of the plurality of scaled second codeword vectors;
generating a plurality of permutation matrices, wherein each permutation matrix of the plurality of permutation matrices comprises a plurality of rows such that each row of the plurality of rows comprises a location mapping of one coset of the plurality of cosets; and
arranging each permutation matrix of the plurality of permutation matrices as sub-matrices thereby generating an LDPC parity check matrix that corresponds to the LDPC code.

### Claim 2 (depends on 1)

The method of claim 1, wherein:
the predetermined finite number of elements of the Galois field comprises 25 elements such that s is an integer;
the plurality of cosets comprises 2s cosets; and
each permutation matrix of the plurality of permutation matrices is a 2s×2s permutation matrix.

### Claim 3 (depends on 1)

The method of claim 1, wherein:
the predetermined finite number of elements of the Galois field comprises 2s elements such that s is an integer;
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that γ and ρ are integers; and
ρ is less than or equal to 2s.

### Claim 4 (depends on 1)

The method of claim 1, wherein:
the predetermined finite number of elements of the Galois field comprises 2s elements such that s is an integer;
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that γ and ρ are integers;
the LDPC parity check matrix has a bit node degree of γ and a check node degree of ρ;
each column of the LDPC parity check matrix comprises a weight of γ;
each row of the LDPC parity check matrix comprises a weight of ρ; and
ρ is less than or equal to 2s.

### Claim 5 (depends on 1)

The method of claim 1, wherein:
the predetermined finite number of elements of the Galois field comprises 26 elements;
the LDPC parity check matrix is a 384×2048 matrix;
the LDPC code is a (2048,1723) regular LDPC code that comprises a code rate of approximately 0.8413; and
a minimum distance of the LDPC code is greater than or equal to 8.

### Claim 6 (depends on 1)

The method of claim 1, wherein:
the predetermined finite number of elements of the Galois field comprises 2s elements such that s is an integer;
the first plurality of scaling factors comprises 2s scaling factors; and
the second plurality of scaling factors comprises 2s scaling factors.

### Claim 7 (depends on 1)

The method of claim 1, wherein:
the LDPC parity check matrix comprises γ×ρpermutation matrices arranged as sub-matrices such that y and p are integers;
the plurality of elements of the location set comprises p elements; and
the plurality of non-zero elements comprises p elements.

### Claim 8 (depends on 1)

The method of claim 1, wherein:
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that y and p are integers;
a minimum distance of the LDPC code is greater than or equal to γ+2 when γ is an even integer; and
the minimum distance of the LDPC code is greater than or equal to γ+1 when γ is an odd integer.

### Claim 9 (depends on 1)

The method of claim 1, wherein:
the first plurality of scaling factors is the second plurality of scaling factors.

### Claim 10 (depends on 1)

The method of claim 1, wherein:
the LDPC code is operable to generate LDPC coded signals that are compliant with recommended practices provided by IEEE (Institute of Electrical & Electronics Engineers) P802.3an (10GBASE-T) Task Force.

### Claim 11 (depends on 10)

The method of claim 10, wherein:
the LDPC parity check matrix that corresponds to the LDPC code is a 384×2048 LDPC parity check matrix, Hb, as provided within Appendix B.

### Claim 12

A method for constructing an LDPC (Low Density Parity Check) code using a GRS (Generalized Reed-Solomon) code, the method comprising:
identifying a first codeword vector of a GRS code, from among a plurality of possible codeword vector values;
identifying a second codeword vector of the GRS code, from among the plurality of possible codeword vector values;
multiplying the first codeword vector by each scaling factor of a first plurality of scaling factors thereby generating a plurality of scaled first codeword vectors;
multiplying the second codeword vector by each scaling factor of a second plurality of scaling factors thereby generating a plurality of scaled second codeword vectors;
generating a plurality of cosets by adding each scaled first codeword vector of the plurality of scaled first codeword vectors to each plurality of scaled second codeword vectors of the plurality of scaled second codeword vectors;
generating a plurality of permutation matrices, wherein each permutation matrix of the plurality of permutation matrices comprises a plurality of rows such that each row of the plurality of rows comprises a location mapping of one coset of the plurality of cosets; and
arranging each permutation matrix of the plurality of permutation matrices as sub-matrices thereby generating an LDPC parity check matrix that corresponds to the LDPC code.

### Claim 13 (depends on 12)

The method of claim 12, further comprising:
selecting a location set that comprises:
a plurality of elements, wherein each element of the plurality of elements may be generated using a primitive element of a Galois field raised to a corresponding exponent, and wherein the Galois field comprises a predetermined finite number of elements;
a first degree 1 polynomial function that is operable to map each element of the plurality of elements of the location set to a corresponding non-zero value; and
a second degree 1 polynomial function that is a non-linear scalar multiple of the first degree 1 polynomial function;
selecting a plurality of non-zero elements from the Galois field; and wherein:
the first codeword vector may be generated using the plurality of non-zero elements and resultants generated by mapping each element of the plurality of elements of the location set according to the first degree 1 polynomial function; and
the second codeword vector may be generated using the plurality of non-zero elements and resultants generated by mapping each element of the plurality of elements of the location set according to the second degree 1 polynomial function.

### Claim 14 (depends on 13)

The method of claim 13, wherein:
the predetermined finite number of elements of the Galois field comprises 2s elements such that s is an integer;
the plurality of cosets comprises 2s cosets;
each permutation matrix of the plurality of permutation matrices is a 2s×2s permutation matrix;
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that γ and ρ are integers;
the LDPC parity check matrix has a bit node degree of γ and a check node degree of ρ;
each column of the LDPC parity check matrix comprises a weight of γ;
each row of the LDPC parity check matrix comprises a weight of ρ; and
ρ is less than or equal to 2s.

### Claim 15 (depends on 13)

The method of claim 13, wherein:
the predetermined finite number of elements of the Galois field comprises 26 elements;
the LDPC parity check matrix is a 384×2048 matrix;
the LDPC code is a (2048,1723) regular LDPC code that comprises a code rate of approximately 0.8413; and
a minimum distance of the LDPC code is greater than or equal to 8.

### Claim 16 (depends on 13)

The method of claim 13, wherein:
the predetermined finite number of elements of the Galois field comprises 25 elements such that s is an integer;
the first plurality of scaling factors comprises 25 scaling factors; and
the second plurality of scaling factors comprises 2s scaling factors.

### Claim 17 (depends on 13)

The method of claim 13, wherein:
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that γ and ρ are integers;
the plurality of elements of the location set comprises ρ elements; and
the plurality of non-zero elements comprises ρ elements.

### Claim 18 (depends on 12)

The method of claim 12, wherein:
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that γ and ρ are integers;
a minimum distance of the LDPC code is greater than or equal to γ+2 when γ is an even integer;
the minimum distance of the LDPC code is greater than or equal to γ+1 when γ is an odd integer.

### Claim 19 (depends on 12)

The method of claim 12, wherein:
the LDPC code is operable to generate LDPC coded signals that are compliant with recommended practices provided by IEEE (Institute of Electrical & Electronics Engineers) P802.3an (10GBASE-T) Task Force.

### Claim 20 (depends on 19)

The method of claim 19, wherein:
the LDPC parity check matrix that corresponds to the LDPC code is a 384×2048 LDPC parity check matrix, Hb, as provided within Appendix B.

### Claim 21

An apparatus that is operable to construct an LDPC (Low Density Parity Check) code using a GRS (Generalized Reed-Solomon) code, the apparatus comprising:
a codeword vector identification module that is operable to:
identify a first codeword vector of a GRS code, from among a plurality of possible codeword vector values; and
identify a second codeword vector of the GRS code, from among the plurality of possible codeword vector values;
a coset generation module that is operable to:
multiply the first codeword vector by each scaling factor of a first plurality of scaling factors thereby generating a plurality of scaled first codeword vectors;
multiply the second codeword vector by each scaling factor of a second plurality of scaling factors thereby generating a plurality of scaled second codeword vectors; and
generate a plurality of cosets by adding each scaled first codeword vector of the plurality of scaled first codeword vectors to each plurality of scaled second codeword vectors of the plurality of scaled second codeword vectors;
an LDPC parity check matrix generation module that is operable to:
generate a plurality of permutation matrices, wherein each permutation matrix of the plurality of permutation matrices comprises a plurality of rows such that each row of the plurality of rows comprises a location mapping of one coset of the plurality of cosets; and
arrange each permutation matrix of the plurality of permutation matrices as sub-matrices thereby generating an LDPC parity check matrix that corresponds to the LDPC code.

### Claim 22 (depends on 21)

The apparatus of claim 21, further comprising:
a location set selection module that is operable to select a location set that comprises:
a plurality of elements, wherein each element of the plurality of elements may be generated using a primitive element of a Galois field raised to a corresponding exponent, and wherein the Galois field comprises a predetermined finite number of elements;
a first degree 1 polynomial function that is operable to map each element of the plurality of elements of the location set to a corresponding non-zero value; and
a second degree 1 polynomial function that is a non-linear scalar multiple of the first degree 1 polynomial function; and
a non-zero element selection module that is operable to select a plurality of non-zero elements from the Galois field; and wherein:
the first codeword vector may be generated using the plurality of non-zero elements and resultants generated by mapping each element of the plurality of elements of the location set according to the first degree 1 polynomial function; and
the second codeword vector may be generated using the plurality of non-zero elements and resultants generated by mapping each element of the plurality of elements of the location set according to the second degree 1 polynomial function.

### Claim 23 (depends on 22)

The apparatus of claim 22, wherein:
the predetermined finite number of elements of the Galois field comprises 2s elements such that s is an integer;
the plurality of cosets comprises 2s cosets;
each permutation matrix of the plurality of permutation matrices is a 2s×2s permutation matrix;
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that γ and ρ are integers;
the LDPC parity check matrix has a bit node degree of γ and a check node degree of ρ;
each column of the LDPC parity check matrix comprises a weight of γ;
each row of the LDPC parity check matrix comprises a weight of ρ; and
ρ is less than or equal to 2s.

### Claim 24 (depends on 22)

The apparatus of claim 22, wherein:
the predetermined finite number of elements of the Galois field comprises 26 elements;
the LDPC parity check matrix is a 384×2048 matrix;
the LDPC code is a (2048,1723) regular LDPC code that comprises a code rate of approximately 0.8413; and
a minimum distance of the LDPC code is greater than or equal to 8.

### Claim 25 (depends on 22)

The apparatus of claim 22, wherein:
the predetermined finite number of elements of the Galois field comprises 2s elements such that s is an integer;
the first plurality of scaling factors comprises 2s scaling factors; and
the second plurality of scaling factors comprises 2s scaling factors.

### Claim 26 (depends on 22)

The apparatus of claim 22, wherein:
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that γ and ρ are integers;
the plurality of elements of the location set comprises ρ elements; and
the plurality of non-zero elements comprises ρ elements.

### Claim 27 (depends on 21)

The apparatus of claim 21, wherein:
the LDPC parity check matrix comprises γ×ρ permutation matrices arranged as sub-matrices such that γ and ρ are integers;
a minimum distance of the LDPC code is greater than or equal to γ+2 when γ is an even integer;
the minimum distance of the LDPC code is greater than or equal to γ+1 when γ is an odd integer.

### Claim 28 (depends on 21)

The apparatus of claim 21, wherein:
the apparatus is communicatively coupled to an LDPC encoder;
the LDPC encoder is operable to encode at least one information bit, using the LDPC code constructed by the apparatus, thereby generating an LDPC coded signal that is compliant with recommended practices provided by IEEE (Institute of Electrical & Electronics Engineers) P802.3an (10GBASE-T) Task Force.

### Claim 29 (depends on 28)

The apparatus of claim 28, wherein:
the LDPC parity check matrix that corresponds to the LDPC code is a 384×2048 LDPC parity check matrix, Hb, as provided within Appendix B.
