Generalized low-density parity check codes (GLDPC)

Abstract

Provided is a system and method for determining a generalized Low-Density Parity-Check (LDPC) code for forward error correction channel coding that has a repeat-accumulate code structure.

Claims

1. A system for determining a generalized Low-Density Parity-Check (LDPC) code for forward error correction channel coding, the system including a processor being configured to: determine 2k parity check matrix columns of size k, wherein k is an integer; label components of a first parity check matrix with n columns and k rows, wherein n is an integer, and wherein the first parity check matrix includes the 2k parity check matrix columns of size k; and select Cordaro-Wagner component code check matrices, wherein each of the selected Cordaro-Wagner component code check matrices has two rows which replace one row of the first parity check matrix to derive a second parity check matrix defining the generalized LDPC code; wherein the determination of the 2k parity check matrix columns of size k and the selection of the Cordaro-Wagner component code check matrices are constrained to 2k parity check matrix columns of size k and Cordaro-Wagner component code check matrices which allow that rows and columns of a parity part consisting of 2k columns of the second parity check matrix which correspond to the 2k parity check matrix columns of size k, can be brought in an order in which the ordered rows and columns form a parity part which has a repeat-accumulate code structure.

2. The system of claim 1, the processor being configured to: split/duplicate each entry of the 2k parity check matrix columns of size k into a vector of size two, wherein each vector of size two having a non-zero weight requires a corresponding non-zero entry, to determine the 2k columns of the second parity check matrix which correspond to the 2k parity check matrix columns of size k, and can be brought in an order in which the ordered rows and columns form a parity part which has a repeat-accumulate code structure.

3. The system of claim 2, the processor being configured to: iteratively label components of n−k unlabeled columns of the first parity check matrix based on a performance measure.

4. The system of claim 1, the processor being configured to: compare multiple alternatives for labelling different components of the n−k columns with non-zero entries; and select one alternative achieving a highest performance score.

5. The system of claim 1, wherein a column of the Cordaro-Wagner component code check matrix has a zero weight if a corresponding component of the row of the first parity check matrix is zero.

6. The system of claim 1, wherein each of the 2k parity check matrix columns of size k has weight one or two.

7. The system of claim 6, wherein k−1 parity check matrix columns of size k of the 2k parity check matrix columns of size k have a weight of one and the remaining parity check matrix columns of size k of the 2k parity check matrix columns of size k have weight two.

8. The system of claim 7, wherein the 2k parity check matrix columns of size k are linearly independent.

9. The system of claim 1, wherein the selection of the Cordaro-Wagner component code check matrices includes replacing each non-zero entry in a row of the first parity check matrix with a non-zero column of a Cordaro-Wagner component code check matrix, wherein: a row having exactly three non-zero entries in components which correspond to the 2k parity check matrix columns, is replaced with a Cordaro-Wagner component code check matrix having columns which correspond to the 2k parity check matrix columns, wherein said columns are linearly independent; and a row having exactly four non-zero entries in components which correspond to the 2k parity check matrix columns is replaced with a Cordaro-Wagner component code check matrix having columns which correspond to the 2k parity check matrix columns, wherein three of said columns are linearly independent.

10. A method of determining a generalized Low-Density Parity-Check (LDPC) code for forward error correction channel coding, the method comprising: determining 2k parity check matrix columns of size k, wherein k is an integer; labeling components of a first parity check matrix with n columns and k rows, wherein n is an integer, and wherein the first parity check matrix includes the 2k parity check matrix columns of size k; and selecting Cordaro-Wagner component code check matrices, wherein each of the selected Cordaro-Wagner component code check matrices has two rows which replace a row of the first parity check matrix to derive a second parity check matrix defining the generalized LDPC code; wherein the determining of the 2k parity check matrix columns of size k and the selecting of the Cordaro-Wagner component code check matrices are constrained to 2k parity check matrix columns of size k and Cordaro-Wagner component code check matrices which allow that rows and columns of a parity part consisting of 2k columns of the second parity check matrix which correspond to the 2k parity check matrix columns of size k can be brought in an order in which the ordered rows and columns form a parity part which has a repeat-accumulate code structure.

11. The method of claim 10, the method comprising: splitting/duplicating each entry of the 2k parity check matrix columns of size k into a vector of size two, wherein each vector of size two having a non-zero weight requires a corresponding non-zero entry, to determine the 2k columns of the second parity check matrix which correspond to the 2k parity check matrix columns of size k, and can be brought in an order in which the ordered rows and columns form a parity part which has a repeat-accumulate code structure.

12. The method of claim 11, comprising: iteratively labeling components of n−k unlabeled columns of the first parity check matrix based on a performance measure.

