T 1255/16 (Irregular LDPC code/ZTE) of 15.2.2019

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 05749661.4, which claims a priority date of 23 January 2005 and was filed in Chinese as PCT/CN2005/000671 and published in English under Article 158(3) EPC 1973 as EP 1 850 484 A1.

II. The decision cited the following document:

D1:|R. Xu et al.: "High girth LDPC coding for OFDMA PHY", IEEE C802.16e-04/423, IEEE 802.16 Broadband Wireless Access Working Group, 3 November 2004, retrieved from http://www.ieee802.org/16/tge/contrib/C80216e-04_423.pdf.|

The Examining Division decided that the subject-matter of claims 1 and 7 of the then sole substantive request infringed Article 123(2) EPC and that claims 1 and 7 were neither clear nor concise within the meaning of Article 84 EPC.

III. In its statement of grounds of appeal, the appellant replaced its sole substantive request with a main request and an auxiliary request.

IV. In a communication accompanying a summons to oral proceedings, the Board expressed the preliminary view that neither the main request nor the auxiliary request complied with Articles 84 and 123(2) EPC and that the subject-matter of claim 1 of both requests lacked inventive step over document D1.

V. In a letter dated 15 January 2019, the appellant filed a set of amended claims based on the main request submitted with the statement of grounds of appeal. It gave arguments in support of their allowability and stated that it would not attend the oral proceedings. It requested that a communication pursuant to Rule 71(3) EPC be issued.

It also submitted the following two documents:

D4:|US 8 185 797 B2, published on 22 May 2012; and |

D5:|R. Xu et al.: "High Girth LDPC Coding for OFDMA PHY", IEEE C802.16e-05/031r1, IEEE 802.16 Broadband Wireless Access Working Group, 25 January 2005.|

VI. In a further communication, the Board informed the appellant that it understood the appellant's intention to have been that the newly filed claims replaced the previously pending substantive requests as a sole substantive request. The appellant did not comment on this communication.

VII. Oral proceedings were held on 15 February 2019 in the appellant's absence. At the end of the oral proceedings, the chairman pronounced the Board's decision.

VIII. Claim 1 of the amended claims filed by letter of 15 January 2019 reads as follows:

"An encoder based on irregular low density parity check, LDPC, codes based on a unit matrix and its cyclic shift matrix comprising an encoding operation module, a basic matrix storage module and an extension module, characterized in that:

said basic matrix storage module is configured to store a basic matrix Hb consisting of an M×(N-M) block A corresponding to information bits and an M×M block B corresponding to check bits; in the basic matrix Hb, for all cycles with length of 4, any element of i, j, k and l constituting the cycle in anti-clockwise or clockwise order always satisfies an inequality: mod (i-j+k-l, z) != 0, wherein mod represents a modulo operation, and z is an extension factor, z=L/N, L is a length of codeword, N is a number of columns in the basic matrix Hb, L, M, and N are integers that are greater than 0;

and said basic matrix Hb also satisfies one of following conditions:

1) supposing the number of columns with the largest weight in the basic matrix Hb is r, then in each new basic matrix formed by deleting random r-1 columns herein, for all cycles with length of 4, any element of i, j, k and l constituting the cycle in anti-clockwise or clockwise order always satisfies the inequality: mod (i-j+k-l, z) != 0, and in the each new basic matrix, for all cycles with length of 6, any element of i, j, k, l, m and n constituting the cycle in anti-clockwise or clockwise order always satisfies an inequality: mod (i-j+k-l+m-n, z) != 0; or

2) supposing the number of the columns with the largest weight in the basic matrix Hb is r, then in each new basic matrix formed by deleting random r-1 columns and all columns with weight of 3 therein, for all cycles with length of 4, any element of i, j, k and l constituting the cycle in an anti-clockwise or clockwise order always satisfies the inequality: mod (i-j+k-l, z) != 0, and in the each new basic matrix, for all cycles with length of 6, any element of i, j, k, l, m and n constituting the cycle in an anti-clockwise or clockwise order always satisfies the inequality: mod (i-j+k-l+m-n, z) != 0; wherein i, j, k, l, m, n-Hb, and i, j, k, l, m, n are integers equal to or greater than 0 and less than or equal to z-1;

