Constructing method, processing device, storage medium and coding method

Patent metadata

Field	Value
Publication number	US-2024007129-A1
Application number	US-202318168888-A
Country	US
Kind code	A1
Filing date	Feb 14, 2023
Priority date	Jun 30, 2022
Publication date	Jan 4, 2024
Grant date	—

Abstract

There are provided a method for constructing a permutation matrix or a check matrix, a processing device, a storage medium and a coding method. The method of constructing a permutation matrix includes: obtaining a base matrix used for the permutation matrix; and lifting the base matrix to obtain the permutation matrix, which includes: obtaining a protograph of the base matrix; and obtaining each macro-cycle in the protograph, and for each macro-cycle in the protograph, determining a size of a short cycle corresponding to the macro-cycle in a Tanner graph of the check matrix corresponding to the permutation matrix by an equivalent cyclic value ECS of the macro-cycle, and determining whether at least one cyclic value in the macro-cycle needs to be set according to the size of the short cycle. The method can efficiently obtain the permutation matrix as required.

First claim

What is claimed is:

1 . A method of constructing a permutation matrix for QC-LDPC codes, comprising:
obtaining a base matrix used for the permutation matrix; and lifting the base matrix to obtain the permutation matrix, which comprises:
obtaining a protograph of the base matrix; and
obtaining each macro-cycle in the protograph, and for each macro-cycle in the protograph, determining a size of a short cycle corresponding to the macro-cycle in a Tanner graph of the check matrix corresponding to the permutation matrix by an equivalent cyclic value ECS of the macro-cycle, and determining whether at least one cyclic value in the macro-cycle needs to be set according to the size of the short cycle.

2 . The method according to claim 1 , wherein the lifting the base matrix to obtain the permutation matrix further comprises:
enabling ECSs of all macro-cycles in the protograph to meet requirements of the Tanner graph of the check matrix on a minimum short cycle and requirements on external information freedom degree.

3 . The method according to claim 1 , wherein the lifting the base matrix to obtain the permutation matrix further comprises:
obtaining ECSs of the macro-cycles, wherein it is assumed that the macro-cycle of size 2*L on the protograph is composed of cyclic values {P(i 0 ,j 0 ), P(i 0 ,j 1 ), P(i 1 ,j 1 ), P(i 1 ,j 2 ), . . . , P(i (L-1) ,j L )}, wherein j L =j 0 , L is a positive integer, then the equivalent cyclic values (ECSs) are determined by the following:

ECS
=

∑

l
=
0

L
-
1

(

-

P
⁡
(

i
l

,

j
l

)

+

P
⁡
(

i
l

,

j

l
+
1

)

)

.

4 . The method according to claim 1 , wherein the obtaining each macro-cycle in the protograph, and for each macro-cycle in the protograph, the determining the size of the short cycle corresponding to the macro-cycle in the Tanner graph of the check matrix corresponding to the permutation matrix by the equivalent cyclic value ECS of the macro-cycle, and the determining whether at least one cyclic value in the macro-cycle needs to be set according to the size of the short cycle comprises:
taking each variable node in the protograph of the base matrix as a root node to expand into a tree, and searching the tree to check whether there is a macro-cycle corresponding to the tree.

5 . The method according to claim 4 , wherein the taking each variable node in the protograph of the base matrix as the root node to expand into the tree, and the searching the tree to check whether there is a macro-cycle corresponding to the tree comprises:
according to the base matrix, establishing variable node information and check node information of the protograph of the base matrix; based on the variable node information and the check node information, establishing a transfer information combination used for transmission among nodes during the tree search; and setting an initial value of the transfer information combination, and recursively calling the tree to perform the tree search to check whether there is a macro-cycle corresponding to the tree.

6 . The method according to claim 5 , wherein each of the variable node information and the check node information includes a node index, a number of neighbor nodes, and an index array of neighbor nodes.

7 . The method according to claim 5 , wherein the transfer information combination comprises a root node index, a parent node index, a current search depth, and a cycle node index, wherein
the cycle node index is used to record the node indexes of all nodes that constitute a cycle.

8 . The method according to claim 7 , wherein the transfer information combination further comprises a minimum cycle threshold of the Tanner graph of the check matrix and a minimum threshold of the external information freedom degree of the Tanner graph of the check matrix.

9 . The method according to claim 5 , wherein the obtaining each macro-cycle in the protograph, and for each macro-cycle in the protograph, the determining the size of the short cycle corresponding to the macro-cycle in the Tanner graph of the check matrix corresponding to the permutation matrix by the equivalent cyclic value ECS of the macro-cycle, and the determining whether at least one cyclic value in the macro-cycle needs to be set according to the size of the short cycle further comprises:
in the process of the tree search, for each currently searched variable node in the tree: if the current search depth has met the minimum cycle threshold of the Tanner graph of the check matrix, stopping the tree search and returning a success flag; if the current search depth does not reach the minimum cycle threshold, but the first macro-cycle has been found in the tree search, then using the equivalent cyclic value ECS of the first macro-cycle to check or allocate respective cyclic values constituting the first macro-cycle, so that the short cycle on the Tanner graph of the check matrix is greater than or equal to the minimum cycle threshold; or if the current search depth does not reach the minimum cycle threshold, and any macro-cycle is found in the tree search, then continuing the tree search.

10 . The method according to claim 9 , wherein, in the process of the tree search, it is further checked whether there is a deadlock for each currently searched variable node in the tree, and if the deadlock occurs, the tree search is stopped.

11 . The method according to claim 9 , wherein the checking or allocating respective cyclic values constituting the first macro-cycle by using the equivalent cyclic value ECS of the first macro-cycle comprises:
if a certain cyclic value constituting the first macro-cycle has not been allocated, then randomly selecting a value within [0, Z−1], and if the ECS of the first macro-cycle meets the minimum cycle threshold, stopping the tree search and returning a success flag; and if all the cyclic values constituting the first macro-cycle have been allocated, but the ECS of the first macro-cycl

Assignees

• Beijing Eswin Computing Tech Co Ltd
• Guangzhou Transa Semi Information Tech Co Ltd

Inventors

• Wu Yanqi
• Dai Yanzhong
• Rong Sujiang

Classifications

• H03M13/116 Primary

  Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• H03M13/616

  Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations · CPC title

• H04L1/0063

  Single parity check · CPC title

• H03M13/1185

  wherein the parity-check matrix comprises a part with a double-diagonal · CPC title