Method and apparatus for channel encoding/decoding in a communication or broadcasting system

Abstract

A channel encoding method in a communication or broadcasting system is provided. The channel encoding method includes reading a first sequence corresponding to a parity check matrix, converting the first sequence to a second sequence by applying a certain rule to a block size corresponding to a parity check matrix and the first sequence, and encoding information bits based on the second sequence. The block size has at least two different integer values.

Claims

1. A method for encoding in a communication or broadcasting system supporting a low density parity check (LDPC) code, the method comprising: identifying a size associated with information bits to encode; identifying a block size Z based on the size associated with the information bits; identifying, from among a plurality of sets of block sizes, a set of block sizes associated with the block size Z; identifying an exponent matrix including at least one integer value based on the identified set of block sizes; identifying a parity check matrix based on the block size Z and the exponent matrix; and encoding the information bits based on the parity check matrix, wherein the parity check matrix includes Z×Z zero matrices and Z×Z circular permutation matrices, wherein the Z×Z circular permutation matrices are identified based on the at least one integer value, wherein the parity check matrix is identified by using a modulo operation based on the block size Z, and wherein a first block size in the set of block sizes is multiple of a second block size in the set of block sizes.

2. The method of claim 1, further comprising: identifying a mother matrix consisting of 0 and 1; and identifying a predetermined number based on the mother matrix, wherein identifying the block size Z based on the size associated with the information bits comprises identifying the block size Z based on the predetermined number and the size associated with the information bits.

3. The method of claim 2, wherein a multiplication of the predetermined number and the block size Z is larger than or equal to the size associated with the information bits.

4. The method of claim 1, wherein the set of block sizes is associated with block sizes determined among {(A+i), 2(A+i), 2.sup.2(A+i) . . . , 2.sup.S(A+i)}, where i=0, 1, 2, . . . , A−1, and A and S are positive integers.

5. The method of claim 4, wherein A is 8 and S is 4.

6. The method of claim 1, wherein the LDPC code is determined based on one of parity check matrices of at least two different sizes.

7. The method of claim 1, wherein the parity check matrix is obtained based on a circular permutation matrix by applying a circularly shifting operation including one of the modulo operation or a flooring operation.

8. The method of claim 1, wherein the LDPC code is determined based on one of two or more mother matrices.

9. The method of claim 1, wherein at least one of the circular permutation matrices is a circularly shifted matrix of a Z×Z identity matrix.

10. An encoder in a communication or broadcasting system supporting a low density parity check (LDPC) code, the encoder comprising: a transceiver; a memory; and at least one processor configured to: identify a size associated with information bits to encode, identify a block size Z based on the size associated with the information bits, identify, from among a plurality of sets of block sizes, a set of block sizes associated with the block size Z, identify an exponent matrix including at least one integer value based on the identified set of block sizes, identify a parity check matrix based on the block size Z and the exponent matrix, and encode the information bits based on the parity check matrix, wherein the parity check matrix includes Z×Z zero matrices and Z×Z circular permutation matrices, and wherein the Z×Z circular permutation matrices are identified based on the at least one integer value, wherein the parity check matrix is identified by using a modulo operation based on the block size Z, and wherein a first block size in the set of block sizes is multiple of a second block size in the set of block sizes.

11. The encoder of claim 10, wherein the at least one processor is further configured to: identify a mother matrix consisting of 0 and 1, identify a predetermined number based on the mother matrix, and identify the block size Z based on the predetermined number and the size associated with the information bits.

12. The encoder of claim 11, wherein a multiplication of the predetermined number and the block size Z is larger than or equal to the size associated with the information bits.

13. The encoder of claim 10, wherein the set of block sizes is associated with block sizes determined among {(A+i), 2(A+i), 2.sup.2 (A+i), . . . , 2.sup.s(A+i)}, where i=0, 1, 2, . . . , A−1, and A and S are positive integers.

14. The encoder of claim 13, wherein A is 8 and S is 4.

15. The encoder of claim 10, wherein the LDPC code is determined based on one of parity check matrices of at least two different sizes.

16. The encoder of claim 10, wherein the parity check matrix is obtained based on a circular permutation matrix by applying a circularly shifting operation including one of the modulo operation or a flooring operation.

17. The encoder of claim 10, wherein the LDPC code is determined based on one of two or more mother matrices.

18. The encoder of claim 10, wherein at least one of the Z×Z circular permutation matrices is a circularly shifted matrix of a Z×Z identity matrix.

19. A method for decoding in a communication or broadcasting system supporting a low density parity check (LDPC) code, the method comprising: receiving a signal from a transmitter; and obtaining a bit sequence by decoding the signal, wherein the decoding of the signal is performed based on a parity check matrix, wherein the parity check matrix is based on a block size Z and an exponent matrix including at least one integer value, wherein the exponent matrix is based on a set of block sizes from among a plurality of sets of block sizes, wherein the set of block sizes is based on the block size Z, wherein the parity check matrix includes Z×Z zero matrices and Z×Z circular permutation matrices, wherein the Z×Z circular permutation matrices are identified based on the at least one integer value, wherein the parity check matrix is identified by using a modulo operation based on the block size Z, and wherein a first block size in the set of block sizes is multiple of a second block size in the set of block sizes.

20. The method of claim 19, wherein the block size Z is based on a predetermined number, and wherein the predetermined number is based on a mother matrix consisting of 0 and 1.

21. The method of claim 20, wherein a multiplication of the predetermined number and the block size Z is larger than or equal to a size associated with information bits.

22. The method of claim 19, wherein the set of block sizes is associated with block sizes determined among {(A+i), 2(A+i), 2.sup.2(A+i), . . . , 2.sup.s(A+i)}, where i=0, 1, 2, . . . , A−1, and A and S are positive integers.

23. The method of claim 22, wherein A is 8 and S is 4.

24. The method of claim 19, wherein the LDPC code is based on one of parity check matrices of at least two different sizes.

25. The method of claim 19, wherein the parity check matrix is based on a circular permutation matrix by applying a circularly shifting operation including one of the modulo operation or a flooring operation.

26. The method of claim 19, wherein the LDPC code is determined based on one of two or more mother matrices.

27. The method of claim 19, wherein at least one of the Z×Z circular permutation matrices is a circularly shifted matrix of a Z×Z identity matrix.

28. A decoder in a communication or broadcasting system supporting a low density parity check (LDPC) code, the decoder comprising: a transceiver; a memory; and at least one processor configured to: control the transceiver to receive a signal from a transmitter, and obtain a bit sequence by decoding the signal, wherein the decoding of the signal is performed based on a parity check matrix, wherein the parity check matrix is based on a block size Z and an exponent matrix including at least one integer value, wherein the exponent matrix is based on a set of block sizes from among a plurality of sets of block sizes, wherein the set of block sizes is based on the block size Z, wherein the parity check matrix includes Z×Z zero matrices, and Z×Z circular permutation matrices, and wherein the Z×Z circular permutation matrices are identified based on the at least one integer value, wherein the parity check matrix is identified by using a modulo operation based on the block size Z, and wherein a first block size in the set of block sizes is multiple of a second block size in the set of block sizes.

29. The decoder of claim 28, wherein the block size Z is based on a predetermined number, and wherein the predetermined number is based on a mother matrix consisting of 0 and 1.

30. The decoder of claim 29, wherein a multiplication of the predetermined number and the block size Z is larger than or equal to a size associated with information bits.

31. The decoder of claim 28, wherein the set of block sizes is associated with block sizes determined among {(A+i), 2(A+i), 2.sup.2(A+i), 2.sup.s(A+i)}, where i=0, 1, 2, . . . , A−1, and A and S are positive integers.

32. The decoder of 31, wherein A is 8 and S is 4.

33. The decoder of claim 28, wherein the LDPC code is based on one of parity check matrices of at least two different sizes.

34. The decoder of claim 28, wherein the parity check matrix is based on a circular permutation matrix by applying a circularly shifting operation including one of the modulo operation or a flooring operation.

35. The decoder of claim 28, wherein the LDPC code is determined based on one of two or more mother matrices.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

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

(2) FIG. 1 is a view illustrating a structure of a systematic low density parity check (LDPC) codeword according to the related art;

(3) FIG. 2 is a view illustrating a parity check matrix H.sub.1 of an LDPC code, with four rows and eight columns, and a Tanner graph representing the parity check matrix H.sub.1 according to the related art;

(4) FIG. 3 is a block diagram of a transmitter according to an embodiment of the present disclosure;

(5) FIG. 4 is a block diagram of a receiver according to an embodiment of the present disclosure;

(6) FIGS. 5A and 5B are message structure diagrams illustrating message passing operations at a check node and a variable node for LDPC decoding according to various embodiments of the present disclosure;

(7) FIG. 6 is a block diagram of an LDPC encoder according to an embodiment of the present disclosure;

(8) FIGS. 7 and 8 are views illustrating structures of transport blocks according to various embodiments of the present disclosure;

(9) FIGS. 9A and 9B are block diagrams of interleavers according to various embodiments of the present disclosure;

(10) FIG. 10 is a block diagram of an LDPC decoder according to an embodiment of the present disclosure;

(11) FIG. 11 is a block diagram of an LDPC decoder according to an embodiment of the present disclosure;

(12) FIG. 12 is a view illustrating a structure of a transport block according to another embodiment of the present disclosure

(13) FIGS. 13A and 13B illustrate a parity check matrix with ID=6 and R=1/3 according to various embodiments of the present disclosure;

(14) FIGS. 14A, 14B, 14C, 14D, and 14E are views illustrating a parity check matrix (an exponent matrix) designed in consideration of lifting according to various embodiments of the present disclosure;

(15) FIGS. 15A, 15B, 15C, 15D and 15E are views illustrating a parity check matrix (an exponent matrix) designed in consideration of lifting according to various embodiments of the present disclosure;

(16) FIGS. 16A, 16B, 16C, and 16D are views illustrating a parity check matrix (an exponent matrix) designed in consideration of lifting according to various embodiments of the present disclosure;

(17) FIGS. 17A and 17B are views illustrating a cycle property of a quasi-cyclic LDPC (QC-LDPC) code according to various embodiments of the present disclosure;

(18) FIG. 18 is an view illustrating an extended Tanner graph according to an embodiment of the present disclosure;

(19) FIG. 19 is a flowchart illustrating a sequence-based LDPC encoding method according to an embodiment of the present disclosure; and

(20) FIG. 20 is a block diagram of a transmitter for performing sequence-based LDPC encoding according to an embodiment of the present disclosure.

(21) Throughout the drawings, like reference numerals will be understood to refer to like parts, components, and structures.

DETAILED DESCRIPTION

(22) The following description with reference to the accompanying drawings is provided to assist in a comprehensive understanding of various embodiments of the present disclosure as defined by the claims and their equivalents. It includes various specific details to assist in that understanding but these are to be regarded as merely exemplary. Accordingly, those of ordinary skill in the art will recognize that various changes and modifications of the various embodiments described herein can be made without departing from the scope and spirit of the present disclosure. In addition, descriptions of well-known functions and constructions may be omitted for clarity and conciseness.

(23) The terms and words used in the following description and claims are not limited to the bibliographical meanings, but, are merely used by the inventor to enable a clear and consistent understanding of the present disclosure. Accordingly, it should be apparent to those skilled in the art that the following description of various embodiments of the present disclosure is provided for illustration purpose only and not for the purpose of limiting the present disclosure as defined by the appended claims and their equivalents.

(24) It is to be understood that the singular forms “a,” “an,” and “the” include plural referents unless the context clearly dictates otherwise. Thus, for example, reference to “a component surface” includes reference to one or more of such surfaces.

(25) By the term “substantially” it is meant that the recited characteristic, parameter, or value need not be achieved exactly, but that deviations or variations, including for example, tolerances, measurement error, measurement accuracy limitations and other factors known to those of skill in the art, may occur in amounts that do not preclude the effect the characteristic was intended to provide.

(26) The following exponent matrix is equivalent to a sequence corresponding to a parity-check matrix or the exponent matrix.

(27) The following block size can have at least two different integer values.

(28) Those skilled in the art will understand that the subject matter of the present disclosure can be implemented in other systems having a similar technical background with a slight modification without departing from the scope of the present disclosure.

(29) The advantages and features of the present disclosure, and a method for achieving them will be apparent from the attached drawings and the following detailed description of embodiments. However, embodiments of the present disclosure may be implemented in various ways, not limited to the following embodiments. The various embodiments of the present disclosure are provided to assist in a comprehensive understanding of the scope and spirit of the present disclosure, and the present disclosure is defined only by the appended claims and their equivalents. Like reference numeral denotes the same components through the specification.

(30) While the following description will be given of the present disclosure with the appreciation that there is only one circulant permutation matrix corresponding to one block for convenience of description, the same thing is applicable to the case where a plurality of circulant permutation matrices are included in one block.

(31) According to embodiments of the present disclosure, a parity check matrix may be extracted using a memory, given preliminarily in a transmitter or receiver, or generated directly in the transmitter or receiver. The transmitter may store or generate a sequence or integer matrix corresponding to the parity check matrix, and apply the sequence or integer matrix to encoding. Similarly, the receiver may store or generate the sequence or square matrix corresponding to the parity check matrix, and apply the sequence or square matrix to decoding.

(32) FIG. 3 is a block diagram of a transmitter according to an embodiment of the present disclosure.

(33) Referring to FIG. 3, a transmitter 300 may include a segmenter 310, a zero padder 320, a low density parity check (LDPC) encoder 330, a rate matcher 340, and a modulator 350 in order to process input bits of a variable length. The rate matcher 340 may include an interleaver 341 and a puncturer/repeater/zero remover 342.

(34) The components illustrated in FIG. 3 are components that encode and modulate input bits of a variable length. A component may be omitted from, modified in, or added to the transmitter 300.

(35) FIG. 4 is a block diagram of a receiver according to an embodiment of the present disclosure.

(36) Referring to FIG. 4, a receiver 400 may include a demodulator 410, a rate dematcher 420, an LDPC decoder 430, a zero remover 440, and a desegmenter 450 in order to process information of a variable length. The rate dematcher 420 may include a log likelihood ratio (LLR) inserter 422, an LLR combiner 423, and a deinterleaver 424.

(37) The components illustrated in FIG. 4 execute functions corresponding to their counterparts illustrated in FIG. 3. A component may be omitted from, modified in, or added to the receiver 400.

(38) Let S LDPC codes to be designed by lifting be denoted by C.sub.1, . . . , C.sub.S, and let the size of a row block or a column block in a parity check matrix H.sub.z of each LDPC code C.sub.Z be denoted by Z (Z=1, . . . , S). The parity check matrix H.sub.z of each code C.sub.Z has an m×n exponent matrix E(H.sub.Z)=(e.sub.i,j.sup.(z)) where each exponent e.sub.i,j.sup.(z) is a value selected from among the values of {−1, 0, 1, 2, . . . , Z−1}. Although an exponent indicating a zero matrix is represented as −1 in the present disclosure, the exponent may be changed to a different value for the convenience of a system.

(39) Therefore, the exponent matrix of an LDPC code C.sub.S having a largest parity check matrix is given as E(H.sub.S)=(e.sub.i,j.sup.(S)).

(40) A general lifting scheme for acquiring E(H.sub.S)=(e.sub.i,j.sup.(S)) may be expressed as Equation 7.

