T 0653/14 (Multi-stage coding III/QUALCOMM) of 13.3.2019

Summary of Facts and Submissions

I. The appeal lies from the decision of the Examining Division to refuse European patent application No. 10013231.5, 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 following documents were cited:

D1: Mandelbaum, D. M., "An Adaptive-Feedback Coding Scheme Using Incremental Redundancy", IEEE Transactions on Information Theory, pages 388 and 389, IEEE Press, USA, May 1974;

D2: Lee, L. H. C., "Error-Control Block Codes for Communications Engineers", Chapter 3 "Linear Block Codes", pages 39 to 45, ARTECH HOUSE, Boston, MA, USA, 2000;

D3: Luby, M. G., et al.: "Efficient Erasure Correcting Codes", IEEE Transactions on Information Theory, Vol. 47, No. 2, pages 569 to 584, IEEE Press, USA, February 2001.

The Examining Division found that the subject-matter of claim 1 of the then sole request was not new over the disclosure of document D1 or not inventive if claim 1 was interpreted as defining two program-code means for the dynamic encoder. The subject-matter of claim 1 also lacked inventive step over documents D2 and D3. The same applied, mutatis mutandis, to independent claims 7 and 13. Also the subject-matter of independent claim 9 was not inventive over any of the documents D1, D2 or D3.

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, as main request, the set of claims refused in the decision under appeal and resubmitted with the grounds of appeal as annex A, or, as auxiliary request, the set of claims submitted with the grounds of appeal as annex B.

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.

The Board was of the preliminary view that claim 1 of both the main request and the auxiliary request did not fulfil the requirements of Article 84 EPC. With regard to novelty and inventive step, the contested decision's reasoning seemed to be based on a particular interpretation of claim 1 which did not seem to be supported by the description. The disclosure of document L1 seemed closer to the invention than the prior art cited in the decision under appeal. The Board expressed the preliminary opinion that the subject-matter of claim 1 of the main request and the auxiliary request was not inventive over document L1.

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

VII. Oral proceedings were held on 13 March 2019. During 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.

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 13 of the revised further amended set of claims labelled "ANNEX A''rev." as filed in the oral proceedings;

- Description: pages 1 to 5 and 8 to 44 as originally filed, and pages 6, 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''rev." reads as follows:

"A computer-readable medium for use with electronics capable of executing instructions read from the computer-readable medium in order to implement multi-stage encoding data for transmission from a source to a destination over an erasure communications channel, the computer-readable medium having stored thereon:

program code for generating, using static encoding, a plurality of redundant symbols from an ordered set of input symbols representing the data to be encoded for transmission, and wherein the 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; and

program code for generating, with a dynamic encoder, a plurality of output symbols derived 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, wherein the sequence of dynamic keys is randomly or pseudorandomly generated, and 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, 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."

Claims 2 to 7 are dependent upon claim 1.

Claim 8 differs from claim 1 in that, apart from a minor typographical error in "pseudorandomly generated,,", the text up to "wherein a dynamic key generator generates a dynamic key for each output symbol" 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 a plurality of input symbols, the plurality of input symbols generated from data to be transmitted, the static encoder including a redundant symbol generator that generates a plurality of redundant symbols based on the 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 plurality 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 plurality of input symbols and the plurality of redundant symbols,".

Claim 9 differs from claim 1 in that, apart from a change of a comma to a semicolon in "pseudorandomly generated;", the text up to "wherein a dynamic key generator generates a dynamic key for each output symbol" reads as follows:

"A method of employing two or more stages of multi-stage encoding to encode data for transmission from a transmitter to at least one receiver over an erasure communication channel, the method comprising:

generating, using static encoding, during a first encoding stage, a plurality of redundant symbols from an ordered set of input symbols representing the data to be encoded for transmission, 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, during a second encoding stage with a dynamic encoder, a set of output symbols derived from a combination of the plurality of redundant symbols and the ordered set of input symbols,".

