T 2118/13 (LDPC code decoding/SATURN LICENSING) of 21.3.2018

Summary of Facts and Submissions

I. The applicant (appellant), which at the time was Sony Corporation, appealed against the decision of the Examining Division refusing European patent application No. 06745481.9. The application has an earliest priority date of 25 April 2005.

II. With effect from 7 June 2017, the EPO registered a transfer of the application to Saturn Licensing LLC, which thereby acquired the status of appellant.

III. The decision cited the following documents:

D1: |EP 1 494 358 A, published on 5 January 2005; |

D2: |EP 1 521 372 A, published on 6 April 2005; and |

D3: |D. Hocevar: "LDPC Code Construction with Flexible Hardware Implementation", Proceedings of the 2003 IEEE International Conference on Communications, 11-15 May 2003.|

The Examining Division refused the then main request because the subject-matter of claims 1 and 7 lacked novelty over any of documents D1, D2 and D3, the subject-matter of claim 5 contravened Article 123(2) EPC, and claims 4 to 6 were not clear within the meaning of Article 84 EPC. It refused the first auxiliary request because the subject-matter of claims 1 and 4 lacked novelty over any of documents D1, D2 and D3.

IV. With its statement of grounds of appeal, the appellant filed an amended main request and an amended first auxiliary request.

V. In a communication accompanying a summons to oral proceedings, the Board introduced the following document:

D6: |EP 1 624 581 A1, published on 8 February 2006.|

It expressed the preliminary opinion that the subject-matter of claim 1 of the amended main request was new over documents D1, D2 and D3 but lacked inventive step over the content of document D6, published in Japanese as WO 2004/102881 on 25 November 2004. The subject-matter of claim 1 of the first auxiliary request also appeared to lack inventive step.

VI. By letter of 9 February 2018, the appellant informed the Board that it would not attend the oral proceedings and requested that the oral proceedings be cancelled. It did not comment on the Board's communication.

VII. Oral proceedings were held on 21 March 2018 in the appellant's absence. At the end of the oral proceedings, the chairman pronounced the Board's decision.

VIII. The appellant requested that the decision 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 the first auxiliary request.

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

"A decoding apparatus (1000) for LDPC (Low Density Parity Check) codes definable by a parity check matrix including a combination of at least one component matrix which is one of

a P X P unit matrix,

a semi unit matrix obtained by setting one or more of matrix elements each having a value of 1 in said unit matrix to 0,

a shift matrix obtained by carrying out a cyclic shift operation on said unit matrix or said semi unit matrix,

a sum matrix obtained by computing the sum of a plurality of said unit matrixes, said semi unit matrixes or said shift matrixes, or

a P X P 0 matrix,

said decoding apparatus (1000) comprising:

a first computation section (1102) configured to carry out a check-node computation process in order to decode said LDPC codes;

a second computation (415) section configured to carry out a variable-node computation process in order to decode said LDPC codes;

wherein said first computation section (1102) is operable to carry out a maximum of N, where N is a positive integer smaller than said P, said check-node computation processes in parallel, and said second computation section (415) is operable to carry out N said variable-node computation processes in parallel; and

a first storage section (1103) configured to store first computation results produced by said first computation section; and

a second storage section (1104) configured to store second computation results produced by said second computation section;

wherein

said first storage section (1103) includes a plurality of memories (1202-1205) operable to allow N said first computation results to be stored in one of the plurality of memories of (basis: p. 145 l. 5-9) [sic] said first storage section and to allow, at the same time, N previously computed first computation results stored in another one of the plurality of memories of said first storage section to be read out, and

said second storage section (1104) includes a plurality of memories operable to allow N said second computation results to be stored in said second storage section at the same time and to be read out."

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

"and wherein

said N first computation results respectively correspond to N matrix elements set at 1 in N upper or lower rows of the at least one component matrix."

XI. 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. As the Board considered it expedient to come to a final decision in this case at the oral proceedings that had already been scheduled, it did not accede to the appellant's request for cancellation of the oral proceedings (Article 116(1) EPC).

3. Background of the invention

3.1 The application relates to the decoding of low-density parity-check (LDPC) codes. An LDPC code is defined by its sparse (low-density) parity-check matrix, which is a binary matrix with relatively few 1s and many 0s. An LDPC matrix is often represented as a bipartite "Tanner" graph, with "variable nodes" corresponding to the columns of the matrix, "check nodes" corresponding to its rows, and edges between variable nodes and check nodes corresponding to the 1s of the matrix.

3.2 The usual process of decoding a received LDPC codeword involves a number of iterations of the "sum product" algorithm (also known as the "belief propagation" or "message passing" algorithm). Each iteration of this algorithm consists of two steps. In one step, a "sum" is computed for each check node. In the other step, a "product" is computed for each variable node.

