Method and apparatus for transmitting and receiving data in a communication system

Abstract

Methods and apparatuses are provided for transmitting signaling information by a transmitting apparatus in a broadcasting system. A controller generates a codeword by encoding information bits of the signaling information. The codeword includes the information bits and parity bits. The controller punctures one or more of the parity bits to generate a punctured codeword. The controller generates a plurality of frames. The plurality of frames include a first frame including at least a part of the punctured codeword and a second frame including at least one additional parity bit for the signaling information. A transmitter transmits the plurality of frames. The at least a part of the punctured codeword is included in a preamble part of the first frame and the at least one additional parity bit is included in a preamble part of the second frame.

Claims

1. A method for transmitting signaling information by a transmitting apparatus in a broadcasting system, the method comprising: generating, by a controller, a codeword by encoding information bits of the signaling information, the codeword including the information bits and parity bits; puncturing, by the controller, one or more of the parity bits to generate a punctured codeword; generating, by the controller, a plurality of frames, wherein the plurality of frames comprise a first frame including at least a part of the punctured codeword and a second frame including at least one additional parity bit for the signaling information, and transmitting, by a transmitter, the plurality of frames, wherein the at least a part of the punctured codeword is included in a signaling information part of the first frame and the at least one additional parity bit is included in a signaling information part of the second frame.

2. The method of claim 1, wherein the second frame precedes the first frame.

3. The method of claim 1, further comprising interleaving, by the controller, the parity bits according to a predetermined order.

4. The method of claim 3, further comprising: grouping, by the controller, the parity bits of the codeword into a plurality of groups, wherein the parity bits of the plurality of groups are group-wise interleaved according to the predetermined order.

5. The method of claim 4, wherein the predetermined order is a reverse order of a puncturing pattern.

6. The method of claim 4, wherein a group of the plurality of groups has a size of 360.

7. The method of claim 3, wherein puncturing, by the controller, the one or more of the interleaved parity bits starts at an end of the interleaved parity bits.

8. The method of claim 1, wherein the additional parity bits are for obtaining the information word of the signaling information.

9. The method of claim 1, wherein the additional parity bits are selected from the punctured codeword.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

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

(2) FIG. 1 illustrates a parity check matrix of a length-8 LDPC code;

(3) FIG. 2 illustrates a Tanner graph corresponding to a parity check matrix of a length-8 LDPC code;

(4) FIG. 3 illustrates a parity check matrix of an LDPC code used in a DVB-T2 system;

(5) FIG. 4 illustrates a frame structure in a form for a DVB-T2/NGH system;

(6) FIG. 5 illustrates a frame structure based on Rule 3 according to an embodiment of the present invention;

(7) FIG. 6 illustrates parity bits included in Q.sub.ldpc groups according to an embodiment of the present invention;

(8) FIG. 7 illustrates a frame structure based on Rule 4 according to an embodiment of the present invention;

(9) FIGS. 8A to 8C illustrate frame structures based on Rule 5 according to an embodiment of the present invention;

(10) FIG. 9 illustrates a frame structure of a DVB-T2/NGH system according to an embodiment of the present invention;

(11) FIG. 10 illustrates a frame structure of a DVB-T2/NGH system according to another embodiment of the present invention;

(12) FIG. 11 illustrates a frame structure of a DVB-T2/NGH system according to another embodiment of the present invention;

(13) FIGS. 12A-12C, 13A-13C, and 14A-14D are diagrams illustrating methods of selecting additional parity bits according to different embodiments of the present invention;

(14) FIG. 15 is a block diagram illustrating a transmission and reception apparatus according to an embodiment of the present invention;

(15) FIG. 16 is a block diagram illustrating a transmission apparatus according to an embodiment of the present invention;

(16) FIG. 17 is a block diagram illustrating a reception apparatus according to an embodiment of the present invention;

(17) FIG. 18 is a block diagram illustrating a transmission apparatus according to an embodiment of the present invention;

(18) FIG. 19 is a block diagram illustrating a reception apparatus according to an embodiment of the present invention;

(19) FIG. 20 is a flowchart illustrating a transmission method according to an embodiment of the present invention;

(20) FIG. 21 is a flowchart illustrating a reception method according to an embodiment of the present invention;

(21) FIGS. 22A and 22B are diagrams illustrating various frame structures according to different embodiments of the present invention; and

(22) FIG. 23 is a diagram illustrating a method for selecting additional parity bits according to an embodiment of the present invention.

(23) Throughout the drawings, the same drawing reference numerals will be understood to refer to the same elements, features and structures.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

(24) Various embodiments of the present invention will be described in detail below with reference to the accompanying drawings. In the following description, specific details such as detailed configuration and components are provided merely to assist in an overall understanding of the described embodiments of the present invention. Therefore, it should be apparent to those skilled in the art that various changes and modifications of the embodiments described herein can be made without departing from the scope and spirit of the invention. In addition, descriptions of well-known functions and constructions are omitted for clarity and conciseness.

(25) Additionally, while detailed descriptions of the present invention will be made based on a DVB-T2 system and a DVB-NGH system, which are typical European digital broadcasting standards, it will be understood by those of ordinary skill in the art that the present invention is not limited to these systems. In addition, while the present invention will be described in conjunction with a method of transmitting signaling information, the present invention is not limited to transmission of the signaling information.

(26) The codeword described below include two parts, i.e., a first part, which is an information part including actual information words, and a second part, which is a parity part including additional information obtained by receiving and encoding information words. As described above, if needed, a codeword can be created from data by puncturing and shortening.

(27) For convenience of description, it is assumed herein that the term codeword refers to all of an information word and parity bits obtained by encoding the information word. That is, the parity bits include both non-punctured parity bits and punctured parity bits.

(28) If sufficient diversity gain cannot be obtained during transmission of the codeword, an additional diversity gain may be obtained by transmitting data on a plurality of frames.

(29) Method 1

(30) Information words are transmitted in a z-th frame, and additional parity bits are created based on information word and parity bits, which can be obtained by encoding information words. The additional parity bits are transmitted over s frames. Groups of additional parity bits transmitted in associated frames are represented by G(0), G(1), . . . , G(s1), and the numbers of bits in the groups are N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, . . . , N.sub.add.sub._.sub.parity.sub.s1. The additional parity bits are grouped according to specific rules.

(31) The term additional parity bits refers to parity bits that are transmitted on frames different from those of information words, separate from the parity bits that are transmitted on the same frames as those of the information words.

(32) As described above, a code is generated based on an (N.sub.ldpc, K.sub.ldpc) code. Accordingly, a puncturing pattern of parity bits, suitable for the code, can be calculated. However, a detailed description of a method for calculating a puncturing pattern will be omitted so as not to obscure the subject matter of the present invention.

(33) The term puncturing pattern of parity bits refers to an order of indexes of punctured parity bits. That is, if the number of punctured parity bits is N.sub.punc=2, then N.sub.punc=2 elements are sequentially selected in the puncturing pattern and parity bits having the selected values as their indexes are punctured. Assuming that a puncturing pattern set, or a puncturing order, is A={1, 5, 2, 6, 4, 0, 3, 7}, if the number of punctured parity bits is 2, then two indexes 1 and 5 are sequentially selected in the puncturing pattern set A. As a result, p.sub.1 and p.sub.5 are punctured from the parity bits p.sub.0, p.sub.1, p.sub.2, p.sub.3, p.sub.4, p.sub.5, p.sub.6, and p.sub.7, and the remaining parity bits p.sub.0, p.sub.2, p.sub.3, p.sub.4, p.sub.6, and p.sub.7 are selected as a parity part and transmitted.

(34) For the information word and parity bits, additional parity bits can be created using Rule 3, as described below.

(35) Rule 3

(36) Additional parity bits may be selected from among parity bits and information bits. An order of selecting additional parity bits from the parity bits is based on a puncturing order. In this case, either a normal order or a reverse order of the puncturing pattern may be used. Otherwise, additional parity bits are selected from information bits, and information bits capable of guaranteeing excellent performance are selected in order.

(37) Generally, bits concatenated in an order of a puncturing pattern are created to have a low correlation. That is, the order of the puncturing pattern is determined such that even though both of two concatenated bits suffer from deep fading and are not easily restored, the restoration may be easily achieved by using other bits. For example, when bits concatenated in a normal order or a reverse order of the puncturing pattern are mapped to the same groups and transmitted on the same frames, even though all the frames suffer from deep fading, the restoration may be easily achieved by other parity bits. Therefore, the restoration may be easily achieved by selecting additional parity bits in the normal order or the reverse order of the puncturing pattern as in Rule 3.

(38) In Rule 3, additional parity bits may be created by first determining an order of remaining bits, except for the punctured bits, and then selecting the punctured bits after selecting the non-punctured bits.

(39) In Rule 3, when additional parity bits are selected after the punctured bits are all selected, bits capable of guaranteeing excellent performance may be selected from among information bits and parity bits using a greedy algorithm. The greedy algorithm selects the best performance bits among the codeword bits when primarily selecting additional parity bits, and selects the best performance bits among the remaining bits, with the first selected bits fixed as previously selected bits, when secondarily selecting additional parity bits. The following should be considered in selecting high-performance bits.

(40) 1) Degrees of variable nodes corresponding to codeword bits

(41) 2) Minimum cycles of variable nodes corresponding to codeword bits

(42) 3) Bit Error Rate (BER) performance of codeword bits

(43) While two embodiments of selecting additional parity bits using the greedy algorithm will be described below, various other methods are also available.

(44) Additionally, the following descriptions assume that the numbers of elements in groups of additional parity bits are N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, . . . , N.sub.add.sub._.sub.parity.sub.s1, and a sum of these values is N.sub.total=N.sub.add.sub._.sub.parity.sub.0+ . . . +N.sub.add.sub._.sub.parity.sub.s1.

(45) Embodiment 1
N.sub.total=N.sub.add.sub._.sub.parity.sub.0+ . . . +N.sub.add.sub._.sub.parity.sub.s1<N.sub.ldpcK.sub.ldpc

(46) If a length of a parity part is greater than a sum of the numbers of elements in groups of additional parity bits, groups of additional parity bits are created based on parity bits of a codeword according to order of a puncturing pattern.

(47) FIG. 5 illustrates a frame structure based on Rule 3 according to an embodiment of the present invention.

(48) Referring to FIG. 5, a codeword includes an information part and a parity part. As an example, in FIG. 7, a length of the information part, after undergoing shortening, is 7 bits, I={i.sub.0, i.sub.1, . . . , i.sub.6}, the parity part is 8 bits in length, P={p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.7}, and a puncturing pattern set representing puncturing order is A={1, 5, 2, 6, 4, 0, 3, 7}.

(49) For N.sub.punc=2, s=3, and N.sub.add.sub._.sub.parity.sub.0=N.sub.add.sub._.sub.parity.sub.1=N.sub.add.sub._.sub.parity.sub.2=2 (where N.sub.punc is the number of punctured bits, s is the number of frames on which additional parity bits are transmitted, and N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, and N.sub.add.sub._.sub.parity.sub.2 are the numbers of additional parity bits transmitted on their associated frames), groups of additional parity bits are created as follows.

(50) Because the number of punctured bits is 2, p.sub.1 and p.sub.5 are punctured according to the puncturing pattern set A.

