Method of and apparatus for generating spatially-coupled low-density parity-check code

Abstract

A method, apparatus, and non-transitory computer-readable recording medium for generating an algebraic Spatially-Coupled Low-Density Parity-Check (SC LDPC) code are provided. The method includes selecting an LDPC block code over a finite field GF(q) with a girth of at least 6; constructing a parity-check matrix H from the selected LDPC block code; replicating H a user-definable number of times to form a two-dimensional array H.sub.rep; constructing a masking matrix W with a user-definable spatially-coupled pattern; and masking a sub-matrix of H.sub.rep using W to obtain a spatially-coupled parity-check matrix H.sub.SC, wherein a null space of H.sub.SC is the algebraic SC LDPC code.

Claims

1. A method of a mobile system that supports hybrid automatic repeat request (HARQ) transmission configured to construct a parity check matrix H.sub.SC of an algebraic Spatially-Coupled Low-Density Parity-Check (SC LDPC) code, comprising: constructing, by a parity-check matrix generator, a non-diagonal LDPC block code parity check matrix H with girth at least 6 by arranging preselected smaller matrices over a finite field GF(q), where q is an integer; replicating, by an array generator connected to an output of the parity check matrix generator, H a predetermined number of times to form a two-dimensional semi-infinite array H.sub.rep; constructing, by a mask matrix generator connected to an output of the array generator, a band-diagonal masking matrix W with a predetermined spatially-coupled pattern based on selecting a step size c of a matrix of L matrices to be spatially coupled and one or more of a length a and a width b of the matrix of the L matrices, wherein the masking matrix W has a different rate than the LDPC block code, and wherein a, b, c, and L are integers; masking, by a masker and SC LDPC code generator connected to an output of the mask matrix generator, a sub-matrix of H.sub.rep using W to obtain the spatially-coupled parity-check matrix H.sub.SC; generating a signal based on the spatially-coupled parity-check matrix H.sub.SC; and transmitting the signal.

2. The method of claim 1, wherein H is an MN matrix, where M and N are integers.

3. The method of claim 1, wherein H.sub.rep is an ST matrix, and the sub-matrix of H.sub.rep is H.sub.rep(S.sub.0,S,T.sub.0,T), wherein H.sub.rep(S.sub.0,S,T.sub.0,T) is obtained by taking an intersection of S consecutive rows of H.sub.rep, starting from row S.sub.0, and T consecutive columns, starting from column T.sub.0, where S.sub.0, S, T.sub.0, and T are integers.

4. The method of claim 1, wherein H.sub.SC is an entry-wise product of H.sub.rep(S.sub.0,S,T.sub.0,T) and W, where S.sub.0, S, T.sub.0, and T are integers.

5. The method of claim 1, further comprising: generating a signal in accordance with the SC LDPC code, where the signal includes a Hybrid Automatic Repeat reQuest (HARQ) signal, and transmitting the generated signal, by one of wireless, wired, and fiber-optic transmission.

6. A method of a mobile system that supports hybrid automatic repeat request (HARQ) transmission configured to generate an algebraic, binary Spatially-Coupled Quasi-Cyclic Low-Density Parity-Check (SC QC LDPC) code, comprising: constructing, by a parity-check matrix generator, an MN base matrix B over a finite field GF(q), wherein every 22 sub-matrix of B contains at least one zero or is non-singular, where M, N, and q are integers; replicating, by an array generator connected to an output of the parity check matrix generator, a (q1)-fold dispersion to B to obtain an MN semi-infinite array H.sub.QC of (q1)(q1) Circulant Permutation Matrices (CPMs) or Zero Matrices (ZMs) or a combination thereof, wherein a null space of H.sub.QC is a QC LDPC block code whose Tanner graph has a girth of at least 6; constructing, by a mask matrix generator connected to an output of the array generator, a binary band diagonal matrix W.sub.QC that is an SC array of (q1)(q1) all one matrices or ZM matrices or a combination thereof that satisfies predetermined properties for girth and rate based on selecting a step size c of a matrix of L matrices to be spatially coupled and one or more of a length a and a width b of the matrix of the L matrices, wherein the binary matrix W.sub.QC has a different rate than the QC LDPC block code, and wherein a, b, c, and L are integers; masking, by a masker and SC LDPC code generator connected to an output of the mask matrix generator, H.sub.QC using W.sub.QC to obtain a non-diagonal spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC; generating a signal based on the spatially-coupled parity-check matrix H.sub.SC; and transmitting the signal.

7. The method of claim 6, further comprising: generating a signal in accordance with the SC QC LDPC code, where the signal includes a Hybrid Automatic Repeat reQuest (HARQ) signal; and transmitting the generated signal, by one of wireless, wired, and fiber-optic transmission.

