T 2097/14 (Systematic chain reaction codes III/QUALCOMM) of 12.12.2019

Summary of Facts and Submissions

I. The then applicant (Digital Fountain, Inc.) appealed against the decision of the Examining Division refusing European patent application No. 10013221.6.

II. The application is a divisional of European patent application No. 03808111.3.

It has the following siblings:

- European patent application No. 10013219.0 corresponding to appeal number T 0449/14;

- European patent application No. 10013220.8 corresponding to appeal number T 0372/14;

- European patent application No. 10013222.4 corresponding to appeal number T 0447/14.

III. The decision cited the following documents:

D1: US 6 307 487 B1 (Luby, Michael), published on

23 October 2001

D2: "Error-Control Block Codes for Communications

Engineers", L.H. Charles Lee, published in 2000,

Artech House, pages 39 to 45

The Examining Division decided that:

- the subject-matter of claim 1 of the then sole request lacked novelty over D2 (Article 54 EPC);

- the subject-matter of claims 2 to 7 and 10 to 15 was not inventive over D2 (Article 56 EPC);

- claims 8, 9, 16 and 17 (the latter erroneously being referred to as claim 7) were not clear (Article 84 EPC).

The decision further contains, in the context of the assessment of inventive step, remarks about the clarity of claims 2 to 7 and 10.

IV. With the statement of grounds of appeal, the then appellant resubmitted a copy of the claims considered in the contested decision.

V. In the course of the appeal proceedings the European Patent Office registered a transfer of the application to QUALCOMM Incorporated, which thereby acquired the status of appellant.

VI. In a communication accompanying a summons to oral proceedings, the Board expressed the preliminary opinion that:

- claims 1, 8 and 10 were not clear (Article 84 EPC);

- the subject-matter of claims 1 and 10 was new over documents D1 and D2 (Article 54 EPC).

Concerning the assessment of inventive step, the Board invited the appellant to explain which technical problem was solved by the use of "intermediate input symbols".

VII. In a letter dated 18 April 2019, the appellant replaced its sole request with a main request and auxiliary requests 1 to 4.

VIII. During oral proceedings held on 29 May 2019, the appellant replaced its requests with a new main request. At the end of the oral proceedings, the Chairman announced that the decision would be given in writing.

IX. The appellant's final requests were that the decision under appeal be set aside and that a patent be granted on the basis of the claims of the new main request. It also requested that the appeal fee be reimbursed.

X. Independent claim 1 of the new main request reads as follows:

"A method of encoding data into a code having systematic output symbols and non-systematic output symbols, the method comprising:

generating, from the data, a set of k input symbols: [sic]

outputting the set of k input symbols as the systematic output symbols;

computing with a systematic key generator

systematic keys for the set of k input symbols using

random numbers generated by a random number generator,

said computing including computing L unique keys,

wherein L is a function of the number of input symbols,

k;

generating, from the set of k input symbols and

corresponding systematic keys, a plurality of k

intermediate input symbols in a chain reaction decoding

process;

generating with a non-systematic key generator non-

systematic keys for the plurality of intermediate input symbols using random numbers generated by said random number generator;

chain reaction encoding the plurality of

intermediate input symbols into one or more non-

systematic output symbols using the non-systematic

keys, wherein one or more intermediate input symbols

are encoded into one non-systematic output symbol,

wherein each of the one or more non-systematic output

symbols is selected from an alphabet of non-systematic

output symbols, and wherein, for each non-systematic

key, a non-systematic output symbol is generated as a

function of one or more of the plurality of

intermediate input symbols and the non-systematic key,

and

wherein any subset of the set of input symbols that

will not be acquired by a receiver of the code is recoverable from (i) a predetermined number of non systematic output symbols that will be acquired, or (ii) a combination of (a) input symbols that will be acquired and (b) one or more of the non-systematic output symbols that will be acquired."

Claims 2 to 5 are directly or indirectly dependent on claim 1.

Independent claim 6 reads as follows:

"A computer-readable medium comprising program code for carrying out the method of claim 1, when said program code is executed on a processor of a computer system."

Independent claim 7 reads as follows:

"An encoder with a processor and the computer-readable medium of claim 6."

Independent claim 8 reads as follows:

"A method of decoding a code having systematic output symbols and non-systematic output symbols into a set of input symbols, the input symbols comprising data which is sought, the method comprising:

acquiring a first subset of the set of input

symbols at a receiver, the first subset of input symbols comprising one or more acquired systematic output symbols, said acquired systematic output symbols having corresponding systematic keys that are generated at a transmitter using random numbers of a random number generator and that are regenerated at the receiver;

acquiring one or more non-systematic output symbols

at the receiver, wherein each acquired non-systematic output symbol is selected from an alphabet of non systematic output symbols, and wherein each non-systematic output symbol was generated in a chain reaction encoding process at said transmitter as a function of one or more of a plurality of intermediate input symbols using a corresponding non-systematic key, said plurality of intermediate input symbols having been generated at said transmitter from the set of input symbols and from corresponding systematic keys in a chain reaction decoding process, the non-systematic keys being generated at said transmitter using random numbers of said random number generator and being regenerated at said receiver; and

recovering a remaining subset of the input symbols

comprising one or more input symbols not included in the first subset of input symbols, the remaining subset of input symbols recovered from: (i) a predetermined number of acquired non-systematic output symbols; or (ii) a combination of (a) one or more input symbols from the first subset, and (b) one or more acquired non-systematic output symbols;

wherein recovering a remaining subset of the input

symbols comprises:

(i) creating a matrix B using regenerated non-

systematic keys, wherein the number of rows in B corresponds to the number of acquired non-systematic output symbols and wherein the number of columns in B corresponds to the number of input symbols, and wherein said creating comprises generating for each non-systematic key a weight and a set of indices (J1, J2,...,JW) of input symbols from which the acquired non-systematic output symbol corresponding to the non-systematic key is generated, wherein in the corresponding row of the matrix B the positions corresponding to the set of indices are set to 1, while other positions in that row are set to 0 and wherein the procedure is repeated until all non-systematic keys corresponding to acquired non-systematic output symbols are exhausted;

(ii) creating a square matrix C from the

regenerated systematic keys in a similar manner than creating matrix B, wherein the number of rows and columns in C corresponds to the number of input symbols.

(iii) creating a matrix A as the inverse of matrix

C;

(iv) creating a matrix H from the product of B and

A;

(v) creating a set E, wherein E is the set of

indices of the non-acquired systematic symbols;

(vi) creating a set R, wherein R is the set of

indices of the acquired systematic symbols;

(vii) dividing matrix H into sub-matrices He and

Hr, wherein He corresponds to the indices of the systematic symbols not acquired and wherein Hr corresponds to the indices of the systematic symbols acquired;

(viii) creating vector y from the product of Hr

with a vector formed by the acquired systematic symbols;

(ix) creating vector b from the acquired non-

systematic output symbols;

(x) solving the system of equations for x, wherein

the system of equations is He*x = y+b; and

using x to recover input symbols."

Claims 9 to 13 are dependent on claim 8.

Independent claim 14 reads as follows:

"A computer-readable medium comprising program code for carrying out the method of claim 8, when said program code is executed on a processor of a computer system."

Independent claim 15 reads as follows:

"A decoder with a processor and the computer-readable medium of claim 14."

Reasons for the Decision

1. Admissibility of the appeal

1.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 "chain reaction codes" (such as chain reaction coding systems described in D1 and referred to in the application as "Luby I", or such as "Raptor" codes), which are a form of forward error correction (FEC) codes. These codes are used in the transmission of data between a sender and a recipient over a communication channel.

2.2 One problem with FEC codes is that the number of output symbols must be determined in advance of the coding process. This can lead to inefficiencies if the loss rate of packets is overestimated, and can lead to failure if the loss rate of packets is underestimated (see page 3 of the description as filed, first paragraph).

2.3 For chain reaction codes, the pool of possible output symbols that can be generated is orders of magnitude larger than the number of the input symbols, and a random output symbol from the pool of possibilities can be generated very quickly. The output symbols can be generated on the fly on an "as needed" basis concurrent with the sending step. Chain reaction codes have the property that all input symbols of the content to be encoded can be regenerated from any subset of a set of randomly generated output symbols slightly longer in length than the original content (see page 3, third paragraph).