(51) Because elements included in groups of additional parity bits are determined from among the bits p.sub.0, p.sub.2, p.sub.3, p.sub.4, p.sub.6, and p.sub.7, not the punctured bits p.sub.1 and p.sub.5, according to the normal puncturing order, a first group is G(0)={p.sub.2, p.sub.6}, a second group is G(1)={p.sub.4, p.sub.0}, and a third group is G(2)={p.sub.3, p.sub.7}. The first group is transmitted on a (k+2)-th frame, the second group on a (k+1)-th frame, and the third group on a k-th frame.

(52) Conversely, if elements included the groups of the additional parity bits are determined from the bits, except for the punctured bits, according to the reverse puncturing order, a first group is G(0)={p.sub.7, p.sub.3}, a second group is G(1)={p.sub.0, p.sub.4}, and a third group is G(2)={p.sub.6, p.sub.2}. The first group is transmitted on a (k+2)-th frame, the second group on a (k+1)-th frame, and the third group on a k-th frame.

(53) While the determined groups are sequentially transmitted, the transmission order of the groups is subject to change.

(54) Embodiment 2
N.sub.total=N.sub.add.sub._.sub.parity.sub.0+ . . . +N.sub.add.sub._.sub.parity.sub.s1N.sub.ldpcK.sub.ldpc

(55) If a length of a parity part is less than or equal to a sum of the numbers of elements in groups of additional parity bits, groups of additional parity bits are created based on parity bits and information bits of a codeword.

(56) Again, a codeword includes an information part and a parity part. Using the same example as above, a length of the information part, after undergoing shortening, is 7 bits, I={i.sub.0, i.sub.1, . . . , i.sub.6}, the parity part is 8 bits in length, P={p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.7}, and a puncturing pattern set representing puncturing order is A={1, 5, 2, 6, 4, 0, 3, 7}.

(57) For N.sub.punc=2, s=3, and N.sub.add.sub._.sub.parity.sub.0=N.sub.add.sub._.sub.parity.sub.1=N.sub.add.sub._.sub.parity.sub.2=3 (where N.sub.punc is the number of punctured bits, s is the number of frames on which additional parity bits are transmitted, and N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, and N.sub.add.sub._.sub.parity.sub.2 are numbers of additional parity bits transmitted on their associated frames), groups of additional parity bits are created as follows.

(58) Because the number of punctured bits is 2, p.sub.1 and p.sub.5 are punctured according to the puncturing pattern set A.

(59) Because elements included groups of additional parity bits are determined according to the normal puncturing order, a first group is G(0)={p.sub.2, p.sub.6, p.sub.4}, a second group is G(1)={p.sub.0, p.sub.3, p.sub.7}, and a third group is G(2)={p.sub.1, p.sub.5, i.sub.0}. Notably, the third group includes the parity bits p.sub.1 and p.sub.5, which were previously punctured, and one bit i.sub.o from among the codeword bits. The first group is transmitted on a (k+2)-th frame, the second group on a (k+1)-th frame, and the third group on a k-th frame.

(60) Conversely, if the elements included in the groups of the additional parity bits are determined according to the reverse puncturing order, a first group is G(0)={p.sub.7, p.sub.3, p.sub.0}, a second group is G(1)={p.sub.4, p.sub.6, p.sub.2}, and a third group is G(2)={p.sub.5, p.sub.1, i.sub.0}. Likewise, the third group includes the parity bits p.sub.5 and p.sub.1, which were previously punctured, and one bit i.sub.0 among the codeword bits. The first group is transmitted on a (k+2)-th frame, the second group on a (k+1)-th frame, and the third group on a k-th frame.

(61) While the determined groups are sequentially transmitted, the transmission order of the groups is subject to change.

(62) A method for generating a plurality of groups of additional parity bits based on information bits and parity bits in accordance with Rule 3 will be described in more detail below.

(63) For the parity check matrix of an LDPC code illustrated in FIG. 3, having a codeword length of N.sub.ldpc and an information word length K.sub.ldpc, the parity bits can be represented as {p.sub.0, p.sub.1, . . . , p.sub.NldpcKldpc1} and Q.sub.ldpc groups of parity bits can be generated.

(64) FIG. 6 illustrates parity bits included in Q.sub.ldpc groups according to an embodiment of the present invention.

(65) An index group representing index values of parity bits included in a j-th group from among the Q.sub.ldpc groups can be expressed as shown in Equation (3) below.
I(j)={k|k mod Q.sub.ldpc=j, 0k<N.sub.ldpcK.sub.ldpc} for 0j<Q.sub.ldpc (3)

(66) Based on Equation (3), an index group of parity bits for a puncturing pattern representing the puncturing order can be calculated as shown in Equation (4) below.
A.sub.360j+i=I.sub.i(.sub.p(j)) for 0i<359, 0j<Q.sub.ldpc (4)

(67) That is, a (360j+i)-th element in a puncturing pattern set A, which indicates a puncturing order, is the same as an i-th element in an I((j)) index group. (j) for 0j<Q.sub.ldpc is defined as Table 1 below.

(68) TABLE-US-00001 TABLE 1 Order of parity group to be punctured, {.sub.P(j), 0 d j < Q.sub.ldpc = 25} Modulation .sub.P(0) .sub.P(1) .sub.P(2) .sub.P(3) .sub.P(4) .sub.P(5) .sub.P(6) .sub.P(7) .sub.P(8) .sub.P(9) .sub.P(10) .sub.P(11) .sub.P(12) and Code rate .sub.P(13) .sub.P(14) .sub.P(15) .sub.P(16) .sub.P(17) .sub.P(18) .sub.P(19) .sub.P(20) .sub.P(21) .sub.P(22) .sub.P(23) .sub.P(24) BPSK/ 1/2 6 4 18 9 13 8 15 20 5 17 2 24 10 QPSK 22 12 3 16 23 1 14 0 21 19 7 11 16-QAM 1/2 6 4 13 9 18 8 15 20 5 17 2 22 24 7 12 1 16 23 14 0 21 10 19 11 3 64-QAM 1/2 6 15 13 10 3 17 21 8 5 19 2 23 16 24 7 18 1 12 20 0 4 14 9 11 22

(69) Table 1 may change, e.g., according to system requirements.

(70) If the number of punctured bits is represented by N.sub.punc and the number of elements in a group l(for 0l<s) is represented by N.sub.add.sub._.sub.parity.sub.l, an index group of parity bits in a group l(for 1l<s) can be calculated using Equation (5) below.

(71) $\begin{array}{cc}C\left(l\right)=\left\{A_{N_{\mathrm{punc}}+N_{{\mathrm{add\_parity}}_0+\mathrm{.Math.}+N_{{\mathrm{add\_parity}}_{l-1}}}},\mathrm{.Math.},A_{N_{\mathrm{punc}}+N_{\mathrm{add}+{\mathrm{parity}}_0}+\mathrm{.Math.}+N_{{\mathrm{add\_parity}}_l}-1}\right\}C\left(l\right)=\left\{A_{N_{\mathrm{punc}+\left(N_{{\mathrm{group}}_0}+\mathrm{.Math.}+N_{{\mathrm{group}}_{l_1}}\right)}},A_{N_{\mathrm{punc}+\left(N_{{\mathrm{group}}_0}+\mathrm{.Math.}+N_{{\mathrm{group}}_{l_1}}+1\right)}},\mathrm{.Math.},A_{N_{\mathrm{punc}+\left(N_{{\mathrm{group}}_0}+N_{{\mathrm{group}}_1}-1\right)}}\right\}1l<s& \left(5\right)\end{array}$

(72) That is, N.sub.add.sub._.sub.parity.sub.l indexes of parity bits included in an l-th group of additional parity bits are sequentially selected, except for indexes corresponding to punctured parity bits in the puncturing pattern set A.

(73) Alternatively, indexes of parity bits included in a group of additional parity bits may be selected in a reverse order of the puncturing pattern. In this case, an index group of parity bits in a group l can be calculated using Equation (6) below.

(74) $\begin{array}{cc}C\left(0\right)=\left\{A_{N_{\mathrm{parity}}-1},A_{N_{\mathrm{parity}}-2},\mathrm{.Math.},A_{N_{\mathrm{parity}}-N_{{\mathrm{add\_parity}}_0}-1}\right\}C\left(l\right)=\left\{A_{N_{\mathrm{parity}}-\left(N_{{\mathrm{add\_parity}}_0}+\mathrm{.Math.}+N_{{\mathrm{add\_parity}}_{l-1}}\right)},A_{N_{\mathrm{parity}}-\left(N_{{\mathrm{add\_parity}}_0}+\mathrm{.Math.}+N_{{\mathrm{add\_parity}}_{l-1}}-1\right)},\mathrm{.Math.},A_{N_{\mathrm{parity}}-\left(N_{{\mathrm{add\_parity}}_0}+\mathrm{.Math.}+N_{{\mathrm{add\_parity}}_1}-1\right)}\right\}1l<s& \left(6\right)\end{array}$

(75) In Equation (6), N.sub.parity=N.sub.ldpcK.sub.ldpc represents the number of parity bits.

(76) That is, N.sub.add.sub._.sub.parity.sub.l indexes of parity bits included in an l-th group of additional parity bits are selected in reverse order in the puncturing pattern set A indicative of puncturing order, starting with the last bit.

(77) Based on the group of indexes calculated using Equation (5) or (6), elements in a group of parity bits transmitted over a plurality of frames can be expressed as shown in Equation (7) below.
G(l)={p.sub.k|kC(l)} for 0l<s (7)

(78) In Equation (7), p.sub.k represents a k-th parity bit in the parity check matrix. Using Equation (7), the parity bits having values belonging to an l-th group C(l) of indexes calculated in Equation (6), are included in an l-th group C(l) of additional parity bits.

(79) Accordingly, Equation (7) generates group satisfying Rule 3.

(80) Rule 4

(81) Additional parity bits are created based on parity bits and information bits by sequentially selecting parity bits and mapping them to groups G(0), G(1), . . . , G(s1) in order. As for the information bits, information bits more likely to provide better performance are sequentially selected.

(82) In creating additional parity bits according to Rule 4, an order of the additional parity bits to be created may also be determined from remaining bits, i.e., the non-punctured bits. However, after all the non-punctured bits are selected, the punctured bits may be selected.

(83) In Rule 4, if additional parity bits should be selected, even after the punctured parity and non-punctured bits are all selected, bits more likely to provide better performance may be selected from information bits and parity bits using the greedy algorithm. The greedy algorithm is provided to select the best performance bits among codeword bits when primarily selecting additional parity bits, and select the best performance bits among the remaining bits, with the first selected bits fixed as previously selected bits, when secondarily selecting additional parity bits. The following should be considered in selecting high-performance bits.

(84) 1) Degrees of variable nodes corresponding to codeword bits

(85) 2) Minimum cycles of variable nodes corresponding to codeword bits

(86) 3) Bit Error Rate (BER) performance of codeword bits

(87) In a parity check matrix with a parity part having a dual diagonal structure, because concatenated bits are connected to the same check nodes, there is a correlation between concatenated bits. Accordingly, it is preferable not to transmit the concatenated bits on the same channel. Thus, parity bits are mapped to different groups in sequence, in order to experience different channels.

(88) Embodiment 3

(89) FIG. 7 illustrates a frame structure based on Rule 4 according to an embodiment of the present invention.

