T 1137/05 () of 28.9.2007

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the examining division refusing the European patent application No. 02 003 682.8.

II. In the contested decision the examining division held, inter alia, that the application as originally filed did not provide a clear definition of "quasi-complementary turbo code" (QCTC), and that also the expression "complementary code" was not clear from the application as a whole. As these expressions appeared in the independent claims then on file, the claims lacked clarity under Article 84 EPC.

III. In the course of the examination proceedings, the examining division had, inter alia, referred to the following documents:

D1: EP-A-1 231 735,

D2: RPA010004.pdf from the 3gpp.org website, published on 16 November 2001, pages 1 to 27,

D3: Advance Program of "The 57th IEEE Semiannual Vehicular Technology Conference", April 22 - 25, 2003, Jeju, Korea, pages 1 to 102.

IV. Oral proceedings were held before the Board on 28 September 2007.

V. The appellant requested that the decision under appeal be set aside and that a patent be granted in the following version:

Claims: 1 to 12 received during the oral proceedings;

Description: pages 1, 4a, 5, 6, 8, 18 received during the oral proceedings,

pages 4 and 28 as filed with letter dated 2 February 2004,

pages 2, 3, 7, 9 to 17 and 19 to 27 as originally filed;

Drawings: Figures 1 to 7 as originally filed.

VI. The wording of claim 1 reads as follows:

" An apparatus for receiving sub-codes of a quasi-complementary turbo code, QCTC, and decoding the QCTC, said QCTC being a code that is generated from a turbo code with a predetermined code rate obtained by using a turbo code encoder for generating N codeword symbols comprising information symbols (x), and parity symbols (Y0, Y1, Y0´, Y1´),

said turbo code encoder comprising a first constituent encoder and a second constituent encoder, each of said first and second constituent encoders generating primary (Y0, Y1) and secondary parity symbols (Y0´, Y1´), wherein sub-codes (Cij) of said QCTC are generated by:

independently interleaving said information symbols (x), said primary (Y0, Y1) and secondary (Y0´, Y1´) parity symbols,

multiplexing the interleaved primary parity symbols (Y0, Y1) to form alternating interleaved primary parity symbols ([Sbi _Y0(1), Sbi _Y1(1), Sbi _Y0(2), Sbi _ Y1(2),...]) from said first and second constituent encoders and multiplexing the interleaved secondary parity symbols (Y0´, Y1´) to form alternating interleaved secondary parity symbols ([Sbi _Y0´(1), Sbi _Y1´(1), Sbi _Y0´(2), Sbi _Y1´(2),...]) from said first and second constituent encoders and

concatenating the interleaved code symbols to form a concatenated code symbol sequence ([A:B:C]), said concatenated code symbol sequence ([A:B:C]) comprising the interleaved information symbols ([Sbi _X(1), Sbi_X(2), Sbi _X(3),...]) followed by alternating interleaved primary parity symbols ([Sbi _Y0(1), Sbi _Y1(1), Sbi _Y0(2), Sbi _Y1(2),...]) from said first and second constituent encoders and then followed by alternating interleaved secondary parity symbols ([Sbi _Y0´(1), Sbi _Y1´(1), Sbi _Y0´(2), Sbi _Y1´(2),...]) from said first and second constituent encoders,

so that the number of punctured parity symbols from the first constituent encoder (Y0 , Y0´) is equal to the number of punctured parity symbols from the second constituent encoder (Y1, Y1´) or that the difference between said numbers is only one in the concatenated code symbol sequence ([A:B:C]) when a number of successive symbols in the concatenated code symbols sequence are punctured;

generating a sub-code (Cij) of a QCTC by selecting a predetermined number of consecutive symbols starting from the symbol next to the last symbol selected for the previous transmission in the concatenated symbol sequence ([A:B:C]) in order to create a sub-code with a given code rate, wherein

