T 0376/03 () of 7.3.2005

Summary of Facts and Submissions

I. The applicant filed an appeal against the decision of the examining division to refuse European patent application Nr. 98 964 255.8.

II. The reason given for the refusal was that the subject- matter of the claims lacked novelty in view of the prior art disclosed in:

pages 258 to 261 (D1) and 235 to 238 (D2) of the book by George C. Clark, Jr. and J. Bibb Cain "Error- Correction Coding for Digital Communications", Plenum Press, New York and London, 1981.

III. The appellant requests the grant of a patent in the following version:

Description

Pages 1, 2 and 4 to 10 as originally filed.

Pages 2a and 3 filed with a letter of 28 February 2005.

Pages 3a and 11 filed with a letter of 25 February 2005.

Claims

No. 1 to 10 filed with the letter of 28 February 2005.

Drawings

Sheets 1/3 to 3/3 as originally filed.

IV. Claim 1 reads as follows:

"A method of decoding an encoded signal transmitted over a channel to determine a source data signal using a non-binary trellis with a plurality of nodes, comprising the steps of:

designating a plurality of binary butterfly trellises within the non-binary trellis, including:

- designating a first binary butterfly trellis having two beginning nodes represented in the non- binary trellis as at a first unit period of time and having two ending nodes represented in the non-binary trellis as at a second unit period of time;

- designating a second binary butterfly trellis having two alternate beginning nodes represented in the non-binary trellis as at the first unit period of time and having said two ending nodes represented in the non-binary trellis as at the second unit period of time;

performing a binary butterfly operation for each designated binary butterfly trellis to determine a most favorable path metric associated with each ending node in each designated binary butterfly trellis such that each ending node will have a plurality of most favorable path metrics associated therewith; and

comparing the plurality of most favorable path metrics associated with each ending node to select a survivor path for each ending node."

Claim 7 reads as follows:

"An apparatus for decoding an encoded signal transmitted over a channel to determine a source data signal, based on a non-binary trellis with a plurality of nodes, comprising:

a first processor for performing a binary butterfly operation for a binary butterfly trellis and determining a most favorable path metric associated with each ending node of the binary butterfly trellis; and

a second processor for designating a plurality of binary butterfly trellises within the non-binary trellis, including designating a first binary butterfly trellis having two beginning nodes represented in the non-binary trellis as at a first unit period of time and having two ending nodes represented in the non- binary trellis as at a second unit period of time and designating a second binary butterfly trellis having two alternate beginning nodes represented in the non- binary trellis as at the first unit period of time and having said two ending nodes represented in the non- binary trellis as at the second unit period of time, for instructing the first processor to perform the binary butterfly operation on the plurality of binary butterfly trellises designated within the non-binary trellis and for comparing the plurality of most favorable path metrics associated with each ending node to select a survivor path for each ending node."

Claims 2 to 6 are dependent on claim 1 and claims 8 to 10 on claim 7.

V. The appellant essentially argued as follows:

The invention related to receivers in a digital communication system and specifically to decoders for decoding non-binary convolutional coded data using a modified Viterbi algorithm, whereby it was a problem underlying the invention to efficiently decode non- binary convolutional coded data.

Document D1 indicated on page 261, second paragraph, that an ACS (add-compare-select) circuit for a R = (n - 1)/n code might contain multiple elements in the form of Figure 6-23 (page 259 of D1), which corresponded to the basic module (a binary butterfly trellis) of Figure 6-22. Document D2 showed in Figure 6-7 a non-binary trellis structure having four states, with four paths entering each state. According to D2, the operation of the Viterbi algorithm in that case was the same as in the case of a binary trellis except that at each node a single best path out of four possibilities had now to be selected, leading to a 4- ary rather than a 2-ary comparison. D2 then stated that the 4-ary comparison constituted a fairly serious implementation difficulty if encountering high data rates. Such data rates might be encountered for example in mobile telephone systems. As a solution to this problem, D2 taught to perform a "puncture" technique in order to reduce the number of comparisons needed, a suitable deletion of symbols leading to being able to use a single ACS (add-compare-select) circuit as shown in Figure 6-23.

The invention disclosed a solution for efficient handling of a non-binary trellis diagram by designating binary butterfly trellis within the non-binary trellis. Decoding of the signal followed a two-stage process, wherein in a first stage most favourable path metrics associated with designated binary butterfly trellises were determined and in the second stage the most favourable path metrics were compared to select the survivor path for the node in the non-binary trellis. Due to the designation of the binary butterfly trellises and the two stage operation for determining a survivor path for the node in the non-binary trellis, the individual processing operations of the binary butterfly trellises could for example be executed in parallel, thus simplifying or reducing hardware requirements.

