T 0676/07 () of 3.3.2010

Summary of Facts and Submissions

I. The appellant (applicant) appealed against the decision of the examining division refusing European application No. 03 254 214.4

II. In the decision under appeal, the examining division held, inter alia, that the subject-matter of claims 1, 3 and 6 then on file lacked an inventive step with respect to the following document:

D7: R. Narayanaswami, "Coded Modulation with Low Density Parity Check Codes", Thesis submitted to Texas A&M University, June 2001.

III. In a communication dated 17 November 2009 accompanying the summons to oral proceedings, the Board introduced, inter alia, the following document into the appeal proceedings:

D14: Xiaodong Li, James A. Ritcey, "Bit-Interleaved Coded Modulation with Iterative Decoding", 1999 IEEE International Conference on Communications ICC '99, pages 858 to 863.

IV. On 3 March 2010, oral proceedings were held before the Board.

V. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the main request filed in the oral proceedings or on the basis of auxiliary request 1 filed as auxiliary request 4 with a letter dated 3 February 2010.

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

"A method for decoding low density parity check (LDPC) codes, the method comprising:

(a) generating a priori probability information based on distance vector information comprising information on distances between received noisy symbol points and symbol points of a 8-PSK signal constellation associated with the LDPC codes, wherein symbols of the 8-PSK signal constellation are Gray coded;

(b) determining a posteriori probability information based on the a priori probability information;

(c) determining whether parity check equations associated with the LDPC codes are satisfied according to the a priori probability and the a posteriori probability information;

(d) if the parity check equations associated with the LDPC codes are not satisfied, regenerating a priori probability information from the a posteriori probability information and repeating steps (b) to (d);

(e) if the parity check equations associated with the LDPC codes are satisfied, outputting decoded messages based on the regenerated signal constellation bit metrics."

Claims 2 and 3 are dependent on claim 1.

Claim 4 relates to a "computer-readable medium bearing instructions for decoding low density parity check (LDPC) codes, said instruction, being arranged, upon execution, to cause one or more processors to perform the method of claim 1".

Claim 5, relates to a "receiver (300) for decoding low density parity check (LDPC) codes" and claims 6 and 7 are dependent on claim 5.

As claims 2 to 7 are not relevant to the present decision, they need no be quoted in full.

Claim 1 of the auxiliary request 1 reads as follows:

"A method for decoding low density parity check (LDPC) codes, the method comprising:

(a) generating a priori probability information based on symbol bit metrics generated from distance vector information comprising information on distances between received noisy symbol points and symbol points of a 8-PSK signal constellation associated with the LDPC codes, wherein symbols of the 8-PSK signal constellation are Gray coded;

(b) determining a posteriori probability information based on the a priori probability information;

(c) determining whether parity check equations associated with the LDPC codes are satisfied according to the a priori probability and the a posteriori probability information;

(d) if the parity check equations associated with the LDPC codes are not satisfied, regenerating the priori [sic] probability information from the a posteriori probability information without regenerating symbol bit metrics and repeating steps (b) to (d);

(e) if the parity check equations associated with the LDPC codes are satisfied, outputting decoded messages based on the a priori probability and the a posteriori probability information."

Claims 2 and 3 according to the auxiliary request correspond to claims 2 and 4 of the main request.

Claim 4 is directed to a "receiver (300) for decoding low density parity check (LDPC) codes". Claim 5 is dependent on claim 4.

As claims 2 to 5 of the auxiliary request are not relevant to the present decision, they need not be quoted in full.

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

D7 did not disclose a method for decoding low density parity check (LDPC) codes comprising the step of regenerating a priori probability information from the a posteriori probability information, as specified in claim 1 of the main request. Although Figure 6 of D7 illustrated an iterative demodulation scheme according to which the output of the LDPC decoder was fed back to the demodulator, this document did not show how the demodulator processed the a posteriori probability information and, in particular, it did not disclose the step of regenerating the a priori probability information from the a posteriori probability information if the parity check equations associated with the LDPC codes were not satisfied. As this step was not suggested in any of the cited prior art documents, the subject-matter of claim 1 involved an inventive step according to Article 56 EPC.

Claim 1 of the auxiliary request was directed to the embodiment of the invention shown in Figure 11 and differed from the main request in that the symbol metrics were not regenerated, if the parity check equations associated with the LDPC codes were not satisfied. This method was based on the realisation that, in the case of Gray labelling, the additional complexity of iterating between the LDPC decoder and the 8-PSK metric generator was not required.

The decoding scheme shown in Figure 6 of D7 involved some kind of iteration between the LDPC decoder and the 8-PSK bit metric generator. In fact, none of the cited prior art disclosed that Gray labelling of the 8-PSK signal constellation allowed a simplified decoding scheme which did not involve the regeneration of the bit metrics after each iteration of the LDPC decoder. The method according to claim 1 of the auxiliary request thus involved an inventive step.

Reasons for the Decision

1. The appeal is admissible.

Main Request

2.1 Claim 1 according to the appellant's main request is concerned with a method for decoding low density parity check (LDPC) codes modulated according to an 8-PSK modulation scheme, whereby the symbols of the 8-PSK signal constellation are Gray coded.

