Universal error control coding scheme for digital communication and data storage systems

• US 8,069,390 B2
• Filed: 06/28/2007
• Issued: 11/29/2011
• Est. Priority Date: 07/25/2006
• Status: Expired due to Fees

• Current Assignee: Communications Coding Corporation
• Original Assignee: Communications Coding Corporation
• Inventors: Lin, Shu
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US11/770,480
• Publication Number:
  US 20080028274A1
• Time in Patent Office: 1,615 Days
• Field of Search: 714/758, 714/801
• US Class Current: 714/758
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/1128 Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations
• CPC Class Codes: H03M 13/116 Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
• CPC Class Codes: H03M 13/1171 Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes
• CPC Class Codes: H03M 13/353 Adaptation to the channel
• CPC Class Codes: H03M 13/6511 Support of multiple decoding rules, e.g. combined MAP and Viterbi decoding
• CPC Class Codes: H03M 13/6513 Support of multiple code types, e.g. unified decoder for LDPC and turbo codes

Abstract

The universal forward error-correction coding system provides adjustable code rates and coding gains to greatly benefit the design of many modern digital communications (data storage) systems. The channel encoding and decoding methods are universal such that a single encoder and a single decoder can be used to implement all the forward error-correction codes of different code rates. This universal forward error-correction coding system also includes a novel systematic code generation procedure that has the capability of generating many classes of codes that provide the best balance between coding gain performance and implementation complexity.

Claims

1. A method for providing forward error-correction coding for data that is transmitted from a source to a destination over a communication medium, comprising:

encoding message blocks, u, of said data to codewords, v, as follows;

v=uG, where G is a generator matrix; and

using a Quasi-Cyclic Low Density Parity Check Code to implement a parity check matrix H, such that every vector in the row space of the generator matrix G is orthogonal to the rows of parity check matrix H and parity check matrix H is given as an array of sparse circulant matrices of the same size comprising;

defining said selected Quasi-Cyclic Low Density Parity Check Code C_qc as the null space of a parity check matrix H_qc, which is a c×

t array of b×

b circulants over the binary Galois field GF(2) of the form given by;

2. The method for providing forward error-correction coding of claim 1 using a Quasi-Cyclic Low Density Parity Check Code C_qc with parity check matrix H_qc wherein said step of using comprises:

forming said generator matrix where the rank r_H of H_qc is equal to cb, assume that the columns of circulants of H_qc are arranged in such a way that the rank of the following c×

c subarray of H_qc,

3. The method for providing forward error correction coding of claim 2 wherein said step of using further comprises:

forming a c×

c array of b×

b circulants D<sup>−

1</sup> based on the circulants in D;

4. The method for providing forward error correction coding of claim 3 wherein said step of using further comprises:

letting B_j=[B_j,1 . . . B_j,c] (the j-th row of D<sup>−

1</sup>);

multiplying out the right side of this equation to obtain the circulants G_i,js in G_qc;

5. The method for providing forward error correction coding of claim 4 wherein said step of using further comprises:

let a=(a₁, a₂, . . . , a<sub>t−

c</sub>) be the information sequence to be encoded and v=(a, p₁, p₂, . . . , p_c) be its codeword and v^T=G_qc^Ta^T, compute the j-th parity section p_j as;

6. The method for providing forward error correction coding of claim 5 wherein said step of using further comprises:

divide the vector y into c sections, y=(y₁ y₂ . . . y_c), where for 1≦

k≦

c, the k-th section y_k=(y_k,1, y_k,2, . . . , y_k,b) and for 1≦

i≦

t−

c, M_i is the i-th column of circulants of H_qc where the k-th section y_k is given by;

7. The method for providing forward error correction coding of claim 2 using a two-stage encoding circuit to complete the encoding of (t−

c)b information bits in 2b clock cycles comprising;

read all the t−

c information sections a=(a₁, a₂, . . . , a<sub>t−

c</sub>) into corresponding ones of (t−

c) b-bit feedback shift-registers, FR₁, FR₂, . . . , FR<sub>t−

c</sub>, in one clock cycle;

switch each output of each of said (t−

c) b-bit feedback shift-registers, FR₁, FR₂, . . . , FR<sub>t−

c</sub>, to corresponding ones of c XOR gates as defined by the “

1”

bits in A_k,i, where 1≦

k≦

c;

form the bits y_1,1, y_2,1, . . . , y_c,1 at the outputs of the c banks of XOR-gates;

shift the bits y_1,1, y_2,1, . . . , y_c,1 into (c) b-bit buffer registers, BR₁, BR₂, . . . , BR_c;

cyclically shift the bits stored in said (t−

c) b-bit feedback shift-registers, FR₁, FR₂, . . . , FR<sub>t−

c</sub> to the left in parallel b−

1 times to generate all the other bits of y;

at the end of the b-th clock cycle, all the c sections of y are stored in said (c) b-bit buffer registers, BR₁, BR₂, . . . , BR_c to complete the first stage of encoding;

form the c parity sections based on p_j^T=B_jy^T by cyclically shifting said (c) b-bit buffer registers, BR₁, BR₂, . . . , BR_c, b times (left shift) to generate all the other bits of p.

8. The method for providing forward error correction coding of claim 1 wherein the step of using comprises:

selecting the parity check matrix H to have constant row and column weights, the number of “

1'"'"'s”

in common between any two columns is no greater than one, and the parity check matrix H has a small density of “

