T 2235/15 (Multi-stage coding IV/QUALCOMM) of 14.3.2019

Summary of Facts and Submissions

I. The appeal lies from the decision of the Examining Division to refuse European patent application No. 10013236.4, filed as a divisional application of European patent application No. 02794439.6, which was published as WO 03/056703.

II. In the decision under appeal, the Examining Division decided that the independent claims of the main request and first and second auxiliary requests did not fulfil the requirements of Article 84 EPC. A third auxiliary request was not admitted into the proceedings under Rules 116(1) and 137(3) EPC.

III. In its statement of grounds of appeal, the then appellant, Digital Fountain, Inc., requested that the decision be set aside and that a patent be granted on the basis of the main request or one of the first, second and third auxiliary requests considered in the contested decision and resubmitted with the grounds of appeal as annexes A, B, C and D.

IV. With effect from 19 April 2018, the European Patent Office registered a transfer of the application to QUALCOMM Incorporated, which thereby acquired the status of appellant.

V. In a communication accompanying a summons to oral proceedings, the Board cited, inter alia, the following documents:

L1: US 6 307 487 B1, published on 23 October 2001;

DA1: Clark Jr., G.C., Cain, J.B.: "Error-Correction Coding for Digital Communications", pages 331 to 341, Plenum Press, New York, US, 1981; and

DA4: US 5 983 383, published on 9 November 1999.

In its communication, the Board stated that it was not persuaded by the reasoning of the decision under appeal with regard to Article 84 EPC, which seemed unclear. Nevertheless, the Board was of the preliminary opinion that the main request did not fulfil the requirements of Articles 76(1) and 84 EPC. The subject-matter of claims 1 and 3 of the main request seemed to lack inventive step over the disclosure of document L1 in combination with the common general knowledge of the skilled person. Similar objections applied to the first and second auxiliary requests. With regard to the third auxiliary request, it had to be discussed whether the request should be admitted into the proceedings and, if admitted, whether it fulfilled the requirements of Articles 56, 76(1) and 84 EPC. The subject-matter of claims 1 and 3 of this request did not seem to be inventive over document L1 in combination with the common general knowledge of the skilled person.

