T 0212/94 11-10-1996
Download and more information:
Resisting the effects of channel noise in digital transmission of information
Clarity - yes (after amendment)
Mathematical method - no (after amendment)
Inventive step - yes (after amendment)
1. The appellant contests the decision of the examining division refusing European patent application No. 88 301 149.6. The reason given for the refusal was that the independent method claim 1 then on file was not clear and that the subject-matter of the independent apparatus claim 6 then on file did not involve an inventive step, having regard to the prior art known from the following document:
D1: Proceedings of MELECON '85, Madrid, Spain October 1985, Volume II: D igital Signal Processing, pages 137-140; S. Bingöl et al: "Joint source channel coding in vector quantization".
II. Following communications from the board in which, in addition to objections of lack of clarity of the claims, an objection that the subject-matter of claim 1 was directed to a mathematical method as such was raised, the appellant requested that the decision under appeal be set aside and a patent granted on the basis of the application in its amended form, that is:
Claims:
1. to 4 as filed with the letter of 28. August 1996, received 31 August 1996;
Description:
Pages 4, 7, 8, 9, 11 and 12, as originally filed.
Pages 1 and 10, as filed with the letter of 21 December 1992.
Pages 1a, 5 and 6, as filed with the letter of 13 September 1994, received 17. September 1994.
Page 2 as filed with the letter of 28. July 1995, received 4 August 1995.
Page 3 as filed with the letter of 28. August 1996, received 31 August 1996.
Drawings:
Sheets 1 to 3, as originally filed.
III. Independent claims 1 and 4 are worded as follows:
"1. A method of assigning binary index code signals to codewords representing vector quantized audio information or vector quantized image information for transmission in a communication system in accordance with a codebook which is generated by the steps of
picking a first codeword having both a high probability of occurrence among the codewords and a low total of the distances, the picking being based on a function of the probability of occurrence of the first codeword among the codewords and on the total of the distances between each nearest neighbor codeword in a group of B nearest neighbor codewords and the first codeword during system operation, where B is the bit length of the codewords,
assigning a first binary index code to the first codeword, and storing said assigned first binary index codeword in the codebook,
finding the group of B nearest neighbor codewords, in terms of a perceptually-related distance measure between the first codeword and the other codewords, wherein the finding step includes measuring the distance or proximity of the nearest neighbor codewords in terms of some perceptually-related similarity of the underlying codewords, such that the decoded information will be perceived to be resistant to noise occurring during transmission in the communication system, provided that the assigning is employed in such a system in which noise typically affects only one bit in any affected binary index code,
assigning to at least some of the nearest neighbor codewords binary index codes a Hamming distance of one from the first binary index code, and storing the binary codes assigned to the at least some of the B nearest neighbors,
repeating the foregoing steps as many times as needed for successive remaining codewords not yet assigned to a binary index code while avoiding duplicate assignments until either the B group of nearest neighbor codewords cannot be found or the group cannot be assigned binary index codes differing in only one bit, and
assigning remaining binary index codes to remaining codewords and storing the assigned remaining binary index codes."
"4. Communication equipment of the type including coding means for assigning binary index codes to codewords representing vector quantized audio information or vector quantized image information to be communicated in accordance with a codebook generated by the steps of
picking a first codeword having both a high probability of occurrence among the codewords and a low total of the distances, the picking being based on a function of the probability of occurrence of the first codeword among the codewords and on the total of the distances between each nearest neighbor codeword in a group of B nearest neighbor codewords and the first codeword during system operation, where B is the bit length of the codewords,
assigning a first binary index code to the first codeword, and storing said assigned first binary index codeword in the codebook,
finding the group of B nearest neighbor codewords, in terms of a perceptually-related distance measure between the first codeword and the other codewords, wherein the finding step includes measuring the distance or proximity of the nearest neighbor codewords in terms of some perceptually-related similarity of the underlying codewords, such that the decoded information will be perceived to be resistant to noise occurring during transmission in the communication system, provided that the assigning is employed in such a system in which noise typically affects only one bit in any affected binary index code,
assigning to at least some of the nearest neighbor codewords binary index codes a Hamming distance of one from the first binary index code, and storing the binary codes assigned to the at least some of the B nearest neighbors,
repeating the foregoing steps as many times as needed for successive remaining codewords not yet assigned to a binary index code while avoiding duplicate assignments until either the B group of nearest neighbor codewords cannot be found or the group cannot be assigned binary index codes differing in only one bit, and
assigning remaining binary index codes to remaining codewords and storing the assigned remaining binary index codes."
Claims 2 to 3 are dependent on claim 1.
IV. The appellant argued essentially as follows:
The objections raised in respect of clarity of the claims had been overcome by amendment. In particular the term "distance measure" had been defined in the independent claims in terms of a perceptually-related measure and the term "nearest neighbor codewords" had been clarified by specifying a group of B nearest neighbour codewords, where B is the bit length of the codewords. The relative terms "high" (probability of occurrence) and "low" (total of the distances) had a clearly defined scope in the context in which they were used.
The objection raised that claim 1 was directed to a mathematical method as such had been overcome by amendment to specify that the codewords represented audio or image information, and by reference to the function of the codebook to make it clear that the subject-matter of the claim was not merely a mathematical algorithm but that it was directed to operations on physical entities.
The amendments also distinguished the invention more clearly from the closest prior art D1. In particular it had been made clear that, whereas in D1 the first codeword was chosen as that having the highest probability of occurrence, in accordance with the claimed invention the choice of first codeword was made on the basis of a trade-off between high probability of occurrence and low total of distances to a group of nearest neighbours. The further steps of the assignment method specified in the independent claims also differed from the D1 algorithm in that the former involved the assignment of binary index codes to groups of nearest neighbours, where the nearest neighbours were determined by a distance measure from the neigbours to only one codeword (ie the selected first codeword). In D1 the assignment was effected sequentially in accordance with a computation involving distances to all previously selected vectors.
These features of trade-off and assignment in groups were not derivable for the person skilled in the art from the teaching of D1.
1. The appeal is admissible.
2. Clarity
2.1. Claim 1 includes the relative terms "high probability of occurrence" and "low total of the distances", which do not have a well-recognised (absolute) meaning in the art in the sense of the Guidelines for Examination in the EPO, C-III, 4.5. In the judgement of the board, however, this lack of precision does not entail a lack of clarity within the meaning of Article 84 EPC; it corresponds rather to the trade-off between codeword frequency and perceptual distance from other codewords which is inherent in the first step of the claimed method. The description (page 7, equation 9) indicates one empirical weighting function which can be used to implement the trade-off decision but the person skilled in the art would appreciate that other choices are possible. The matter for which protection is sought here is not a unique optimum encoding of audio or image information, but a method of encoding which employs objective criteria to achieve a result tending towards reduced distortion induced by channel noise. A crisp mathematical definition of the periphery of such a method would be artificial and arbitrary, whereas the claim as now worded is susceptible of a clear functional interpretation which, in the judgement of the board, strikes an appropriate balance between legal certainty and fair protection.
The board finds therefore, that claim 1 meets the clarity requirement of Article 84 EPC, which finding also applies, for analogous reasons, to the independent apparatus claim 4.
3. Mathematical method
Claim 1 as now worded is, in substance, directed to the encoding of data representing audio information or image information for transmission in a communication system in accordance with a codebook (ie an assignment rule) specified in the claim. Although the idea underlying the invention - the novel algorithm defining the codebook as a mathematical function - may be considered to be a mathematical method, the present claim is directed to the use of the assignment rule in the processing of audio or image signals, which are themselves physical entities. In addition, the step of "finding the group of B nearest neighbour codewords" in claim 1 includes "measuring the distance...in terms of some perceptually-related similarity of the underlying codewords". This in turn means that the entities and relationships featuring in the problem solved by the invention are not purely abstract mathematical ones. The claimed method solves a technical problem (see paragraph 4.1 below). Following the VICOM decision (T 208/84, OJ EPO 1987, 14, points 5 to 7), the board finds, therefore, that the subject-matter of this claim does not relate to a mathematical method as such and is not excluded from patentability by the provisions of Article 52(2)(a) and 52(3) EPC.
This finding also applies, for analogous reasons, to the apparatus claim 4.
4. Inventive step
4.1. Starting from the undisputed closest prior art D1, the technical problem solved by the method of coding audio or image information for transmission specified in claim 1 is to find a method of assigning binary index codes to codewords representing vector quantized information which further reduces the effects of distortion induced by channel noise. The latter can change one or more bits in the transmitted binary code and change the decoded signal values to values which are perceptually far removed from the intended values; see pages 1 to 1a of the application.
4.2. This problem is plausibly solved in accordance with the teaching of the present application by assigning the binary index codes (constructing the codebook) in accordance with the steps specified in claim 1.
4.3. Although D1 is the closest prior art, the board considers that a two-part form of claim delimited with respect to D1 would not be appropriate, since it would involve an artificial generalisation of the prior art steps.
4.4. Claim 1 specifies a solution to the assignment problem which differs from the D1 method in two significant respects:
(i) the first vector codeword to be assigned is not necessarily the codeword with the highest probability of occurrence (cf. D1, page 139, left column, step 1); it is chosen with regard also (in a trade-off sense) to the total of the distances between each nearest neighbour codeword in a group of B (B = bit length of codeword) nearest neighbour codewords and the first codeword during system operation;
(ii) groups of B nearest neighbour codewords are identified and at least some of the latter are assigned binary index codes a Hamming distance of one from the first binary index code;
the above steps being repeated for remaining codewords.
In D1 the codewords are assigned one at a time in accordance with a criterion based on distance of the respective codeword from those previously assigned, the distance being weighted in accordance with probability of occurrence; see D1, page 139, steps 2 to 8.
4.5. In the judgement of the board these significant differences, which plausibly result in an improved codebook in the sense of affording better resistance to channel noise, are not obvious variations of the teaching of D1 having regard to the available prior art including common general knowledge in the art.
4.6. One strand of the reasoning on the issue of inventive step in the decision under appeal remains relevant to the amended claims. It was argued (paragraph bridging pages 5 and 6) that since Euclidean distance in the codevector (codeword) space is preserved as Hamming distance in the binary index space, it followed that the inverse image of the neighbourhood in this latter space, ie the original Euclidean neighbourhood in the codevector space, necessarily involved a low nearest neighbour total distance. In this way the first codeword chosen as a starting point in step 1 of D1 would satisfy the criteria of claim 1.
This argument relies on an interpretation of the statement in D1, at page 139, left column, under "Code Design and Simulation Results": "... we need a rule which preserves Euclidean distance in the vector(codeword) space as Hamming distance in the (binary index)code space". However, as understood by the board, this statement is referring to a desideratum for a notional optimal assignment. It does not say it is attainable by the D1 assignment algorithm. It is clear that making the Hamming distance small in the code space (by assigning the binary index code) cannot affect the pre-existing Euclidean vector distance. If the vector selected in step 1 of the D1 algorithm (vector with the highest probability of occurrence) has not, in fact, got a low nearest neighbour total distance (ie is a relatively isolated point) then assigning indices cannot alter this fact. The "nearest vector" selected by step 2 in D1 is not guaranteed to be near in any absolute sense since this was not a selection criterion in step 1 - as distinct from the algorithm of the present application. The latter thus provides a closer approach to the optimal Euclidean -> Hamming metric preserving assignment which is not derivable from the prior art.
4.7. The board therefore concludes that the subject-matter of claim 1 involves an inventive step within the meaning of Article 56 EPC. The same is true for the dependent claims 2 and 3. This finding also applies, for analogous reasons, to the apparatus claim 4.
5. In the judgement of the board, the application meets the requirements of the EPC. However, the board has noticed an obvious clerical error on page 2 of the description (as filed with the letter 28 July 1995), namely in line 13 "claim 5" should read "claim 4". The board directs that this error be corrected.
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 appellant's request (see paragraph II above), with correction of the obvious clerical error on page 2 (see paragraph 5 above).