said selecting comprises puncturing all the symbols which are not necessary for creating said sub-code from the end of the concatenated code symbol sequence ([A:B:C]), or repeating the concatenated code symbol sequence ([A:B:C]) and puncturing all the symbols which are not necessary for creating said sub-code from the end of the repeated concatenated code symbol sequence;

said apparatus comprising:

a buffer (501) to store received sub-codes (C00, C10, C20, C21,...),

a sequence combiner (411) adapted to generate a symbol stream by sequence-combining the symbols of the stored sub-codes (Cij), wherein the number of code symbols in said generated symbol stream is the number N of codeword symbols output by said turbo code encoder, and wherein said combiner performs a reverse operation of the process of sequence repetition and symbol puncturing performed to generate the sub-codes (Cij) in order to generate the concatenated code symbol sequence ([A:B:C]);

channel de-interleaver (421) adapted to separate the output of the combiner (411) into an information symbol stream (x) and primary (Y0, Y1) and secondary parity (Y0´, Y1´) symbol streams, to independently de-multiplex the primary (Y0, Y1) and secondary (Y0´, Y1´) parity symbol streams into parity symbol stream pairs (Y0, Y0´ and Y1, Y1´) and to separately output the parity symbol streams and information symbol stream; and

a code decoder (431) adapted to multiplex the output of the channel de-interleaver to turbo decode the multiplexed output according to the predetermined code rate of said turbo code encoder, and to output an information symbol stream (x)."

Claims 2 to 8 are dependent on claim 1.

The wording of claim 9 reads as follows:

" A method for receiving sub-codes of a quasi-complementary turbo code, QCTC, and decoding the QCTC, said QCTC being a code that is generated from a turbo code with a predetermined code rate obtained by using a turbo code encoder for generating N codeword symbols comprising information symbols (x), and parity symbols (Y0, Y1, Y0´, Y1´),

said turbo code encoder comprising a first constituent encoder and a second constituent encoder, each of said first and second constituent encoders generating primary (Y0, Y1) and secondary parity symbols (Y0´, Y1´), wherein sub-codes (Cij) of said QCTC are generated by:

independently interleaving said information symbols (x), said primary (Y0, Y1) and secondary (Y0´, Y1´) parity symbols,

multiplexing the interleaved primary parity symbols (Y0, Y1) to form alternating interleaved primary parity symbols ([Sbi _Y0(1), Sbi _Y1(1), Sbi _Y0(2), Sbi _Y1(2),...]) from said first and second constituent encoders and multiplexing the interleaved secondary parity symbols (Y0´, Y1´) to form alternating interleaved secondary parity symbols ([Sbi _Y0´(1), Sbi _Y1´(1), Sbi _Y0´(2), Sbi _Y1´(2),...]) from said first and second constituent encoders and

concatenating the interleaved code symbols to form a concatenated code symbol sequence ([A:B:C]), said concatenated code symbol sequence ([A:B:C]) comprising the interleaved information symbols ([Sbi _X(1), Sbi_X(2), Sbi _X(3),...]) followed by alternating interleaved primary parity symbols ([Sbi _Y0(1), Sbi _Y1(1), Sbi _Y0(2), Sbi _ Y1(2),...]) from said first and second constituent encoders and then followed by alternating interleaved secondary parity symbols ([Sbi _Y0´(1), Sbi _Y1´(1), Sbi _Y0´(2), Sbi _Y1´(2),...]) from said first and second constituent encoders,

so that the number of punctured parity symbols from the first constituent encoder (Y0, Y0´) is equal to the number of punctured parity symbols from the second constituent encoder (Y1, Y1´) or that the difference between said numbers is only one in the concatenated code symbol sequence ([A:B:C]) when a number of successive symbols in the concatenated code symbols sequence are punctured;

generating a sub-code (Cij) of a QCTC by selecting a predetermined number of consecutive symbols starting from the symbol next to the last symbol selected for the previous transmission in the concatenated symbol sequence ([A:B:C]) in order to create a sub-code with a given code rate, wherein