8. A method of a mobile system that supports hybrid automatic repeat request (HARQ) transmission configured to generate an algebraic, binary Spatially-Coupled Quasi-Cyclic Low-Density Parity-Check (SC QC LDPC) code, comprising: constructing, by an LDPC block code selector, an LDPC block code over a finite field GF(q), where q is an integer; replicating, by a parity-check matrix generator connected to an output of the LDPC block code selector, a base matrix B from the selected LDPC block code, replicating B to form a two-dimensional semi-infinite array B.sub.rep; constructing, by a mask matrix generator connected to an output of the array generator, a band-diagonal masking matrix W.sub.base with a predetermined spatially-coupled pattern based on selecting a step size c of a matrix of L matrices to be spatially coupled and one or more of a length a and a width b of the matrix of the L matrices, wherein the masking matrix W.sub.base has a different rate than the LDPC block code, and wherein a, b, c, and L are integers; masking, by a masker and SC LDPC code generator connected to an output of the mask matrix generator, a sub-matrix of B.sub.rep using W.sub.base to obtain a spatially-coupled parity-check matrix B.sub.SC; applying a (q1)-fold dispersion to obtain a non-diagonal spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC; generating a signal based on the spatially-coupled parity-check matrix H.sub.SC; and transmitting the signal.

9. The method of claim 8, wherein B is an MN matrix, where M, and N are integers.

10. The method of claim 8, wherein B.sub.rep is an ST matrix, and the submatrix of B.sub.rep is B.sub.rep(S.sub.0,S,T.sub.0,T), wherein B.sub.rep(S.sub.0,S,T.sub.0,T) is obtained by taking an intersection of S consecutive rows of B.sub.rep, starting from row S.sub.0, and T consecutive columns, starting from column T.sub.0, where S.sub.0, S, T.sub.0, and T are integers.

11. The method of claim 8, wherein W.sub.base is a regular SC masking matrix with a predetermined spatially-coupled pattern.

12. The method of claim 11, wherein W.sub.base has L all one matrices of size ab with a step size c, wherein s=cL+(ac), t=bL, and an entry W.sub.base.sub.i,j of W.sub.base is a 1 if kci<kc+a and kbj<(k+1)b for 0k<L, and 0, otherwise, wherein (bc)/b is a rate, and (ac)/bL is a rate loss due to edge effect, and wherein bL(q1) is a length of the constructed SC QC LDPC code, where L, a, b, c, s, t, k, and l are integers.

13. The method of claim 8, wherein W.sub.base is based on unwrapping a protograph of an irregular LDPC code, wherein the protograph is decomposed into n matrices, wherein n is an integer greater than or equal to a largest number in the protograph matrix, the decomposed matrices sum to the protograph matrix, and unwrapping the decomposed matrices yields W.sub.base so that masking a sub-matrix of B.sub.rep using W.sub.base yields an irregular SC QC LDPC code.

14. The method of claim 13, wherein constructing W.sub.base comprises constructing a masking matrix W.sub.base* based on unwrapping a protograph of an irregular LDPC code, wherein the protograph is decomposed into n matrices, wherein na largest number in the protograph matrix, the decomposed matrices sum to the protograph matrix, and unwrapping the decomposed matrices yields W.sub.base*; and constructing the masking matrix W.sub.base by replacing each 1-entry in W.sub.base* with an NN permutation matrix and designating the result W.sub.base, where N is an integer.

15. The method of claim 14, wherein the NN permutation matrix is chosen randomly.

16. The method of claim 14, further comprising puncturing the irregular SC QC LDPC code with a puncturing pattern to generate additional irregular SC QC LDPC codes with different rates.

17. The method of claim 16, wherein the puncture pattern has repetitive structure and comprises (0,X,X,0,0,X,X,0), (0,X,X,0,X,X,X,0), and (0,X,X,0,X,X,X,0,0,X,X,X,X,X,X,0), wherein X denotes a punctured variable node in a protograph.

18. The method of claim 8, wherein B.sub.SC is an entry-wise product of B.sub.rep(S.sub.0,S,T.sub.0,T) and W.sub.base, where S.sub.0, S, T.sub.0, and T are integers.

19. The method of claim 8, further comprising generating a signal in accordance with the SC QC LDPC code, where the signal includes a Hybrid Automatic Repeat reQuest (HARD) signal, and transmitting the generated signal, by one of wireless, wired, and fiber-optic transmission.

20. A method of a mobile system that supports hybrid automatic repeat request (HARD) transmission configured to generate an algebraic, non-binary Spatially-Coupled Quasi-Cyclic Low-Density Parity-Check (SC QC LDPC) code, comprising: constructing, by an LDPC block code selector, an LDPC block code over a finite field GF(q), where q is an integer; constructing, by a matrix generator connected to an output of the LDPC block code selector, a base matrix B from the selected LDPC block code, replicating, by an array generator connected to an output of the parity check matrix generator, B to form a two-dimensional semi-infinite array B.sub.rep; constructing, by a mask matrix generator connected to an output of the array generator, a band-diagonal masking matrix W.sub.base with a predetermined spatially-coupled pattern based on selecting a step size c of a matrix of L matrices to be spatially coupled and one or more of a length a and a width b of the matrix of the L matrices, wherein the masking matrix W.sub.base has a different rate than the LDPC block code, and wherein a, b, c, and L are integers; masking, by a masker and SC LDPC code generator connected to an output of the mask matrix generator, a sub-matrix of B.sub.rep using W.sub.base to obtain a spatially-coupled parity-check matrix B.sub.SC; applying a (q1)-fold dispersion to obtain a non-diagonal spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC; replacing entries of the binary SC QC LDPC to obtain the non-binary SC QC LDPC code; generating a signal based on the spatially-coupled parity-check matrix H.sub.SC; and transmitting the signal.

