T 2318/10 () of 11.12.2014

Summary of Facts and Submissions

I. The applicant lodged an appeal, received on 24 August 2010, against the decision of the Examining Division, posted on 25 June 2010, refusing the application No. 00307366.5. The statement setting out the grounds of appeal was received on 5 November 2010.

II. The Examining Division held that the application did not meet the requirements of Articles 123(2) and 84 EPC, and that the subject-matter of claims 1 and 8 did not involve an inventive step having regard to document:

D1: H.-L. Lou: "Implementing the Viterbi Algorithm, Fundamentals and real-time issues for processor designers" IEEE Signal Processing Magazine, New York, US, vol.12, no.5, 1 September 1995, pages 42 to 52.

III. In an annex to the summons to oral proceedings dated 10 September 2014 the Board pointed out some apparent errors in equations in the description and the claims, and expressed the preliminary opinion that the subject-matter of claim 1 of the main request might be obvious in the light of document D1.

IV. With a letter dated 11 November 2014 the appellant filed amended description pages and new sets of claims of a main request and an auxiliary request.

V. Oral proceedings were held before the Board as scheduled on 11 December 2014. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the claims of the main request filed with letter dated 11 November 2014, or that a patent be granted in the following version:

- description, pages 1, 2, 2a, 3 to 16 filed in the oral proceedings of 11 December 2014;

- claims: 1 to 8 of the first auxiliary request filed with letter dated 11 December 2014;

- drawings: sheets 1/5 to 5/5 as originally filed.

VI. Claim 1 of the main request reads as follows:

"A decoder (10) for processing a sequence of received symbols, the decoder comprising:

a branch metric calculation unit (12) for computing branch metrics associated with transitions between states of a multi-stage trellis representation of a state machine, wherein at least a non-empty subset of the branch metrics correspond to a linear distance between a given one of the received symbols and its nearest codeword in a given stage of the trellis;

an add-compare-select unit (14) having an input coupled to an output of the branch metric calculation unit, the add-compare-select unit utilizing the linear distance branch metrics generated by the branch metric calculation unit for a current stage of the trellis, and a path metric generated for a previous stage of the trellis, for comparison purposes in determining a survivor path and corresponding updated path metric for the current stage of the trellis; and

a traceback unit (16) having an input coupled to an output of the add-compare-select unit, the traceback unit generating an output for a given stage of the multi-stage trellis based on the path metric determined for that stage;

wherein a given one of the linear distance branch metrics corresponds to a transition from state i to state j in stage n of the trellis;

characterized in that

the survivor path is determined utilizing one of the following computations (1) and (2) involving the linear distance branch metrics, with computation (1) being used for trellis codes with infinite constellations and computation (2) being used for trellis codes with finite constellations:

FORMULA/TABLE/GRAPHIC

(2) DeltaM =

FORMULA/TABLE/GRAPHIC

where yn,m denotes an m**(th)-dimensional received symbol at stage n, Pijnm denotes a nearest codeword in a coset Ci,j to the m**(th)-dimensional received symbol, yn,m, at stage n, Mj,n denotes a path metric for state j at stage n, DeltaM denotes a path metric difference, si = sign(yn,m - Pi,j,n,m), and sk = sign(yn,m - Pk,j,n,m)."

Claims 2 to 7 are dependent on claim 1.

Claim 8 is a method claim comprising functional features corresponding to the features of the decoder claimed in claim 1.

Claims 9 to 14 are dependent on claim 8.

VII. Claim 1 of the auxiliary request reads as follows:

"A decoder (10) for processing a sequence of received symbols, the decoder comprising:

a branch metric calculation unit (12) for computing branch metrics associated with transitions between states of a multi-stage trellis representation of a state machine, wherein at least a non-empty subset of the branch metrics correspond to a linear distance between a given one of the received symbols and its nearest codeword in a given stage of the trellis;

an add-compare-select unit (14) having an input coupled to an output of the branch metric calculation unit, the add-compare-select unit utilizing the linear distance branch metrics generated by the branch metric calculation unit for a current stage of the trellis, and a path metric generated for a previous stage of the trellis, for comparison purposes in determining a survivor path and corresponding updated path metric for the current stage of the trellis; and

