T 0449/14 (Systematic chain reaction codes IV/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 application 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 becoming the "systematic" output symbols. The invention is directed to the corresponding systematic decoder and decoding method.

3. Sole request

3.1 Claim 1

3.1.1 Claim 1 of the sole request relates to a method of decoding data at a receiver received from an electronically-readable medium, wherein the received data to be decoded is received from a transmitter as a set of output symbols comprising

(A) all or some of K systematic output symbols having corresponding systematic keys and corresponding to K input symbols, the systematic keys have been generated at the transmitter using random numbers of a random number generator,

(B) all or some of a plurality of non-systematic output symbols, 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 K input symbols and from the corresponding systematic keys in a chain reaction decoding process, the non-systematic keys have been generated at said transmitter using random numbers of said random number generator,

(C) wherein K is an integer greater than one and the chain reaction encoding process may generate a potentially limitless number of non-systematic output symbols from the K intermediate input symbols, wherein each of the K input symbols is representable by a value that is from an input symbol alphabet, and wherein each of the received output symbols has a value that is from an output symbol alphabet, the method comprising: (D) determining a key for each of the received output symbols to be used in decoding;

(E) if an output symbol's key is one of the systematic keys, storing that output symbol's value as the value for at least one of the K input symbols corresponding to the systematic key, thereby recovering at least one input symbol;

(F) determining if any of the K input symbols are not yet recovered; and

(G) if any unrecovered input symbols remain, performing the steps of:

a) determining at least one of the non-systematic keys for received non-systematic output symbols;

b) determining (i) a mapping between one or more intermediate input symbols and the output symbols based on the systematic and non-systematic keys and (ii) a mapping between the one or more intermediate input symbols and the unrecovered input symbols based on the systematic keys;

c) identifying if any intermediate input symbols can be recovered from the available output symbols;

d) recovering intermediate input symbols that can be recovered in a chain reaction decoding process, and recovering input symbols from the recovered intermediate input symbols in a chain reaction encoding process; and

e) repeating steps c) and d), until a threshold number of the K input symbols are recovered.

4. Basis in the application as originally filed and in the parent application

4.1 Features A and B of claim 1, and a part of feature C, are based on Figures 7C and 9A, passages of the description as originally filed corresponding to Figure 7C, from page 15, line 5, to page 18, line 2, and passages corresponding to Figure 9A, from page 19, line 17, to page 20, line 6. The remaining part of feature C relating to "potentially limitless" is based on the description, page 8, lines 3 to 17, and page 19, line 28, to page 20, line 3. Features D, E, F and G are based on Figures 17A, 17B, and the corresponding description from page 28, line 1, to page 29, second full paragraph, and on page 15, lines 1 to 4 ("Once the desired number of missing input symbols is recovered"). The same applies mutatis mutandis to independent claim 4 defining the decoder. Claim 7 defining a computer program product is based on clause 35 on page 41 of the description and on the passages indicated above for claim 1.

4.2 Dependent claims 2 and 5 are based on the description on page 15, lines 1 to 2.

4.3 Dependent claims 3 and 6 are based on the description on page 9, lines 13 to 14.

4.4 Dependent claims 8 and 9 are based on the description, last sentence of page 22 and last paragraph of page 16 respectively.

4.5 The same passages and drawings as indicated under points 4.1 to 4.4 above were present in the parent application as originally filed.

4.6 The Board is therefore satisfied that claims 1 to 9 of the sole request comply with the requirements of Articles 76(1) and 123(2) EPC.

4.7 The amended drawing sheet 18/18 corrects obvious errors which were contained in the originally filed corresponding drawing sheet. The Board has no doubts that the skilled person would have noted these errors and corrected them in the same manner as the amendments do. The amended drawing sheet therefore does not add subject-matter contrary to Article 123(2) EPC.

5. Clarity (Article 84 EPC) of claims 7 to 9

5.1 In its decision to refuse the European patent application, the Examining Division argued that the then claims 15 to 17 were unclear, contrary to the requirements of Article 84 EPC. It was noted that "'program code for carrying out the method of any of claims 1-7' (claim 15), merely means 'code suitable for being interpreted by an unspecified computer as an instruction to perform the method of any of claims 1-7'". The Examining Division concluded that "It is noted that claims 15 to 17 do not refer to a 'standard computer' and even if they did then the examining division would be of the opinion that there are no standard computers and that therefore such claims would still be unclear."