(41) $\begin{array}{cc}E\left(H_Z\right)=\left(e_{\mathrm{ij}}^{\left(Z\right)}\right),e_{\mathrm{ij}}^{\left(Z\right)}=\{\begin{array}{c}{e}_{\mathrm{ij}}^{\left(S\right)},e_{\mathrm{ij}}^{\left(S\right)}\le 0\\ f\left(e_{\mathrm{ij}}^{\left(S\right)},Z\right),e_{\mathrm{ij}}^{\left(S\right)}>0\end{array}.\mathrm{Or}E\left(H_Z\right)=\left(e_{\mathrm{ij}}^{\left(Z\right)}\right),e_{\mathrm{ij}}^{\left(Z\right)}=\{\begin{array}{c}{e}_{\mathrm{ij}}^{\left(S\right)},e_{\mathrm{ij}}^{\left(S\right)}<0\\ f\left(e_{\mathrm{ij}}^{\left(S\right)},Z\right),e_{\mathrm{ij}}^{\left(S\right)}\ge 0\end{array}.& \mathrm{Equation}7\end{array}$

(42) In Equation 7, a lifting function f(x, Z) is an integer function defined by integers x and Z. For example, the lifting function f(x,Z) is a function determined by the exponents of the parity check matrix of a given quasi-cyclic LDPC (QC-LDPC) code and the size of a circulant matrix included in the parity check matrix of the QC-LDPC code. In this context, a lifting method of the present disclosure will be described briefly. In the lifting method, the exponents of an exponent matrix given to define an LDPC code are converted using integers corresponding to the exponents and Z determined from the size Z×Z of a circulant matrix, and LDPC encoding or decoding is performed using the converted exponents.

(43) An embodiment of the present disclosure provides a method for appropriately selecting the function f(x,Z) as an exponent matrix conversion rule and designing a parity check matrix according to the selected function f(x,Z). When the function f(x,Z) has a different value for every Z value, implementation of the parity check matrix in a system increases complexity. Therefore, the present disclosure deals with a method for minimizing performance degradation with reduced implementation complexity by using the same f(x,Z) value for different Z values. In other words, the function f(x,Z) of the present disclosure is characterized by conversion to the same exponent matrix at least for different Z values. However, it is not necessary to always impose this constraint on f(x,Z).

(44) Exponents representing a circulant permutation matrix and a zero matrix included in the parity check matrix of each LDPC code may be determined by Equation 8 or Equation 9.

(45) $\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}\le 0\\ \mathrm{mod}\left(e_{i,j}^{\left(S\right)},2^k\right)& \mathrm{if}{e}_{i,j}^{\left(S\right)}>0\mathrm{and}{2}^k\le Z<2^{k+1}\end{array}& \mathrm{Equation}8\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}<0\\ \mathrm{mod}\left(e_{i,j}^{\left(S\right)},2^k\right)& \mathrm{if}{e}_{i,j}^{\left(S\right)}\ge 0\mathrm{and}{2}^k\le Z<2^{k+1}\end{array}& \mathrm{Equation}9\end{array}$

(46) In Equation 8 and Equation 9, mod (e.sub.i,j.sup.(S), 2.sup.k) represents the remainder of dividing e.sub.i,j.sup.(S) by 2.sup.k where k is 0, 1, . . . , └ log.sub.2S┘. └x┘ represents a largest integer smaller than X.

(47) First, a block size Z is determined. The block size Z may be determined based on exponent matrix information or the size of an information word.

(48) Once the block size Z is determined, a range of numbers to which the block size Z belongs is determined. More specifically, referring to Equation 8 or Equation 9, if all of the exponents of circulant permutation matrices included in the parity check matrix of the largest QC-LDPC code are set, the range of numbers to which the block size Z belongs is first determined. Subsequently, a representative value of the determined range (a specific value or predetermined value in the determined range) is determined, and if the representative value is not a value representing a zero matrix, the exponents of circulant permutation matrices of a final desired QC-LDPC code may be determined by performing a modulo operation on the representative value. While in the embodiment of the present disclosure, the first value in a range is set as a representative value of the range, various other values may be available as the representative value.

(49) For reference, the range of numbers to which the block size Z belongs in Equation 8 or Equation 9 may be determined in various methods. For example, the determination may be made easily by defining k according to Z as k=└ log.sub.2 Z┘ as illustrated in Equation 10 or Equation 11. For example, the operation for determining a range to which the block size Z belongs and the operation for determining a representative value for the range may be performed simply by applying a system-set calculation method to the block size Z.

(50) $\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}\le 0\\ \mathrm{mod}\left(e_{i,j}^{\left(S\right)},2^k\right)& \mathrm{if}{e}_{i,j}^{\left(S\right)}>0\mathrm{and}k=.Math.{\log }_{2}Z.Math.\end{array}& \mathrm{Equation}10\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}<0\\ \mathrm{mod}\left(e_{i,j}^{\left(S\right)},2^k\right)& \mathrm{if}{e}_{i,j}^{\left(S\right)}\ge 0\mathrm{and}k=.Math.{\log }_{2}Z.Math.\end{array}& \mathrm{Equation}11\end{array}$

(51) As described above, an embodiment of the present disclosure may configure a parity check matrix of every possible block size Z using the circulant permutation matrices included in the parity check matrix of the largest QC-LDPC code.

(52) While a modulo operation is taken as an example in the present disclosure, many other operations are also applicable.

(53) For example, a flooring operation described in Equation 12 or Equation 13 may be used.

(54) $\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}\le 0\\ .Math.\frac{e_{i,j}^{\left(S\right)}}{2^{k_s-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S\right)}>0\mathrm{and}{2}^k\le Z<2^{k+1}\end{array}& \mathrm{Equation}12\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}<0\\ .Math.\frac{e_{i,j}^{\left(S\right)}}{2^{k_s-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S\right)}\ge 0\mathrm{and}{2}^k\le Z<2^{k+1}\end{array}& \mathrm{Equation}13\end{array}$

(55) In Equation 12 or Equation 13, k.sub.s is a constant preset by the system. Although it is typical that k.sub.s=└ log.sub.2S┘, k.sub.s may be changed according to a system requirement.

(56) 0$.Math.\frac{e_{\mathrm{ij}}^{\left(S\right)}}{2^{k_S-k}}.Math.$
represents the quotient of dividing e.sub.i,j.sup.(S) by 2.sup.k.sup.s.sup.−k (k may be 0, 1, . . . , └ log.sub.2S┘).

(57) For reference, the operation for determining the range of numbers to which the block size Z belongs by Equation 12 or Equation 13 may be performed easily by defining k according to Z as k=└ log.sub.2Z┘ as illustrated in Equation 14 or Equation 15.

(58) $\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}\le 0\\ .Math.\frac{e_{i,j}^{\left(S\right)}}{2^{k_S-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S\right)}>0\mathrm{and}k=.Math.{\log }_{2}Z.Math.\end{array}& \mathrm{Equation}14\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}<0\\ .Math.\frac{e_{i,j}^{\left(S\right)}}{2^{k_S-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S\right)}\ge 0\mathrm{and}k=.Math.{\log }_{2}Z.Math.\end{array}& \mathrm{Equation}15\end{array}$

(59) The above process of the present disclosure is summarized as follows.

(60) If information about a parity check matrix (that is, information about an exponent matrix) is given in a given communication or broadcasting system, the block size Z of the parity check matrix is determined, and an integer k is determined based on the block size Z by k=└ log.sub.2Z┘ according to a system-set method. A sequence corresponding to the blocks of the parity check matrix is converted by applying a predefined computation method based on the integer k=└ log.sub.2Z┘, and encoding and decoding are performed using the converted sequence.

(61) For reference, the reason for using 2.sup.k.sup.s.sup.−k as the denominator in Equation 12 to Equation 15 will be described briefly as follows.

(62) If the floor lifting of the related art as described in Equation 5 is applied, each entry of a given exponent matrix is multiplied by Z/S. A general integer division and multiplication increases implementation complexity. For complexity reduction, approximation of a value to a form with base 2, such as 2.sup.X or 2.sup.−X, integer division and multiplication may be implemented easily.

(63) If S=2.sup.k.sup.s from k.sub.s=└ log.sub.2Z┘ where 2.sup.k≤Z<2.sup.k+1, it is obvious that 2.sup.k.sup.s.sup.−k −1<S/Z≤2.sup.k.sup.s.sup.−k. Thus, [S/Z]=2.sup.−(k.sup.s.sup.−k), and Z/S may be approximated to Z/S≈2.sup.k.sup.s.sup.−k. Floor lifting using Z/S≈2.sup.−(k.sup.s.sup.−k) simplifies implementation. It is obvious that the approximation is possible using flooring according to S or a Z range.

(64) Various embodiments of implementing Equation 10, Equation 11, Equation 14, and Equation 15 in hardware will be described below.

(65) In Equation 10 and Equation 11 based on a modulo operation, calculation of the remainder of a given exponent e.sub.ij.sup.(S) by 2.sup.k is equivalent to selection and output of only bits at k.sup.th and lower digits, when the exponent e.sub.ij.sup.(S) is expressed as a binary number. For example, if a given exponent is 118, its binary number is 1110110. Herein, the remainder of dividing the exponent by 2.sup.6 (=64) is obtained by selecting only bits at 5.sup.th and lower digits, that is, 110110(=2.sup.5+2.sup.4+2.sup.2+2.sup.1=5.sup.4).

(66) Calculation of the quotient of dividing a given exponent e T by in Equation 14 and Equation 15 based on flooring is equivalent to selection and output of only bits at digits higher than a (k.sub.s−k).sup.th digit from the start, when the exponent e.sub.ij.sup.(S) is expressed as a binary number. For example, if S=256, k.sub.s=┘ log.sub.2256┘=8, and the given exponent is 157, the binary number is 10011101. If for Z=96, a flooring operation is performed on the exponent 10011101, calculating the quotient of dividing the exponent 10011101 by 2.sup.2 (=4) is equivalent to selecting only bits at digits higher than a second digit in the exponent, 100111(=2.sup.5+.sup.22+2.sup.1+1=39), considering that k=┘ log.sub.296┘=6 and k.sub.s−k=2. Flooring-based lifting may be regarded as selecting k bits from the start, when an exponent is expressed as a binary number of k.sub.s bits. For example, if S=256, k.sub.s=┘ log.sub.2256┘=8, a given exponent is 00100101, and a flooring operation is performed for Z=96, calculation of the quotient of dividing the exponent by 2.sup.2 (=4) is equivalent to selection of the first 6 bits of the exponent 00100101, 001001(=9), considering that k=┘ log.sub.296┘=6 and k.sub.s−k=2.

(67) Further, it is obvious that although ranges are defined on a 2.sup.k basis, the ranges may also be defined on a 3.sup.k basis or on an any other unit basis. The ranges may not need to be set always in the same rule. According to a lifting process, ranges may be set differently, such as 2.sup.k≤Z<2.sup.k+1, 2.sup.k+1≤Z<3.Math.2.sup.k+1 and 3.Math.2.sup.k+1≤Z<2.sup.k+2.

(68) While it has been described that when ranges of the block size Z to which lifting is applied are defined as 1.sub.i≤Z<1.sub.i+1 (i=1, 2 . . . ), the representative value of each i.sup.th range is set as 1.sub.i, the representative value may be changed according to a system requirement.

(69) If S LDPC codes designed by lifting are C.sub.1, . . . , C.sub.S, and Z values being row block sizes or column block sizes increment sequentially by D at each time, such as Z={D, 2*D, 3*D, 4*D, . . . , S*D}, rather than the Z values sequentially increases, such as 1, 2, 3, . . . , lifting may be performed in the manner expressed as Equation 16 to Equation 23.

(70) $\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}<0\\ \mathrm{mod}\left(e_{i,j}^{\left(S\right)},2^{k}D\right)& \mathrm{if}{e}_{i,j}^{\left(S\right)}\ge 0\mathrm{and}{2}^k\le \frac{Z}{D}<2^{k+1}\end{array}& \mathrm{Equation}16\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}\le 0\\ \mathrm{mod}\left(e_{i,j}^{\left(S\right)},2^{k}D\right)& \mathrm{if}{e}_{i,j}^{\left(S\right)}>0\mathrm{and}{2}^k\le \frac{Z}{D}<2^{k+1}\end{array}& \mathrm{Equation}17\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}<0\\ \mathrm{mod}\left(e_{i,j}^{\left(S\right)},2^{k}D\right)& \mathrm{if}{e}_{i,j}^{\left(S\right)}\ge 0\mathrm{and}k=.Math.{\log }_2\left(\frac{Z}{D}\right).Math.\end{array}& \mathrm{Equation}18\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}\le 0\\ \mathrm{mod}\left(e_{i,j}^{\left(S\right)},2^{k}D\right)& \mathrm{if}{e}_{i,j}^{\left(S\right)}>0\mathrm{and}k=.Math.{\log }_2\left(\frac{Z}{D}\right).Math.\end{array}& \mathrm{Equation}19\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}<0\\ .Math.\frac{e_{i,j}^{\left(S\right)}}{2^{k_S-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S\right)}\ge 0\mathrm{and}{2}^k\le \frac{Z}{D}<2^{k+1}\end{array}& \mathrm{Equation}20\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}\le 0\\ .Math.\frac{e_{i,j}^{\left(S\right)}}{2^{k_S-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S\right)}>0\mathrm{and}{2}^k\le \frac{Z}{D}<2^{k+1}\end{array}& \mathrm{Equation}21\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}<0\\ .Math.\frac{e_{i,j}^{\left(S\right)}}{2^{k_S-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S\right)}\ge 0\mathrm{and}k=.Math.{\log }_2\left(\frac{Z}{D}\right).Math.\end{array}& \mathrm{Equation}22\end{array}$$\begin{array}{cc}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S\right)}& \mathrm{if}{e}_{i,j}^{\left(S\right)}\le 0\\ .Math.\frac{e_{i,j}^{\left(S\right)}}{2^{k_S-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S\right)}>0\mathrm{and}k=.Math.{\log }_2\left(\frac{Z}{D}\right).Math.\end{array}& \mathrm{Equation}23\end{array}$

(71) The lifting method has been described above on the assumption that there is one parity check matrix. However, if a plurality of parity check matrices are used, lifting may support more excellent coding performance.

(72) Let S LDPC codes designed by lifting be denoted by C.sub.1, . . . , C.sub.S. If the size of row blocks and column blocks, Z increases in the order of 1, 2, 3, . . . , a method for supporting lifting using a plurality of parity check matrices, instead of a single parity check matrix, will be described. For convenience of description, application of lifting based on two parity check matrices will be described. An LDPC code corresponds to at least two parity check matrices of different sizes, and the parity check matrices may be defined using different row block (or column block) sizes and the same sequence (or integer matrix). The lifting method described by Equation 8 to Equation 23 will be summarized briefly. If 2.sup.k≤Z<2.sup.k+1 or 2.sup.k≤Z/D<2.sup.k+1, an exponent matrix corresponding to Z may be identical to an exponent matrix with Z=2.sup.k or Z=2.sup.kD. In other words, up to 2.sup.k parity check matrices may be acquired from the same exponent matrix according to the range of Z.

(73) However, the algebraic characteristics of a parity check matrix are determined according to an exponent matrix and the size Z of a permutation matrix included in the parity check matrix. If more parity check matrices have the same exponent matrix, the probability of performance degradation may be increased.

(74) Therefore, the following method may be used in order to reduce occurrences of the same exponent matrix according to each Z value. It is first assumed that two exponent matrices E(H.sub.S1)=(e.sub.i,j.sup.(S1)), E(H.sub.S2)=(e.sub.i,j.sup.(S1)) are given to apply sequence conversion. Notably, it is assumed that the mother matrices of the exponent matrices are the same. As in Equation 24 or Equation 25, conversion of different exponent matrices may be applied according to Z values.

(75) $\begin{array}{cc}i)2^k\le Z<3.Math.2^{k-1}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S1\right)}& \mathrm{if}{e}_{i,j}^{\left(S1\right)}<0\\ \mathrm{mod}\left(e_{i,j}^{\left(S1\right)},2^k\right)& \mathrm{if}{e}_{i,j}^{\left(S1\right)}\ge 0\end{array}\mathrm{ii})3.Math.2^{k-1}\le Z<2^{k+1}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S2\right)}& \mathrm{if}{e}_{i,j}^{\left(S2\right)}<0\\ \mathrm{mod}\left(e_{i,j}^{\left(S2\right)},3.Math.2^k\right)& \mathrm{if}{e}_{i,j}^{\left(S2\right)}\ge 0\end{array}& \mathrm{Equation}24\end{array}$$\begin{array}{cc}i)2^k\le Z<3.Math.2^{k-1}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S1\right)}& \mathrm{if}{e}_{i,j}^{\left(S1\right)}<0\\ .Math.\frac{e_{i,j}^{\left(S1\right)}}{2^{k_S-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S1\right)}\ge 0\end{array}\mathrm{ii})3.Math.2^{k-1}\le Z<2^{k+1}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S2\right)}& \mathrm{if}{e}_{i,j}^{\left(S2\right)}<0\\ .Math.\frac{3.Math.e_{i,j}^{\left(S2\right)}}{2^{k_S-k+1}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S2\right)}\ge 0\end{array}& \mathrm{Equation}25\end{array}$