a traceback unit (16) having an input coupled to an output of the add-compare-select unit, the traceback unit generating an output for a given stage of the multi-stage trellis based on the path metric determined for that stage;

wherein a given one of the linear distance branch metrics corresponds to a transition from state i to state j in stage n of the trellis;

characterized in that

the survivor path is determined utilizing the following computation for trellis codes with finite constellations:

DeltaM =

FORMULA/TABLE/GRAPHIC

where yn,m denotes an m**(th)-dimensional received symbol at stage n, Pijnm denotes a nearest codeword in a coset Ci,j to the m**(th)-dimensional received symbol, yn,m, at stage n, Mj,n denotes a path metric for state j at stage n, DeltaM denotes a path metric difference, si = sign(yn,m - Pi,j,n,m), and sk = sign(yn,m - Pk,j,n,m)."

Claims 2 to 4 are dependent on claim 1.

Claim 5 reads as follows:

"A method of processing a sequence of received symbols, the method comprising the steps of:

computing branch metrics associated with transitions between states of a multi-stage trellis representation of a state machine, wherein at least a non-empty subset of the branch metrics correspond to a linear distance between a given one of the received symbols and its nearest codeword in a given stage of the trellis;

utilizing the linear distance branch metrics for a current stage of the trellis, and a path metric generated for a previous stage of the trellis, for comparison purposes in determining a survivor path and corresponding updated path metric for the current stage of the trellis, such that a level of performance achieved using the linear distance branch metric is substantially equivalent to that achieved using squared distance branch metrics; and

generating an output for a given stage of the multi-stage trellis based on the path metric determined for that stage;

wherein a given one of the linear distance branch metrics corresponds to a transition from state i to state j in stage n of the trellis;

characterized in that

the survivor path is determined utilizing the following computation for trellis codes with finite constellations:

DeltaM =

FORMULA/TABLE/GRAPHIC

where yn,m denotes an m**(th)-dimensional received symbol at stage n, Pijnm denotes a nearest codeword in a coset Ci,j to the m**(th)-dimensional received symbol, yn,m, at stage n, Mj,n denotes a path metric for state j at stage n, DeltaM denotes a path metric difference, si = sign(yn,m - Pi,j,n,m), and sk = sign(yn,m - Pk,j,n,m)."

Claims 6 to 8 are dependent on claim 5.

VIII. The appellant argued essentially as follows:

From the very beginning, i.e. the drafting of the present patent application, the teaching of Dl had been taken into account. As stated on the original description page 2, lines 22 to 24, the absolute distances which were proposed in Dl for use as branch metrics, had the undesirable effect of reducing the performance of the Viterbi decoder.

In view of Dl the objective technical problem was to provide a more efficient branch metric representation which simplified the decoder without compromising its performance (original description page 2, lines 27 to 28). The performance was achieved by reducing the computation amount.

On page 45, second paragraph Dl stated that equation (4) might be simplified further, depending on the nature of the transition output symbols Ci,j, and afterwards described two such cases (case I and case II). In particular, in case I the transition output symbols were assumed to be binary and to be represented by -a and a. In case II the transition output symbols were considered as Ci,j epsilon {b, b + k} where k>0, i.e. the transition output symbols were either b or b+k. Only in the case II did Dl derive a simplified equation (6) which required only addition operations or table-lookup operations to compute the branch metrics (cf. Dl, page 45, right hand column, text below equation (6)). It was exactly this case II which was referred to by Dl when stating "Note that depending on the arrangement of the code words in a given code set, one might be able to use absolute linear distances, rather than squared distances, as branch metrics" (see case II above and bridging paragraph of pages 46 and 47 of D1).

Beyond the passages cited above, Dl did not provide any further details regarding an approach that would have prompted the skilled person, faced with an objective technical problem to simplify a decoder without compromising its performance, to provide a decoder falling under the new claim 1 of the main request.

In particular, Dl did not provide any hint that would have led a person skilled in the art to the considerations provided on page 7 to page 9, second paragraph of the present application. Further, Dl did not provide any hint that would have prompted the skilled person, faced with the objective technical problem, to determine a survivor path by involving linear distance branch metrics for finite constellations and infinite constellations according to computations (1) and (2) of the new claim 1 of the main request.