21. The method of claim 20, wherein B is an MN matrix, where M and N are integers.

22. The method of claim 20, wherein B.sub.rep is an ST matrix, and the submatrix of B.sub.rep is B.sub.rep(S.sub.0,S,T.sub.0,T), wherein B.sub.rep(S.sub.0,S,T.sub.0,T) is obtained by taking an intersection of S consecutive rows of B.sub.rep starting from row S.sub.0 and T consecutive columns starting from column T.sub.0, where S.sub.0, S, T.sub.0, and T are integers.

23. The method of claim 20, wherein B.sub.SC is an entry-wise product of B.sub.rep(S.sub.0,S,T.sub.0,T) and W.sub.base, where S.sub.0, S, T.sub.0, and T are integers.

24. The method of claim 20, wherein replacing entries of the binary SC QC LDPC to obtain the non-binary SC QC LDPC code comprises multiplying each i.sup.th set of q1 columns in H.sub.SC,QC by .sup.i, wherein is a primitive element in the finite field GF(q), where q=2.sup.P, where S.sub.0, S, T.sub.0, and T are integers.

25. The method of claim 20, wherein W.sub.base is based on unwrapping a protograph of an irregular LDPC code, wherein the protograph matrix is decomposed into n matrices, wherein n is an integer greater than or equal to a largest number in the protograph matrix, the decomposed matrices sum to the protograph matrix so that masking a sub-matrix of B.sub.rep using W.sub.base yields an irregular SC QC LDPC code.

26. The method of claim 25, further comprising assigning finite field elements to H.sub.SC,QC, for each column of Circulant Permutation Matrices (CPMs) or Zero Matrices (ZMs) in H.sub.SC,QC, by replacing each 1-component in the column with a non-zero element selected from GF(2.sup.P), where P is an integer.

27. The method of claim 26, wherein the non-zero element selected from GF(2.sup.P) is a non-zero element selected randomly from GF(2.sup.P).

28. The method of claim 20, further comprising: generating a signal in accordance with the SC QC LDPC code, where the signal includes a Hybrid Automatic Repeat reQuest (HARD) signal, and transmitting the generated signal, by one of wireless, wired, and fiber-optic transmission.

29. A mobile system that supports hybrid automatic repeat request (HARD) transmission configured to generate an algebraic, Spatially-Coupled Low-Density Parity Check (SC LDPC) code and transmitting a signal generated therefrom, comprising: an LDPC block code selector; a parity-check matrix generator connected to an output of the LDPC block code selector and configured to generate a non-diagonal parity-check matrix; an array generator connected to an output of the parity check matrix generator; a mask matrix generator connected to an output of the array generator configured to select a step size c of a matrix of L matrices to be spatially coupled and one or more of a length a and a width b of the matrix of the L matrices, wherein a masking matrix W has a different rate than an LDPC block code, and wherein a, b, c, and L are integers; a masker and SC LDPC code generator connected to an output of the mask matrix generator; and a signal generator/transmitter connected to the masker and SC LDPC code generator and configured to generate a signal based on an SC LDPC code generated by the SC LDCP code generator and transmit the signal.

30. A non-transitory computer-readable recording medium including a program for a mobile system that supports hybrid automatic repeat request (HARQ) transmission configured to construct a parity check matrix H.sub.SC of an algebraic, binary, Spatially-Coupled Low-Density Parity Check (SC LDPC) code, the program, when executed by a computer, causes the computer to perform a method, the method comprising: constructing, by a parity-check matrix generator, a non-diagonal LDPC block code parity check matrix H with girth at least 6 by arranging preselected smaller matrices over a finite field GF(q), where q is an integer; replicating, by an array generator connected to an output of the parity check matrix generator, H a predetermined number of times to form a two-dimensional array H.sub.rep; constructing, by a mask matrix generator connected to an output of the array generator, a band-diagonal masking matrix W with a predetermined spatially-coupled pattern based on selecting a step size c of a matrix of L matrices to be spatially coupled and one or more of a length a and a width b of the matrix of the L matrices, wherein the masking matrix W has a different rate than the LDPC block code, and wherein a, b, c, and L are integers; masking, by a masker and SC LDPC code generator connected to an output of the mask matrix generator, a sub-matrix of H.sub.rep using W to obtain the spatially-coupled parity-check matrix H.sub.SC; generating a signal based on the spatially-coupled parity-check matrix H.sub.SC; and transmitting the signal.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The above and other aspects, features, and advantages of the present invention will be more apparent from the following detailed description, taken in conjunction with the accompanying drawings, in which:

(2) FIG. 1 is an illustration of a Tanner graph for an SC LDPC;

