T 0894/15 (Adaptive turbo decoding/SAMSUNG ELECTRONICS) of 28.10.2019

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 00935678.3, filed as the international application published as WO 00/74399.

II. The following documents were cited in the first-instance proceedings:

D1:|S. Pietrobon: "Implementation and performance of a turbo/MAP decoder", International Journal of Satellite Communications, 16, 1998, pp. 23-46; |

D2:|P. Hoeher: "New iterative ('turbo') decoding algorithms", Proceedings of the International Symposium on Turbo Codes and Related Topics, 1997, pp. 63-70;|

D3:|X. Huang and N. Phamdo: "Turbo decoders which adapt to noise distribution mismatch", IEEE Communications Letters, Vol. 2, No. 12, December 1998, pp. 321-323;|

D4:|T. Summers and S. Wilson: "SNR mismatch and online estimation in turbo decoding", IEEE Transactions on Communications, Vol. 46, No. 4, April 1998, pp. 421-423;|

D5:|"Iterative decoding of parallel concatenated convolutional codes", Application Note, Small World Communications, 13 January 1999, pp. 1-12; |

D6:|C. Heegard and S. Wicker: "Turbo coding", ISBN 0792383788, January 1999, pp. 156-161. |

The Examining Division decided that the subject-matter of independent claims 1, 4 and 7 of the main request and independent claims 1 and 4 of auxiliary request 1 infringed Article 123(2) EPC and that the subject-matter of claims 1 and 4 of the main request and auxiliary requests 1 to 3 lacked inventive step within the meaning of Article 56 EPC in view of, in particular, the teaching of document D4.

III. In the statement of grounds of appeal, the appellant maintained the requests considered in the decision under appeal. Oral proceedings were requested as auxiliary measure.

IV. In a communication accompanying the summons to oral proceedings, the Board, inter alia, expressed the preliminary view that the main request did not comply with Articles 123(2) and 84 EPC and that the subject-matter of claim 1 of all requests lacked inventive step over the disclosure of both document D1 and document D4.

V. In a letter dated 27 September 2019, the appellant replaced its requests with a new main request and new auxiliary requests 1, 2 and 3.

VI. During oral proceedings held on 28 October 2019, the appellant replaced its requests with a sole substantive requests, for which it filed amended claims and description pages. At the end of the oral proceedings, the chairman pronounced the Board's decision.

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

- claims 1 to 4 as filed in the oral proceedings before the Board at 15.00 hours;

- description:

- pages 1, 3, 3a, 4 and 12 as filed in the oral proceedings at 15.00 hours;

- pages 2 and 5 to 11 of the application as published;

- drawing sheets 1/6 to 6/6 of the application as published.

VIII. Independent claim 1 of the sole substantive request reads as follows:

"An adaptive MAP channel decoding apparatus, comprising:

a channel estimator (420) adapted to calculate a channel noise power and a scaling factor;

a MAP channel decoder (440);

a controller (430) adapted to determine an operation mode of the MAP channel decoder (440); and

the MAP channel decoder (440) being adapted to selectively operate in a static channel mode or in a time-varying mode, wherein the MAP channel decoder is adapted to use in the static channel mode the following equation for decoding:

xEy = min(x, y) - log(1+e**(-|x-y|))

and wherein the MAP channel decoder is adapted to use in the time-varying mode the following equation for decoding:

xEy = min(x, y)

where x and y are metric values,

wherein a current channel state is determined by the controller to be time-varying or static based on changes in the channel noise power or the scaling factor, and

wherein the time-varying channel mode is determined if the current channel state is determined to be time-varying, and otherwise the static channel mode is determined."

Claims 2 and 3 are directly or indirectly dependent on claim 1.

Independent claim 4 reads as follows:

"An adaptive MAP channel decoding method in a communication system, comprising the steps of:

estimating, by a channel estimator, a channel noise power and a scaling factor;

determining a current channel state to be time-varying or static based on changes in the channel noise power or the scaling factor;

controlling an E function operation according to the determined current channel state by:

performing (630) MAP channel decoding using the E function operation according to the following first MAP decoding equation when the current channel state is determined to be static:

xEy = min(x, y) - log(1+e**(-|x-y|))

where x and y are metric values, and

