T 0554/04 () of 27.1.2006

Summary of Facts and Submissions

I. This is an appeal of the applicant against the decision of the examining division to refuse European patent application No. 99 962 544.5.

II. The reason given for the refusal was that the subject-matter of the claims did not involve an inventive step.

III. The decision under appeal cited the following prior art documents:

D1: "Rational Rate Punctured Convolutional Codes for Soft-Decision Viterbi Decoding" by Irina E. Bocharova and Boris D. Kudryashov, published in the IEEE Transactions on Information Theory, vol. 43, No. 4, July 1997, pages 1305 to 1313; and

D2: "Rate-Compatible Punctured Convolutional Codes (RCPC Codes) and their Applications" by Joachim Hagenauer, published in the IEEE Transactions on Communications, vol. 36, No. 4, April 1988, pages 389 to 400.

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

Description

Pages 2, 3 and 6 to 11 as originally filed,

Pages 1 and 12 filed with a letter of 20 October 2003,

Pages 4, 4a and 5 filed with a letter of 9 January 2006.

Claims

No. 1 to 10 filed with the letter of 9 January 2006.

Drawings

Sheets 1/3, 2/3 and 3/3 as originally filed.

Subsidiarily, the appellant requests oral proceedings.

V. The application in its present form includes four independent claims. The independent claims 1 and 7 read as follows:

1. "A convolutional encoding device (125) in a digital system, comprising:

a convolutional encoder (130) for generating a subgroup of three encoded symbols C0, C1 and C2 for each input bit using generator polynomial g0(x)=1+x**(2)+x**(3)+x**(5)+x**(6)+x**(7)+x**(8) for generating a first code symbol C0, generator polynomial g1(x)=1+x+x**(3)+x**(4)+x**(7)+x**(8) for generating a second code symbol C1, and generator polynomial g2(x)=1+x+x**(2)+x**(5)+x**(8) for generating a third code symbol C2, for inputting input bits to generate a symbol group of three subgroups for three successive input bits, and for generating a stream of the symbol groups,

characterised in that

the device further comprises a symbol puncturer (135) for deleting the first code symbol C0 in one of the three subgroups in each symbol group generated from said convolutional encoder."

7. "A convolutional encoding method in a digital system, comprising:

generating a subgroup of three encoded symbols C0, C1 and C2 for each input bit using generator polynomial g0(x)=1+x**(2)+x**(3)+x**(5)+x**(6)+x**(7)+x**(8) for generating a first code symbol C0, generator polynomial g1(x)=1+x+x**(3)+x**(4)+x**(7)+x**(8) for generating a second code symbol C1, and generator polynomial g2(x)=1+x+x**(2)+x**(5)+x**(8) for generating a third code symbol C2;

inputting input bits to generate a symbol group of three subgroups for three successive input bits;

generating a stream of the symbol groups,

characterised in that

each generated symbol group is punctured by deleting the first code symbol C0 in one of the three subgroups."

The pre-characterising portions of the independent claims 4 and 9 are identical to the pre-characterising portions of claims 1 and 7, respectively. The characterising portions of claims 4 and 9 read as follows:

claim 4:

"characterised in that the device further comprises a symbol puncturer (135) for deleting the second code symbol C1 in one of the three subgroups in each symbol group generated from said convolutional encoder."

claim 9:

"characterised in that each generated symbol group is punctured by deleting the second symbol C1 in one of the three subgroups."

Claims 2 and 3 are dependent on claim 1, claims 5 and 6 on claim 4, claim 8 on claim 7 and claim 10 on claim 9.

VI. The appellant essentially argued as follows:

The CDMA 2000 standard disclosed a convolutional encoder with constraint length k=9 and code rate R=1/3, which used generator polynomials g0, g1 and g2 as set out in the pre-characterising portions of the independent claims of the present application. A puncturer deleted every ninth symbol of an encoded sequence, more precisely every third symbol generated by generator polynomial g2. By contrast, the independent claims 1 and 7 specified deleting every third symbol generated by generator polynomial g0, and independent claims 4 and 9 every third symbol generated by generator polynomial g1. The object of the invention was to improve the channel coding specified by the CDMA 2000 standard in terms of bit error rate. The CDMA 2000 standard did not provide any hint in which way the encoder or the puncturer could be modified in order to improve channel coding. Regarding the encoder, the skilled person had the choice among different encoder types, code rates, constraint length or generator polynomials. Regarding the puncturer, the skilled person had the choice among different puncturer periods, number of punctured bits or puncturing patterns. From the teaching of document D1, it was clear that simulation techniques involving all parameters of the encoder and the puncturer were complex, so that exhaustive searches could not always be performed, but mostly merely random searches. Table XV of D1, which referred to convolutional codes of rate 3/8 like the invention, showed that an increased free distance could be obtained by increasing the constraint length. D1 did not provide any hint that the error rate could be improved by modifying the puncturing scheme. Part III of document D2 gave some criteria for judging RCPC codes and indicated that slightly better codes could be obtained by increasing the puncturing period P. Part III of D2 also stated that time-varying codes were better than fixed codes and that time-varying codes became better with increasing time periods. Both D1 and D2 pointed into completely different directions than the invention and did not carry any reasonable expectation of success that modifying the puncturing pattern in the way proposed by the invention would result in an improvement of the bit error rate.

