T 2230/12 (LDPC encoding and decoding I/LG ELECTRONICS) 12-12-2017

1. The appellant's statement that it would not be attending the oral proceedings is, without indication to the contrary, to be understood as a withdrawal of its request for oral proceedings (see Case Law of the Boards of Appeal, 8th edition, 2016, III.C.2.3.1). The decision can therefore be taken without holding oral proceedings.

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

3. The invention

3.1 The application relates to encoding and decoding data using low-density parity-check (LDPC) error-correcting codes. Such codes are defined by a sparse parity-check matrix. Because in practical communication systems these matrices are very large, the process of encoding and decoding requires many calculations and much storage space.

3.2 The application discloses a technique by which a family of large parity-check matrices can be obtained from a single "first base matrix" having modest dimensions. This technique uses two main ideas.

The first is to associate a base matrix Hb, in which each value is either -1 or a non-negative integer, with a binary parity-matrix H as follows: in each position of base matrix Hb, the value -1 is replaced with a z×z zero matrix, the value 0 is replaced with a z×z identity matrix, and a positive "shift" value k is replaced with a z×z permutation matrix obtained by circularly shifting the identity matrix by k positions. The application refers to this process as "expanding" the base matrix Hb.

The second idea is to scale the values of the base matrix by z. This is done by fixing a maximum value zmax and designing a "first base matrix" corresponding to zmax. For a value z lower than zmax, a "second base matrix" is obtained by replacing each shift value shift(zmax) in the first base matrix with a value shift(z) derived from shift(zmax), for example by means of the formula shift(z) = floor(shift(zmax)z / zmax). This second base matrix can then be expanded by applying the first idea.

Main request

4. Claim 1 of the main request relates to an LDPC encoding method. It defines a "first base matrix" from which a parity-check matrix is generated. The entries of this matrix correspond to zero, identity and permutation matrices of size zmax×zmax. Dependent claim 2 further defines the encoding step of claim 1, specifying that a second base matrix having entries indicating z×z matrices is generated from the first base matrix, where z is smaller than zmax, and that the parity-check matrix is generated from this second base matrix by replacing the entries of the second base matrix with the z×z matrices.

In view of dependent claim 2 and the references in claim 1 to matrices of size zmax×zmax rather than z×z, the feature of claim 1 specifying that the parity-check matrix is "generated from a first base matrix" is to be understood as encompassing the steps of deriving a second base matrix from the first base matrix and expanding the second base matrix into the parity-check matrix.

5. Added subject-matter - Article 123(2) EPC

5.1 Whereas claim 1 of the second auxiliary request refused in the decision under appeal included the feature "zmax is equal to 96", present claim 1 specifies that "the maximum value of zmax is 96". In its communication, the Board expressed doubt as to whether the application as filed disclosed that the value of zmax for the first base matrix of claim 1 could be any positive integer up to 96.

5.2 The first base matrix of claim 1 appears only in description paragraphs [0016] and [0020] and in Figure 26 of the application as filed.

Paragraphs [0016], [0017], [0020] and [0021] disclose the generation of a parity-check matrix directly from a base matrix with a fixed expansion factor z = 96, without an intermediate step of "scaling" a first base matrix associated with a value zmax to a second base matrix associated with a value z. In the light of the detailed description of the invention starting from paragraph [0055], in particular paragraphs [0072] to [0077], the Board accepts that the application as a whole discloses the use of the matrix of paragraphs [0016] and [0020] as a "first base matrix" having zmax = 96, from which a second base matrix can be generated for values z lower than zmax. But this suggests to the skilled person only that the value zmax is equal to 96, not that it can be any positive integer up to 96.

Paragraph [00132], which explains that Figure 26 illustrates a base matrix for code rate 2/3, does not explicitly state an expansion factor, but it does mention a range of shift values from 0 to 95. Since the expansion factor z refers to the size of the z×z permutation matrices in the expansion of a base matrix, and shift values denote the number of positions by which the z×z identity matrix is shifted to obtain the required z×z permutation matrices, the skilled person understands the range from 0 to 95 to correspond to an expansion factor of 96.

