T 1173/15 (LDPC encoding/SATURN LICENSING) of 12.2.2020

Summary of Facts and Submissions

I. The then applicant (Sony Corporation) appealed against the decision of the Examining Division refusing European patent application No. 06745483.5 which was published, in accordance with Article 153(4) EPC, as EP 1 876 717 A1.

II. The decision cited the following documents:

D1: WO 2004/019268 A1, published on 4 March 2004;

D2: "The pi-rotation low-density parity-check codes", Echard R. et al., IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE, GLOBECOM 2001, SAN ANTONIO, TX, 25 November 2001, pages 980-984.

The Examining Division decided that:

- the subject-matter of claims 1 to 17 of the main request was not inventive in the sense of Article 56 EPC over document D1, the subject-matter of dependent claim 5 of the main request contravened Article 123(2) EPC, and claims 3, 4, 7, 9 and 12 of the main request were not clear in the sense of Article 84 EPC;

- the subject-matter of claims 1 and 16 of the first auxiliary request was not inventive in the sense of Article 56 EPC over document D1 and contravened Article 123(2) EPC;

- the subject-matter of claims 1 and 16 of the second auxiliary request was not inventive in the sense of Article 56 EPC over document D1 and contravened Article 123(2) EPC.

III. With the statement of grounds of appeal, the appellant filed amended main and first to third auxiliary requests, and requested that a European patent be granted on the basis of one of these requests.

IV. A registration of a transfer of the application to "Saturn Licensing LLC", which thereby acquired the status of appellant, took effect on 7 June 2017.

V. In a communication accompanying the summons to oral proceedings, the Board expressed, among others, the preliminary opinion that claim 1 of the main request was not clear (Article 84 EPC) and that claim 1 of each and every request was not inventive having regards to the disclosure of document D1 (Article 56 EPC).

VI. In a letter dated 30 January 2020, the appellant informed the Board that neither the applicant nor the representative would attend the oral proceedings and requested a decision to be made based on the current state of the file. It did not comment on the Board's communication and did not file new requests.

VII. Thus the appellant requested that the decision under appeal be set aside and that a European patent be granted on the basis of one of the main and first to third auxiliary requests, as filed with the statement of grounds of appeal.

VIII. Oral proceedings took place on 12 February 2020 in the absence of the appellant. At the end of the oral proceedings, the chairman pronounced the decision of the Board.

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

"A coding apparatus for linearly encoding predetermined information using a check matrix having an information part and a parity part, the information part being represented by one of:

a combination of a plurality of component matrices, the plurality of component matrices being one or more of: a unit matrix of size P x P; a quasi unit matrix which is a matrix wherein one or more components of the unit matrix which are 1 are changed into 0; a shift matrix which is a matrix formed by cyclically shifting the unit matrix or the quasi unit matrix; a sum matrix which is the sum of a plurality of ones of the unit matrix, quasi unit matrix and shift matrix; and a 0 matrix of size P x P; and

a combination of a plurality of component matrices by permutation of rows and/or columns of the check matrix,

in which the apparatus comprises:

a data store (14);

a re-arranger (12) for cyclically shifting the predetermined information to calculate a product of the predetermined information and the information part of the check matrix corresponding to the predetermined information;

an adder (13) operable to add the product from the re-arranger and data read out from the data store and integrate the product of the predetermined information and the information part of the check matrix corresponding to the predetermined information for each row in a unit of P rows;

wherein the data store (14) is operable to store a first integration value obtained as a result of the integration by said adder; and

an integrator (16) operable to integrate first integration values read out from said data store and to output a second integration value providing a parity bit obtained by the integration as part of the linear encoding."

X. In claim 1 of the first auxiliary request, the expression "wherein the data store (14) is operable to store a first integration value obtained as a result of the integration by said adder;" of claim 1 of the main request has been replaced with "wherein the data store (14) is operable to store first integration values obtained as a result of the integration by said adder, the first integration values comprising the P bits of a product formed from an information vector of P-bits and one of the PxP component matrices of the information part of the parity check matrix, each of the P-bits being stored at successive addresses corresponding to each of the sets of P bits received from the re-arranger (12),".