(90) Referring to FIG. 7, a codeword includes an information part and a parity part. Using the same example as above, a length of the information part, after undergoing shortening, is 7 bits, I={i.sub.0, i.sub.1, . . . , i.sub.6}, the parity part is 8 bits in length, P={p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.7}, and a puncturing pattern set representing puncturing order is A={1, 5, 2, 6, 4, 0, 3, 7}.

(91) For N.sub.punc=2, s=3, and N.sub.add.sub._.sub.parity.sub.0=N.sub.add.sub._.sub.parity.sub.1=N.sub.add.sub._.sub.parity.sub.2=2 (where N.sub.punc is the number of punctured bits, s is the number of frames on which additional parity bits are transmitted, and N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, and N.sub.add.sub._.sub.parity.sub.2 are numbers of additional parity bits transmitted on their associated frames), groups of additional parity bits are created as described below. It is assumed that a parity check matrix corresponding to the parity part is a dual diagonal matrix in structure.

(92) Because the number of punctured bits is 2, p.sub.1 and p.sub.5 are punctured according to the puncturing pattern set A.

(93) Because parity bits are sequentially mapped to groups according to Rule 4, among the bits p.sub.0, p.sub.2, p.sub.3, p.sub.4, p.sub.6, and p.sub.7, i.e., the non-punctured parity bits, p.sub.0 is mapped to a first group, p.sub.2 to a second group, p.sub.3 to a third group, p.sub.4 to the first group, p.sub.6 to the second group, and p.sub.7 to the third group. As a result, the first group is G(0)={p.sub.0, p.sub.4}, the second group is G(1)={p.sub.2, p.sub.6}, and the third group is G(2)={p.sub.3, p.sub.7}. The first group is transmitted on a (k+2)-th frame, the second group on a (k+1)-th frame, and the third group on a k-th frame. While the determined groups are sequentially transmitted, transmission order of the groups is subject to change.

(94) Embodiment 4

(95) Again, a length of the information part, after undergoing shortening, is 7 bits, I={i.sub.0, i.sub.1, . . . , i.sub.6}, the parity part is 8 bits in length, P={p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.7}, and a puncturing pattern set representing puncturing order is A={1, 5, 2, 6, 4, 0, 3, 7}.

(96) For N.sub.punc2, s3, and N.sub.add.sub._.sub.parity.sub.0=N.sub.add.sub._.sub.parity.sub.1=N.sub.add.sub._.sub.parity.sub.2=3 (where N.sub.punc is the number of punctured bits, s is the number of frames on which additional parity bits are transmitted, and N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, and N.sub.add.sub._.sub.parity.sub.2 are numbers of additional parity bits transmitted on their associated frames), groups of additional parity bits are created as follows. It is assumed that a parity check matrix corresponding to the parity part is a dual diagonal matrix in structure.

(97) Because the number of punctured bits is 2, p.sub.1 and p.sub.5 are punctured according to the puncturing pattern set A.

(98) Because the number N.sub.add.sub._.sub.parity.sub.0+N.sub.add.sub._.sub.parity.sub.1+N.sub.add.sub._.sub.parity.sub.3=9 of additional parity bits forming groups is greater than the number of parity bits, i.e., 8, bits included in the last group are selected from the information bits. That is, a first group is G(0)={p.sub.0, p.sub.4, p.sub.1}, a second group is G(1)={p.sub.2, p.sub.6, p.sub.5}, and a third group is G(2)={p.sub.3, p.sub.7, i.sub.0}.

(99) The first group is transmitted on a (k+2)-th frame, the second group on a (k+1)-th frame, and the third group on a k-th frame. While the determined groups are sequentially transmitted, transmission order of the groups is subject to change.

(100) A method for generating additional parity bits in accordance with another embodiment of the present invention will be described below.

(101) By transmitting non-punctured parity bits and an information word on the same frame and transmitting additional parity bits on other frames to obtain an additional diversity gain, it is possible to obtain diversity gain while reducing the actual code rate.

(102) For convenience of description, it is assumed herein that the term codeword refers to all of an information word and parity bits obtained by encoding the information word. That is, the parity bits include both non-punctured parity bits and punctured parity bits.

(103) Method 2

(104) Non-punctured parity bits are transmitted on a z-th frame, which is the same frame as that of the information word, and additional parity bits obtained from information word and parity bits, which are included in groups G(0), G(1), . . . , G(s1), according to specific rules, are transmitted over s frames.

(105) The additional parity bits are bits that are transmitted on previous frames, instead of being transmitted on the same frame as that of the information words, aside from the parity bits that are transmitted on the same frames as those of the information words. G(0), G(1), . . . , G(s1) represent groups of additional parity bits.

(106) Rule 5

(107) Additional parity bits are selected from parity bits and information bits, and the parity bits that are not transmitted on the same frames as the information bits are first selected. The parity bits that are not transmitted on the same frames the information bits are punctured parity bits. When additional parity bits are selected from parity bits, an order of selection of the additional parity bits is determined according to a normal order or a reverse order of a puncturing pattern. As to the information bits, information bits that are more likely to have a better performance are sequentially selected.

(108) In creating additional parity bits according to Rule 5, parity bits that are not transmitted on the frames that information bits are transmitted, i.e., the punctured parity bits, are first selected as additional parity bits. After these parity bits that are all selected, information bits and parity bits from the codeword are selected as additional parity bits.

(109) In Rule 5, if additional parity bits should be selected, after all of the punctured parity bits are selected all, bits that are more likely to provide better performance may be selected from the information bits and the parity bits of the codeword using the greedy algorithm. As described above, the greedy algorithm is provided to select the best performance bits among codeword bits when primarily selecting additional parity bits, and select the best performance bits among the remaining bits, with the first selected bits fixed as previously selected bits, when secondarily selecting additional parity bits, and considers the following in selecting high-performance bits.

(110) 1) Degrees of variable nodes corresponding to codeword bits

(111) 2) Minimum cycles of variable nodes corresponding to codeword bits

(112) 3) BER performance of codeword bits

(113) Embodiment 5

(114) FIGS. 8A to 8C illustrate frame structures based on Rule 5 according to an embodiment of the present invention.

(115) Referring to FIG. 8A, a codeword includes an information part and a parity part. A length of the information part, after undergoing shortening, is 7 bits, I={i.sub.0, i.sub.1, . . . , i.sub.6}, the parity part is 8 bits in length, P={p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.7}, and a puncturing pattern set representing puncturing order is A={1, 5, 2, 6, 4, 0, 3, 7}.

(116) If the number of parity bits transmitted on the same frames as those of information bits is 5, for N.sub.punc=3, s=3, and N.sub.add.sub._.sub.parity.sub.0=N.sub.add.sub._.sub.parity.sub.1=N.sub.add.sub._.sub.parity.sub.2=2 (where N.sub.punc is the number of punctured bits, s is the number of frames on which additional parity bits are transmitted, and N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, and N.sub.add.sub._.sub.parity.sub.2 are the numbers of additional parity bits transmitted on their associated frames), groups of additional parity bits are created as described below.

(117) Because N.sub.punc=3, p.sub.1, p.sub.5, and p.sub.2 are punctured, and parity bits transmitted on the same frames as those of information bits are p.sub.0, p.sub.3, p.sub.4, p.sub.6, and p.sub.7.

(118) In mapping bits to groups in a puncturing order according to Rule 5, a first group G(0)={p.sub.1, p.sub.5} is created by selecting parity bits p1 and p.sub.5, which have first and second elements of 1 and 5 in the puncturing pattern as their index values. For a second group, a parity bit p.sub.2 having a third element of 2 in the puncturing pattern as its index is selected. Because all of the punctured parity bits are selected, the second group is created by selecting one of the information bits and the non-punctured parity bits. If a first information bit is selected, the second group is G(1)={p.sub.2, i.sub.0}. If i.sub.1 and i.sub.2 are selected from among information bits and non-punctured parity bits to create a third group, the third group is G(2)={i.sub.1, i.sub.2}. The first group is transmitted on a (k+2)-th frame, the second group on a (k+1)-th frame, and the third group on a k-th frame.

(119) Referring to FIG. 8B, if bits are mapped to groups in a reverse order of the puncturing pattern, a first group G(0)={p.sub.2, p.sub.5}, a second group G(1)={p.sub.1, i.sub.0}, and a third group G(2)={i.sub.1, i.sub.2} are created by selecting bits from among the punctured parity bits {p.sub.1, p.sub.5, p.sub.2} among elements in the puncturing pattern set A, starting with the last bit. The first group is transmitted on a (k+2)-th frame, the second group on a (k+1)-th frame, and the third group on a k-th frame.

(120) Referring to FIG. 8C, to facilitate easy selection of parity bits transmitted on frames, parity bits are sequentially transmitted in a reverse order of the puncturing pattern, after undergoing permutation. That is, because the puncturing pattern is A={1, 5, 2, 6, 4, 0, 3, 7}, parity bits are arranged as p.sub.7, p.sub.3, p.sub.0, p.sub.4, p.sub.6, p.sub.2, p.sub.5, and p.sub.1 in reverse order of the puncturing pattern, and parity bits transmitted on the same frames as those of the information bits are p.sub.7, p.sub.3, p.sub.0, p.sub.4, and p.sub.0, because five bits are sequentially selected from the arranged parity bits. Thus, for G(0), p.sub.2 and p.sub.5 are selected. For G(1), p.sub.1 is selected and one bit is selected from the information bits. For G(2), two bits are selected from the information bits according to the greedy algorithm.

(121) While the determined groups are sequentially transmitted, the transmission order of the groups is subject to change.

(122) Embodiment 6

(123) A length of the information part, after undergoing shortening, is 7 bits, I={i.sub.0, i.sub.1, . . . , i.sub.6}, the parity part is 8 bits in length, P={p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.7}, and a puncturing pattern set representing puncturing order is A={1, 5, 2, 6, 4, 0, 3, 7}.

(124) For N.sub.punc=3, s=3, and N.sub.add.sub._.sub.parity.sub.0=N.sub.add.sub._.sub.parity.sub.1=N.sub.add.sub._.sub.parity.sub.2=4 (where N.sub.punc is the number of punctured bits, s is the number of frames on which additional parity bits are transmitted, and N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, and N.sub.add.sub._.sub.parity.sub.2 are the numbers of additional parity bits transmitted on their associated frames), groups of additional parity bits are created as described below.

(125) Because N.sub.punc=3, p.sub.1, p.sub.5, and p.sub.2 are punctured, and p.sub.0, p.sub.3, p.sub.4, p.sub.6, and p.sub.7 are the parity bits transmitted on the same frames as those of information bits.

(126) By mapping the remaining parity bits, i.e., the punctured parity bits, to groups in puncturing order according to Rule 5, a first group is G(0)={p.sub.1, p.sub.5, p.sub.2, i.sub.0}, a second group is G(1)={i.sub.1, i.sub.2, i.sub.3 i.sub.4}, and a third group is G(2)={i.sub.5, i.sub.6, p.sub.6, p.sub.4}. In creating the third group G(2), because the parity bits are arranged as i.sub.1, i.sub.5, p.sub.2, p.sub.6, i.sub.4, i.sub.0, p.sub.3, and p.sub.7 according to the puncturing pattern, and among them, i.sub.1, i.sub.5, and p.sub.2 were selected for the first group G(0), then p.sub.6, and i.sub.4 are selected for the third group G(2).