performing MAP channel decoding using the E function operation according to the following second MAP decoding equation when the current channel state is determined to be time-varying:

xEy = min(x, y)

where x and y are metric values."

Reasons for the Decision

1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.

2. The invention

2.1 The application relates to the decoding of turbo codes by means of the maximum a posteriori (MAP) method.

The background section of the application gives an overview of the MAP algorithm used in known MAP channel decoders. One of the inputs to this algorithm is an estimation of the "noise power" sigma**(2) of the channel, which is provided by a channel estimator and is used to calculate the "channel reliability" Lc = 2/sigma**(2) (page 1, line 34, to page 2, line 11, of the published application). The decoding performance of the MAP channel decoder is "sensitively influenced" by the noise power calculated by the channel estimator (page 3, lines 5 to 9). A further parameter that must be estimated accurately is a "scaling factor" to compensate for fading (page 3, lines 15 to 21).

2.2 The invention is concerned with ensuring stable decoding performance regardless of the current channel state (page 3, lines 11 to 13; page 3, line 30, to page 4, line 4). To achieve that, a "controller" is provided that monitors changes in the channel noise power and the scaling factor and controls the MAP channel decoder to operate in either a "static channel mode" or a "time-varying mode" (page 4, lines 13 to 20).

2.3 The MAP algorithms used in the two operation modes differ on account of the definition of a function denoted by the letter E.

In the static channel mode, this function is defined by means of the equation

xEy = min(x, y) - log(1+e**(-|x-y|)).

In the time-varying mode, the log function component is omitted:

xEy = min(x, y).

2.4 The Board notes that these definitions refer to the well-known "log-MAP" and "sub-MAP" decoding algorithms as presented in section 2 of document D1. In particular, the log-MAP algorithm is used in the static channel mode, and the sub-MAP algorithm is used in the time-varying mode. As explained in document D1 on page 28, right-hand column, lines 22 to 24, the sub-MAP algorithm is suboptimal but has the advantage that it does not require an estimation of the noise power sigma**(2) (see also page 7, lines 5 to 24, of the published application).

2.5 In the following, the Board will write "MAP" for "log-MAP", as is also done in the present application.

3. Added subject-matter

3.1 Independent apparatus claim 1 corresponds to original claim 1 with amendments based on original claim 4 and the description on page 11, lines 8 to 12 and 23 to 25, of the application as filed. Independent method claim 4 corresponds to apparatus claim 1.

3.2 Dependent claims 2 and 3 correspond to original claims 2 and 3.

3.3 Hence, the sole substantive request complies with Article 123(2) EPC.

4. Clarity

4.1 According to claim 1, the channel estimator is adapted "to calculate a channel noise power and a scaling factor". In its communication, the Board questioned whether the term "scaling factor" had a well-defined meaning in the art in the context of the claim.

On reconsideration, the Board accepts the appellant's argument that the "scaling factor" of claim 1 is a known parameter of the MAP algorithm and is used to compensate for variations in signal strength which are typically caused by fading.

4.2 The sole substantive request therefore also complies with Article 84 EPC.

5. Document D1

5.1 Document D1 relates to the decoding of turbo codes by means of the MAP algorithm ("Summary" section; page 24, left-hand column, lines 1 to 28). It discloses, in sections 2.1, 2.2 and 2.3 on pages 25 to 29, the MAP, log-MAP and sub-MAP algorithms.

5.2 The log-MAP algorithm disclosed in section 2.2 corresponds to the MAP algorithm of the present application (see D1, page 27, right-hand column, equations (21) and (22)). It requires knowledge of the channel reliability Lc = 2/sigma**(2) (page 28, left-hand column, line 6, to right-hand column, line 2; page 27, left-hand column, lines 18 to 25) and thus also of the channel noise power/noise variance sigma**(2).

The sub-MAP algorithm disclosed in section 2.3 corresponds to the sub-MAP algorithm of the present application (see page 28, right-hand column, lines 16 to 21; letting f(z)=0 in equation (22) turns equation (21) into "a E b = min(a,b)"). This algorithm is suboptimal but has the advantage that it is independent of sigma**(2) (page 28, right-hand column, lines 22 to 24).