(76) Equation 24 and Equation 25 will be described below.

(77) First, ranges of Z values are determined, and an integer representing each range is determined. In Equation 24 and Equation 25, the first value of each range is determined to be a representative value of the range. Subsequently, one of a plurality of exponent matrices is selected according to a Z-value range or a representative value, and exponent matrix conversion is performed using the selected exponent matrix.

(78) As two exponent matrices are used as described in Equation 24 and Equation 25, if 2.sup.k≤Z<2.sup.k+1, 2.sup.k−1 parity check matrices have the same exponent matrix. Since the number of occurrences of the same exponent matrix is reduced in this manner, design of a QC-LDPC code may be facilitated and performance degradation may further be reduced. On the other hand, since there should be a plurality of exponent matrices and Z-value ranges should be defined more elaborately, complexity is slightly increased. Accordingly, lifting should be applied in proper consideration of performance and complexity.

(79) For reference, ii) of Equation 25 may be changed to another similar equation, such as Equation 26 in order to reduce implementation complexity.

(80) $\begin{array}{cc}\mathrm{ii})3.Math.2^{k-1}\le Z<2^{k+1}{e}_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S2\right)}& \mathrm{if}{e}_{i,j}^{\left(S2\right)}<0\\ .Math.\frac{e_{i,j}^{\left(S2\right)}}{2^{k_S-k}}.Math.+.Math.\frac{e_{i,j}^{\left(S2\right)}}{2^{k_S-k+1}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S2\right)}\ge 0\end{array}& \mathrm{Equation}26\end{array}$

(81) Another embodiment of supporting lifting using a plurality of exponent matrices will be described.

(82) It is assumed that values available as a row block size or a column block size are given as Equation 27.

(83) $\begin{array}{cc}A,A+1,A+2,A+3,.Math.,2A-2,2A-12A,2\left(A+1\right),2\left(A+2\right),.Math.,2\left(2A-2\right),2\left(2A-1\right)4A,4\left(A+1\right),4\left(A+2\right),.Math.,4\left(2A-2\right),4\left(2A-1\right).Math.2^{S}A,2^S\left(A+1\right),2^S\left(A+2\right),.Math.,2^S\left(2A-2\right),2^S\left(2A-1\right)& \mathrm{Equation}27\end{array}$

(84) In Equation 27, A and S are any positive integers. The block sizes are classified into A sets, as expressed as Equation 28.
X.sub.i={(A+i),2(A+i),2.sup.2(A+i) . . . ,2.sup.S(A+i)},i=0,1,2, . . . ,A−1.   Equation 28

(85) In a set X.sub.i, integers are in a factor or multiple relationship. Therefore, it is noted that one exponent matrix may be generated by applying the lifting scheme of the related art for the block sizes of each set X.sub.i. In other words, all exponent matrices supporting the block sizes included in the set X.sub.i may be generated out of a single exponent matrix. Therefore, once a total of A exponent matrices are obtained, exponent matrices supporting the block sizes included in the A sets, X.sub.i (i=0, . . . , A−1) may be generated. In general, A exponent matrices may be converted to exponent matrices for a total of A*S block sizes.

(86) While it has been described that both a supported minimum block size and the number of elements in each of the sets into which block sizes are classified are equally A in the above embodiment of the present disclosure, this should not be construed as limiting the present disclosure.

(87) Accordingly, once a transmitter and a receiver determine a block size according to an information word size, they determine a block size set to which the block size belongs (an exponent matrix to be used), and apply lifting using the exponent matrix defined for the block size set, thereby achieving an exponent matrix suitable for the block size.

(88) For example, if block sizes are classified as described in Equation 28 and a block size Z is determined according to a given information word size in the transmitter and the receiver, non-negative integers b and i satisfying Z=2.sup.b(A+i) for a given minimum block size A are obtained and b.sup.th lifting is applied using an i.sup.th exponent matrix, thus achieving an exponent matrix or a parity check matrix corresponding to the block size Z. For reference, the non-negative integers b and i satisfying Z=2.sup.b(A+i) may be obtained in various manners. For example, b may be easily obtained by setting b=x−1 for a first x satisfying Z/2.sup.X<A, while the determined Z value is sequentially divided by 2. After b is obtained, i may be easily obtained by Z/2.sup.b−A=i.

(89) As described before, the foregoing method needs a plurality of exponent matrices, thus increasing complexity slightly. However, the method advantageously improves performances because lifting almost optimum for an information word length belonging to each set X.sub.i may be applied.

(90) Another embodiment of supporting lifting using a plurality of exponent matrices will be described.

(91) To get a plurality of exponent matrices according to a block size, the block size Z may be classified according to an integer type. For example, the block size Z may be expressed as Z=qa+b where q, a, and b are all non-negative integers. For q=4, block sizes may be classified as enumerated in Equation 29.

(92) $\begin{array}{cc}\begin{array}{c}1,2,3,4,\\ 5,6,7,8,\\ \mathrm{.Math.}\\ 4a+1,4a+2,4a+4,4\left(a+1\right)\\ \mathrm{.Math.}\end{array}& \mathrm{Equation}29\end{array}$

(93) The block sizes may be classified into a plurality of sets described in Equation 30. For example, the block sizes Z are grouped into one or more sets each including 4 block sizes, and each set is mapped to a base matrix (for example, an exponent matrix).
X.sub.b={x|x=q(a−1)+b,a=1,2 . . . },b=1,2, . . . ,q  Equation 30

(94) It is assumed that the block sizes Z are classified by Equation 30, each set X.sub.b has a specific exponent matrix, and b exponent matrices are given as E(H.sub.S.sub.b)=(e.sub.i,j.sup.(S.sup.b.sup.)), for sequence conversion. Notably, it is assumed that the same mother matrix corresponds to the exponent matrices. Conversion of different exponent matrices may be applied according to Z values, as expressed as Equation 31 or Equation 32.

(95) $\mathrm{Equation}31$$e_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S_b\right)}& \mathrm{if}{e}_{i,j}^{\left(S_b\right)}<0\\ \mathrm{mod}\left(e_{i,j}^{\left(S_b\right)}\right),q.Math.\left(2^k-1\right)+b& \mathrm{if}{e}_{i,j}^{\left(S_b\right)}\ge 0,Z\in X_b,2^k\le a<2^{k+1}\end{array}\mathrm{Equation}32e_{i,j}^{\left(Z\right)}=\{\begin{array}{cc}{e}_{i,j}^{\left(S_b\right)}& \mathrm{if}{e}_{i,j}^{\left(S_b\right)}<0\\ .Math.\frac{e_{i,j}^{\left(S_b\right)}}{2^{k_s-k}}.Math.& \mathrm{if}{e}_{i,j}^{\left(S_b\right)}\ge 0,Z\in X_b,2^k\le a<2^{k+1}\end{array}$

(96) While the foregoing lifting method has been described on the assumption that lifting is applied to an entire exponent matrix corresponding to a parity check matrix, for convenience of description, lifting may be applied to a part of the exponent matrix. For example, a partial matrix corresponding to parity bits of a parity check matrix generally has a special structure, for efficient encoding. In this case, lifting may cause a change in an encoding method or complexity. Therefore, to maintain the same encoding method or the same complexity, lifting may not be applied or lifting different from lifting applied to a part of an exponent matrix corresponding to information word bits may be applied to a part of the exponent matrix corresponding to a parity of a parity check matrix. In other words, lifting applied to a sequence corresponding to information word bits, and lifting applied to a sequence corresponding to parity bits may be set differently for an exponent matrix. Under circumstances, lifting may not be applied to the whole or part of the sequence corresponding to the parity bits, and thus the sequence may be used fixedly without sequence conversion.

(97) Information of a parity check matrix to be used for encoding and decoding may be generated by performing the foregoing lifting method in the same manner in a transmitter and a receiver. For example, if both the transmitter and the receiver are aware of the same exponent matrix and the same lifting method, once the receiver acquires information about Z used in the transmitter, the receiver may acquire information about an exponent matrix used by the transmitter by converting the stored exponent matrix. Although the transmitter may directly transmit information about the Z value, the receiver may determine the Z value in a different manner.

(98) If the number of information word column blocks is K.sub.b, a supported information word size is K.sub.bZ in the lifting method of the present disclosure. For example, the granularity of supported information words is K.sub.b bits. Thus, to support a smaller information word granularity than K.sub.b bits, a method, such as shortening may be used. For example, if an information word length to be supported is K, a Z value satisfying K.sub.bZ≥K is first determined. When shortening is needed, an information word is shortened by K.sub.bZ−K bits. Thus, a K-bit information word may be applied easily. Accordingly, the maximum length of shortened bits may be K.sub.b−1.

(99) This operation may be summarized briefly as follows.

(100) Step 1) Z is determined by Equation 33.
Z=┌K/K.sub.b┘  Equation 33

(101) Step 2) An exponent matrix of a parity check matrix supporting a length K.sub.bZ is generated by applying lifting with respect to Z.

(102) Step 3) In LDPC encoding/decoding based on the exponent matrix, a shortened information word of a size K.sub.bZ−K is considered.

(103) Meanwhile, an LDPC code may be decoded by an iterative decoding algorithm based on a sum-product algorithm on the bipartite graph illustrated in FIG. 2, and the sum-product algorithm is a form of message passing algorithm.

(104) With reference to FIGS. 5A and 5B, a general message passing operation used for LDPC decoding will be described below.

(105) FIGS. 5A and 5B illustrate message passing operations at any check node and variable node, for LDPC decoding according to various embodiments of the present disclosure.

(106) Referring to FIG. 5A, a check node m 500, and a plurality of variable nodes 510, 520, 530, and 540 connected to the check node m 500 are shown. T.sub.n′,m is a message passed from the variable node n′ 510 to the check node m 500, and E.sub.n,m is a message passed from the check node m 500 to the variable node n 530. A set of all variable nodes connected to the check node m 500 is defined as N(m), and a set obtained by excluding the variable node n 530 from the set N(m) is defined as N(m)\n.

(107) In this case, a message update rule based on the sum-product algorithm may be expressed as Equation 34.
|E.sub.n,m|=Φ[Σ.sub.n′∈N(m)\nΦ(|T.sub.n′,m|)]
Sign(E.sub.n,m)=Π.sub.n′∈N(m)\n sign(T.sub.n′,m)  Equation 34

(108) In Equation 34, Sign(E.sub.n,m) represents the sign of the message E.sub.n,m, and |E.sub.n,m| represents the magnitude of the message E.sub.n,m. Meanwhile, a function Φ(x) may be given by Equation 35.

(109) $\begin{array}{cc}\Phi \left(x\right)=-\log \left(\tanh \left(\frac{X}{2}\right)\right)& \mathrm{Equation}35\end{array}$

(110) Meanwhile, referring to FIG. 5B, a variable node x 550 and a plurality of check nodes 560, 570, 580, and 590 connected to the variable node x 550. E.sub.y′,x represents a message passed from the check node y′ 560 to the variable node x 550, and T.sub.y,x represents a message passed from the variable node x 550 to the check node y 580. A set of all variable nodes connected to the variable node x 550 is defined as M(x), and a set obtained by excluding the check node y 530 from the set M(x) is defined as M(x) y.

(111) In this case, a message update rule based on the sum-product algorithm may be expressed as Equation 36.
T.sub.y,x=E.sub.x+Σ.sub.y′∈M(x)\yE.sub.y′,x  Equation 36

(112) In Equation 36, E.sub.x represents an initial message value of the variable node X.

(113) A bit value of the node x may be decided by Equation 37.

(114) $\begin{array}{cc}{P}_x=E_x+\underset{y^{\prime }\in M\left(x\right)}{.Math.}{E}_{y^{\prime },x}& \mathrm{Equation}37\end{array}$

(115) In this case, a coded bit corresponding to the node x may be decided according to P.sub.x.

(116) The method described above with reference to FIGS. 5A and 5B is a general decoding method and thus will not be described herein. However, aside from the method illustrated in FIGS. 5A and 5B, other methods may be used in determining a message value passed between a variable node and a check node, as disclosed in Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 47, NO. 2, FEBRUARY 2001, pp 498-519).

(117) FIG. 6 is a block diagram of an LDPC encoder according to an embodiment of the present disclosure.

(118) Referring to FIG. 6, K.sub.ldpc bits may form K.sub.ldpc LDPC information bits I=(i.sub.0, i.sub.1, . . . , i.sub.Kldpc-1) for an LDPC encoder 610. The LDPC encoder 610 may generate an LDPC codeword including N.sub.ldpc bits, Λ=(c.sub.0, c.sub.1, . . . , c.sub.Nldpc-1)=(i.sub.0, i.sub.1, . . . , i.sub.Kldpc-1,p.sub.0,p.sub.1, . . . , p.sub.Nldpc-Kldpc-1) by systematically LDPC-encoding the K.sub.ldpc LDPC information word bits.

(119) As described in Equation 1, LDPC encoding involves an operation for determining a codeword in such a manner that the product between the LDPC codeword and a parity check matrix may be a zero vector. The parity check matrix of the present disclosure is in the form as defined by Equation 3 and Equation 4. Hereinbelow, a description will be given of a method for designing a parity check matrix and a method for using the same in order to address the length compatibility issue of the lifting method of the related art.

(120) It is assumed that there are a mother matrix H.sub.1 of a parity check matrix and an exponent matrix E(H.sub.1)=(e.sub.ij.sup.(1)) of the parity check matrix. Since the mother matrix H.sub.1 obviously includes only 0s and 1s as its entries, the exponent matrix E(H.sub.1) includes only−1s representing zero matrices or 0s representing identity matrices. The following is a modified modulo-based lifting method according to the present disclosure.

(121) For convenience of description, ranges of numbers for lifting are defined as 2.sup.k≤Z<2.sup.k+1 (k=0, 1, 2 . . . ). A maximum Z value is Z.sub.max.

(122) Step 1). If e.sub.i,j.sup.(1)=−1, e.sub.i,j.sup.(Z)=−1 Z=2, 3, . . . , Z.sub.max for E(H.sub.z)=(e.sub.i,j.sup.(Z)).

(123) Step 2) k=1. E(H.sub.2.sub.k)=e.sub.i,j.sup.(2.sup.k.sup.), E(H.sub.2.sub.k.sub.+1)=e.sub.i,j.sup.(2.sup.k.sup.+1), (H.sub.2.sub.k.sub.+2)=e.sub.i,j.sup.(2.sup.k.sup.+2), E(H.sub.2.sub.k+1.sub.−1)=e.sub.i,j.sup.(2.sup.k+1.sup.−1) are set so that the following conditions may be satisfied.

(124) Condition 1: If e.sub.i,j.sup.(2.sup.k.sup.−1)≠1, e.sub.i,j.sup.(2.sup.k.sup.) is determined to be one of e.sub.i,j.sup.(2.sup.k.sup.−1) and e.sub.i,j.sup.(2.sup.k−1.sup.)+2.sup.k−1.

(125) Condition 2: For every i and j, each exponent e.sub.i,j.sup.(2.sup.k), e.sub.i,j.sup.(2.sup.k.sup.+1), . . . , e.sub.i,j.sup.(2.sup.k+1.sup.−1), satisfies e.sub.in.sup.(2.sup.k.sup.)=e.sub.ij.sup.(2.sup.k+1.sup.)=e.sub.ij.sup.(2.sup.k+1.sup.−1).

(126) Condition 3: If k>A, a Tanner graph for each parity check matrix H.sub.2 k, H.sub.2.sub.k+1, . . . , H.sub.2.sub.k+1.sub.−1 does not include a short cycle between variable nodes (bit nodes) with orders of 2 and 3 (a short cycle is a predetermined value. Although the short cycle typically refers to a cycle of length 4 or 6, it may have a longer length according to the size of a given mother matrix to apply lifting. A is a constant determined according to the size of the given mother matrix to apply lifting).

