T 1469/16 (Mapping LDPC bits on a QAM signal constellation/SAMSUNG ELECTRONICS) 22-05-2019
Apparatus and method for mapping and demapping signals in a communication system using a low density parity check code
Sufficiency of disclosure - all requests (yes)
Inventive step - all requests (no)
I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 12161585.0.
II. The application was filed on 27 March 2012 and claims the priority of Korean patent applications Nos. 10-2011-0029128 (filed on 30 March 2011), 10-2011-0034481 (filed on 13 April 2011), 10-2011-0037531 (filed on 21 April 2011) and 10-2011-0141033 (filed on 23 December 2011).
III. The decision cited, inter alia, the following documents:
D5:|M. Lunglmayr and J. Berkmann: "Optimized Mapping Schemes for LDPC Coded Higher Order Modulated QAM Transmission", February 2007, Proceedings of the 11th International Conference on Computer Aided Systems Theory, EUROCAST 2007, pp. 952-959;|
D6:|Y. Li and W. Ryan: "Bit-Reliability Mapping in LDPC-Coded Modulation Systems", January 2005, IEEE Communications Letters, Vol. 9, No. 1, pp. 1-3; |
E1:|H. Yang, "16k-LDPC Codes (1/3 & 2/5) for T2-Mobile", slides of a presentation dated 12 May 2011 by one of the inventors; |
E2:|F. Herrmann, "[tm-h][t2-mobile][cci]: Decision in favour with S2 codes for rates 1/3 and 2/5 and demultiplexers", printout of an email dated 12 May 2011; |
E3:|"Digital Video Broadcasting (DVB); Frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)", February 2011, ETSI EN 302 755 V1.2.1; |
E4:|"Digital Video Broadasting (DVB); Frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)", November 2011, Final draft ETSI EN 302 755 V1.3.1; |
E5:|"Digital Video Broadcasting (DVB); Next Generation broadcasting system to Handheld, physical layer specification (DVB-NGH)", November 2012, DVB Document A160. |
The Examining Division decided that the main request and the first and second auxiliary requests did not comply with Article 83 EPC and also that the second auxiliary request did not comply with Article 84 EPC. It did not admit the third and fourth auxiliary requests into the proceedings under Rule 137(3) EPC because they did not prima facie overcome the objections under Articles 83 and 84 EPC and raised new issues under Article 123(2) EPC.
In an obiter dictum, the Examining Division argued that the subject-matter of all claims of all requests lacked inventive step over document E3.
IV. In its statement of grounds of appeal, the appellant maintained the main request, withdrew the first auxiliary request, maintained the second and third auxiliary requests as the first and second auxiliary requests, and submitted a new third auxiliary request. It attached a copy of the claims of the main request and marked-up copies of the claims of the auxiliary requests. It also submitted the following document:
E7:|H.-K. Yang and K. Yang: "Optimization of Degree-Profile Matching Interleavers for LDPC-Coded Modulation", December 2006, IEEE Communications Letters, Vol. 10, No. 12.|
V. In a communication accompanying the summons to oral proceedings, the Board expressed, inter alia, the preliminary view that the subject-matter of claim 1 of all requests lacked inventive step.
VI. In a letter dated 19 April 2019, the appellant submitted an amended main request.
VII. In the course of oral proceedings held on 22 May 2019, the appellant replaced its three auxiliary requests with amended first and second auxiliary requests based on the previous first and third auxiliary requests. At the end of the oral proceedings, the chair pronounced the Board's decision.
VIII. 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 the letter dated 19 April 2019 or, in the alternative, the first and second auxiliary requests filed in the oral proceedings.
IX. Claim 1 of the main request reads as follows:
"A substream generating method of a signal transmitter, the substream generating method comprising:
encoding information bits using a low density parity check, LDPC, code to provide LDPC codeword bits;
interleaving the LDPC codeword bits;
wherein the interleaving the LDPC codeword bits comprises:
writing the LDPC codeword bits column-wise to a plurality of columns; and
reading the written LDPC codeword bits row-wise;
demultiplexing the interleaved LDPC codeword bits to generate substreams; and
mapping bits in each of the substreams to symbols on a constellation based on a modulation scheme,
wherein the substreams are generated by using the relationship defined in the table 1 and the modulation scheme is 64-ary quadrature amplitude modulation, 64-QAM, a length of the LDPC codeword bit and a length of the LDPC code are 16200 (Nldpc=16200), and a number of the substreams and a number of the plurality of columns are 12 (Nsubstreams=12).
X. Claim 1 of the first auxiliary request differs from claim 1 of the main request in that "in a Digital Video Broadcasting (DVB)-Next Generation Handheld (NGH) system" has been inserted after "A substream generating method of a signal transmitter".
XI. Claim 1 of the second auxiliary request differs from claim 1 of the main request in that the following text has been added at the end of the claim (before "[table 1]"):
", according to a variable node degree of each of the LDPC codeword bits and an error probability of each of the modulated bits included in a 64-QAM symbol so as to minimize the error probability of the 64-QAM symbol".
XII. The appellant's arguments, where relevant to the decision, are discussed in detail below.
1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.
2. The application relates to low-density parity-check (LDPC) codes used in combination with quadrature amplitude modulation (QAM). Since different LDPC codeword bits have different error-correcting abilities (depending on the degree of the variable node corresponding to the LDPC codeword bit), and since different modulation bits in one QAM symbol have different error probabilities, coding performance can be improved by optimising the mapping of LDPC codeword bits to QAM bits. The application discloses schemes for mapping LDPC codeword bits to QAM symbols.
3. The invention as defined by claim 1
3.1 Claim 1 of the main request is directed to a "substream generating method of a signal transmitter". It includes four steps:
- encoding information bits using an LDPC code to obtain an LDPC codeword;
- interleaving the LDPC codeword bits by writing the bits column-wise to a plurality of columns and reading back the written bits row-wise;
- demultiplexing the interleaved LDPC codeword bits into substreams; and
- mapping bits in each of the substreams to symbols of a constellation based on a modulation scheme.
3.2 Claim 1 further specifies that the modulation scheme is 64-QAM and that the number of columns and of substreams is 12.
3.3 The claim also specifies that "a length of the LDPC codeword bit and a length of the LDPC code are 16200 (Nldpc=16200)". At the oral proceedings, the appellant explained that this feature was to be understood as meaning that the length of the LDPC codeword was 16200 bits.
3.4 Finally, the claim states that "the substreams are generated by using the relationship defined in the table 1", where table 1 defines a specific mapping of "interleaved LDPC codeword bits" v0 to v11 to substreams b0 to b11.
4. Sufficiency of disclosure - Article 83 EPC
4.1 In its decision, the Examining Division argued that the then main request did not comply with Article 83 EPC because the application disclosed neither an embodiment which achieved the envisaged technical effect as set out in the description nor information on how to put the invention into practice over the whole scope of the claims.
Claim 1 of the then main request did not include the steps of encoding information bits to obtain an LDPC codeword and of mapping bits in substreams to constellation symbols, and it was silent on the number of columns written to in the "interleaving" step. Otherwise, it corresponded to present claim 1.
4.2 The Board notes that carrying out the individual steps of claim 1 would have been well within the abilities of the skilled person. Although the claim leaves several aspects open, in particular which LDPC code with codeword length 16200 to use and precisely how to map the bits in a substream on a 64-QAM signal constellation, there is no doubt that the skilled person would have been able to select such codes and mappings.
4.3 The Examining Division essentially considered that for the main request to comply with Article 83 EPC, it was necessary that the skilled person, by carrying out the invention, would have achieved the effect of improved coding performance due to the mapping of LDPC codeword bits to QAM modulation bits being optimised (as explained in point 2 above).
However, claim 1 does not express such an effect, and the same applies to the other claims of the main request. This means that if the effect is not achieved over the whole scope of any of the claims, this is not a problem under Article 83 EPC but may have an impact on the assessment of inventive step (see decisions T 939/92, OJ EPO 1996, 309, reasons 2.2.2 and 2.2.3; G 1/03, OJ EPO 2004, 413, reasons 2.5.2; and T 862/11 of 17 March 2015, reasons 5.4 and 5.5).
4.4 Hence, the main request complies with Article 83 EPC.
5. Inventive step - Article 56 EPC
5.1 Document E3 is version 1.2.1 of the standard specification of the DVB-T2 channel coding/modulation system. Section 4.1 discloses a signal transmitter comprising a "bit interleaved coding and modulation" subsystem. This subsystem is discussed in more detail in section 6. It includes an LDPC encoder which outputs codewords Lambda of length Nldpc (section 6.1.2). If the modulation scheme being used is 16-QAM, 64-QAM or 256-QAM, each codeword Lambda is bit interleaved, which involves writing its bits column-wise and reading them out row-wise (see section 6.1.3, in particular page 39, lines 2 to 5). The interleaved bits are then demultiplexed into multiple substreams (section 6.2.1), and the bits in each substream are mapped on a signal constellation of the modulation scheme (section 6.2.2).
If the modulation scheme is 64-QAM, the value of Nldpc is either 64800 or 16200, and the number of interleaver columns and of substreams is 12 (section 6.1.3, table 9; section 6.2.1, table 12).
5.2 Tables 13(a), 13(b) and 13(c) in section 6.2.1 include a number of mappings valid for Nldpc=16200, 64-QAM and code rates 1/2, 3/5, 2/3, 3/4, 4/5 and 5/6, which specify how interleaved bits are to be mapped to the 12 substreams. The LDPC codes corresponding to these code rates are defined in tables B.2 to B.7 of Annex B in terms of "parity bit accumulators" (see section 184.108.40.206).
5.3 None of the mappings in section 6.2.1 corresponds to the mapping defined in table 1 of claim 1. The subject-matter of claim 1 hence differs from what is disclosed in document E3 in that the mapping of interleaved bits to substreams is the mapping defined by table 1.
5.4 In its obiter dictum, the Examining Division essentially argued that the claimed mapping represented a technically arbitrary selection from the known set of all possible mappings in the sense that the mapping did not achieve a technical effect not achieved by all other mappings. Its selection therefore involved no inventive step.
5.5 The only technical effect of the claimed mapping that is suggested by the application as filed is that of optimising the mapping of LDPC codeword bits to QAM modulation bits and thereby improving coding performance. The application explains that such an optimised mapping has to take into account the error-correction ability of each LDPC codeword bit, which is related to the degree of the variable node corresponding to the bit, and the error probability of each modulation bit (see page 2, lines 6 to 15, of the application's description).
Since claim 1 specifies that the length of an LDPC codeword is 16200 but otherwise leaves the LDPC code to use completely undefined, claim 1 contains no restriction that could ensure that the variable-node degree of LDPC codeword bits is taken into account. In fact, the bits of LDPC codewords can be arbitrarily rearranged by permuting the columns of the LDPC code's parity-check matrix, which shows that the specification of a mapping of interleaved bits to substreams is not meaningful without restrictions on the LDPC code used.
The Board therefore agrees with the Examining Division that, in the absence of a relevant restriction in the claim on the LDPC code to use, the claimed mapping does not achieve a technical effect that distinguishes it from arbitrary mappings.
5.6 In this context, the appellant referred to decision G 1/03, which, in point 2.5.2 of its reasons, stated that the inclusion of non-working embodiments was of no harm if the specification contained sufficient information on the relevant criteria for finding appropriate alternatives over the claimed range with reasonable effort. In the present case, the application as filed would have given the skilled person sufficient information to find LDPC codes for which the claim achieved the desired effect.
But this is not a case where the claim can be said to include non-working embodiments. Apart from the specification of the codeword length, claim 1 does not contain any restriction, whether structural or functional, on the LDPC code to use.
5.7 The appellant also argued that documents E1 and E2 showed that the claimed mapping resulted in superior performance and was therefore not merely an arbitrary selection.
However, documents E1 and E2 relate to the specific LDPC codes defined in the DVB-S2 standard for code rates 1/3 and 2/5. Claim 1 is not limited to either of these codes.
5.8 In sum, the subject-matter of claim 1 lacks inventive step over document E3 (Article 56 EPC).
First auxiliary request
6. Inventive step
6.1 Claim 1 of the first auxiliary request limits the claim to a substream generating method of a signal transmitter "in a Digital Video Broadcasting (DVB)-Next Generation Handheld (NGH) system".
This amendment is based on the following passage on page 6, lines 21 to 26, of the description:
"The following description of the present invention is provided for a system using LDPC codes, for example, a broadcasting system such as Digital Video Broadcasting (DVB)-Next Generation Handheld (NGH) or a communication system such as Moving Picture Experts Group (MPEG) Media Transport (MMT), Evolved Packet System (EPS), Long-Term Evolution (LTE), and Institute of Electrical and Electronics Engineers (IEEE) 802.16m."
6.2 The appellant did not contest that the first (draft) specification of the DVB-NGH standard is document E5, which was published after the filing date (and even after the publication date) of the application. But it argued that the skilled person, at the priority date of the application, would have consulted the DVB-NGH "call for proposals" document, which made clear that the DVB-NGH standard was to be based on the DVB-T2 standard. The skilled person would therefore have consulted DVB-T2 standard documents, which would have led him to the LDPC codes for which the mapping of claim 1 achieved improved coding performance. Claim 1 had to be read as being limited to those LDPC codes.
6.3 The only reference to the DVB-NGH standard in the application as filed is the passage on page 6, which only generally states that the present invention is provided "for a system using LDPC codes", of which the DVB-NGH system is just one example. Since no DVB-NGH specification had yet been published at the filing date of the application, the skilled person would have interpreted this passage as meaning that the invention was of a kind that could be used in a broadcasting system such as the (then) future DVB-NGH system.
The only interpretation of the amendment of claim 1 which does not conflict with Article 123(2) and which the Board - to the appellant's benefit - adopts for the purpose of assessing inventive step is therefore that the signal transmitter performing the claimed method is of a kind that could be used in a broadcasting system such as the DVB-NGH system.
With this interpretation, the amendment does not restrict the claim to the use of any particular LDPC code. The claimed mapping therefore still does not achieve a technical effect that distinguishes it from arbitrary mappings.
6.4 As, moreover, the DVB-T2 signal transmitter of document E3 is of a kind that could be used in a broadcasting system such as the future DVB-NGH system, the subject-matter of claim 1 of the first auxiliary request lacks inventive step over that document (Article 56 EPC).
Second auxiliary request
7. Sufficiency of disclosure - Article 83 EPC
7.1 Claim 1 of the second auxiliary request adds to claim 1 of the main request the feature "according to a variable node degree of each of the LDPC codeword bits and an error probability of each of the modulated bits included in a 64-QAM symbol so as to minimize the error probability of the 64-QAM symbol".
7.2 The appellant did not dispute that, at the claimed invention's priority date, it was generally known that coding performance could be improved by basing the mapping of LDPC codeword bits to modulation bits on the variable-node degree of each LDPC codeword bit and the error probability of each modulation bit (see in particular documents D5, sections 4 and 4.3, and D6, section III). In other words, the feature added to claim 1 was part of the common general knowledge of the skilled person.
7.3 Nevertheless, the added feature does imply a restriction on the claimed subject-matter to the effect that "the error probability of the 64-QAM symbol" is "minimized". This means that claim 1 expresses an effect. Thus, the Examining Division's objection under Article 83 EPC potentially applies to this request (see point 4.3 above).
7.4 At the oral proceedings, the appellant agreed that, in the context of the invention, "minimized" was to be understood as "reduced" rather than "brought to its lowest possible value". The Board sees insufficient reason to doubt that, at the priority date, the skilled person would not have been able to fill in the various aspects of the method that claim 1 leaves open (in particular which LDPC code to use) in such a way that "the error probability of the 64-QAM symbol" is reduced. This corresponds to the appellant's view expressed in its statement of grounds of appeal, where it cited document E7 as evidence of the skilled person's common general knowledge.
7.5 In the oral proceedings, the appellant nevertheless argued that the skilled person, seeking to carry out the invention as defined by claim 1, would have had to resort to the DVB-T2 standard documents - to which he would have been referred by the DVB-NGH "call for proposals" document - to find an LDPC code that could be used with the specific mapping of table 1. However, this presupposes a narrower reading of claim 1 than that adopted by the Board in point 7.4 above. Furthermore, the Board does not agree that the skilled person reading the application would have interpreted the passage on page 6 quoted in point 6.1 above as an instruction to consult the DVB-NGH "call for proposals" document. The appellant's remaining arguments, relying on the skilled person subsequently consulting document E3 and even document E4 (published after the first three priority dates and adding, inter alia, the mapping of table 1 to document E3), therefore need not be discussed.
7.6 Thus, the invention as defined by claim 1 is sufficiently disclosed within the meaning of Article 83 EPC. In fact, the skilled person was able to put the invention into practice for the specific mapping of table 1 in the same way as he would have been able to do for any mapping of interleaved bits to substreams. In other words, the finding of sufficiency of disclosure is independent of the specific mapping of table 1.
8. Inventive step - Article 56 EPC
8.1 As noted in point 7.2 above, the feature added to claim 1 was per se part of the common general knowledge of the skilled person. It therefore cannot be the sole basis for acknowledging inventive step.
8.2 The appellant essentially argued that, in the presence of this added feature, the feature specifying that interleaved bits are mapped to substreams in accordance with the mapping defined by table 1 was no longer arbitrary because that mapping was one for which the skilled person could - via the DVB-NGH "call for proposals" - have found an LDPC code with which the claimed method could be carried out to achieve the effect now expressed in the claim.
8.3 As explained in points 7.4 to 7.6 above, the Board has found that the skilled person could have carried out the invention - including finding suitable LDPC codes - with the particular mapping of table 1 in the same way as with any other mapping. Hence, the specified mapping is still an arbitrary mapping in the sense that it is not technically distinguished from all other possible mappings. Thus, its selection does not contribute to inventive step.
8.4 The subject-matter of claim 1 therefore lacks inventive step over document E3 (Article 56 EPC).
Since none of the requests is allowable, the appeal is to be dismissed.
For these reasons it is decided that:
The appeal is dismissed.