T 0538/05 () of 16.3.2007

European Case Law Identifier: ECLI:EP:BA:2007:T053805.20070316
Date of decision: 16 March 2007
Case number: T 0538/05
Application number: 01109157.6
IPC class: H03M 13/09
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 26.974K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Crc operation unit and crc operation method
Applicant name: MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD.
Opponent name: -
Board: 3.5.02
Headnote: -
Relevant legal provisions:
European Patent Convention 1973 Art 84
Keywords: Claims - clarity (no)
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. This is an appeal of the applicant against the decision of the examining division to refuse European patent application No. 01 109 157.6.

II. The decision under appeal cited the following prior art document:

D1: EP-A-0 936 537.

III. In a communication annexed to summons to attend oral proceedings the board expressed doubts as to the clarity of claim 1. In addition to D1, the communication of the board cited the following document:

D2: application report SPRA530 of Texas Instruments "Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x" by Patrick Geremia, carrying a date of April 1999.

IV. The appellant replied with a letter dated 15 February 2007 which cited the following further documents:

D3: JP-A-5 151 007, and

D4: "A Tutorial on CRC Computations" by Tenkasi V. Ramabadran and Sunil S. Gaitonde, published by the IEEE and carrying a date of August 1998.

V. Oral proceedings before the board took place on 16 March 2007. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of claims 1 to 10 of the main request, or alternatively on the basis of claims 1 to 9 of the auxiliary request, both requests filed with the letter of 15 February 2007.

VI. Claim 1 of the main request reads as follows:

"A processor provided with a CRC operation unit for executing CRC operation, said processor comprising general processor components including an arithmetic and logic unit (32) and said CRC operation unit comprises:

generating polynomial supply means (11) for holding data representing a generating polynomial and selectively outputting either the data representing a generating polynomial or zero data of which all bits have a value of "0";

operation data supply means (21) for outputting operation data to be subjected to CRC operation; and

exclusive OR (XOR) operation means (31) for performing exclusive OR operation between the data representing a generating polynomial or the zero data and the operation data;

wherein the generating polynomial supply means (11) selects the data representing a generating polynomial or the zero data depending on the value of the MSB of operation results from the exclusive OR operation means (31); and

the operation data supply means (21) outputs, as the operation data, data composed of:

values of bits in lower order than the MSB of the operation results from the exclusive OR operation means as values of higher-order bits of the operation data; and

the value of the MSB of unprocessed data to be subjected to CRC operation as the value of the LSB of the operation data,

characterized in that,

the components of said CRC operation unit are formed of said general processor components and additional components in such a manner that said exclusive OR operation means (31) is formed by said arithmetic and logic unit (32), and

said generating polynomial supply means (11) and said operation data supply means (21) are at least partly formed by said additional components."

Claims 2 to 10 of the main request are dependent on claim 1.

VII. The pre-characterising portion of claim 1 of the auxiliary request is identical to the pre-characterising portion of claim 1 of the main request.

The characterising portion of claim 1 of the auxiliary request reads as follows:

"characterized in that,

the components of said CRC operation unit are formed of said general processor components and additional components in such a manner that said exclusive OR operation means (31) is formed by said arithmetic and logic unit (32), and

the generating polynomial supply means (11) comprises a selector (13) for selectively outputting either the data representing the generating polynomial or the zero data;

the operation data supply means (21) comprises a shift register (23) for holding part of the unprocessed data to be subjected to CRC operation, for outputting the value of the MSB of the held data, and for shifting bits of the held data leftward one by one;

the selector (13) and the shift register (23) are components specialized for CRC operation."

Claims 2 to 9 of the auxiliary request are dependent on claim 1.

VIII. The appellant essentially argued as follows:

It was known to carry out CRC computations by means of special hardware circuits (comprising Linear Feedback Shift Registers: LFSR) added to a microprocessor and designed to carry out the complete CRC computation in hardware and return the final result. Further, two different software solutions were known: a bitwise software solution with a plurality of software steps carried out for each bit of the data to be processed, and a software solution using look-up tables to avoid parts of computation routines. These software solutions were discussed in D4 and made use of general purpose microprocessors that included the following essential parts: instruction fetcher, instruction decoder, registers, memory interface, barrel shifter, and an ALU (Arithmetic Logical Unit) to carry out logical computations (AND, OR, NOR, NAND and XOR) and arithmetic computations (multiplication and division). Hardware circuits specialized for CRC operation were the fastest. However, they required sophisticated hardware, especially when the generator polynomial was not fixed, and increased the circuit size of a communication unit. The hardware expense was even larger if flexibility was needed to allow different generator polynomials. When specialized hardware circuits were used for the CRC computation, all computational steps were carried out in the specialized hardware circuits and none in the ALU. D1 and D3 disclosed hardware "add-ons", i.e. specialised hardware, which carried out the complete algorithm to compute the CRC remainder for a frame of data and thereby provided maximum speed but at a considerable hardware expense. Table 7 of D2 showed that the bitwise software solution was the slowest but used a minimum of storage capacity. D2 suggested using look-up tables, which improved the speed performance but at the expense of an increase in the memory required. For low cost solutions in consumer products, it was essential to look for an optimum solution on costs, physical size of the processor, energy consumption, and flexibility. The inventors of the present invention had questioned whether it would be possible to reduce the hardware resources by using already existing hardware of the ALU for selectable procedural steps and nevertheless retain a high speed comparable with that obtainable with specialised hardware. This required a profound knowledge of how a usual general purpose processor worked, what processor cycles were needed for the different processes and how the performance could be improved with a minimum of "additional components". The claimed processor used the hardware XOR circuit of the ALU for the XOR operations so that it was not necessary to include hardware for XOR operation in a specialised circuit. It was only necessary to add some selected components in the generating polynomial supply means and the operational data supply means to overcome the disadvantages of a low speed software solution and nevertheless obtain a low cost and flexible solution. The expression "general processor components" and "additional components" had a well defined meaning for a person skilled in the art. "General processor components" were those components that were common and essential in usual microprocessors. Any components added in hardware for a special task, such as an MPEG calculator, a cryptographic engine, Huffman-encoding/decoding hardware or a LFSR for CRC computation, were known as "additional components". Additional components were activated by a special operational code or instruction added to the set of codes to be used for the processor. Therefore, the "additional components" were clearly defined, because they were not needed for any other purpose than the special task and did not carry out normal computational functions such as AND, OR, NOT and XOR and the arithmetic functions of multiplication and division for which a processor was designed. In particular, the selector (13) and the shift register (23) were low cost hardware components compared to the LFSR of a specialised hardware solution. Compared to a software solution, the present invention required a low number of cycles to perform a CRC computation, whereby the speed was improved. Furthermore, the invention allowed use of different generator polynomials with no hardware adaptation. The claimed solution was intermediate between the slow software solution and the fast but expensive specialised hardware solution. The prior art did neither show nor suggest such a "mixed" or "hybrid" solution, which was not a common design practise. Claim 1 of the main request left open, which specific "additional components" were to be added as it merely referred to components of the generating polynomial supply means (11) and the operation data supply means (21) that had to be at least partly formed by additional components. This definition was in line with the general teaching of the invention. The CRC algorithm was state of the art. Which parts had to be added to perform the algorithm depended on the functionality of the processor and the ALU. Therefore, the skilled person was in a position to determine which components had to be added, depending on the requirements to carry out CRC operations. Thus, claim 1 of the main request included a complete teaching of the claimed invention. Claim 1 of the auxiliary request was a combination of claims 1 and 2 of the main request and was more specific than claim 1 of the main request as regards the "additional components". Therefore, the claims were clear.

Reasons for the Decision

1. The appeal is admissible.

2. Main request

Claim 1 of the main request relates to a processor provided with a CRC operation unit. The appellant agrees that the algorithm carried out by the CRC operation unit is state of the art. It is therefore essential in the present case that the hardware aspects of the invention be clearly defined in claim 1. As regards the hardware, claim 1 states that the processor comprises general processor components including an arithmetic and logic unit, which in the following will be referred to as an ALU, and that the components of the CRC operation unit are formed of said general processor components and additional components in such a manner that exclusive OR operation means is formed by said ALU, and generating polynomial supply means and operation data supply means are at least partly formed by said additional components. Thus, claim 1 attempts to draw a distinction between two types of components of the CRC operation unit: "general processor components" and "additional components". Which components of a processor are to be regarded as being "general processor components" and which components as being "additional components" is not immediately apparent, because there exist many different processors, comprising different components. According to the appellant, for a person skilled in the art, "general processor components" are those components that are common and essential in usual microprocessors, while "additional components" are any components added in hardware for performing special tasks. Even if this would effectively be a generally accepted distinction between "general processor components" and "additional components", it would be a subjective distinction that depends on which processors are regarded as being usual and on the degree of specialisation that is regarded as necessary to qualify as an add-on for performing a special task. Furthermore, the distinction made by the appellant appears to be based on the conceptual origin of the components (apparently, "general processor components" are found in usual microprocessors for performing usual tasks, and "additional components" are found in add-ons for performing special tasks). Thus, which components are general processor components and which are additional components depends on which usual processor(s) and which add-on(s) are taken into consideration. This becomes manifest in particular if one attempts to determine which components of the processor defined in document D2 are "general processor components" and which are "additional components". D2 relates to a digital signal processor TMS320C54x used for CRC computation. The processor of D2 includes a 40-bit arithmetical and logical unit (ALU) that carries out an XOR instruction during a CRC computation. Thus, the processor of D2 appears to have exclusive OR operation means formed by the arithmetic and logic unit (ALU) of the processor. D2 states that the digital signal processor TMS320C54x processor is interesting for the implementation of CRC algorithms because, in addition to the 40-bit arithmetical and logical unit (ALU), it includes two 40-bit accumulators, efficient memory addressing modes, multiple bus structure and a barrel shifter (see page 9 of D2, under "General Considerations"). It is not clear which of these components should objectively be regarded as "general processor components" and which should be regarded as "additional components", because this depends on which processor is taken as the conceptual origin of the TMS320C54x processor. For these reasons, the board considers that claim 1 of the main request is not clear in the sense of Article 84 EPC.

3. Auxiliary request

Claim 1 of the auxiliary request states that the components of the CRC operation unit are formed of general processor components and additional components. Furthermore, claim 1 of the auxiliary request states that the selector (13) of the generating polynomial supply means (11) and the shift register (23) of the operation data supply means (21) are components specialized for CRC operation. It appears from the passage on page 12, lines 10 to 22 of the originally filed application that the CRC operation unit can be constructed by adding only these specialised components to a general processor. This means that the specialised components of claim 1 are added to the general processor components, i.e. are "additional components". Here also, it is not clear which of the components of the processor should objectively be regarded as "general processor components" and which should be regarded as "additional components", because this depends on which processor is taken as conceptual starting point.

4. Therefore, the board concludes that claim 1, both in the version of the main request and in the version of the auxiliary request, does not meet the requirement of clarity specified in Article 84 EPC.

ORDER

For these reasons it is decided that:

The appeal is dismissed.

Quick Navigation