(127) Condition 4: If the same cycle is generated for the exponents e.sub.ij.sup.(2.sup.k−1.sup.) and e.sub.ij.sup.(2.sup.k−1.sup.)+2.sup.k−1 of Condition 1, a case with a larger sum of the orders of variable nodes forming the cycle is selected.

(128) Step 3) k=k+1 is applied, and Step 2) is repeated until k=└ log.sub.2Z.sub.max┘.

(129) The method is a simple design method for a case where a modulo-based lifting method is applied. If a flooring lifting method is applied, Condition 1 and Condition 4 of Step 2) are represented as follows.

(130) Condition 1′: If e.sub.i,j.sup.(2.sup.k−1.sup.)≠1, the value of e.sub.i,j.sup.(2.sup.k) is determined to be one of 2e.sub.i,j.sup.(2.sup.k−1.sup.) and 2e.sub.i,j.sup.(2.sup.k−1.sup.)+1.

(131) Condition 4′: If the same cycle is generated for the exponents 2e.sub.i,j.sup.(2.sup.k−1.sup.) and 2e.sub.i,j.sup.(2.sup.k−1.sup.)+1 of Condition 1, a case with a larger sum of the orders of variable nodes included in the cycle is selected.

(132) FIG. 3 is a block diagram illustrating the detailed structure of a transmitter according to an embodiment of the present disclosure.

(133) Referring to FIG. 3, the transmitter 300 may include the segmenter 310, the zero padder 320, the LDPC encoder 330, the rate matcher 340, and the modulator 350 in order to process input bits of a variable length.

(134) The components illustrated in FIG. 3 encode and modulate input bits of a variable length. When needed, a component may be omitted from, modified in, or added to the components illustrated in FIG. 3.

(135) The LDPC encoder 330 illustrated in FIG. 3 may perform an operation of the LDPC encoder 500 illustrated in FIG. 5.

(136) Meanwhile, the transmitter 300 may determine necessary parameters (for example, an input bit length, a modulation and code rate (ModCod), a parameter for zero padding, a code rate/codeword length of an LDPC code, a parameter for interleaving, a parameter for repetition, a parameter for puncturing, and a modulation scheme), encode input bits based on the determined parameters, and transmit the coded bits to the receiver 400.

(137) If the variable number of input bits is larger than a predetermined value, the input bits may be segmented so that each segment may have a length equal to or less than the predetermined value. Each segmented block may correspond to one LDPC code block. However, if the number of input bits is equal to or less than the predetermined value, the input bits are not segmented. The input bits may correspond to one LDPC code block.

(138) Now, a detailed description will be given of a segmentation method.

(139) The segmenter 310 segments input bits. In the method for segmenting input bits in the segmenter 311, B input bits b.sub.0, b.sub.1, b.sub.2, b.sub.3, . . . , b.sub.B-1 (B>0) are input to the segmenter 310. If B is larger than a predetermined value being a maximum number of input bits for encoding, K.sub.max, the input bits are segmented. The maximum number of input bits for encoding, K.sub.max is determined according to a code rate, as listed in Table 1.

(140) TABLE-US-00001 TABLE 1 Code Rate K.sub.max K.sub.min 1/4 2048 8 1/2 4096 16 3/4 6144 24 7/8 7168 28

(141) Table 1 may be changed according to a system, and Table 2 may also be made.

(142) TABLE-US-00002 TABLE 2 Code Rate K.sub.max K.sub.min 8/9 3072 384 6/9 2304 288 4/9 1536 192 1/3 3072 384

(143) If the number of segment blocks is C, the number of bits to be segmented is determined as follows.

(144) If input bits are segmented into at least two segments, the two segments of input bits are separately LDPC-encoded, producing at least two forward error correction (FEC) frames. Accordingly, at least two FEC frames are required to transmit the input bits.

(145) Therefore, the segmenter 310 may calculate the number C of FEC frames by Equation 38.
C=┌B/(K.sub.max−L)┐  Equation 38

(146) In Equation 38, ┌x┐ represents a smallest integer equal to or larger than x.

(147) The following representation is possible.

(148) TABLE-US-00003 if B≤ K.sub.max  L = 0  Number of code blocks: C=1 B′ = B else  L = 24  Number of code blocks: C = ┌B / (K.sub.max − L)┐.  B′ = B + C .Math. L end if

(149) L represents the number of parity bits of a CRC code. The segment blocks are CRC-encoded separately. Therefore, the number of input bits, B is changed to B′ in consideration of the number of CRC bits.

(150) To make the segment blocks have the same number of bits, <Null> bits may be inserted. The number of <Null> bits and the number of bits in each block may be calculated in the following manner.

(151) Let an r.sup.th block of output bits of the segmenter 310 be denoted by c.sub.r0, c.sub.r1, c.sub.r2, c.sub.r3, . . . , c.sub.r(K.sub.r.sub.−1) where K.sub.r is the number of bits in the r.sup.th block.

(152) The number of bits in each block is determined as follows. To make the lengths of all blocks equal, <Null> bits are inserted in the last block. For example, the segmenter 310 may fill F<Null> bits (that is, bits being zeroes). Accordingly, F<Null> bits may be filled as illustrated in FIG. 7.

(153) FIGS. 7 and 8 illustrate structures of transport blocks according to various embodiments of the present disclosure.

(154) Referring to FIGS. 7 and 8, since the length of a padding field is calculated and as many<Null> bits as the calculated length are padded in a padding part, input bits may be segmented into a plurality of blocks each having an equal number of bits, that is, K.sub.r bits.

(155) It is possible to pad<Null> bits at the start or end of Segmentation C in FIG. 7.

(156) It is also possible to pad<Null> bits at the start or end of Segmentation C in FIG. 8.

(157) if C=1, Kr=B′

(158) else The number of filler bits F F=ceiling(B′/C)×C−B′ B″=B′+F

(159) Kr=B″/C

(160) The filler bits<NULL> shall be inserted at the end of the last block (or at the beginning of the first block).

(161) The position of <NULL> bits may be changed. For example, the <Null> bits may be inserted at the end or start of the last segment block. In the above, ceiling(x) represents a smallest integer equal to or larger than x. For example, ceiling(1.5)=2.

(162) For k=Kr−F−1−L to Kr−1−L, c.sub.(C-1)k=<NULL>

(163) end for

(164) end if

(165) If the number of segment blocks is 2 or large, each segment is CRC-encoded. A CRC code may be omitted according to a transmission system.

(166) for r=0 to C−1

(167) k=0 while k<K.sub.r−L c.sub.rk=b.sub.s//segmented bits are mapped. k=k+1 s=s+1 end while if C>1

(168) CRC bits p.sub.r0, p.sub.r1, p.sub.r2, . . . , p.sub.r(L-1) are added to the bits of the r.sup.th segment block c.sub.r0, c.sub.r1, c.sub.r2, c.sub.r3, . . . , c.sub.r(K.sub.r.sub.−L-1) and mapped to c.sub.rk as follows.

(169) For CRC calculation, it is assumed that filler bits, if present, have the value 0.

(170) while k<K, C.sub.rk=P.sub.r(k+L-K.sub.r.sub.) k=k+1 end while

(171) end if k=0

(172) end for

(173) Specifically, if C is larger than 1 as illustrated in FIG. 7, the segmenter 310 may group every K.sub.r input bits into one block, thus segmenting total input bits into C blocks. The blocks of input bits are individually CRC-encoded. As a result of encoding, the number of input bits for the zero padder 320 of the transmitter 300 may be K=(K.sub.r+L) where L is the parity length of a CRC code, 24.

(174) However, if L1 detail signaling is not segmented, K=B. The segmented blocks may be encoded in the following procedure.

(175) The zero padder 320 pads zero bits. Specifically, in the case of an LDPC code, a predetermined number of LDPC information word bits according to a code rate and a code length are required. This, if the number of bits in a segment block is smaller than the number of LDPC information word bits, the zero padder 320 may generate the predetermined number of LDPC information word bits by padding zero bits for LDPC encoding and output the LDPC information word bits to the LDPC encoder 330. On the other hand, if the number of bits in one block received from the segmenter 310 is equal to the number of LDPC information word bits, the zero padder 320 does not perform zero padding.

(176) Because the zero padder 320 pads zero bits for LDPC encoding, zero bits padded for shortening are not transmitted to the receiver 400.

(177) Specifically, Z is determined based on K.sub.ldpc_b defined according to a code rate. Z is the size of a sub-matrix in a parity check matrix of an LDPC code, and K.sub.ldpc_b is the number of column groups in an information word part of the parity check matrix. Therefore, the maximum of values obtained by dividing the length K of input bits by K.sub.ldpc_b is determined to be a sub-matrix size, thereby minimizing the number of <Null> bits. The submatrix size Z may be any integer between a minimum value and a maximum value. Hereinbelow, ZP represents the number of <Null> bits.
Z=┌K/K.sub.ldpc_b┐
ZP=Z×K.sub.ldpc_b−K
K.sub.ldpc=Z×K.sub.ldpc_b  Equation 39

(178) In Equation 39, the values of K.sub.ldpc_b are listed in [Table 3] according to the code rates of 1/4, 1/2, 3/4, and 7/8.

(179) TABLE-US-00004 TABLE 3 Code Rate K.sub.ldpc_b 1/4   8 1/2 16 3/4 24 7/8 28

(180) The parameters described in Table 3 may be changed according to a system, and Table 4 is also available.

(181) TABLE-US-00005 TABLE 4 Code Rate (R) K.sub.ldpc_b 8/9 32 2/3 24 4/9 16 1/3 32

(182) In the foregoing embodiment of the present disclosure, all integers from the minimum value to the maximum value are available as the submatrix size, Z. If Z is a multiple of D, Z may be determined for the number of input bits, K as follows. D may be 12.
Z=┌K/K.sub.ldpc_b×D┐×D  Equation 40

(183) //// zero padding for shortening

(184) For j=0 to ZP-1

(185) i.sub.k=<NULL>

(186) end for

(187) For j=ZP to K.sub.ldpc−1

(188) i.sub.k=c.sub.{k-ZP}

(189) end for

(190) The <NULL> bits may be padded at a specific position in information word bits. For example, the <NULL> bits may be positioned at the end of the information word.

(191) In another example, as <NULL> bits are padded and interleaved, the padded bits may be distributed uniformly across bit blocks corresponding to the column blocks of the parity check matrix.

(192) //// zero padding for shortening

(193) For j=0 to ZP-1

(194) x.sub.k=<NULL>

(195) end for

(196) For j=ZP to K.sub.ldpc−1

(197) x.sub.k=c.sub.{k−ZP}

(198) end for

(199) /// interleaving the information bits

(200) For j=0 to K.sub.ldpc b−1

(201) For k=0 to Z−1
i.sub.{j.Math.Z+k}=x.sub.{k.Math.Kldpc_b+j}

(202) end for k

(203) end for j

(204) Z is a submatrix size calculated by Equation 39 or Equation 40. K.sub.ldpc_b is the number of column blocks in an information word part of a parity check matrix, given as Table 3 or Table 4.

(205) More specifically, as illustrated in FIG. 8, the segmenter 310 inserts<Null> bits in a segment block (including a CRC), to thereby making the length of the segment block equal to the information word length of an LDPC code. The smallest of integers equal to or larger than the number K of input bits among multiples of the number of column blocks in the parity check matrix of the LDPC code is selected as the information word length of the LDPC code. For example, K.sub.ldpc=┌K/K.sub.ldpc_b┐×K.sub.ldpc_b.

(206) Now, a detailed description is given of the LDPC encoder 330 of the transmitter 300 or the LDPC encoder 500 of FIG. 5.

(207) The LDPC encoder 330 LDPC-encoders outputs bits of the zero padder 320.

(208) Specifically, the LDPC encoder 330 may generate LDPC parity bits by LDPC-encoding LDPC information word bits received from the zero padder 320, and output an LDPC codeword including the LDPC information word bits and the LDPC parity bits to the rate matcher 340.

(209) For example, K.sub.ldpc bits output from the zero padder 320 may form K.sub.ldpc LDPC information word bits I=(i.sub.0,i.sub.1, . . . , i.sub.K.sub.ldpc.sub.−1) for the LDPC encoder 330.

(210) The LDPC encoder 330 may generate an LDPC codeword with N.sub.ldpc bits, Λ=(c.sub.0,c.sub.1, . . . , c.sub.N1dpc-1)=(i.sub.0,i.sub.1, . . . , i.sub.Kldpc-1,p.sub.0,p.sub.1, . . . , p.sub.Nldpc-Kldpc-1) by systematically LDPC-encoding the K.sub.ldpc LDPC information word bits.

(211) According to the present disclosure, parameters for a parity check matrix are listed in Table 5. Code Rate means the code rate of an LDPC code, N.sub.ldpc_b represents the number of column blocks of the parity check matrix, equal to n in Equation 4, K.sub.ldpc_b represents the number of column blocks in an information word part of the parity check matrix, equal to (n−m), and N.sub.parity_b represents the number of column blocks or row blocks in a parity part of the parity check matrix.

(212) TABLE-US-00006 TABLE 5 Code Rate N.sub.ldpc_b K.sub.ldpc_b N.sub.parity_b 1/4 32 8 28 1/2 32 16 16 3/4 32 24 8 7/8 32 28 4

(213) For the size of a circulant permutation matrix being a submatrix, Z (L×L=Z*Z) in Equation 3 is 256, Table 6 to Table 9 list the exponent of each circulant permutation matrix, a.sub.i,j (0≤i<N.sub.ldpc-K.sub.ldpc, 0≤j<N.sub.ldpc). Table 6, Table 7, Table 8, and Table 9 describe parity check matrices of LDPC codes with code rates of 7/8, 3/4, 1/2, and 1/4, respectively. If the size of a circulant permutation matrix, Z is equal to or less than 255, the exponents of a parity check matrix, a ij (Z) is determined by Equation 41.

(214) 0$\mathrm{Equation}41$$a_{i,j}\left(z\right)=\{\begin{array}{c}{a}_{i,j}\mathrm{if}{a}_{i,j}\le 0\\ \mathrm{mod}\left(a_{i,j},2^k\right)\mathrm{for}{2}^k\le z<2^{k+1},0\le k\le 7,\mathrm{if}{a}_{i,j}>0\end{array}$

(215) In Equation 41, a.sub.i,j represents an entry in an i.sup.th row and a j.sup.th column in [Table 6] to [Table 9], which is the exponent of a circulant permutation matrix in an i.sup.th row and a j.sup.th column, for a circulant permutation matrix size of 256. a.sub.i,j(Z) represents the exponent of a circulant permutation matrix in an i.sup.th row and a j.sup.th column, for a circulant permutation matrix size of 255 or less (0≤Z<256).

(216) Specifically, for 2.sup.0≤Z<2.sup.1, if a.sub.i,j is −1 or 0, a.sub.i,j(Z) is a.sub.i,j and if a.sub.i,j is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j, 1). This means that a circulant matrix other than a zero matrix is 1 representing a 1×1 circulant matrix.

(217) Specifically, for 2.sup.1≤Z<2.sup.2, if a.sub.i,j is −1 or 0, a.sub.i,j(Z) is a.sub.i,j, and if a.sub.i,j is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j, 2.sup.1).

(218) Specifically, for 2.sup.2≤Z<2.sup.3, if a.sub.i,j is −1 or 0, a.sub.i,j(Z) is a.sub.i,j, and if a.sub.i,j is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j, 2.sup.2).

(219) Specifically, for 2.sup.7≤Z<2.sup.8, if a.sub.i,j is −1 or 0, a.sub.i,j(Z) is a.sub.i,j, and if a.sub.i,j is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j, 2.sup.7).

