T 0305/11 (Parallel decoding/SONY) 26-04-2016
Download und weitere Informationen:
Decoding method, decoding device, and program
Admissibility of appeal - appeal sufficiently substantiated (yes)
Amendments - all requests (not allowable)
Summary of Facts and Submissions
I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 04728245.4, filed in Japanese as international application PCT/JP2004/005551 and published in English as EP 1 521 372 A1.
II. The decision cited the following documents:
D1: Hocevar D.E.: "LDPC Code Construction with Flexible Hardware Implementation", 2003 IEEE International Conference on Communications, pp. 2708-2712, 11-15 May 2003;
D2: WO 02/103631 A, 27 December 2002; and
D3: Richardson T.J. et al.: "Efficient Encoding of Low-Density Parity-Check Codes", IEEE Transactions on Information Theory, Vol. 47, No. 2, pp. 638-656, February 2001.
With respect to the then main request, the Examining Division decided that independent claims 1, 3 and 18 did not meet the requirements of Article 84 EPC and that the subject-matter of claims 1 and 3 was not new and that of claim 18 not inventive in view of "any prior art disclosing LDPC decoding using check matrices, or more particularly, prior art D2".
With respect to the then first auxiliary request, the Examining Division decided that independent claims 1, 2 and 14 did not meet the requirements of Article 84 EPC and that their subject-matter lacked inventive step in view of a combination of documents D2 and D3.
III. With the statement of grounds of appeal, the appellant replaced its substantive requests with a new main request and a new first auxiliary request, both requests based on the claims of the previous main request with further amendments.
IV. The appellant was summoned to oral proceedings. In a communication under Article 15(1) RPBA, the Board questioned whether the statement of grounds of appeal was sufficiently reasoned and expressed the preliminary view that both the main request and the first auxiliary request infringed Articles 84 and 123(2) EPC and that the subject-matter of claim 1 of neither request involved an inventive step within the meaning of Articles 52(1) and 56 EPC.
V. With a letter dated 23 March 2016 and received one day earlier, the appellant replaced its substantive requests with amended main and first auxiliary requests and commented on the Board's communication.
VI. Oral proceedings were held on 26 April 2016. At the end of the oral proceedings, the chairman pronounced the Board's decision.
VII. 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 the first auxiliary request.
VIII. Claim 1 of the main request reads as follows:
"A decoding method of decoding received LDPC (Low Density Parity Check) codes having an information part of k bits and a parity part of m bits, where k/(k+m) is the coding rate, represented by an original check matrix of m rows and (k+m) columns, said decoding method comprising:
a decoding step of decoding said LDPC codes by using a transformation check matrix obtained by performing a row permutation and a column permutation on the original check matrix;
wherein, by using, as a formation matrix, a P x P unit matrix, a quasi-unit matrix in which one 1, which are [sic] elements of the unit matrix, is substituted with 0, a shift matrix in which said unit matrix or said quasi-unit matrix is cyclically shifted, a sum matrix, which is the sum of two or more of said unit matrix, said quasi-unit matrix, and said shift matrix, and a P x P 0-matrix, said transformation check matrix is represented by a combination of a plurality of said formation matrices,
wherein the parity part of the original check matrix has a staircase-like structure with ones filling the leading diagonal, and the diagonal immediately below,
wherein a single quasi-unit matrix exists in the parity part of the transformation check matrix used at the decoding step."
IX. Claim 1 of the first auxiliary request reads as follows:
"A decoding method of decoding received LDPC (Low Density Parity Check) codes having an information part of k bits and a parity part of m bits, where k/(k+m) is the coding rate, represented by an original check matrix of m rows and (k+m) columns, said decoding method comprising:
a decoding step of decoding said LDPC codes by using a transformation check matrix obtained by performing a row permutation and a column permutation on the original check matrix;
wherein, by using, as a formation matrix, a P x P unit matrix, a quasi-unit matrix in which one 1, which are [sic] elements of the unit matrix, is substituted with 0, a shift matrix in which said unit matrix or said quasi-unit matrix is cyclically shifted, a sum matrix, which is the sum of two or more of said unit matrix, said quasi-unit matrix, and said shift matrix, and a P x P 0-matrix, said transformation check matrix is represented by a combination of a plurality of said formation matrices,
wherein the row permutation permutes the [(m/P)x+y+1]th row to the [P.y+x+1]th row, and
wherein the column permutation permutes the [(m/P)s+t+(K+1)]th column to the [P.t + s + (K+1)]th column,
where x, y, s and t are integers in the range:
0<=x
0<=y
0<=s
0<=t
wherein the parity part of the original check matrix has a staircase-like structure with ones filling the leading diagonal, and the diagonal immediately below,
wherein a single quasi-unit matrix exists in the parity part of the transformation check matrix used at the decoding step."
X. The appellant's arguments relevant to this decision are discussed in detail below.
Reasons for the Decision
1. Admissibility of the appeal
1.1 Rule 99(2) EPC requires that the statement of grounds of appeal indicate the reasons for setting aside the decision impugned. If this requirement is not complied with before the expiry of the time period for filing the statement of grounds of appeal, the appeal is to be rejected as inadmissible (Rule 101(1) EPC). According to the established case law of the boards of appeal, for the statement of grounds of appeal to comply with Rule 99(2) EPC it should address in sufficient detail each of the grounds for the decision (see decisions T 1045/02 of 13 November 2003, reasons 4; T 1187/04 of 6 December 2006, reasons 1.1; T 395/12 of 23 November 2012, reasons 1.7; T 899/13 of 29 January 2014, reasons 2.1; T 1831/14 of 28 May 2015, reasons 1.1).
1.2 An appellant may address a ground for refusal either by giving arguments why the objection raised was incorrect or by amending its claims and explaining why the objection is no longer relevant. An amendment of the claims without accompanying explanations may exceptionally suffice only where it is evident that the amendment overcomes the objection (see decision T 395/12, reasons 1.5). The statement of grounds of appeal should direct the board of appeal towards the facts that need to be examined and not leave it to the board of appeal to look for the relevant details of the case of its own motion (see decision T 922/05 of 7 March 2007, reasons 14 and 16).
1.3 The decision under appeal contains the following objections against the main request:
- lack of clarity/support (points 2.3.1 and 2.3.2);
- lack of novelty (points 2.4.1 and 2.4.2); and
- lack of inventive step (point 2.4.3).
The decision contains the following objections against the then first auxiliary request:
- lack of clarity/support (point 3.2); and
- lack of inventive step (points 3.3.1 to 3.3.5).
In section 2.3.2.3, the decision explained that the application disclosed the specific original check matrix shown in Figure 15, corresponding specific mathematical row and column permutation rules (see paragraph [0084] of the published application) and the resulting transformation check matrix shown in Figures 16 and 17. The description was silent about construction rules or algebraic properties of the original check matrix, although the disclosed mathematical permutation rules had a regularity which implied the existence of a mathematical construction principle for the original check matrix. On the basis of the information given in the application, the skilled person would have been unable to extend the particular teaching of the specific example to the whole field of original LDPC check matrices to solve the technical problem posed.
1.4 With the statement of grounds of appeal, the appellant replaced its requests with a new main request and a new first auxiliary request, the claims of both requests being based on the claims of the previous main request with certain amendments added.
In particular, the following text was added at the end of claim 1 of the main request:
"wherein the parity part of the original check matrix has a staircase-like structure with ones filling the leading diagonal, and the diagonal immediately below,
whereby the decoding step results in a single quasi-unit matrix existing in the parity part of the transformation check matrix."
1.5 In the statement of grounds of appeal, the appellant observed with respect to the main request that "A principal reason for the refusal was that claim 1 is too broad having regard to the overall disclosure of the patent application". The appellant then discussed the objections raised under points 2.3.1 and 2.3.2 of the reasons for the decision and explained why it disagreed with them. Part of this discussion reads as follows:
"In Section 2.3.2.3 the refusal then goes on to argue that 'the person skilled in the art would be unable to extend the particular teaching of said example' - in other words no general inventive features are evident in the original check matrix of the original check matrix [sic] shown in Figure 15.
We disagree with this statement. The skilled person is able quite clearly to identify that the parity part of the original check matrix has a characteristic and unusual staircase-like structure with ones filling the leading diagonal, and the diagonal immediately below. It is this staircase-like structure of the parity part which results, after permutation, in a single quasi-unit matrix existing in the parity part of the transformation check matrix. This parity bit structure solves the technical problem of suppressing the operating frequency to a sufficiently realisable range."
With respect to the first auxiliary request, the appellant stated that it had incorporated "additional text to explicitly state the row and column permutations used to transform from the original check matrix (Fig. 15) to the transformation check matrix (Fig. 16/17)". The Examining Division had therefore been incorrect in concluding that a person skilled in the art would have been unable to extract relevant teaching from the specific example.
The statement of grounds of appeal does not explicitly refer to novelty or inventive step.
1.6 In its communication the Board questioned the admissibility of the appeal, noting that the statement of grounds of appeal appeared to deal only with the objection of lack of support.
In response, the appellant explained that the grounds of lack of novelty and inventive step on which the decision was based depended entirely on the Examining Division's broad interpretation of the claims and were therefore intrinsically linked to the ground of lack of support. The statement of grounds of appeal dealt with the ground of lack of support and thereby also with the grounds of lack of novelty and inventive step.
1.7 The Board acknowledges that an objection of lack of novelty or inventive step may sometimes be linked to an alleged lack of clarity or support. Thus, if the statement of grounds of appeal explains not only why a claim or claim feature had been given an unduly broad interpretation, but also why that had led to an incorrect finding of lack of novelty, then the objection of lack of novelty will have been sufficiently addressed. But in the present case the statement of grounds of appeal is silent on such a connection between lack of support and lack of novelty and inventive step; the Board could have become aware of it, if at all, only by performing its own investigations.
1.8 Nevertheless, the Board has come to the conclusion that the statement of grounds of appeal is sufficiently reasoned. Although the features added to claim 1 of the main request relating to the "staircase-like structure" of the "parity part" of the original check matrix are discussed only in the appellant's explanation of why it did not agree that the application as filed failed to disclose a generalisation of the example original check matrix shown in Figure 15, that explanation does include the statement that the "staircase-like structure" solves the technical problem of "suppressing the operating frequency to a sufficiently realisable range". Minimal as this may be, the Board accepts it as an argument why, in the appellant's view, the novelty and inventive-step objections raised in the contested decision no longer applied to the amended main request.
1.9 Since the appeal also complies with the other provisions referred to in Rule 101 EPC, it is admissible.
2. The invention
The application relates to decoding of low-density parity-check (LDPC) codes. Under the heading "Background Art" it discusses several known decoding methods and points out their disadvantages. The object of the invention is presented as "to suppress the operating frequency [of an LDPC decoder] to a sufficiently realizable range while suppressing the circuit scale for both logic and memory, and to be capable of easily controlling memory access" (see paragraph [0077] of the A1 publication).
The solution as presented in the application starts from the "original" parity-check matrix defining the LDPC code used by the encoder. An example original check matrix is the 30-by-90 matrix shown in Figure 15 (a dot representing a 0):
FORMULA/TABLE/GRAPHIC
The original check matrix is then transformed by means of permutations of both its rows and its columns into a "transformation check matrix" suitable for parallel decoding. The permutations applied to the original check matrix of Figure 15 are specified in paragraphs [0084] and [0085] of the published application. For integers x, y, s and t satisfying 0 <= x < 5, 0 <= y < 6, 0 <= s < 5 and 0 <= y < 6, row 6x+y+1 is moved to row 5y+x+1 and column 6s+t+61 is moved to column 5t+s+61. The resulting example transformation check matrix is shown in Figure 16:FORMULA/TABLE/GRAPHIC
This example transformation check matrix has the property that it is built up from 5-by-5 matrices of a restricted structure. Most of these matrices which are not all-zero matrices are unit matrices (with 1s on the diagonal) or "shifted" unit matrices (with the diagonal cyclically shifted by a number of positions). Some are the superimposed sum of two such matrices. The 5-by-5 matrix in the top-right corner is different in that it is a shifted unit matrix with one 1 missing (a shifted "quasi-unit" matrix).
As explained in paragraph [0046], a serially operating prior-art decoder requires 269 x 2 = 538 clock cycles to perform one iteration of the well-known message passing algorithm for decoding LDPC codes when using a check matrix having 269 1s such as those shown in Figures 15 and 16. According to paragraph [0135] of the detailed description, using the example transformation matrix of Figure 16 the parallel decoder disclosed in the application processes one (shifted) diagonal at a time and therefore requires only 269/5 x 2 APPROX 108 clock cycles.
3. Main request - added subject-matter
3.1 Original claim 2 attempts to define the general structure of the transformation check matrix by means of the term "formation matrix", which is defined as "a P x P unit matrix, a quasi-unit matrix in which one or more 1s, which are elements of the unit matrix, are substituted with 0, a shift matrix in which said unit matrix or said quasi-unit matrix is cyclically shifted, a sum matrix, which is the sum of two or more of said unit matrix, said quasi-unit matrix, and said shift matrix, and a P x P 0-matrix". The same definition is given in paragraphs [0093] to [0095] of the detailed description. According to original claim 2, the transformation check matrix is "represented by a combination of a plurality of said formation matrices", meaning that the transformation check matrix is composed of P-by-P blocks, each block being a formation matrix. As the Examining Division pointed out in the course of the first-instance proceedings, the definition of formation matrix is too broad as, upon close inspection, it covers any (binary) P-by-P matrix.
3.2 Claim 1 of the main request refused by the Examining Division attempted to give a narrower definition of the transformation check matrix by modifying the definition of "formation matrix". Claim 1 of the present main request now further includes restrictions on both the original check matrix and the transformation check matrix based on the example matrices of Figures 15 and 16. In particular, the "parity part" of the original check matrix is to have a "staircase-like structure with ones filling the leading diagonal, and the diagonal immediately below" and the "parity part" of the transformation check matrix is to include "a single quasi-unit matrix".
The modification of the definition of the "formation matrix" (the redefinition of quasi-unit matrix as a matrix "in which one 1, which are [sic] elements of the unit matrix, is substituted with 0") raises issues under both Article 84 EPC and Article 123(2) EPC, but the Board will not pursue them here.
3.3 As the statement of grounds of appeal makes clear, the feature specifying that the parity part of the original check matrix has a staircase-like structure is based on the example original check matrix shown in Figure 15. The appellant has not indicated any other basis in the application as filed and the Board is not aware of any either.
Figure 15 indeed discloses a "staircase-like structure" as claimed: the 30 rightmost columns form a 30-by-30 matrix with 1s only on the main diagonal and on the diagonal immediately below.
The feature specifying that the parity part of the transformation check matrix includes a quasi-unit matrix can only be based on the 5-by-5 matrix in the top-right corner of the example transformation check matrix of Figure 16. This 5-by-5 matrix is a quasi-unit matrix, albeit a shifted one.
The application as filed does not refer to the 30 rightmost columns as the "parity part" of the example check matrices or at any other point mention this term. For the purpose of interpreting claim 1, the Board reads this term as simply referring to the rightmost m columns of an m-by-n parity-check matrix.
3.4 Although the features added to claim 1 are thus indeed shown by Figures 15 and 16, it is also apparent that the two matrices disclosed by these figures exhibit many more features. For example, the "quasi-unit matrix" in the parity part of the transformation check matrix is located in the top-right corner and is a shifted quasi-unit matrix, and the parity part also includes a main diagonal of 1s and a subdiagonal of 1s. In addition, the leftmost 60 columns of the transformation check matrix show a structure going beyond that of being composed of 5-by-5 "formation matrices"; in particular, both the leftmost 30 columns and the middle 30 columns of the transformation check matrix exhibit main diagonals filled with 1s. It may further be mentioned that the two example matrices have specific numbers of rows and columns with a specific ratio. Moreover, the two matrices are connected by the specific permutations specified in paragraphs [0084] and [0085].
The features added to claim 1 have thus been isolated from the combination of features in which they were originally disclosed. This is not permissible under Article 123(2) EPC unless the skilled person reading the application as a whole and using his common general knowledge would recognise without any doubt that the extracted features are not merely incidental features of the example embodiment, but were deliberately included to serve a particular purpose which they continue to serve in the more general context of the claim and are not otherwise inextricably linked with further features of the combination.
3.5 The appellant argued that, regardless of the other features of the transformation check matrix, it was the inclusion of a single quasi-unit matrix in the parity part of the transformation check matrix that allowed the operating frequency of the LDPC decoder of the invention "to be suppressed to a realisable range". Furthermore, it was the staircase-like structure of the parity part of the original check matrix that resulted, after permutation, in that single quasi-unit matrix. The appellant referred to paragraphs [0133] to [0137] of the published application and in particular to paragraphs [0135] to [0137].
The passage cited by the appellant does not, however, support its argument. It explains that the P-by-P block structure of the transformation check matrix allows the parallel decoding architecture disclosed in the detailed description to perform P operations in parallel, and it makes no particular mention of a single quasi-unit matrix in the "parity part" of the transformation check matrix. The argument therefore cannot succeed.
3.6 The application as filed merely presents the matrices in Figures 15 and 16 as example original and transformation low-density parity-check matrices and specifies, without further explanation, row and column permutations that transform one into the other. The skilled reader of the application learns that the 5-by-5 block structure of the transformation check matrix is important for the application's parallel decoding architecture, but obtains no information about which other properties of the two matrices were included for a technical reason as opposed to being merely incidental. The Board also sees no reason why the skilled person studying the example matrices would focus on a property such as the shifted quasi-unit matrix in the top-right corner of the transformation check matrix of Figure 16.
3.7 Although the "staircase-like structure" of the parity part of the original check matrix of Figure 15 undeniably "sticks out", the Board does not consider that visual aspect alone to be sufficient for the skilled reader of the application to recognise without doubt that the feature was intended for generalisation in the context of the present application. The application as filed does not use the term "staircase-like structure" and makes no reference to the diagonal structure of the 30 rightmost columns of the original check matrix. The application in fact never singles out those columns. Only the features in claim 1 that were added to the originally filed claims introduce the term "parity part" to refer to a portion of the original and transformation check matrices, and make reference to the "staircase-like structure".
3.8 The Board concludes that no justification exists for isolating the features added to claim 1 from the combination of features in which they were originally disclosed. It follows that the main request cannot be allowed because the subject-matter of claim 1 extends beyond the content of the application as filed (Article 123(2) EPC).
4. First auxiliary request - added subject-matter
4.1 Claim 1 of the first auxiliary request adds to claim 1 of the main request features amounting to a generalisation of the row and column permutations disclosed in paragraphs [0084] and [0085] of the published application. Instead of being applicable to a 30-by-90 matrix having a 30-by-30 parity part in the 30 rightmost columns and being adapted to a 5-by-5 block structure, the generalised permutations are applicable to an m-by-(k+m) matrix having an m-by-m parity part in the rightmost m columns and are adapted to a P-by-P block structure.
4.2 The inclusion in claim 1 of generalised row and column permutations is an improvement in the sense that those permutations in combination with the claimed staircase-like structure of the parity part of the original check matrix determine the structure of the parity part of the transformation check matrix, including the quasi-unit matrix in the top-right corner.
However, the problem remains that the application as filed does not disclose the staircase-like structure of the 30 rightmost columns of the original check matrix of Figure 15 as being more generally applicable. It therefore cannot be isolated from the context in which it was originally disclosed without infringing Article 123(2) EPC (see points 3.43.4 to 3.73.7 above).
4.3 It follows that the first auxiliary request, too, is not allowable.
5. Conclusion
Since neither 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.