said selecting comprises puncturing all the symbols which are not necessary for creating said sub-code from the end of the concatenated code symbol sequence ([A:B:C]), or repeating the concatenated code symbol sequence ([A:B:C]) and puncturing all the symbols which are not necessary for creating said sub-code from the end of the repeated concatenated code symbol sequence;

said method comprising:

storing received sub-codes (C00, C10, C20, C21,...),

sequence combining the symbols of the stored sub-codes (Cij), wherein the number of code symbols in said generated symbol stream is the number N of codeword symbols output by said turbo code encoder, and wherein said combiner performs a reverse operation of the process of sequence repetition and symbol puncturing performed to generate the sub-codes (Cij), in order to generate the concatenated code symbol sequence ([A:B:C]) of codeword symbols;

separating the N combined codeword symbols of said code symbol sequence [A:B:C]) into an information symbol part ([Sbi _X(1), Sbi_X(2), Sbi _X(3),...]), a primary parity symbol part ([Sbi _Y0(1), Sbi _Y1(1), Sbi _Y0(2), Sbi _ Y1(2),...]) and secondary parity symbol part ([Sbi _Y0´(1), Sbi _Y1´(1), Sbi _Y0´(2), Sbi _Y1´(2),...]), de-multiplexing the separated primary and secondary parity symbol parts, respectively, to rearrange the codeword symbols in an information symbol part (x), a de-multiplexed primary parity symbol part (Y0, Y1) and a de-multiplexed secondary parity symbol part (Y0´, Y1´),

separating the information symbol part (x), the de-multiplexed primary parity symbol part (Y0, Y1) and the de-multiplexed secondary parity symbol part (Y0´, Y1´) into an information symbols stream (x) and separate primary and secondary parity symbol streams (Y0, Y0´, Y1, Y1´),

independently de-interleaving the information symbol stream (x) and the primary and secondary parity symbol streams (Y0, Y0´, Y1, Y1´)

multiplexing the independently de-interleaved information symbol stream (x) and the independently de-interleaved parity symbol streams (Y0, Y1, Y0´, Y1´),

decoding the multiplexed information symbol stream (x) and the parity symbol streams (Y0, Y1, Y0´, Y1´) according to the predetermined code rate of said turbo code encoder,

outputting the information symbol stream (x)."

Claims 10 to 12 are dependent on claim 9.

VII. The appellant's arguments relevant to the present decision may be summarized as follows:

The claimed subject-matter related to an apparatus and a method for receiving a sub-code of a quasi-complementary turbo code, QCTC, and for decoding the QCTC. The description as originally filed provided a clear definition of QCTC´s and, in fact, referred in detail to an apparatus and a method for generating sub-codes of a QCTC on the basis of information symbols encoded by a turbo encoder with a predetermined code rate. Thus, contrary to the understanding of the examining division, the application as originally filed sufficiently disclosed what was meant by the term "QCTC". As claims 1 and 9 specified how the sub-codes of a QCTC were generated from the turbo coded data, the independent claims defined all the features that were essential for a skilled person to unambiguously understand the claimed invention and to be able to carry it out. The requirements of Articles 83 and 84 EPC were thus satisfied.

In the course of the examination proceedings, the examining division had cited documents D1, D2 and D3. Document D1 constituted prior art in the sense of Article 54(3) EPC and was relevant only to establish the novelty of the claimed subject-matter. D1 was concerned with the generation of sub-codes of a QCTC but did not disclose a decoder for such sub-codes. Furthermore, it did not refer to the step of independently de-interleaving the separate streams of information symbols and primary and secondary parity symbols.

Thus, the subject-matter of claims 1 and 9 was new with respect to D1 within the meaning of Article 54(3) EPC.

D2 and D3 were not relevant to the patentability of the claimed invention as they had been published after the priority date of the present application.