2.4 In a chain reaction coding system the output symbols are usually generated as follows: for every output symbol a key is (pseudo)randomly generated. Based on the key, a weight W is computed from a weight table. Then a (pseudo)random subset of W source symbols is chosen. The output symbol will then be the "exclusive OR", or XOR, of these source symbols. These source symbols are called the "neighbors" or "associates" of the output symbol (see page 4, third paragraph).

2.5 A coding system is referred to as a systematic coding system, if it transmits the source symbols first, and then continues the transmission by sending output symbols. On the receiving side, the receiver may try to receive as many original input symbols as possible, replace the input symbols not received by one or more output symbols and use them to recover the missing input symbols (see page 4, last paragraph).

2.6 Straightforward modifications of chain reaction coding systems as described in D1 ("Luby I"), to produce systematic coding systems, generally lead to inefficiencies. For example, if in a chain reaction coding system the first transmitted symbols comprise the original symbols, then it may be necessary to receive a number of pure output symbols which is of the same order of magnitude as the original symbols in order to be able to recover the original data. In other words, reception of the original symbols may only minimally help the decoding process, so that the decoding process has to rely entirely on the other received symbols. This leads to an unnecessarily high reception overhead (see page 5, second paragraph).

2.7 One possible embodiment of a decoding process for a chain reaction decoding can be described in terms of the corresponding decoding graph, as exemplified in Figure 3 of the application. This graph consists of two sets of nodes, the source nodes, and the output nodes, corresponding to the source symbols and to the received output symbols, respectively.

2.8 A matrix representation of the decoding graph is also possible. The decoding matrix corresponding to the decoding graph has as many rows as there are output nodes, and as many columns as there are source nodes, and has entries 0 or 1. There is a "1" at position (k, j) of the decoding matrix if the j-th source node is a neighbor of the k-th output node (page 10, last paragraph, to page 11, second paragraph).

2.9 The invention proposes a systematic version of a chain reaction coding system which has a similar reception overhead as a conventional chain reaction coding system. The systematic encoder consists of a conventional chain reaction decoder 910 concatenated with a conventional chain reaction encoder 920 (see Figure 9A). The conventional chain reaction decoder is used to convert the input symbols into intermediate symbols by using "systematic keys". These intermediate symbols are fed to the conventional chain reaction encoder which generates non-systematic output symbols by using non-systematic keys. Both the non-systematic output symbols and the input symbols are sent as output, the input symbols thereby becoming the "systematic" output symbols.

3. Right to be heard

3.1 The Examining Division decided that the subject-matter of claim 1 lacked novelty because it was fully anticipated by "normal systematic block encoding" as disclosed in document D2. The reasons for the decision under appeal were copied from the European search opinion, except for the last two paragraphs. These last two paragraphs contain remarks about the inventive-step objections. The decision therefore does not deal explicitly with any of the appellant's arguments in respect of the Examining Division's novelty objection.

3.2 In its letter dated 17 February 2012 in response to the European search opinion, the appellant argued that document D2 did not anticipate the subject-matter of claim 1 because it failed to disclose, among other features, the step of computing systematic keys. It repeated this argument in its letter of 2 May 2013 and, again, in its letter of 14 February 2014 in reply to the summons to oral proceedings before the Examining Divisions.

3.3 The Examining Division referred to this argument only in its communication of 23 October 2012, where it stated the following:

"In the present communication, it is not argued that in block codes keys are calculated. It is, instead, observed that the key identifies the symbol. In a normal block code the symbols are in a fixed order so that no key has to be calculated".

The Examining Division hence admitted that "normal systematic block coding" as disclosed in document D2 did not disclose one of the features of claim 1. It must therefore have been aware that the appellant's argument directly put into question the correctness of its novelty reasoning. Yet, it maintained the objection and its original reasoning.

3.4 The right to be heard under Article 113(1) EPC encompasses the right of a party to have its comments considered in the written decision (see decision T 763/04 of 22 June 2007, reasons 4.3 and 4.4). Although a decision does not have to address each and every argument of a party in detail, it must comment on the crucial points of dispute in order to give the losing party a fair idea of why its arguments were not considered convincing (see decision T 1557/07 of 9 July 2008, reasons 2.6).

3.5 In the present case, the argument that the prior art cited by the Examining Division did not disclose at least one of the features of claim 1 was clearly crucial to the question of novelty. The appellant raised this argument early and maintained it throughout the first-instance proceedings. The only time that the Examining Division acknowledged the argument, it effectively confirmed its relevance but did not modify the reasoning. The Board can therefore only conclude that the argument was not considered in the written decision and that, consequently, the appellant's right to be heard was infringed (Article 113(1) EPC). This amounts to a substantial procedural violation.

