T 0447/14 (Systematic chain reaction codes I/QUALCOMM) of 29.5.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. 10013222.4.

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. 10013221.6 corresponding to appeal number T 2097/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 sole request was obvious in view of document D1, contrary to the requirements of Articles 52(1) and 56 EPC.

- claim 3 was not clear, contrary to the requirements of Article 84 EPC.

IV. With the statement of grounds of appeal, the then appellant maintained the request on which the decision was based as main request and filed an auxiliary request. It requested that the decision under appeal be set aside and the application be remitted to the first instance with the order to grant a European patent based on the main request or on the auxiliary request.

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, 3 and 20 of both requests did not appear to be clear (Article 84 EPC);

- claims 1 and 20 of both requests did not appear to meet the requirements of Article 123(2) EPC;

- the subject-matter of claims 1 and 20 of both requests appeared to be novel over the method of encoding of D1 (Article 54 EPC);

- concerning the assessment of inventive step, it was not clear to the Board for which purpose the "intermediate input symbols" were generated.

VII. In a letter dated 17 April 2019, the appellant filed a new main request and new auxiliary requests 1 and 2.

VIII. The oral proceedings were held on 24 May 2019 and continued on 29 May 2019. In the course of the oral proceedings, the appellant replaced its requests with a new sole substantive request. At the end of the oral proceedings, the chairman pronounced the Board's decision.

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 sole substantive request consisting of:

- description: pages 2 to 5, 7 to 11, 15, 16, 18, 21 to 26 and 28 as originally filed, and pages 1, 6, 12 to 14, 17, 19, 20, 27, 29 and 30 as filed in the oral proceedings

- drawings: sheets 1/18 to 17/18 as filed with the letter dated 3 March 2011, and sheet 18/18 as filed in the oral proceedings

- claims: claims 1 to 6 as filed in the oral proceedings

X. Independent claim 1 of the sole substantive request reads as follows:

"A method of encoding data from received input data into encoded data that is encoded according to a code having systematic output symbols and non-systematic output symbols and that can be stored in machine-readable form and/or transmitted electronically, the method comprising:

generating, from the input data, a set of input

symbols;

outputting the set of input symbols as the systematic

output symbols;

computing with a systematic key generator systematic

keys for the input symbols in the set of input symbols using random numbers generated by a random number generator;

generating, from the set of input symbols and

corresponding systematic keys, a plurality of 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; and

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, 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 4 are directly or indirectly dependant on claim 1.

Independent claim 5 reads as follows:

"A method for decoding encoded data, wherein said data is encoded in accordance with a method of any of claims 1 or 2, said method for decoding comprising:

receiving, by a receiver, one or more systematic

output symbols forming a first subset of the set of input symbols;

receiving, by said receiver, one or more non-

systematic output symbols; and

recovering, by said receiver, a remaining subset of

the set of 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 received non-systematic output symbols; or

(ii) a combination of (a) one or more received input symbols from the first subset, and (b) one or more received non-systematic output symbols;

wherein recovering the remaining subset comprises:

chain reaction decoding a combination of the one or

more received non-systematic output symbols and the one or more received systematic output symbols into a plurality of intermediate input symbols; and

chain reaction encoding the plurality of intermediate

input symbols into a plurality of input symbols comprising a remaining subset of input symbols comprising one or more input symbols not included in the first set of input symbols;

wherein chain reaction decoding the combination

comprises:

regenerating systematic keys corresponding to the

received systematic output symbols;

regenerating non-systematic keys corresponding to the

received non-systematic output symbols; and

generating the plurality of intermediate input symbols

from (i) the systematic keys, (ii) the non-systematic keys, (iii) the received non-systematic output symbols, and (iv) the received systematic output symbols; and

wherein chain reaction encoding the plurality of

intermediate input symbols comprises:

regenerating systematic keys for the systematic

output symbols not received;

and

generating the remaining subset of input symbols from

(i) the systematic keys corresponding to the systematic output symbols not received and (ii) the intermediate input symbols."

Independent claim 6 reads as follows:

"An encoder for encoding received input data into encoded data that is encoded according to a code having systematic output symbols and non-systematic output symbols and that can be stored in machine-readable form and/or transmitted electronically, the encoder comprising:

an input symbol generator for generating from the input data a set of input symbols;

a systematic key module for computing systematic keys

for the input symbols in the set of input symbols using random numbers generated by a random number generator;

an intermediate input symbol generator for generating a plurality of intermediate input symbols from the plurality of input symbols and corresponding systematic keys in a chain reaction decoding process; and

a non-systematic key module for computing non-systematic keys for the plurality of intermediate input symbols using random numbers generated by said random number generator;

a non-systematic output symbol generator for 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

a module for outputting said set of input symbols as the systematic output symbols and for outputting said one or more non-systematic output symbols;

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."

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 larger in order of magnitude 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. Sole request

3.1 Claims 1 and 6

3.1.1 Claim 1 of the sole request relates to a method of encoding data from received input data into encoded data that is encoded according to a code having systematic output symbols and non-systematic output symbols and that can be stored in machine-readable form and/or transmitted electronically, which comprises the following features itemised by the Board:

(A) generating, from the input data, a set of input

symbols;

(B) outputting the set of input symbols as the

systematic output symbols;

(C) computing with a systematic key generator

systematic keys for the input symbols in the set of input symbols using random numbers generated by a random number generator;

(D) generating, from the set of input symbols and

corresponding systematic keys, a plurality of intermediate input symbols in a chain reaction decoding process;

(E) 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; and

(F) chain reaction encoding the plurality of

intermediate input symbols into one or more non-systematic output symbols using the non-systematic keys,

(F1) wherein one or more intermediate input symbols

are encoded into one non-systematic output symbol,