said extension module is configured to extend said basic matrix Hb according to the extension factor z and a z×z basic permutation matrix to obtain a (M×z) × (N×z) parity check matrix of LDPC codes; and

said encoding operation module is configured to perform an encoding operation on source data of (N-M)×z bits to obtain a codeword of N×z bits based on the (M×z) × (N×z) parity check matrix obtained from extension of said basic matrix Hb;

wherein weight of the column represents the number of non-negative elements in the column."

IX. The appellant's arguments, where relevant to the decision, are discussed in detail below.

Reasons for the Decision

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

2. The appellant's requests - Article 113(2) EPC

2.1 In its letter of 15 January 2019, the appellant did not state whether it maintained or withdrew the main request and the auxiliary request filed with the statement of grounds of appeal. The absence of an explicit statement to the effect that pending substantive requests are maintained normally cannot be taken to mean that those requests are withdrawn.

2.2 In the present case, however, the letter lacks any argument in support of the previously filed requests and merely gives reasons why the newly filed amended claims comply with the EPC. In the Board's view, this is an indication that the appellant meant to replace its pending requests with the newly filed claims.

2.3 Moreover, if it were to be assumed that the main request and the auxiliary request were maintained, the appellant's letter would leave the Board in doubt about the order in which it was to consider its requests: the appellant referred to the newly filed claims only as "amendments", not as "a new main request" or "a second auxiliary request". Under Article 113(2) EPC, the EPO is to examine, and decide upon, the European patent application only in the text submitted to it, or agreed, by the applicant. In the case of multiple substantive requests, this means that it is the responsibility of the applicant or appellant to specify the order in which its requests are to be examined (see decisions T 255/05 of 18 October 2005, reasons 17; T 1312/13 of 6 December 2017, reasons 2.3).

2.4 In view of these considerations, the Board informed the appellant, in its further communication, that it assumed that the previously filed requests had been withdrawn and that the amended set of claims formed the basis for the appellant's sole substantive request. Since the appellant did not express disagreement with this observation, the Board now considers it to have been established that the main request and the auxiliary request filed with the statement of grounds of appeal are no longer maintained and that the appellant requests that the decision under appeal be set aside and that a patent be granted on the basis of the claims filed with the letter of 15 January 2019. The Board is therefore in a position to proceed with the examination of the appeal without infringing Article 113(2) EPC.

3. The application

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 these matrices can be very large, the application considers parity-check matrices H that are constructed by "expanding" a smaller basic matrix Hb. In this expansion process, each element j of the basic matrix Hb is replaced with a z×z matrix that is either the z×z zero matrix (if j = -1) or the j**(th) power of a cyclic right shift of the z×z unit matrix (if j >= 0) (see paragraphs [0051] to [0053] and [0093] of the A1 publication). The integer z is referred to as the "expansion factor".

3.2 An LDPC parity-check matrix can be represented as a bipartite graph (known as the "Tanner graph") on N "variable nodes" corresponding to the columns of the matrix, and M "check nodes" corresponding to the rows of the matrix, a variable node being connected to a check node by an edge if the element in the corresponding row and column of the matrix is a "1" (paragraph [0048]). The "girth" of this graph, i.e. the length of its shortest cycle, is an indicator for the error-correcting performance of the LDPC code. As explained in paragraph [0050] of the application, ideally the girth of the graph is as large as possible, and the number of cycles in the graph having a length equal to the girth is as low as possible.

The Board notes that since the "Tanner graph" is bipartite (because there are no edges between variable nodes or between check nodes), the length of each cycle in the graph is necessarily even.

3.3 Paragraph [0055] of the application explains that the girth of the parity-check matrix H is related to the girth of the basic matrix Hb. The application then lists "sufficient and necessary conditions" in terms of conditions on the basic matrix Hb and the expansion factor z for the girth of the parity-check matrix H to be at least six (in paragraph [0056]), at least eight (in paragraph [0057]) and at least ten (in paragraph [0058]).

