T 0632/12 (LDPC code parity-check matrix/GOOGLE TECHNOLOGY HOLDINGS) 07-06-2017

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 encoding and decoding of data by means of low-density parity-check (LDPC) codes. Such codes are based on a large sparse binary parity-check matrix H. When transmitting information, the matrix H is used to determine parity-check bits corresponding to the bits of a symbol set representing the information to be transmitted, and the parity-check bits are transmitted along with the symbol set.

To reduce memory requirements and allow parallel encoding and decoding, it is advantageous to employ a "structured LDPC design" starting from a small mb×nb base matrix Hb. This base matrix is expanded to a full matrix H of size m×n, where m=mb×z and n=nb×z, by replacing each 1 in Hb with a z×z submatrix (typically a permutation submatrix) and each 0 with the z×z all-zero submatrix.

2.2 The invention proposes a family of base matrices together with assignments of submatrices that is said to result in LDPC codes which have good error-correcting performance and can be efficiently encoded and decoded.

The proposed base matrices Hb according to claim 1 of the main request consist of a part Hb1 corresponding to systematic bits and a part Hb2 corresponding to parity-check bits. This is depicted as follows in Equation (6) on page 10 of the application as published:

FORMULA/TABLE/GRAPHIC

The part Hb2 is again composed of a first part hb and a second part H'b2, where hb consists of a single column having an odd weight (i.e. number of 1s) greater than 2 and H'b2 has a staircase structure as follows:

FORMULA/TABLE/GRAPHIC

In the expansion of Hb, for each column of H'b2 the two 1s are replaced with identical submatrices. The expansion of hb "uses submatrices that are identical for an even number of 1s except one 1". The Board understands this as meaning that 1s in hb are replaced pairwise with identical submatrices, leaving a single 1 to be replaced with an arbitrary submatrix (given that hb has odd weight) (see page 5, lines 2 to 4; page 11, lines 3 to 10).

2.3 The structure of the parity part as defined by claim 1 of the main request is identical to that defined by claim 1 of the sole request refused by the Examining Division and to that defined by claim 1 of the first auxiliary request. The differences between these claims are discussed below under points 4 and 5.

3. Document D1

3.1 Document D1 was retrieved from the Internet. Its cover page indicates that it was submitted to the IEEE 802.16 Broadband Wireless Access Working Group on 1 May 2004. According to the "Release" section on the same page, the contributor "acknowledges and accepts that this contribution may be made public by IEEE 802.16".

The Board has no reason to doubt the accuracy of the cover page, which was not contested by the appellant. It follows that the recipient of the submission made on 1 May 2004 was not bound by confidentiality. There is, however, some room for discussion as to whether this recipient is to be regarded as a "member of the public", which is a precondition for the submission itself to qualify as an act of "making available" within the meaning of Article 54(2) EPC (on the one hand, see decisions T 834/09 of 2 February 2012, reasons 5.2, and T 343/12 of 21 April 2015, reasons 1.3; on the other hand, see decisions T 314/99 of 21 June 2001, reasons 5.5, T 1081/01 of 27 September 2004, reasons 6, and T 1057/09 of 25 October 2011, reasons 5.23).

This issue need not be resolved, as document D2 shows that document D1 was uploaded to a public file server on 1 May 2004 (or on 30 April 2004, depending on time zone) and was thereby made available to the public. Document D2 is the printout of a conversation held between subscribers to an IEEE 802.16 mailing list and contains, in particular, a reply dated 30 April 2004 to a message dated 1 May 2004. The reply mentions that a document with version number "86r1" has been uploaded to the address http://ieee802.org/16/tgd/contrib/C80216d-04_86r1.pdf. The Board has verified that the document available at this address is identical to document D1.

The earliest priority date of the application being 9 August 2004, it follows that document D1 is part of the state of the art under Article 54(2) EPC.