The gist of the present invention consisted in generating from a turbo code a quasi complementary turbo code, QCTC, which had sub-codes with given code rates, and in providing an apparatus and a method for decoding the received sub-codes and obtaining the originally turbo coded information symbols. As the QCTC specified in the claims were not known in the prior art, it was not obvious to a person skilled in the art to arrive at an apparatus according to claim 1 or at a method as specified in claim 9. Thus, the claimed subject-matter involved an inventive step within the meaning of Article 56 EPC.

Reasons for the Decision

1. The appeal is admissible.

Article 83 EPC

2.1 The present application relates, inter alia, to the use of a "packet code combining technique" in a communication system which relies on turbo codes as forward error correction codes. As pointed out on page 2, lines 4 to 9, of the application as originally filed (all quotations hereafter refer to the original application documents), the "packet code combining technique transmits varying codes having a code rate R for each packet transmitted. Upon a receiver detecting an error in the received packet after decoding, the receiver stores the failed packet rather than discarding it, and then soft-combines the stored packet with a packet retransmitted by the transmitter. Here, different codes may be used for the retransmitted packet."

It is, in fact, known that it may be advantageous to use codes with different code rates R and code lengths when retransmitting packets of information.

2.2 The present application addresses in particular the problem of generating codes with different code rates and code lengths on the basis of a turbo code used for encoding information prior to its transmission. Such codes, which can be alternatively used when a failed packet is retransmitted in an ARQ (Automatic Repeat reQuest) packet communication system, are labelled in the present application "quasi-complementary turbo codes (QCTC)". According to page 6, lines 11 to 14, a "QCTC is defined as a complementary code generated using a turbo code. The QCTC is not a perfect complementary code as noted from the term "quasi" because a sub-code includes repeated symbols and has a different characteristic such as error correcting capability from another sub-code."

After a schematic explanation of the principles involved in the generation of a QCTC (page 6, line 20, to page 7, line 20), the present application (page 7, lines 20 to 23) points out that it "is difficult to implement a system to use the dispersed symbols as input to the puncturing and repetition block for generating the quasi-complementary turbo codes, and it is not easy to generate sub-codes satisfying the characteristics of a QCTC with the mixed symbols of X, Y0, Y1, Y0´ and Y1´ ". Thus, in order to solve this problem, the application "provides a method for generating the quasi - complementary turbo codes by a specific technique regardless of the code rate of the sub-codes" (page 7, lines 24 to 26).

2.3 As concluded by the examining division, the expression "quasi-complementary turbo codes" had not been generally known in the art before the priority date of the present application, but was first used in the context of the present invention to define codes of different code lengths and different code rates which were generated from a turbo code and had, inter alia, the property that by combining sub-codes of different QCTC´s the original turbo code used for generating them could be recovered.

In the opinion of the Board, however, a skilled person would be able to understand the term "QCTC" in the context of the invention, since it applies to sub-codes of predetermined code rates generated by means of a method which is explicitly disclosed in the application as originally filed.

2.4 The method for generating a QCTC according to the present application involves the following steps (see Figure 2):

- an encoder 201 generates information symbols X, first parity symbols Y0 and Y1 and second parity symbols Y0´ and Y1´ by encoding input information symbols (3072 information bits in the given example) (page 7, last paragraph and page 8, first paragraph);

- a de-multiplexer 202 de-multiplexes the codeword symbols X and the parity symbols Y0, Y1 and Y0´, Y1´ into 5 groups (page 8, second paragraph);

- the de-multiplexed symbols are provided to sub-block interleavers 204, 214, 224, 234 and 244, respectively;

- as specified in the description (page 8, lines 24 to 26), various sub-block interleaving methods can be used as long as the "Interleaved code symbols are partially punctured in such a way that the puncturing pattern of code symbols before interleaving has a uniform puncturing distance" ;

- the interleaved code symbols are then divided into three sub-groups A, B and C, whereby sub-group A contains the interleaved information symbols X, sub-group B is formed by multiplexing the interleaved parity symbols Y0 and Y1 (see (4) on page 11) and sub-group C is generated by multiplexing the interleaved parity symbols Y0´ and Y1´;