Hence, the new claim 1 of the main request involved an inventive step. Since the independent method claim 8 included similar features, also the new method claim 8 of the main request involved an inventive step.

The appellant had removed the reference to computation (1) and the trellis codes with infinite constellations from the independent claims of the first auxiliary request. Since the features of the independent claims 1 and 5 of the auxiliary request were already included in independent claims 1 and 8 of the main request, the respective arguments provided with regard to the main request applied mutatis mutandis to the independent claims 1 and 5 of the first auxiliary request. Hence, for this reason independent claims 1 and 5 of the first auxiliary request involved an inventive step.

Reasons for the Decision

1. The appeal is admissible.

2. Main request

2.1 The invention of the present application aims at providing improved representation of branch metrics, based on "linear distance" (cf. section [0008] of the published application) and at simplifying the computation of branch metrics by avoiding the use of Euclidean distance.

"Linear distance" branch metrics are an alternative to the conventional "Euclidean distance" branch metrics, (cf. sections [0013] and [0018] of the published application) and allow a decoder to use adders rather than multipliers (cf. section [0010]).

"Linear distance" branch metrics are implicitly defined in section [0023] which recites that "...the branch metric can be computed one dimension at a time and then the sum of these one-dimensional branch metrics is the branch metric for the multi-dimensional symbol". This type of metrics is sometimes called "Manhattan metrics" or "linear metrics" and is well known to a person skilled in the art.

2.2 The general principle behind the claimed invention was disclosed in D1 by H.-L. Lou, recorded as inventor for the present application (cf. D1, in particular equations (3), (5) and (6) and sections "step I: Branch Metric Generation" at page 44 and sections "case I" and "case II" at page 45). D1 recites in particular (cf. case II) that "the branch metric can be represented as the distance between the noisy symbol and the output symbol of the given transition" and that "the branch metrics can be computed one dimension at a time". It also mentions in the passage spanning pages 46 and 47 the use of "absolute linear distances, rather than squared distances, as branch metrics". Hence, D1 discloses a branch metric calculation involving linear distances.

2.3 D1 not only acknowledges that computing one dimension at a time (i.e. using linear distance) is an acceptable solution, but also recites that the calculation of case II according to equation (6) involves only addition operations or table-lookup operations, and that this property can be applied to computing the branch metrics of some trellis codes when their branch metrics can be computed one dimension at a time and the codewords in each given dimension are either b or (b+k), whereby the value of b can be different in different dimensions (cf. D1, paragraph following equation (6) on page 45, right hand column). Hence a person skilled in the art is taught that the difference of the branch metrics for an m**(th)-multidimensional value can be calculated by summing the differences of the branch metrics calculated for each dimension, i.e. by summing the difference B'i,j,n - B'k,j,n for each dimension according to the equations shown at lines 1 to 4 of the right-hand column of page 45 of D1, namely

B'i,j,n-B'k,j,n = 0 for Ci,j = Ck,j

B'i,j,n-B'k,j,n =(yn-b)-((b+k)-yn) for Ci,j = b and Ck,j = (b+k)

B'i,j,n-B'k,j,n =((b+k)-yn)-yn+b) for Ci,j= (b+k) and Ck,j= b

2.3.1 A person skilled in the art aware of D1 and aiming at improving further the performance of the Viterbi decoder disclosed therein, i.e. reducing the computing time and complexity of the said decoder, would look for a possibility to simplify the calculation of the sum of these differences.

2.3.2 The second equation above corresponds to the case cited at the bottom of page 10 of the published application wherein Pi,j,n and Pk,j,n could be renamed respectively Ci,j and Ck,j,

whereby (Pk,j,n - Pi,j,n) = (Ck,j - Ci,j) > 0.

In this case (b+k)-yn >0 and yn-b>0 and consequently

(b+k)-yn = +|yn -(b+k)| and yn-b = |(yn-b)|.

The second equation cited above thus reads:

B'i,j,n-B'k,j,n= |(yn-b)|-|yn -(b+k)| or