(F2) wherein each of the one or more non-systematic

output symbols is selected from an alphabet of non-systematic output symbols,

(F3) 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

(G) 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.

3.1.2 Claim 6 defines the apparatus features of an encoder performing the encoding method of claim 1.

3.2 Claim 5

3.2.1 Claim 5 of the sole request relates to a method for decoding encoded data, wherein said data is encoded in accordance with a method of any of claims 1 or 2, which comprises the following features itemised by the Board:

(H) receiving, by a receiver, one or more systematic output symbols forming a first subset of the set of input symbols;

(I) receiving, by said receiver, one or more non-systematic output symbols; and

(J) recovering, by said receiver, a remaining subset

of the set of 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 received non-systematic output symbols; or

(ii) a combination of (a) one or more received input symbols from the first subset, and (b) one or more received non-systematic output symbols;

wherein recovering the remaining subset comprises:

(K) chain reaction decoding a combination of the one

or more received non-systematic output symbols and the one or more received systematic output symbols into a plurality of intermediate input symbols; and

(L) chain reaction encoding the plurality of

intermediate input symbols into a plurality of input symbols comprising a remaining subset of input symbols comprising one or more input symbols not included in the first set of input symbols;

(M) wherein chain reaction decoding the combination comprises:

regenerating systematic keys corresponding to the

received systematic output symbols;

regenerating non-systematic keys corresponding to the

received non-systematic output symbols; and

generating the plurality of intermediate input symbols

from (i) the systematic keys, (ii) the non-systematic keys, (iii) the received non-systematic output symbols, and (iv) the received systematic output symbols; and

(N) wherein chain reaction encoding the plurality of intermediate input symbols comprises:

regenerating systematic keys for the systematic output symbols not received;

and

generating the remaining subset of input symbols from

(i) the systematic keys corresponding to the systematic output symbols not received and (ii) the intermediate input symbols.

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

4.1 Claim 1:

The feature "a method of encoding data from received input data into encoded data that is encoded according to a code having systematic output symbols and non-systematic output symbols" is based on Figure 7C and the description, page 15, lines 5 to 11, and page 16, lines 14 to 21, in conjunction with Figure 9A. The feature specifying that the encoded data "can be stored in machine-readable form and/or transmitted electronically" is disclosed in the description, page 13, lines 9 to 18. Feature A finds support in Figure 7C and the description, page 15, lines 8 to 11. Feature B is based on the description, page 16, lines 14 to 17. Feature C is supported by the description, page 15, lines 25 to 29, in conjunction with Figures 7C and 9A. Feature D is based on Figure 9A and the description, page 19, lines 21 to 24. Feature E is based on Figure 7C and the description, page 15, lines 17 to 20, in conjunction with Figure 9A. The feature specifying that it is the same random number generator which is used for generating random numbers for the non-systematic key generator and for the systematic key generator is based on Figure 7C. Features F, F1 and F2 are based on Figure 9A, on page 6, lines 6 to 8 and page 19, lines 28 to 31 of the description, and on "clause" 1 of the "Further Summary of the invention" on page 31 of the description. Feature F3 is based on page 19, line 28, to page 20, line 3, of the description. Feature G is based on page 6, lines 8 to 12 of the description and on "clause" 1 of the "Further Summary of the invention" on page 31 of the description, or on Figure 7B and page 14, lines 11 to 30 of the description, or on Figure 9B and its corresponding description on pages 20 and 21. Throughout the description, these features are also disclosed in combination.

4.2 Claim 5:

Feature H and I are based on Figure 7B and the description, page 14, lines 12 to 26, and page 20, lines 8 to 11. Feature J is based on Figure 7B and the description, page 14, line 27, to page 15, line 4, and page 20, lines 8 to 11. Feature K is based on Figure 9B and the description, page 20, lines 14 to 17. Feature L is based on Figure 9B and the description, page 20, lines 22 to 25. Feature M is based on Figure 9B and the description, page 20, lines 14 to 18. Feature N is based on Figure 9B and the description, page 20, lines 22 to 25.

4.3 Dependent claim 2 is based on Figure 7C and the description, page 16, lines 23 to 31, as well as on point 8 of the "Further Summary of the invention" on page 32 of the description.

4.4 Dependent claim 3 is based on Figure 10 and the description, from page 21, line 20, to page 22, line 15.

4.5 Dependent claim 4 is based on page 21, line 29, to page 22, line 2.

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

4.7 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.8 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. Inventive step

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

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

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

5.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.

5.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 10 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.

5.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 (see page 4, 2nd paragraph, of the appellant's letter dated 10 February 2012).

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.

5.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.

5.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 make the "trivial" observation that this can be done by means of intermediate input symbols as claimed.

But this observation cannot be derived from the cited prior art, and, without documentary evidence, the Board cannot agree that it is trivial.

5.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 5.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.

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

5.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.

5.12 Hence, the subject-matter of method claim 1 and of the corresponding apparatus claim 6 involves an inventive step over the cited prior art (Article 56 EPC).

5.13 The same conclusion applies to the subject-matter of claim 5, which is directed to a corresponding decoding method and comprises features reflecting the use of intermediate input symbols in the encoding method.

6. Conclusion

It follows from the above that a patent has to be granted in accordance with the appellant's request.

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 with the order to grant a patent on the basis of the following documents:

- description: pages 2 to 5, 7 to 11, 15, 16, 18, 21 to 26 and 28 as originally filed, and pages 1, 6, 12 to 14, 17, 19, 20, 27, 29 and 30 as filed in the oral proceedings;

- drawings: sheets 1/18 to 17/18 as filed with the letter dated 3 March 2011, and sheet 18/18 as filed in the oral proceedings;

- claims: claims 1 to 6 as filed in the oral proceedings.