- as pointed out on page 11, lines 16 to 23, the reason for multiplexing the interleaved code symbols Y0 and Y1 or Y0´ and Y1´ is that when a sequence B or C is cut off by puncturing M successive symbols, the same number of parity symbols Y0 and Y1 (or Y0´ and Y1´) is punctured, if M is an even number, or the difference is only 1, if M is an odd number;

- a symbol concatenator 207 sequentially concatenates the sequences A, B and C and produces a sequence [A:B:C] comprising information symbols followed by alternating parity symbols Y0 and Y1 and then by alternating parity symbols Y0´ and Y1´ (see (8) on page 13);

- quasi-complementary turbo codes are generated on the basis of the symbol sequence [A:B:C]; in particular, a sub-code of a QCTC with a given code rate is obtained by "puncturing or pruning as many symbols as necessary from the end of the symbol sequence [A: B:C]", or by repeating this symbol sequence and then pruning as many symbols as necessary from the end of the repeated sequence (page 14, lines 6 to 8).

2.5 Examples of sub-codes of QCTC´s with different code rates (1/7, 2/7 and 4/7) are shown in Figure 2. The first sub-code of the first QCTC, which contains 21504 symbols is obtained by repeating the sequence [A:B:C] and by pruning the last 9216 symbols from the repeated sequence. Thus, it contains the 15360 symbols of the sequence [A:B:C] followed by the first 6144 symbols of the same sequence. The first sub-code of the second QCTC contains 10752 symbols and is generated by cutting off the last 4608 symbols from the sequence [A:B:C].

As pointed out on page 17, lines 16 to 19, it can be assumed that the first sub-code C00 of the first QCTC is used for initial transmission and that a repeat request is satisfied by transmitting the first sub-code C10 of the second QCTC and a further request by the first sub-code C20 of the third QCTC.

According to the "adaptive QCTC scheme" proposed in the present application, a sub-code of a QCTC with a predetermined code rate is generated starting with the symbol following the last symbol used for the previous transmission (page 17, line 25 to page 18, line 1).

2.6 Though the description appears to imply that other puncturing schemes might be applied to the sequence [A:B:C] to generate sub-codes of a QCTC, as long as the resulting code satisfies a number of conditions (see page 13, line 10 to page 14, line 4), the only method for obtaining such sub-codes, which is actually clearly disclosed in the application, is the one summarized in item 2.4 of this decision. It relies on "repeating and puncturing as many symbols as needed in the symbol sequence [A:B:C]" (page 14, lines 8 to 11).

3.1 According to the description (page 21, lines 9 to 21), Figure 4 illustrates a structure of a receiver for receiving data transmitted by the transmitter of Figure 1. Sub-codes with different code rates are sent to a "QCTC processor 411" which "depunctures" and combines the received sub-codes in order to convert them into the original turbo codes with the initial code rate R.

3.2 The essential operations performed by the receiver on the transmitted sub-codes are as follows (see Figure 5):

- the received sub-codes are stored in a buffer, whose size depends on the number N of symbols contained in a codeword of the initial turbo code (page 22, line 24 to page 23, line 7);

- a sequence combiner/symbol combiner 502 performs on the stored sub-codes the reverse operations of the symbol repeater 308 and symbol puncturer 309 of the transmitter in order to restore the codeword sequence [A:B:C] generated in the transmitter (page 23, lines 9 to 16);

- after "group separation", "de-multiplexing for parity symbols", "sub-block de-interleaving" and "multiplexing of all code symbols in the original order", the codeword generated in the transmitter by turbo coding the original information bits is retrieved (cf. Figure 6).

Therefore, the receiver carries out essentially the inverse operations performed by the transmitter when it generates sub-codes of QCTC´s on the basis of turbo coded information bits.

