T 2272/15 (Multi-stage coding I/QUALCOMM) of 18.2.2019

Summary of Facts and Submissions

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

II. In the decision under appeal, the following document was cited:

D6: Hasan, M., Bhargava, V.K.: "Architecture For a Low Complexity Rate-Adaptive Reed-Solomon Encoder", IEEE Transactions on Computers, Vol. 44, No. 7, pages 938 to 942, July 1995.

The Examining Division considered a main request and first to fifth auxiliary requests and ruled that:

- the main request was not allowable for insufficiency of disclosure, lack of clarity and lack of novelty over document D6;

- the first auxiliary request was not allowable for lack of clarity and lack of novelty;

- the second and third auxiliary requests were not allowable for insufficiency of disclosure and lack of clarity;

- the fourth and fifth auxiliary requests were not admitted into the proceedings.

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 of one of the first to third auxiliary requests considered by the decision under appeal or on the basis of a new fourth auxiliary request. The main and first to fourth auxiliary requests were submitted as annexes A to E of the statement of grounds of appeal.

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 the summons to oral proceedings, the Board referred, inter alia, to the following documents previously cited in the first-instance proceedings:

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;

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

In addition, the Board introduced documents C1 to C4 (not cited in this decision) illustrating the common general knowledge and/or common practice at the date of priority of the present application.

The Board informed the appellant that even though the decision under appeal did not deal with the question of inventive step, for procedural efficiency the Board was inclined to also assess this issue.

The Board raised objections under Articles 83, 84 and 123(2) EPC against claim 1 of the main request and first and second auxiliary requests, and under Articles 84 and 123(2) EPC against claim 1 of the third auxiliary request.

The Board expressed the preliminary opinion that the subject-matter of claim 1 of the main request, as far as it could be understood, was not inventive over the dynamic encoding method of document L1 in combination with the common practice of adding a pre-coding stage to known encoding schemes as illustrated by documents DA1, DA4 and C1 to C4. Claim 1 of the auxiliary requests also lacked inventive step over that prior art.

VI. With a letter of reply dated 19 January 2019, the appellant submitted amended versions of the main and first to fourth auxiliary requests as annexes A' to E'. With a further letter dated 21 January 2019, the appellant amended the claims of annex B'.

VII. Oral proceedings were held on 18 February 2019. During the oral proceedings, the appellant filed two amended versions "revised 1" and "revised 2" of some of the claims of the fourth auxiliary request. It later withdrew its requests corresponding to annexes A to E, and the "revised 2" claims. At the end of the oral proceedings, the chairman pronounced the Board's decision.

VIII. The appellant's final requests were that the contested decision be set aside and that a patent be granted on the basis of one of the following requests:

- main request filed as annex A' with the letter of 19 January 2019,

- first auxiliary request filed as annex B' with the letter of 21 January 2019,

- second auxiliary request filed as annex C' with the letter of 19 January 2019,

- third auxiliary request filed as annex D' with the letter of 19 January 2019,

- fourth auxiliary request filed as annex E' with the letter of 19 January 2019, or

- amended fourth auxiliary request including claims 1 and 2 submitted at the oral proceedings before the Board as claims 1 and 26 of the amended fourth auxiliary request labelled "revised 1".

IX. Claim 1 of the main request filed as annex A' reads as follows:

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

arranging data to be transmitted into an ordered set of input symbols;

generating a plurality of redundant symbols from the input symbols using a static encoder, wherein the static encoder is an encoder wherein the number of the redundant symbols is determined prior to encoding; and

generating a plurality of output symbols from a combined set of symbols that includes the input symbols and the redundant symbols, wherein the number of possible output symbols that can be generated from a given set of input symbols is independent of the number of input symbols, wherein at least one output symbol of the plurality of output symbols 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 wherein the plurality of output symbols are generated with sufficient information content needed to regenerate the ordered set of input symbols to a desired degree of accuracy from N of the output symbols that are determined to be possible output symbols."

X. Claim 1 of the first auxiliary request according to annex B' differs from that of annex A' in that the part of the claim starting with the text "and wherein the plurality of output symbols" has been deleted.

XI. Claim 1 of the second auxiliary request according to annex C' differs from that of annex A' in that at the end of the claim "to a desired degree of accuracy from N of the output symbols that are determined to be possible output symbols" has been replaced with the following text:

"to a desired degree of accuracy in the number of input symbols regenerated from N of the output symbols that are determined to be possible output symbols".

XII. Claim 1 of the third auxiliary request according to annex D' differs from that of annex A' in that the part of the claim starting with "wherein the number of possible output symbols" has been replaced with the following text:

"wherein each of the plurality of output symbols is generated according to a key, the key being an identifier associated with the output symbol being generated, such that the number of output symbols that could be generated corresponds to the number of distinct keys and the number of distinct keys being independent of the number of input symbols, wherein at least one output symbol of the plurality of output symbols 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 wherein the plurality of output symbols are generated with sufficient information content needed to regenerate the ordered set of input symbols to a desired degree of accuracy in the number of input symbols regenerated from N of the output symbols that are determined to be possible output symbols, wherein the desired degree of accuracy ranges from complete recovery to less than complete recovery according to an input constraint."

XIII. Claim 1 of the fourth auxiliary request according to annex E' reads as follows:

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

arranging data to be transmitted into an ordered set of input symbols;

generating a plurality of redundant symbols from the input symbols using a static encoder, wherein the static encoder is an encoder wherein the number of the redundant symbols is determined prior to encoding;

generating a plurality of dynamic keys, wherein the number of distinct dynamic keys is determined by a key resolution that is unconstrained by the number of symbols in the ordered set of input symbols; and

generating a plurality of output symbols from a combined set of symbols that includes the input symbols and the redundant symbols, each output symbol of the plurality of output symbols having a dynamic key of the plurality of dynamic keys and each output symbol generated as an XOR of associated symbols, the associated symbols for a given output symbol being selected from the combined set of symbols based on the dynamic key for that given output symbol,

wherein at least one output symbol of the plurality of output symbols is generated as an XOR of more than one symbol in the combined set of symbols and of less than all of the symbols in the combined set of symbols."

XIV. Claim 1 of the amended fourth auxiliary request according to the "revised 1" annex differs from that of annex E' in that the part of the claim starting with "generating a plurality of dynamic keys" has been replaced with the following text:

"generating a plurality of dynamic keys with a dynamic key generator, wherein the number of distinct dynamic keys that can be generated is only limited by a key resolution; and

generating a plurality of output symbols with a dynamic encoder from a combined set of symbols that includes the input symbols and the redundant symbols, wherein the 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 of the plurality of dynamic keys and each output symbol generated as an XOR of associated symbols, the associated symbols for a given output symbol being selected from the combined set of symbols based on the dynamic key for that given output symbol,

wherein at least one output symbol of the plurality of output symbols is generated as an XOR of more than one symbol in the combined set of symbols and of less than all of the symbols in the combined set of symbols."

XV. 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 in communication systems to account for errors and gaps in communicated data (data erasure and incompleteness), e.g. because 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 international publication).

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 or 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. The description defines a "dynamic encoder" as an encoder in which "the number of possible output symbols is orders of magnitude larger than the number of input symbols" and 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], [84] and [166]).

2.1 A multi-stage encoder according to the invention is illustrated in Figure 2 of the application shown below. It includes the static encoder 210 and the dynamic encoder 220 (Figures 1 and 2, paragraphs [65] to [67]).

FORMULA/TABLE/GRAPHIC

Figure 2

2.1.1 The static encoder 210 receives as input the 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 RE(j) is calculated as a function Fj of the input symbols and of the previously generated redundant symbols (paragraph [74], Figure 2; paragraphs [79] to [81], Figures 3 and 4).