3.3 The "Background Art" section of the application contains an extensive discussion of known techniques for performing the various "sum" and "product" computations in parallel. Typically, the LDPC matrix is required to be composed of P×P submatrices ("component matrices" in the application), with further restrictions being imposed on the submatrices. This structure then allows the decoder to perform P check-node (or "sum") computations in parallel and also P variable-node (or "product") computations in parallel, by means of as many computation units.

3.4 Since the size of such a parallel-decoding circuit increases with the value of P, the application proposes a variation whereby an LDPC code defined by an LDPC matrix with a P×P-submatrix structure is decoded by performing N check-node or variable-node computations in parallel by means of N computation units, where N is an integer smaller than P.

Main request

4. The invention as defined by claim 1

4.1 Claim 1 defines a decoding apparatus for LDPC codes defined by "a parity check matrix including a combination of at least one component matrix", where the component matrix is one of:

- the P×P unit matrix;

- a semi-unit matrix obtained from the P×P unit matrix by replacing one or more 1s with 0s;

- a shift matrix obtained by cyclically shifting the unit matrix or a semi-unit matrix;

- a sum matrix obtained by computing the sum of a plurality of unit, semi-unit or shift matrices; and

- the P×P zero matrix.

Although the sample parity-check matrices shown in the application's figures are composed entirely of such component matrices, claim 1 requires the parity-check matrix only to include (at least) one component matrix.

4.2 The apparatus comprises first and second computation sections configured to carry out check-node computations and variable-node computations, respectively. Both computation sections are operable to carry out N computations in parallel, where N is a positive integer smaller than P. The Board notes that the claim wording "a maximum of N" is intended to rule out the interpretation that "N computations" means "at least N computations" (which would have rendered meaningless the restriction that N is smaller than P).

4.3 The computation results produced by the first and second computation sections are stored in respective first and second storage sections.

The first storage section includes a plurality of memories operable "to allow N said first computation results to be stored in one of the plurality of memories of said first storage section and to allow, at the same time, N previously computed first computation results stored in another one of the plurality of memories of said first storage section to be read out".

The second storage section includes a plurality of memories operable "to allow N said second computation results to be stored in said second storage section at the same time and to be read out".

4.4 Hence, the first storage section allows write and read operations to be carried out simultaneously. The second storage section, however, allows N computation results to be written simultaneously and N computation results to be read out simultaneously, but it need not allow those write and read operations to be carried out at the same time.

The Board observes that this difference in the definitions of the first and second storage sections finds support in the application as filed. Indeed, paragraphs [0268], [0269] and [0271] of the published application explain, with reference to Figures 23 and 24, that control signal D11081 in combination with switch 1201 selects, from the four RAMs 1202 to 1205 of the first storage section 1103, the RAM to which intermediate results are written, while at the same time control signal D11086 in combination with switch 1206 selects the other RAM of the first storage section 1103 from which intermediate results are read out. No such control signals and switches in connection with the second storage section 1104 are shown in Figure 23 or mentioned in its description (see in particular paragraphs [0239] to [0243]).

5. The objections raised in the decision under appeal

5.1 Since the main request no longer includes claims 4 to 6 of the main request considered in the decision under appeal, the Examining Division's objections under Articles 84 and 123(2) EPC have been overcome.

5.2 As set out in its communication, the Board agrees with the appellant that claim 1 of the main request as amended on appeal is new over documents D1, D2 and D3. In particular, none of these documents discloses a first storage section that allows write and read operations to be carried out simultaneously.

6. Inventive step - Article 56 EPC

6.1 Document D6 is the published English translation of application WO 2004/102811, which was published on 25 November 2004. The content of document D6 is therefore part of the prior art under Article 54(2) EPC for the present application. The document is a family member of Japanese patent application No. 2004-364233, which is one of the documents cited in the "Background Art" section of the present application (see paragraph [0220]). The Board considers the LDPC decoding apparatus depicted in Figure 18 of document D6 to be a suitable starting point for assessing inventive step.

6.2 The decoding apparatus of Figure 18 is operable to decode an LDPC code defined by the parity-check matrix of Figure 15 (paragraph [0221]). This parity-check matrix is composed of P×P submatrices, where each submatrix is either the P×P unit matrix, a P×P semi-unit ("quasi-unit") matrix, a cyclically shifted P×P unit or semi-unit matrix, a sum of two or more such matrices, or the P×P zero matrix (paragraphs [0155] and [0156]); the description uses P=5 for simplicity (paragraph [0451]).

6.3 The apparatus includes calculation sections 412 and 415, each section consisting of five calculators (paragraph [0223]). The calculators of section 412 perform check-node computations (paragraphs [0232] and [0026]; equation (7)). The calculators of section 415 perform variable-node computations (paragraphs [0232], [0017] and [0018]; equation (5)).

6.4 The apparatus further includes a memory 413 for storing check-node computation results and a memory 410 for storing variable-node computation results (Figure 18 and paragraph [0238]).

The memory 413 is formed by two single-port RAMs 502 and 503 and switches 501 and 502. It is capable of storing five computation results and, at the same time, allowing five previously computed computation results to be read out (Figures 23 and 24; paragraphs [0249], [0250], [0292], [0293] and [0305] to [0317]).