3.2 Document D1 relates to "block LDPC codes" for use in an encoder (see page 2, Figure 1) as part of an implicitly disclosed transmitter (see title, "LDPC coding for OFDMA PHY"). According to the last paragraph on page 2, a block LDPC code is "an almost structured LDPC codes [sic] whose parity-check matrix consists of small square blocks which are the zero matrix or a circulant permutation matrix". The matrix H shown on page 3 is an mNs×nNs matrix consisting of m×n submatrices of size Ns×Ns, each submatrix being either a shifted identity matrix (denoted P**(0), P**(1), P**(2), ...) or the zero matrix (denoted P**(INF)); see page 3, first paragraph. In the terminology of the present application, the matrix H is "expanded" from an m×n base matrix by replacing each entry with a z×z submatrix, where z=Ns. The matrix H is used to calculate the parity-check bits of code words to be transmitted (see page 1, second paragraph, to page 2, third paragraph).

3.3 In document D1 the parity-check matrix H is composed of submatrices A, B, T, C, D and E as follows (see page 1, equation (2)):

FORMULA/TABLE/GRAPHIC

At the bottom of page 4 and on pages 5 to 9, example matrices A, B, T, C, D and E are specified in terms of the exponents of the right-shifted identity matrix P (the exponent INF denoting the zero matrix).

3.4 As pointed out by the appellant in the statement of grounds of appeal and confirmed by equations (2) and (3) and their accompanying text on page 1 of document D1, the matrices A and C are intended to correspond to the systematic part of H, while the matrices B, T, D and E are intended to correspond to the parity part of H. This is consistent with the matrix sizes disclosed on page 1 of document D1: the part consisting of submatrices A and C has size Np×Nk, and the part consisting of submatrices B, T, D and E has size Np×Np, where Nk is the number of information bits and Np is the number of parity bits.

3.5 The Examining Division decided that the subject-matter of the then claim 1 was not new in view of document D1. In particular, it found that the parity-check matrix defined by the "Code Rate = 3/4" example on page 8 satisfied the restrictions on the parity part Hb2 imposed by the then claim 1 (and described in point 2.2 above). This example specifies the following matrices A, B, T, C, D and E:

FORMULA/TABLE/GRAPHIC

3.6 In the statement of grounds of appeal, the appellant submitted that, in this example, the leftmost column of the parity part of H (referred to as hb in the application) was formed by matrices B and D, which was not a column in which there were "identical sub-matrices for an even number of 1s except one 1" as required by the claim.

3.7 The Board notes, however, that page 8 of document D1 contains an error - or at least deviates from the general disclosure on pages 1 to 4 and the other examples on pages 5 to 7 and 9 - in that the matrices B and D belong to the systematic part of the parity-check matrix rather than the parity part. Indeed, the part consisting of A and C has size 8Ns×23Ns, and the part consisting of B, T, D and E has size 8Ns×9Ns. Since this gives a combined matrix H of size 8Ns×32Ns, it follows that Np=8Ns and Nk=24Ns (see document D1, page 1, second paragraph, which confirms the basic fact that a parity-check matrix has size (Nc-Nk)×Nc, where Nc-Nk=Np). Thus, in this case, the systematic part of H is the 8Ns×24Ns matrix consisting of A, B, C and D, and the parity part of H is the 8Ns×8Ns matrix consisting of T and E.

3.8 Consequently, the parity part of the parity-check matrix of the "Code Rate = 3/4" example is an expansion of an 8×8 matrix Hb2 consisting of an 8×1-column hb and an 8×7 part H'b2, where hb corresponds to the leftmost column of T and E and H'b2 corresponds to the remaining part of T and E.

Since a "0" in T and E corresponds to P**(0), i.e. to the (non-zero) Ns×Ns identity matrix, and a "INF" corresponds to a zero Ns×Ns matrix (see the example at the bottom of page 4 of document D1), it is evident that H'b2 has the staircase structure required by claim 1 of the main request and that the two 1s in each column are expanded to identical submatrices, also as required by claim 1 of the main request.

The leftmost column of T and E (transposed to row form) is [0 INF INF INF Ns-1 INF INF 0]. This corresponds to an expansion of [1 0 0 0 1 0 0 1] of odd weight 3, where the first and last 1s are both replaced with the Ns×Ns identity matrix P**(0), and the remaining 1 is replaced with a shifted Ns×Ns identity matrix (shifted Ns-1 times to the right). Thus, hb and the corresponding expansions likewise are as required by claim 1 of the main request.

