US 2022/0278698 A1 · Protograph Quasi-Cyclic Polar Codes and Related Low-Density Generator Matrix Family

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.

Claims27

Dependent claims

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.

8 more elements

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, wherein the leftward and rightward messages are updated by an iterative method comprising the steps of:
(a) selecting a parallelizable set of variable and check nodes according to the rule of message passing;
(b) feeding a set of the leftward and rightward messages as incoming messages into the chosen variable and check nodes according to the rule of the protograph permutation;
(c) calculating a set of outgoing messages based on the incoming messages at the chosen variable and check nodes, according to the rule of the message passing;
(d) replacing a set of the leftward and rightward messages with the outgoing messages at the chosen variable and check nodes;
and
(e) repeating the above steps (a) through (d) for a specified number of times according to the rule of the message passing;
selecting a set of the leftward messages as an output message in a specified order;
and
providing the output message as a decoded digital data.

10 more elements

An encoder circuit configured to generate an encoded digital data from a source bit stream as an input digital data, comprising:

an encoder interface configured to receive the source bit stream;
at least one memory bank configured to store a computer-executable encoding method;
one or more computing processors configured to generate a codeword as an encoded digital data from the input digital data by performing steps of the computer-executable encoding method, wherein the steps comprise:
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 protograph permutation, and at least one rule of a message passing;
initializing a data array with the source bit stream and a set of frozen bits according to the at least one rule of frozen bits allocation;
propagating the data array according to the at least one rule of the message passing over entire stages of the proto-polarizations, wherein the steps further comprising:
(a) feeding the data array into the at least two stages of the proto-polarizations sequentially from one stage to another stage, wherein each stage of the proto-polarizations comprises at least one proto-polarization unit;
(b) permuting the data array at each of the proto-polarization unit according to the at least one rule of the protograph permutation;
and
(c) modifying the data array at each of the proto-polarization unit according to the at least one rule of the message passing;
and
generating the codeword based on a specified order as the encoded digital data by arranging the modified data array.

9 more elements

A decoder circuit configured to generate a decoded digital data from a noisy version of an encoded codeword, comprising:

a decoder interface configured to receive the noisy encoded codeword as an input data;
at least one memory bank configured to store a computer-executable decoding method;
one or more computing processors configured to generate the decoded digital data from the encoded codeword from the decoder interface by performing steps of the computer-executable decoding method, wherein the steps comprise:
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 protograph permutation, and at least one rule of a message passing;
initializing an array of leftward and rightward messages associated with each edge in the protograph structure, wherein the rightward messages feeding into a first stage of the proto-polarizations are fixed based on the at least one rule of the frozen bits allocation and the leftward messages feeding into a last stage of the proto-polarizations are fixed based on the encoded codeword in a specified order;
propagating the leftward and rightward messages according to the at least one rule of the message passing across the at least two stages of the proto-polarizations comprising at least one variable node and at least one check node, wherein the leftward and rightward messages are updated by an iterative method, wherein the iterative method comprises steps of:
(a) selecting a parallelizable set of variable and check nodes according to the at least one rule of message passing;
(b) feeding a set of the leftward and rightward messages as incoming messages into the selected variable and check nodes according to the at least one rule of the protograph permutation;
(c) calculating a set of outgoing messages based on the incoming messages at the selected variable and check nodes,
according to the at least one rule of the message passing;
(d) replacing the set of the leftward and rightward messages with the set of outgoing messages at the selected variable and check nodes;
and
(e) repeating the steps (a) through (d) for a specified number of times according to the at least one rule of the message passing;
and
generating an output message as a decoded digital data by selecting a set of the leftward messages in a specified order.

12 more elements

Dependencies are inferred from the claim text.

Protograph Quasi-Cyclic Polar Codes and Related Low-Density Generator Matrix Family

Life of this patent

Protograph Quasi-Cyclic Polar Codes and Related Low-Density Generator Matrix Family

Life of this patent

Abstract

Claims27