T 2097/14 (Systematic chain reaction codes III/QUALCOMM) 12-12-2019

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.