In particular, paragraph [0056] states that for the girth of the matrix H to be at least six, it is sufficient and necessary that "in its basic matrix, for all girths with length of 4, any element of i, j, k and l constituting the basic matrix in anti-clockwise or clockwise (the effect is equivalent for clockwise order and anti-clockwise order) always satisfies: mod (i-j+k-l, z) != 0, wherein mod is modular operation, and z is the extension factor, an even number".

And paragraph [0057] states for the girth of the matrix H to be at least eight, it is sufficient and necessary that "in its basic matrix, for all girths with length of 4, any element of i, j, k and l constituting the basic matrix in anti-clockwise or clockwise always satisfies: mod (i-j+k-l, z) != 0; and for all girths with length of 6, any element of i, j, k, l, m and n constituting the basic matrix in anti-clockwise or clockwise always satisfies: mod (i-j+k-l+m-n, z) != 0".

3.4 To understand these somewhat cryptically formulated conditions, it is helpful to consider Figures 4 and 5 of the application, which show - according to paragraph [0049] - "the general forms of girths with length of 4 and 6 respectively in the LDPC parity check matrix", and to realise that what is meant is "cycles of length 4 and 6" rather than "girths with length 4 and 6".

FORMULA/TABLE/GRAPHIC

3.5 A cycle of length 4 in the Tanner graph of the LDPC matrix H corresponds to two columns/variable nodes xi and xj and two rows/check nodes cp and cq for which the matrix H has 1s at their four intersections (as shown in Figure 4). These 1s in the matrix H are part of right-shifted z×z unit matrices and therefore correspond to non-negative elements in the basic matrix Hb. These non-negative elements corresponding to the four 1s in the LDPC matrix H form themselves a "cycle of length 4" in the basic matrix Hb in the sense that they are in the same configuration as the 1s in Figure 4. The elements "i, j, k and l" of girths/cycles of length 4 "in the basic matrix" hence refer to any four non-negative elements in matrix Hb in this configuration. The condition formulated in paragraph [0056] requires that any such four non-negative elements i, j, k and l in matrix Hb satisfy mod (i-j+k-l, z) != 0 (meaning that the number i-j+k-l is not evenly divisible by z).

The conditions on cycles of length 6 can likewise be understood with the help of Figure 5.

3.6 An LDPC code is commonly classified as being either "regular", meaning that its LDPC matrix has both identical row weights and identical column weights, or "irregular". Paragraph [0006] of the present application mentions regular and irregular LDPC codes but also a further category of "semi-regular" codes, for which the row weights and column weights are identical only for the "information bits" of the LDPC matrix, i.e. for the left-hand side of an LDPC matrix having the shape shown in Figure 7:

FORMULA/TABLE/GRAPHIC

According to paragraph [0006], an irregular LDPC code has "totally different row weight and column weight of parity check matrix, and column weight of the information bits of the parity check matrix is also different". However, it is easy to verify that not all the row weights and column weights are "totally different" for the examples of irregular codes given in the application, for instance the irregular LDPC code corresponding to the basic matrix Hb of size 6×24 defined in original claim 13 (the (24-6)×z "information bits" columns having either weight three or weight six). The Board therefore understands an "irregular" LDPC code within the meaning of the application to be an LDPC code that is neither regular nor semi-regular.

4. Interpretation of claim 1

4.1 Independent claim 1 is directed to an LDPC encoder comprising an encoding-operation module, a basic-matrix-storage module and an extension module.

The basic-matrix-storage module holds a basic matrix Hb consisting of an information part of size M×(N-M) and a parity part of size M×M.

The extension module is configured to extend the basic matrix Hb to obtain an LDPC matrix of size (M×z) × (N×z) in the manner explained in point 3.1 above.

The encoding-operation module is configured to encode (N-M)×z bits of source data to obtain a codeword having N×z bits on the basis of the (M×z) × (N×z) LDPC matrix.