XI. In claim 1 of the second auxiliary request, the expression "by cyclically shifting information words of P-bits successively supplied thereto to determine the products of the rows of the check matrix which are non-zero and the P-bit information words" has been added to the end of the expression "a re-arranger (12) for cyclically shifting the predetermined information to calculate a product of the predetermined information and the information part of the check matrix corresponding to the predetermined information" of claim 1 of the first auxiliary request (and the expression "{p. 26 para [0061])" [sic] has been erroneously added).

XII. In claim 1 of the third auxiliary request, the expression "a bit width adjustment circuit (11) for receiving, P divided by s, s-bit information words and forming the s-bit words into P-bit words;" has been added just after "a data store (14);" and just before "a re-arranger (12) [...]" of claim 1 of the second auxiliary request.

Reasons for the Decision

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

2. The application

2.1 The application relates to Low Density Parity Check (LDPC) coding for the correction of errors in communication. The most significant characteristic of an LDPC code is that a "check" matrix (parity check matrix) H which defines the LDPC code is sparse, a sparse matrix being a matrix wherein the number of "1s" in the matrix is very small (paragraphs [0005] and [0007] of the description as originally filed). Any codeword c of a LDPC code defined by a check matrix H has the property that the product of the check matrix by (a transposed vector of) c, H.c**(T), is equal to "0".

2.2 The description of the present application discloses that, in a check matrix H of (n-k) rows and n columns, a portion of (n-k) rows and k columns (corresponding to the information word i of k bits from a codeword c of n bits) is called the "information part" and another portion of (n-k) rows and (n-k) columns (corresponding to the parity bit p of (n-k) bits) is called the "parity part" (paragraph [0010]).

2.3 Considering a check matrix H whose parity part is a lower triangular matrix (i.e. all elements on the right upper side of a diagonal line of the matrix are "0") as illustrated in Figure 3 of the application reproduced below, coding of the information word i into an LDPC code is performed in the following manner using the check matrix H.

FORMULA/TABLE/GRAPHIC

A codeword c of n bits obtained by LDPC coding is represented as the concatenation of the information word to be coded i and a parity word p, i.e.

c = (i0, i1, ... , ik-1, p0, p1, ... , pn-k-1). Since H.c**(T) equals 0, the codeword c can be obtained by determining successively the n-k bits of the parity word p0, p1, ..., pn-k-1 and placing the determined parity word behind the information word i0, i1, ..., ik-1 of k bits (paragraphs [0017] to [0030] of the description).

2.4 The description of the application presents some problems concerning the hardware implementation of an LDPC code, for example a large circuit scale for an implementation using a shift register and a lack of adaptability for an implementation using a RAM (paragraphs [0033] and [0034]).

2.5 The method described in the application starts from a check matrix H as illustrated in Figure 4 where the parity part has the structure of a lower triangular matrix. After row or column permutation, a check matrix H' as illustrated in Figures 5 and 6 is obtained. In this check matrix H' of Figure 5, the information part can be represented by a combination of the following component matrices (paragraph [0049]):

- a unit matrix of size P × P;

- a "quasi unit" matrix wherein one or more of "1"s in the unit matrix are changed to "0";

- a "shift" matrix wherein the unit matrix or the quasi unit matrix is cyclically shifted;

- the sum matrix of a plurality of ones of the unit matrix, quasi unit matrix and shift matrix; and

- a zero matrix of size P × P.

2.6 The application proposes a coding apparatus as illustrated in Figure 8 reproduced below, wherein in this example P=6:

FORMULA/TABLE/GRAPHIC

2.6.1 The functioning of this coding apparatus (after the bit width adjustment circuit 11) is as follows (see paragraphs [0057]-[0069] of the application as originally filed, see also Figure 17 and paragraphs [0118]-[0128]):