(3) FIG. 2 is an illustration of a (3,6,5) Tanner graph for an SC LDPC;

(4) FIG. 3 is an illustration of an SC matrix;

(5) FIG. 4 is an illustration of a quasi-cyclic parity-check matrix;

(6) FIG. 5A is an illustration of splitting a matrix;

(7) FIG. 5B is an illustration of unwrapping the split matrix of FIG. 5A;

(8) FIG. 6 is a flowchart for generating a SC LDPC code according to the present invention;

(9) FIG. 7 is a flowchart for generating a binary SC QC LDPC code according to the present invention;

(10) FIG. 8 is a flowchart for generating a binary SC QC LDPC code according to the present invention;

(11) FIG. 9 is a flowchart for generating a regular, binary SC QC LDPC code according to the present invention;

(12) FIG. 10 is an illustration of a parity-check matrix according to FIG. 9;

(13) FIG. 11 is a flowchart for generating an irregular, binary SC QC LDPC code according to the present invention;

(14) FIG. 12 is an illustration of a parity matrix according to FIG. 11;

(15) FIG. 13 is a flowchart for generating an irregular, binary SC QC LDPC code using two stage lifting according to the present invention;

(16) FIG. 14 is an illustration of puncturing patterns;

(17) FIG. 15 is a flowchart for generating a regular, non-binary SC QC LDPC code according to the present invention;

(18) FIG. 16 is a flowchart for generating an irregular, non-binary SC QC LDPC code according to the present invention; and

(19) FIG. 17 is a schematic block diagram of an apparatus of the present invention.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE PRESENT INVENTION

(20) Hereinafter, embodiments of the present invention are described in detail with reference to the accompanying drawings. In the following description, specific details such as detailed configurations and components are merely provided to assist the overall understanding of the embodiments of the present invention. Therefore, it should be apparent to those skilled in the art that various changes and modifications of the embodiments described herein may be made without departing from the scope and spirit of the present invention. In addition, descriptions of well-known functions and constructions are omitted for clarity and conciseness. The terms described below are terms defined in consideration of the functions in the present invention, and may be different according to users, intentions of the users, or customs. Therefore, the definitions of the terms should be determined based on the contents throughout the specification.

(21) The present invention may have various modifications and various embodiments, among which embodiments will now be described in detail with reference to the accompanying drawings. However, it should be understood that the present invention is not limited to the embodiments, but the present invention includes all modifications, equivalents, and alternatives within the spirit and the scope of the present invention.

(22) Although the terms including an ordinal number such as first, second, etc. may be used for describing various elements, the structural elements are not restricted by the terms. The terms are only used to distinguish one element from another element. For example, without departing from the scope of the present invention, a first structural element may be referred to as a second structural element. Similarly, the second structural element may also be referred to as the first structural element. As used herein, the term and/or includes any and all combinations of one or more associated items.

(23) The terms used herein are merely used to describe specific embodiments and are not intended to limit the present invention. Singular forms are intended to include plural forms unless the context clearly indicates otherwise. In the description, it should be understood that the terms include or have indicate existence of a feature, a number, a step, an operation, a structural element, parts, or a combination thereof, and do not exclude the existence or probability of addition of one or more other features, numerals, steps, operations, structural elements, parts, or combinations thereof.

(24) Unless defined differently, all terms used herein, which include technical terminologies or scientific terminologies, have the same meaning as that understood by a person skilled in the art to which the present invention belongs. Such terms as those defined in a generally used dictionary are to be interpreted to have meanings equal to the contextual meanings in the relevant field of art, and are not to be interpreted to have ideal or excessively formal meanings unless clearly defined in the present specification.

(25) Although the following description of the embodiments of the present invention uses terms and names defined for LDPC, the present invention is not limited by these terms and names, and is identically applicable to other similar systems.

(26) The present invention is a method of and apparatus for generating Spatially-Coupled Low-Density Parity-Check (SC LDPC) codes that overcome the restrictions of prior art unwrapping techniques described above. The method and apparatus generate algebraic SC LDPC codes that are binary or non-binary, regular or irregular, and robust to puncturing, which enables the present invention to provide rate-compatible SC LDPC codes suitable for mobile systems that support Hybrid Automatic Repeat reQuest (HARD) transmissions. While the prior art constructs SC LDPC codes that satisfy a girth requirement from a given LDPC block (i.e., the Tanner graph of the parity-check matrix of the resulting code is a graph-cover of the Tanner graph of the parity-check matrix of the underlying LDPC block code), the present invention does not require the Tanner graph of the resulting SC LDPC parity-check matrix to be a graph cover of the parity-check matrix of the underlying LDPC block code.

(27) FIG. 6 is a flowchart for generating a SC LDPC code according to the present invention.

(28) Referring to FIG. 6, in step 601, an LDPC block code over a finite field GF(q) with a girth of at least six is selected. The rate of the selected LDPC is not required to be equal to the design rate of the desired SC LDPC code resulting from the present invention.