Claim 1 requires the LDPC code defined by the LDPC matrix to be irregular.

4.2 Claim 1 imposes a number of inequality conditions on the basic matrix Hb.

In particular, any four non-negative elements i, j, k, l of the basic matrix Hb forming a cycle with length four (in the sense discussed in point 3.5 above) must satisfy mod (i-j+k-l, z) != 0.

In addition, the matrix must satisfy one of conditions 1) and 2).

4.3 Condition 1) refers to a "each new basic matrix formed by deleting random r-1 columns" from the basic matrix Hb, where r is the number of columns with the largest weight in matrix Hb. In each such (hypothetically created) new basic matrix, non-negative elements i, j, k and l forming a cycle of length four must satisfy mod (i-j+k-l, z) != 0; and non-negative elements i, j, k, l, m and n forming a cycle of length six must satisfy mod (i-j+k-l+m-n, z) != 0.

4.4 Condition 2) is similar to condition 1) but considers "each new basic matrix" formed by deleting, from the basic matrix Hb, random r-1 columns and all columns with weight three.

5. Clarity

In its communication, the Board expressed doubts as to whether claim 1 of both the main request and the auxiliary request was clear, in particular in respect of the features referring to "elements i, j, k and l" and to "cycles" in the basic matrix Hb.

Although the appellant has amended the wording of claim 1 in this respect, it may be questioned whether the amended claim actually overcomes the Board's clarity objection. In fact, the appellant considered it necessary to submit post-published document D4 "for the Board to more clearly understand i, j, k, l of the short cycle".

The Board will leave this question open since it can decide the case on the basis of the inventive-step objection which was raised in the Board's communication against claim 1 of the previous main request and auxiliary request and which still applies to the amended claim 1.

6. Inventive step

6.1 Before considering the prior art, the Board notes that the condition discussed in point 4.2, second paragraph, above corresponds to the sufficient and necessary condition on the basic matrix Hb for the girth of the expanded LDPC matrix to be at least six (see points 3.3 to 3.5).

Moreover, since the columns of each "new basic matrix" considered in conditions 1) and 2) form a subset of the columns of the basic matrix Hb, each cycle of length four or six in each "new basic matrix" corresponds to a cycle of length four or six in the basic matrix Hb. This means that if the girth of the expanded LDPC matrix is at least eight, the non-negative integers i, j, k, l or i, j, k, l, m, n corresponding to a cycle of length four or six in each "new basic matrix" satisfy the inequality mod (i-j+k-l, z) != 0 or mod (i-j+k-l+m-n, z) != 0.

Hence, if the girth of the expanded LDPC matrix is at least eight, then the basic matrix Hb satisfies all the inequality conditions listed in claim 1.

6.2 Document D1, in section 8.4.9.2.5.1, discloses the construction of a parity-check matrix H by expansion of a model matrix Hbm. Each blank or negative value in the model matrix Hbm (values -1 in the sample model matrices on pages 4, 5 and 6) is replaced with the z×z zero matrix, and each non-negative value corresponds to a "circular shift size p(i,j)>=0" and is replaced with a circular right shift by the same amount of the z×z unit matrix. It is undisputed that this expansion method corresponds to the functionality of the "extension module" as disclosed in the present application (see point 3.1 above).

On page 2, fourth to sixth paragraphs, document D1 discloses that high-girth LDPC codes have good performance characteristics. The "Rate 1/2" model matrices Hbm disclosed on page 4 of document D1 are said to have girth eight for z < 80 and girth ten for z >= 80. They thus satisfy the inequality conditions on the "basic matrix" specified in claim 1.

6.3 Document D1, in section 8.4.9.2.5.2, discloses an encoder for encoding source data using the parity-check matrix obtained by expanding the model matrix Hbm. In the Board's view, this encoder comprises implicitly disclosed encoding-operation, basic-matrix-storage and extension modules as claimed.

