T 1563/05 () of 3.9.2008

Summary of Facts and Submissions

I. The applicant appealed against the decision of the examining division to refuse the European patent application No. 02 007 488.6.

II. The present application is a divisional application divided from earlier Euro-PCT application 99 949 717.5 which was published as international publication number WO 00/18017 A1 (hereinafter the "parent").

III. In the contested decision, the examining division essentially held that claim 1 of all three requests then on file lacked an inventive step over the prior oral disclosure, in the early afternoon session on 2 September 1998 at the SIGCOMM'98 Conference in Vancouver, of the content of the later published document:

Dl: J. Byers, M. Luby et al. "A Digital Fountain approach to Reliable Distribution of Bulk Data", ACM SIGCOMM´98, Vancouver, 2-4 Sept. 1998, Computer Communications Review, Association for Computing Machinery, New-York (US), October 1998, vol. 28, Nr. 4, pages 56 to 67,

and that the subject-matter of claim 1 of all three requests had been extended over the content of the earlier application 99 949 717.5 as originally filed, Article 76(1) EPC.

The examining division added various further remarks, applicable to all requests, including inter alia that:

- the remaining independent claims 18, 28, 37 and 53 gave rise to objections under Articles 56 and 76(1);

- claim 37 lacked novelty Article 54 EPC; and

- claim 48 was not clear.

IV. Oral proceedings were held before the Board on 3 September 2008. The appellant requested that the decision under appeal be set aside and that a patent be granted in the following version:

Description:

- Pages 1 to 5, 8, 9 and 11 to 49 as originally filed;

- Pages 6, 6a, 7, 10 and 10a received during the oral proceedings of 3 September 2008;

Claims:

- Nos. 1 and 2 received during the oral proceedings of 3 September 2008;

Drawings:

- Sheets 1/18 to 18/18 as originally filed.

V. Claim 1 reads as follows:

"A method of transmitting data from a source to a destination over a packet communication channel, the method comprising:

a) arranging the data to be transmitted into an ordered set of input symbols representing an input file, wherein each of the input symbols is a symbol from an input alphabet and each of the input symbols represents a sequence of bits at a particular position in the input file;

b) selecting keys I from a key alphabet, wherein the key alphabet is such that the number of possible keys in the key alphabet is much larger than the number of input symbols in the ordered set of input symbols such that an effectively unbounded number of output symbols that are generally independent of each other can be generated;

c) generating a plurality of output symbols from the input symbols, wherein each output symbol is generated by the steps of:

i) selecting, from the key alphabet, a key I for the output symbol being generated;

ii) determining, according to a predetermined function of I, a list AL(i) that indicates W(i) associated input symbols to be associated with the output symbol, wherein weights W are positive integers that vary over the plurality of keys and are greater than one for at least some keys in the key alphabet; and

iii) generating an output symbol value B(i) from a predetermined function of the W(i) associated input symbols indicated by AL(i), wherein B(i) is a value from an output alphabet;

d) packetizing the plurality of output symbols into a plurality of packets; and

e) transmitting the plurality of packets over the packet communication channel, such that a recipient can decode the input file from a number of output symbols equal to, or slightly greater than, the number of input symbols representing the input file, assuming that input symbols and output symbols represent the same number of bits of data."

VI. Claim 2 reads as follows (the changes with respect to claim 1 have been underlined by the Board):

"A system of transmitting data from a source to a destination over a packet communication channel, the system comprising:

a) means for arranging the data to be transmitted into an ordered set of input symbols representing an input file, wherein each of the input symbols is a symbol from an input alphabet and each of the input symbols represents a sequence of bits at a particular position in the input file;

b) means for selecting keys I from a key alphabet, wherein the key alphabet is such that the number of possible keys in the key alphabet is much larger than the number of input symbols in the ordered set of input symbols such that an effectively unbounded number of output symbols that are generally independent of each other can be generated;

c) means for generating a plurality of output symbols from the input symbols, wherein each output symbol is generated by the steps of:

i) selecting, from the key alphabet, a key I for the output symbol being generated;

ii) determining, according to a predetermined function of I, a list AL(i) that indicates W(i) associated input symbols to be associated with the output symbol, wherein weights W are positive integers that vary over the plurality of keys and are greater than one for at least some keys in the key alphabet; and

iii) generating an output symbol value B(i) from a predetermined function of the W(i) associated input symbols indicated by AL(i), wherein B(i) is a value from an output alphabet;

