# US 2021/0376858 A1 · Method for optimizing protograph-based ldpc code over underwater acoustic channel

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

- Number: US 2021/0376858 A1
- Document ID: US20210376858A1
- Status: Published application
- Kind: A1
- Application number: 17/336,717
- Filed: 2021-06-02
- Published: 2021-12-02
- Earliest claimed: 2020-06-02
- Assignees: Zhejiang University
- Applicants: Zhejiang University
- Inventors: Lei XIE; Huifang Chen; Hongda Duan
- Web page: https://patentgrep.com/patent/US20210376858A1

## CPC

- H03M 13/033: {Theoretical methods to calculate these checking codes}
- H03M 13/1182: {wherein the structure of the parity-check matrix is obtained by reordering of a random parity-check matrix}
- H03M 13/1102: {Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes}
- H03M 13/1174: {Parity-check or generator matrices built from sub-matrices representing known block codes such as, e.g. Hamming codes, e.g. generalized LDPC codes}
- H03M 13/616: {Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations}
- H04B 11/00: Transmission systems employing ultrasonic, sonic or infrasonic waves
- H04B 13/02: Transmission systems in which the medium consists of the earth or a large mass of water thereon, e.g. earth telegraphy
- H03M 13/1131: {Scheduling of bit node or check node processing}
- 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)
- H04B: TRANSMISSION

## Abstract

The present disclosure provides a method for optimizing a protograph-based LDPC code over an underwater acoustic (UAW) channel. The traditional protograph-based LDPC code over an UAW channel does not consider performance in an error floor region. The method first determines parameters such as a protograph-based LDPC code length, a basic protograph, a target decoding threshold, a threshold adjustment factor, and an ACE check parameter. The protograph is optimized, and the method constructs a parity check matrix by using a UAW channel-based PEG/ACE hybrid algorithm, performs ACE check on the parity check matrix, and calculates a decoding threshold for the matrix passing the check. If the decoding threshold is within a range of an iterative decoding threshold, the parity check matrix is a final optimized matrix. Otherwise, the method continues to optimize the protograph until a parity check matrix passing the check is obtained.

## Claims

### Claim 1

A method for optimizing a protograph-based low-density parity-check (LDPC) code over an underwater acoustic (UAW) channel, comprising:
step (1). constructing an UAW channel transfer function based on an eigenray model: a channel is represented by a linear time-invariant finite impulse response filter, and z-transform for finite impulse response is: H(z)=Σl=1LAl×z−τl, wherein L denotes the number of multipaths of the channel in a symbol duration, Al is a signal amplitude of the l-th multipath, τl is a relative signal delay of the l-th multipath, and l=1, 2, . . . , L; and
determining, based on a basic protograph B and an LDPC code length N, first-extension times T1 and second-extension times T2 of the protograph, wherein
the basic protograph B is an m×n matrix, and
B
=
[
B
1
,
1
B
1
,
2
…
B
1
,
n
B
2
,
1
B
2
,
2
…
B
2
,
n
⋮
⋮
⋱
⋮
B
m
,
1
B
m
,
2
…
B
m
,
n
]
;
each row of the matrix corresponds to one check node, and there are a total of m check nodes; each column of matrix B corresponds to one variable node, and there are a total of n variable nodes; element Bi,j represents a quantity of edges between the i-th check node and the j-th variable node, i=1, 2, . . . , m, and j=1, 2, . . . , n;
a value of T1 is set to be greater than or equal to a maximum value of elements in the matrix of the basic protograph B,
N
T
1
×
n
is set to a minimum value among integers; and
T
2
=
N
T
1
×
n
;
step (2). selecting two variable nodes for the first optimization:
rearranging n variable nodes in the basic protograph B in descending order of column weights, to obtain a rearranged protograph B, wherein the column weight is the sum of values of m elements constituting a variable node;
wherein one of the variable nodes to be optimized is a variable node with a largest column weight in B, and a sequence number of the variable node is ja−1; the other variable node to be optimized is a variable node with the smallest column weight among variable nodes with a column weight greater than 2, and a sequence number of the variable node is jb; and jb>ja;
step (3). among m elements of the variable node numbered jb, subtracting 1 from a value of element Bi,jb with a maximum value, to reduce the column weight of the variable node numbered jb, wherein i∈(1, m); among m elements of the variable node numbered ja, adding 1 to a value of element Bi,ja, to keep a row weight of the i-th check node ci unchanged and increase the column weight of the variable node numbered ja, wherein the row weight is the sum of values of n elements constituting a check node; and a matrix with the values of the element Bi,jb and the element Bi,ja changed is an optimized protograph {tilde over (B)};
step (4): if ja+1≥jb−1, rearranging n variable nodes in the optimized protograph {tilde over (B)} in descending order of column weights, repeating steps (2) and (3) until ja+1<jb−1, and then performing step (5);
step (5): replicating check nodes and variable nodes in the optimized protograph {tilde over (B)} in step (4) for T1 times, and generating a transition graph B′ by using a traditional progressive edge growth (PEG) algorithm, wherein the transition graph B′ is an m′×n′ matrix, m′=T1×m, and n′=T1×n;
step (6): replicating check nodes and variable nodes in the transition graph B′ for T2 times, to obtain a derived graph matrix H; and interleaving all edges of H by using a UAW channel-based traditional PEG/approximate cycle extrinsic message degree (ACE) hybrid construction algorithm, to generate a parity check matrix H′;
step (7). performing ACE check on rings in which all variable nodes vj′ in the parity check matrix H′ are located:
if H′ does not pass the ACE check, using variable nodes numbered j′a and j′b in B′ as two variable nodes for the next optimization, and performing step (3), wherein j′a=ja+1, and j′b=jb−1;
if H′ passes ACE check, performing step (8);
step (8). calculating a decoding threshold γ′ for an optimized codeword by using an extrinsic information transfer chart algorithm of a finite-length protograph-based LDPC code over a UAW channel: if |γ−γ′|≥η, using the variable nodes numbered j′a and j′b in B′ as two variable nodes for the next optimization, and performing step (3), wherein γ is a target decoding threshold, η is a threshold adjustment factor, j′a=ja+1, and j′b=jb−1; if |γ−γ′|<η, performing step (9); and
step (9). obtaining a final optimized parity check matrix H=H′.