5.3 The log-MAP channel decoder of document D1 includes an estimator for estimating the channel noise power/noise variance sigma**(2) (page 29, left-hand column, line 50, to right-hand column, line 31).

The decoder also calculates an optimum value for a parameter denoted by A, which relates to the signal amplitude and which is a "scaling factor" within the meaning of the present application (page 28, right-hand column, lines 2 to 10; page 29, left-hand column, lines 45 to 48; page 29, right-hand column, line 32, to page 30, left-hand column, line 3).

Both estimates are used in the MAP algorithm (see page 28, left-hand column, equation (27), and right-hand column, line 1; page 29, left-hand column, lines 27 to 48).

6. Document D4

6.1 Document D4 also relates to the decoding of turbo codes by means of the MAP algorithm (abstract; page 421, left-hand column, lines 2 to 17). It explains that the MAP algorithm requires knowledge of the approximate channel signal-to-noise ratio (SNR) for a Gaussian noise channel (page 421, left-hand column, lines 18 to 29).

6.2 According to the passage on page 421, right-hand column, lines 17 to 41, received data can be represented by rn = ±my + nn, where my**(2) is the energy per bit and nn is a Gaussian random variable having zero mean and variance sigma**(2). The SNR parameter relevant for the MAP algorithm is beta = my**(2)/sigma**(2) (page 421, right-hand column, lines 37 and 38).

In view of the passage on page 7, line 32, to page 8, line 3, in the present application the energy per bit my**(2) is normalised to 1 (and the same applies to document D1 - see page 25, right-hand column, second full paragraph, equations (3) and (4)). The parameter beta of document D4 therefore corresponds to the parameter Lc = 2/sigma**(2) of the application (and of document D1) up to a factor of 2.

6.3 Document D4 discloses, on page 422, left-hand column, line 23, to page 423, right-hand column, line 7, an algorithm for calculating an estimate of beta. In view of the preceding paragraph, this is effectively an estimate of the (normalised) channel noise power sigma**(2).

6.4 One aim of document D4 is to study the sensitivity of decoder performance to misestimation of the SNR (abstract; page 421, right-hand column, line 42, to page 422, left-hand column, line 22; Figure 1). The document proposes an algorithm for estimating the SNR at a packet level to anticipate variations from packet to packet (page 422, left-hand column, line 23, to page 423, right-hand column, line 16).

7. Inventive step

7.1 Documents D1 and D4 both disclose a MAP channel decoding apparatus based on the MAP decoding algorithm that is adaptive in the sense that the information about the current channel state required by the MAP algorithm is obtained dynamically by a channel estimator.

7.2 The apparatus of claim 1 differs from both disclosures at least in that it switches to using the sub-MAP algorithm when the current channel state is determined to be time-varying on the basis of changes in the (estimated) channel noise power or the scaling factor.

7.3 The Examining Division essentially argued that the MAP algorithm was known to be superior to the sub-MAP algorithm in terms of decoding performance as long as the algorithm worked with accurate estimations of the true channel conditions. In document D4, the channel conditions were estimated on the fly. Mismatches between the channel conditions assumed by the decoder and the true channel conditions were therefore avoided.

7.4 The Board does not agree with the Examining Division's view that, at least in the context of document D4, switching to the sub-MAP algorithm would always have been disadvantageous in respect of decoding performance. Although it is true that the MAP algorithm outperforms the sub-MAP algorithm as long as the estimated channel conditions are sufficiently close to the true channel conditions, the Board accepts the appellant's argument that the estimates produced by a practical channel estimator can be inaccurate in case of highly fluctuating channel conditions. Indeed, a channel estimator in a decoder cannot directly measure the channel noise power and the scaling factor but necessarily has to infer the values of these parameters indirectly from a series of signal values observed over a certain period of time, which may themselves have been affected by fluctuating channel conditions.

7.5 In its communication, the Board argued that the condition for selecting the MAP algorithm as specified in claim 1 of the then main request, namely that "a predetermined number of successive occurrences of the calculated channel noise power and scaling factor approximate to a predetermined value is observed", was not suitable for distinguishing situations in which the channel estimator was likely to be sufficiently accurate from situations in which the channel estimator was likely to be considerably inaccurate.