(29) In step 603, a parity-check matrix H whose Tanner graph has a girth of at least 6 is constructed from the selected LDPC block code. H may be an MN matrix.

(30) In step 605, H is replicated a user-definable number of times to form a two-dimensional array H.sub.rep. A sub-matrix of H.sub.rep, denoted by H.sub.rep(S.sub.0,S,T.sub.0,T), is obtained by taking an intersection of S consecutive rows of H.sub.rep, starting from row S.sub.0, and T consecutive columns, starting from column T.sub.0. The present invention expands the parity-check matrix H.

(31) In step 607, a masking matrix W is constructed with a user-definable spatially-coupled pattern. The parameters selected to design the masking matrix, or band-diagonal masking matrix, determines the rate and the SC pattern of the constructed SC LDPC code. The rate of the SC LDPC code resulting from the present invention is determined by the designed masking matrix, or band-diagonal masking matrix, rather than the selected LDPC block code.

(32) In step 609, a sub-matrix of H.sub.rep is masked using W to obtain a spatially-coupled parity-check matrix H.sub.SC, wherein a null space of H.sub.SC is the SC LDPC code. H.sub.SC is an entry-wise product, or Hadamard product, of H.sub.rep(S.sub.0,S,T.sub.0,T) and W. The resulting SC LDPC code is used to generate a signal, where the signal includes a HARQ signal. The generated signal may be transmitted via wireless, wired, or fiber-optic transmission.

(33) The present invention can generate SC LDPC codes with different degree distributions from the corresponding selected LDPC block codes, and the Tanner graphs of the resulting SC LDPC codes are not required to be graph-covers of the Tanner graphs of the corresponding selected LDPC block codes as required by the prior art. In addition, the present invention can generate any spatial coupling pattern independent of the parameters of the base block code. Furthermore, generated SC LDPC codes are robust to puncturing, where the puncturing pattern may be regular for constructing rate-compatible codes for incremental redundancy Hybrid Automatic Repeat reQuest (HARQ), whereas prior art methods may not be robust to puncturing.

(34) In an embodiment of the present invention, if the masking matrix W=[w.sub.i,j].sub.0i<S,0j<T satisfies the following conditions: for any i.sub.1, i.sub.2, j.sub.1, j.sub.2 with 0i.sub.1<i.sub.2<S, 0j.sub.1<j.sub.2<T such that w.sub.i.sub.1.sub.,j.sub.1=w.sub.i.sub.2.sub.,j.sub.2=w.sub.i.sub.3.sub.,j.sub.3=w.sub.i.sub.4.sub.,j.sub.r=1, i.sub.1i.sub.2 is not divisible by M and j.sub.1j.sub.2 is not divisible by N, the girth of H.sub.SC is at least 6.

(35) In another embodiment of the present invention, if the masking matrix W=[w.sub.i,j].sub.0i<S,0j<T satisfies the following conditions: for any i.sub.1, i.sub.2, j with 0i.sub.1<i.sub.2<S,0j<T such that w.sub.i.sub.1.sub.,j=w.sub.i.sub.2.sub.,1=1, i.sub.1i.sub.2 is not divisible by M, and for any j.sub.1, j.sub.2, i with 0j.sub.1<j.sub.2<T, 0i<S such that w.sub.i,j.sub.1=w.sub.i,j.sub.2=1, j.sub.1j.sub.2 is not divisible by N, the girth of the Tanner graph of H.sub.SC is at least as large as the that of H.

(36) FIG. 7 is a flowchart for generating an algebraic, binary SC QC LDPC code according to the present invention.

(37) Referring to FIG. 7, in step 701, an MN base matrix B is selected over a finite field GF(q), wherein every 2 by 2 sub-matrix of B contains at least one zero or is non-singular.

(38) In step 703, a (q1)-fold dispersion is applied to B to obtain an MN array H.sub.QC of (q1)(q1) Circulant Permutation Matrices (CPMs) or Zero Matrices (ZMs) or a combination thereof, wherein a null space of H.sub.QC is a QC LDPC block code whose Tanner graph has a girth of at least 6.

(39) In step 705, a binary matrix W.sub.QC is constructed that is an SC array of (q1)(q1) all1 matrices or ZM matrices or a combination thereof that satisfies user-definable properties for girth and rate.

(40) In step 707, H.sub.QC is masked using W.sub.QC to obtain a spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC, wherein the null space of H.sub.SC,QC is the algebraic, binary SC QC LDPC code. The resulting SC QC LDPC code is used to generating a signal, where the signal includes a HARQ signal. The generated signal may be transmitted via wireless, wired, or fiber-optic transmission.

(41) FIG. 8 is a flowchart of an alternate embodiment for generating an algebraic, binary SC QC LDPC code according to the present invention.

(42) Referring to FIG. 8, in step 801, an LDPC block code is selected over a finite field GF(q).

(43) In step 803, a base matrix B is constructed from the selected LDPC block code, wherein every 22 sub-matrix of B contains at least one zero or is non-singular. B may be an MN matrix.

(44) In step 805, B is replicated to form a two-dimensional semi-infinite array B.sub.rep. B.sub.rep may be an ST matrix.