Claim 10 reads as follows:

"A computer-readable medium for use with electronics capable of executing instructions read from the computer-readable medium in order to implement receiving multi-stage encoded data transmitted from a source over an erasure communications channel, the computer-readable medium having stored thereon:

program code for receiving output symbols transmitted over the communications channel, wherein a dynamic key generator has generated a dynamic key for each output symbol to be generated, wherein a dynamic encoder has received each dynamic key, and wherein each output symbol is generated by the dynamic encoder 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, 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 sequence of dynamic keys is randomly or pseudorandomly generated;

program code for decoding, 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; and

program code for 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."

Claims 11 to 13 are dependent upon claim 10.

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) which occur, for instance, when 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 need 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 specify that "there is no upper or lower bound on the number of output symbols", 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.

Furthermore, the independent claims are now limited to multi-stage encoding using static encoding at the first stage.

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 computer-readable medium for use with electronics capable of executing instructions read from the computer-readable medium in order to implement multi-stage encoding data for transmission from a source to a destination over an erasure communications channel. The features relating to the computer-readable medium can be derived from paragraph [169] of the parent application as filed and published, according to which the encoder and decoder blocks can be implemented by a combination of software and/or hardware. The other features are disclosed in paragraphs [01], [52], [53], [61], [69] and [71] of the description and in original claim 27 of the parent application.

The multi-stage encoding features of claim 1 are described in paragraphs [74] to [84] and [166] and in Figures 1 and 2. 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 face of erasures. The distribution of the weights in order to minimise the number of operations is mentioned in paragraph [149] and described in more detail in paragraphs [148] to [154] of the parent application as filed.

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) and complies with Article 123(2) EPC.

6. Claims 8 and 9 are directed to a system for multi-stage encoding and a method of employing two or more stages of multi-stage encoding to encode data for transmission, and they define the subject-matter in terms of features essentially corresponding to those of claim 1.

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

7. Claim 10 is directed to a computer-readable medium with instructions to receive multi-stage encoded data. It specifies subject-matter corresponding to that of claim 1 and decoder features describing program code of the decoder for decoding a subset of symbols from received output symbols and program code for decoding, using static decoding, at least some undecoded input symbols. The decoder features of claim 10 are disclosed in claim 45 and paragraphs [108] to [110] in combination with paragraph [169] of the parent application as filed, and in the corresponding passages of the present application.

Therefore, claim 10 fulfils the requirements of Articles 76(1) and 123(2) EPC.

8. Dependent claims 2 to 6 are based on claims 2 and 32 to 35 of the parent application as filed.

The features of claim 7 find a basis in paragraph [111] of the parent application as filed.

Dependent claims 11 to 13 are based on claims 46 to 49 and paragraphs [128] to [139] of the parent application as originally filed, and on the corresponding passages of the present application as filed (see also point 2.3 above).

Therefore, dependent claims 2 to 7 and 11 to 13 comply with Articles 76(1) and 123(2) EPC.

Inventive step - Articles 52(1) and 56 EPC

9. None of the prior-art documents D1, D2 and D3 cited in the decision under appeal discloses multi-stage coding or a coding scheme similar to that of the present invention. Document D1 discloses an adaptive-feedback coding scheme using incremental redundancy, document D2 discloses conventional linear block codes, and document D3 concerns an erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs. Therefore, these documents are not relevant for the inventive-step assessment.

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

10.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 included in all the independent claims. Independent claim 10 further specifies feature (b).

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

10.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 combined with 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]).

10.4 Therefore, the subject-matter of independent claims 1 and 8 to 10, and consequently that of dependent claims 2 to 7 and 11 to 13, is inventive within the meaning of Article 56 EPC.

Conclusion

11. 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 13 of the revised further amended set of claims labelled "ANNEX A''rev." as filed in the oral proceedings;

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

- Drawings: Figures 1 to 22 as originally filed.