T 0372/14 (Systematic chain reaction codes II/QUALCOMM) 01-07-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 a 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. Sole request

3.1 Claims 1 and 6

3.1.1 Claim 1 of the sole request relates to a method of encoding data, wherein the data to be encoded is represented as a set of K input symbols stored in an electronically-readable medium, K being an integer greater than one, wherein each of the K input symbols has a value that is from an input symbol alphabet, and wherein the encoded data is representable as a plurality of output symbols, each of which has a value that is from an output symbol alphabet, which comprises the following features itemised by the Board:

(A) obtaining at an input the K input symbols in an electronically-readable form, such that each of the K input symbols has an associated position within the K input symbols;

(B) determining K systematic keys for the K input symbols, wherein the systematic keys have been generated with a systematic key generator using random numbers generated by a random number generator;

(C) generating, from the input symbols, a plurality of intermediate input symbols, each intermediate input symbol having an associated position within the plurality of intermediate input symbols, wherein the generation of the plurality of intermediate input symbols from the plurality of input symbols is performed according to a chain reaction decoding process and using the corresponding systematic keys;

(D) determining non-systematic keys for the plurality of intermediate input symbols, wherein the non-systematic keys have been generated with a non-systematic key generator using random numbers generated by said random number generator; and

(E) generating output symbols of the plurality of output symbols, wherein generating output symbols of the plurality of output symbols comprises

(E1) generating K systematic output symbols by passing the K input symbols from the input to a transmit module and

(E2) generating a number of non-systematic output symbols using chain reaction encoding and having the plurality of intermediate input symbols and the corresponding non-systematic keys as an input, said non-systematic output symbols being output to the transmit module, and

(F) wherein any subset of the set of input symbols that will not be acquired by a receiver 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."

3.1.2 Claim 6 defines an encoder corresponding to the encoding method of claim 1, but in terms of apparatus features.

3.1.3 Claim 10 relates to a computer program product that comprises a non-transitory tangible medium storing computer-executable code for execution upon a computer system including a processor, the computer program product comprising:

program code for carrying out the method of any of claims 1 to 5, when said code is executed on said processor.

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

4.1 Claims 1 and 6:

The feature "wherein the data to be encoded is represented as a set of K input symbols stored in an electronically-readable medium, K being an integer greater than one, wherein each of the K input symbols has a value that is from an input symbol alphabet, and wherein the encoded data is representable as a plurality of output symbols, each of which has a value that is from an output symbol alphabet" is based on page 15, lines 5 to 16, of the description as originally filed, together with Figure 7C, and on page 14, lines 3 to 10. Feature A finds support in the description, on page 15, lines 8 to 11. Features B and D are disclosed on page 15, lines 17 to 31 of the description, and the connections of the random number generator 735 of Figure 7C to both the systematic key generator 730 and the non-systematic key generator 727.

Feature C is based on page 19, lines 17 to 27, of the description, and Figure 9A. Features E, E1 and E2 find support in the description, from page 19, line 28, to page 20, line 6, and page 16, lines 14 to 19. Feature F is based on Figure 7B and the description, from page 14, line 11, to page 15, line 4.

4.2 Claim 10 is based on clause 32 on page 40 of the description.

4.3 Dependent claims 2 and 7 are based on the description, page 19, lines 4 and 5.

4.4 Dependent claims 3 and 8 are based on the description, page 22, lines 21 to 31.

4.5 Dependent claims 4 and 9 are based on the description, page 16, lines 14 to 16, and 23 to 26.

4.6 Dependent claim 5 is based on the description, page 14, lines 22 to 25.

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

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

4.9 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 Articles 76(1)and 123(2) EPC.

5. Clarity

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

"A computer program product that comprises a non-transitory tangible media storing computer-executable code for execution upon a computer system including a processor, the computer program product comprising:

program code for carrying out the method of any of claims 1 to 8."

It argued that "program code for carrying out the method of any of claims 1 to 8" merely meant "code suitable for being interpreted by an unspecified computer as an instruction to perform the method of any of claims 1 to 8". Whether a particular disclosure fell within the scope of claim 16 depended not solely on that disclosure but also on the unspecified computer.

5.2 Then claim 16 defined its subject-matter by reference to an entity, namely a computer system, that was not part of the claimed invention, and the same applies to present claim 10. It is true that this makes the answer to the question whether a given data carrier falls within the scope of the claim dependent not only on its data content and the method being implemented but also on the computer system for which the data carrier is intended. But the Board fails to see why this should render the claim unclear. If the data stored on the given data carrier is not intended to be loaded as a computer program into a computer system for execution, the data carrier 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. The required intention has to be derivable from the data carrier itself or the context in which it is disclosed.

5.3 Hence, the clarity objection raised in the decision under appeal is not convincing. As the Board sees no other reason to object to the clarity of the claims, it is satisfied that the sole substantive request complies with Article 84 EPC.

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 and the distribution of associated input symbols over the output symbols (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 encoding method of claim 1 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 (see page 6 of the statement of grounds of appeal).

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 encoding method of claim 1 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 of claim 1 turns a non-systematic chain reaction coding process such as disclosed in document D1 into a systematic chain reaction coding process that preserves the efficiency of the non-systematic chain reaction coding process.

6.8 In the contested decision, the Examining Division essentially argued that the skilled person, looking for a way to turn the non-systematic chain reaction coding process disclosed in document D1 into a systematic chain reaction coding process, would have attempted to do so by suitably precoding the input data before encoding it with the non-systematic chain reaction encoder and would then, as a mathematical necessity, have arrived at the claimed method.

However, without any suggestion in the prior art to the effect that an efficient systematic chain reaction coding process can be obtained by suitably precoding the input data, the Examining Division's reasoning is tainted with hindsight and thus unconvincing.

6.9 In the communication accompanying the summons to oral proceedings, 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 claimed invention avoids this distortion by ensuring that all output symbols are encoded with the appropriate weight distribution relative to the intermediate input symbols. In present claim 1, the above-mentioned "extra complication" therefore contributes to preserving the weight distribution and thus also to the technical effect of preserving the efficiency of the chain reaction coding process.

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 Therefore, the Board is convinced that the subject-matter of independent claim 1 is inventive over the cited prior art (Article 56 EPC). The same applies to corresponding apparatus claim 6 and computer program product claim 10.

7. Double patenting

7.1 The Board is aware that independent claims 1 and 6 of the sole substantive request are similar in scope to independent claims 1 and 6 that were found to be allowable in decision T 447/14 of 29 May 2019. However, since the present independent claims require the output symbols to be transmitted (via a transmit module) rather than merely output, their scope is only similar and not identical. The prohibition of double patenting therefore does not apply.

8. Conclusion

Since the appellant's sole substantive request complies with the EPC, the appeal is to be allowed.