B'i,j,n-B'k,j,n= |yn-Pi,j,n|-|yn -Pk,j,n|

The third equation mentioned above corresponds to the other case mentioned at page 11, lines 2 to 5 wherein Co and C1 can be seen as corresponding respectively to Ci,j and Ck,j, whereby Ci,j= (b+k) and Ck,j= b.

Here again (b+k)-yn >0 and (yn-b)>0 and the third equation is equivalent to

B'i,j,n - B'k,j,n = |yn-(b+k)|-|(yn-b)|;

B'i,j,n - B'k,j,n = |yn-Ci,j|-|yn -Ck,j| or

B'i,j,n - B'k,j,n = |yn-Pi,j,n|-|yn -Pk,j,n|

2.3.3 Thus, starting from D1, the person skilled in the art would easily notice that these two equations mentioned in D1 are in effect one and the same equation, so that the application of the teaching of D1 to a m**(th)-dimensional constellation would lead in a straightforward manner to the equation (1) of claim 1 of the main request.

FORMULA/TABLE/GRAPHIC

A decoder for processing a sequence of received symbols and determining a survivor path according to the claimed equation (1) is therefore obvious in the light of D1. Thus the subject-matter of claim 1 of the main request does not meet the requirements following from Article 56 EPC.

3. Auxiliary request

3.1 The amendments to the claims and the description of the first auxiliary request meet the requirements following from Article 123(2) EPC.

Claim 1 of this request is based on original claim 1, whereby the feature "wherein the add-compare select unit is configured such that it achieves a level of performance using the linear distance branch metrics which is substantially equivalent to that achieved using squared distance branch metrics", to which the examining division objected as being unclear, has been removed and the equations recited at page 11, lines 15 to 30 of the published application introduced therein. Claims 2 and 3 correspond to the original claims 2 and 3 and claim 4 comprises the equation 19 found in the original published application at page 11, line 45. The features of method claims 5 to 8 correspond to the features of device claims 1 to 4.

The board considers that the erroneous symbols and equations of the description result from obvious clerical mistakes falling under Rule 139 EPC. The amendments in the corresponding pages of the description therefore do not contravene Article 123(2) EPC.

3.2 Article 84 EPC

3.2.1 The claims of the auxiliary request are now limited to the case of a trellis code with finite constellation, so that the objection of lack of clarity of the expression "a trellis code with infinite constellation" raised by the examination division is void.

3.2.2 The examining division objected to the expression "linear distance" as being unclear (cf. contested decision item II. (b2)), because no explicit definition of this expression was given in the different passages of the description mentioning "linear distance" (cf. sections [0009], [0010], [0014],]0016], [0018], [0019], [0025], [0026], [0027], [0031], [0034], [0035]).

The expression "linear distance" for branch metrics is implicitly defined in section [0023]. The board is moreover of the opinion that this expression and the expression "linear distance branch metrics" were known to the person skilled in the art, so that no lack of clarity results from their use.

3.3 Article 56 EPC

The invention defined in claim 1 of the first auxiliary request considers the use of a linear branch metric and the determination of a survivor path in the case of a trellis code with finite constellation. In a finite constellation the noisy received symbols might not fall between two codewords, so that the calculation of the survivor path is not as straightforward as that discussed in section 2.3 above for the case of infinite constellations. Hence the board considers that the claimed equation is not obviously derivable from the equations describing case II of D1. The subject-matter of claim 1 of the first auxiliary request therefore involves an inventive step in the sense of Article 56 EPC having regard to D1. This conclusion applies also to the remaining claims, since claim 5 defines the method steps corresponding to the device features of claim 1, and since claims 2 to 4 and 6 to 8 are dependent on these claims.

4. The board therefore concludes that the appellant's main request is not allowable, but that the application documents according to the auxiliary request satisfy the requirements of the EPC and thus provide a basis for granting a patent.

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:

- description: pages 1, 2 2a, 3 to 16 filed in the oral proceedings of 11 December 2014;

- claims: 1 to 8 of the first auxiliary request filed with letter dated 11 November 2014;

- drawings: sheets 1/5 to 5/5 as originally filed.