(45) In step 807, a masking matrix W.sub.base is constructed with a user-definable spatially-coupled pattern.

(46) In step 809, a sub-matrix of B.sub.rep is selected. The submatrix of B.sub.rep is B.sub.rep(S.sub.0,S,T.sub.0,T), which is obtained by taking an intersection of S consecutive rows of B.sub.rep starting from row S.sub.0 and T consecutive columns starting from column T.sub.0.

(47) In step 811, the sub-matrix of B.sub.rep is masked using W.sub.base to obtain a spatially-coupled base matrix B.sub.SC.

(48) In step 813, a (q1)-fold dispersion is applied to B.sub.SC to obtain a spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC, wherein the null space of H.sub.SC,QC is the algebraic, binary SC QC LDPC code.

(49) FIG. 9 is a flowchart for generating a regular, binary SC QC LDPC code according to the present invention.

(50) Referring to FIG. 9, in step 901, a base matrix B is constructed from an LDPC block code, wherein every 22 sub-matrix of B contains at least one zero or is non-singular. B may be an MN matrix, and the LDPC block code is over a finite field GF(q).

(51) In step 903, a masking matrix W.sub.base is constructed with a user-definable spatially-coupled pattern, where W.sub.base is i a regular SC masking matrix with a user-definable spatially-coupled pattern. W.sub.base may have L all1 matrices of size a by b with a step size c, wherein s=cL+(ac), t=bL, and an entry W.sub.base.sub.i,j and W.sub.base is a 1 if kci<kc+a and kbj<(k+1)b for 0k<L, and 0, otherwise, wherein (bc)/b is a rate, (ac)/bL is a rate loss due to edge effect, and bL(q1) is a the length of the constructed SC QC LDPC code.

(52) In step 905, B is replicated to form a two-dimensional semi-infinite array B.sub.rep. B.sub.rep may be an ST matrix.

(53) In step 907, a sub-matrix of B.sub.rep is selected. The submatrix of B.sub.rep is B.sub.rep(S.sub.0,S,T.sub.0,T), which is obtained by taking an intersection of S consecutive rows of B.sub.rep starting from row S.sub.0 and T consecutive columns starting from column T.sub.0.

(54) In step 909, the sub-matrix of B.sub.rep is masked using W.sub.base to obtain a spatially-coupled base matrix B.sub.SC.

(55) In step 911, a (q1)-fold dispersion is applied to B.sub.SC to obtain a spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC, wherein the null space of H.sub.SC,QC is the algebraic, binary SC QC LDPC code.

(56) In one embodiment, if the parameter a, b and c satisfies the following conditions:

(57) $am,.Math.\frac{a-1}{c}.Math.bn,$
the girth of the Tanner graph of H.sub.SC,QC is at least 6.

(58) In another embodiment, if the parameter a, b and c satisfies the following conditions:

(59) $am,.Math.\frac{a}{c}.Math.bn,$
the girth of the Tanner graph of H.sub.SC,QC is at least as large as that of H.sub.QC, which is the (q1)-fold dispersion of B.

(60) FIG. 10 is an illustration of a parity-check matrix according to FIG. 9, where m=3, c=1, n=5, b=2, and m/cn/b. The parity-check matrix of FIG. 10 cannot be achieved using prior art unwrapping methods, because of the restrictions of the prior art unwrapping methods described above.

(61) FIG. 11 is a flowchart for generating an irregular, binary SC QC LDPC code according to the present invention.

(62) Referring to FIG. 11, in step 1101, a base matrix B is constructed from an LDPC block code over a finite field GF(q), wherein every 22 sub-matrix of B contains at least one zero or is non-singular. B may be an MN matrix. The base matrix is not a regular LDPC code, but is an optimized protograph of an irregular LDPC code.

(63) In step 1103, a masking matrix W.sub.base is constructed based on unwrapping a protograph of an irregular LDPC code, wherein the protograph is decomposed into n matrices, wherein n is greater than or equal to the largest number in the protograph, and the decomposed matrices sum to the protograph. If the protograph has multiple edges then it is decomposed so that its component matrices have either ones or zeros, (i.e., no multiple edges). To preserve the degree distribution, the unwrapping technique is used to construct the masking matrix. Equivalently, a staircase masking approach is applied to construct the masking matrix with parameters a, b, c, L from a semi-indefinite matrix, except the elements of the masking matrix are either the component matrices or a zero matrix of the same size, rather than being a simple 1 or 0.

(64) In step 1105, B is replicated to form a two-dimensional semi-infinite array B.sub.rep. B.sub.rep may be an ST matrix.

(65) In step 1107, a sub-matrix of B.sub.rep is selected. The submatrix of B.sub.rep is B.sub.rep(S.sub.0,S,T.sub.0,T), and is obtained by taking an intersection of S consecutive rows of B.sub.rep, starting from row S.sub.0, and T consecutive columns, starting from column T.sub.0.

(66) In step 1109, the sub-matrix of B.sub.rep is masked using W.sub.base to obtain a spatially-coupled base matrix B.sub.SC for an irregular LDPC code.