6.4 As the appellant pointed out in its statement of grounds of appeal, the examples in document D1 relate to semi-regular LDPC codes. Indeed, each of the 12 leftmost columns of the "Rate 1/2" family of model matrices includes four non-negative elements, which means that the 12×z columns in the information part of the corresponding LDPC matrices all have weight four. These LDPC codes are therefore not irregular LDPC codes (see point 3.6 above).

6.5 Hence, the subject-matter of claim 1 of the main request differs from the encoder of document D1 only in that the LDPC code is irregular.

6.6 According to paragraph [0004] of the application, it was known at the priority date that irregular codes have performance advantages over regular codes. And document D1, in the paragraph bridging pages 2 and 3, states that the method for designing high-girth LDPC codes can be used to design both regular and irregular LDPC codes. It adds that "any matrix structure with given code rate, codeword length and degree distribution can be obtained by our method".

At the priority date of the invention, it was therefore obvious for the skilled person to consider applying the techniques of document D1 to irregular codes.

6.7 In its letter of 15 January 2019, the appellant argued that irregular codes were "completely different" from the codes disclosed in document D1 "due to different densities of non-zero elements". For irregular codes, it was "impossible to find the extension matrix H with girth of 8".

The Board cannot agree that it is impossible to find a basic matrix Hb for which the expanded LDPC matrix H has a girth of at least eight and which defines an irregular LDPC code. In fact, any of the "Rate 1/2" model matrices of document D1 can be made irregular by replacing a single non-negative element in the information part of Hbm with the element -1 (causing the weights of its "information bits" columns and rows to be different from the other weights), and such a modified model matrix continues to have a girth of at least eight (since such a modification removes edges from the Tanner graph and thus can only remove cycles and not introduce new cycles). Such basic matrices Hb therefore exist and thus can be found, if not by the aforementioned modification, then at least by a straightforward computer search.

The Board hence concludes that the skilled person, starting from document D1, would not only be motivated to look for a basic matrix Hb for which the expanded LDPC matrix is irregular but still has girth eight or higher, but would also succeed in finding one. He would thereby arrive at the subject-matter of claim 1 without the exercise of inventive skill.

6.8 The appellant submitted that "in our example, a column weight of r=3 columns reaches 12, which is much larger than the maximum column weight of the semi-regular code which is 4, so we can't design an irregular matrix with girth of 8, but can only design an overall matrix with a girth of 6". The appellant appears to be referring to the sample basic matrix of size 12×24 shown in paragraph [0077] of the A1 publication, which indeed includes three columns of weight 12.

Since claim 1 does not require the basic matrix Hb to have columns of a particular (largest) weight, the appellant's submission has no bearing on the Board's reasoning.

6.9 The appellant further argued that document D5 gave evidence of good coding performance achieved by the three sample basic matrices shown in paragraphs [0077], [0084] and [0098]. A high-girth structured LDPC code with optimal performance was first proposed in the present application. The design of the semi-regular LDPC code of document D1 was completely different from the design of the irregular code of the application.

However, claim 1 is not limited to any of the sample matrices of the present application. As explained in point 6.1 above, claim 1 encompasses all basic matrices for which the expanded LDPC matrix H is irregular and has a girth of at least eight. It was already known at the priority date that high girth and irregularity of the LDPC matrix were advantageous.

6.10 The appellant requested the Board to provide evidence that the features of claim 1 defining the various inequality conditions were common general knowledge.

The Board notes that, for the subject-matter of claim 1 to lack inventive step, it is sufficient that the skilled person would have arrived at something falling within the terms of the claim, i.e. at a basic matrix Hb that corresponds to an irregular LDPC code and that satisfies the inequality conditions specified in claim 1. Those inequality conditions are satisfied if the expanded LDPC code has a girth of at least eight. There is no need for the Board to show that the skilled person would have arrived at the wording of the claim, since that is not what Article 56 EPC is about.

6.11 Hence, the subject-matter of claim 1 lacks inventive step (Article 56 EPC).

7. Conclusion

Since the sole substantive request cannot be allowed, the appeal is to be dismissed.

Order

For these reasons it is decided that:

The appeal is dismissed.