2.1.2 The dynamic encoder 220 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 (paragraph [67], paragraph [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 dynamic key I by applying 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.2 Optimisation of the coding process requires the right choice of the number of redundant symbols R (paragraph [96]), the distribution of weights W(I) over all keys I, and the distribution of associates over the output symbols, i.e. the memberships of AL(I) over all I (paragraphs [144] and [154]).

Main request - Annex A'

3. Clarity and support - claim 1

3.1 Claim 1 defines a method of encoding comprising a step of generating a plurality of redundant symbols from input symbols by static encoding and a step of generating a plurality of output symbols from a combined set of the input and redundant symbols, where one output symbol is generated from more than one and less than all combined symbols. It further specifies that

(a) "the number of possible output symbols that can be generated [...] is independent of the number of input symbols" and

(b) the output symbols are generated with sufficient information content needed to regenerate the ordered set of input symbols "to a desired degree of accuracy from N of the output symbols that are determined to be possible output symbols".

These two features are not clearly defined.

3.2 In feature (b), it is unclear what it means technically to determine output symbols to be possible output symbols.

3.3 Following one possible interpretation of both features, the expressions "possible", "can be generated" and "determined to be possible" do not refer to concrete features of the method but to hypothetical features.

In this case, the phrases "number of possible output symbols that can be generated" and "the output symbols that are determined to be possible output symbols" do not impose a clear limitation since they do not describe what the method does but what could hypothetically be done. From the other features of the claim, the skilled reader understands that the output symbols are to be generated with sufficient information content for regenerating the input symbols to a desired degree of accuracy from N symbols, but not from which N input symbols, nor what N is, which again renders the scope of the claim unclear (Article 84 EPC).

3.4 Feature (a) can also be interpreted as characterising the number of output symbols that are actually generated as being "independent of the number of input symbols".

However, in the invention as described in the present application, the number of output symbols generated by the method is not independent of the number of input symbols. For a given number K+R of input and redundant symbols, the number of dynamic keys has to be at least large enough to produce a number K+A of output symbols, where K+A is the number of output symbols needed to achieve a desired degree of accuracy (paragraph [111]). A dependency thus exists, for a desired degree of accuracy, between the "number of possible output symbols that can be generated" and the number of input symbols. The claimed method is thus not supported by the description (Article 84 EPC).

3.5 The appellant submitted that the term "independent" would have been understood by the skilled person. Just as noted in the Board's communication, "the number of dynamic keys has to be at least large enough to produce the number of output symbols needed to achieve the desired degree of accuracy". There was, however, no "static" relationship between the number of input and output symbols of the encoder. The claim, the appellant argued, would have been clear when construed by a mind willing to understand.

However, for the reasons given above, the "number of possible output symbols that can be generated" is not independent of the number of input symbols, even if the dependency is not static. The matter for which protection is sought has to be clear from the wording of the claim alone. This is not the case here.

3.6 Therefore, claim 1 of the main request does not satisfy the requirements of Article 84 EPC for lack of clarity and lack of support by the description.

First to third auxiliary requests - Annexes B' to D'

4. Clarity and support - claim 1

4.1 Claim 1 of the first auxiliary request differs from that of the main request essentially in that the description of the plurality of output symbols according to feature (b) is deleted.

Claim 1 of the second auxiliary request further explains, compared with claim 1 of the main request, that the degree of accuracy is "in the number of input symbols regenerated" from N of the output symbols but does not improve the unclear phrase "that are determined to be possible output symbols" of feature (b).

Therefore, claim 1 of the first and second auxiliary requests also define feature (a) without further clarifying it. The objections under Article 84 EPC given above with regard to feature (a) thus equally apply to claim 1 of the first and second auxiliary requests.

4.2 Claim 1 of the third auxiliary request differs from that of the main request in that it specifies that the desired degree of accuracy is "in the number of input symbols regenerated" from N of the output symbols and ranges from complete recovery to less than complete recovery according to an input constraint, and in that feature (a) was amended to:

(a') each of the plurality of output symbols is generated according to a key, the key being an identifier associated with the output symbol being generated, such that the number of output symbols that could be generated corresponds to the number of distinct keys and the number of distinct keys being independent of the number of input symbols.

These amendments do not overcome the objections under Article 84 EPC mentioned above. The phrase "the number of output symbols that could be generated corresponds to the number of distinct keys and the number of distinct keys being independent of the number of input symbols" in feature (a') mentions what could be done, not what is done in the method. It hence still defines a hypothetical feature, not a concrete feature of the claimed method. The claim still specifies that "the number of output symbols is "independent of the number of input symbols" and refers to the unclear phrase "output symbols that are determined to be possible output symbols" of feature (b), without clearly specifying which output symbols are actually generated.

4.3 Therefore, claim 1 of the first, second and third auxiliary requests do not satisfy the requirements of Article 84 EPC.

Fourth auxiliary request - Annex E'

5. Claim 1 of the fourth auxiliary request filed as Annex E' defines a method of encoding data for transmission from a source to a destination over a communications channel, the method comprising (features itemised by the Board):

(c) arranging data to be transmitted into an ordered set of input symbols;

(d) generating a plurality of redundant symbols from the input symbols using a static encoder, wherein the static encoder is an encoder wherein the number of the redundant symbols is determined prior to encoding;

(e) generating a plurality of dynamic keys, wherein the number of distinct dynamic keys is determined by a key resolution that is unconstrained by the number of symbols in the ordered set of input symbols; and

(f) generating a plurality of output symbols

(f1) from a combined set of symbols that includes the input symbols and the redundant symbols,

(f2) each output symbol of the plurality of output symbols having a dynamic key of the plurality of dynamic keys and each output symbol generated as an XOR of associated symbols,

(f3) the associated symbols for a given output symbol being selected from the combined set of symbols based on the dynamic key for that given output symbol,

(f4) wherein at least one output symbol of the plurality of output symbols is generated as an XOR of more than one symbol in the combined set of symbols and of less than all of the symbols in the combined set of symbols.

6. Inventive step - claim 1

6.1 Document L1 describes a method of encoding data for transmission from a source to a destination over a communications channel, which is denoted as "chain reaction coding" (column 7, lines 21 to 24). This encoding corresponds to the dynamic encoding of the present application (paragraph [84] of the international publication).

In the encoding 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). One output symbol is generated for each key I (column 5, lines 2 to 9), where keys I of document L1 correspond to the "dynamic keys" of the present invention. The number of output symbols is said to be "unbounded" or "indeterminate", limited only by the resolution of the 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). These features correspond to the claim features "the number of distinct dynamic keys is determined by a key resolution that is unconstrained by the number of symbols in the ordered set of input symbols" interpreted in light of the description of the present application (see also point 2 above). Therefore, document L1 discloses features (c) and (e) of claim 1.

The output symbols are generated as described in features (f) and (f2) to (f4), except that the combined set of symbols in the claimed method also includes redundant symbols (see e.g. column 11, lines 48 to 59; column 13, lines 5 to 31, of L1).

6.2 The subject-matter of claim 1 thus differs from the dynamic encoding method of document L1 in that redundant symbols are generated from the original input symbols and the dynamic encoder obtains a combination of the original input symbols and the redundant symbols for encoding (features (d), (f1) and the combined set of symbols in (f3) and (f4)).

6.3 At the priority date of the present application, it was common practice to add an outer coding or pre-coding stage to known encoding schemes (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 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). Reed-Solomon codes are disclosed as the most natural choice for outer codes (DA1, page 333, first three paragraphs). As another example, it was common practice to add redundant symbols in the form of checksum data to input data in advance of encoding.

It would therefore have been a matter of common practice for the skilled person to add a pre-coding stage to a known encoder, for example, by passing to the known encoder the combination of source input symbols and redundant symbols generated by the pre-coding stage.

In its letter, the appellant argued that when starting from the dynamic encoder L1, the skilled person would not have considered the prior-art documents, which all deal with static encoders. The Board notes however that those documents, especially DA1, generally teach the usefulness of multi-stage encoding for different types of encoders.

The Board sees no reason why the skilled person would not have considered adding a static encoder to the dynamic encoder L1. Combining the two schemes in the way claimed does not pose specific technical difficulties. In the method of claim 1, static encoding is merely added to the known dynamic encoding scheme in a conventional way by passing to the known dynamic encoder the input symbols and the redundant symbols generated by the static encoder.

6.4 An inventive step of the combination of the L1 encoder with a known static encoder could only be derived from a particular advantage achieved by that combination that would not have been immediately foreseen by the skilled person.

At the oral proceedings, the appellant argued that by combining the static encoder with the dynamic encoder of L1, 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.

The Board is, however, not persuaded that claim 1 of the fourth auxiliary request defines the features necessary to establish such an effect. Claim 1 does not mention weight distributions. It therefore covers a multi-stage encoding method using the same weight distributions as used in the prior-art dynamic encoding L1.

Therefore, the combination of the known static and dynamic encoders in the way claimed does not result in any surprising effect.

6.5 Thus, the subject-matter of claim 1 of the fourth auxiliary request according to Annex E' does not involve an inventive step (Article 56 EPC).

Amended fourth auxiliary request "revised 1"

7. The amendments introduced by claim 1 of the amended fourth auxiliary request "revised 1" do not significantly change the claimed subject-matter. Compared to claim 1 of Annex E', claim 1 of the "revised 1" request additionally mentions a dynamic encoder and a dynamic key generator.

8. Inventive step - claim 1

8.1 Since the method of encoding data of document L1 uses a dynamic encoder and a dynamic key generator in the same way as the dynamic encoding phase described in claim 1 (see e.g. column 11, lines 48 to 59, column 13, lines 5 to 31, and Figure 1), the distinguishing features are the same as those established for the fourth auxiliary request under point 6.2 above. The reasoning given above for claim 1 of the fourth auxiliary request Annex E' thus equally applies to the present claim 1 of the "revised 1" request.

8.2 Therefore, claim 1 of the amended fourth auxiliary request "revised 1" does not fulfil the requirements of Article 52(1) EPC for lack of inventive step within the meaning of Article 56 EPC.

Conclusion

9. Since claim 1 of the main and first to third auxiliary requests according to annexes A', B', C' and D' do not satisfy the requirements of Article 84 EPC, and claim 1 of the fourth auxiliary request according to annex E' and of the amended fourth auxiliary request "revised 1" do not comply with Articles 52(1) and 56 EPC, none of the requests on file is allowable. The appeal is hence to be dismissed.

Order

For these reasons it is decided that:

The appeal is dismissed.