Back to results
US 7,831,895 B2Granted
Universal error control coding system for digital communication and data storage systems
AssigneeCommunications Coding Corporation
InventorShu Lin
Life of this patent
Estimating the term…
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.
Claims17
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- selecting the parity check matrix H to have constant row and column weights, the number of “1s” in common between any two columns is no greater than one, and the parity check matrix H has a small density of “1s.”
2 more elements
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, comprising:
- 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=u0g0+1g1+ . . . +uk−1gk−1 to form the k×n generator matrix G, using these linearly independent vectors g0 . . . gk−1 as its rows;
- and
- using a parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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.
6 more elements
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- selecting said Quasi-Cyclic Low Density Parity Check Code from a structurally compatible family of codes to provide code lengths, code rates, and coding gain performances that are adaptable to changing conditions, wherein said changing conditions include:
- channel and storage medium conditions, error performance requirements, and information message throughput requirements.
3 more elements
A method for providing forward error-correction coding for data comprising an information sequence that is transmitted from a source to a destination over a communication medium, comprising:
- encoding message blocks, u, of said information sequence a to codewords, v, as follows:
- v=uG, where G is a generator matrix;
- and
- using a parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- dividing the information sequence a into (t−c) sections of equal length of b consecutive information bits;
- selecting the codeword for the information sequence a as v=a Gqc, which has the following systematic form:
- v=(a, p1, p2, . . . , pc), where for 1≦j≦c, pj=(pj,1, pj,2, . . . , pj,b) is a section of b parity-check bits, wherein it follows from v=a Gqc that:
- p
- j
- =
- ∑
- i
- =
- 1
- t
- -
- c
-
- a
- i
-
- G
- i
- ,
- j
- for 1≦j≦c, and for 0≦l≦b, let gi,j(l) be the l-th (right) cyclic shift of the generator gi,j, with gi,j(0)=gi,j(b)=gi,j;
- then for 1≦i≦≦t−c,
- aiGi,j=a(i−1)b+1gi,j(0)+a(i−1)b+2gi,j(1)+ . . . +aibgi,j(b−1),
- for 1 ≦k<t−c, at the k-th step, the accumulated sum, sk,j=a1G1,j+a2G2,j+ . . . +akGk,j, is formed and stored in a register;
- compute, at the (k+1)th step, the partial sum ak+1Gk+1,j from equation:
- ak+1Gk+1,j=akb+1gk+1,j(0)+akb+2gk+1,j(1)+ . . . +a(k+1)bgk+1,j(b−1),
- and add the partial sum to sk,j to form the next accumulated sum sk+1,j;
- and
- at the end of (t−c)-th step, the accumulated sum st−c,j gives the j-th parity section pj.
31 more elements
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- decoding said coded data using a Bit Flipping decoding algorithm, comprising:
- (a) Compute the parity check sums (syndrome bits), and if all the parity check equations are satisfied (i.e., all the syndrome bits are zero), stop the decoding;
- (b) Find the number of unsatisfied parity check equations for each code bit position, denoted fi, i=0, 1, . . . , n−1;
- (c) Identify the set of bits for which fi is the largest;
- (d) Flip the bits in set, and
- (e) Repeat steps (a) to (d) until all the parity check equations are satisfied or a predefined maximum number of iterations is reached.
7 more elements
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- decoding said coded data using a Weighted Bit Flipping decoding algorithm, comprising:
- denoting z=(z0, z1, . . . , zn−1) to be the hard decisions sequence obtained from the soft-decision received sequence y=(y0, y1, . . . , yn−1), where
- z
- j
- =
- {
- 1
- ,
- for
-
-
- y
- j
- >
- 0
- ,
- 0
- ,
- for
-
-
- y
- j
- ≤
- 0
- ,
- (a) Compute the check sums, and if all the parity check equations are satisfied, stop the decoding;
- (b) Compute El, for 0≦l≦n−1 for the soft-decision received sequence y=(y0, y1, . . . , yn−1):
- E
- l
- =
- ∑
- s
- j
- (
- l
- )
- ∈
- S
- l
-
- (
- 2
-
- s
- j
- (
- l
- )
- -
- 1
- )
- ·
-
- y
- j
-
- min
- (
- l
- )
- where |yj|min(l)=min {|yi|:0≦i≦n−1,hj,i(l)=1} and where Sl is the set of check sums sj(l) orthogonal on code bit-position l;
- (c) Find the bit position l for which El is the largest;
- (d) Flip the bit zl, and
- (e) Repeat steps (a) to (d), wherein this process of bit flipping continues until all the parity check equations are satisfied or a preset maximum number of iterations is reached.
66 more elements
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- decoding said coded data using a Sum-Product Algorithm decoding algorithm, comprising:
- (a) Set i=0 and the maximum number of iterations to Imax,
- (b) For every pair (j,l) such that hj,l=1 with 1≦j≦J and 0 ≦l≦n−1, set qj,l0,(0)=pl0=Pr(vl=0) and qj,l1,(0)=pl1=Pr(vl=1),
- (c) For 0≦l≦n−1,1≦j≦J and each hjεAl, compute the probabilities, σj,l0,(i) and σj,l1,(i), where Al is the set of rows of the parity check matrix H that are orthogonal to code bit vl.
- (d) For 0≦l≦n−1,1≦j≦J and each hjεAl, compute the values of qj,l0,(i+1) and qj,l1,(i+1) and the values of P(i+1)(vl=0|y) and P(i+1)(vl=1|y);
- then form z(i+1), test z(i+1)·HT, and if z(i+1)·HT=0 or the maximum iteration number Imax is reached, go to Step (e);
- otherwise, set i:=i+1 and go to Step (c), and
- (e) Output z(i+1) as the decoded codeword and stop the decoding process.
9 more elements
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- decoding said coded data using a Double-Weighted Bit Flipping decoding algorithm, comprising:
- denoting z=(z0, z1, . . . , zn−1) to be the hard decisions sequence obtained from the soft-decision received sequence y=(y0,y1, . . . , yn−1), where
- z
- j
- =
- {
- 1
- ,
- for
-
-
- y
- j
- >
- 0
- ,
- 0
- ,
- for
-
-
- y
- j
- ≤
- 0
- ,
- computing the syndrome s=(s0, s1, . . . , sn−1) for the sequence z given by s=zHT,
- stop the decoding if all parity equations are satisfied, otherwise, s≠0,
- define r=(r0, r1, . . . , rn−1), where rj=|yj|,
- for each check-sum record the largest and the smallest values among the received soft-decision sequence y that is related to check-sum sj, where 1≦j≦J,
- for 1≦j≦J, denote K(j)={0≦i≦n−1:hj,i=1}, and let Uj=max {|yi|:iεK(j)} and Lj=min {|yi|:iεK(j)} be the largest and the smallest soft-decision samples respectively corresponding to the check-sum sj,
- calculate a weighted check sum Tl for every bit position l, 0≦l≦n−1,
- by performing the following computation:
- T
- l
- =
- ∑
- j
- ∈
- M
-
- (
- l
- )
-
- T
- j
- ,
- l
-
- R
- j
- ,
- l
- where M(l)={1≦j≦J:hj,l=1}
- where
- R
- j
- ,
- l
- =
- (
- 1
- +
- exp
- (
- -
- 4
-
-
- min
- i
- ∈
- N
-
- (
- j
- )
- /
- l
-
-
- y
- i
-
- N
- 0
- )
- )
- -
- 1
- where N(j)={i:hj,i=1}
- flip the bit in zj with smallest Tj value,
- recompute the syndrome s=zHT for this bit-flipped sequence z, and
- if s=0, stop the decoding;
- otherwise, repeat this iteration step if the number of iterations is less than the preset maximum allowable number of iterations.
97 more elements
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- selecting, where q>2, said Quasi-Cyclic Low Density Parity Check Code as a q-ary linear code over the Galois field GF(q) for which shifting a codeword a fixed number of bit positions results in another codeword.
2 more elements
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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:
- selecting, where q>2, said Quasi-Cyclic Low Density Parity Check Code as a q-ary linear code over the Galois field GF(q) from a structurally compatible family of codes, all of which can be encoded using one universal encoder and decoded using one universal decoder.
2 more elements
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 parity check matrix H to implement a Quasi-Cyclic Low Density Parity Check Code, 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 His given as an array of sparse circulant matrices of the same size, comprising:
- selecting said Quasi-Cyclic Low Density Parity Check Code from a structurally compatible family of codes, all of which can be encoded using one universal encoder and decoded using one universal decoder.
2 more elements
Dependencies are inferred from the claim text.