(220) TABLE-US-00007 TABLE 6 234 32 12 24 195 162 81 237 44 251 205 172 141 10 194 −1 241 251 105 139 112 28 22 255 227 68 31 0 182 177 131 162 252 134 245 228 250 205 252 204 184 21 94 249 10 45 63 105 155 5 75 14 70 231 227 26 101 246 161 3S 88 123 232 32 71 27 −1 210 105 0 −1 147 78 153 178 84 1 0 −1 −1 −1 169 61 −1 211 100 92 132 −1 174 181 −1 0 0 0 −1 99 −1 91 44 88 −1 101 72 47 −1 48 79 −1 −1 0 0 1 184 16 192 −1 161 80 −1 1 168 −1 128 1 −1 −1 0

(221) TABLE-US-00008 TABLE 7 −1 180 175 225 −1 22 −1 −1 −1 153 −1 −1 86 188 −1 147 246 −1 14 127 61 −1 −1 −1 −1 50 13 −1 66 159 −1 160 245 −1 −1 −1 4 −1 152 247 108 −1 70 174 −1 −1 83 −1 −1 231 −1 −1 −1 99 249 54 144 −1 −1 56 −1 −1 193 −1 234 32 12 24 195 162 81 237 −1 −1 205 −1 −1 −1 −1 −1 241 251 105 139 112 28 22 255 −1 −1 −1 −1 −1 −1 131 −1 252 134 245 228 250 205 252 204 184 21 −1 −1 −1 −1 −1 105 155 5 75 14 70 231 227 26 −1 −1 −1 35 88 123 −1 −1 158 −1 203 −1 218 −1 68 −1 1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 141 4 −1 75 −1 −1 0 0 −1 −1 −1 −1 −1 −1 77 −1 55 −1 207 −1 103 −1 −1 0 0 −1 −1 −1 −1 120 26 92 −1 −1 168 −1 106 −1 −1 −1 0 1 −1 −1 −1 −1 27 −1 210 −1 −1 −1 147 0 −1 −1 −1 1 0 −1 −1 −1 −1 61 −1 211 100 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 101 −1 −1 −1 −1 −1 −1 −1 0 0 1 −1 −1 −1 −1 −1 −1 −1 1 −1 −1 −1 −1 −1 −1 0

(222) TABLE-US-00009 TABLE 8 −1 17 243 134 152 155 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 144 −1 −1 −1 254 −1 85 −1 4 −1 −1 249 −1 70 −1 185 −1 −1 −1 −1 −1 161 −1 171 4 167 — −1 −1 −1 0 243 −1 58 181 215 −1 −1 −1 −2 — −1 4 −1 6 −1 −1 234 −1 −1 −1 195 162 81 −1 −1 −1 −1 −1 54 −1 −1 −1 241 251 −1 139 112 4 −1 −1 −1 — −1 −1 −1 249 −1 −1 −1 −1 −1 228 −1 −1 252 −1 184 21 −1 −1 −1 −1 −1 105 −1 5 75 14 −1 −1 −1 −1 −1 246 −1 −1 88 −1 −1 −1 −1 180 175 225 −1 22 −I −1 −1 −1 −1 −1 −1 −I −1 −1 246 −1 14 127 61 −1 −1 −1 −1 −1 −1 4 −1 4 160 245 −1 −1 −1 4 −1 −1 247 −1 −1 70 174 −1 −1 −1 −1 −1 231 −1 −1 −1 99 −1 −1 144 −1 −1 56 −1 −1 193 −1 −2 32 12 24 −1 −1 −1 −1 −1 251 205 −1 −1 −1 4 −1 −1 −1 105 −1 −1 28 −1 255 −1 −1 −1 −1 −1 −1 131 −1 252 134 245 −1 250 205 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 155 −1 −1 −1 70 231 −1 −1 −1 −1 −1 35 −1 123 −1 −1 1 0 −1 −1 −1 −1 −1 −I −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −I −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −I −1 −1 −1 −1 −1 −1 −1 −I −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −I −1 −1 −1 −1 1 0 −1 −I −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −I −1 0

(223) TABLE-US-00010 TABLE 9 4 221 32 251 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 187 255 31 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 239 −1 −1 −1 3 243 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 134 −1 61 −1 −1 −1 247 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 121 243 197 −1 −1 −1 −1 −1 0 −1 −1 −1 4 134 123 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 121 121 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 255 −1 223 −1 253 130 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 17 243 134 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 144 −1 −1 −1 254 −1 85 −1 −1 −1 −1 −1 −1 −1 −1 185 −1 −1 −1 −1 −1 161 −1 −1 −1 −1 −1 −1 −1 −1 −1 248 −1 58 181 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 234 −1 −1 −1 195 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 241 251 −1 139 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 228 −1 −1 252 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 5 75 14 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 180 175 225 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 246 −1 14 127 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 245 −1 −1 −1 4 −1 −1 247 −1 −1 −1 −1 −1 −1 −1 −1 −1 231 −1 −1 −1 99 249 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 32 12 24 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 105 −1 −1 28 −1 255 −1 −1 −1 −1 −1 −1 −1 −1 252 134 245 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 155 −1 −1 −1 70 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0

(224) In Table 6, Table 7, Table 8, and Table 9, all of the column permutations of the parity check matrices may be regarded as the same parity check matrix.

(225) More specifically, the exponents of the 28.sup.th column in Table 6 may be changed from [1 0−1 1].sup.T to [0 Y−1 0].sup.T, as illustrated in Table 10. Y may be any integer, (Z−1).

(226) TABLE-US-00011 TABLE 10 234 32 12 24 195 162 81 237 44 251 205 172 141 10 194 −1 241 251 105 139 112 28 22 255 227 68 31 0 182 177 131 162 252 134 245 228 250 205 252 204 184 21 94 249 10 45 68 105 155 5 75 14 70 231 227 26 101 246 161 35 88 123 232 32 71 27 −1 210 105 0 −1 147 78 153 178 84 0 0 −1 −1 −1 169 61 −1 211 100 92 132 −1 174 181 −1 Y 0 0 −1 99 −1 91 44 88 −1 101 72 47 −1 48 79 −1  −1 0 0 0 184 16 192 −1 161 80 −1 0 168 −1 128 0 −1 −1 0

(227) More specifically, the exponents of the 24.sup.th column in Table 7 may be changed from [1−1−1−1−1 0−1−1 1].sup.T to[0−1−1−1−1 Y−1−10].sup.T, and the exponents of the 28.sup.th column in Table 7 may be changed from [−1−1−1 1 1−1−1−1] to [−1−1−1 0 0−1−1−1].sup.T as illustrated in Table 11. Y may be any integer, (Z−1).

(228) TABLE-US-00012 TABLE 11 −1 180 175 225 −1 22 −1 −1 −1 153 −1 −1 86 188 −1 147 246 −1 14 127 61 −1 −1 −1 −1 50 13 −1 65 159 −1 160 245 −1 −1 −1 4 −1 152 247 108 −1 70 174 −1 −1 83 −1 −1 231 −1 −1 −1 99 249 54 144 −1 −1 56 −1 −1 193 −1 234 32 12 24 195 162 81 237 −1 −1 205 −1 −1 −1 −1 −1 241 251 103 139 112 28 22 255 −1 −1 −1 −1 −1 −1 131 −1 252 134 245 228 250 205 252 204 184 21 −1 −1 −1 −1 −1 105 155 5 75 14 70 231 227 26 −1 −1 −1 35 88 123 −1 −1 158 −1 203 −1 218 −1 68 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 141 4 −1 75 −1 −1 0 0 −1 −1 −1 −1 −1 −1 77 −1 55 −1 207 −1 103 −1 −1 0 0 −1 −1 −1 −1 120 26 92 −1 −1 168 −1 106 −1 −1 −1 0 0 −1 −1 −1 −1 27 −1 210 −1 −1 −1 147 Y −1 −1 −1 0 0 −1 −1 −1 −1 61 −1 211 100 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 101 −1 −1 −1 −1 −1 −1 −1 0 0 0 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 0

(229) More specifically, the exponents of the 16.sup.th column and 24.sup.th column in Table 8 may be changed, as illustrated in Table 12. Y may be any integer, (Z−1).

(230) TABLE-US-00013 TABLE 12 −17 17 243 134 152 155 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 144 −1 −1 −1 254 −1 85 −1 −1 −1 −1 249 −1 70 −1 185 −1 −1 −1 −1 −1 161 −1 171 −1 167 −1 −1 −1 −1 0 248 −1 58 181 215 −1 −1 −1 −1 −1 −1 −1 −1 6 −1 −1 234 −1 −1 −1 195 162 81 −1 −1 −1 −1 −1 54 −1 −1 −1 241 251 −1 139 112 −1 −1 −1 −1 −1 −1 −1 −1 249 −1 −1 −1 −1 −1 228 −1 −1 252 −1 184 21 −1 −1 −1 −1 −1 105 −1 5 75 14 −1 −1 −1 −1 −1 246 −1 −1 88 −1 −1 −1 −1 180 175 225 −1 22 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 246 −1 14 127 61 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 160 245 −1 −1 −1 4 −1 −1 247 −1 −1 70 174 −1 −1 −1 −1 −1 231 −1 −1 −1 99 −1 −1 144 −1 −1 56 −1 −1 193 −1 −1 32 12 24 −1 −1 −1 −1 −1 251 205 −1 −1 −1 −1 −1 −1 −1 105 −1 −1 28 −1 255 −1 −1 −1 −1 −1 −1 131 −1 252 134 245 −1 250 205 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 155 −1 −1 −1 70 231 −1 −1 −1 −1 −1 35 −1 123 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 Y −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0

(231) More specifically, the exponents of the 16.sup.th column and 24.sup.th column in Table 9 may be changed, as illustrated in Table 13. Y may be any integer, (Z−1).

(232) TABLE-US-00014 TABLE 13 4 221 32 251 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 187 255 35 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 239 −1 −1 −1 2 243 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 134 −1 61 −1 −1 −1 247 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 121 243 197 −1 −1 −1 −1 −1 0 −1 −1 −1 4 134 123 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 121 121 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 255 −1 223 −1 253 130 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 17 243 134 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 144 −1 −1 −1 254 −1 85 −1 −1 −1 −1 −1 −1 −1 −1 185 −1 −1 −1 −1 −1 161 −1 −1 −1 −1 −1 −1 −1 −1 −1 248 −1 58 181 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 234 −1 −1 −1 195 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 241 251 −1 139 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 228 −1 −1 252 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 5 75 14 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 180 175 225 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 246 −1 14 127 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 245 −1 −1 −1 4 −1 −1 247 −1 −1 −1 −1 −1 −1 −1 −1 −1 231 −1 −1 −1 99 249 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 32 12 24 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 105 −1 −1 28 −1 255 −1 −1 −1 −1 −1 −1 −1 −1 252 134 245 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 155 −1 −1 −1 70 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 1 −1 −1 −1 −1 −1 −1 −1 0 −1 −1 −1 −1 −1 −1 −1 1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 1 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0

(233) Table 6, Table 7, Table 8, and Table 9 represent parity check matrices for LDPC codes with code rates of 7/8, 3/4, 1/2, and 1/4, respectively. The size of a circulant permutation matrix of each parity check matrix, Z is an integer ranging from 1 to Z.sub.max. A set of {Z.sub.0, Z.sub.1, . . . , Z.sub.1} may be defined by selecting 1 values from among the integers from 1 to Z.sub.max. For example, {Z.sub.0, Z.sub.1, . . . , Z.sub.1}={2.sup.0, 2.sup.1, . . . , 2.sup.1}. In the set, if i<j, Z.sub.i<Z.sub.j, Z.sub.1≥Z.sub.max.

(234) For Z.sub.1>Z.sub.max, if a circulant matrix size of a parity check matrix is Z (1≤Z≤Z.sub.max), the exponent of a circulant matrix in an i.sup.th row block and a j.sup.th column block is determined by Equation 42.

(235) $\mathrm{Equation}42$$a_{i,j}\left(Z\right)=\{\begin{array}{c}{a}_{i,j}\left(Z_{l-1}\right)\mathrm{if}{a}_{i,j}\left(Z_{l-1}\right)\le 0\\ \mathrm{mod}\left(a_{i,j}\left(Z_{l-1}\right),Z_k\right)\mathrm{for}{Z}_k\le Z<Z_{k+1},0\le k<l,\mathrm{if}{a}_{i,j}\left(Z_{l-1}\right)>0\end{array}$

(236) In Equation 42, mod(x,y)=x mod y, representing the remainder of dividing x by y.

(237) Specifically, for Z.sub.0≤Z≤Z.sub.1, if a.sub.i,j(Z.sub.1-1) is −1 or 0, a.sub.i,j(Z) is a.sub.i,j(Z.sub.1-1), and if a.sub.i,j(Z.sub.1-1) is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j(Z.sub.1-1), Z.sub.0).

(238) For example, Z.sub.max=192, 1=8, and {Z.sub.0, Z.sub.1, . . . , Z.sub.8}={2.sup.0, 2.sup.1, . . . , 2.sup.8}.

(239) $\mathrm{Equation}43$$a_{i,j}\left(Z\right)=\{\begin{array}{c}{a}_{i,j}\left(2^7\right)\mathrm{if}{a}_{i,j}\left(2^7\right)\le 0\\ \mathrm{mod}\left(a_{i,j}\left(Z_{l-1}\right),2^k\right)\mathrm{for}{2}^k\le Z<2^{k+1},0\le k<l,\mathrm{if}{a}_{i,j}\left(2^7\right)>0\end{array}{a}_{i,j}\left(z\right)=\{\begin{array}{c}{a}_{i,j}\mathrm{if}{a}_{i,j}\le 0\\ \mathrm{mod}\left(a_{i,j},2^k\right)\mathrm{for}{2}^k\le z<2^{k+1},0\le k<7,\mathrm{if}{a}_{i,j}>0\end{array}$

(240) If Z.sub.1=Z.sub.max, for example, Z.sub.max=256, 1=8, and {Z.sub.0, Z.sub.1, . . . , Z.sub.8}={2.sup.0, 2.sup.1, 2.sup.8}. If the size of a circulant permutation matrix in a parity check matrix is Z (1<Z<Z.sub.max), the exponent a.sub.i,j(Z) of a circulant matrix in an i.sup.th row block and a j.sup.th column block is determined by Equation 44.

(241) $\mathrm{Equation}44$$a_{i,j}\left(Z\right)=\{\begin{array}{c}{a}_{i,j}\left(Z_l\right)\mathrm{if}{a}_{i,j}\left(Z_l\right)\le 0\\ \mathrm{mod}\left(a_{i,j}\left(Z_l\right),Z_k\right)\mathrm{for}{Z}_k\le Z<Z_{k+1},0\le k<l,\mathrm{if}{a}_{i,j}\left(Z_l\right)>0\end{array}$

(242) In Equation 44, mod(x, y)=x mod y, representing the remainder of dividing x by y.

(243) Specifically, for Z.sub.0≤Z<Z.sub.1, if a.sub.i,j(Z.sub.1-1) is −1 or 0, a.sub.i,j(Z) is a.sub.i,j(Z.sub.1-1), and if a.sub.i,j(Z.sub.1-1) is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j(Z.sub.1-1), Z.sub.0).

(244) Specifically, for Z.sub.1≤Z<Z.sub.2, if a.sub.i,j(Z.sub.1-1) is −1 or 0, a.sub.i,j(Z) is a.sub.i,j(Z.sub.1-1), and if a.sub.i,j(Z.sub.1-1) is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j, 2.sup.1).

(245) Specifically, for 2.sup.2≤Z<2.sup.3, if a.sub.i,j is −1 or 0, a.sub.i,j(Z) is a.sub.i,j, and if a.sub.i,j is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j, 2.sup.2).

(246) Specifically, for 2.sup.7≤Z<2.sup.8, if a.sub.i,j is −1 or 0, a.sub.i,j(Z) is a.sub.i,j, and if a.sub.i,j is larger than 0, a.sub.i,j(Z) is mod(a.sub.i,j, 2.sup.7).

(247) Various parameters may be available for the parity check matrix, for example, as listed in Table 14 or Table 15.

(248) TABLE-US-00015 TABLE 14 ID Code Rate N.sub.ldpc_b K.sub.ldpc_b N.sub.parity_b 0 8/9 37 32  5 1 2/3 37 24 13 2 4/9 37 16 21