VI. With a letter of reply, the appellant submitted further auxiliary requests as annexes A', B', C' and D'. With a later letter, the appellant filed additional auxiliary requests as annexes A'', C'', D'', A''', C''' and D'''.

VII. Oral proceedings were held on 14 March 2019. During the oral proceedings, the appellant replaced its requests with a new sole substantive request labelled "ANNEX A''c". At the end of the oral proceedings, the chairman pronounced the Board's decision.

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 following documents:

- Claims: claims 1 to 5 of the amended set of claims labelled "ANNEX A''c" as filed in the oral proceedings at 14:00 hours;

- Description: pages 1 to 6 and 8 to 44 as originally filed, pages 7 and 45 as filed in the oral proceedings;

- Drawings: Figures 1 to 22 as originally filed.

VIII. Claim 1 of the sole request ANNEX A''c reads as follows:

"A decoder for decoding output symbols received over an erasure communications channel wherein the output symbols represent multi-stage encoded data sent by one or more transmitters, the decoder comprising:

a receiver input for receiving output symbols,

wherein a dynamic key generator has generated a dynamic key for each output symbol to be generated by a dynamic encoder, wherein the number of distinct dynamic keys that can be generated with the dynamic key generator is only limited by the key resolution, wherein the dynamic encoder has received each dynamic key, and wherein the dynamic encoder has generated each output symbol based on the corresponding dynamic key from at least one symbol in a combined set of input symbols and redundant symbols, each output symbol having a weight representing the number of symbols from the combined set used to generate that output symbol, wherein the weights of the output symbols in the plurality of output symbols are distributed in a way to minimize the number of operations needed to regenerate the ordered set of input symbols, wherein at least one output symbol is generated from more than one symbol in the combined set and less than all of the symbols in the combined set, wherein the input symbols are from an ordered set of input symbols, wherein the redundant symbols are generated from the input symbols;

memory for storing received output symbols received at the receiver input;

a dynamic key regenerator that generates corresponding dynamic keys for the received output symbols;

dynamic decoder logic that decodes, upon receiving N output symbols, wherein N is an integer, a subset of the symbols in the combined set from the N output symbols, the subset including a plurality of decoded input symbols and a plurality of decoded redundant symbols, the dynamic decoder being dynamic in that it can decode symbols generated by the dynamic encoder encoding the data sent by the one or more transmitters; and

static decoder logic that decodes at least some undecoded input symbols, if any, from the plurality of decoded redundant symbols, wherein the static decoder can decode data that was encoded by static encoding, wherein static encoding is an encoding wherein the number of the redundant symbols is determined prior to encoding, and wherein the redundant symbols add redundant information in such a way that recovery of the ordered set of input symbols is possible in face of erasures."

Claims 2 to 5 are directed to a method of multi-stage decoding, a computer readable medium with program code for carrying out the method of claim 2, a method of multi-stage encoding and a system for multi-stage encoding comprising features essentially corresponding to those of claim 1. The text of those claims is given below.

Claim 2 reads as follows:

"A method of multi-stage decoding output symbols transmitted over an erasure communications channel, the method comprising:

(i) receiving a plurality of multi-stage encoded output symbols,

wherein a dynamic key generator has generated a dynamic key for each symbol to be generated by a dynamic encoder, wherein the number of distinct dynamic keys that can be generated with the dynamic key generator is only limited by the key resolution, wherein the dynamic encoder has received each dynamic key, and wherein the dynamic encoder has generated each output symbol based on the corresponding dynamic key from at least one symbol in a combined set of input symbols and redundant symbols, each output symbol having a weight representing the number of symbols from the combined set used to generate that output symbol, wherein the weights of the output symbols in the plurality of output symbols are distributed in a way to minimize the number of operations needed to regenerate the ordered set of input symbols, wherein at least one output symbol is generated from more than one symbol in the combined set and less than all of the symbols in the combined set, wherein the input symbols are from an ordered set of input symbols, wherein the redundant symbols are generated from the input symbols;

(ii) storing the output symbols in memory;

(iii) generating corresponding dynamic keys for the received output symbols by a dynamic key regenerator;

(iv) decoding, using a dynamic decoder, upon receiving N output symbols, wherein N is an integer, a subset of the symbols in the combined set from the N output symbols, the subset including a plurality of decoded input symbols and a plurality of decoded redundant symbols, the dynamic decoder being dynamic in that it can decode symbols generated by a dynamic encoder encoding the data sent by the one or more transmitters;

(v) decoding, using static decoding, at least some undecoded input symbols, if any, from the plurality of decoded redundant symbols, wherein the static decoding is decoding that can decode data that was encoded by static encoding, wherein static encoding is an encoding wherein the number of the redundant symbols is determined prior to encoding, and wherein the redundant symbols add redundant information in such a way that recovery of the ordered set of input symbols is possible in face of erasures."

Claim 3 reads as follows:

"A computer-readable medium for use with electronics capable of executing instructions read from the computer-readable medium, the computer-readable medium having stored thereon program code for carrying out the method of claim 2."

Claim 4 reads as follows:

"A method of multi-stage encoding data for transmission from a source to a destination over an erasure communications channel, the method comprising:

generating, using static encoding, a plurality of redundant symbols from an ordered set of input symbols to be transmitted, and wherein static encoding is an encoding wherein the number of the redundant symbols is determined prior to encoding, and wherein the redundant symbols add redundant information in such a way that recovery of the ordered set of input symbols is possible in face of erasures;

generating, with a dynamic encoder, a plurality of output symbols from a combined set of symbols including the input symbols and the redundant symbols, wherein a dynamic key generator generates a dynamic key for each output symbol to be generated, wherein the dynamic encoder receives each dynamic key, and wherein the dynamic encoder generates each output symbol based on the corresponding dynamic key, wherein the number of distinct dynamic keys that can be generated with the dynamic key generator is only limited by the key resolution, each output symbol having an associated weight representing the number of symbols from the combined set of symbols used to generate that output symbol, wherein the weights of the output symbols in the plurality of output symbols are distributed in a way to minimize the number of operations needed to regenerate the ordered set of input symbols, and wherein at least one output symbol is generated from more than one symbol in the combined set of symbols and from less than all of the symbols in the combined set of symbols; and

providing the output symbols to a transmit module for transmission over the erasure communications channel."

Claim 5 reads as follows:

"A system for multi-stage encoding data for transmission from a source to a destination over an erasure communications channel, the system comprising:

a static encoder coupled to receive an ordered set of input symbols, the ordered set of input symbols generated from data to be transmitted, the static encoder including a redundant symbol generator that generates a plurality of redundant symbols from the ordered set of input symbols, and wherein the static encoder is an encoder wherein the number of the redundant symbols is determined prior to encoding, and wherein the redundant symbols add redundant information in such a way that recovery of the ordered set of input symbols is possible in face of erasures; and

a dynamic encoder coupled to receive the ordered set of input symbols and the plurality of redundant symbols, the dynamic encoder including an output symbol generator that generates a plurality of output symbols from a combined set of symbols including the ordered set of input symbols and the plurality of redundant symbols, wherein a dynamic key generator generates a dynamic key for each output symbol to be generated, wherein the dynamic encoder receives each dynamic key, and wherein the dynamic encoder generates each output symbol based on the corresponding dynamic key, wherein the number of distinct dynamic keys that can be generated with the dynamic key generator is only limited by the key resolution, each output symbol having an associated weight representing the number of symbols from the combined set of symbols used to generate that output symbol, wherein the weights of the output symbols in the plurality of output symbols are distributed in a way to minimize the number of operations needed to regenerate the ordered set of input symbols, and wherein at least one output symbol is generated from more than one symbol in the combined set of symbols and from less than all of the symbols in the combined set of symbols; and

a transmit module, coupled to the dynamic encoder and to the erasure communications channel, that receives the output symbols and transmits the output symbols over the erasure communications channel."

IX. The appellant's arguments, where relevant to this decision, are discussed in detail below.

Reasons for the Decision

1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.

The invention

2. The application relates to multi-stage encoding and decoding of data transmitted over an erasure communications channel. The coding scheme of the invention accounts for errors and gaps in communicated data (data erasure and incompleteness), e.g. the recipient does not begin and end reception exactly when a transmission begins and ends (see title and paragraphs [01], [48], [52] and [61] of the original application).

In a first stage of encoding, a predetermined amount of redundancy is added to the data using "static encoding", thereby generating a combined set of symbols consisting of the original data and the redundant symbols. Examples of static encoding codes include Reed-Solomon codes, Tornado codes, Hamming codes and Low Density Parity Check (LDPC) codes (paragraphs [48] and [56]). In a second stage, using "dynamic encoding", a code, such as the "chain reaction code" described in document L1, is used to produce output symbols from the combined set of symbols. A "dynamic encoder" is an encoder in which the number of output symbols to be generated needs not be fixed and is only limited by the resolution of the dynamic keys used (paragraphs [57], [83] and [166]).

2.1 The static encoder receives as input a number K of input symbols, the original input symbols IS(0), IS(1),..., IS(K-1), a value R corresponding to the number of redundant symbols, and possibly static keys S0, S1,..., and generates redundant symbols RE(0),..., RE(R-1). Each redundant symbol is calculated as a function of the input symbols and the previously generated redundant symbols (paragraph [74], Figure 2; paragraphs [79] to [81], Figures 3 and 4).

2.2 The dynamic encoder receives the "dynamic input symbols", consisting of the input symbols and the redundant symbols, and a dynamic key Ij (I0, I1, I2,... in Figure 2) for each output symbol to be generated. It then generates one output symbol B(Ij) for each key Ij, where B(Ij) is a function of one or more of the input and redundant symbols. This set of "associated symbols" or "associates" is determined by the key Ij (paragraphs [67] and [83], Figures 1 and 2).

As explained in paragraphs [83] to [93] with reference to Figure 5, taking into account a dynamic key I and the number K+R of dynamic symbols, the dynamic encoder first generates, on the basis of the dynamic key I:

- a weight W(I), which is the number of associates of the output symbol to be generated,

- the list AL(I) of the W(I) positions of dynamic input symbols associated with the output symbol, preferably uniformly distributed in their range, and

- a value function F(I) used to calculate the output symbol B(I) on the basis of the symbols of AL(I), e.g. the XOR of the values of all associates.

The dynamic encoder then generates the output symbol B(I) for the dynamic key I by applying the value function F(I) to the associates indicated by the list AL(I). For example, if W(I)=3, AL(I)=0,2,K+R-2, and F(I) is the XOR function (circle plus), then B(I)=IS(0)(circle plus)IS(2)(circle plus)RE(R-2) (paragraph [93], Figure 6).

2.3 The decoder includes a dynamic decoder (paragraphs [118] to [127], Figure 15) and a static decoder (paragraphs [128] to [139], Figures 16 to 19), where the static decoder can be used to decode input symbols that the dynamic decoder did not recover (paragraph [109]).

2.4 The performance and efficiency of the encoder/decoder are dependent on the distribution of weights of the output symbols generated by the dynamic encoder. A weight distribution should be selected for the coding process so that an input file can be reconstructed as reliably as possible with as few output symbols and operations as possible. The application describes a methodology for determining distributions for near optimal performance (paragraphs [144] to [154]).

Clarity - Article 84 EPC

3. The objections of lack of clarity raised in the Board's communication have been overcome by amendment. In particular, the independent claims no longer refer to the number of output symbols being "independent of the number of input symbols encoding the data", but now specify that one output symbol is generated for each dynamic key from the input and redundant symbols and that the number of distinct dynamic keys that can be generated is only limited by the key resolution.

The Board is therefore satisfied that the claims comply with Article 84 EPC.

Added subject-matter - Articles 76(1) and 123(2) EPC

4. Claim 1 is directed to a decoder for decoding output symbols received over an erasure communications channel in which the output symbols represent multi-stage encoded data sent by one or more transmitters. These features are described in paragraphs [01], [52], [53], [61], [69] and [71] of the description and claim 45 of the parent application as filed (see international publication).

The claim text "wherein a dynamic key generator has generated ... wherein the redundant symbols are generated from the input symbols" of claim 1 specifies how each output symbol has been generated at the encoder from an ordered set of input symbols by static and dynamic encoding and in such a way as to minimise the number of operations needed to regenerate the ordered set of input symbols. The multi-stage encoding features of claim 1 are described in paragraphs [74] to [84] and [166] and Figures 1 and 2. The minimisation of the number of operations needed in the coding process is mentioned in paragraph [149] and described in more detail in paragraphs [148] to [154] of the parent application as filed. That the minimisation had a corresponding effect in the decoding process would have been recognised by the skilled person and is implied by the statement in paragraph [14].

Claim 1 describes the decoder as including a receiver input, a memory for storing received output symbols, a dynamic key regenerator, dynamic decoder logic and static decoder logic. The dynamic key regenerator is shown in Figure 1. The other features find an implicit basis in paragraphs [108] to [110] in combination with paragraph [169] and Figures 1 and 11 of the parent application. Paragraph [96] discloses that in the static encoding stage, the redundant information is added to the input data in such a way that recovery of the input data is possible in the face of erasures.

Therefore, claim 1 satisfies the requirements of Article 76(1) EPC.

5. The description of the present application as filed corresponds to the description and claims of the parent application as filed, and the drawings are the same as those of the parent application. Therefore, the subject-matter of claim 1 also finds a basis in the present application as originally filed (see also points 2. to 2.4 above).

Therefore, claim 1 fulfils the requirements of Article 123(2) EPC.

6. Claims 2 and 4 are directed to methods of multi-stage decoding and encoding, and claim 5 is directed to a system for multi-stage encoding. Each of these claims defines its subject-matter in terms of features substantially corresponding to those of claim 1. Claim 3 defines a computer-readable medium by reference to claim 2.

For analogous reasons to those given for claim 1, claims 2 to 5 thus also fulfil the requirements of Articles 76(1) and 123(2) EPC.

Inventive step - Articles 52(1) and 56 EPC

7. Document L1 describes "chain reaction coding", a method of encoding data for transmission from a source to a destination over an erasure communications channel (column 7, lines 21 to 24; column 7, line 44 to column 8, line 10; column 12, lines 17 to 40). As explained in the present application, the encoding method of L1 corresponds to the dynamic encoding of the present invention.

In the method of L1, the input symbols are first arranged into an ordered set of input symbols and then encoded into output symbols (column 11, lines 21 to 28; Figure 1). The number of output symbols is subject only to the resolution of the dynamic keys I (column 5, lines 9 to 14; column 26, lines 14 to 23; column 27, lines 21 to 26 and lines 50 to 51).

The keys may be generated randomly or pseudo-randomly (column 11, lines 42 to 47; column 27, lines 3 to 6), and each output symbol is generated from a number W(I) of input symbols called the "associates" of the output symbol having key I. The number of associates W(I) of an output symbol is the "weight" and is obtained for each output symbol by using its associated key I (column 13, lines 11 to 21).

Document L1 also discloses a decoder comprising a receiver module 150, a key regenerator 160 and dynamic decoder logic 155 (column 12, lines 1 to 51; Figure 1). The decoder receives output symbols from one or more transmitters (column 29, lines 39 to 63; Figure 24) and includes an output symbol buffer, which is a memory for storing output symbols received at the decoder (Figure 4; column 14, lines 58 to 63). The dynamic decoder logic decodes the received output symbols using their corresponding keys and recovers a set of symbols used in the creation of the received output symbols (column 12, lines 41 to 51).

7.1 However, document L1 does not disclose multi-stage coding. It describes optimisation of weight distributions (column 23, lines 30 to 46), but not in a context of multi-stage encoding. The encoding/decoding method of document L1 does not include the "static" encoding/decoding stage of the present invention.

Consequently, document L1 does not disclose that

(a) at the encoder, redundant symbols are generated from the input symbols using static encoding and the dynamic encoder obtains a combined set of symbols including the ordered set of input symbols and the redundant symbols for encoding;

(b) at the decoder, the recovered symbols consist of input and redundant symbols, and input symbols not decoded by the dynamic decoder logic are decoded from at least some of the redundant symbols;

(c) the weights of the output symbols are distributed in such a way as to minimise the number of operations needed to regenerate the ordered set of input symbols from the output symbols obtained from the multi-stage encoder; and

(d) the redundant symbols add redundant information in such a way that recovery of the ordered set of input symbols is possible in the face of erasures.

Distinguishing features (a), (c) and (d) are specified in all the claims. Claims 2 and 3 additionally include feature (b).

7.2 The appellant argued that by combining the static encoder with the dynamic encoder of L1 in the present invention, the average weights necessary to achieve a desired degree of accuracy were lower than those required for encoding only with the L1 encoder, resulting in a reduction of the number of symbols that had to be combined. This was explained on page 42, paragraph [154]. The advantages of lower average weights were reduced complexity of the implementation and improved encoding speed.

Paragraphs [148] to [154], which provide the basis for feature (c), describe how to select weight distributions to achieve near optimal performance. The purpose of the optimisation is to reduce the number of output symbols that have to be processed and the number of operations that have to be performed for a given error probability (page 35, paragraph [149] and page 42, paragraph [154]). On pages 38 to 42, the application gives examples of optimised weight distributions that can be used in the present invention, including the following table:

FORMULA/TABLE/GRAPHIC

Each table provides a list of weights and associated probabilities for a specific range of K (the number of input symbols), a static encoder overhead ß and a relative overhead alpha. The overheads ß and alpha determine the number of redundant symbols R as the smallest integer greater or equal to ß*K and the number of output symbols collected A as the smallest integer greater or equal to alpha*K (paragraph [150]). The error probability for these examples is less than 10**(-12) for K > 49251 and 10**(-10) otherwise (page 38, paragraph [154]). According to the passage cited by the appellant on page 42, the average weights for these weight distributions (around 6.75 for Table 1 and around 6 for Tables 2 to 9) are significantly lower than the average weight of 26.86 (for K = 60000) achieved by the weight distribution used in the prior-art L1 encoder. This means that, on average, the number of associated symbols for one output symbol is lower for the weight distributions of Tables 1 to 9 of the present application than for those disclosed in document L1.

Taking into account these results, the Board is persuaded that, in spite of the overhead caused by the extra steps of static encoding, the distinguishing features result in an efficient alternative implementation of the encoding and decoding methods of document L1 to be used in an erasure communications channel. Since the overhead of static encoding is fixed, the advantage is greater when more output symbols are generated.

7.3 At the priority date of the present application, concatenated-encoding schemes were widely known and adding a pre-coding stage to known encoding schemes was common practice (see DA1, sections 8.1 and 8.1.1, Figure 8.1; DA4, abstract). As can be derived from documents DA1 and DA4, it was known that such a technique could be used in some cases to reduce complexity compared to that required to provide the same overall error rate with a single level of coding (DA1, page 333, third to fifth lines), or to improve the performance of the decoder (document DA4, abstract). In its communication, the Board suggested that the combination of a pre-coding stage to the prior-art encoding of L1 would have been obvious for the skilled person.

However, the present claims do not define an arbitrary combination of the two encoding schemes but a particular advantageous manner of combining static encoding with L1 encoding by features (c) and (d), which are not known from the state of the art. None of the cited prior-art documents describes pre-coding, or multi-stage encoding, in the context of erasure channels, as defined in feature (d). As explained above, the addition to the dynamic encoder of the static encoder and feature (c) results in an unexpectedly optimised implementation of the dynamic-encoding phase.

In the Board's opinion, the skilled person would not have anticipated that such a further optimisation of the L1 encoding scheme for erasure channels could be achieved by adding a static encoder, as a first-stage encoder, and features (c) and (d) to the L1 encoder. It would hence not have been obvious for the skilled person to adapt the coding scheme of document L1 in the particular manner described by distinguishing features (a), (c) and (d).

The reduced average weight brings about an advantage not only in the coding but also in the decoding phase (see also paragraph [14]).

7.4 Therefore, the subject-matter of claims 1 to 5 is inventive within the meaning of Article 56 EPC.

Double patenting - divisional T 653/14

8. In decision T 653/14 of 13 March 2019, which concerns a further divisional application of the present application's parent application No. 02794439.6, the Board decided to remit the case to the department of first instance with the order to grant a patent. The claims of the present application are distinct in scope from those of T 653/14 and therefore no objection of double patenting arises.

Conclusion

9. The claims satisfy the requirements of the EPC and the description has been adapted accordingly. The case is therefore to be remitted for grant on the basis of the documents according to the sole substantive 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:

- Claims: claims 1 to 5 of the amended set of claims labelled "ANNEX A''c" as filed in the oral proceedings at 14:00 hours;

- Description: pages 1 to 6 and 8 to 44 as originally filed, pages 7 and 45 as filed in the oral proceedings;

- Drawings: Figures 1 to 22 as originally filed.