Then claims 15 to 17 essentially correspond to present claims 7 to 9.

5.2 The Examining Division's objection corresponds to the clarity objection discussed and refuted in decision T 372/14, reasons 5. The Board does not agree with the objection for the same reasons as given there. Hence, claims 7 to 9 are clear.

6. Inventive step

6.1 Document D1, which was used by the Examining Division as starting point for assessing inventive step, relates to "chain reaction coding" (see column 7, lines 20 to 24, and column 10, lines 37 to 45). It discloses a communications system 100 comprising a conventional chain reaction encoder 115 and a conventional chain reaction decoder 155 (Figure 1; column 11, line 21, to column 12, line 51).

6.2 Encoder 115 generates output symbols from input symbols, one output symbol being generated for each key I provided by a key generator 120 (column 11, lines 48 to 50).

The value B(I) of the output symbol corresponding to the key I is obtained by applying a function, such as XOR, to one or more input symbols that are "associated" with that output symbol. The set of associated input symbols for a particular output symbol is determined by the key I (column 11, lines 50 to 56; column 13, lines 11 to 39).

The number W(I) of associated input symbols for the output symbol corresponding to key I is determined on the basis of a weight distribution, which is stored as a distribution table (column 13, lines 40 to 48).

6.3 Document D1 explains that the efficiency of chain reaction coding (in the sense of minimising the number of output symbols that need to be received to ensure a high probability of recovery of the input symbols) can be improved by optimising the weight distribution (column 24, lines 25 to 49).

6.4 The chain reaction coding process disclosed in document D1 is not systematic, since there is no control over whether the output symbols include the input symbols.

6.5 The basic idea behind the systematic coding system disclosed in the application is that a conventional non-systematic chain reaction encoder can be turned into a systematic chain reaction encoder by first converting the input symbols into suitably chosen intermediate input symbols and then encoding the intermediate input symbols with the conventional chain reaction encoder. The intermediate input symbols are chosen such that encoding them results in a sequence of output symbols that, at predetermined positions corresponding to "systematic keys", include the original input symbols. The application refers to the keys corresponding to the remaining positions as "non-systematic keys".

To ensure that the values of the output symbols corresponding to systematic keys are equal to the values of the original input symbols, the intermediate input symbols are generated by applying the reverse chain reaction decoding process to the original input symbols and the systematic keys.

The Board notes that this ensures not only that a systematic chain reaction encoding is achieved but also that the efficiency of the conventional chain reaction encoder is preserved, provided that both the systematic and the non-systematic keys are generated from the same weight distribution as the keys used in the conventional chain reaction coding process. This is because decoding the intermediate input symbols from a set of received systematic and non-systematic output symbols uses the same mechanism and has the same probability of success, i.e. is as efficient, as decoding the input symbols from a same-sized set of received output symbols encoded by the conventional encoder. Once the intermediate input symbols have been decoded, the original input symbols can always be obtained by encoding the intermediate input symbols with the systematic keys.

6.6 The decoding method of present claim 1 reflects an encoding method, disclosed in the application and claimed in the related application that was the subject of decision T 447/14, which essentially implements this basic idea.

As the "systematic" output symbols, i.e. the output symbols corresponding to the systematic keys, are equal to the original input symbols, they are generated simply by outputting the set of input symbols. This saves the effort of encoding the intermediate input symbols with the systematic keys to obtain the original input symbols which are anyway already available.

Then the method computes the systematic keys with a systematic key generator that uses random numbers generated by a random number generator. The intermediate input symbols are generated from the set of input symbols and the computed systematic keys by applying the (conventional non-systematic) chain reaction decoding process.

Since the systematic output symbols do not need to be (re-)generated, the (conventional non-systematic) chain reaction encoder is used to encode the intermediate input symbols with non-systematic keys to produce non-systematic output symbols. The non-systematic keys are generated with a non-systematic key generator that uses the random numbers generated by the same random number generator as used by the systematic key generator. The Board accepts that the use of the same random number generator means that the (systematic and non-systematic) keys have the same weight distribution as the keys used by the conventional non-systematic chain reaction encoder.

6.7 Hence, the encoding method disclosed in the application and the corresponding decoding method of claim 1 turn a non-systematic chain reaction coding scheme such as disclosed in document D1 into a systematic chain reaction coding scheme that preserves the efficiency of the non-systematic chain reaction coding process.