These passages do not therefore disclose 96 as the maximum zmax value in the sense that lower zmax values can also be used for this matrix.

5.3 In the statement of grounds of appeal, the appellant also referred to paragraph [0096] of the application as filed and to original dependent claim 12.

Paragraph [0096] relates to an embodiment different from the one claimed: it explains that if the range of z is 10-96, one "first base matrix" could be used for the range 10-53 and another for the range 54-96. The paragraph does not refer to the specific first base matrix of claim 1, and the range 10-96 is said to be an example. It therefore gives no specific information on zmax values for the first base matrix of claim 1.

Original dependent claim 12, which in any case does not refer to the specific base matrix of present claim 1, only states that "zmax is 96".

These passages therefore do not support the appellant's position.

5.4 Hence, the subject-matter of claim 1 extends beyond the content of the application as filed, contrary to Article 123(2) EPC.

5.5 The appellant could have overcome this objection by reverting the amendment it had made when filing the appeal, i.e. by replacing the expression "the maximum value of zmax is 96" with "zmax is equal to 96", but the appellant chose not to make further submissions. Nevertheless, the Board considers it appropriate in the present case to consider also the questions of priority and novelty/inventive step.

6. Entitlement to priority/effective filing date

6.1 The only priority document disclosing the first base matrix of claim 1 is Korean patent application P13. The appellant took the position that the subject-matter of independent claim 1 of the main request was indeed entitled to the priority of this application.

6.2 Application P13 discloses the idea of defining a parity-check matrix H by means of a base matrix Hb (page 12, second full paragraph, of the English translation). It then discusses desirable properties of the base matrix (page 12, last paragraph, to page 15, third full paragraph). In the paragraph bridging pages 15 and 16, it presents the idea of using a first base matrix associated with a dimension zmax to generate (second) base matrices associated with other dimensions z. This is repeated on page 19, first full paragraph. The method of obtaining the second base matrix from the first base matrix by means of scaling (and the "floor" operation) is disclosed on page 19, second full paragraph, to page 20, last paragraph, but not with reference to any particular first base matrix.

None of the claims of application P13 is directed to the generation of a second base matrix associated with a value z from a first base matrix associated with a value zmax.

Application P13 discloses, in Figure 16, the first base matrix of claim 1 of the main request, including the two X marks. But neither the description nor the claims of P13 contain any reference to Figure 16.

6.3 As the Enlarged Board of Appeal held in opinion G 2/98 (OJ EPO 2001, 413), priority of a previous application is to be acknowledged only if the skilled person can derive the subject-matter of the claim directly and unambiguously, using common general knowledge, from the previous application as a whole. To derive the subject-matter of claim 1 from application P13, the skilled person has to take a number of steps. In particular, he needs to recognise

- that the matrix of Figure 16 is to be used as a "first base matrix" in the method disclosed on page 19, second full paragraph;

- that the two X marks are to be substituted with the same value, which is either 0 or 95; and

- that, for this matrix, zmax is to have a maximum value of 96.

For the reasons that follow, the Board takes the view that the skilled person would not directly and unambiguously infer from application P13 that the value of zmax for the matrix of Figure 16 is to be 96 (or lower). The other two steps therefore need no further consideration.

6.4 As explained earlier, the value zmax in claim 1 corresponds to the expansion factor z to be applied when expanding the first base matrix itself. For values of z lower than zmax, a second base matrix is generated by scaling down the shift values of the first base matrix.

6.5 As a basis in application P13 for a zmax value of (at most) 96 for the base matrix shown in Figure 16, the appellant referred to the passage on page 16, line 11, to page 17, line 2, in particular the phrase reading "if the range of the changing dimension (z) is between 10 and 96". It also submitted that P13 disclosed no other values for zmax.