(a) the cyclic shift circuit 12 cyclically shifts information words D12 (of P=6 bits) by a number of positions indicated by the control signal D21 to determine, for those of the component matrices of the check matrix H' which are not zero matrices, the products (h x i) of the values h of the rows of the component matrices and the information words D12. The products are supplied to the adder 13 as information words D13;

(b) the adder 13 adds the products D13 to a previous sum held in the RAM 14 to obtain a sum D15;

(c) the RAM 14 receives the sum D15 from the adder 13 (in a unit of 6 bits) and supplies sums D16 (in units of 2 bits) to the interleaver 15;

(d) the interleaver 15 re-arranges the sums D16 obtained from the RAM 14 into an order corresponding to the check matrix H and supplies the re-arranged sums D17 to the accumulator 16;

(e) the accumulator 16 performs predetermined arithmetic operations based on the selection signal D23 and the sums D17, and outputs parity bits D18 to the selector 17.

3. Preliminary remark

In its communication, the Board raised a number of objections, about which no comments were filed by the appellant. The Board chooses to base its decision on the clarity objections. This does not mean that the Board has decided that the other objections do not apply anymore.

4. Clarity concerning claim 1 of all the requests - Article 84 EPC

4.1 Claim 1 of all the requests specifies that the information part of the check matrix having an information part and a parity part and used by the coding apparatus for linearly encoding predetermined information, is represented by one of "a combination of a plurality of component matrices [...]" and "a combination of a plurality of component matrices by permutation of rows and/or columns of the check matrix".

4.1.1 The skilled person would understand the expression "a combination of a plurality of component matrices by permutation of rows and/or columns of the check matrix" as meaning that the "combination of a plurality of component matrices" is obtained by "permutation of rows and/or columns" of the check matrix.

4.1.2 Combining both permutation of rows and columns of the original check matrix would yield obtained information and parity parts of the obtained check matrix having permutated rows and columns with respect to the original information and parity parts, and the obtained information part could have columns interleaved with the columns of the obtained parity part. Thus the information part of the original check matrix cannot be represented by "a combination of a plurality of component matrices [obtained] by permutation of rows and/or columns of the [original] check matrix".

4.1.3 Hence, claim 1 expresses that, as one alternative, a portion of the check matrix is obtained by permutation of the rows and/or columns of that same check matrix. This circular definition renders the claim unclear (Article 84 EPC).

4.1.4 The Board is aware of the fact that paragraphs [0047] to [0049] of the application as originally filed describe that, in the check matrix H of Figure 4, the parity part forms a lower triangular matrix, that Figures 5 and 6 show a check matrix H' after row permutation or column permutation of the check matrix H of Figure 4 is performed, and that it is in the check matrix H' of Figure 5 that the information part can be represented by a combination of a unit matrix of size P × P, a quasi unit matrix, a shift matrix, a sum matrix, and a 0 matrix of size P × P. Therefore it may have been the appellant's intention to express in claim 1 that an original check matrix H (being lower triangular in its parity part) yields, after row permutation or column permutation, the defined combination of a plurality of component matrices, as part of the check matrix H'.

However, this interpretation is not supported by the wording of claim 1, which refers only to the check matrix.

4.2 Claim 1 of all the requests also defines "an integrator (16) operable to integrate first integration values read out from said data store and to output a second integration value providing a parity bit obtained by the integration as part of the linear encoding".

4.2.1 It is however not clear for claim 1 of all the requests how the second integration value providing the parity bit is obtained by integration, by the integrator, of the first integration values, in particular how the parity bit is obtained "by the integration as part of the linear encoding". The application appears to describe this integration process (paragraphs [0108] to [0117]; Figures 14 to 16) but this process is not clearly defined in claim 1 of all the requests. (Moreover, this process could yield the parity bits only if the interleaver 15 is used to re-arrange the sums into an order corresponding to the check matrix H, the parity part of which forms a lower triangular matrix; see points 2.6(d) and 4.1.4 above).

4.3 Therefore, claim 1 of all the requests does not fulfill the requirements of Article 84 EPC.

Conclusion

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

Order

For these reasons it is decided that:

The appeal is dismissed.