(67) In step 1111, a (q1)-fold dispersion is applied to B.sub.SC to obtain an ST spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC, wherein the null space of H.sub.SC,QC is the algebraic, irregular, binary SC QC LDPC code. The ST spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC contains (q1)(q1) Circulant Permutation Matrices (CPMs) and/or Zero Matrices (ZMs).

(68) FIG. 12 is an illustration of a parity-check matrix according to FIG. 11, where m=3, c=2, n=6, b=3, and m/cn/b. The parity-check matrix of FIG. 12 cannot be achieved using prior art unwrapping methods, because of the restrictions of the prior art unwrapping methods described above.

(69) FIG. 13 is a flowchart for generating an irregular, binary SC LDPC code according to the present invention, using two-stage lifting.

(70) Referring to FIG. 13, in step 1301, a base matrix B is constructed from an LDPC block code over a finite field GF(q), wherein every 22 sub-matrix of B contains at least one zero or is non-singular. B may be an MN matrix.

(71) In step 1303, a masking matrix W.sub.base* is constructed based on unwrapping the protograph of an irregular LDPC code, wherein the protograph is decomposed into n matrices, and n is greater than or equal to the largest number in the protograph, and the decomposed matrices sum to the protograph. If the protograph of the irregular LDPC code has multiple edges, corresponding to entries in the protograph matrix which are greater than 1, then it is unwrapped so that the masking matrix has either ones or zeros.

(72) In step 1305, a masking matrix W.sub.base is constructed by replacing each 1-entry in W.sub.base* with an NN permutation matrix and designating the result W.sub.base. The NN permutation matrix may be chosen randomly.

(73) In step 1307, B is replicated to form a two-dimensional semi-infinite array B.sub.rep. B.sub.rep may be an ST matrix.

(74) In step 1309, a sub-matrix of B.sub.rep is selected. The submatrix of B.sub.rep is B.sub.rep(S.sub.0,S,T.sub.0,T), which is obtained by taking an intersection of S consecutive rows of B.sub.rep, starting from row S.sub.0, and T consecutive columns, starting from column T.sub.0.

(75) In step 1311, the sub-matrix of B.sub.rep is masked using W.sub.base to obtain a spatially-coupled base matrix B.sub.SC. The B.sub.SC is an entry-wise product, or Hadamard product, of B.sub.rep(S.sub.0,S,T.sub.0,T) and W.sub.base.

(76) In step 1313, a (q1)-fold dispersion is applied to B.sub.SC to obtain an ST spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC, wherein the null space of H.sub.SC,QC is the algebraic, irregular, binary SC QC LDPC code, using two-stage lifting. The ST spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC contains (q1)(q1) Circulant Permutation Matrices (CPMs) and/or Zero Matrices (ZMs).

(77) FIG. 14 is an illustration of puncturing patterns.

(78) Referring to FIG. 14, the irregular, binary SC QC LDPC code of FIG. 13 may be punctured to obtain rate-compatible irregular, binary SC QC LDPC codes suitable for generating a signal in accordance with the irregular, binary SC LDPC code, where the signal includes a HARQ signal. The resulting signal may then be transmitted via wireless, wired, or fiber-optic transmission. A puncture pattern with repetitive structure includes (0,X,X,0,0,X,X,0), (0,X,X,0,X,X,X,0), and (0,X,X,0,X,X,X,0,0,X,X,X,X,X,X,0), wherein X denotes a punctured variable node in a protograph.

(79) FIG. 15 is a flowchart for generating a regular, non-binary SC QC LDPC code according to the present invention.

(80) Referring to FIG. 15, in step 1501, an LDPC block code is selected over a finite field GF(q).

(81) In step 1503, a base matrix B is constructed from the selected LDPC block code, wherein B may be an MN matrix over finite field GF(q) with quasi-cyclic structure.

(82) In step 1505, B is replicated to form a two-dimensional, semi-infinite array B.sub.rep. B.sub.rep, may be an ST matrix.

(83) In step 1507, a masking matrix W.sub.base is constructed with a user-definable spatially-coupled pattern.

(84) In step 1509, a sub-matrix of B.sub.rep is selected, where the submatrix of B.sub.rep is B.sub.rep(S.sub.0,S,T.sub.0,T), which is obtained by taking an intersection of S consecutive rows of B.sub.rep, starting from row S.sub.0, and T consecutive columns, starting from column T.sub.0.

(85) In step 1511, the sub-matrix of B.sub.rep is masked using W.sub.base to obtain a spatially-coupled parity-check matrix B.sub.SC, wherein B.sub.SC is an entry-wise product, or Hadamard product, of B.sub.rep(S.sub.0,S,T.sub.0,T) and W.sub.base.

(86) In step 1513, a (q1)-fold dispersion is applied to obtain a spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC, wherein the null space of H.sub.SC,QC is the algebraic, binary SC QC LDPC code. The ST spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC contains (q1)(q1) Circulant Permutation Matrices (CPMs) and/or Zero Matrices (ZMs).