6.6 The passage on page 16, line 11, to page 17, line 2, of application P13 largely corresponds to paragraph [0096] of the present application, discussed in point 5.3 above. This passage does not refer to any specific base matrix, let alone that of Figure 16; it specifically qualifies the range 10-96 as an example; and the idea of dividing a larger range (10-96) into two smaller ranges (10-53 and 54-96) and using a different "first base matrix" for each range does not correspond to the method disclosed on page 19, second full paragraph, of application P13 (nor to the claimed invention). This passage therefore gives no specific information on zmax values to be used for the matrix of Figure 16.

6.7 The appellant's argument that application P13 discloses no other value for zmax is incorrect, at least on the assumption that the skilled person would infer at all that the various matrices disclosed in P13 can serve as "first base matrix" in the scaling method disclosed on page 19, second full paragraph, to page 20, last full paragraph, i.e. that the skilled person would take the first of the steps listed in point 6.3 above. In particular, on page 18, line 18, to page 19, line 3, the matrix of Figure 13 is associated with z = 56 and the matrices of Figures 14 and 15 are associated with codeword lengths 576 and 672, which correspond to z = 24 and z = 28 respectively (the codeword length is equal to the number of columns of the parity-check matrix obtained by expanding the 24-column base matrices of Figures 14 and 15 by a factor of z). These examples disclose zmax values of 56, 24 and 28 to be used in the scaling method applied to these matrices. But application P13 suggests no such value for the matrix of Figure 16.

6.8 In sum, the subject-matter of claim 1 of the main request is not entitled to priority. The effective filing date for determining the state of the art under Article 54(2) EPC is therefore the application's filing date, which is 24 June 2005.

7. Public availability of documents D1 and D4