13. The method of claim 10, comprising: comparing multiple alternatives for labelling different components of the n−k columns with non-zero entries; and selecting one alternative achieving a highest performance score.

14. The method of claim 10, wherein a column of the Cordaro-Wagner component code check matrix has zero weight if at least one of the following is satisfied: a) a corresponding component of the row of the first parity check matrix is zero; b) each of the 2k parity check matrix columns of size k has weight one or two; and c) the 2k parity check matrix columns of size k are linearly independent.

15. The method of claim 10, wherein selecting the Cordaro-Wagner component code check matrices includes replacing each non-zero entry in a row of the first parity check matrix with a non-zero column of a Cordaro-Wagner component code check matrix, wherein: a row having exactly three non-zero entries in components which correspond to the 2k parity check matrix columns, is replaced with a Cordaro-Wagner component code check matrix having columns which correspond to the 2k parity check matrix columns, wherein said columns are linearly independent; and a row having exactly four non-zero entries in components which correspond to the 2k parity check matrix columns is replaced with a Cordaro-Wagner component code check matrix having columns which correspond to the 2k parity check matrix columns, wherein three of said columns are linearly independent.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram illustrating a generic digital communications system in which the elements of the present disclosure may be implemented.

(2) FIG. 2 is a flow-chart of a procedure for determining the GLDPC code.

(3) FIG. 3 illustrates an exemplary structure of the parity part of the first parity check matrix.

(4) FIG. 4 illustrates an exemplary structure of the parity part of the second parity check matrix.

(5) FIG. 5 shows additional steps of the procedure illustrated in FIG. 2.

DETAILED DESCRIPTION

(6) The following provides a non-limiting example of a procedure for determining a GLDPC code for forward error correction. The procedure as well as procedures involving the usage of the determined GLDPC code may be implemented by hardware, software, or a combination of hardware and software. For example, the procedure of determining the GLDPC code may be automatically carried-out by a computer comprising a processor which carries out machine-readable instructions persistently stored on a machine-readable medium. Moreover, procedures involving the usage of the determined GLDP code, such as encoding/decoding an information sequence IS.sub.1 may be automatically carried-out by the system 10 which may have been designed or configured in accordance with the determined GLDPC code.

(7) As shown in FIG. 2, the procedure may involve a step 22 of determining 2k parity check matrix columns of size k as shown in FIG. 3 which illustrates an exemplary structure of a parity part 28 of the first parity check matrix 30 in array form, wherein black squares indicate entries of non-zero weight (i.e., ‘1s’) and white squares indicate entries of zero weight (i.e., ‘0s’). The parity part 28 comprises the determined ten columns of length five. In the exemplary structure, the columns of the parity part are linearly independent and comprise either one or two entries of non-zero weight. In particular, four columns have one entry of non-zero weight and the remaining columns have two entries of non-zero weight.

(8) At step 24, the procedure may be continued with labelling components of the first parity check matrix 30 with n columns and k rows, wherein the first parity check matrix 30 includes the 2k parity check matrix columns of size k. As shown in FIG. 3, labelling the components may involve labelling the columns of the information part 32 of the first parity check matrix 30. For example, as indicated in step 34 in FIG. 5, the information part 32 may be labelled by performing a progressive edge growth algorithm.

(9) At step 26, Cordaro-Wagner component code check matrices may be selected, wherein each of the selected Cordaro-Wagner component code check matrices has two rows which replace a row of the first parity check matrix to derive a second parity check matrix defining the generalized LDPC code. For example, as indicated in step 36 of FIG. 5, each entry of the parity part 28 may be split/duplicated into a vector of size two, wherein entries of zero weight are split/duplicated into a zero vector whereas entries of non-zero weight are split/duplicated into a vector having one or two non-zero entries.

(10) As shown in in FIG. 4, the replacing may be made under the provision that the rows and columns of the parity part 28′ consisting of 2k columns of the second parity check matrix can be brought in an order in which the ordered rows and columns form a parity part which has a repeat-accumulate code structure. For example, the parity part H.sub.2 of the LDPC parity-check matrix:

(11) $H_2^{\mathrm{EIRA}}=\left[\begin{array}{cccccccccc}1& 0& 0& 0& 0& 0& 0& 1& 0& 1\\ 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 1& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 1& 1& 0\end{array}\right]$
may be chosen such that, after replacing the rows of the first parity check matrix with rows of a Cordaro-Wagner component code, an extended irregular repeat-accumulate (EIRA) code can be obtained.

(12) Replacing may start at the first row of H.sub.2.sup.EIRA which has the following entries: 1 0 0 0 0 0 0 1 0 1

(13) By replacing the entries with vectors of size two using

(14) $\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 1\end{array}\right],$
two rows of a generalized EIRA (GEIRA) code may be maintained, wherein the rows have the entries