(127) By mapping the punctured parity bits to groups in a reverse puncturing order, a first group is G(0)={p.sub.2, p.sub.5, p.sub.1, i.sub.0}, a second group is G(1)={i.sub.1, i.sub.2, i.sub.3, i.sub.4}, and a third group is G(2)={i.sub.5, i.sub.6, p.sub.7, p.sub.3}. In creating the third group G(2), because the parity bits are arranged as i.sub.7, i.sub.3, p.sub.0, p.sub.4, i.sub.6, i.sub.2, p.sub.5, and p.sub.1 in reverse order of the puncturing pattern, and among them, i.sub.2, i.sub.5, and p.sub.1 were selected for the first group G(0), then p.sub.7 and i.sub.3, which are first and second parity bits among the parity bits arranged in reverse puncturing order, are selected for the third group G(2).

(128) The first group is transmitted on a (k+2)-th frame, the second group is transmitted on a (k+1)-th frame, and the third group is transmitted on a k-th frame.

(129) While the determined groups are sequentially transmitted, the transmission order of the groups is subject to change. In addition, various other methods for selecting information bits are available in different embodiments of the present invention.

(130) A method for creating additional parity bits when encoding and decoding are performed based on the parity check matrixes used in Digital Video Broadcasting the 2nd Generation Satellite (DVB-S2), DVB-T2, Digital Video Broadcasting the 2nd Generation Cable (DVB-C2), and DVB-NGH systems will be described below.

(131) In the following description, it is assumed that a code rate of a parity check matrix is R=4/9, the number of information bits is K.sub.ldpc=7200, the number of codeword bits is N.sub.ldpc=16200, and the number of parity bits is N.sub.parity=N.sub.ldpcK.sub.ldpc=9000.

(132) As described above, for an information part of an LDPC code, blocks are generated on a 360-column basis. In a parity check matrix, a total of 20 column groups are generated by grouping 7200 columns corresponding to an information word on a 360-column basis. A parity part may express Q.sub.ldpc groups, each of which includes 360 elements as shown in Equation (2) and represents indexes of parity bits. For a code rate R of 4/9, Q.sub.ldpc=25. In addition, any of the puncturing patterns in Table 1 may be used.

(133) For convenience of description, sets of indexes included in column groups of an information part can be expressed as shown in Equation (8) below.

(134) $\begin{array}{cc}X\left(j\right)=\{k.Math.\left[\frac{k}{360}\right]=j,0k<K_{\mathrm{bch}}\}\mathrm{for}0j<N_{\mathrm{info}}& \left(8\right)\end{array}$

(135) In Equation (8), [k/360] indicates an integer less than k/360. For example, if k/360=0.2, [0.2]=0, or if k/360=11.8, [11.8]=11. In addition, N.sub.info indicates the number of column groups in the information part, and N.sub.info=20 for R=4/9. Additionally, K.sub.bch indicates the number of information bits of a BCH code, when an LDPC code and a BCH code are used by being concatenated.

(136) An order for creating optimal additional parity bits according to a length will be described below. The following description assumes that additional parity bits can be selected from parity bits in a reverse order of puncturing.

(137) If the number of input information word is 7200, additional parity bits are first selected in a reverse order of puncturing, because puncturing and shortening are not required. That is, by selecting index values in the following order, information bits and parity bits corresponding to the index values are selected. In the following description, I(a) indicates a set of indexes of parity bits as defined in Equation (3), and X(a) indicates a set of indexes of information bits as defined in Equation (8). In other words, I(a) indicates that parity bits having elements of I(a) are selected as their indexes, and X(a) indicates that information bits having elements of X(a) are selected as their indexes.

(138) I(11).fwdarw.I(7).fwdarw.I(19).fwdarw.I(21).fwdarw.I(0).fwdarw.I(14).fwdarw.I(1).fwdarw.I(23).fwdarw.I(16).fwdarw.I(3).fwdarw.I(12).fwdarw.I(22).fwdarw.I(10).fwdarw.I(24).fwdarw.I(2).fwdarw.I(17).fwdarw.I(5).fwdarw.I(20).fwdarw.I(15).fwdarw.I(8).fwdarw.I(13).fwdarw.I(9).fwdarw.I(18).fwdarw.I(4).fwdarw.I(6)

(139) I(9).fwdarw.I(26).fwdarw.I(3).fwdarw.I(15).fwdarw.I(30).fwdarw.I(13).fwdarw.I(6).fwdarw.I(19).fwdarw.I(34).fwdarw.I(16).fwdarw.I(1).fwdarw.I(23).fwdarw.I(4).fwdarw.I(17) I(22).fwdarw.I(24).fwdarw.I(7).fwdarw.I(11).fwdarw.I(31).fwdarw.I(10).fwdarw.I(8).fwdarw.I(2).fwdarw.I(35).fwdarw.I(28).fwdarw.I(20).fwdarw.I(18).fwdarw.I(25).fwdarw.I(33).fwdarw.I(0).fwdarw.I(21).fwdarw.I(12).fwdarw.I(5).fwdarw.I(32).fwdarw.I(29).fwdarw.I(14).fwdarw.I(27)

(140) When more additional parity bits are required, bits are selected in the following order.

(141) I(11).fwdarw.I(7).fwdarw.I(19).fwdarw.I(21).fwdarw.I(0).fwdarw.I(14).fwdarw.I(1).fwdarw.I(23).fwdarw.I(16).fwdarw.I(3).fwdarw.I(12).fwdarw.I(22).fwdarw.I(10).fwdarw.I(24).fwdarw.I(2).fwdarw.I(17).fwdarw.I(5).fwdarw.I(20).fwdarw.I(15).fwdarw.I(8).fwdarw.I(13).fwdarw.I(9).fwdarw.I(18).fwdarw.I(4).fwdarw.I(6).fwdarw.X(5).fwdarw.X(6).fwdarw.X(7).fwdarw.X(8).fwdarw.X(9).fwdarw.X(10).fwdarw.X(11).fwdarw.X(12).fwdarw.X(13).fwdarw.X(14).fwdarw.X(15).fwdarw.X(16).fwdarw.X(17).fwdarw.X(18).fwdarw.X(19).fwdarw.X(0).fwdarw.X(1).fwdarw.X(2).fwdarw.X(3).fwdarw.X(4)

(142) X(4).fwdarw.X(5).fwdarw.I(9)>I(26).fwdarw.X(6).fwdarw.X(7).fwdarw.X(8).fwdarw.I(3).fwdarw.I(15).fwdarw.I(30).fwdarw.I(13).fwdarw.I(6).fwdarw.I(19).fwdarw.I(34).fwdarw.I(16).fwdarw.I(1).fwdarw.I(23).fwdarw.I(4).fwdarw.I(17).fwdarw.I(22).fwdarw.I(24).fwdarw.I(7).fwdarw.I(11).fwdarw.I(31).fwdarw.I(10).fwdarw.I(8).fwdarw.I(2).fwdarw.I(35).fwdarw.I(28).fwdarw.I(20).fwdarw.I(18).fwdarw.I(25).fwdarw.I(33).fwdarw.I(0).fwdarw.I(21).fwdarw.I(12).fwdarw.I(5).fwdarw.I(32).fwdarw.I(29).fwdarw.I(14).fwdarw.I(27)

(143) Thereafter, if even more additional parity bits are required, both of the above transmission orders are repeated in the same way.

(144) As another example, if the number of input information word is 3600, 10 information bocks undergo shortening and 12 parity blocks undergo puncturing. As a result, the number of non-punctured blocks is 2512=13, and non-punctured blocks are first selected in the following order.

(145) I(11).fwdarw.I(7).fwdarw.I(19).fwdarw.I(21).fwdarw.I(0).fwdarw.I(14).fwdarw.I(1).fwdarw.I(23).fwdarw.I(16).fwdarw.I(3).fwdarw.I(12).fwdarw.I(22).fwdarw.I(10)

(146) I(9).fwdarw.I(26).fwdarw.I(3).fwdarw.I(15).fwdarw.I(30).fwdarw.I(13).fwdarw.I(6).fwdarw.I(19).fwdarw.I(34).fwdarw.I(16).fwdarw.I(1).fwdarw.I(23).fwdarw.I(4).fwdarw.I(17).fwdarw.I(22).fwdarw.I(24).fwdarw.I(7).fwdarw.I(11).fwdarw.I(31).fwdarw.I(10).fwdarw.I(8).fwdarw.I(2).fwdarw.I(35).fwdarw.I(28).fwdarw.I(20).fwdarw.I(18).fwdarw.I(25).fwdarw.I(33).fwdarw.I(0)

(147) If more additional parity bits are required, bits are selected in the following order.

(148) X(5).fwdarw.X(6).fwdarw.X(7).fwdarw.X(8).fwdarw.X(9).fwdarw.X(19).fwdarw.X(0).fwdarw.X(1) 4(11).fwdarw.I(7).fwdarw.X(2).fwdarw.X(3).fwdarw.I(19).fwdarw.I(21).fwdarw.I(0).fwdarw.I(14).fwdarw.I(1).fwdarw.I(23).fwdarw.I(16).fwdarw.I(3).fwdarw.I(12).fwdarw.I(22).fwdarw.I(10).fwdarw.I(24).fwdarw.I(2).fwdarw.I(17).fwdarw.I(5).fwdarw.I(20).fwdarw.I(15).fwdarw.I(8).fwdarw.I(13).fwdarw.I(9).fwdarw.I(18).fwdarw.I(4).fwdarw.I(6)

(149) I(21).fwdarw.I(12).fwdarw.I(5).fwdarw.I(32).fwdarw.I(29).fwdarw.I(14).fwdarw.I(27).fwdarw.X(4.fwdarw.X(5.fwdarw.X(6).fwdarw.I(9).fwdarw.X(8).fwdarw.I(26).fwdarw.I(3).fwdarw.I(15).fwdarw.I(30).fwdarw.I(13).fwdarw.I(6).fwdarw.I(19).fwdarw.X(4).fwdarw.I(34).fwdarw.I(16).fwdarw.I(1).fwdarw.I(23).fwdarw.I(4).fwdarw.I(17).fwdarw.I(22).fwdarw.I(24).fwdarw.I(7).fwdarw.X(5) I(11).fwdarw.I(31).fwdarw.I(10).fwdarw.I(8).fwdarw.X(6).fwdarw.I(2).fwdarw.I(35).fwdarw.I(28).fwdarw.I(20).fwdarw.I(18).fwdarw.I(25).fwdarw.I(33).fwdarw.I(0).fwdarw.I(21).fwdarw.I(12).fwdarw.I(5).fwdarw.I(32).fwdarw.I(29).fwdarw.I(14).fwdarw.I(27)

(150) Thereafter, if even more additional parity bits are required, bits are repeatedly transmitted starting with codeword bits.

(151) As is apparent from the foregoing description, the order of selecting additional parity bits having an optimal performance may be difference according to the length of input information bits. However, if bits are selected as will be described below, optimal performance and optimal system efficiency may be achieved.

(152) More specifically, because Method 1 does not transmit parity bits on the same frames as those of information bits, additional parity bits may be selected in the following order.

(153) 1) Non-punctured parity bits are selected in a normal order or a reverse order of the puncturing pattern.

(154) 2) If more additional parity bits are required, punctured parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(155) 3) If more additional parity bits are still required, bits are selected starting with information bits with a degree of 3.