3.6 Although the finding of a substantial procedural violation in principle may justify an immediate remittal of the case to the department of first instance (Article 11 RPBA), for the sake of procedural efficiency the Board will still deal in substance with the grounds for the refusal.

4. Novelty and inventive step over document D2

4.1 Since present claim 1 still defines a step of computing systematic keys, and since the Board agrees with the appellant that document D2 does not disclose this feature, the subject-matter of claim 1 is new over document D2 for this reason alone.

4.2 In its decision, the Examining Division argued that "chain reaction codes", with which the invention is concerned, encompassed well-known linear block codes.

As explained in point 2.3 above, in a chain reaction coding system, the encoder is designed to encode a set of input symbols on the fly into an effectively unlimited number of output symbols, and the decoder is designed to reconstruct the input symbols with high probability from any set of received output symbols that is just slightly larger in size than the set of input symbols. Chain reaction codes are therefore fundamentally different from linear block codes, which are codes of finite length.

Since document D2 merely contains a brief introduction into linear block codes, it is unrelated to chain reaction codes and cannot render the claimed invention obvious.

5. Clarity

5.1 In its decision, the Examining Division raised a clarity objection against then claim 8, which reads as follows:

"A computer-readable medium comprising code for performing the method of claim 1."

It argued that the claim did not provide a clear definition of the "code for performing the method of claim 1", which could be any code that could be interpreted by an unspecified runtime environment as an instruction to perform the method of claim 1.

The Examining Division added that, consequently, also claims 9, 16 and 17 were unclear.

5.2 Then claim 8 corresponds to present claim 6, which reads as follows:

"A computer-readable medium comprising program code for carrying out the method of claim 1, when said program code is executed on a processor of a computer system."

Although claim 6 now refers to a "computer system" as a "runtime environment" for the program code, the claim leaves this computer system unspecified. The essence of the Examining Division's clarity objection therefore still appears to be applicable.

Then claims 9, 16 and 17 likewise correspond to present claims 7, 14 and 15.

5.3 It is not immediately evident why the lack of a further specification of "computer system" would render the definition of "program code for carrying out the method of claim 1, when said program code is executed on a processor of a computer system" unclear. The Board suspects that the Examining Division was concerned about defining "program code" implicitly or explicitly by reference to a separate "runtime environment" or "computer system".

5.4 It is true that the question whether a given computer-readable medium falls within the scope of claim 6 depends not only on its data content but also on the computer system for which the computer-readable medium is intended. But the Board fails to see why this should render the claim unclear. If the data stored on the given computer-readable medium is not intended to be loaded as a computer program into a computer system for execution, the computer-readable medium does not fall within the scope of the claim. If its data content is intended to be loaded as a computer program into a computer system for execution, it falls within the scope of the claim if that computer system, when executing the program, would carry out the method of claim 1. The required intention has to be derivable from the data carrier itself or the context in which it is disclosed.

5.5 Hence, claim 6 and also claims 7, 14 and 15 are clear (Article 84 EPC).

5.6 The Board is further satisfied that the clarity objections raised in the communication accompanying the summons to oral proceedings before the Board no longer apply to the claims of the new main request.

6. Remittal

6.1 The new main request was filed during the oral proceedings before the Board and has not yet been fully examined. The Board will therefore remit the case to the Examining Division for further prosecution on the basis of the new main request.

6.2 The Examining Division should, in particular, examine whether the new main request complies with Articles 76(1), 84 and 123(2) EPC.

6.3 As to novelty and inventive step over document D1, although the independent claims may still need amendment in view of the requirements of Articles 76(), 84 and 123(2) EPC, at present they do appear to include the features of the independent claims that formed the basis for an order to grant a patent in the related case T 447/14.

6.4 In view of this similarity, the Examining Division may also wish to consider the issue of double patenting.

7. Reimbursement of the appeal fee

Since the above-mentioned violation of the right to be heard affected the main ground for the refusal, reimbursement of the appeal fee under Rule 103(1)(a) EPC is equitable.

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the department of first instance for further prosecution.

3. The appeal fee is to be reimbursed.