T 1241/17 (Circuit for compressing data/MOVIDIUS) 17-11-2020
Download and more information:
A circuit for compressing data and a processor employing same
Amendments - added subject-matter (no after amendment)
Claims - clarity (yes after amendment)
Inventive step - (yes over the prior art on file)
Remittal to the department of first instance
Remittal - (yes after amendment)
I. The applicant (appellant), at the time Linear Algebra Technologies Limited, appealed against the decision of the Examining Division refusing European patent application No. 08717870.3, filed as international application PCT/EP2008/053133 (published as WO 2008/110633). The application claims priority dates of 15 March 2007 and 11 April 2007.
II. In the course of the appeal proceedings, Linear Algebra Technologies Limited merged by absorption into Movidius Limited, which thereby obtained the status of appellant.
III. The documents cited by the Examining Division were:
D1 WO 01/43074 A1, published on 14 June 2001;
D2 Wikipedia article "Arbeitsspeicher", version last modified on 14 March 2007.
The international search report further cited the textbook:
D3 Salomon, D., "Data Compression - the Complete Reference", Springer, 1998, pp. 6-10.
IV. In its decision, the Examining Division held that claim 1 of the main request did not comply with Articles 84 and 123(2) EPC and that the subject-matter of claim 1 according to the first and second auxiliary requests did not involve an inventive step, having regard to document D1. Moreover, claim 1 of the second auxiliary request did not comply with Article 84 EPC.
V. In its appeal, the appellant requested that the decision be set aside and that a patent be granted on the basis of a sole request, submitted with the grounds of appeal, which, according to the appellant, clarified the main request considered in the contested decision.
VI. In a communication under Article 15(1) RPBA 2020 accompanying the summons to oral proceedings, the Board expressed its preliminary opinion that the subject-matter of claim 1 of the sole request did not comply with Articles 84 and 123(2) EPC. The Board did not share the Examining Division's view that the subject-matter of claim 1 lacked inventive step in view of document D1. Rather, the Board indicated that it was inclined to remit the case to the department of first instance for further prosecution should the appellant overcome the Board's preliminary objections on lack of clarity and added subject-matter.
VII. In reply, the appellant submitted a main request and an auxiliary request, replacing its prior sole request.
VIII. In a subsequently-filed letter, the appellant informed the Board that it would not be represented at the oral proceedings, and that its request for oral proceedings was withdrawn.
IX. In response, the Board cancelled the oral proceedings.
X. The appellant's final requests were that the contested decision be set aside and that a patent be granted on the basis of the main request or the auxiliary request, both as filed in reply to the Board's communication.
XI. Claim 1 of the main request reads as follows:
"A processor having an instruction for storing data in block form, the processor comprising a circuit responsive to the instruction, the circuit comprising:
a) a data memory for storing a first data structure comprising individual data values, the first data structure corresponding to the data in block form to be stored,
b) a map memory for storing a map, the map representing the locations of individual non-zero data values within the first data structure,
c) a data output for outputting to a memory for storage,
wherein the circuit is configured to retrieve the non-zero data values from the first data structure of the data memory using the map and to provide the retrieved data as a second data structure in combination with data representing the map on the data output."
Claims 2 to 11 and 13 are dependent, directly or indirectly, on claim 1. Dependent claim 13 has been erroneously renumbered as claim 12 by the appellant.
The correct claim 12 reads as follows:
"A processor having an instruction for retrieving data in block form, the processor comprising a decompression circuit responsive to the instruction for decompressing a compressed data structure containing the data in block form to be retrieved, the circuit comprising:
a) an input for accepting a compressed data structure comprising individual non-trivial data values, where the non-trivial values are non-zero values;
b) a map register for receiving a map identifying locations, the locations being the locations of the non-trivial data values within a decompressed data structure,
c) a memory for storing the decompressed data structure, wherein the circuit is configured to decompress the compressed data structure by populating the locations of an unpopulated uncompressed data structure which are specified in [a] map register as being locations of non-trivial data with individual inputted non-trivial data values to provide a[n] uncompressed and populated data structure."
In view of the outcome of the appeal, the auxiliary request is not relevant to the present decision.
XII. The appellant's arguments, where relevant to the decision, are discussed in detail below.
1. Since the appellant has withdrawn its request for oral proceedings, the decision can be taken without holding oral proceedings.
2. Admissibility of the appeal
The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.
The invention
3. The invention relates to compression and decompression of data.
According to the application (international publication, page 1, last paragraph), it is known from US patent 6,591,019 to compress a matrix of data values into a structure comprising a "bitMap" table, a "signMap" table and a "dataMap" table. The "bitMap" table comprises a series of 2-bit entries, each 2-bit entry corresponding to an entry in the uncompressed matrix structure. Each 2-bit entry in the "bitMap" identifies whether the corresponding value in the uncompressed matrix is either a zero or a one or stored in "scaled form" or in uncompressed form in the "dataMap". The "signMap" table identifies the signs of the values in the uncompressed structure. A disadvantage of this compression method is that it is not lossless, as information is lost in scaling values. Moreover, the method is only practical for implementation in software.
The claimed invention relates to a processor comprising a circuit for compression or decompression (see page 8, line 7, to page 10, line 24; Figures 1 to 5, 7 and 9). The underlying idea of the invention is to support a specific processor instruction for the storing or reading of a block of data by the circuit for compression or decompression, respectively. The compression method implemented by the instruction for storing a block of data uses a bitmap having one bit for each element of the data block, with bitmap entry values equal to "1" indicating the non-zero elements in the data block and bitmap entry values equal to "0" indicating the zero elements. Compression is achieved by suppressing the zero elements of the data block as they are redundant due to the use of the bitmap (since a bitmap entry of "0" always corresponds to a data element having a value of zero). The advantage of the invention is that it can be implemented with low cost and fast processing speed in hardware without taking up processor resources (page 2, line 29, to page 3, line 3).
Main request
4. Admission
The set of claims according to the main request was a response to objections raised for the first time in the preliminary opinion of the Board. In view of this situation, there are exceptional circumstances justifying the amendments at this stage. Consequently, the Board admits the main request into the appeal proceedings (Article 13(2) RPBA 2020).
5. Added subject-matter
5.1 Compared to claim 1 of the main request as considered in the contested decision, the appellant added the text "the first data structure corresponding to the data in block form to be stored" to claim 1 of the main request (see feature a)). It also amended feature b) and the final feature of claim 1 ("wherein ...") so that these features refer to the "first data structure" according to feature a). The appellant cited page 12, line 14, and page 13, lines 1 and 2, of the description as a basis (statement of grounds of appeal, points 45 and 46).
The Board agrees that the above amendments comply with Article 123(2) EPC.
5.2 In the contested decision, the Examining Division had objected to the amendment "wherein the second data structure is a compressed data structure with respect to the first data structure as long as one of the individual data values of the first data structure is zero" in feature c) of claim 1. Since the appellant has removed this wording, which had been added to claim 1 in the proceedings before the department of first instance, this objection is no longer relevant.
5.3 The Examining Division had also objected under Article 123(2) EPC to the wording a "processor having an instruction for storing data in block form, the processor comprising a circuit responsive to the instruction" in claim 1, since it considered this wording to be an unjustified generalisation of the content of the application as filed (see point 1.2 of the contested decision). There was no link between the processor and the instruction on the one hand and the data/map memory and the data output on the other hand.
5.3.1 The appellant argued that there was a link as the processor had the instruction, the circuit was responsive to the instruction, and data was placed on the data output as a result. Nevertheless, it had clarified this link in its request submitted with the statement of grounds of appeal (see therein points 43 to 46), citing page 13, lines 1 and 2, as basis.
5.3.2 The Examining Division's objection cannot be upheld for the present request as the Board agrees with the appellant that the link between the instruction and the further features is clear in the present main request. The data and map memories (see features a) and b) of claim 1) are now linked to the instruction via the first data structure, and the data output according to feature c) of claim 1 is obtained by processing the first data structure (see the final feature of claim 1). There is a basis for the amended features in the application as filed. For example, Figure 4 of the application shows a processor having decompression and compression circuits, embodiments of which are shown in Figures 5 and 7, respectively (see also page 12, line 9, to page 14, line 11; page 16, lines 16 to 22, and original claim 1).
5.4 The Board is satisfied that claim 1 of the main request complies with the requirements of Article 123(2) EPC. In the contested decision, there was no objection to the corresponding independent claim 12 of the main request, which is directed to a processor comprising a decompression circuit, and the Board sees no reason to question the compliance of claim 12 with Article 123(2) EPC.
6. Clarity and support
6.1 In the contested decision, the Examining Division had objected to the wording "processor having an instruction for storing data in block form, the processor comprising a circuit responsive to the instruction" under Article 84 EPC, as it rendered the scope of protection of claim 1 unclear. It was not clear what limitations, if any, resulted from this wording with respect to features a) to c). It was unclear which of these features was implemented by the processor.
6.1.1 In its statement of grounds of appeal, the appellant argued that it had addressed this clarity issue by amending claim 1. The data memory feature a) of the main request refers to "data in block form to be stored". Moreover, the appellant clarified claim 1 of the main request in that it is the circuit that comprises features a) to c), so that there is no ambiguity as to whether the circuit or only the processor comprises these features.
6.1.2 The Board agrees with the appellant, as features a) to c) of claim 1 refer to the first data structure which is linked to the instruction for storing data in block form. Hence the Board considers that the clarity objection raised in the contested decision is overcome by the amendments made to claim 1.
6.2 In reply to the Board's communication, the appellant further clarified claim 1 so that its features are now consistent with each other.
6.3 In view of the above, claim 1 of the main request meets the requirements of Article 84 EPC, the same applying mutatis mutandis to the corresponding independent claim 12.
7. Inventive step
7.1 In the contested decision, the Examining Division had decided that the auxiliary requests then on file lacked inventive step in view of document D1.
7.2 In its statement of grounds of appeal, the appellant contested that document D1 was a suitable starting point for assessing inventive step. It argued that the subject-matter of claim 1 was novel over D1 as this document did not disclose any features of a processor. No circuit responsive to an instruction in a processor was disclosed.
The appellant also argued that the compression method disclosed in document D1 differed from the approach of the invention and was not at all suitable for implementation in a general-purpose computer. Furthermore, D1 did not disclose a processor having an instruction for storing data in block form. Hence, in the appellant's view, a further step was needed to arrive at the invention.
7.3 The Board agrees with the appellant that document D1 is not a promising starting point for assessing inventive step of the independent claims. The Examining Division refused the then-pending auxiliary requests using D1 as a starting point for assessing inventive step, but the subject-matter of the then-pending auxiliary requests differs considerably from the subject-matter of claim 1 according to the present main request.
Document D1 is closely related to the subject-matter of US patent 6,591,019 that is cited on page 1 of the description. The compression method disclosed in D1 is specifically tailored to the compression of three-dimensional transformation matrices in the context of computer animations. Such matrices typically have elements with values of 0, 1 and floating point numbers. An implementation of this particular compression scheme in hardware is not disclosed in document D1. Rather, document D1 discloses that the transformation data is compressed off-line, for example by a special tool prior to compilation (see D1, page 3, lines 25 and 26; page 6, lines 20 to 24). Hence the skilled person would recognise that the lossy compression algorithm of D1 is not suitable for a hardware implementation supporting storing data in block form at run-time in a compressed format in memory.
When starting from document D1, the skilled person would have to first simplify the algorithm, in particular by omitting the core steps of the algorithm relating to the lossy compression of floating point numbers, then decide that the compression should be implemented in hardware, and finally come up with the specific solution claimed using a particular instruction implemented by the circuit as specified in claim 1. All this would have to be done by the skilled person without any hint in this direction in document D1, which is directed to off-line compression and thus rather teaches away from the solution claimed. This requires substantially more skill than a mere routine task. Consequently, claim 1 involves an inventive step over document D1 (Article 56 EPC). The same applies to independent claim 12, which is directed to a processor supporting efficient decompression in hardware.
7.4 The Board is aware that the effect of compression is not explicitly specified in claim 1 as required by the Examining Division. However, this effect does not have to be explicitly specified in claim 1. Rather, it is sufficient that claim 1 specifies how the data is processed. The skilled person reading claim 1 can derive from its wording that the claimed processor supports a compression algorithm.
The Board does not consider that the effect of compression has to be achieved for all possible data sets to be stored. The claimed processor includes the features necessary for achieving compression for data in block form with a redundancy above a particular threshold. Feature c) and the last feature of claim 1 ("wherein ...") state clearly what the output is. These features are based on "further technical considerations" (opinion G 3/08, OJ EPO 2011, 10, Reasons 13.5.1), which is sufficient to establish that the features relating to compression contribute to the technical character of the algorithm in the present case.
7.5 Document D2 is a Wikipedia entry about computer memories that is evidently not suitable as a starting point for assessing inventive step.
The international search report also cites document D3, a textbook excerpt about run length encoding, as an "A" document. The Board agrees that D3 is only a background document.
7.6 In its statement of grounds of appeal, the appellant submitted that the Examining Division had not cited any pertinent prior art, and the Board agrees that the search report does not list any relevant documents concerning hardware implementations of compression. Since the search may not have covered the subject-matter presently claimed, an additional search may be necessary, in particular in view of the amendments made to the claims during the proceedings.
Conclusion and remittal for further prosecution
8. In view of the above, the independent claims of the main request meet the requirements of Articles 123(2) and 84 EPC and involve an inventive step over the prior art on file (Article 56 EPC). Consequently, the contested decision cannot be upheld.
9. Under Article 111(1) EPC, the Board may either proceed further with the examination of the application or remit the case to the department responsible for the decision under appeal for further prosecution.
Article 11 RPBA 2020 provides that the Board should not remit a case for further prosecution unless special reasons present themselves for doing so. Since an additional search for relevant prior art may be necessary, and this is the responsibility of the department of first instance, such special reasons present themselves in this case. Consequently, the case is to be remitted to the department of first instance for further prosecution on the basis of the main request. Given the long duration of the proceedings thus far, the remitted case should be dealt with expeditiously.
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 for further prosecution.