(156) 4) If even more additional parity bits are still required, parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(157) 5) If more additional parity bits are required, information bits with a degree of 12 are selected.

(158) 6) If more additional parity bits are required, the procedure above is repeated from step 1).

(159) In accordance with another embodiment of the present invention, additional parity bits may be selected in the following order.

(160) 1) Non-punctured parity bits are selected in a normal order or a reverse order of the puncturing pattern.

(161) 2) If more additional parity bits are required, punctured parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(162) 3) If more additional parity bits are still required, bits are selected starting with information bits with a degree of 3.

(163) 4) If even more additional parity bits are still required, information bits with a degree of 12 are selected.

(164) 5) If more additional parity bits are required, parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(165) 6) If more additional parity bits are required, the procedure above is repeated from step 1).

(166) In accordance with another embodiment of the present invention, additional parity bits may be selected in the following order.

(167) 1) Non-punctured parity bits are selected in a normal order or a reverse order of the puncturing pattern.

(168) 2) If more additional parity bits are required, punctured parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(169) 3) If more additional parity bits are still required, parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(170) 4) If even more additional parity bits are still required, bits are selected starting with information bits with a degree of 12.

(171) 5) If more additional parity bits are required, information bits with a degree of 2 are selected.

(172) 6) If more additional parity bits are required, the procedure above is repeated from step 1).

(173) Because Method 2, as described above, transmits parity bits on the same frames as those of information bits, non-punctured parity bits are transmitted on the same frames as those of information bits.

(174) Therefore, in accordance with an embodiment of the present invention, additional parity bits are selected in the following order.

(175) 1) If additional parity bits are required, punctured parity bits are selected in a normal order or a reverse order of the puncturing pattern.

(176) 2) If more additional parity bits are required, bits are selected starting with information bits with a degree of 3.

(177) 3) If more additional parity bits are still required, parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(178) 4) If even more additional parity bits are still required, information bits with a degree of 12 are selected.

(179) 5) If more additional parity bits are required, non-punctured parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(180) 6) If more additional parity bits are required, the above is repeated from 1).

(181) In accordance with another embodiment of the present invention, additional parity bits may be selected in the following order.

(182) 1) If additional parity bits are required, punctured parity bits are selected in a normal order or a reverse order of the puncturing pattern.

(183) 2) If more additional parity bits are required, bits are selected starting with information bits with a degree of 3.

(184) 3) If more additional parity bits are still required, information bits with a degree of 12 are selected.

(185) 4) If even more additional parity bits are still required, punctured parity bits and non-punctured parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(186) 5) If more additional parity bits are required, the procedure above is repeated from step 1).

(187) In accordance with another embodiment of the present invention, additional parity bits may be selected in the following order.

(188) 1) If additional parity bits are required, punctured parity bits are selected in a normal order or a reverse order of the puncturing pattern.

(189) 2) If more additional parity bits are required, parity bits are selected in the normal order or the reverse order of the puncturing pattern.

(190) 3) If more additional parity bits are still required, bits are selected starting with information bits with a degree of 3.

(191) 4) If even more additional parity bits are still required, information bits with a degree of 12 are selected.

(192) 5) If more additional parity bits are required, the procedure above is repeated from step 1).

(193) While methods above have been described based on a code with a code rate of 1/2, among LDPC codes used in DVB-S2, DVB-T2, DVB-C2, and DVB-NGH systems, the same methods may be applied to other code rates.

(194) FIG. 9 illustrates a frame structure of a DVB-T2/NGH system according to an embodiment of the present invention.

(195) Referring to FIG. 9, the signaling information word used in the DVB-T2/NGH system includes a configurable information part and a dynamic information part. The configure information part includes information that remains unchanged for several frames, whereas the dynamic information part includes information that changes for each frame. It is important to receive the configure information part and the dynamic information part without error, because they include information about data of the current frame. For example, when a Cyclic Redundancy Check (CRC) error occurs, data information of the pertinent frame may not be received.

(196) In the configure information part, because the same information is received over several frames, if the received information is stored, errors may be corrected by obtaining diversity gain using the stored information. However, because the dynamic information part, is not repeatedly transmitted, sufficient diversity gain may not be obtained and significant deterioration of error correction capability may occur.

(197) Therefore, as illustrated in FIG. 9, additional parity bits are transmitted on a plurality of frames by applying Method 1, as described above, to the dynamic information part. That is, additional parity bits are created after encoding the dynamic information part by a specific method, and the additional parity bits are divided into a plurality of groups G(0), G(1), . . . , G(s1) whose numbers of elements are N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, . . . , N.sub.add.sub._.sub.parity.sub.s1, and transmitted on s frames. While s=3 in FIG. 9, it is obvious that s can be determined at random. Bits in each group are transmitted on the same frame. Rules 3 and 4 may be applied to the method of dividing parity bits into a plurality of groups. While G(0), G(1), . . . , G(s1) are sequentially mapped to frames in FIG. 9, the method of mapping groups to frames is subject to change.

(198) An occurrence of an error in the signaling information may be detected through a CRC check. If an error is detected through the CRC check, G(0), G(1), . . . , G(s1) are received and dynamic information undergoes additional decoding. After the decoding operation is performed, a CRC check on the signaling may be performed once again to determine whether or nor there is an error.

(199) If an error occurs in additional parity bits in the signaling information parts, the CRC check error may continuously occur, even though dynamic information is recovered through the additional decoding. To resolve these problems, an additional CRC may be used in dynamic information.

(200) FIG. 10 illustrates a frame structure in which an additional CRC is used for dynamic information. Specifically, FIG. 10 illustrates a frame structure of a DVB-T2/NGH system according to another embodiment of the present invention.

(201) If dynamic information is transmitted on a (k+3)-th frame, a CRC for the dynamic information may be transmitted on one of the frames over which additional parity bits are transmitted. As illustrated in FIG. 10, the CRC is transmitted on a (k+2)-th frame. When the dynamic information is encoded in the above method, a CRC may be included or not included in the information word.

(202) In the DVB-T2/NGH system, signaling information, including configurable information, dynamic information, an extension part, a CRC, and padding bits, is encoded as an information word.

(203) In accordance with an embodiment of the present invention, when information is transmitted as illustrated in FIGS. 9 and 10, a transmitter performs additional encoding on the dynamic information, and a receiver performs an additional decoding process on the dynamic information, when a CRC error for the signaling information occurs. In addition, if puncturing and shortening patterns for encoding of dynamic information are different from puncturing and shortening patterns for signaling, an additional module may be required for encoding and decoding of the dynamic information.

(204) Using the frame structures as illustrated in FIGS. 9 and 10, encoding and decoding is performed twice for the signaling information. That is, signaling is divided into two different types of information: one is configure (conf) information that does not vary every frame, and another is dynamic (dyn) information that varies every frame. These two types of information are input as one information word and encoded. Of them, only the dyn information is separately encoded, and its parity bits are transmitted in previous frames. Therefore, primarily, conf and dyn are input as an information word and encoded, and secondarily, dyn is input and encoded. However, by using Method 2, encoding may be performed only once, and because additional puncturing and shortening patterns are not required, the additional module may be minimized in the encoding and decoding process.

(205) FIG. 11 illustrates a frame structure of a DVB-T2/NGH system according to another embodiment of the present invention. Specifically, FIG. 11 illustrates Method 2, as described above, applied to a DVB-T2/NGH system.

(206) The configurable information and dynamic information are received and LDPC-encoded. Generally, because signaling is variable, it undergoes shortening and puncturing to be adaptively encoded according to the variable length.

(207) In the NGH system, because configurable information and dynamic information are encoded independently, L1 signaling in FIG. 11 refers to all kinds of L1 signaling information, instead of being limited to the configurable and dynamic information.

(208) Non-punctured parity bits are transmitted on a (k+3)-th frame, which is the same frame as that of the signaling bits of FIG. 11. Groups G(0), G(1), and G(2) of additional parity bits, which are calculated by Rule 5 and whose numbers of elements are N.sub.add.sub._.sub.parity.sub.0, N.sub.add.sub._.sub.parity.sub.1, and N.sub.add.sub._.sub.parity.sub.2, are transmitted on a (k+2)-th frame, a (k+1)-th frame, and a k-th frame, respectively.

(209) While the number of frames on which additional parity bits are transmitted is assumed to be 3 in FIG. 11, as mentioned above, other numbers of frames may be used. Also, positions of the groups G(0), G(1), and G(2) of additional parity bits are changeable. That is, the additional parity bits may be transmitted on P1/P2 symbols, or an auxiliary stream. Also, the additional parity bits may be transmitted using the general data stream.

(210) While the additional parity bits are transmitted on a (k+2)-th frame, a (k+1)-th frame, and a k-th frame, i.e., subsequent frames, in the descriptions above, alternatively, the additional parity bits may be transmitted on s previous frames.

(211) FIGS. 22A and 22B are diagrams illustrating various frame structures according to different embodiments of the present invention. Specifically, FIGS. 22A and 22B illustrate frames structures in which additional parity bits are transmitted on s previous frames.

(212) FIG. 22A illustrates additional parity bits being transmitted on frames preceding concatenated frames. For example, in the DVB-NGH system, NGH frames are transmitted using Future Extension Frames (FEF) in DVB-T2. Accordingly, the various embodiments of the present invention are not limited to the transmission of additional parity bits on s concatenated frames, and may be applied to the transmission on s frames preceding the frames carrying information bits.

(213) FIG. 22B illustrates that additional parity bits may be transmitted in other RF bands. That is, in accordance with an embodiment of the present invention, the additional parity bits are not limited to the frames transmitted in the same RF channel.

(214) Signaling used in a DVB-T2 system is classified into two types: L1 pre-signaling and L1 post-signaling including a configurable part, a dynamic part, and an extension part. While Method 2 has been described based on L1 post-signaling of T2 type signaling in FIG. 2, it may be applied to L1 pre-signaling of another type, e.g., DVB-NGH.

(215) As in Method 2, after signaling information is encoded, non-punctured parity bits are transmitted on the same frames as those of information bits, and additional parity bits including information bits and parity bits are transmitted on previous frames. For the additional parity bits, punctured parity bits are first selected, and these bits are selected in a normal order or a reverse order of the puncturing pattern.

(216) (N.sub.ldpcK.sub.ldpc) parity bits can be divided into Q.sub.ldpc groups, and a j-th parity group P.sub.j can be expressed as shown in Equation (9).
P.sub.j={p.sub.k|k modQ.sub.ldpc=j, 0k<N.sub.ldpcK.sub.ldpc} for 0j<Q.sub.ldpc (9)

(217) Using Equation (10) below, Q.sub.ldpc can be calculated based on M, N.sub.ldpc and K.sub.ldpc as illustrated in FIG. 3.
Q.sub.ldpc=(N.sub.ldpcK.sub.ldpc)/M (10)

(218) In Equation (10), parity bits are divided into Q.sub.ldpc groups, and each group includes M bits.

(219) For a given number N.sub.punc of punctured bits, punctured parity bits may be calculated as described below in Steps 1-3.

(220) Step 1: The number N.sub.punc.sub._.sub.group of groups whose all parity bits are punctured can be calculated using Equation (11) below, wherein an operator indicates a maximum integer not exceeding . For example, 1.1=1, and 4.5=4.

