Protograph quasi-cyclic polar codes and related low-density generator matrix family

Patent metadata

Field	Value
Publication number	US-11463114-B2
Application number	US-202117181819-A
Country	US
Kind code	B2
Filing date	Feb 22, 2021
Priority date	Feb 22, 2021
Publication date	Oct 4, 2022
Grant date	Oct 4, 2022

Abstract

Data communications and storage systems require error control techniques to be transferred successfully without failure. Polar coding has been used as a state-of-the-art forward error correction code for such an error control technique. However, the conventional decoding based on successive cancellation has a drawback in its poor performance and long latency to complete. Because the factor graph of polar codes has a lot of short cycles, a parallelizable belief propagation decoding also does not perform well. The method and system of the present invention provide a way to resolve the issues by introducing a protograph lifting expansion for a polar coding family so that highly parallelizable decoding is realized to achieve a high coding gain and high throughput without increasing the computational complexity and latency. The invention enables an iterative message passing to work properly by eliminating short cycles through a hill-climbing optimization of frozen bits allocation and permutation.

First claim

What is claimed is:

1. A computer-implemented method for encoding digital data, performed by one or more computing processors, comprising:
defining a protograph structure of a polar-type low-density generator matrix (LDGM) code based on a code specification, wherein the code specification comprises at least two stages of proto-polarizations, at least one rule of frozen bits allocation, at least one rule of a protograph permutation, and at least one rule of a message passing;
accessing a source bit stream as an input digital data;
initializing a data array with the source bit stream and a set of frozen bits according to the rule of frozen bits allocation;
propagating the data array according to the rule of the message passing over the all stages of the proto-polarizations, further comprising the steps of:
(a) feeding the data array into the proto-polarization stages sequentially from one stage to another stage, wherein the proto-polarization stage comprises at least one proto-polarization unit;
(b) permuting the data array at each of the proto-polarization unit according to the rule of the protograph permutation; and
(c) modifying the data array at each of the proto-polarization unit according to the rule of the message passing;

arranging the modified data array into a codeword in a specified order; and
providing the codeword as an encoded digital data of the input digital data.

2. The method according to claim 1 , wherein the proto-polarization unit comprises
at least one proto-check node; and
at least one proto-variable node;

wherein at least one pair of the proto-check node and the proto-variable node is mutually connected to pass a multi-bit message according to the rule of the protograph permutation.

3. The method according to claim 1 , wherein the modifying the data array based on the rule of the message passing comprises applying a set of algebraic arithmetic operations at each of the proto-polarization unit, wherein the algebraic arithmetic operation is based on a finite ring, a finite Galois field, a look-up table, or a combination thereof.

4. The method according to claim 1 , wherein the code specification defining the protograph structure of the polar-type LDGM code is based on a lifting operation for a generator matrix of a base code, wherein the lifting operation applies a replication and a permutation of the base code by replacing each element of the generator matrix with a permutation matrix, and wherein the generator matrix is decomposed into at least two sub-generator matrices to define multiple proto-polarization stages.

5. The method according to claim 1 , wherein the rule of the protograph permutation comprises a set of parameters defining a circulant permutation with a shift value, a reversed circulant permutation with a shift value, a polynomial permutation with a set of polynomial coefficients, a random weight-one permutation matrix, a random weight-two permutation matrix, a random weight-three permutation matrix, or a combination thereof, associated with each of the proto-polarization.

6. The method according to claim 1 , wherein the rule of the frozen bits allocation and the rule of the protograph permutation are determined by an iterative method, comprising the steps of:
(a) initializing frozen bits locations, a skeleton base matrix, and a set of permutation parameters;
(b) pruning a set of the proto-polarization units depending on the skeleton base matrix;
(c) calculating an upper bound of error rate based on a protograph extrinsic information transfer (P-EXIT) method, wherein the P-EXIT method further comprises the steps of:
(b1) initializing a set of extrinsic information associated with each edge in the protograph, depending on the frozen bits locations and the permutation parameters given a set of channel mutual information;
(b2) updating the extrinsic information at a proto-polarization unit based on a set of P-EXIT rules defining an evolution of the extrinsic information;
(b3) repeating the updating step (b2) for a set of the proto-polarization units in a specified order depending on a decoding schedule; and
(b4) calculating the upper bound of error rate based on the updated extrinsic information and the frozen bits locations;

(c) calculating a score at each of proto-polarization unit, wherein the score is calculated by the steps of:
(c1) finding a cycle departing from a proto-polarization unit and returning the same proto-polarization unit through the protograph;
(c2) determining a cycle length depending on the frozen bits locations, the skeleton base matrix, and the permutation parameters;
(c3) adding a weighted value depending on the cycle length into all the scores associated with the proto-polarization units participated in the cycle;
(c4) repeating the above steps (c1) through (c3) for a specified set of paths in the protograph;

(d) modifying the frozen bits locations, the skeleton base matrix, and the permutation parameters based on the upper bounds and the scores; and
(e) repeating the above steps (b) through (d) until a specified condition meets for the upper bounds and the scores.

7. The method according to claim 1 , wherein the initializing the data array based on the rule of the frozen bits allocation further comprises the steps of:
(a) forming a bit sequence selectively chosen from a part of the data array;
(b) calculating a parity sequence from the bit sequence based on a linear code, comprising a cyclic redundancy check (CRC) code, a Bose-Chaudhuri-Hocquenghem (BCH) code, a cyclic code, a quasi-cyclic code, a convolutional code, or a combination thereof;
(c) embedding the parity sequence into a selected part of the data array;
(d) repeating the above steps (a) through (c) to embed a plurality of the parity bits into the data array for a specified number of times.

8. The method according to claim 4 , wherein the base code is a polar code, comprising at least two polarization stages based on at least two Kronecker power of a kernel matrix, wherein the kernel matrix is a full-rank matrix of an order size greater than one, and wherein the kernel matrix is based on a finite Galois field, a finite ring, or a combination thereof.

9. The method according to claim 1 , wherein the protograph structure defined by the code specification is based on a spatial coupling of the proto-polarization units, wherein the spatial coupling forms the protograph structure in a homogeneous or inhomogeneous manner to construct a rectangular, a cubic, a braided, a staircase, or a torus shape of the protograph with or without a tail biting.

10. A computer-implemented method for decoding a noisy codeword, performed by one or more computing processors, comprising:
defining a protograph structure of a polar-type low-density generator matrix (LDGM) code based on a code specification, wherein the code specification comprises at least two stages of proto-polarizations, at least one rule of frozen bits allocation, at least one rule of a protograph permutation, and at least one rule of a message passing;
accessing an input data which represents a belief message for a noisy codeword;
initializing an array of leftward and rightward messages associated with each edge in the protograph, wherein the rightward messages feeding into a first stage of the proto-polarizations are fixed based on the rule of the frozen bits allocation and the leftward messages feeding into a last stage of the proto-polarizations are fixed based on the input data in a specified order;
propagating the leftward and rightward messages according to the rule of the message passing across multiple stages of the proto-polarizations comprising at least one variable node and at least one check node, w

Assignees

• Mitsubishi Electric Res Laboratories Inc

Inventors

• Koike-Akino Toshiaki
• Wang Ye

Classifications

• H03M13/13 Primary

  Linear codes · CPC title

• G06F13/4027

  using bus bridges (G06F13/4022 takes precedence) · CPC title

• G06F13/4282

  on a serial bus, e.g. I2C bus, SPI bus (on daisy chain buses G06F13/4247) · CPC title

• H03M13/116

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

• H03M13/458 Primary

  by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result · CPC title