Document D1 only generally taught that an ACS circuit for a larger non-binary trellis structure (e.g. Figure 6-7) could include multiple smaller elements of the form of Figure 6-23. Accordingly, starting from D1, the person skilled in the art was faced with the objective problem of how to break-down a non-binary trellis into binary trellises and how to obtain the survivor path. D1 did not give any hint as to how binary butterfly trellises could be designated in a non-binary trellis or how to select a survivor path. Thus, D1 did not contain any explicit or implicit teaching leading to the features of the independent claims. The puncture technique taught by D2 was in clear contrast to the invention, which broke the non- binary trellis into binary trellises that could be much more easily handled, e.g. in a parallel computing scheme. Thus, document D2 led the skilled person away from the invention.

Reasons for the Decision

1. The appeal is admissible.

2. Amendments

Claim 1 now includes all the features of claim 1 of the application as originally filed, plus details of the step of designating a plurality of binary butterfly trellises within the non-binary trellis as specified in claim 4 of the application as filed. Present claim 1 also indicates that the most favourable path metrics are associated with the ending nodes as is apparent in particular from claims 5 and 6 of the application as filed.

The present independent claim 7 includes all the features of claim 10 of the application as filed. Furthermore, the function of the second processor regarding designating a plurality of binary butterfly trellises within the non-binary trellis is as specified in claim 4 of the application as filed. Claim 7 also indicates that the most favourable path metrics are associated to the ending nodes, as is apparent from the application as filed.

Present dependent claims 2 to 6 respectively correspond to claims 2, 3, 7, 8 and 9 of the application as filed. Present claim 8 corresponds to claim 11 as filed, whereby the wording of present claim 8 has been harmonised with the wording used in present claim 2. Present claims 9 and 10 respectively correspond to claims 12 and 13 of the application as filed.

The description of the application has been amended to acknowledge the background art known from D1 and D2 (whereby, in order to properly reflect the name of one of the authors of the book containing D1 and D2, "Georges" should be amended to read "George" in lines 1 and 9 of page 2a of the description). The description has also been amended for consistency with the wording of the claims.

Thus, the amendments do not extend beyond the content of the application as filed and do not contravene Article 123 (2) EPC.

3. Novelty

D2 discusses non-binary convolutional codes having a code rate R = m/n with m > 1 and shows in Figure 6-7 the trellis structure for a rate 2/3, k = 4 code with four paths entering each state rather than two as in the R = 1/2, k = 3 case. D2 indicates that the operation of the Viterbi algorithm is the same except that at each node the single best path out of the four possibilities must be selected, i.e. a 4-ary rather than a 2-ary comparison must be made. D2 adds that this turns out to be a fairly serious implementation difficulty, particularly at high data rates (several Mb/s). According to D2, the key to simplifying the algorithm is to take a R = 1/n code and "puncture" or delete certain channel symbols, thereby producing a R = m/n code. Figure 6-8 shows the trellis diagram of a rate 2/3, k = 4 code produced by periodically deleting symbols from a rate 1/2, k = 3 code, whereby the transmitted symbols are identical in Figures 6-7 and 6- 8. In this case, the direct method (Figure 6-7) requires four 4-ary comparisons (each equivalent to three 2-ary comparisons) while the punctured code approach (Figure 6-8) uses two levels of four 2-ary comparisons. Hence, according to D2, there is a 3:2 advantage with the punctured code approach.

D1 observes that an ACS (add-compare-select) circuit for a R = (n - 1)/n code would normally contain multiple elements of the form of Figure 6-23 (i.e. an ACS circuit corresponding to a binary butterfly trellis). D1 continues stating that however, if one uses the "punctured code approach", then the structure of Figure 6-23 is all that is needed. Thus, the use of punctured codes for higher rate implementations results in a significantly simpler ACS circuit.

Thus, neither D2 nor D1 discloses designating first and second binary butterfly trellises within a non-binary trellis in the manner specified in the independent claim 1 and 7. The subject-matter of claims 1 and 7 is therefore considered to be new in the sense of Article 54. (1) EPC.

4. Inventive step

It is known from D2 that the operation of the Viterbi algorithm meets difficulties in the case of a non- binary trellis. D1 and D2 suggest solving this problem by using a punctured code approach, which results in a binary trellis structure for decoding. By contrast, the invention defined in claims 1 and 7 solves the problem in particular by designating specific binary butterfly trellises in the non-binary trellis, so that it is possible to perform in parallel the calculations associated with the designated binary butterfly trellises. Thus, the board does not see any reason why, having regard to the state of the art disclosed in D1 and D2, the subject-matter defined in claims 1 and 7 would be obvious to a person skilled in the art. The subject-matter of claims 1 and 7 is therefore considered to involve an inventive step in the sense of Article 56 EPC.

5. By virtue of their dependency on claim 1 or claim 7, the subject-matter of claims 2 to 6 and 8 to 10 is also considered to be new and involve an inventive step.

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 1, 2 and 4 to 10 as originally filed.

Pages 2a and 3 filed with the letter of 28 February 2005, whereby in line 1 and line 9 of page 2a "Georges" is to be amended to read "George".

Pages 3a and 11 filed with the letter of 25. February 2005.

Claims

No. 1 to 10 filed with the letter of 28 February 2005.

Drawings

Sheets 1/3 to 3/3 as originally filed.