(221) $\begin{array}{cc}{N}_{\mathrm{punc\_group}}=.Math.\frac{N_{\mathrm{punc}}}{M}.Math.\mathrm{for}0N_{\mathrm{punc}}<N_{\mathrm{ldpc}}-K_{\mathrm{ldpc}}& \left(11\right)\end{array}$

(222) Step 2: For N.sub.punc.sub._.sub.group parity bit groups

(223) 0$P_{{}_p\left(0\right)},P_{{}_p\left(1\right)},\mathrm{.Math.},P_{{}_p\left(N_{\mathrm{punc\_group}}-1\right)},$
all parity bits in the groups are punctured. .sub.p(j), which represents an index of a parity group, also indicates a puncturing order, e.g., as defined in Table 1. For example, in BPSK modulation, since .sub.p(0) is 6, parity bits in a parity bit group P.sub..sub.p.sub.(0)=P.sub.6 are first punctured.

(224) Step 3: For a group

(225) $P_{{}_p\left(N_{\mathrm{punc\_group}}\right),\left(N_{\mathrm{punc}}-M{N}_{\mathrm{punc\_group}}\right)}$
bits are punctured starting with first parity bits in the group. Non-punctured parity bits are transmitted on the same frames as those of the information bits.

(226) Embodiment 7

(227) A group G(0) of first additional parity bits is calculated as described below. For convenience of description, the description assumes that the method is performed starting with Step 4) below, after already performing Steps 1 to 3, described above.

(228) Step 4: The number of parity bit groups whose all elements are selected to select additional parity bits, is calculated using Equation (12).

(229) $\begin{array}{cc}{N}_{{\mathrm{add\_parity}}_0\mathrm{\_group}}=.Math.\frac{N_{{\mathrm{add\_parity}}_0}}{M}.Math.& \left(12\right)\end{array}$

(230) In Equation (12), N.sub.add.sub._.sub.parity.sub.0 indicates the number of first additional parity bits.

(231) Step 5: For

(232) $N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}$
parity bit groups

(233) $P_{{}_p\left(0\right)},P_{{}_p\left(1\right)},\mathrm{.Math.},P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}-1\right)},$
all parity bits in the groups are included in a group G(0) of first additional parity bits, and are transmitted on frames preceding the frame over which the information bits are transmitted. The preceding frames may be applied even in other RF channels as described above in connection with FIG. 22.

(234) Step 6: For a group

(235) $P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)},\left(N_{{\mathrm{add\_parity}}_0}-M{N}_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)$
parity bits are included in a group G(0) of first additional parity bits, starting with first parity bits in the group.

(236) There are several possible methods for determining order of bits in a group G(0) of first additional parity bits. For example, as illustrated in FIGS. 12A and 12C, bits are arranged in an order of a group P.sub..sub.p.sub.()(0<Q.sub.ldpc) of parity bits in units of a group of P.sub..sub.p.sub.() of parity bits. Also, as illustrated in FIG. 12B, parity bits selected for G(0) may be arranged in an order of indexes of parity bits on a bit-by-bit basis.

(237) Step 7: In a group

(238) $P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)},$
the number of parity bits not included in the group G(0) of first additional parity bits may be calculated using Equation (13). Definitions of x and y are illustrated in FIGS. 12A to 12C.

(239) $\begin{array}{cc}y=\min \left(M-\left(N_{{\mathrm{add\_parity}}_0}-M{N}_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right),N_{{\mathrm{add\_parity}}_1}\right)& \left(13\right)\end{array}$

(240) Therefore, a group G(1) of second additional parity bits can be created starting with an

(241) $\left(N_{{\mathrm{add\_parity}}_0}-M{N}_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)$
-th bit in a group

(242) $P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)}.$
The term a-th bit refers to a bit located in an a-th position when the first bit in a group

(243) 0$P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)}$
is defined as a 0-th bit. In addition, min(a,b) represents a function of selecting one of a and b, which is the minimum value. For example, min(a,b)=a for ab, and min(a,b)=b for a>b.

(244) Step 8: For N.sub.add.sub._.sub.parity.sub.1>y, the number of parity bit groups whose all elements are selected to select second additional parity bits, is calculated using Equation (14) below.

(245) $\begin{array}{cc}{N}_{{\mathrm{add\_parity}}_1\mathrm{\_group}}=.Math.\frac{N_{{\mathrm{add\_parity}}_1}-y}{M}.Math.& \left(14\right)\end{array}$

(246) Step 9: All parity bits in the groups

(247) $P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1\right)},P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+2\right)},\mathrm{.Math.},P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}\right)}$
are included in a group of second additional parity bits.

(248) Step 10: In a group

(249) $P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}+1\right)},$

(250) $\left(N_{{\mathrm{add\_parity}}_1}-y-M{N}_{{\mathrm{add\_parity}}_1\mathrm{\_group}}\right)$
parity bits are created as second additional parity bits.

(251) Step 11: In a group

(252) $P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1\right)},$
the number y of parity bits not included in the group G(1) of second additional parity bits can be calculated using Equation (15).

(253) $\begin{array}{cc}x=N_{{\mathrm{add\_parity}}_1}-y-M{N}_{{\mathrm{add\_parity}}_1\mathrm{\_group}}y=\min \left(M-x,N_{{\mathrm{add\_parity}}_2}\right)& \left(15\right)\end{array}$

(254) Therefore, y bits may be included in a group G(2) of third additional parity bits, starting with an x bit in the group

(255) $P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1\right).}$

(256) Step 12: For N.sub.add.sub._.sub.parity.sub.2>y, the number of parity bit groups whose elements are all selected to select third additional parity bits, is calculated using Equation (16).

(257) $\begin{array}{cc}{N}_{{\mathrm{add\_parity}}_2\mathrm{\_group}}=.Math.\frac{N_{{\mathrm{add\_parity}}_2}-y}{M}.Math.& \left(16\right)\end{array}$

(258) Step 13: All parity bits in groups

(259) $P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}+2\right)},P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}+3\right)},\mathrm{.Math.},P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_2\mathrm{\_group}}+2\right)}$
are included in a group of third additional parity bits.

(260) Step 14: In a group

(261) 0$P_{{}_p\left(N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_2\mathrm{\_group}}+3\right)},$
(N.sub.add.sub._.sub.parity.sub.2yMN.sub.add.sub._.sub.parity.sub.2.sub.group) parity bits are created as third additional parity bits.

(262) The method of determining an order of bits in a group G(1) of second additional parity bits is equal to the method of determining order of bits in a group G(0) of first additional parity bits.

(263) Embodiment 8

(264) A method of selecting additional parity bits in a reverse order of a puncturing pattern will be described below with reference to FIGS. 13A to 13C.

(265) A method of calculating parity bits transmitted on the same frames as the information bits corresponds to Steps 1 to 3, as described above.

(266) A group G(0) of first additional parity bits is calculated in the following method.

(267) Step 4: The number y of bits selected for a group G(0) in a group

(268) $P_{{}_p\left(N_{\mathrm{punc\_group}}\right)}$
can be calculated using Equation (17).
y=min(N.sub.puncMN.sub.punc.sub._.sub.group, N.sub.add.sub._.sub.parity.sub.0) (17)

(269) Step 5: y bits are selected as first additional parity bits, starting with a first bit in the group

(270) $P_{{}_p\left(N_{\mathrm{punc\_group}}\right)}.$

(271) If (N.sub.ldpcMN.sub.punc.sub._.sub.group) bits are punctured starting with the last parity bit in the group

(272) $P_{{}_p\left(N_{\mathrm{punc\_group}}\right)}$
and non-punctured bits are transmitted on the same frames as the information bits in Step 3, y bits are selected as first additional parity bits, starting with the last parity bit in a group

(273) $P_{{}_p\left(N_{\mathrm{punc\_group}}\right)}$
in Step 5.

(274) If N.sub.add.sub._.sub.parity.sub.0 is greater than y, the following Steps 6-8 are performed.

(275) Step 6: The number of parity bit groups whose all parity bits are selected for transmission, is calculated using Equation (18).

(276) $\begin{array}{cc}{N}_{{\mathrm{add\_parity}}_0\mathrm{\_group}}=.Math.\frac{N_{{\mathrm{add\_parity}}_0-y}}{M}.Math.& \left(18\right)\end{array}$

(277) Step 7: All parity bits in the

(278) $N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}$
parity bit groups

(279) $P_{{}_p\left(N_{\mathrm{punc\_group}}\right)},P_{{}_p\left(N_{\mathrm{punc\_group}}-1\right)},\mathrm{.Math.},P_{{}_p\left(N_{\mathrm{punc\_group}}-N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1\right)}$
are selected for the group G(0) of first additional parity bits, and are transmitted on frames preceding the frames where the information bits are transmitted.

(280) Step 8:

(281) $\left(N_{{\mathrm{add\_parity}}_0}-M{N}_{{\mathrm{add\_parity}}_0\mathrm{\_group}}-y\right)$
parity bits are selected for the group G(0) of first additional parity bits, starting with first parity bits in a group

(282) $P_{{}_p\left(N_{\mathrm{punc\_group}}-N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)}.$

(283) There are several possible methods for determining an order of bits in a group G(0) of first additional parity bits. For example, as illustrated in FIGS. 13A and 13C, bits are arranged in reverse order of a group P.sub..sub.p.sub.()(0<Q.sub.ldpc) of parity bits in units of the parity bit group P.sub..sub.p.sub.(). Also, as illustrated in FIG. 13B, parity bits selected as additional parity bits may be arranged in an order of indexes of parity bits on a bit-by-bit basis.

(284) A group G(1) of second additional parity bits is created by Steps 9-12.

(285) Step 9: The number y of bits selected for a group G(1) in a group

(286) 0$P_{{}_p\left(N_{\mathrm{punc\_group}}-N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)}$
is calculated using Equation (19).

(287) $\begin{array}{cc}x=N_{{\mathrm{add\_parity}}_0}-M{N}_{{\mathrm{add\_parity}}_0\mathrm{\_group}}-yy=\min \left(M-x,N_{{\mathrm{add\_parity}}_1}\right)& \left(19\right)\end{array}$

(288) Step 10: y bits are selected starting with a first bit in a group

(289) $P_{{}_p\left(N_{\mathrm{punc\_group}}-N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}\right)}.$

(290) If N.sub.add.sub._.sub.parity.sub.1 is greater than y, the following process is performed.

(291) Step 11: The number of parity bit groups whose all bits are transmitted, is calculated using Equation (20).

(292) $\begin{array}{cc}{N}_{{\mathrm{add\_parity}}_1\mathrm{\_group}}=.Math.\frac{N_{\mathrm{add}-{\mathrm{parity}}_1}-y}{M}.Math.& \left(20\right)\end{array}$

(293) Step 12: All parity bits in the

(294) $N_{{\mathrm{add}\_\mathrm{parity}}_1\mathrm{\_group}}$
parity bit groups

(295) $P_{{}_p\left(N_{\mathrm{punc}\mathrm{\_group}}-N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}-1\right)},P_{{}_p\left(N_{\mathrm{punc\_group}}-N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}-2\right)},\mathrm{.Math.},P_{{}_p\left(N_{\mathrm{punc\_\_group}}-N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}-N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}\right)}$
are included in a group G(1) of second additional parity bits, and are transmitted on frames preceding the frames in which the information bits are transmitted.