1'"'"'s.”

9. The method for providing forward error correction coding of claim 1 wherein the step of using comprises:

selecting said Quasi-Cyclic Low Density Parity Check Code as a linear code for which shifting a codeword a fixed number of bit positions results in another codeword.

10. The method for providing forward error correction coding of claim 1 wherein a circulant is a square matrix in which each row is the cyclic shift one place to the right of the row above it and the first row is the cyclic shift of the last row.

11. The method for providing forward error correction coding of claim 1 wherein said step of encoding comprises:

dividing said data into message blocks of k bits each;

mapping each of the message blocks into a unique codeword which consists of a block of n bits, where k<

n; and

making every codeword v a linear combination of k basis vectors;

v=u₀g₀+u₁g₁+ . . . +u<sub>k−

1</sub>g<sub>k−

1</sub> to form the k×

n generator matrix G, using these linearly independent vectors g₀, . . . , g<sub>k−

1</sub> as its rows.

12. The method for providing forward error correction coding of claim 1 wherein said step of using comprises:

dividing the file a into (t−

c) sections of equal length of b consecutive information bits;

selecting the codeword for the information sequence a as v=aG_qc, which has the following systematic form;

v=(a, p₁, p₂, . . . , p_c), where for 1≦

j≦

c, p_j=(p_j,1, p_j,2, . . . , p_j,b) is a section of b parity-check bits;

and it follows from v=aG_qc that;

13. The method for providing forward error correction coding of claim 1 further comprising:

decoding said coded data using a Bit-Flipping decoding algorithm, comprising;

(1) Compute the parity check sums (syndrome bits). If all the parity check equations are satisfied (i.e., all the syndrome bits are zero), stop the decoding,

(2) Find the number of unsatisfied parity check equations for each code bit position, denoted f_i, i=0, 1, . . . , n−

1,

(3) Identify the set of bits for which f_i is the largest,

(4) Flip the bits in set, and

(5) Repeat steps 1 to 4 until all the parity check equations are satisfied or a predefined maximum number of iterations is reached.

14. The method for providing forward error correction coding of claim 1 further comprising:

decoding said coded data using a Weighted Bit-Flipping decoding algorithm, comprising;

(1) Compute the check sums, and if all the parity check equations are satisfied, stop the decoding;

(2) Compute E_l, for 0≦

l≦

n−

1 for the soft-decision received sequence y=(y₀, y₁, . . . , y<sub>n−

1</sub>);

15. The method for providing forward error correction coding of claim 1 further comprising:

decoding said coded data using a Sum-Product Algorithm decoding algorithm, comprising;

(1) Set i=0 and the maximum number of iterations to I_max,

(2) For every pair (j, l) such that h_j,l=1 with 1≦

j≦

J and 0≦

l≦

n−

1, set q_j,l^0,(0)=p_l⁰ and q_j,l^1,(0)=p_l¹,

(3) For 0≦

l≦

n−

1, 1≦

j≦

J and each h_j∈

A_l, compute the probabilities, σ

_j,l^0,(i) and σ

_j,l^1,(i), where A_l is the set of rows of the parity check matrix H that are orthogonal to code bit v_l,

(4) For 0≦

l≦

n−

1, 1≦

l≦

j≦

J and each h_j∈

A_l, compute the values of q_j,l^0,(i+1) and q_j,l^1,(i+1) and the values of P⁽ⁱ⁺¹⁾(v_l=0|y) and P⁽ⁱ⁺¹⁾(v_l=1|y);

then form z⁽ⁱ⁺¹⁾, test z⁽ⁱ⁺¹⁾·

H^T, and if z⁽ⁱ⁺¹⁾·

H^T=0 or the maximum iteration number I_max is reached, go to Step (e);

otherwise, set i;

=i+1 and go to Step (3), and

(5) Output z⁽ⁱ⁺¹⁾ as the decoded codeword and stop the decoding process.

16. The method for providing forward error correction coding of claim 1 further comprising:

decoding said coded data using a Double-Weighted Bit Flipping decoding algorithm, comprising;

denoting z=(z₀, z₁, . . . , z<sub>n−

1</sub>) to be the hard decisions sequence obtained from the soft-decision received sequence y=(y₀, y₁, . . . , y<sub>n−

1</sub>), where

17. The method for providing forward error correction coding of claim 1 wherein the step of using comprises:

selecting said Quasi-Cyclic Low Density Parity Check Code as a q-ary linear code for which shifting a codeword a fixed number of bit positions results in another codeword.

18. The method for providing forward error correction coding of claim 17 wherein the step of using comprises:

selecting the parity check matrix H to have constant row and column weights, no two rows or two columns of the parity check matrix H have more than one position at which both have nonzero components in the binary Galois field GF(q), and the parity check matrix H has a small density of nonzero components.

19. The method for providing forward error correction coding of claim 18 wherein said step of encoding comprises:

dividing said data into message blocks represented by a k-tuple u=(u₀, . . . u<sub>k−

1</sub>), where each message symbol u_i is an element of the Galois field GF(q);

mapping each of the message blocks into a unique codeword which is an n-tuple v=(v₀, . . . v<sub>n−

1</sub>), and each code symbol v_l is an element of the Galois field GF(q); and

making the set of codewords v a k-dimensional subspace of the vector space of all the n-tuples over the Galois field GF(q) to form the k×

n generator matrix G over the Galois field GF(q).