(249) TABLE-US-00016 TABLE 15 ID Code Rate N.sub.ldpc_b K.sub.ldpc_b N.sub.parity_b 3 8/9 36 32 4 4 2/3 36 24 12 5 4/9 36 16 20 6 1/3 96 32 64

(250) Various embodiments of parity check matrices corresponding to the parameters listed in Table 14 and table 15 are illustrated in Table 1] to Table 3. Table 1 to Table 3 describe the exponent matrix of each parity check matrix (a small empty block represents a Z×Z zero matrix). For convenience of design, the numbers of columns in mother matrices are equally 36. Code rates of 8/9, 2/3, and 4/9 are set respectively for Table 1 to Table 3. For lifting, Z is set to 12, 24, 36, 48, 60, 72, 84, and 96, which means support of a total of 8 lengths.

(251) For Z=96, Z being the size of a circulant permutation matrix which is a submatrix in Equation 3 (L×L=Z*Z), Table 16 to Table 18 list the exponents of circulant permutation matrices, a.sub.i,j (0≤i<N.sub.ldpc−K.sub.ldpc, 0≤j<N.sub.ldpc). If the circulant permutation matrix size, Z is equal to or less than 96, the exponents of a parity check matrix, a.sub.i,j(Z.sub.k) is determined by Equation 45.
a.sub.i,j(Z.sub.k)≡a.sub.i,j mod Z.sub.k
Z.sub.k=12.Math.k,(k=1,2, . . . ,8)  Equation 45

(252) TABLE-US-00017 TABLE 16 50 47 35 49 24 13 85 30 58 84 93 44 86 65 89 57 60 15 33 48 26 3 59 11 33 19 67 0 27 61 26 23 55 13 40 20 27 76 41 24 85 54 29 28 73 16 30 92 81 61 5 95 21 45 20 73 23 87 73 33 16 26 75 42 61 63 25 86 71 8 25 20 21 8 55 67 79 34 86 3 28 44 29 1 0 83 78 77 76 5 91 65 35 33 41 12 0 0 71 15 71 85 89 84 11 8 71 50 0 0 0 67 95 52 35 42 70 93 63 61 63 1 0

(253) TABLE-US-00018 TABLE 17 29 86 48 36 34 14 52 54 34 78 3 10 24 9 13 29 34 60 9 94 75 58 83 62 21 68 14 42 48 67 30 65 66 94 17 77 45 88 10 10 3 57 45 8 49 31 38 36 44 45 58 6 3 25 76 8 35 57 64 44 53 94 77 94 55 86 84 39 2 73 41 54 71 63 83 37 27 85 39 42 58 40 9 3 89 68 80 22 36 54 49 43 13 62 41 83 43 72 61 22 20 1 52 81 76 60 27 89 64 1 37 28 1 0 0 0 17 53 0 0 0 0 82 0 0 31 0 0 0 0 0 91 89 0 0 69 95 0 0 52 22 16 0 0 50 93 40 0 0 1 0

(254) TABLE-US-00019 TABLE 18 50 39 22 49 43 1 0 23 86 39 82 85 0 28 85 32 45 29 63 29 56 0 93 13 80 68 68 88 88 44 89 33 91 53 86 42 40 89 60 85 55 58 82 37 82 91 9 36 46 48 14 72 17 71 16 21 78 0 45 33 39 61 4 75 28 46 93 13 93 92 31 16 42 74 45 52 53 65 76 91 55 34 78 34 41 48 27 72 83 24 53 2 54 40 7 73 87 20 54 7 14 60 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

(255) Other embodiments of parity check matrices are illustrated in Table 19, Table 20, and Table 21. Table 19 to Table 21 represent the exponent matrix of each parity check matrix. For convenience of design, the numbers of columns in mother matrices are equally 37. Code rates of 32/37, 24/37, and 16/37 are set respectively for Table 19 to Table 21. For lifting, Z is set to 12, 24, 36, 48, 60, 72, 84, and 96, which means support of a total of 8 lengths.

(256) TABLE-US-00020 TABLE 19 43 15 3 66 59 47 39 34 86 95 37 13 32 82 24 80 36 62 65 43 44 93 21 90 45 43 24 25 72 62 30 20 36 51 11 33 59 43 29 27 61 50 15 16 24 62 81 51 39 86 4 36 46 0 27 72 0 89 86 70 49 64 30 64 81 25 39 56 62 18 77 33 41 1 0 75 57 33 67 10 46 26 36 60 0 0 4 95 31 13 76 93 7 42 2 0 0 0 77 34 72 24 50 52 76 0 0 0 64 42 34 33 11 64 89 1 0

(257) TABLE-US-00021 TABLE 20 39 65 34 37 38 39 36 42 28 95 26 32 13 13 29 13 36 82 48 81 92 86 89 92 71 88 65 17 17 77 93 87 23 78 50 19 55 10 86 87 55 81 32 77 80 52 9 58 25 87 82 0 84 32 53 24 91 56 81 75 61 58 40 48 61 84 95 31 31 50 93 20 7 49 41 77 51 37 57 75 62 23 46 45 29 16 35 41 85 36 60 77 27 64 90 24 1 0 0 93 0 0 93 0 0 94 48 0 0 25 75 0 0 50 0 0 88 24 0 0 0 0 0 85 44 0 0 74 0 0 28 0 0 48 0 0 1 0

(258) TABLE-US-00022 TABLE 21 50 51 94 93 38 1 0 23 37 62 69 39 0 0 90 19 28 0 93 19 75 37 23 32 47 25 41 10 89 81 41 83 36 81 3 21 72 48 7 92 14 58 49 86 57 89 32 90 22 44 86 75 59 11 0 24 7 53 32 89 3 12 62 79 41 85 70 5 55 81 68 16 69 74 5 52 39 7 4 21 33 41 14 88 58 27 93 80 19 60 24 50 82 3 82 45 49 16 54 56 7 50 3 81 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

(259) In the case where LDPC encoding is performed using the parity check matrices illustrated in Table 19 to Table 21, if information word bits corresponding to the first column block in a partial matrix corresponding to an information word are punctured, prior to transmission, the code rates of Table 19 to Table 21 are finally 8/9, 2/3, and 4/9, respectively, which are the same as the code rates of Table 16 to Table 18. Since an LDPC code has improved performance through appropriate puncturing, LDPC encoding may be performed using Table 19 to Table 21 for performance improvement.

(260) FIGS. 13A and 13B illustrate a parity check matrix with ID=6 and R=1/3 in Table 15 according to various embodiments of the present disclosure.

(261) Referring to FIGS. 13A and 13B, the exponent matrix of the parity check matrix is illustrated. A small empty block represents a Z×Z zero matrix. For lifting, Z is set to 12, 24, 36, 48, 60, 72, 84, and 96, which means support of a total of 8 lengths. For reference, the 37.sup.th to last column blocks illustrated in FIGS. 13A and 13B are characterized by a degree of 1. For convenience of description, the column blocks are partially omitted in the tables. Column blocks with a degree of 1 include identity matrices.

(262) Since the parity check matrix to which single parity check codes are concatenated is easily extended, it is advantageous in applying an incremental redundancy (IR) scheme. The IR scheme is very important to support hybrid automatic repeat request (HARQ). Therefore, an IR scheme with excellent performance increases the efficiency of an HARQ system. As LDPC codes based on the parity check matrices are transmitted by generating a new parity using a part extended to the single parity check codes, an efficient IR scheme with excellent performance may be applied.

(263) Regarding the parity check matrix illustrated in FIGS. 13A and 13B, a partial matrix with the top four row blocks by 36 column blocks of the parity check matrix is identical to the parity check matrix of Table 35. For example, it is noted that the parity check matrix illustrated in FIGS. 13A and 13B is extended from the parity check matrix of Table 35 by concatenating a plurality of single parity check codes to the parity check matrix of Table 35.

(264) Another embodiment of a parity check matrix designed according to the design method of the present disclosure is illustrated in FIGS. 14A and 14B.

(265) FIGS. 14A and 15A illustrate exponent matrices of parity check matrices according to various embodiments of the present disclosure.

(266) The parity check matrix illustrated in FIG. 14A is divided into parts 1410, 1420, 1430, and 1440. FIGS. 14B to 14E are enlarged views of the parts 1410, 1420, 1430, and 1440. Similarly, parts denoted by 1510, 1520, 1530, and 1540 in FIG. 15A are illustrated respectively in 15B, 154C, 154D, and 154E. The diagonal elements of the diagonal matrices illustrated in FIGS. 14E and 15E are filled with zeroes.

(267) FIGS. 15B, 154C, 154D, and 15E are enlarged views of the parts 1510, 1520, 1530, and 1540 divided from the parity check matrix of FIG. 15A according to various embodiments of the present disclosure.

(268) Referring to FIGS. 14A and 15A, a small empty block represents a Z×Z zero matrix, and the exponent matrices are designed in consideration of Equation 8 to Equation 15.

(269) For reference, all of the 37.sup.th to last column blocks 1420 and 1440 illustrated in FIG. 14A and the 39.sup.th to last column blocks 1520 and 1540 illustrated in FIG. 15A have a degree of 1. For convenience of description, the column blocks with a degree of 1 include identity matrices, for convenience of description.

(270) Regarding the parity check matrix of FIG. 14A, the partial matrix 1410 including the top 4 row blocks by 36 column blocks of the whole parity check matrix does not have a column block with a degree of 1. For example, it may be noted that the parity check matrix of FIG. 14A is extended by concatenating a plurality of single parity check codes to a small QC-LDPC code corresponding to the partial matrix 1410.

(271) Regarding the parity check matrix of FIG. 15A, the partial matrix 1510 including the top 6 row blocks by 38 column blocks of the whole parity check matrix does not have a column block of a degree of 1. For example, it may be noted that the parity check matrix of FIG. 15A is extended by concatenating a plurality of single parity check codes to a small QC-LDPC code corresponding to the partial matrix 1510.

(272) The parity check matrix of FIG. 15A is extended to support R=32/38 to R=32/98. If the parity check matrix is continuously extended by use of a plurality of single parity check codes, a low code rate may be supported readily.

(273) FIGS. 16A, 16B, 16C, and 16D illustrate a parity check matrix (an exponent matrix) designed in consideration of lifting according to various embodiments of the present disclosure.

(274) Referring to FIG. 16A, a low code rate may be supported by concatenating a single parity check code 1610 illustrated in FIGS. 16B and 16C, and a single parity check code 1620 in FIG. 16D to the parity check matrix of FIG. 15A. In FIGS. 16B, 16C, and 16D, the number of rows is 64 and thus up to R=32/162 may be supported with the parity check matrix of FIG. 16A. For reference, reference numerals 1630 and 1640 denote zero matrices in FIG. 16A. For reference, FIG. 16C is connected to FIG. 16B, and reference numeral 160 of FIG. 16A denotes a combination of FIGS. 16B and 16C. For reference, FIG. 16D illustrates the extended parity check matrix shown as rotated to the right at 90 degrees.

(275) Since a parity check matrix to which single parity check codes are concatenated is easily extended, it is advantageous in applying an IR scheme. The IR scheme is very important to support HARQ. Therefore, an IR scheme with excellent performance increases the efficiency of an HARQ system. As LDPC codes based on the foregoing parity check matrices are transmitted by generating a new parity using a part extended to the single parity check codes, an efficient IR scheme with excellent performance may be applied.

(276) While parity check matrices of various lengths, that is, QC-LDPC codes may be generated by applying lifting proposed by the present disclosure to exponent matrices designed according to the designing method proposed by the present disclosure, appropriate application of shortening or puncturing may enable application of an LDPC encoding scheme supporting various information word lengths and code rates. In other words, if lifting, shortening, or puncturing is appropriately applied to the exponent matrix of FIG. 14A or FIG. 15A, IR or HARQ are readily supported, thereby increasing system flexibility.

(277) A method for designing an LDPC code suitable for using the lifting method of the present disclosure will be described below.

(278) In general, a QC-LDPC code has a special cycle property according to the characteristics of the mother matrix and exponent matrix of a parity check matrix. In the following cited reference [Myung2005], a couple of examples in which a cycle property is determined according to a mother matrix and an exponent matrix are described.

(279) Reference [Myung2005] S. Myung, K. Yang, and J. Kim, “Quasi-Cyclic LDPC Codes for Fast Encoding,” IEEE Transactions on Information Theory. vol. 51, No. 8, pp. 2894-2901, August 2005.

(280) The cycle property of a QC-LDPC code disclosed in [Myung2005] will be described briefly.

(281) To describe the cycle property of the simplest QC-LDPC code, four circulant permutation matrices with a 4-cycle in a mother matrix are assumed, as in Equation 46. The size of each circulant permutation matrix is assumed to be Z×Z.

(282) $\begin{array}{cc}\left[\begin{array}{ccc}{P}^{a_1}& \mathrm{.Math.}& P^{a_2}\\ \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ P^{a_4}& \mathrm{.Math.}& P^{a_S}\end{array}\right]& \mathrm{Equation}46\end{array}$

(283) According to [Myung2005], if there is a minimum positive integer r satisfying Equation 47, a cycle of length 4r exists on the Tanner graph of a parity check matrix corresponding to Equation 46.
r.Math.(a.sub.1−a.sub.2+a.sub.3−a.sub.4)≡0(mod Z).  Equation 47

(284) FIGS. 17A and 17B illustrate a cycle property of a quasi-cyclic LDPC (QC-LDPC) code according to various embodiments of the present disclosure.

(285) Referring to FIG. 17A, for example, if Z=6, a.sub.1=a.sub.2=0, and a.sub.3=a.sub.4=1, a.sub.1−a.sub.2+a.sub.3−a.sub.4=0. Thus, a 4-cycle is readily derived on the Tanner graph.

(286) Referring to FIG. 17B, if Z=6, a.sub.1=a.sub.2=0, a.sub.3=3, and a.sub.4=1, r.Math.(a.sub.1−a.sub.2+a.sub.3−a.sub.4) ≡3.Math.2≡0 (mod 6). Thus, a 12-cycle is readily derived on the Tanner graph.

(287) In this manner, the cycle property of a QC-LDPC code may be defined from the relationship between the exponents of QC permutation matrices of the parity check matrix.

(288) Because the lifting method of the present disclosure may cause use of the same exponent matrix for different Z values in some cases, an exponent matrix should be selected carefully. For example, even though the same a.sub.1=a.sub.2=0, a.sub.3=3, and a.sub.4=1 are used in Equation 46, if Z=4, r.Math.(a.sub.1−a.sub.2+a.sub.3−a.sub.4) ≡2.Math.2≡0 (mod 4), resulting in an 8-cycle. For example, if the same exponent matrix is used in consideration of different Z values, a change in cycle property should be considered.

(289) However, it is very difficult to select an exponent matrix satisfying a cycle property by calculating all r values by modulo-Z in Equation 47, while changing the exponent of a QC permutation matrix from many cycles in a mother matrix. In this context, the present disclosure proposes a method for fast determining an exponent matrix in a simple manner, as follows.

(290) For this purpose, if a circulant permutation matrix size is Z×Z in Equation 46, an extended Tanner graph with 8(Z−1)+2 variable nodes and 8(Z−1)+2 check nodes corresponding to Equation 46 will be described with reference to FIG. 18.

(291) In general, one Z×Z QC matrix corresponds to Z variable nodes and Z check notes on a Tanner graph. Therefore, QC permutation matrices with a 4-cycle in a mother matrix as described in Equation 46 correspond to 2Z variable nodes and 2Z check nodes. However, since variable and check nodes corresponding to one QC-permutation matrix are extended by 4(Z−1)+1 nodes ranging from the −2(Z−1).sup.th to 2(Z−1).sup.th nodes, the extended Tanner graph of FIG. 18 includes 8(Z−1)+2 variable nodes and 8(Z−1)+2 check nodes.

(292) For convenience of description, it is assumed that a cycle starts from a 0.sup.th check node of check node group 1 on the extended Tanner graph. A cycle property is determined for the circulant permutation matrices of Equation 46 according to the exponent of each circulant permutation matrix, as illustrated in FIG. 18. If (a.sub.1−a.sub.2+a.sub.3−a.sub.4)=0, the circulant permutation matrices form a 4-cycle as indicated by dotted lines in FIG. 18. Otherwise, a cycle larger than the 4-cycle may be achieved.

