Decoder and decoding method for low-density parity check codes constructed based on reed-solomon codes
Configurable permutators in an LDPC decoder are provided. A partially-parallel architecture combined with the proposed permutators is used to mitigate the increase in implementation complexity for the multi-mode function. To overcome the difficulty in efficient implementation of a high-throughput decoder, the variable nodes are partitioned into several groups, and each group is processed sequentially in order to shorten the critical-path delay and, hence, increase the maximum operating frequency. In addition, shuffled message-passing decoding can be adopted in decoders according to the invention to increase the convergence speed, which reduces the number of iterations required to achieve a given bit-error-rate performance.
1. A decoder for a low-density parity check (LDPC) code constructed based on a Reed-Solomon (RS) code, comprising:
a permutation circuit for providing configurable connections defined by a sub-matrix B(i 0 , j 0 ) in a parity check matrix, the parity check matrix being related to a Galois field GF(p s ), wherein p is a prime, s is a positive integer, i 0 and j 0 are integer indices ranging from 0 to (p s −1), a set of input comprising p s elements, the permutation circuit comprising:
a first permutator for fixing the first element in the set of input and cyclically shifting the other (p s −1) elements in the set of input by j 0 positions, so as to generate a first set of temporary elements;
a fixed routing, for rearranging the first set of temporary elements, so as to generate a second set of temporary elements; and
a second permutator for fixing the first element in the second set of temporary elements and cyclically shifting the remaining (p s −1) elements of the second set of temporary elements by i 0 positions.
2. The decoder in claim 1 , the decoder being in a receiver conforming to a 10-gigabit Ethernet specification.
3. The decoder in claim 1 , wherein when the LDPC code is an extended RS code, (p s −1) connections in the second permutator for cyclically shifting the (p s −1) elements of the second set of temporary elements are fixed.
4. The decoder in claim 1 , the decoder using column scheduling and comprising a plurality of the permutation circuits, wherein when the LDPC code is an extended RS code, the integer indices i 0 in the permutation circuits are the same, the first permutator comprises a barrel shifter, and the second permutator comprises plural fixed connections.
5. The decoder in claim 1 , wherein the first permutator and the second permutator respectively comprise a barrel shifter.
6. The decoder of claim 1 , wherein the parity check matrix comprises γ×ρ sub-matrices, the first (ρ−1) sub-matrices in a first block row of the parity check matrix are type-I sub-matrices, the γ sub-matrices in a last block column of the parity check matrix are type-II sub-matrices, and the other (γ−1)×(ρ−1) sub-matrices in the parity check matrix are type-III sub-matrices, γ and ρ are positive integers, and the sub-matrix B(i 0 , j 0 ) is one of the type-I sub-matrices or the type-III sub-matrices.
7. The decoder of claim 1 , further comprising:
a check-node operation module for generating a check-to-variable message R ij [k] associated with a j-th variable node for an i-th check node at a k-th iteration according to the following equation:
R ij [k]=S ij [k] ×max{(| R ij ′ [k]|−δ), 0},
wherein S ij [k] is a positive/negative sign of R ij [k], δ is an offset constant, the check-node operation module selects |R ij ′ [k]| from {|Q j 0 i |, |Q j 1 i |, . . . , |Q j ω-1 i |};
wherein {|Q j 0 i |, Q j 1 i |, . . . , |Q j ω-1 i |} are the ω smallest values among a plurality of variable-to-check messages associated to the i-th check node;
wherein i is an integer index ranging from 0 to (M−1), j is an integer index ranging from 0 to |I R [i]|, k is an iteration number, ω is an integer ranging from 3 to (|I R [i]|−1), M is the number of rows of the parity check matrix, and |I R [i]| is the i-th row weight of the parity check matrix.
8. The decoder of claim 7 , wherein |Q j 0 i |, Q j 1 i |, . . . , |Q j ω-1 i | are generated in the k-th iteration or a (k−1)-th iteration previous to the k-th iteration.
9. The decoder of claim 7 , wherein the (k+1)-th iteration is aborted if the most significant bit of the absolute value of R ij [k] is equal to 1.
10. A decoding method for low-density parity check (LDPC) codes constructed based on Reed-Solomon (RS) codes, a parity check matrix being related to a Galois field GF(p s ), p being a prime, s being a positive integer, i 0 and j 0 being integer indices ranging from 0 to (p s −1), a set of input comprising p s elements, the decoding method comprising the following steps:
for the set of input, providing configurable rearrangements defined by a sub-matrix B(i 0 , j 0 ) in the parity check matrix by:
fixing the first element in the set of input and cyclically shifting the other (p s −1) elements in the set of input by j 0 positions, so as to generate a first set of temporary elements;
rearranging the first set of temporary elements, so as to generate a second set of temporary elements; and
fixing the first element in the second set of temporary elements and cyclically shifting the remaining (p s −1) elements of the second set of temporary elements by i 0 positions.
11. The decoding method in claim 10 , the decoding method is applied in a receiver conforming to a 10-gigabit Ethernet specification.
12. The decoding method in claim 10 , wherein cyclically shifting in the steps are performed by barrel shifting.
13. The decoding method of claim 10 , wherein the parity check matrix comprises γ×ρ sub-matrices, the first (ρ−1) sub-matrices in a first block row of the parity check matrix are type-I sub-matrices, the γ sub-matrices in a last block column of the parity check matrix are type-II sub-matrices, and the other (γ−1)×(ρ−1) sub-matrices in the parity check matrix are type-III sub-matrices, the sub-matrix B(i 0 , j 0 ) is one of the type-I sub-matrices or the type-III sub-matrices.
14. The decoding method of claim 10 , further comprising:
generating a check-to-variable message R ij [k] associated with a j-th variable node for an i-th check node at a k-th iteration according to the following equation:
R ij [k]=S ij [k] ×max{(| R ij ′ [k]|−δ), 0},
wherein S ij [k] is a positive/negative sign of R ij [k], δ is an offset constant, and |R ij ′ [k]| is selected from {|Q j 0 i |, |Q j 1 i |, . . . , |Q j ω-1 i |};
wherein {|Q j 0 i |, |Q j 1 i |, . . . , |Q j ω-1 i |} are the ω smallest values among a plurality of variable-to-check messages associated to the i-th check node;
wherein i is an integer index ranging from 0 to (M−1), j is an integer index ranging from 0 to |I R [i]|, k is an iteration number, ω is an integer ranging from 3 to (|I R [i]|−1), M is the number of rows of the parity check matrix, and |I R [i]| is the i-th row weight of the parity check matrix.
15. The decoding method of claim 14 , wherein |Q j 0 i |, |Q j 1 i |, . . . , |Q j ω-1 i | are generated in the k-th iteration or a (k−1)-th iteration previous to the k-th iteration.
16. The decoding method of claim 14 , wherein the (k+1)-th iteration is aborted if the most significant bit of the absolute value of R ij [k] is equal to 1.