(296) Step 13:

(297) $\left(N_{{\mathrm{add}\_\mathrm{parity}}_1}-M{N}_{{\mathrm{add}\_\mathrm{parity}}_1\_\mathrm{group}}-y\right)$
parity bits are included in a group G(1) of second additional parity bits, starting with first parity bits in a group

(298) $P_{{}_p\left(N_{\mathrm{punc\_group}}-N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1\right)}.$

(299) The method of determining order of bits in a group G(1) of second additional parity bits is equal to the method of determining order of bits in a group G(0) of first additional parity bits.

(300) Embodiment 9

(301) A method of more efficiently calculating additional parity bits by interleaving parity bits will be described below with reference to FIGS. 14A to 14D.

(302) Parity bits p={p.sub.1, p.sub.1, . . . , p.sub.N.sub.parity} obtained by LDPC encoding are interleaved in accordance with Equation (21).
d.sub.Mt+s=P.sub.Q.sub.ldpc.sub.s+t where MQ.sub.ldpc=N.sub.parity, 0s<M, 0t<Q.sub.ldpc
D.sub.j={d.sub.k|jMk<(j+1)M} for 0j<Q.sub.ldpc (21)

(303) The parity bit group is group-interleaved based on the .sub.p(j), and can be presented as shown in Equation (22).

(304) If interleaved by Equation (21), an LDPC codeword constructed as illustrated in FIG. 14A is arranged in units of a plurality of parity bit groups P.sub.(0<Q.sub.ldpc), as illustrated in FIG. 14B.
Z.sub.i=D.sub..sub.p.sub.(Q.sub.ldpc.sub.1i) (22)

(305) The group interleaving, or group-by-group interleaving, means that bits in a group are equally interleaved, and bits in a group Z are equal to bits of D.sub..sub.p.sub.(Q.sub.ldpc.sub.1i).

(306) The .sub.p(j), a value representing puncturing order, means the puncturing pattern for 0j<Q.sub.ldpc, which has been described in Table 1.

(307) If interleaved by Equation (22), an LDPC codeword as illustrated in FIG. 14B is arranged such that a plurality of groups of parity bits are arranged in a reverse order of a puncturing pattern as in illustrated in FIG. 14C.

(308) A method of calculating parity bits transmitted on the same frames as the information bits, is described below.

(309) Step 1: The number N.sub.tx.sub._.sub.group of parity bit groups in which all parity bits are transmitted, can be calculated based on the number of punctured parity bits in accordance with Equation (23).

(310) $\begin{array}{cc}{N}_{\mathrm{tx\_group}}=.Math.\frac{N_{\mathrm{parity}}-N_{\mathrm{punc}}}{M}.Math.\mathrm{for}0N_{\mathrm{tx}}<N_{\mathrm{ldpc}}-K_{\mathrm{ldpc}}& \left(23\right)\end{array}$

(311) Step 2: All parity bits in the N.sub.tx.sub._.sub.group parity bit groups

(312) $Z_0,Z_1,\mathrm{.Math.},Z_{N_{\mathrm{tx\_group}-1}}$
are transmitted.

(313) Step 3: (N.sub.txMN.sub.tx.sub._.sub.group) bits are transmitted on the same frames as those of information bits, starting with first parity bits in a group

(314) 0$Z_{N_{\mathrm{punc\_group}}}.$

(315) First additional parity bits are calculated using Steps 4-8.

(316) Step 4: The number y of bits selected for a group G(0) in a group

(317) $Z_{N_{\mathrm{punc\_group}}}$
can be calculated in accordance with Equation (24).
y=min((N.sub.txMN.sub.tx.sub._.sub.group), N.sub.add.sub._.sub.parity.sub.0) (24)

(318) Step 5: y bits are selected as first additional parity bits, starting with a first bit in a group

(319) $Z_{N_{\mathrm{punc\_group}}}.$

(320) If N.sub.add.sub._.sub.parity.sub.0 is greater than y, Steps 6 and 7 are performed.

(321) Step 6: The number of groups in which all bits are transmitted, is calculated using Equation (25).

(322) $\begin{array}{cc}{N}_{{\mathrm{add\_parity}}_0\mathrm{\_group}}=.Math.\frac{N_{{\mathrm{add\_parity}}_0}-y}{M}.Math.& \left(25\right)\end{array}$

(323) Step 7: All parity bits in the

(324) $N_{{\mathrm{add}\_\mathrm{parity}}_0\mathrm{\_group}}$
parity bit groups