3.3 As the originally filed application explicitly discloses a method for producing sub-codes of a QCTC based on the repetition and puncturing of a certain sequence of information and parity symbols obtained from a turbo code of an initial information packet, an apparatus and a method specifically designed to perform the inverse operations on the sub-codes thus generated are also clearly and sufficiently disclosed (Article 83 EPC).

Article 84 EPC

4.1 Claim 1 relates to an apparatus for receiving sub-codes of a quasi-complementary code, QCTC, generated as specified by the wording of the claim. The apparatus according to claim 1 essentially comprises a "sequence combiner", a channel de-interleaver" and a "code decoder" for `reversing´ the operations required for generating the sub-codes in order to retrieve the originally turbo encoded information.

4.2 Similarly, claim 9 is directed to a method for receiving sub-codes of a quasi-complementary turbo code, QCTC, generated as specified in the claim. The claimed method comprises all the steps for performing on the sub-codes the reverse operations required for retrieving the originally turbo encoded information.

4.3 In the opinion of the Board, the claims now clearly define the matter for which protection is sought and are supported by the description in accordance with the requirements of Article 84 EPC.

Article 123(2) EPC

5.1 The definition of a QCTC given in claims 1 and 9 and the steps for generating sub-codes of a QCTC specified in these claims are based on the description as originally filed (see item 2.4 of this decision).

The features of the apparatus, in particular the sequence combiner, the channel de-interleaver and the code decoder, specified in claim 1 are shown in Figure 4. Their functions are described on page 21, line 9 to page 22, line 18 of the application documents and illustrated in Figure 5.

The steps of the method recited in claim 9 correspond essentially to the description page 23, line 8 to page 25, line 3 and page 27, line 9 to page 28, line 4.

5.2 All amendments to the description as originally filed are solely directed to bringing it into conformity with the new independent claims and thus do not add new subject-matter.

5.3 In the result the Board considers that the amended application documents satisfy the requirements of Article 123(2) EPC.

Novelty and inventive step

6.1 Document D1 is state of the art within the meaning of Article 54(3) EPC and thus of relevance only as far as the novelty of the subject-matter of claims 1 and 9 of the present application is concerned.

Though D1 relates to an apparatus and a method for generating sub-codes of a QCTC as specified in the present application, it does not disclose an apparatus or a method for receiving these sub-codes and retrieving the encoded information.

6.2 The subject-matter of claims 1 and 9 is thus new with respect to D1 within the meaning of Article 54(3) EPC.

7.1 As to the other documents on file, either they do not relate to sub-codes of a QCTC, as specified in the application documents, or, if they do (see D2 and D3), they were published after the priority date of the present application and thus are not comprised in the state of the art within the meaning of Article 54(2) EPC.

7.2 Since there is no available prior art relating to a quasi-complementary turbo code according to the present invention, it appears that such codes were not known before the priority date of the present application. Consequently, it was not obvious to a person skilled in the art to arrive at an apparatus or a method specifically directed to receiving sub-codes generated as disclosed in the present application and specified in claims 1 and 9.

7.3 Hence, the subject-matter of claims 1 and 9 involves an inventive step within the meaning of Article 56 EPC.

8. Claims 2 to 8 and 10 to 12, are dependent on claims 1 and 9, respectively. As they represent different embodiments of an apparatus and a method which are both new and inventive, they also satisfy the requirements of Articles 54 and 56 EPC.

9. In the result, the Board considers that the application documents on file satisfy the requirements of the EPC and that a patent can be granted on the basis thereof, as requested by the appellant.

ORDER

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the department of first instance with the order to grant a patent in the following version:

Claims: 1 to 12 received during the oral proceedings of 28 September 2007;

Description: pages 1, 4a, 5, 6, 8, 18 received during the oral proceedings of 28 September 2007,

pages 4 and 28 as filed with letter dated 2 February 2004,

pages 2, 3, 7, 9 to 17 and 19 to 27 as originally filed;

Drawings: Figures 1 to 7 as originally filed.