T 2232/15 (LDPC encoding and decoding II/LG ELECTRONICS) of 12.12.2017

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 10179172.1.

II. The application was filed as a divisional application of European patent application No. 05756780.2 and claimed the priority of 13 earlier applications, the three earliest being the following Korean patent applications:

P1: |No. 10-2004-0047898, filed on 24 June 2004; |

P2: |No. 10-2004-0048454, filed on 25 June 2004; and|

P3: |No. 10-2004-0085512, filed on 25 October 2004. |

III. The decision was issued as a so-called decision on the state of the file, making reference to an earlier communication of the Examining Division for the reasons for the refusal. That earlier communication had referred to the following documents:

D1: |Classon B. et al.: "LDPC coding for OFDMA PHY", IEEE C802.16e-04/278r1, IEEE 802.16 Broadband Wireless Access Working Group, 17 August 2004, retrieved from http://www.ieee802.org/16/tge/contrib/C80216e-04_278r1.pdf;|

D2: |Classon B. et al.: "LDPC coding for OFDMA PHY", IEEE C802.16e-04/374, IEEE 802.16 Broadband Wireless Access Working Group, 24 August 2004, retrieved from http://www.ieee802.org/16/tge/contrib/C80216e-04_374.pdf; |

D3: |Even G. et al.: "A dual precision IEEE floating-point multiplier", Integration, the VLSI Journal, Vol. 29, No. 2, September 2000, pp. 167-180; and |

D4: |"Teaching Rounding Rules", The Math Forum@Drexel, 27 August 2003, retrieved from http://mathforum.org/library/drmath/view/63989.html. |

The Examining Division considered 25 October 2004 to be the effective filing date for the subject-matter claimed and decided that the subject-matter of claims 1 to 8 of the sole substantive request lacked inventive step in view of document D1 and common general knowledge as exemplified by documents D3 and D4, noting that the same objections could be based on the disclosure of document D2.

IV. In its statement of grounds of appeal, the appellant maintained the sole substantive request considered in the decision under appeal as its main request and filed amended sets of claims as first and second auxiliary requests. The appellant also submitted the following post-published documents:

D7: |"Modulo operation", Wikipedia, 12 October 2015, retrieved from https://en.wikipedia.org/wiki/Modulo_operation; and |

D8: |"What is the most efficient way to round a float value to the nearest integer in java?", Stack Overflow, 12 October 2015, retrieved from http://stackoverflow.com/questions/12091014/what-is-the-most-efficient-way-to-round-a-float-value-to-the-nearest-integer-in.|

V. In a communication accompanying a summons to oral proceedings, the Board inter alia expressed the preliminary view that the subject-matter of the independent claims of each request lacked inventive step.

VI. In a letter not containing any comments on the substance of the Board's communication, the appellant informed the Board that it would not be attending the oral proceedings.

VII. The Board cancelled the oral proceedings.

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 or, in the alternative, on the basis of the claims of one of the first and second auxiliary requests.

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

"A method of encoding data using low density parity check (LDPC) code, the method comprising:

generating (S41) a second base matrix by replacing each first value corresponding to each element of a first base matrix with a second value corresponding to each element of the second base matrix, wherein each first value of the first base matrix is an integer which indicates either a zero matrix or a first permutation matrix having a zmax×zmax size, and wherein each second value of the second base matrix is an integer which indicates either a zero matrix or a second permutation matrix having a z×z size;

generating (S43) a parity check matrix by replacing each second value of the second base matrix with a corresponding second permutation matrix or the zero matrix having a z×z size; and

encoding (S45) input data using the generated parity check matrix,

characterized in that each second value is determined in accordance with the following equation:

shift(z) = floor(shift(zmax)z / zmax), where 'shift(zmax)' is the first value, 'shift(z)' is the second value, and 'floor(x)' denotes a nearest integer from x toward negative infinity, wherein zmax is greater than z."

X. Claim 1 of the first auxiliary request differs from claim 1 of the main request in that "and zmax is greater than '0'" has been added at the end of the claim.

XI. Claim 1 of the second auxiliary request differs from claim 1 of the first auxiliary request in that the following text has been added at the end of the claim:

"wherein the second value corresponding to each element of the second base matrix is either a non-negative integer or '-1' and expanding the second base matrix comprises:

replacing the second value of '-1' with the zero matrix;

replacing the second value of the positive integer with a second permutation matrix altered according to the positive integer; and

replacing the second value of a zero with a second permutation matrix which is an identity matrix;

wherein the second permutation matrix indicated by a positive integer is altered by circular shifting one of each entire row and each entire column of the identity matrix a number of intervals equal to the positive integer."

XII. The appellant's arguments as relevant to this decision are discussed in detail below.

Reasons for the Decision

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 large 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 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 smaller than zmax, a "second base matrix" is obtained by replacing each shift value shift(zmax) in the first base matrix with the value shift(z) where shift(z) = floor(shift(zmax)z / zmax). Here, floor(x) denotes "a nearest integer from x toward negative infinity", i.e. the value of x is rounded down to obtain an integer value. The second base matrix is then expanded to a parity-check matrix by applying the first idea.