6.8 In the communication accompanying the summons to oral proceedings in the related case T 447/14, the Board argued that the skilled person would succeed in turning a conventional non-systematic chain reaction encoder as disclosed in document D1 into a systematic chain reaction encoder simply by first outputting the input symbols as systematic output symbols and then generating non-systematic output symbols by encoding the input symbols directly with the non-systematic chain reaction encoder. The method of then claim 1 corresponded to this approach but with the extra complication of generating the intermediate input symbols. The Board expressed doubt that this extra complication contributed to any technical effect.

However, claim 1 now implies that the weight distribution of the keys is preserved (see point 6.6 above). This would not be guaranteed in the simplified and arguably obvious approach suggested in the Board's communication. For example, if the non-systematic chain reaction encoder employs the XOR function, then the systematic output symbols all have weight 1 relative to the input symbols (each systematic output symbol being the "XOR" of its corresponding input symbol), which would distort the overall weight distribution and thereby affect coding efficiency. The systematic coding system of the claimed invention avoids this distortion by ensuring that all output symbols are encoded with the appropriate weight distribution relative to the intermediate input symbols. The above-mentioned "extra complication" therefore now contributes to preserving the weight distribution and thus also to the technical effect of preserving the efficiency of the chain reaction coding process.

6.9 The inventive-step reasoning contained in the decision under appeal and the novelty reasoning contained in the Board's communication need not be discussed in detail, since claim 1 has been considerably amended compared with the independent claims on which the contested decision and the Board's communication were based. In particular, the claimed decoding method now reflects the essential features of the systematic encoding method disclosed in the application.

6.10 In sum, the disclosure of document D1 does not render the subject-matter of claim 1 obvious.

6.11 Document D2 is a brief introduction into linear block codes, which are not chain reaction codes. It is not closer to the claimed invention than document D1.

6.12 It follows that the subject-matter of independent claim 1 and corresponding independent claims 4 and 7 involves an inventive step over the cited prior art (Article 56 EPC).

7. Remittal

7.1 The beginning of claim 1 reads as follows:

"A method of decoding data at a receiver received from an electronically-readable medium, wherein the received data to be decoded is received from a transmitter as a set of output symbols"

At first glance, this formulation seems contradictory since, on the one hand, the data to be decoded is said to be received "from an electronically-readable medium" and, on the other hand, the same data (i.e. the "received data to be decoded") is said to be received "from a transmitter".

Hence, claim 1 may still require amendment for it to comply with Article 84 EPC.

7.2 Moreover, the description may still have to be adapted to the claims of the sole request.

7.3 It is therefore appropriate to remit the case to the Examining Division for further prosecution.

8. The request for reimbursement of the appeal fee

8.1 In its statement of grounds of appeal, the appellant noted that the contested decision's wording was nearly identical to that of the Examining Division's communication dated 25 September 2012, which itself was largely identical to the European search opinion. The appellant's response dated 5 April 2013 therefore appeared not to have been taken into account in the decision.

At the oral proceedings, the appellant confirmed that it alleged that the Examining Division had committed a substantial procedural violation and that it requested reimbursement of the appeal fee in accordance with Rule 103(1)(a) EPC.

8.2 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).

8.3 The European search opinion contains, in point 2, a lengthy discussion of "chain reaction coding" as known from document D1 and of "common binary block encoding" as disclosed in document D2. The core of the inventive-step reasoning is found in point 3, where the Examining Division briefly analysed claim 1 and argued that it defined "nothing more than trivial linear algebra applied to a systematic block code on an erasure channel". Since erasure decoding was known from document D1, and since systematic block codes were well-known, the subject-matter of claim 1 was obvious.

8.4 In its letter of 17 February 2012, the appellant criticised many of the statements made in point 2 of the European search opinion but did not directly address point 3. The arguments in this letter are dealt with in some detail in point 5 of the reasons for the decision.

8.5 The appellant's letter of 5 April 2013 in response to the communication dated 25 September 2012 repeats, at least to some extent, the arguments already made in the letter of 17 February 2012. The remaining arguments again do not directly address point 3 of the European search opinion (corresponding to point 3 of the communication).

8.6 In view of this, the Board cannot easily identify ex officio a specific argument of the appellant that was clearly crucial with respect to the Examining Division's reasons for refusing the application and ignored in the written decision. Since the appellant's arguments in support of reimbursement of the appeal fee were essentially limited to noting that large parts of the decision had been copied from the European search opinion and the communication dated 25 September 2012, the Board is therefore not in a position to allow the request for reimbursement.