### Claim 2 (depends on 1)

The method for optimizing a protograph-based LDPC code over a UAW channel according to claim 1, wherein the eigenray model takes the propagation of sound waves as the propagation of countless rays perpendicular to an isophase plane, wherein each ray is perpendicular to the isophase plane, and the ray is an eigenray; it is assumed that a sound velocity and an refractive index do not change horizontally, but are only a function of sea depth; sea surface and seabed interfaces are assumed to be flat interfaces; positions of a sound source and a reception point are static and unchanged; a sound field is determined by the eigenray; and an entire UAW channel is taken as a network system.

### Claim 3 (depends on 1)

The method for optimizing a protograph-based LDPC code over a UAW channel according to claim 1, wherein the UAW channel-based PEG/ACE hybrid algorithm in step (6) includes:
(6-1). calculating a column weight wj′ of each variable node vj′ in H, wherein j′=1, 2, . . . , N, and rearranging the variable nodes in ascending order of column weights to obtain a rearranged derived graph {tilde over (H)}, wherein {tilde over (H)} is an M×N matrix, and
M
=
m
×
N
n
;
(6-2). adding L virtual check nodes (c′1, c′2, . . . , c′L) to {tilde over (H)}, and adding two virtual edges (vj′, c′l) and (vj′-τl, c′l) related to the variable node vj′ for any virtual check node c′l, that is, adding 2 L virtual edges in total, wherein L denotes the number of multipaths of the channel in a symbol duration, and l=1, 2, . . . , L;
(6-3). for vj′, generating wj′ generated edges ek, wherein k=1, 2, . . . , wj′, and the generating process is as follows:
taking vj′ as a root node, extending a path tree Rj′ based on the 2 L virtual edges, wherein the path tree Rj′ extends to layer d at most, d is a maximum number of layers that the path tree extends, and a set of candidate check nodes is C=Nj′(d); Nj′(d) represents a set of check nodes in the path tree Rj′, Nj′(d) is a complement of Nj′(d), Nj′(d)=Vc\Nj′(d), and Vc is a set of check nodes in {tilde over (H)} that are allowed to be connected to vj′;
calculating an ACE value of a ring generated by edges (vj′, cp) connecting candidate check nodes cp in C and vj′, wherein the ACE value of the ring is the sum of ACE values of all variable nodes on the ring, and an ACE value of a variable node is a column weight of the variable node minus 2; and
reserving an edge (vj′, cmax p) connecting a candidate check node cmax p with the largest ACE value of the ring and vj′ as the generated edge ek, and deleting other connected edges;
(6-4). deleting all virtual check nodes and virtual edges; and
(6-5). repeating (6-2) to (6-4) until the generated edges of all variable nodes in {tilde over (H)} are generated, to obtain the parity check matrix H′.

### Claim 4 (depends on 1)

The method for optimizing a protograph-based LDPC code over a UAW channel according to claim 1, wherein the ACE check method for the ring in which any variable node vj′ is located in step (7) is as follows:
(7-1). performing initialization: making all check nodes and all variable nodes except vj′ in the parity check matrix H′ satisfy ρ(μt)=∞, wherein μt represents all check nodes and all variable nodes except vj′ in the parity check matrix H′, ρ(μt) is an ACE value of a path (vj′, μt), an ACE value of a path is equal to the sum of ACE values of all variable nodes in the path, and ρ(vj′) is equal to an ACE value ACE(vj′) of the variable node vj′;
(7-2). taking vj′ as a root node, extending a path tree R′j, wherein the path tree R′j′ extends to layer dACE at most;
(7-3). finding a child node set Ch(ws) for any node ws with a depth of d′ in the path tree R′j′, wherein 0≤d′≤dACE; each node in Ch(ws) satisfies ws′∈Ch(ws); and if ρ(ws)+ρ(ws′)−ACE(vj′)<ε, the check fails, or if ρ(ws)+ρ(ws′)−ACE(vj′)≥ε, step (7-4) is performed, wherein ε represents an ACE check parameter;
(7-4). if ρ(ws)+ACE(ws′)≥ρ(ws′), deleting a path (ws, ws′) from the path tree R′j′;
if ρ(ws)+ACE(ws′)<ρ(ws′), setting ρ(ws′)=ρ(ws)+ACE(ws′), wherein ACE(ws′) is an ACE value of the node ws′; and
(7-5). repeating steps (7-3) and (7-4) until there is no check failure for nodes at all depths in the path tree R′j′, indicating that the check is successful.