3.9 As to the consequence of document D1 including the above-mentioned error on page 8, the Board notes that a document normally forms part of the state of the art, even if its disclosure is deficient, unless it can be proved that the disclosure is not enabling or that the literal disclosure is manifestly erroneous and does not represent the intended technical reality (see decision T 230/01 of 26 April 2005, reasons 5.2, and Case Law of the Boards of Appeal, 8th edition, I.C.4.9).

In the present case, the skilled person would, whether he is aware of the error or not, directly and unambiguously derive a parity-check matrix from the example on page 8, namely the parity-check matrix H composed of matrices A, B, T, C, D and E arranged as shown in point 3.3 above. It is this matrix H that satisfies the restrictions on the parity part imposed by the invention.

In fact, upon detecting the error, the skilled person reading document D1 would have no problem recognising, for example by comparing matrix sizes, that the column specified by matrices B and D should have been included as the rightmost column in matrices A and C, and that matrices B and D should have been formed from what on page 8 is the leftmost column of T and E. It is important to note that performing this correction leaves the resulting parity-check matrix unchanged; only the decomposition of the matrix H into matrices A, B, T, C, D and E is affected.

4. Main request - novelty

4.1 The main request was not filed with the statement of grounds of appeal but only after the Board had arranged oral proceedings. Its admission is therefore within the Board's discretion under Article 13(1) and (3) RPBA. Since the amendments made do not raise issues which the Board cannot deal with, the main request is admitted into the proceedings.

4.2 Apart from minor clarifications, claim 1 of the main request differs from claim 1 considered in the decision under appeal only in the addition of the words "for any selected code rate" to the feature characterising the submatrices to be substituted for the 1s in the column hb. The appellant has added these words in an attempt to distinguish the claimed invention from the method of document D1 as applied to the "Code Rate = 3/4" example.

4.3 However, the added words do not limit the subject-matter claimed. Claim 1 specifies particular restrictions on the submatrices used in the expansion of column hb (as discussed in point 2.2 above). The statement that this holds "for any selected code rate" adds nothing to those restrictions.

4.4 The appellant is correct in stating that only the "Code Rate = 3/4" example of document D1 discloses a parity-check matrix in which the expansion of the column corresponding to hb "uses submatrices that are identical for an even number of 1s except one 1". But claim 1 does not rule out H being the parity-check matrix of the "Code Rate = 3/4" example (in which case the code rate - which is a function of the size of the parity-check matrix - is indeed 3/4).

4.5 Thus, the subject-matter of claim 1 of the main request is still anticipated by the LDPC encoding and transmitting method disclosed in document D1 for code rate 3/4 in accordance with the analysis given under point 3 above. It is therefore not new (Article 54(1) and (2) EPC).

5. First auxiliary request - admission

5.1 Admission into the proceedings of the first auxiliary request is again within the Board's discretion under Article 13(1) and (3) RPBA.

5.2 Claim 1 of the first auxiliary request does not include the phrase "for any selected code rate" that was added to the main request. Instead, in claim 1 the text "the method comprising the steps of" has been replaced with "the method, for code rates other than 3/4, comprising the steps of".

According to the appellant, this amendment is intended as a disclaimer, limiting the claimed method to code rates other than 3/4. The appellant has not indicated a basis in the original application for this amendment or given arguments why the disclaimer is an allowable undisclosed disclaimer.

5.3 The Board has not been able to identify in the original application any mention of a code rate of 3/4, let alone a specific indication that code rate 3/4 may be excluded from the scope of the invention. The disclaimer is therefore a so-called undisclosed disclaimer, disclaiming subject-matter which is not specifically disclosed in the original application.

5.4 The appellant may have considered the disclaimer to be allowable under the conditions set out in decision G 1/03 (OJ EPO 2004, 413). Indeed, it noted that only the "Code Rate = 3/4" example could be detrimental to novelty and that "the inventors of D1 have failed to appreciate the benefits of the specific limitations as specified in the claim", which could be understood as a suggestion that the "Code Rate = 3/4" example is an "accidental anticipation".