(87) In step 1515, entries of the binary SC QC LDPC are replaced to obtain the non-binary SC QC LDPC code. The entries of the binary SC QC LDPC may be replaced by multiplying each i.sup.th set of q1 columns in H.sub.SC,QC by .sup.i, wherein is a primitive element in the finite field GF(2.sup.P).

(88) FIG. 16 is a flowchart for generating an irregular, non-binary SC QC LDPC code according to the present invention.

(89) Referring to FIG. 16, in step 1601, a base matrix B is constructed from a selected LDPC block code, wherein B may be an MN matrix over finite field GF(q) with quasi-cyclic structure.

(90) In step 1603, a masking matrix W.sub.base is constructed based on unwrapping a protograph of an irregular LDPC code, wherein the protograph is decomposed into n matrices, wherein n is greater than or equal to the largest number in the protograph, and the decomposed matrices sum to the protograph matrix.

(91) In step 1605, B is replicated to form a two-dimensional semi-infinite array B.sub.rep. B.sub.rep may be an ST matrix.

(92) In step 1607, a sub-matrix of B.sub.rep is selected, where the submatrix of B.sub.rep is B.sub.rep(S.sub.0,S,T.sub.0,T) obtained by taking an intersection of S consecutive rows of B.sub.rep, starting from row S.sub.0, and T consecutive columns, starting from column T.sub.0.

(93) In step 1609, the sub-matrix of B.sub.rep is masked using W.sub.base to obtain a spatially-coupled parity-check matrix B.sub.SC, wherein B.sub.SC is an entry-wise product, or Hadamard product, of B.sub.rep(S.sub.0,S,T.sub.0,T) and W.sub.base.

(94) In step 1611, a (q1)-fold dispersion is applied to B.sub.SC to obtain a spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC. The ST spatially-coupled quasi-cyclic parity-check matrix H.sub.SC,QC contains (q1)(q1) Circulant Permutation Matrices (CPMs) and/or Zero Matrices (ZMs).

(95) In step 1613, finite field elements is assigned to H.sub.SC,QC by, for each column of Circulant Permutation Matrices (CPMs) or Zero Matrices (ZMs) in H.sub.SC,QC, replacing each 1-component in the column with a non-zero element selected from GF(2.sup.P). The non-zero element selected from GF(2.sup.P) may be a non-zero element selected randomly from GF(2.sup.P).

(96) The irregular, non-binary SC QC LDPC code may be used to generate a signal, including a HARQ signal, and the signal may be transmitted via wireless, wired, or fiber-optic transmission.

(97) FIG. 17 is a schematic block diagram of an apparatus 1700 of the present invention for generating an algebraic SC LDPC code and transmitting a signal generated therefrom.

(98) Referring to FIG. 17, the apparatus 1700 includes an LDPC block code selector 1701, a parity-check matrix generator 1703, an array generator 1705, a mask matrix generator 1707, a masker and SC LDPC code generator 1709; and a signal generator/transmitter 1711. The apparatus 1700 may be configured to generate a binary SC LDPC code, a binary SC QC LDPC code, a regular SC QC LDPC code, an irregular SC QC LDPC code that is punctured for rate compatibility, a regular, non-binary SC QC LDPC code, and an irregular, non-binary SC QC LDPC code, as described above.

(99) The present invention may also be implemented as computer readable codes in a non-transitory computer readable recording medium. The non-transitory computer readable recording medium is a data storage device for storing data read by a computer system. For example, the non-transitory computer readable recording medium includes a Read-Only Memory (ROM), a Random Access Memory (RAM), a Compact Disc (CD) ROM, a magnetic tape, a floppy disk, an optical data storage device, and a carrier wave (i.e., a transmission of data through the Internet). The non-transitory computer readable recording medium may be distributed through computer systems connected to a network, and thus, the computer readable code may be stored and executed in a distributed manner. Further, functional programs, codes, and code segments for establishing the present invention may easily be interpreted by programmers skilled in the art to which the present invention is applied.

(100) Accordingly, the present invention includes a program including a code for implementing the apparatus and methods described in the appended claims of the specification and a non-transitory machine (a computer or the like)-readable storage medium for storing the program. Further, the program may be electronically transferred by a predetermined medium such as a communication signal transferred through a wired or wireless connection, and the present invention appropriately includes equivalents of the program.

(101) A portable terminal according to the embodiments of the present invention may receive the program from a program providing device that is wiredly or wirelessly connected with the portable terminal, and may store the program. The program providing apparatus may include a program including instructions through which a graphic processing apparatus implements a preset content protection method, a memory for storing information or the like required for the content protecting method, a communication unit for performing wired or wireless communication with the graphic processing apparatus, and a controller for transmitting the corresponding program to a transceiver according to a request of the graphic processing apparatus or automatically.

(102) Although embodiments of the present invention have been described in the detailed description of the present invention, the present invention may be modified in various forms without departing from the scope of the present invention. Thus the scope of the present invention shall not be determined merely based on the described embodiments, but rather determined based on the accompanying claims and the equivalents thereto.