According to present claim 1, the sub-MAP algorithm is to be used only if the "current channel state is determined by the controller to be time-varying", this determination being "based on changes in the channel noise power or the scaling factor". In other words, the sub-MAP algorithm is used when the estimated channel noise power or the estimated scaling factor has been varying over some period of time.

Arguably, this condition still does not reliably identify situations in which the channel estimator can reasonably be expected to produce inaccurate estimations. Indeed, the whole point of the channel estimator of document D4 is to produce accurate estimations when the channel conditions change. In a literal reading of claim 1, the claimed MAP channel decoding apparatus switches to using the sub-MAP channel algorithm whenever the estimated channel conditions have changed, even if the changes are relatively gradual and it is unlikely that the estimations are inaccurate.

7.6 Nevertheless, by switching to using the sub-MAP channel algorithm whenever the estimated channel conditions have changed, the MAP channel decoding apparatus is made more robust against misestimations of the channel conditions than an apparatus that always uses the MAP channel algorithm. At the same time, by using the MAP channel algorithm when the estimated channel conditions have remained static over some period of time, the claimed apparatus is able to achieve better overall decoding performance than an apparatus that always uses the sub-MAP channel algorithm.

The Board therefore considers that the claimed conditional switching from the known MAP algorithm to the known sub-MAP algorithm goes beyond a technically arbitrary switching between two known algorithms. Rather, it solves the objective technical problem of increasing the robustness of a MAP channel decoding apparatus as known from documents D1 and D4 while maintaining better decoding performance than provided by the sub-MAP algorithm.

7.7 As explained below, the skilled person, starting from the known MAP channel decoder and faced with this problem, would not have found a pointer to the claimed solution in the cited prior art.

Document D1 describes both the MAP algorithm and the sub-MAP algorithm and discloses, on page 28, right-hand column, lines 22 to 24, that the sub-MAP algorithm has the advantage of being independent of the estimated channel noise power. But this is not a suggestion to combine both algorithms in one decoder to achieve both robustness and good performance. Rather, the skilled person is led to contemplate simplifying a MAP channel decoder by implementing the sub-MAP algorithm and leaving out the channel estimator.

Document D2, in section 2, likewise discusses the advantages and disadvantages of the MAP and sub-MAP algorithms but does not suggest combining both algorithms in one decoder to solve the problem posed.

Document D3 investigates the sensitivity of turbo decoder performance to a mismatch of the noise distribution and proposes a procedure for estimating the noise distribution from received signal blocks (see abstract). There is no mention of the sub-MAP algorithm, let alone a suggestion to combine the MAP and sub-MAP algorithms in one decoder.

Document D4 does not mention the sub-MAP algorithm either.

The disclosure of document D5 is similar to that of document D1 in that the document describes, on page 6, left-hand column, line 5, to right-hand column, line 26, the MAP and sub-MAP decoding algorithms and discloses, on page 6, right-hand column, lines 7 to 12, that the sub-MAP algorithm performs worse than the MAP algorithm but has the advantage of not needing to know the values of the scaling factor ("A") and the channel noise power ("Eb/N0"). There is no suggestion to solve the problem posed by combining the MAP and sub-MAP algorithms in one decoder.

Document D6 is an excerpt from a textbook on turbo decoding. It discusses the question of decoder mismatch but does not mention the sub-MAP algorithm.

7.8 Nor would the common general knowledge have led the skilled person, faced with the problem of increasing the robustness of a MAP channel decoder while maintaining good performance, to the two steps of combining the MAP and sub-MAP algorithms in one decoder and letting the decoder switch from the MAP algorithm to the sub-MAP algorithm when the estimated channel conditions are determined to be changing.

7.9 In sum, the subject-matter of apparatus claim 1, dependent claims 2 and 3 and corresponding method claim 4 involves an inventive step (Article 56 EPC).

8. Conclusion

Since the sole substantive request complies with the provisions of the EPC, the appeal succeeds.

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 4 as filed in the oral proceedings before the Board at 15.00 hours;

- description:

- pages 1, 3, 3a, 4 and 12 as filed in the oral proceedings at 15.00 hours;

- pages 2 and 5 to 11 of the application as published;

- drawing sheets 1/6 to 6/6 of the application as published.