(325) $Z_{N_{\mathrm{punc\_group}}+1},\mathrm{.Math.},Z_{N_{\mathrm{punc\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}}$
are included in a group G(0) of first additional parity bits and are transmitted on frames preceding the frames where the information bits are transmitted.

(326) Step 8:

(327) $\left(N_{{\mathrm{add}\_\mathrm{parity}}_0}-M{N}_{{\mathrm{add}\_\mathrm{parity}}_0\_\mathrm{group}}-y\right)$
parity bits are included in a group G(0) of first additional parity bits, starting with first parity bits in a group

(328) $Z_{N_{\mathrm{punc\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1}.$

(329) The group of additional parity bits is constructed as illustrated in FIG. 14D.

(330) A group G(1) of second additional parity bits is created using steps 9-13.

(331) Step 9: The number y of bits selected for a group G(1) in a group

(332) $Z_{N_{\mathrm{punc\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1}$
can be calculated using Equation (26).

(333) $\begin{array}{cc}x=N_{{\mathrm{add}\_\mathrm{parity}}_0}-M{N}_{{\mathrm{add}\_\mathrm{parity}}_0\_\mathrm{group}}-yy=\min \left(M-x,N_{{\mathrm{add}\_\mathrm{parity}}_1}\right)& \left(26\right)\end{array}$

(334) Step 10: y bits are selected starting with a first bit in a group

(335) 0$Z_{N_{\mathrm{punc\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1}.$

(336) If N.sub.add.sub._.sub.parity.sub.1 is greater than y, Steps 11 to 13 are performed.

(337) Step 11: The number of groups in which all bits are transmitted, is calculated using Equation (27).

(338) $\begin{array}{cc}{N}_{{\mathrm{add\_parity}}_1\mathrm{\_group}}=.Math.\frac{N_{{\mathrm{add\_parity}}_1}-y}{M}.Math.& \left(27\right)\end{array}$

(339) Step 12: All parity bits in the

(340) $N_{{\mathrm{add}\_\mathrm{parity}}_1\mathrm{\_group}}$
parity bit groups

(341) $Z_{N_{\mathrm{punc\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+2},Z_{N_{\mathrm{punc\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+3},\mathrm{.Math.},Z_{N_{\mathrm{punc\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+1+N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}}$
are included in a group G(1) of second additional parity bits, and are transmitted on frames preceding the frames in which the information bits are transmitted.

(342) Step 13:

(343) $\left(N_{{\mathrm{add}\_\mathrm{parity}}_1}-M{N}_{{\mathrm{add}\_\mathrm{parity}}_1\_\mathrm{group}}-y\right)$
parity bits are included in a group G(1) of second additional parity bits, starting with first parity bits in a group

(344) $Z_{N_{\mathrm{punc\_group}}+N_{{\mathrm{add\_parity}}_0\mathrm{\_group}}+N_{{\mathrm{add\_parity}}_1\mathrm{\_group}}+2}.$

(345) Group interleaving of Equation (22) can be expressed as shown in Equation (28).
z.sub.lM+s=d.sub..sub.p.sub.(l)M+s, 0l<Q.sub.ldpc, 0s<M (28)

(346) In this case, parity bits may be represented as z=z.sub.0, z.sub.1, z.sub.2, . . . , z.sub.N.sub.parity.

(347) Therefore, parity bits, which are selected even when additional parity bits are not used, may be selected based on the value N.sub.tx calculated in Equation (23), representing the number of parity bits transmitted on the same frames as those of the information bits, and on the additional parity bits

(348) $N_{{\mathrm{add\_parity}}_0},\mathrm{and}{N}_{{\mathrm{add\_parity}}_1}.$

(349) Equation (29) represents a group {circumflex over (P)} of parity bits transmitted on the same frames as the information word, a group G(0) of first additional parity bits, and a group G(1) of second additional parity bits.

(350) $\begin{array}{cc}\hat{P}=\left\{z_0,z_1,\mathrm{.Math.},z_{N_{\mathrm{tx}}-1}\right\}G\left(0\right)=\left\{z_{N_{\mathrm{tx}}},z_{N_{\mathrm{tx}}+1},z_{N_{\mathrm{tx}}+2},\mathrm{.Math.},z_{N_{\mathrm{tx}}+N_{{\mathrm{add\_parity}}_0-1}}\right\}G\left(1\right)=\left\{z_{N_{\mathrm{tx}}+N_{{\mathrm{add\_parity}}_0}},z_{N_{\mathrm{tx}}+N_{{\mathrm{add\_parity}}_0}+1},z_{N_{\mathrm{tx}}+N_{{\mathrm{add\_parity}}_0}+2},\mathrm{.Math.},z_{N_{\mathrm{tx}}+N_{{\mathrm{add\_parity}}_0}+N_{{\mathrm{add\_parity}}_1-1}}\right\}& \left(29\right)\end{array}$

(351) If the total number

(352) $N_{{\mathrm{add}\_\mathrm{parity}}_0}+\mathrm{.Math.}+N_{{\mathrm{add}\_\mathrm{parity}}_{s-1}}$
of additional parity bits is greater than N.sub.punc, N.sub.punc additional parity bits are selected in accordance with Embodiments 7 and 8. More additional parity bits, which are required exceeding N.sub.punc, may be selected from the codeword, and the simplest way is to sequentially select the information word, parity bits transmitted in the same frames as those of the information word, and the selected additional parity bits, on a repeated basis, which is illustrated in FIG. 23 in brief.

(353) Embodiment 10

(354) A method of selecting additional parity bits in reverse order of a puncturing pattern is described below, wherein the total number

(355) $N_{{\mathrm{add}\_\mathrm{parity}}_0}+\mathrm{.Math.}+N_{{\mathrm{add}\_\mathrm{parity}}_{s-1}}$
of additional parity bits is greater than N.sub.punc.

(356) This method of calculating parity bits transmitted on the same frames as the information bits corresponds to Steps 1 to 3, as described above.

(357) A group G(0) of first additional parity bits is calculated in Step 4.

(358) Step 4: For

(359) 0$N_{{\mathrm{add}\_\mathrm{parity}}_0}>N_{\mathrm{punc},N_{\mathrm{punc}}}$
bits are selected for a group G(0), and

(360) $N_{{\mathrm{add}\_\mathrm{prity}}_0}-N_{\mathrm{punc}}$
bits are selected from codeword bits, for the group G(0). A simple method is to sequentially select the codeword bits and additional parity bits on a repeated basis, as illustrated in FIG. 23.

(361) For

(362) $N_{{\mathrm{add}\_\mathrm{parity}}_0}<N_{\mathrm{punc}},$
Steps 4 to 8 of Embodiment 8 are performed in the same way.

(363) A group G(1) of second additional parity bits is created in the following method.

(364) Step 9: For

(365) $N_{{\mathrm{add}\_\mathrm{parity}}_0}>N_{\mathrm{punc}}$
in Step 4, G(.sub.1) is selected from the codeword bits. The simplest way is to sequentially select the previously transmitted bits.

(366) For

(367) $N_{{\mathrm{add}\_\mathrm{parity}}_0}<N_{\mathrm{punc}}\mathrm{and}{N}_{{\mathrm{add}\_\mathrm{parity}}_0}+N_{{\mathrm{add}\_\mathrm{parity}}_1}>N_{\mathrm{punc}},$
G(1) is selected from the codeword bits. A simple method is to sequentially select the information bits, parity bits, and additional parity bits on a repeated basis, as illustrated in FIG. 23.

(368) For

(369) $N_{{\mathrm{add}\_\mathrm{parity}}_0}+N_{{\mathrm{add}\_\mathrm{parity}}_1}<N_{\mathrm{punc}},$
Steps 9 to 13 of Embodiment 8 are performed in the same way.

(370) FIG. 15 is a block diagram illustrating a transmission and reception apparatus according to an embodiment of the present invention.

(371) Referring to FIG. 15, a transmitter 1500 includes an encoder 1502, a modulator 1504, and a framer 1506. A message u is encoded by the encoder 1502, modulated by the modulator 1504, and framed by the framer 1506 before being transmitted over a channel 1508. The transmitted signal is received at a receiver 1510 including a de-framer 1516, a demodulator 1514, and a decoder 1512. The received signal r is de-framed by a de-framer 1516 and a signal y is input to the demodulator 1514. The decoder 1512 calculates an estimate of a message from a signal z demodulated by the demodulator 1514.

(372) The encoder 1502 generates parity bits by performing puncturing and shortening in a predetermined manner according to the size of the message.

(373) FIG. 16 is a block diagram illustrating a transmission apparatus using a shortened LDPC code according to an embodiment of the present invention.

(374) Referring to FIG. 16, the transmission apparatus includes an encoder 1602, a controller 1604, a puncturer 1606, an additional parity bit group generator 1608, and a framer 1610. Optionally, the transmission apparatus may include a shortening applying unit 1600.

(375) The controller 1604 determines the number of bits that the shortening applying unit 1600 will shorten according to the length of an information word. The shortening applying unit 1600 inserts a bit having a value of 0 in a position corresponding to a shortened bit, or removes a column corresponding to a shortened bit from a parity check matrix of a given LDPC code. A method for determining the shortening pattern includes using a shortening pattern stored in a memory, generating a shortening pattern using a sequence generator (not shown), or obtaining a shortening pattern by using a density evolution analysis algorithm for a parity check matrix and a given information word length.

(376) The LDPC encoder 1602 performs encoding based on an LDPC code shortened by the controller 1604 and the shortening applying unit 1600. In addition, puncturing is required, puncturing is applied to a generated LDPC codeword by the puncturer 1606. The number of and positions of bits the puncturer 1606 should puncture are determined by the controller 1604 according to a puncturing pattern. That is, knowing a puncturing pattern or puncturing order, the controller 1604 selects the bits to be punctured according to the puncturing order. The puncturing pattern may be stored in a memory, or may be generated using a sequence generator (not shown).

(377) The additional parity bit group generator 1608 receives output data of the controller 1604 and the encoder 1602, and data from the puncturer 1606, and based thereon, generates additional parity bit groups in accordance with the above-described rules.

(378) The framer 1610 generates frames corresponding to Methods 1 and 2, as described above.

(379) FIG. 17 is a block diagram illustrating a reception apparatus using an LDPC code to which additional parity bit groups are applied, according to an embodiment of the present invention. Specifically, the example of the reception apparatus illustrated in FIG. 17 receives a signal transmitted from a communication system using the additional parity bit groups, and restores user-desired data from the received signal upon acquiring information about additional parity bits constituting the additional parity bit groups, from the received signal.

(380) Referring to FIG. 17, the reception apparatus includes a controller 1700, a shortening/puncturing processor 1702, a demodulator 1704, an additional parity bit group processor 1706, and a decoder 1708. The demodulator 1704 receives and demodulates an LDPC code, reconstructs a frame by the controller 1700, and estimates an input value to the LDPC encoder in FIG. 16 based on the received signal. The demodulator 1704 delivers the demodulated signal to the shortening/puncturing processor 1702, the decoder 1708, and the additional parity bit group processor 1706.

(381) The shortening/puncturing processor 1702, under control of the controller 1700, determines information about the shortened/punctured bits of an LDPC code based on the signal demodulated by the demodulator 1704, and delivers position information of the shortened/punctured bits to the decoder 1708.

(382) The decoder 1708 restores user-desired data from the received signal using an output value of the demodulator 1704, and length information of the shortened/punctured code and position information of the shortened/punctured bits, received from the shortening/puncturing processor 1702. The decoder 1708 performs decoding by receiving position information of additional parity bits and a demodulation value from the additional parity bit group processor 1706.

(383) The additional parity bit group processor 1706, under control of the controller 1700, processes position information of additional parity bits and demodulated data, and delivers the processed data to the decoder 1708. Processing demodulated data may vary in meaning. For example, values demodulated when the same bits are received several times, may be added.

(384) FIG. 18 is a block diagram illustrating a transmission apparatus using a shortened LDPC code according to an embodiment of the present invention.

(385) Referring to FIG. 18, the transmission apparatus includes an encoder 1802, a controller 1804, a puncturer 1806, an additional parity bit group generator 1808, a framer 1810, and a parity interleaver 1812. Optionally, the transmission apparatus may include a shortening applying unit 1800.

(386) The controller 1804 determines the number of bits that the shortening applying unit 1800 will shorten, according to the length of an information word. The shortening applying unit 1800 inserts a bit having a value of 0 in a position corresponding to a shortened bit, or removes a column corresponding to a shortened bit from a parity check matrix of a given LDPC code. A method for determining the shortening pattern includes using a shortening pattern stored in a memory, generating a shortening pattern using a sequence generator (not shown), or obtaining a shortening pattern by using a density evolution analysis algorithm for a parity check matrix and a given information word length.

(387) The encoder 1802 performs encoding based on an LDPC code shortened by the controller 1804 and the shortening applying unit 1800. Output values of the encoder 1802 are parity-interleaved by the parity interleaver 1812 on a group basis or on a bit basis, as described above in Embodiment 9.

(388) As described above, the parity interleaver 1812 performs interleaving according to a puncturing pattern under control of the controller 1808. In addition, if puncturing is required, puncturing is applied to a generated LDPC codeword by the puncturer 1806. The number of and positions of bits the puncturer 1806 should puncture are determined by the controller 1804 according to a puncturing pattern. That is, knowing the puncturing pattern (or a puncturing order), the controller 1804 selects the bits punctured according to the puncturing pattern. The puncturing pattern may be stored in a memory, or may be generated using a sequence generator (not shown).

(389) The additional parity bit group generator 1808 receives output data of the controller 1804 and the encoder 1802, and data from the puncturer 1806, and based thereon, generates additional parity bit groups in accordance with the above-described rules.

(390) The framer 1810 generates frames corresponding to Methods 1 and 2, as described above.

(391) FIG. 19 is a block diagram illustrating a reception apparatus using an LDPC code to which additional parity bit groups are applied, according to an embodiment of the present invention. Specifically, the example of the reception apparatus illustrated in FIG. 19 receives a signal transmitted from a communication system using the additional parity bit groups, and restores user-desired data from the received signal upon acquiring information about additional parity bits constituting the additional parity bit groups, from the received signal.

(392) Referring to FIG. 19, the reception apparatus includes a controller 1900, a shortening/puncturing processor 1902, a demodulator 1904, an additional parity bit group processor 1906, a decoder 1908, and a parity deinterleaver 1910. The demodulator 1904 receives and demodulates an LDPC code, and delivers the demodulated signal to the shortening/puncturing processor 1902, the decoder 1908, and the additional parity bit group processor 1906.

(393) The shortening/puncturing processor 1902, under control of the controller 1900, acquires information about shortened/punctured bits of an LDPC code from the signal demodulated by the demodulator 1904, and delivers the position information of the shortened/punctured bits to the decoder 1908.

(394) The parity deinterleaver 1910, which corresponds to the parity interleaver 1812 illustrated in FIG. 18, reconstructs parity bits using an output value of the demodulator 1904, and length information of the shortened/punctured code and position information of the shortened/punctured bits, received from the shortening/puncturing processor 1902, and performs parity deinterleaving thereon.

(395) The decoder 1908 restores user-desired data from the received signal using an output value of the parity deinterleaver 1910, and length information of a shortened/punctured code and position information of the shortened/punctured bits, received from the shortening/puncturing processor 1902. The decoder 1908 receives position information of additional parity bits and a demodulation value from the additional parity bit group processor 1906, and performs decoding thereon.

(396) The additional parity bit group processor 1906, under control of the controller 1900, processes position information of the additional parity bits and the demodulated data, and delivers the processed data to the decoder 1908. Processing demodulated data may vary in meaning. For example, values demodulated when the same bits are received several times, may be added.

(397) FIG. 20 is a flowchart illustrating a transmission method according to an embodiment of the present invention.

(398) Referring to FIG. 20, in step 2000, the controller 1604 (or 1804) determines the number of bits for puncturing and shortening, the number of frames for carrying parity bits, and the number of bits and groups transmitted on each frame, in accordance with the above-described methods and rules.

(399) In step 2002, the shortening applying unit 1600 (or 1800) performs shortening as needed. In step 2004, the encoder 1602 (or 1802) performs LDPC encoding using the determined parameters. In step 2006, the puncturer 1606 (or 1806) shortens/punctures the encoded bits. In step 2008, the additional parity bit group generator 1608 (or 1808) generates a plurality of additional parity bit groups using the codeword bits and parity bits in accordance with Rules 3 to 5. Step 2008 may also include a parity interleaving process. In step 2010, the framer 1610 (or 1810) transmits the codeword and the additional parity bit groups on a plurality of frames in accordance with the various methods according to the above-described embodiments of the present invention.

(400) FIG. 21 is a flowchart illustrating a reception operation of a reception apparatus according to an embodiment of the present invention.

(401) Referring to FIG. 21, in step 2100, the reception apparatus receives a code. In step 2102, the demodulator 1704 (or 1904) demodulates the received signal. Thereafter, in step 2104, the shortening/puncturing processor 1702 (or 1902) performs shortening/puncturing on the demodulated signal.

(402) If there are no shortened/punctured bits, the decoder 1708 (or 1908) performs decoding in step 2108, skipping step 2106. However, if there are shortened/punctured bits, the shortening/puncturing processor 1702 (or 1902) delivers position information of shortened/punctured bits to the decoder 1708 (or 1908) and the additional parity bit group processor 1706 (or 1906) delivers position information of the additional parity bits to the decoder 1708 (or 1908), in step 2106.

(403) In step 2108, considering that a probability that values of the shortened bits will be 0 is 1, based on the position information of the shortened/punctured bits, the decoder 1708 (or 1908) performs LDPC decoding, after determining that the punctured bits are erased bits.

(404) As is apparent from the foregoing description, according to the above-described embodiments of the present invention, additional diversity gain may be obtained by transmitting parity bits over a plurality of frames.

(405) In addition, by transmitting additional parity bits on a plurality of frames, the various embodiments of the present invention minimize for the use of an additional module in an encoding/decoding process, while increasing diversity gain.

(406) While the present invention has been shown and described with reference to certain 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 invention as defined by the appended claims and their equivalents.