d) means for packetizing the plurality of output symbols into a plurality of packets; and

e) means for transmitting the plurality of packets over the packet communication channel, such that a recipient can decode the input file from a number of output symbols equal to, or slightly greater than, the number of input symbols representing the input file, assuming that input symbols and output symbols represent the same number of bits of data."

VII. The arguments of the appellant can be summarised as follows. In the present invention, an effectively unbounded number of output symbols could be generated which effectively overcame some of the shortcomings of Tornado codes, which were the subject of D1. With Tornado codes, the number of output symbols was fixed by the number of input symbols divided by a code rate that was fixed by the graph being used to generate the particular Tornado code.

Reasons for the Decision

1. The appeal is admissible.

Admissibility of the amendments

2. The Board is satisfied that the claims and the description according to the current request meet the requirements of Article 84 EPC and do not contravene Article 76(1) EPC or Article 123(2) EPC.

2.1 Independent claim 1 is directed to a method of transmitting data from a source to a destination over a communication channel. It is based to a large extent on independent claim 19 as filed for the parent, the text of which was repeated in the description of the present application as filed (see paragraph [0028] of the published application, EP 1 241 795 A2).

2.2 The changes made with respect to parent claim 19 are considered to have been disclosed in the original filings of the parent and divisional application as detailed below (page and line references refer to the published parent application WO 00/18017; paragraph references in square brackets refer to the published divisional application EP 1 241 795 A2).

2.2.1 The additional feature of the "ordered set of input symbols representing an input file" was disclosed at page 12, lines 7 to 10 of the parent and in paragraph [0035] of the divisional.

2.2.2 The additional feature of "each input symbol comprising a sequence of bits" has a basis from page 12, lines 16 and 17, of the parent and paragraph [0036] of the divisional.

2.2.3 Considering feature b), the step of selecting keys from a key alphabet was outlined in feature b)1) of parent claim 19 and the further definition that "the number of possible keys in the key alphabet is much larger than the number of input symbols in the ordered set of input symbols" was set out in parent claim 1. The expression "much larger" has been qualified by the statement "such that an effectively unbounded number of output symbols that are generally independent of each other can be generated" which originates from page 6, lines 28 to 30 and page 7, lines 24 to 27 of the parent and paragraphs [0020] and [0023] of the divisional. The Board considers this qualification adequately clear in the present context.

2.2.4 Feature c)ii) has a basis in features b)2) and b)3) of parent claim 19 and in lines 8 to 12 of parent claim 1. The removal of the phrase "between at least two values" does not introduce fresh subject-matter because an integer that varies must necessarily vary "between at least two values". Hence the variation "between at least two values" is implicit from the remaining wording.

2.2.5 Feature c)iii) has a basis in lines 13 and 14 of parent claim 1 and feature b) of parent claim 19.

2.2.6 Feature d) has a basis in feature c) of parent claim 19. The amendment to the wording serves to remove the interpretation, possible from the original wording, that one of the plurality of output symbols is packetized into every packet, an interpretation which is not supported by the description.

2.2.7 In feature e), the feature "such that a recipient can decode the input file from a number of output symbols equal to, or slightly greater than, the number of input symbols representing the input file, assuming that input symbols and output symbols represent the same number of bits of data" was not specified in the corresponding feature d) of parent claim 19. This additional feature originates from page 7, lines 3 to 6 of the parent and paragraph [0021] of the divisional.

2.3 Independent claim 2 defines a system which corresponds to the method of claim 1 and hence has the same basis in the parent and divisional applications as filed.

2.4 The description has been amended for conformity with the claims and to acknowledge the disclosure at the ACM SIGCOMM '98 conference. No fresh subject-matter has been added by these amendments.

Novelty and Inventive Step

3. The Board considers that the subject-matter of present claims 1 and 2 is novel and involves an inventive step within the meaning of Articles 54 and 56 EPC.

3.1 The disclosure which is most relevant to the subject-matter of the present claims is that contained in document D1. The most relevant part of document D1 is the discussion of so called "Tornado codes" in section 5. There it is explained that (emphasis added by the Board):

- Erasure codes are considered in the discussion "that take a set of k source data packets and produce a set of l redundant packets for a total of n = k + l encoding packets all of a fixed length P" (page 58, right column, third paragraph).

- "We think of the ith source data packet as containing the value of a variable xi, and we think of the jth redundant packet as containing the value of a variable yj" (section 5.1 Theory, page 58, right column, fourth paragraph).