The steps (a) to (e) of claim 1 specify a decoding scheme corresponding to Figures 3 and 10 of the application as originally filed, whereby, after a first unsuccessful attempt at reconstructing the original source message, the LDPC decoder 305 feeds the a posteriori probability information back to the bit metric generator 307 in order to regenerate the a priori probability information. The bit metric generator 307 thus exchanges probability information with the LDPC decoder until the parity check equations are satisfied or a maximum number of iterations is reached (see application as published, paragraph [0042]).

2.2 Document D7 relates, inter alia, to the decoding of binary data which are first encoded with LDPC codes and then mapped onto an 8-PSK signal constellation (see page 18, last paragraph). As shown in Figure 5, the 8-PSK signal constellation used in D7 is Gray coded and the step of generating a priori probability information as specified in feature (a) of claim 1 corresponds essentially to the first step of the algorithm given on page 23 of D7.

As to the decoding of the LDPC codes, D7 points out that each bit node receives extrinsic information from the adjacent check nodes and each check node receives extrinsic information from the adjacent bit nodes. "Each node receives information along it's [sic] edges and sends back new information along the same edges after processing the information. When a node sends back information on an edge it does not make use of the information it received along the same edge. This procedure is repeated many times" (D7, page 10, lines 13 to 16).

The appellant has not contested that steps (a), (b) and (c) of claim 1 are known from D7.

2.3 The appellant has, however, argued that D7 did not teach to regenerate a priori probability information from the a posteriori probability information and to output decoded messages based on the regenerated signal constellation metrics as specified in steps (d) and (e) of claim 1.

3.1 D7 describes in section B., ("Bit Interleaved Coded Modulation") on page 19, that, in the case of Bit Interleaved Coded Modulation (BICM), the binary data is first encoded with the LDPC codes and then mapped onto 8-PSK or 16 QAM constellations. In BICM there is only one decoder and the decoding is thus not done in stages. In fact, Figure 6 shows that the extrinsic probability Lext is fed from the output of the LDPC decoder to the input of the demodulator. According to section C. (last paragraph of page 20 and first line of page 22), when decoding LDPC codes with coded modulation, "the estimate of a bit is improved with a better estimate of the other bits in the symbol. In other words, the channel a bit in the symbol sees improves when the other bits in the symbol are decoded correctly. This fact can be used to form an iterative demodulator" (emphasis added).

Furthermore, D7 teaches in the same section (page 22, lines 7 to 9) that initially "from the channel the symbol probabilities are equal but after a couple of iterations by the decoder we can update these apriori [sic] probabilities with the information received from the decoder".

3.2 In summary, D7 considers the LDPC decoder and the 8-PSK demodulator as a decoding unit. A posteriori probability information is fed to the demodulator in order to update the a priori probability information sent from the demodulator to the LDPC decoder. This necessarily implies that the decoded messages generated by the decoder are based on the updated a priori probabilities.

3.3 As to the wording used in D7 and in the present application, paragraph [0053] of the application as published specifies that the "8-PSK bit metric generator 307 communicates with the LDPC decoder 305 to exchange a priori probability information and a posteriori probability information, which respectively are represented as u, and a. That is, the vectors u and a respectively represent a priori and a posteriori probabilities of log likelihood ratios of coded bits." If the parity check equations are not satisfied, the 8-PSK bit metrics and channel input u are "re-derived" (cf. Figure 10 and paragraph [0060] of the application). In other words, the fact that the iterative demodulation of the received message directly involves the 8-PSK metric generator 307 implies that its output is changed as a function of the LDPC decoder's output, i.e. that the a priori probability information is updated by means of the a posteriori probability information.

In the present application, the expressions "regenerating" and "updating" a priori probability information appear to have the same meaning, while "a priori" probability information and "signal constellation bit metrics" appear to be used interchangeably. Thus, the Board sees no difference between the step of "updating" the a priori probabilities taught in D7 and the step of "regenerating" the a priori probability information specified in step (d) of claim 1, or between "updated" a priori probabilities and "regenerated" signal constellation metrics referred to in step (e) of claim 1.

As to the step of outputting decoded messages if the parity check equations associated with the LDPC codes are satisfied (see step (e) of claim 1), the Board considers that it is necessarily part of the decoding method known from D7. As pointed out in the contested decision (see section 5), D7 teaches that a general decoding scheme for LDPC codes involved a "Hard Decision" based on the probability information available at the time of the last iteration and that the "Stopping Criterion" for stopping the decoder iterations depends on the parity check equations being satisfied or a maximum number of iterations being achieved (D7, pages 10 to 12 and pages 22 to 24).

3.4 As pointed out in D7 (page 22, second paragraph), the known method carries out an update of the probability information "after a couple of iterations". However, the wording of claim 1 according to the appellant's main request appears to imply that the a priori probability information is regenerated after every LDPC decoder iteration as long as the parity check equations are not satisfied.

3.5 In the Board's opinion, it would be obvious to a skilled person, having realized the advantage of regenerating the a priori probability information "after a couple of iterations" according to the scheme shown in D7, to increase the frequency of this regeneration and, in particular, to consider the possibility of regenerating the probability information after each LDPC decoder iteration. In doing so, the skilled person would arrive at the method of claim 1 of the main request.