(15) TABLE-US-00001 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1

(16) The second row of the parity part H.sub.2.sup.EIRA which has 1 1 1 0 0 0 0 0 0 0
as entries may be replaced using

(17) $\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 1\end{array}\right]$
with another two rows of the GEIRA code having

(18) TABLE-US-00002 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
as entries. The third row of the parity part H.sub.2.sup.EIRA which has 0 1 0 1 1 0 0 0 0 1
as entries may be replaced using

(19) $\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 1\end{array}\right]$
with another two rows of the GEIRA code having

(20) TABLE-US-00003 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0
as entries. The fourth row of the parity part H.sub.2.sup.EIRA which has 0 0 0 1 0 1 1 0 0 0
as entries may be replaced using

(21) $\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 1\end{array}\right]$
with another two rows of the GEIRA code having

(22) TABLE-US-00004 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0
as entries. The fifth row of the parity part H.sub.2.sup.EIRA which has 0 0 0 0 0 1 0 1 1 0
as entries may be replaced using

(23) $\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 1\end{array}\right]$
with another two rows of the GEIRA code having

(24) TABLE-US-00005 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0
as entries. The parity part of the second parity check matrix may thus be

(25) $H_2^{\mathrm{GEIRA}}=\left[\begin{array}{cccccccccc}1& 0& 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 1\\ 1& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right]$

(26) After reordering the columns in accordance with

(27) $P_{\mathrm{column}}=\left(\begin{array}{cccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 1& 3& 2& 5& 4& 7& 6& 9& 8& 10\end{array}\right)$
and reordering the rows in accordance with

(28) $P_{\mathrm{row}}=\left(\begin{array}{cccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 1& 3& 4& 5& 6& 7& 8& 9& 10& 2\end{array}\right)$
an EIRA structure may be obtained:

(29) 0$H_2^{\mathrm{EIRA}}=\begin{array}{c}13254769810\\ \begin{array}{c}1\\ 3\\ 4\\ 5\\ 6\\ 7\\ 8\\ 9\\ 10\\ 2\end{array}\left[\begin{array}{cccccccccc}1& 0& 0& 0& 0& 0& 0& 0& 0& 1\\ 1& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 1\end{array}\right]\end{array}$

(30) In this regard, it is noted that although the procedure is described in relation to a specific example of size 5×10, codes of other sizes may be generated analogously:

(31) $H_2^{\mathrm{GEIRA}}=\left[\begin{array}{cccccccccccc}1& 0& 0& 0& 0& 0& 0& \mathrm{.Math.}& 0& 1& 0& 1\\ 1& 1& 1& 0& 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 1& \mathrm{.Math.}& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& \mathrm{.Math.}& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& \mathrm{.Math.}& 0& 1& 0& 1& 1& 0& 0& 0\\ 0& 0& \mathrm{.Math.}& 0& 0& 0& 0& 1& 0& 1& 1& 0\end{array}\right]$

(32) Heretofore: a. non-zero entries in a row of the parity part with three non-zero entries may be replaced by

(33) $\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right],\mathrm{and}\left[\begin{array}{c}1\\ 1\end{array}\right],$
respectively. b. non-zero entries in a row of the parity part with four non-zero entries may be replaced by

(34) $\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 1\end{array}\right],\mathrm{and}\left[\begin{array}{c}1\\ 0\end{array}\right],$
respectively. c. columns and rows may be reordered in accordance with

(35) $P_{\mathrm{column}}=\left(\begin{array}{ccccccccc}1& 2& 3& \mathrm{.Math.}& 2s& 2s+1& \mathrm{.Math.}& k& k\\ 1& 3& 2& \mathrm{.Math.}& 2s+1& 2s& \mathrm{.Math.}& a& k\end{array}\right),\mathrm{with}a=\{\begin{array}{c}k,k\mathrm{is}\mathrm{even}\\ k-1,k\mathrm{is}\mathrm{odd}\end{array},s=\stackrel{\_}{2K\mathrm{.Math.}.Math.\frac{k}{2}.Math.},\mathrm{and}{P}_{\mathrm{row}}=\left(\begin{array}{ccccccc}1& 2& 3& \mathrm{.Math.}& s& \mathrm{.Math.}& k\\ 1& 3& 4& \mathrm{.Math.}& s+1& \mathrm{.Math.}& 2\end{array}\right),\mathrm{with}s=\stackrel{\_}{2\mathrm{.Math.}k-1}$

(36) Once, the EIRA structure has been obtained, encoding may be performed as described in U.S. Pat. No. 7,627,801 B2 or in EP 1,816,750 A1.

(37) Moreover, decoding may be performed as described in EP 1,816,750 A1.