- "For Tornado codes, the equations have the form y3 = x1 XOR x4 XOR x7, where XOR is bitwise exclusive-or. Tornado codes also use equations of the form y53 = y3 XOR y7 XOR y13; that is, redundant packets may be derived from other redundant packets" (page 59, left column, second paragraph).

3.2 From these explanations in D1 it is clear to the Board that when Tornado codes are used, the transmitted packets include source data packets, which each contain a source data variable xi, and redundant packets, which contain a variable yj derived by combining a plurality of source data variables xi using the XOR operator. These source data variables xi and transmitted packets correspond to the input symbols and output symbols referred to in the present claims.

3.3 Document D1 does not explain in detail how, for the generation of any given redundant packet, the particular source data variables xi are to be selected. However the example described in section 5.2 and shown in figure 1 gives some insight. The left side of figure 1 shows how two levels of redundant packets l are generated from the source data k using bipartite graphs. The right side of Figure 1 shows the source data k and the first level of redundant packets l in more detail. Variables a to h of the source data are depicted as solid circles and variables of the redundant packets are depicted as shaded circles. A graph is drawn between the source data and the redundant packets to show which variables a to h of the source data are combined to form each of four redundant packets, in particular:

a + b + f

a + b + c + d + g

c + e + g + h

c + d + e + f + h

(where + denotes the XOR operator)

It is evident from this example that D1 contemplates forming redundant packets from differing numbers of input variables (e.g. 3, 4 or 5 input variables) and from diverse combinations of the input variables.

According to D1 (page 60, left column, second paragraph), the code is specified by specifying the random graphs to place between consecutive levels of figure 1.

3.4 In the contested decision (see reasons for the decision, paragraph 10a) the examining division held that the list of input symbols indicated in figure 1 of D1 constituted a key which must be made available to the generating step for it to be able to determine which input symbols should be exclusive-ORed. In the Board's view, however, the lists of input symbols indicated in figure 1 of D1 correspond not to the claimed keys, but rather to the claimed lists AL(i) that indicate W(i) associated input symbols. Document D1 does not disclose how the lists of input symbols (or in other terms the graphs between consecutive levels) are generated. In particular, D1 does not disclose the claimed features that:

- for each output symbol a list AL(i) of associated input symbols is determined according to a predetermined function of a key I; and

- the keys (i) are selected from a key alphabet, wherein the key alphabet is such that the number of possible keys in the key alphabet is much larger than the number of input symbols in the ordered set of input symbols such that an effectively unbounded number of output symbols that are generally independent of each other can be generated.

The Board therefore considers claims 1 and 2 to be new, Article 54 EPC.

3.5 By having a number of keys available that is much larger than the number of input symbols, the method and system according to the invention is able to generate an effectively unbounded number of generally independent output symbols. This reduces the chance that output symbols will be generated that do not contribute to the later process of decoding the transmitted data.

3.6 There is no suggestion in D1 or in any of the other available prior art to use such a key alphabet with a number of keys that is much larger than the number of input symbols to be coded. For this reason the Board does not consider it obvious for the skilled person to come to the subject-matter of claims 1 and 2. The Board therefore considers the invention according to claims 1 and 2 to involve an inventive step, Article 56 EPC.

3.7 The Board notes that questions may remain as to whether or not the content of document D1 formed part of the state of the art in the sense of Article 54(2) EPC.

The D1 document itself appears to have been published in October 1998, i.e. after the filing of the first of the present application's two priority documents (US 60/101473) on 23 September 1998.

It has not been proven whether or to what extent the content of document D1 was made available to the public, orally or in written form, at SIGCOMM'98 Conference in Vancouver on 2 September 1998, i.e. before the earliest priority date of the present application. Conversely, it has not been established whether or not this first priority document was filed in respect of the same invention in the sense of Article 87(1) EPC and hence whether or not this earliest priority date counts as the date of filing for the present application (Article 87 EPC). The Board did not consider it necessary to decide upon these questions since the content of D1 was anyway found not to be prejudicial to novelty and inventive step.

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 in the following version:

Description:

- Pages 1 to 5, 8, 9 and 11 to 49 as originally filed;

- Pages 6, 6a, 7, 10 and 10a received during the oral proceedings of 3 September 2008;

Claims:

- Nos. 1 and 2 received during the oral proceedings of 3 September 2008;

Drawings:

- Sheets 1/18 to 18/18 as originally filed.