3.6 Hence, in the Board's opinion, the subject-matter of claim 1 of the main request is an obvious development of the method known from D7 and, as such, it does not involve an inventive step within the meaning of Article 56 EPC.

Auxiliary request

4.1 Claim 1 of the auxiliary request differs from claim 1 of the main request essentially in that no iteration is carried out between the LDPC decoder and the 8-PSK bit metric generator (see feature (d)).

Thus, as pointed out by the appellant, claim 1 of the auxiliary request is directed to a method of decoding which generates only once the bit metrics indicative of the distances between the received noisy symbol points and the symbol points of the Gray coded 8-PSK symbol constellation, as illustrated by the flow chart of Figure 11.

4.2 According to the appellant, it was customary before the priority date of the present application to regenerate the bit metrics after an LDPC decoder iteration. The inventors of the claimed method had, however, realized that this was not necessary when Gray mapping was used. Thus, the present inventors had overcome the general belief that the bit metrics had to be regenerated after an LDPC decoder iteration and come up with a simpler and more efficient method of decoding 8-PSK modulated LDPC codes.

4.3 As pointed out above (see items 3.1 and 3.2), D7 relates to a method for decoding binary data which are LDPC coded and then mapped onto 8-PSK constellations. The mapping used for Bit Interleaved Coded Modulation (BICM) is Gray labelling. After a decoder iteration, the output of the LDPC decoder is fed to the 8-PSK demodulator in order to regenerate the bit metrics.

4.4 Hence, the subject-matter of claim 1 of the auxiliary request differs from the method of decoding shown in D7 only in that the bit metrics are not regenerated after a decoder iteration.

It is self-evident that a method involving the regeneration of the bit metrics after one or more iterations of the LDPC decoder has a higher degree of complexity than a method in which the bit metrics are generated only once for every decoding operation. Thus, starting from the method disclosed in D7, a problem addressed by the present application can be seen in providing a simpler method for decoding 8-PSK modulated LDPC codes.

4.5 In D7 (page 20, section C. "Decoding LDPC codes with coded modulation") it is specified that in "coded modulation, the estimate of a bit is improved with a better estimate of the other bits in the symbol. In other words the channel a bit in the symbol sees improves when the other bits in the symbol are decoded correctly. This fact can be used to form an iterative demodulator" (emphasis added). Thus, "after a couple of iterations by the decoder we can update these apriori probabilities with the information we receive from the decoder" (D7, page 22, third paragraph, emphasis added). In other words, D7 presents an iterative demodulator as a possibility for improving the estimate of a bit. It is, however, evident to the skilled person that it is also possible to decode modulated LDPC codes in two stages, i. e. by first demodulating the received message and then decoding the demodulated codes.

4.6 Hence, a skilled person wishing to simplify the iterative decoding scheme for LDPC codes with BICM and Gray labelling known from D7 codes would have found it obvious to do without the optional step of regenerating the a priori probability information with information from the LDPC decoder. In doing so, the skilled person would have arrived at the method according to claim 1 of the auxiliary request without exercising any inventive activity (Article 56 EPC).

4.7 The above conclusion finds corroboration in D14 which relates to the decoding of a digital signal generated by Bit-Interleaved Coded Modulation (cf. D7, page 18, section B.).

As explained in the first paragraph of section A. (page 858, right-hand column) of D14, a BICM transmitter is a serial concatenation of convolutional encoder, bit-by-bit interleaver and a high-order modulator, for example an 8-PSK modulator. According to D14 (page 858, left-hand side, third paragraph of section "I. Introduction") "the maximum-likelihood decoding (MLD) of BICM requires joint demodulation/convolutional decoding, which is often too complicated to implement. In practice, MLD is replaced by a suboptimal approach using separate bit-metric generation and Viterbi decoding [2]. As shown in [3], such a suboptimal scheme generally demands Gray labelling for the best performance".

As pointed out on page 859, section B., first paragraph, "true MLD of BICM would require joint demodulation and convolutional decoding, and is therefore too complex to implement in practice. In [2], Zehavi suggested a suboptimal method using two separate steps: bit metric generation and Viterbi decoding".

Furthermore, section B. (page 860) gives a detailed description of a "suboptimal" iterative method involving the determination of the a posteriori probabilities for the information and coded bits on the basis of the a priori probabilities.

As to signal labelling, D14 (page 860, section D., second sentence) acknowledges that different decoding methods may require different constellation labelling to achieve the best performance. "For BICM without iterative decoding, Gray labeling is the best approach".

The effects of signal labelling are shown in Figure 7. Thus, "Gray labeling offers the best first-pass performance, but yields almost no gain with ID [iterative decoding]" (D14, page 861, Section B.2).

4.8 In summary, the subject-matter of claim 1 according to the auxiliary request does not involve an inventive step within the meaning of Article 56 EPC.

5. As the Board finds that none of the appellant's requests is allowable, the application has to be refused.

ORDER

For these reasons it is decided that:

The appeal is dismissed.