According to their cover pages, documents D1 and D4 were submitted to the IEEE 802.16 Broadband Wireless Access Working Group on 24 August 2004 and 27 January 2005 respectively. The "Release" sections of both documents state that the contributor "acknowledges and accepts that this contribution may be made public by IEEE 802.16", and both documents were in fact downloaded from web pages listing documents contributed to the working group (http://www.ieee802.org/16/tge/contrib/ and http://www.wirelessman.org/tge/contrib/). The Board therefore has no reason to doubt that both documents were made available on these web pages before 24 June 2005. The appellant has not argued otherwise.

Hence, the Board concludes that documents D1 and D4 belong to the prior art under Article 54(2) EPC for the subject-matter of claim 1 of the main request.

8. Novelty - Article 54(1) and (2) EPC

8.1 In its decision, the Examining Division found that the subject-matter of claim 1 of the then second auxiliary request lacked inventive step over document D4.

8.2 The appellant has not argued that the Examining Division's analysis of document D4 is incorrect, and the Board agrees with it.

Document D4 discloses methods of data encoding and decoding using an LDPC code whose parity-check matrix is obtained from a (first) "base model matrix". This base model matrix specifies shift sizes p(i,j) for an expansion factor z0 = 96 corresponding to the largest code length. Those shift sizes are proportionally scaled to shift sizes p(f,i,j) for an expansion factor zf, whereby fractional shift sizes are rounded down by means of the floor function (see page 4, section "Features"; page 11, last two paragraphs).

One of the base model matrices disclosed in document D4 is the "Rate 2/3 B code" matrix shown on page 12. This matrix is identical to the matrix of claims 1 and 3 with "X" set to 95. The "Rate 2/3 B code" is indeed subject to the scaling method (see page 11, last paragraph) rather than the modulo method also disclosed in document D4, as is the case, for example, for the "Rate 2/3 A code" matrix disclosed on the same page (see page 12, first paragraph).

Document D4 hence discloses a data encoding method that uses an LDPC parity-check matrix generated by expansion of a second base matrix with expansion factor z (= zf), the second base matrix being derived from a first base matrix as defined in claim 1 with expansion factor zmax = 96 (= z0).

8.3 Document D4, which - as mentioned above - was published in the context of the IEEE 802.16 Broadband Wireless Access Working Group, does not explain in detail how a parity-check matrix is obtained from a matrix of shift sizes and an expansion factor; it assumes that the reader has some background knowledge. This knowledge is available from other documents published in the same context, such as document D1. Indeed, document D1 describes on page 4, fourth and fifth paragraphs, how a parity-check matrix H is obtained from a model matrix Hbm by replacing non-negative entries of the model matrix with z×z identity matrices shifted by a corresponding number of positions and replacing "-1" with the z×z zero matrix.

The Board considers that the skilled person reading document D4 on the day it was published either possessed the necessary background knowledge or would have obtained it by having recourse, for example, to the related document D1 (see decision T 233/90 of 8 July 1990, reasons 3.3, for an analogous situation). He would therefore have understood the contents of document D4, including the matrix-expansion method it relies on, and would thus have directly and unambiguously derived from it an encoding method falling within the scope of claim 1 of the main request.

8.4 This means that the subject-matter of claim 1 is not new over document D4 (Article 54(1) and (2) EPC).

First auxiliary request

9. Claim 1 of the first auxiliary request relates to an LDPC decoding method. Compared with the independent claims of the main request, it does not define a specific first base matrix, but it does specify how the shift values in the second base matrix are derived from the shift values in the first base matrix, namely by means of the equation "shift(z) = floor(shift(zmax)z / zmax)".

10. Entitlement to priority/effective filing date

The earliest priority application disclosing the scaling of the entries of a first base matrix to obtain the entries of a second base matrix by means of the equation "shift(z) = floor(shift(zmax)z / zmax)" is Korean patent application P3, filed on 25 October 2004. In particular, this equation is not present in the English translation of either of the two earlier priority applications P1 and P2. The effective filing date for the purpose of establishing the prior art under Article 54(2) EPC for the subject-matter of independent claim 1 of the first auxiliary request is therefore 25 October 2004 at the earliest. The appellant has not disputed this.

11. Public availability of document D1

For the reasons given in point 7. above, the Board has no reason to doubt that document D1 was made available to the public before 25 October 2004, and the appellant has not disputed this.

Hence, the Board finds that document D1 is prior art under Article 54(2) EPC for the subject-matter of claim 1 of the first auxiliary request.

12. Inventive step - Article 56 EPC

12.1 Document D1 discloses methods of encoding and decoding data using an LDPC code whose parity-check matrix is obtained from a (second) base model matrix by replacing each entry of the matrix with either a z×z permutation matrix or the z×z zero matrix (page 1, section titled "Features"; page 4, second to fifth paragraphs). The entries p(f,i,j) of the second base model matrix for expansion factor z = zf are obtained from a (first) base model matrix having entries p(i,j) corresponding to a maximum expansion factor z0 by means of the equation p(f,i,j) = [p(i,j)zf / z0], where "[x] denotes rounding to the integer that differs from x the least" (page 5, "Model Matrix Set" section).

12.2 The subject-matter of claim 1 therefore differs from the method of document D1 in that fractional scaled values are rounded down rather than rounded to the nearest integer.

12.3 The Board considers that the skilled person is well aware of the possible ways of rounding a non-integral value to an integer, including rounding down, rounding up and rounding to the nearest integer. For a particular selection from these well-known equivalents to support an inventive step, it would have to be established that, in the context of the claimed invention, the selection made contributes to a surprising technical effect.

12.4 The appellant argued that rounding down, i.e. using the floor function, saved resources. This was stated explicitly in paragraph [00115] of the application. Document D1 contained no suggestion that resources could be saved by replacing its rounding function with the floor function.

12.5 However, paragraph [00115] merely states that "It is possible to simplify the complexities by implementing the flooring function to hardware or software". In the Board's view, this is stating the obvious: the required calculations necessarily have to be implemented in hardware, software or a combination of both. The paragraph does not say that use of the floor function saves resources as compared with other rounding methods.

More importantly, both the claim and the application are silent on how the floor function or the claimed calculation of shift(z) is to be implemented in either software or hardware. The Board does not find it plausible that the floor function inherently leads to resource savings in the implementation of the decoding method as compared with the rounding function of document D1, in the absence of details regarding the implementation.

Since the claimed use of the floor function is not considered to save resources, it is not relevant that neither document D1 nor any of the other documents on file suggests that resources can be saved by means of the floor function.

12.6 The appellant further argued that even in the absence of an effect, it was not permissible to formulate the objective technical problem as that of finding an alternative for the rounding method of document D1. The skilled person starting from document D1 would recognise, from the formula presented in the "Model Matrix Set" section on page 5, that the document was aiming for a proportional mapping of shift values. For that purpose, rounding to the nearest integer was more appropriate than rounding down. In particular, the floor function resulted in a "broad range of the proportionality constant" and the nearest-integer function in a "quite small range".

12.7 The passage on page 5 of document D1 cited by the appellant indeed mentions that the shift sizes p(f,i,j) are derived from the shift sizes p(i,j) "by scaling p(i,j) proportionally", and this is also what the formula given in that section does: it scales the value p(i,j) proportionally by multiplying with a fractional constant and rounds the result to the nearest integer. The formula of claim 1 does precisely the same, and with the same fractional proportionality constant, except that it rounds the fractional result of the multiplication down instead of to the nearest integer. The Board sees no reason why the mention of "proportionally" in document D1 would deter the skilled person from considering alternative rounding methods.

12.8 In sum, since rounding down is one of the well-known ways of rounding a non-integral value to an integer and does not achieve any surprising technical effect in the context of the claimed invention, the subject-matter of claim 1 lacks inventive step over document D1 (Article 56 EPC).

Second auxiliary request

13. Compared with claim 1 of the main request, claim 1 of the second auxiliary request includes no limitation on the value of zmax but specifies that "'X' is an integer selected among '0' and a positive integer smaller than zmax".

14. Added subject-matter - Article 123(2) EPC

14.1 The second auxiliary request corresponds to the main request refused by the Examining Division on the ground of added subject-matter. The Examining Division took the view that the application as filed disclosed the claimed first base matrix neither in conjunction with zmax values other than 96, nor in combination with any non-negative value of the integer X smaller than zmax.

14.2 The appellant argued that paragraph [0073] of the present application generally disclosed zmax as the "largest dimension", without a limitation to any particular value. It was therefore not mandatory to limit the claimed subject-matter to zmax = 96. And it was clear from the application as a whole, and in particular from paragraph [0073], that parameter X was limited only by zmax. Paragraph [00132], which limited the value to the range from 0 to 95, was just an example.

14.3 Paragraph [0073] introduces the general idea that second base matrices for various expansion factors z are generated from a first base matrix for a "largest" expansion factor zmax. It does not limit zmax to any specific value, but neither does it relate to a specific first base matrix. The skilled person would therefore not infer from it that any first base matrix can be used with arbitrary zmax values. And since it does not relate to the first base matrix of claim 1, it cannot give information about possible values for parameter X. Paragraph [0073] does not therefore support the appellant's position.

14.4 As the Board has explained in point 5.2 above, the application as filed consistently presents the matrix of claim 1 in conjunction with an expansion factor of 96, suggesting a zmax value of 96 when the matrix is used as a "first base matrix".

The application as filed further discloses, in paragraphs [0017] and [0021], that parameter X is an integer between 0 and 95. Paragraph [00132] states that X is an integer from 0 to 95, adding that X is preferably one of 86, 89 and 95 and that most preferably X is 95.

14.5 Since the application as filed lists a number of specific example base matrices without mentioning a particular expansion factor (see in particular Figures 14a to 14f, 15 to 22 and 24 and their description in paragraphs [00123] to [00129] and [00131]), there is room for the argument that the skilled person would recognise that there is, in general, some freedom in choosing the zmax value to be used for a particular first base matrix without varying (for example by scaling) the values of the matrix entries.

14.6 To derive the subject-matter of claim 1, however, the skilled person has to recognise, without doubt, not only that there is freedom in choosing the zmax value for the matrix of claim 1, but also that the range of possible values of the two matrix entries determined by parameter X varies depending on the value of zmax, namely that it runs from 0 to zmax-1. But paragraph [00132] states that X is an integer from 0 to 95, not that it is an integer from 0 to zmax-1, and it mentions 86, 89 and 95 as preferable values and 95 as the most preferable value of X. In the Board's view, the skilled person would not recognise without doubt that the value 95, specifically mentioned to be the most preferable, is to be understood as zmax-1, and he would not know how to relate the two preferable values 86 and 89 to a range of values of X from 0 to zmax-1, where zmax could even be lower than 86.

14.7 Hence, the application as filed does not disclose that, for a first base matrix as specified in claim 1, the value of X can be any integer from 0 to zmax-1, where zmax can be values other than 96.

14.8 It follows that the second auxiliary request does not comply with Article 123(2) EPC.

Third auxiliary request

15. Compared with claim 1 of the main request, claim 1 of the third auxiliary request includes no limitation on the value of zmax and specifies that the integer X is 0 or 1 or 95.

16. Admission into the proceedings - Article 12(4) RPBA

16.1 The third auxiliary request corresponds to the first auxiliary request filed with the written submissions in preparation for the oral proceedings before the Examining Division. That request was withdrawn in the course of those oral proceedings, after the chairman had noted that it gave rise to the same objections as the then main request (corresponding to the present second auxiliary request) and had asked whether the appellant wished to maintain it.

16.2 If a request withdrawn before the examining division is resubmitted on appeal, a board will normally, in the exercise of its discretion under Article 12(4) RPBA, not admit the request into the proceedings (see Case Law of the Boards of Appeal, 8th edition 2016, IV.E.4.3.3 c)); an appellant is not free to select the board of appeal as the first instance to rule on a particular issue.