(293) A method for designing parity check matrices (or exponent matrices) for QC-LDPC codes with the same exponent matrix without a 4-cycle for Z, Z+1, Z+2, . . . , Z+m (m>1) for convenience of description will be described in brief. An extended Tanner graph for the largest Z value, Z+m is considered. For example, the extended Tanner graph includes 8(Z+m−1)+2 variable nodes and 8(Z+m−1)+2 check nodes, and covers all extended Tanner graphs for Z, Z+1, . . . , Z+m−1. If the exponents a.sub.1, a.sub.2, a.sub.3, and a.sub.4 are changed while checking whether−Z<(a.sub.1−a.sub.2+a.sub.3−a.sub.4)<Z is satisfied for all circulant permutation matrix combinations, such as Equation 46, for Z, Z+1, Z+2, Z+3, . . . , Z+m, a design without a 4-cycle is possible without the need for performing a modulo operation or calculating r for Z, Z+1, Z+2, Z+3, . . . , by Equation 47. For example, it may be concluded that the use of an extended Tanner graph obviates the need for performing a modulo operation or calculating r for all of Z, Z+1, . . . , Z+m, and facilitates design of a parity check matrix without a short cycle.

(294) The above method for designing a parity check matrix for an LDPC code may be applied to any of Z.sub.1, Z.sub.2, . . . , Z.sub.max to be supported. Once only one exponent matrix (or sequence) corresponding to Z.sub.max is stored in a system, all exponent matrices (or sequences) corresponding to Z.sub.1, Z.sub.2, . . . , Z.sub.max may be generated and applied to LDPC encoding.

(295) Now, a detailed description will be given of the rate matcher 340 of the transmitter 300.

(296) Input bits of the rate matcher 340 are output bits of the LDPC encoder 330, C=(i.sub.0, i.sub.1, i.sub.2, . . . , i.sub.Kldpc-1, p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.Nldpc-Kldpc-1). i.sub.k,(0≤k<K.sub.ldpc) represents the input bits of the LDPC encoder 330, and p.sub.k(0≤k<N.sub.ldpc-Kldpc) represents LDPC parity bits. The rate matcher 340 includes the interleaver 341 and the puncturer/repeater/zero remover 342.

(297) FIGS. 9A and 9B illustrate structures of interleavers according to various embodiments of the present disclosure.

(298) Referring to FIG. 9A, the interleaver 341 interleaves i.sub.k. As illustrated in FIG. 9B, the interleaver 341 may interleave both i and p.

(299) p.sub.k is interleaved in the following interleaving method.

(300) Step 1) The number of columns in a block interleaver is set to C.sub.subblock.sup.LDPC=N.sub.parity_b based on N.sub.parity_b of Table 3.

(301) Step 2) The number of rows in the block interleaver is set to the size Z of a circulant permutation matrix of a parity check matrix.

(302) Step 3) Parity bits of an LDPC code, p.sub.k (k=0, 1, . . . , N.sub.parity-1) are input, in an ascending order of row indexes starting from the first row of the first column, as in Equation 48.

(303) $\mathrm{Equation}48\left[\begin{array}{ccccc}{p}_0& p_{\left(R_{\mathrm{subblock}}^{\mathrm{LDPC}}\right)}& p_{\left(2{\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}\right)}& \mathrm{.Math.}& P_{\left(C_{\mathrm{subblock}}^{\mathrm{TC}}-1\right){\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}}\\ p_1& p_{\left(R_{\mathrm{subblock}}^{\mathrm{LDPC}}+1\right)}& p_{\left(2{\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}+1\right)}& \mathrm{.Math.}& p_{\left(C_{\mathrm{subblock}}^{\mathrm{TC}}-1\right){\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}+1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ p_{\left(R_{\mathrm{subblock}}^{\mathrm{LDPC}}-1\right)}& p_{\left(2{\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}-1\right)}& p_{\left(3{\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}-1\right)}& \mathrm{.Math.}& p_{\left(C_{\mathrm{subblock}}^{\mathrm{TC}}\right){\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}-1}\end{array}\right]$
For p.sub.x:

(304) Step 4) p.sub.k arranged as illustrated in Equation 48 is interleaved column-wise based on an inter-column permutation pattern so that the positions of columns may be changed. Table 22 illustrates inter-column permutation patterns for a sub-block interleaver.

(305) TABLE-US-00023 TABLE 22 Number of Code columns Inter-column permutation pattern Rate C.sub.subblock.sup.LDPC < P(0), P(1), . . . , P (C.sub.subblock.sup.LDPC −1) > 1/4 24 < 0, 2, 4, 8, 10, 12, 14, 16, 18, 20, 22, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 > 1/2 16 < 0, 2, 4, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15 > 3/4 8 < 0, 2, 4, 1, 3, 5, 7 > 7/8 4 < 0, 2, 1, 3>

(306) The parameters of Table 22 may be changed according to a system, for example, to Table 23.

(307) TABLE-US-00024 TABLE 23 Number of Code columns Inter-column permutation pattern ID Rate C.sub.subblock.sup.LDPC  P(0), P(1), . . . , P(C.sub.subblock.sup.LDPC −1)    0 8/9 5 0 4 2 3 1 1 2/3 13 0 12 8 4 10 6 2 11 9 8 5 3 1 2 4/9 21 0 20 16 12 8 4 18 14 10 6 2 19 17 15 13 11 9 7 5 3 1 3 8/9 4 0 2 3 1 4 2/3 12 0 8 4 10 6 2 11 9 7 5 3 1 5 4/9 20 0 16 12 8 4 18 14 10 6 2 19 17 15 13 11 9 7 5 3 1 6 1/3 64 0 2 3 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 67 68 69 60 61 62 63

(308) In the above inter-column permutation patterns, the columns are arranged in a reverse order of puncturing. For example, for an ID of 5, the bits of the first column out of 20 columns are first punctured. If consecutive parity blocks are punctured, it may affect performance. Therefore, the bits of the first column are first punctured, and the bits of the third column are punctured in the second place. In this manner, the order of puncturing odd-numbered columns ending with the 19.sup.th column is determined and an order of puncturing even-numbered blocks is determined in such a manner that the punctured even-numbered blocks may be spaced from each other by four blocks. A similar method is used for other code rates.

(309) For example, P(j) of <P(j)>.sub.j∈{0, 1, . . . , C.sub.subblock.sub.LDPC.sub.−1} in Table 22 represents a pre-permutation index of a j.sup.th permuted column. After the column-wise permutation, the inter-column permutated (R.sub.subblock.sup.LDPC×C.sub.subblock.sup.LDPC) matrix may be represented as Equation 49.

(310) $\mathrm{Equation}49\left[\begin{array}{ccccc}{y}_0& y_{\left(R_{\mathrm{subblock}}^{\mathrm{LDPC}}\right)}& y_{\left(2{\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}\right)}& \mathrm{.Math.}& y_{\left(C_{\mathrm{subblock}}^{\mathrm{TC}}-1\right){\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}}\\ y_1& y_{\left(R_{\mathrm{subblock}}^{\mathrm{LDPC}}+1\right)}& y_{\left(2{\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}+1\right)}& \mathrm{.Math.}& y_{\left(C_{\mathrm{subblock}}^{\mathrm{TC}}-1\right){\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}+1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ y_{\left(R_{\mathrm{subblock}}^{\mathrm{LDPC}}-1\right)}& y_{\left(2{\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}-1\right)}& y_{\left(3{\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}-1\right)}& \mathrm{.Math.}& y_{\left(C_{\mathrm{subblock}}^{\mathrm{TC}}\right){\mathrm{XR}}_{\mathrm{subblock}}^{\mathrm{LDPC}}-1}\end{array}\right]$

(311) Step 5) The values of the inter-column permutated (R.sub.subblock.sup.LDPC×C.sub.subblock.sup.LDPC) matrix described in Equation 49 are output row by row, starting from the first row of the first column, while increasing the indexes of columns.

(312) The resulting subblock interleaved bits are (v.sub.0, v.sub.1, v.sub.2, . . . , v.sub.Nparity−1).

(313) The interleaver 341 of the rate matcher 340 receives C=(i.sub.0, i.sub.1, i.sub.2, . . . , i.sub.Kldpc-1, p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.Nldpc-Kldpc-1), and block-interleaves p.sub.k, thus outputting C′=(i.sub.0, i.sub.1, i.sub.2, . . . , i.sub.Kldpc-1, v.sub.0, v.sub.1, v.sub.2, . . . , v.sub.Nldpc-Kldpc-1).

(314) The parity bits are interleaved on a Z bit basis, Z being the circulant permutation matrix size of the parity check matrix. Thus, the input bits of the LDPC code i.sub.0, i.sub.1, i.sub.2, . . . , i.sub.Kldpc-1 and the parity bits of the LDPC code p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.Nldpc-Kldpc-1 may be interleaved on a Z bit basis, Z being the circulant permutation matrix size of the parity check matrix.

(315) Because similar encoding or decoding characteristics may result on a Z bit basis, Z being the circulant permutation matrix size of the parity check matrix, Z unit-based interleaving may optimize encoding or decoding performance.

(316) The output bits of the interleaver 341 in the rate matcher 340 of the transmitter 330, i.sub.0, i.sub.1, i.sub.2, . . . , i.sub.Kldpc-1, v.sub.0, v.sub.1, v.sub.2, . . . , v.sub.Nldpc-Kldpc-1 are input to the puncturer/repeater/zero remover 342.

(317) The puncturer/repeater/zero remover 342 performs puncturing/repetition according to the size of bits to be transmitted and removes the <Null> bits input by the zero padder 320.

(318) The puncturing refers to non-transmission of some bits except for the <Null> bits among the outputs bits of the interleaver 341, i.sub.0, i.sub.1, i.sub.2, . . . , i.sub.Kldpc-1, v.sub.0, v.sub.1, v.sub.2, . . . , v.sub.Nldpc-Kldpc-1, and the repetition refers to repeating some bits except for the <Null> bits among the outputs bits of the interleaver 341, i.sub.0, i.sub.1, i.sub.2, . . . , i.sub.Kldpc-1, v.sub.0, v.sub.1, v.sub.2, . . . , v.sub.Nldpc-Kldpc-1.

(319) The number of codeword bits to be transmitted may be controlled by puncturing and repetition.

(320) More specifically, the puncturer/repeater/zero remover 342 operates in the following manner.

(321) K.sub.w=N.sub.ldpc bits are input to a circular buffer.
W.sub.k=i.sub.k for k=0, . . . ,K.sub.ldpc
W.sub.k.sub.ldpc+k=V.sub.k for k=0, . . . ,N.sub.parity

(322) If E bits are transmitted at this transmission, for HARQ, transmission bits are determined as follows. A maximum allowed transmission number is M.sub.DL_HARQ.

(323) Set k.sub.0=0, k.sub.0=i.Math.E−1 for 1≤i≤M.sub.DL_HARQ (if incremental redundancy is used),

(324) set k.sub.0=0 for 1≤i≤M.sub.DL_HARQ (if chase combining is used)

(325) Set k=0 and j=0

(326) while {k<E}
if w.sub.(K.sub.0.sub.+j)mod N.sub.cb≠<NULL>
e.sub.k=w.sub.(k.sub.0.sub.+j)mod N.sub.cb
k=k+1

(327) end if

(328) j=j+1

(329) end while

(330) Further, if E bits are transmitted at this transmission, for HARQ, transmission bits are determined as follows.

(331) The indexes k.sub.0 of initially transmitted bits may be determined by Equation 50.

(332) $\begin{array}{cc}{k}_0=\left(.Math.\frac{N_{\mathrm{cb}}}{4}.Math..Math.{\mathrm{rv}}_{\mathrm{idx}}+Z\right)& \mathrm{Equation}50\end{array}$

(333) In Equation 50, Z is the circulant permutation matrix size of a parity check matrix, rv.sub.idx is an integer selected from {0, 1, 2, 3}, and N.sub.cb is the number of bits that can be processed in a receiver, in consideration of a buffer size in the receiver. For example, N.sub.cb may be equal to or less than the number of codeword bits, N.sub.ldpc. Considering Z in Equation 50 implies that transmission bits are selected from among information bits except for Z bits.

(334) Thus, if bits except for Z bits are transmitted, Equation 50 may be expressed as Equation 51.

(335) $\begin{array}{cc}{k}_0=\left(.Math.\frac{N_{\mathrm{cb}}}{4}.Math..Math.{\mathrm{rv}}_{\mathrm{idx}}\right)& \mathrm{Equation}51\end{array}$

(336) In the above case, rv.sub.idx is an integer and four values of {0, 1, 2, 3} are available as rv.sub.idx. If rv.sub.idx is {0, 1, 2, . . . , M−1}, the indexes k.sub.0 of initially transmitted bits may be determined by Equation 52.

(337) $\begin{array}{cc}{k}_0=\left(.Math.\frac{N_{\mathrm{cb}}}{M}.Math..Math.{\mathrm{rv}}_{\mathrm{idx}}\right)& \mathrm{Equation}52\end{array}$

(338) Bits are transmitted by dividing the number Ncb of bits storable in the buffer of the receiver by M. In order not to transmit X bits at rv0, k0 may be determined by Equation 53.

(339) 0$\begin{array}{cc}{k}_0=\left(.Math.\frac{N_{\mathrm{cb}}}{M}.Math..Math.{\mathrm{rv}}_{\mathrm{idx}}+X\right)& \mathrm{Equation}53\end{array}$

(340) Set k=0 and j=0

(341) while {k<E}
if w.sub.(k.sub.0.sub.+j)mod N.sub.cb.sub.≠<NULL>
e.sub.k=w.sub.(k.sub.0.sub.+j)mod N.sub.cb
k=k+1

(342) end if

(343) j=j+1

(344) end while

(345) Transmission bits e.sub.k (0≤k<E) are selected from among the interleaved bits w.sub.k (0≤k<N.sub.cb) except for <NULL> values. If E is larger than N.sub.cb, transmission bits are repeatedly selected.

(346) The modulator 350 modulates a bit stream received from the rate matcher 340 and transmits the modulated bit stream to a receiver (for example, the receiver 400 in FIG. 4).

(347) Specifically, the modulator 350 may demultiplex bits received from the rate matcher 340 and map the demultiplexed bits to a constellation.

(348) For example, the modulator 350 converts serial bits received from the rate matcher 340 to parallel bits, and form cells each including a predetermined number of bits. The number of bits per cell may be equal to the number of bits that form a modulation symbol mapped to the constellation.

(349) Subsequently, the modulator 350 may map the demultiplexed bits to the constellation. For example, the modulator 350 may modulate the demultiplexed bits in any of various modulation schemes, such as QPSK, 16-QAM, 64-QAM, 256-QAM, 1024-QAM, and 4096-QAM, and map the modulated bits to constellation points. In this case, since cells are formed with the demultiplexed bits, each cell including the number of bits per modulation symbol, each cell may be mapped sequentially to a constellation point.

(350) The modulator 350 may modulate the signals mapped to the constellation and transmit the modulated signals to the receiver 400. For example, the modulator 350 may map the signals mapped to the constellation to an OFDM frame and transmit the OFDM frame on an allocated channel to the receiver 400.

(351) Meanwhile, the transmitter 300 may pre-store various parameters used in encoding, interleaving, and modulation. Parameters for encoding may be information about a code rate, codeword length, and parity check matrix of an LDPC code. An interleaving parameter may be information about an interleaving rule, and a modulation parameter may be information about a modulation scheme. A puncturing parameter may be information about a puncturing length. A repetition parameter may be information about a repetition length. The information about a parity check matrix may be information about the exponents of circulant permutation matrices given by Equation 3 and Equation 4, if a parity check matrix of the present disclosure is used.

(352) In this case, the components of the transmitter 300 may operate using these parameters.

(353) While not shown, the transmitter 300 may further include a controller (not shown) for controlling operations of the transmitter 300.

(354) FIG. 6 is a block diagram of an encoder according to an embodiment of the present disclosure.