4. 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 each request is therefore 25 October 2004. The appellant has not disputed this.

5. Public availability of documents D1 and D2

According to their cover pages, documents D1 and D2 were submitted to the IEEE 802.16 Broadband Wireless Access Working Group on 17 and 24 August 2004 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 the contributions directory of the working group (http://www.ieee802.org/16/tge/contrib/). The Board has no reason to doubt that both documents were made available on this website before 25 October 2004. The appellant has not argued otherwise.

Hence, the Board concludes that documents D1 and D2 are prior art under Article 54(2) EPC for the subject-matter of claim 1 of all requests.

6. Main request - inventive step

6.1 As acknowledged by the appellant, documents D1 and D2 have very similar content and either may serve as a starting point for assessing inventive step. The Board prefers to start with document D2.

6.2 Document D2 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 the 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).

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

6.4 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 give rise to 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. The application says nothing about such an effect.

6.5 The appellant argued that "Using a truncation-function, such as the floor-function, to scale the base matrices allows an easier grouping-step with enormously reduced computing effort" because "The floor-function discards any decimal value without any additional parameter-setting". According to the appellant, rounding to the nearest integer always involves "rounding-parameters that indicate the precision" and "a comparing-function for deciding whether [a] real number is nearest to the higher value or the lower value".

However, rounding to the nearest integer does not involve any setting of precision parameters; it simply means that 3.45 becomes 3 and that 3.63 becomes 4. A comparison function is not required either, as rounding to the nearest integer can be implemented, for example, by adding 0.5 and rounding down.

6.6 As to the alleged reduction in computational effort, the Board notes first that the claim's equation for shift(z) defines the result rather than the precise way in which the value is calculated. Whether calculating "floor(shift(zmax)z / zmax)" is computationally more efficient than calculating "[shift(zmax)z / zmax]" will depend on the precise implementation of the calculations and on low-level details of the hardware. Neither the claims nor the description give such details. The Board therefore does not accept that the claimed rounding method is more efficient than the rounding method of document D2.

6.7 The appellant referred to document D8 in support of its argument that rounding to the nearest integer used more computational resources than rounding down. But document D8 in fact compares two different implementations, in Java SE6, of rounding to the nearest integer and thus does not support the argument.

6.8 The appellant also argued that always rounding down reduced "the number of shifts".

The application contains no indication, however, that lower shift values are somehow more efficient. Nor is the Board convinced that, in a realistic implementation of the invention, lower shift values would lead to faster or more efficient processing; a circular permutation with variable shift size is typically implemented by means of a barrel shifter and performed in constant time.

6.9 Referring to Figure 13 of the application, the appellant argued that the floor function reduced the bit-error rate as compared with a modulo-function approach that is also discussed in the application (as an alternative method of mapping shift values for a permutation matrix of size zmax×zmax to shift values for a permutation matrix of size z×z; see paragraphs [00104] and [00105]). But document D2 - the prior art being considered here - is not based on this modulo-function approach. The appellant has not suggested, nor is there anything in the application to suggest, that the bit-error rate is reduced by rounding scaled shift sizes down instead of to the nearest integer.

Likewise, the appellant's argument that the claimed invention achieves an "enormous simplification" compared with the modulo-function approach is unable to support the argument that the claimed invention involves an inventive step over the disclosure of document D2.

6.10 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 D2 (Articles 52(1) and 56 EPC).

7. Auxiliary requests - inventive step

7.1 Since the permutation matrices of the invention are of size zmax×zmax, the value zmax is necessarily a positive integer. Thus the feature "zmax is greater than '0'" included in claim 1 of auxiliary request 1 adds no further limitation.

7.2 The features added to claim 1 of auxiliary request 2 clarify that generating the parity-check matrix by replacing the entries of the second base matrix with z×z matrices involves replacing the value -1 with the zero matrix, the value 0 with the identity matrix and a positive integer with a permutation matrix obtained by circularly shifting either the rows or the columns of the identity matrix by a number of positions equal to the integer's value.

In the method of document D2, the value -1 in the first base model matrix corresponds to the zero matrix and a shift size p(i,j)>=0 to a permutation matrix obtained by circularly shifting the identity matrix to the right by p(i,j) positions (page 4, fifth paragraph). The second base matrix likewise contains values -1 and (scaled) shift sizes p(f,i,j)>=0 (page 5, "Model Matrix Set" section).

The features added to claim 1 of auxiliary request 2 therefore do not further distinguish the subject-matter claimed from the disclosure of document D2.

7.3 Hence, the subject-matter of claim 1 of each of auxiliary requests 1 and 2 also lacks inventive step over document D2 (Articles 52(1) and 56 EPC).

8. Conclusion

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

Order

For these reasons it is decided that:

The appeal is dismissed.