5.4.1 According to the order of decision G 1/03, "an anticipation is accidental if it is so unrelated to and remote from the claimed invention that the person skilled in the art would never have taken it into consideration when making the invention". The fact that the disclosure belongs to a remote or unrelated technical field may be important, but it is not decisive; the anticipation must be such that it "has nothing to do with the teaching of the claimed invention" (G 1/03, reasons 2.2.2).

In the present case, document D1 and its examples relate to LDPC codes and thus belong to the same technical field as the claimed invention. Both document D1 and the claimed invention concern the problem of constructing an LDPC parity-check matrix having advantageous properties by expanding a suitable base matrix. It cannot be said that document D1 "has nothing to do with the invention" or that the skilled person "would never have taken it into consideration when making the invention". It is thus not an accidental anticipation within the meaning of G 1/03.

5.4.2 Also, the present disclaimer does not satisfy the requirement of decision G 1/03 that it does not remove more than is necessary to restore novelty: it removes from the scope of claim 1 all parity-check matrices corresponding to a code rate of 3/4 and not just the specific parity-check matrix of the "Code Rate = 3/4" example.

5.4.3 Hence, the disclaimer included in claim 1 cannot be justified on the basis of decision G 1/03.

5.5 A further Enlarged Board of Appeal decision relating to disclaimers is G 2/10 (OJ EPO 2012, 376). This decision is concerned with amendments that disclaim subject-matter which is disclosed in the application as filed (see reasons 2.1). It is therefore not directly applicable to the present case.

5.6 Currently, further questions relating to the allowability of disclaimers are pending before the Enlarged Board of Appeal as case G 1/16, arising from a referral made in interlocutory decision T 437/14 of 17 October 2016. Essentially, the Enlarged Board is being asked whether the "gold standard" disclosure test is also to be applied to claims containing undisclosed disclaimers and, if so, whether the exceptions formulated in decision G 1/03 no longer apply. In case the exceptions relating to undisclosed disclaimers are to be applied in addition to the gold standard, the Enlarged Board is asked to consider whether the gold standard is to be modified in view of those exceptions.

This Board does not wish to speculate on the outcome of case G 1/16 but observes that it cannot be ruled out entirely that the Enlarged Board's answers will affect the test for the allowability under Article 123(2) EPC of undisclosed disclaimers - even those that do not strictly comply with the conditions set forth in decision G 1/03.

It could, therefore, be argued that proceedings in the present case should be stayed until the questions now pending as case G 1/16 have been answered.

5.7 Staying the proceedings would mean, however, that the inclusion of the disclaimer in claim 1 of the first auxiliary request - an amendment made after the Board arranged oral proceedings - raises an issue which the Board cannot deal with without adjournment of the oral proceedings. This is a situation which strongly suggests that the first auxiliary request should not be admitted into the proceedings under Article 13(1) and (3) RPBA.

In this context, the Board notes that the disclaimer was added to restore novelty over document D1, i.e. to overcome the very objection which formed the ground for refusal. The first auxiliary request could have been filed with the statement of grounds of appeal, if not earlier.

This argument of lateness could perhaps be countered with the argument that at the time of filing the appeal there was no doubt - in view of the case law - that the disclaimer infringed Article 123(2) EPC, whereas the referral made in decision T 437/14 has at least some potential to change this situation.

The Board finds this counterargument not necessarily persuasive, as it was always open to the appellant to argue that the disclaimer complied with Article 123(2) EPC, even if the case law may have suggested otherwise. In any event, the appellant has not raised this counterargument or any other relevant argument in support of the admissibility or of the allowability under Article 123(2) EPC of the first auxiliary request; it has left it entirely to the Board to investigate whether and for what reason the disclaimer may be allowable.

5.8 In these circumstances, the Board considers it appropriate not to admit the first auxiliary request into the proceedings.

6. Conclusion

Since the main request is not allowable and the first auxiliary request is not admitted into the proceedings, the appeal is to be dismissed.