Reasons for the Decision

1. The appeal is admissible.

2. Present independent claims 1, 4, 7 and 9 correspond to the independent claims 1, 3, 5 and 7 of the application as originally filed, whereby the claims are now drafted in two-part form. Present claims 2, 3, 5, 6, 8 and 10 correspond to originally filed claims 2, 9, 4, 11, 6 and 8, respectively, whereby present claims 3 and 6 are now drafted as dependent claims.

The description has been amended to acknowledge the background art known from the documents D1 and D2 and to be consistent with the present claims.

Thus, the amendments to the application do not introduce subject-matter extending beyond the content of the application as filed, and do not contravene Article 123(2) EPC.

3. According to the appellant, the CDMA 2000 standard discloses a convolutional encoding device and method using the generator polynomials g0(x), g1(x) and g2(x) set out in the pre-characterising portions of the independent claims, for generating a subgroup of three encoded symbols C0, C1 and C2 for each input bit. According to the appellant, the CDMA 2000 standard further discloses puncturing a symbol group formed by three subgroups for three successive input bits by deleting the ninth symbol of the symbol group (i.e. a symbol C2 generated by polynomial g2(x)).

4. The present invention uses a different puncturing pattern than the CDMA 2000 standard. In particular, the independent claims of the present application specify that either the first symbol (i.e. a symbol C0 generated by polynomial g0(x)) or the second symbol (i.e. a symbol C1 generated by polynomial g1(x)) of one subgroup in each symbol group is deleted. The documents D1 and D2 do not disclose the generator polynomials or the particular puncturing patterns specified in the independent claims of the present application. The subject-matter of these claims is therefore considered to be new in the sense of Article 54(1) EPC.

5. According to the present application, the puncturing patterns of the invention lead to a lower bit error rate (BER) as compared to the puncturing pattern of the CDMA 2000 standard. Thus, taking the channel coding known from the CDMA 2000 standard as a starting point for the assessment of inventive step, the objective problem solved by the invention can be seen in improving the channel coding in terms of bit error rate.

6. D1 concerns rational rate punctured convolutional codes and provides lists of convolutional codes that have been obtained by searching. In particular, table XV in page 1310 of D1 provides a list of convolutional codes of rate 3/8 and table III on page 1306 a list of convolutional codes of rate l/3l, l=1, 2. None of the codes listed in D1 uses the generator polynomials specified in the present application. As regards the puncturing pattern, D1 indicates that punctured codes are obtained by periodically deleting bits from low-rate 1/no convolutional codes (see the penultimate sentence in the left-hand column of page 1305 of D1). D1 does not indicate the specific puncturing patterns used for the listed codes.

7. D2 concerns rate-compatible punctured (RCPC) codes. RCPC codes constitute a specific class of time-varying codes with a fixed generator but time-varying puncturing. D2 states in particular that some improvement may be possible by using a higher period P. Section III of D2 reports the results of a computer search for families of RCPC codes. Section III states that no constructive method is known for determining the generator matrix and the puncturing matrices for a RCPC code family. Tables I and II of D2 contain the puncturing tables for RCPC code families found by the computer search. None of these puncturing tables is arranged for deleting one out of nine code symbols.

8. Convolutional codes are essentially defined by their generator polynomials and, if punctured, also by their puncturing matrices. D1 and D2 show that different convolutional codes, based on different generator polynomials and possibly different puncturing matrices, can be evaluated by means of computers. D1 does not provide any indication as to which puncturing matrix would be optimal for a code with given generator polynomials. D2 merely indicates that higher puncturing periods P might improve the code. Thus, having regard to D1 and D2, in the view of the board it is not obvious to a person skilled in the art to evaluate the effects of different puncturing matrices that have the same period on a code with given generator polynomials. Furthermore, in view of the suggestion in D2 to use higher puncturing periods to improve the code, it is surprising that the puncturing claimed in the present application achieves a better BER performance than the puncturing provided in the CDMA 2000 standard (which has the same period).

9. The invention specified in the independent claims 1, 4, 7 and 9 is therefore considered as involving an inventive step in the sense of Article 56 EPC.

The subject-matter of dependent claims 2, 3, 5, 6, 8 and 10 is thereby also to be considered as being new and involving an inventive step.

Oral proceedings are not necessary since the patent can be granted in the form 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 first instance with the order to grant a patent in the following version:

Description

Pages 2, 3 and 6 to 11 as originally filed,

Pages 1 and 12 filed with the letter of 20 October 2003,

Pages 4, 4a and 5 filed with the letter of 9 January 2006.

Claims

No. 1 to 10 filed with the letter of 9 January 2006.

Drawings

Sheets 1/3, 2/3 and 3/3 as originally filed.