16.3 In the present case, however, the request's withdrawal cannot be said to have precluded the Examining Division from giving a ruling on the critical issues of the then first auxiliary request: it is clear that the Examining Division would have refused the first auxiliary request for essentially the same reasons as given for the main request. And although the appellant could theoretically have attempted to defend the request before the Examining Division by pointing out a relevant difference with regard to the main request, the appellant would not have been obliged to do so if he had maintained the first auxiliary request. The withdrawal of the request therefore makes no material difference for these appeal proceedings.

16.4 The Board therefore admits the third auxiliary request into the proceedings.

17. Added subject-matter - Article 123(2) EPC

17.1 In the statement of grounds of appeal, the appellant argued that 0, 1 and 95 as possible values for the integer X were disclosed in paragraph [0017], which stated that X was an integer "between 0 and 95", and in paragraph [00132], which stated that X was an integer "from 0 to 95". The value 1 was the next integer after 0.

17.2 The appellant apparently reasoned that "between 0 and 95" had to be read as "from 1 to 94", which then disclosed "1" as an end point. But, in particular in light of the disclosure of the range "from 0 to 95" in paragraph [00132] as possible values for X and the mention of 95 as "the most preferable value", the Board considers that the range of values "between 0 and 95" referred to in paragraph [0017] can only be understood as including 0 and 95. The passages referred to by the appellant do not therefore give a basis for singling out "1" as a possible value for the integer X.

17.3 The Board has not been able to identify any other passage in the original application as a basis for the specific value "1" for the integer X. The third auxiliary request therefore does not comply with Article 123(2) EPC.

18. Conclusion

Since none of the requests on file is allowable, the appeal is to be dismissed.