# US 11,309,917 B2 · Base parity-check matrices for LDPC codes that have subsets of orthogonal rows

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

- Number: US 11,309,917 B2
- Document ID: US11309917B2
- Status: Granted
- Kind: B2
- Application number: 16/901,934
- Filed: 2020-06-15
- Published: 2020-10-01
- Granted: 2022-04-19
- Earliest claimed: 2017-12-15
- Assignees: Huawei Technologies Co., Ltd.
- Applicants: Huawei Technologies Co., Ltd.
- Inventors: Balazs Matuz; Gianluigi Liva; Onurcan Iscan; Ronald Boehnke; Wen Xu
- Web page: https://patentgrep.com/patent/US11309917B2

## CPC

- H03M 13/036: {Heuristic code construction methods, i.e. code construction or code search based on using trial-and-error}
- H03M 13/1185: {wherein the parity-check matrix comprises a part with a double-diagonal}
- H03M 13/116: {Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices}
- 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/616: {Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations}
- H03M 13/6544: {IEEE 802.16 (WIMAX and broadband wireless access)}
- 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

Protograph-based LDPC codes are obtained from z-row-orthogonal base matrices with some additional structure constraints, such as a diagonal and/or double-diagonal structure, in order to allow a high parallelization that is a multiple of z, while having an efficient encoding or decoding. A “big” base matrix is constructed from a structured square submatrix in order to have a WiMAX-like structure and a z-row-orthogonality. Also, starting from a “smaller” base matrix having a part arranged in a double-diagonal shape with tail-biting one, an expansion by a factor equal to z can be performed, followed by an addition of a single one-entry into the last column at a specific location, thereby obtaining a three-degree column, and followed by a row and/or column permutation in order to obtain a base matrix in a WiMAX-like structure.

## Claims

### Claim 1

A device for providing a matrix for data processing within a communication system the device comprising a processor, and a memory storing program instructions for execution by the processor, wherein when the program instructions are executed by the processor, the processor is configured to:
construct a first matrix, wherein all entries of the first matrix are either zero or one, wherein the first matrix is composed of a set of submatrices and each submatrix has a maximum column weight of one, and wherein each submatrix is obtained through grouping each row of the first matrix with one or more rest row of the first matrix;
expand the first matrix by a factor equal to z into an expanded matrix of size mb×nb in such a manner that the expanded matrix is z-row-orthogonal;
modify the expanded matrix into a second matrix of size mb×nb in such a manner that the second matrix is z-row-orthogonal; and
encode or decode data within the communication system based on the first matrix for a high parallelization of row decoding operations.

### Claim 2 (depends on 1)

The device of claim 1, wherein the processor is configured, according to the program instructions, to modify the expanded matrix by performing an operation comprising:
adding into the expanded matrix or removing from the expanded matrix at least one entry equal to one at a respective location of the expanded matrix that is chosen in such a manner that the second matrix is z-row-orthogonal.

### Claim 3 (depends on 1)

The device of claim 1, wherein the processor is configured, according to the program instructions, to modify the expanded matrix by performing an operation comprising:
adding into the expanded matrix or removing from the expanded matrix at least one row in such a manner that the second matrix is z-row-orthogonal.

### Claim 4 (depends on 1)

The device of claim 1, wherein the degree-2 columns of the submatrix are arranged in a double-diagonal structure.

### Claim 5 (depends on 1)

The device of claim 1, wherein the processor is configured, according to the program instructions, to modify the expanded matrix by performing an operation comprising:
adding, at a respective location of the matrix, at least one entry equal to one into the matrix, wherein the respective location is chosen to preserve a z-row orthogonality of the matrix.

### Claim 6 (depends on 1)

The device of claim 1, wherein:
a single entry equal to one is added at an intersection of the last column of the second matrix and a predetermined row of the second matrix.

### Claim 7 (depends on 1)

The device of claim 1, wherein the matrix comprises a square submatrix A, the square submatrix A being
A
=
[
1
1
…
1
1
1
1
1
…
1
1
1
1
]
.

### Claim 8 (depends on 1)

The device of claim 1, wherein the matrix represents a low-density parity-check (LDPC) code.

### Claim 9 (depends on 1)

The device of claim 1, wherein when the program instructions are executed by the processor, the processor is further configured to: encode or decode data using the second matrix.

### Claim 10

A method for providing a matrix for data processing within a communication system, comprising:
constructing, by one or more processors, a first matrix, wherein all entries of the first matrix are either zero or one, wherein the first matrix is composed of a set of submatrices and each submatrix has a maximum column weight of one, and wherein each submatrix is obtained through grouping each row of the first matrix with one or more rest row of the first matrix;
expanding, by the one or more processors, the first matrix by a factor equal to z into an expanded matrix of size mb×nb in such a manner that the expanded matrix is z-row-orthogonal;
modifying, by the one or more processors, the expanded matrix into a second matrix of size mb×nb in such a manner that the second matrix is z-row-orthogonal; and
encoding or decoding, by the one or more processors, data within the communication system based on the first matrix for a high parallelization of row decoding operations.

### Claim 11 (depends on 10)

The method according to claim 10, wherein the expanded matrix is modified by performing an operation comprising:
adding into the expanded matrix or removing from the expanded matrix, by the one or more processors, at least one entry equal to one at a respective location of the expanded matrix that is chosen in such a manner that the second matrix is z-row-orthogonal.

### Claim 12 (depends on 10)

The method according to claim 10, wherein the expanded matrix is modified by performing an operation comprising:
adding into the expanded matrix or removing from the expanded matrix, by the one or more processors, at least one row in such a manner that the second matrix is z-row-orthogonal.

### Claim 13 (depends on 10)

The method according to claim 10, wherein the matrix represents a low-density parity-check (LDPC) code.

### Claim 14 (depends on 10)

The method according to claim 10, further comprising:
encoding or decoding, by the one or more processors, data using the second matrix.

### Claim 15

A non-transitory computer-readable medium for providing a matrix for data processing within a communication system storing program instructions that when executed by a processor cause the processor to:
construct a first matrix, wherein all entries of the first matrix are either zero or one, wherein the first matrix is composed of a set of submatrices and each submatrix has a maximum column weight of one, and wherein each submatrix is obtained through grouping each row of the first matrix with one or more rest row of the first matrix;
expand the first matrix by a factor equal to z into an expanded matrix of size mb×nb in such a manner that the expanded matrix is z-row-orthogonal;
modify the expanded matrix into a second matrix of size mb×nb in such a manner that the second matrix is z-row-orthogonal; and
encode or decode data within the communication system based on the first matrix for a high parallelization of row decoding operations.

### Claim 16 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein program instructions that when executed by the processor further cause the processor to modify the expanded matrix by performing an operation comprising:
adding into the expanded matrix or removing from the expanded matrix at least one entry equal to one at a respective location of the expanded matrix that is chosen in such a manner that the second matrix is z-row-orthogonal.

### Claim 17 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein program instructions that when executed by the processor further cause the processor to modify the expanded matrix by performing an operation comprising:
adding into the expanded matrix or removing from the expanded matrix at least one row in such a manner that the second matrix is z-row-orthogonal.

### Claim 18 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the matrix represents a low-density parity-check (LDPC) code.

### Claim 19 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the program instructions that when executed by the processor further cause the processor to:
encode or decode data using the second matrix.