The memory 410 is formed by "a single-port RAM capable of simultaneously reading and writing five decoding in-progress results" (paragraph [0245]). The Board understands this as meaning that memory 410 allows five computation results to be stored in parallel and five computation results to be read out in parallel, but that it is not required that both operations can be carried out simultaneously. Indeed, the memory may consist of a single single-port RAM, and a selection mechanism as provided by switches 501 and 504 in memory 413 is not disclosed for memory 410.

6.5 Although document D6 does not disclose that the calculation sections 412 and 415 carry out fewer than P=5 computations in parallel, the Board observes that the matrix shown in Figure 15 includes at least one 10×10 unit matrix, namely in rows 1 to 10 and columns 31 to 40. This matrix hence satisfies the conditions of claim 1 for P=10 (see point 4.1 above). The decoding apparatus of Figure 18 thus carries out N=5 computation processes in parallel, where N=5 is an integer smaller than P=10.

6.6 For the sake of completeness, the Board notes that even if claim 1 were to be interpreted as requiring that the LDPC matrix is composed entirely of P×P "component matrices", this would not represent a further difference from the disclosure of document D6. It can be verified without much effort that the 30×90 parity-check matrix of Figure 15 of document D6 can in fact be represented as a combination of such 10×10 matrices. For example, the 10×10 matrix in rows 1 to 10 and columns 1 to 10 corresponds to a "sum matrix" formed by adding the following four shifted semi-unit matrices to the 10×10 unit matrix:

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . 1 . . . . . . . . . . . . .

. . . . . . . 1 . . . . . . . . . . . .

. . . . . . . . 1 . . . . . . . . . . .

. . . . . . . . . 1 1 . . . . . . . . .

1 . . . . . . . . . . 1 . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. 1 . . . . . . . . . . 1 . . . . . . .

. . 1 . . . . . . . . . . 1 . . . . . .

. . . 1 . . . . . . . . . . 1 . . . . .

. . . . 1 . . . . . . . . . . . . . . .

. . . . . 1 . . . . . . . . . . . . . .

6.7 The subject-matter of claim 1 therefore differs from the decoding apparatus of Figure 18 only in that the "second storage section" for storing variable-node computation results includes "a plurality of memories". But it is well known that a memory may be constructed from a number of RAM memories which may, for example, act as a single memory. This is also disclosed by document D1, which explains, in paragraph [0049], that, for cost reasons, it is advantageous to form one functional RAM memory by "lumping" together as much RAM as possible. This distinguishing feature is therefore an obvious constructional detail that cannot render the claimed apparatus inventive.

6.8 In the "Inventive Step" section of the statement of grounds of appeal, the appellant relies on paragraph [0283] of the present application, which states that the computation section 1102 "is capable of carrying out a first computation process continuously", and on paragraph [0306], which essentially states that the invention allows a reduction in the number of parallel units without an inversely proportional increase in the required operating frequency.

These alleged advantages do not relate to the sole distinguishing feature, which means either that they are already achieved by the features known in combination from document D6 or that claim 1 does not include all the features necessary for achieving them over the whole scope of the claim. They therefore do not represent technical effects that could support an inventive step over document D6.

6.9 The Board is aware that the present application discloses, as a concept, that it may be advantageous to use an LDPC decoder having N < P parallel computation units to decode an LDPC code that can be efficiently decoded by LDPC decoders having P parallel computation units. This concept is admittedly not present in document D6, but neither is it adequately captured by the wording of claim 1. Again for the sake of completeness, the Board notes that the concept is known from document D1, which, in paragraphs [0070] to [0074], discloses a family of matrices designed for efficient "n parallel decoding" (by being composed of circulant n×n matrices) that also allow efficient "m parallel decoding" if m is an integer fraction of n (and thus smaller than n).

6.10 In conclusion, the subject-matter of claim 1 lacks inventive step over the decoding apparatus of document D6 (Article 56 EPC).

First auxiliary request

7. Inventive step - Article 56 EPC

7.1 Claim 1 of the first auxiliary request adds to claim 1 of the main request that "said N first computation results respectively correspond to N matrix elements set at 1 in N upper or lower rows of the at least one component matrix".

7.2 Since both the N=5 upper rows and the N=5 lower rows of the P×P=10×10 unit matrix of Figure 15 of document D6 identified in point 6.5 above correspond to two 5×5 submatrices, the "N first computation results" produced in parallel by the decoding apparatus of document D6 corresponds to "N matrix elements set at 1 in N upper or lower rows of the at least one component matrix". The added feature therefore does not further distinguish the claimed subject-matter from what is disclosed in document D6.

7.3 The subject-matter of claim 1 therefore lacks inventive step (Article 56 EPC).

8. Conclusion

Since neither of the requests is allowable, the appeal is to be dismissed.

Order

For these reasons it is decided that:

The appeal is dismissed.