(355) Referring to FIG. 6, an encoder 600 may perform LDPC encoding and includes the LDPC encoder 610. The LDPC encoder 610 may generate an LDPC codeword by LDPC-encoding input bits based on a parity check matrix.

(356) The parity check matrix may have the same structure as a parity check matrix described by Equation 3 and Equation 4.

(357) In this case, the LDPC encoder 610 may perform LDPC encoding using a parity check matrix defined differently according to a code rate (i.e., the code rate of an LDPC code).

(358) For example, if the code rate is 7/8, the LDPC encoder 610 may perform LDPC encoding using a parity check matrix as defined by Table 6. If the code rate is 3/4, the LDPC encoder 610 may perform LDPC encoding using a parity check matrix as defined by Table 5. If the code rate is 1/2, the LDPC encoder 610 may perform LDPC encoding using a parity check matrix as defined by Table 8. If the code rate is 1/4, the LDPC encoder 610 may perform LDPC encoding using a parity check matrix as defined by Table 7.

(359) A specific method for performing LDPC encoding has been described below, and thus will not be described herein to avoid redundancy.

(360) The encoder 600 may further include a memory (not shown) for pre-storing information about the code rates, codeword lengths, and parity check matrices of LDPC codes, and the LDPC encoder 610 may perform LDPC encoding using this information. Information about a parity check matrix may include information about the exponents of circulant matrices, when a parity check matrix proposed by the present disclosure is used.

(361) Now, a detailed description will be given of an operation of a receiver with reference to FIG. 4.

(362) The demodulator 410 demodulates a signal received from the transmitter 300. Specifically, the demodulator 410, which is a counterpart of the modulator 350 of the transmitter 300, may generate values corresponding to bits transmitted by the transmitter 300 by demodulating a signal received from the transmitter 300.

(363) For this purpose, the receiver 400 may pre-store information about modulation schemes according to modes of the transmitter 300. Accordingly, the demodulator 410 may generate values corresponding to LDPC codeword bits by demodulating a signal received from the transmitter 300 according to a mode.

(364) The values corresponding to the bits transmitted by the transmitter 300 may be LLRs.

(365) Specifically, the LLR of a bit transmitted by the transmitter 300 may be a value obtained by performing a log operation on a ratio between the probability of 0 and the probability of 1 for the bit. The LLR may also be the value of the bit itself. The LLR may be a representative value of a range to which the probability of the transmitted bit being 0 or 1 belongs.

(366) The demodulator 410 may include a multiplexer (MUX) for multiplexing the LLRs. Specifically, the MUX is a counterpart of a bit DEMUX (not shown) of the transmitter 300 and may perform an operation corresponding to the bit DEMUX.

(367) For this purpose, the receiver 400 may pre-store information about parameters used for demultiplexing and block interleaving of the transmitter 300. Accordingly, the MUX may multiplex LLRs corresponding to a cell word on a bit basis by performing the demultiplexing and block interleaving of the bit DEMUX in a reverse order.

(368) The rate dematcher 420 may insert LLRs in LLRs received from the demodulator 410. In this case, the rate dematcher 420 may insert predetermined LLRs in the LLRs received from the demodulator 410.

(369) Specifically, the rate dematcher 420, which is a counterpart of the rate matcher 340 of the transmitter 300, may perform operations corresponding to the interleaver 341 and the puncturer/repeater/zero remove 342.

(370) The rate dematcher 420 deinterleaves in correspondence with the interleaver 341 of the transmitter 300. LLRs corresponding to zero bits may be inserted at the positions of the zero bits added to the LDPC codeword in the output values of the deinterleaver 424 by the LLR inserter 422. In this case, the LLRs corresponding to the padded zero bits, that is, shortened zero bits may be ∞ or −∞. However, ∞ or −∞ is a theoretical value, and may be the maximum or minimum value of the LLRs used in the receiver 400.

(371) For this purpose, the receiver 400 may pre-store information about a parameter used for padding zero bits in the transmitter 300. Therefore, the rate dematcher 420 may determine the positions of padded zero bits in the LDPC code and insert LLRs corresponding to shortened zero bits at the positions.

(372) The LLR inserter 422 of the rate dematcher 420 may insert LLRs corresponding to puncturing bits at the positions of the puncturing bits in the LDPC codeword. In this case, the LLRs corresponding to the punctured bits may be zeroes.

(373) For this purpose, the receiver 400 may pre-store information about a parameter used for puncturing in the transmitter 300. Therefore, the LLR inserter 422 may insert corresponding LLRs at the positions of punctured parity bits.

(374) The LLR combiner 423 may combine, that is, sum the LLRs output from the LL inserter 422 and the demodulator 410. Specifically, the LLR combiner 423, which is a counterpart of the puncturer/repeater/zero remover 342 of the transmitter 300, may perform an operation corresponding to the repeater 342. First, the LLR combiner 423 may combine LLRs corresponding to repeated bits with other LLRs. The other LLRs may be LLRs of bits based on which the repeated bits are generated, that is, LLRs of LDPC parity bits selected for repetition.

(375) For example, as described before, the transmitter 300 selects bits from among LDPC parity bits, repeats the selected bits between LDPC information word bits and LDPC parity bits, and transmits them to the receiver 400.

(376) Therefore, the LLRs of the LDPC parity bits may include the LLRs of repeated LDPC parity bits and the LLRs of non-repeated LDPC parity bits, that is, LDPC parity bits generated by encoding. Accordingly, the LLR combiner 423 may combine the LLRs of the same LDPC parity bits.

(377) For this purpose, the receiver 400 may pre-store information about a parameter used for repetition in the transmitter 300. Thus, the LLR combiner 423 may determine the LLRs of repeated LDPC parity bits and combine the LLRs with the LLRs of LDPC parity bits based on which the repeated LDPC parity bits are produced.

(378) Further, the LLR combiner 423 may combine the LLRs of retransmission bits or IR bits with other LLRs. The other LLRs may be the LLRs of bits selected for generation of LDPC codeword bits, based on which the retransmission bits or the IR bits are generated.

(379) For example, as described before, if a negative acknowledgement (NACK) is generated in HARQ, the transmitter 300 may transmit all or part of codeword bits to the receiver 400.

(380) Therefore, the LLR combiner 423 may combine the LLRs of the retransmission bits or the IR bits with the LLRs of LDPC codeword bits received in a previous frame.

(381) For this purpose, the receiver 400 may pre-store information about a parameter used for generation of the retransmission bits or the IR bits in the transmitter 300. Thus, the LLR combiner 423 may determine the LLRs of the retransmission bits or the IR bits and combine the LLRs with the LLRs of LDPC parity bits based on which the retransmission bits or the IR bits are produced.

(382) The deinterleaver 424 may deinterleave LLRs received from the LLR combiner 423.

(383) Specifically, the deinterleaver 424, which is a counterpart of the interleaver 341 of the transmitter 300, may perform an operation corresponding to the interleaver 341.

(384) For this purpose, the receive 400 may pre-store information about a parameter used for interleaving in the transmitter 300. Thus, the deinterleaver 424 may deinterleave the LLRs of the LDPC codeword bits by reversely performing interleaving performed in the interleaver 341.

(385) The LDPC decoder 4300 may perform LDPC decoding based on the LLRs received from the rate dematcher 420.

(386) Specifically, the LDPC decoder 430, which is a counterpart of the LDPC encoder 330 of the transmitter 300, may perform an operation corresponding to the LDPC encoder 330.

(387) For this purpose, the receiver 400 may pre-store information about a parameter used for LDPC encoding according to a mode in the transmitter 300. Thus, the LDPC decoder 430 may perform LDPC decoding based on the LLRs received from the rate dematcher 420 according to a mode.

(388) For example, the LDPC decoder 430 may perform LDPC decoding based on the LLRs received from the rate dematcher 420 in an iterative decoding scheme based on a sum-product algorithm, and output error-corrected bits according to the LDPC decoding.

(389) The zero remover 440 may remove zero bits in the bits received from the LDPC decoder 430.

(390) Specifically, the zero remover 440, which is a counterpart of the zero padder 320 in the transmitter 300, may perform an operation corresponding to the zero padder 320.

(391) For this purpose, the receiver 400 may pre-store information about a parameter used for padding zero bits in the transmitter 300. Thus, the zero remover 440 may remove zero bits padded by the zero padder 320 in the bits received from the LDPC decoder 430.

(392) The desegmenter 450, which is a counterpart of the segmenter 310 in the transmitter 300, may perform an operation corresponding to the segmenter 310.

(393) For this purpose, the receiver 400 may pre-store information about a parameter used for segmentation in the transmitter 300. Thus, the desegmenter 450 may recover pre-segmentation bits by combining segments of the bits received from the zero remover 440, that is, input bits of a variable length.

(394) FIG. 10 is a block diagram of a decoder according to an embodiment of the present disclosure.

(395) Referring to FIG. 10, a decoder 1000 may include an LDPC decoder 1010. The LDPC decoder 1010 performs LDPC decoding on an LDPC codeword based on a parity check matrix.

(396) For example, the LDPC decoder 1010 may generate information word bits by performing LDPC decoding by passing the LLRs of LDPC codeword bits in an iterative decoding algorithm.

(397) An LLR is a channel value corresponding to an LDPC codeword bit, which may be expressed in various manners.

(398) For example, an LLR may be represented as a value obtained by performing a log operation on the ratio between the probability of 0 and the probability of 1 for a bit transmitted on a channel by a transmitter. The LLR may be a bit value decided by hard decision, and may be a representative value of a range to which the probability of the transmitted bit being 0 or 1 belongs.

(399) In this case, the transmitter may generate an LDPC codeword using the LDPC encoder 610 illustrated in FIG. 6.

(400) The parity check matrix used for the LDPC decoding may have the same structure as a parity check matrix described by Equation 3 and Equation 4.

(401) In this case, the LDPC decoder 1010 may perform LDPC decoding using a parity check matrix defined differently according to a code rate (i.e., the code rate of an LDPC code).

(402) For example, if the code rate is 7/8, the LDPC decoder 1010 may perform LDPC decoding using a parity check matrix as defined by Table 6. If the code rate is 3/4, the LDPC decoder 1010 may perform LDPC decoding using a parity check matrix as defined by Table 5. If the code rate is 1/2, the LDPC decoder 1010 may perform LDPC decoding using a parity check matrix as defined Table 8. If the code rate is 1/4, the LDPC decoder 1010 may perform LDPC decoding a parity check matrix as defined by [Table 7].

(403) FIG. 11 is a block diagram of an LDPC decoder according to an embodiment of the present disclosure.

(404) Referring to FIG. 11, the LDPC decoder 1010 may perform LDPC decoding using an iterative decoding algorithm. In this case, the LDPC decoder 1010 may be configured in the structure illustrated in FIG. 11. The detailed structure illustrated in FIG. 11 in that the iterative decoding algorithm is well known.

(405) Referring to FIG. 11, a decoder 1100 includes an input processor 1101, a memory 1102, a variable node operator 1104, a controller 1106, a check node operator 1108, and an output processor 1110.

(406) The input processor 1101 stores input values. Specifically, the input processor 1101 may store LLRs of a signal received on a radio channel.

(407) The controller 1104 determines the number of values input to the variable node operator 1104, an address of the memory 1102, the number of values input to the check node operator 1108, an address of the memory 1102, and so on based on a block size (that is, a codeword length) of the signal received on the radio channel, and a parity check matrix corresponding to a code rate.

(408) According to an embodiment of the present disclosure, decoding may be performed based on a parity check matrix with the indexes of rows having is in column 0 of an i.sup.th column group as defined in Table 6 to Table 9.

(409) The memory 1102 stores input data and output data of the variable node operator 1104 and the check node operator 1108.

(410) The variable node operator 1104 receives data from the memory 1102 according to the information about the addresses and number of input data, received from the controller 1106, and performs variable node computation. The variable node operator 1104 stores variable node computation results in the memory 1102 based on the information about the addresses and number of output data, received from the controller 1106. The variable node operator 1104 also provides the variable node calculation results to the output processor 1110 based on data received from the input processor 1101 and the memory 1102. Herein, the variable node computation has been described before with reference to FIG. 5.

(411) The check node operator 1108 receives data from the memory 1102 according to information about the addresses and number of input data, received from the controller 1106, and performs check node computation. The check node operator 1108 stores variable node computation results in the memory 1102 based on information about the addresses and number of output data, received from the controller 1106. Herein, the check node computation has been described before with reference to FIG. 5.

(412) The output processor 1110 hard-decides whether information word bits of a codeword transmitted by the transmitter are 0s or 1s based on data received from the variable node operator 1104, and outputs the hard-decision values. The output values of the output processor 1110 are final decoded values. In this case, the hard decision may be made based on the sum of all message values input to one variable node (an initial message value and all message values received from check nodes).

(413) Meanwhile, the decoder 1100 may further include a memory (not shown) for pre-storing information about code rates, codeword lengths, and parity check matrices of LDPC codes, and the LDPC decoder 1010 may perform LDPC decoding using this information. However, the information may be received from the transmitter.

(414) FIG. 12 illustrates a structure of a transport block according to an embodiment of the present disclosure.

(415) Referring to FIG. 12, <Null> bits may be added to make the lengths of segments equal.

(416) <Null> bits may be added to match the information length of an LDPC code. Since the same exponent matrix is produced for different Z values in the present disclosure, the increase of implementation complexity of a parity check matrix may be overcome. Even though encoding is performed using different encoders for Z=a and Z=b, the same result may be achieved.

(417) FIG. 19 is a flowchart illustrating an LDPC encoding method based on a sequence according to an embodiment of the present disclosure.

(418) Referring to FIG. 19, the transmitter/receiver reads a stored exponent matrix (or sequence) corresponding to a parity check matrix in operation 1910. In operation 1920, the transmitter/receiver determines a block size Z corresponding to the size of a circulant permutation matrix included in a parity check matrix. The parity-check matrices in operations 1910 and 1920 may be the same or differ from each other. The sequence of operations 1910 and 1920 may be changed.

(419) Subsequently, the transmitter may determine an appropriate integer based on the determined block size in a predetermined method in operation 1930. Operation 1930 may be performed in various methods. For example, if the determined block size is Z, the integer may be determined by k=└ log.sub.2 Z┘. In another embodiment of the present disclosure, the transmitter may determine a range or set including the determined block size, when needed. A representative integer of the range or set may be the integer determined in operation 1930. Although the representative integer may be a minimum value, a maximum value, an intermediate value, or an average value of the values of the range or set, any value is available as far as the value is an integer uniquely representing the range or set.

(420) In operation 1940, the transmitter converts the sequence read in operation 1910 based on the integer determined in operation 1930. In operation 1950, the transmitter performs LDPC encoding based on the converted sequence.

(421) The sequence conversion in operations 1930 and 1940 is characterized by conversion to the same sequence for at least two different block sizes among block sizes determined in operation 1920. This characteristic may be obtained in various manners. In an embodiment, if a rule of determining the same integer is applied to the at least two different block sizes in operation 1930, the characteristic may be easily obtained.

(422) FIG. 20 is a block diagram of a transmitter for performing LDPC encoding based on a sequence according to an embodiment of the present disclosure.

(423) Referring to FIG. 20, the transmitter includes an LDPC encoder 2010, a memory 2020, a controller 2030, and a converter 2040.

(424) The memory 2020 reads a sequence corresponding to a parity check matrix.

(425) The controller 2030 provides information about block sizes to the converter 2040 and controls conversion of the sequence.

(426) Even though the converter 2040 receives the information about different block sizes from the controller 2030, there is always a case in which the same sequence is out for the input of a sequence from the memory 202.

(427) The LDPC encoder 2010 performs LDPC encoding based on the converted sequence.

(428) Obviously, the receiver may include a controller for receiving an LDPC codeword produced by LDPC encoding based on a sequence converted in the manner illustrated in FIGS. 19 and 20, and decoding the received codeword.

(429) As is apparent from the foregoing description, the present disclosure can support an LDPC code of a variable length and a variable code rate.

(430) While the present disclosure has been shown and described with reference to various embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present disclosure as defined by the appended claims and their equivalents.