T 0571/03 (Adding and averaging circuit/HEWLETT-PACKARD) of 22.3.2006

Summary of Facts and Submissions

I. European patent application number 94 112 045.3 filed on 2 August 1994 claims a priority date of 29 November 1993 for a parallel adding and averaging circuit and method.

II. Claim 1 of the application as filed has the following wording:

" An apparatus for operating on the contents of an X word having bits Xi and a Y word having bits Yi; to generate a result word having bits Zi, where i=0 to N-1, where Z0 is the least significant bit of one of said sub-words and ZN-1 is the most significant bit of one of said sub-words, said apparatus comprising: means for partitioning said X, Y and result words into a plurality of sub-words, there being one sub-word of said Y and result words corresponding to each sub-word of said X word; means, responsive to a first instruction, for generating the sum of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a third instruction, for generating the sum divided by two of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word."

III. A European search was carried out on the basis of the application. From the search report, the following documents were cited in the subsequent examination procedure with respect to claim 1:

| D1: |Vernon Coleman et al. "The Next|

| |Generation Four-Bit Bipolar Mic|

| |roprocessor Slice - The Am2903"|

| |, IRE Wescon Convention Record,|

| | Paper 16/4, Sep tember 1977, N|

| |orth Hollywood, USA, pages 1 - |

| | 19|

| D2: |US-A-4 137 568 (published in 19|

| | 79)|

| D3: |US-A-3 987 291 (published in 19|

| | 76)|

| D4: |JP-A-61 024 331 (published in 1|

| | 986)|

D1:

In two communications (of 16 November 2000 and 1 August 2001), in the summons and according to the minutes of the oral proceedings held on 15 September 2002, the examining division raised and repeated objections of lack of inventive step on the basis of document D3 as the closest prior art, document D4 as an example for averaging two numbers by shifting, and the "self-evident" or "common" nature of various features of the invention to which the applicant resorted as inventive contributions over the prior art. According to these objections, the invention merely solved the problem to increase the functionality of a device like the one of document D3. The skilled person could find in document D4 a "typical solution" how to combine an "adder with a shifter, while taking care to reintroduce in the result the overflow bit" (see minutes, page 5). The introduction of multiplexers was "merely a common workbench implementation feature". Other differences to the prior art were acknowledged but qualified as obvious: "(t)he functionality of the multiplexer corresponding to the most significant bit position is indeed different, albeit obvious." Providing control signals for changing the functionality of the multiplexers according to their position was also considered "obvious".

IV. The examining division refused the application orally at the end of the oral proceedings and notified the decision to the parties by a registered letter posted on 13 December 2002.

The decision states in the summary of facts and submissions that the objection of lack of inventive step was already raised in the communication of 16 November 2000 and that subsequent amendments had led to a claim 1 which was essentially identical to originally filed claim 1. The part titled "Reasons for the decision" takes up fully 18 lines and reads as follows:

Regarding the main request: "Claim 1 of the main request is based on claim 1 on which the summons to Oral Proceedings were based, with the addition of a feature to save the carry-out of a sub-word addition in order to use it in a divide by two operation.

Such a feature is self-evident when dividing an adder output by two. Moreover, it is explicitly taught by D4 (JP61024331).

Consequently claim 1 of the Main Request lacks inventive step as required by Article 56."

Regarding the auxiliary request: "Claim 1 of the auxiliary request is based on claim 1 on which the summons to Oral Proceedings were based, with the specification that divide by two is carried out by multiplexers, effectively constituting a shift function.

However, the implementation of shifting by means of multiplexers is very common.

Consequently claim 1 of the Auxiliary Request lacks inventive step as required by Article 56.

Further details are set out in the summons and the minutes to the Oral Proceedings."

V. On 22 January 2003 the applicant (appellant) filed a notice of appeal and paid the appeal fee. The written statement setting out the grounds of appeal and an annexed set of claims 1 to 10 were filed on 10 April 2003. Claim 1 reads as follows:

"1. An apparatus (10, 30, 100) for operating on the contents of an X word (12) having bits Xi and a Y word (14) having bits Yi to generate a result word having bits Zi, where i=0 to N-1, where Z0 is the least significant bit of said result word (16) and ZN-1 is the most significant bit of said result word, said apparatus comprising means for partitioning (33, 110, 112) said X, Y and result words into a plurality of sub-words (17, 18, 19, 20, 21, 22), there being one sub-word of said Y and result words corresponding to each sub-word of said X word; adding means (31, 32, 102, 121-124), responsive to a first instruction (A=false), for generating the sum of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word, and, responsive to a second instruction (A=true), for generating the sum divided by two of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word; wherein said adding means comprises a number of adding sections (102), each adding section (102) having multiplexers (121-124) associated therewith, said multiplexers being controlled by said first and second instructions (a), said multiplexers being configured to operate as a least significant bit multiplexer (124), an interior multiplexer (122, 123), or a most significant bit multiplexer (121), wherein a most-significant bit multiplexer (121) is provided at each sub-word boundary for shifting a carry overflow of the sum back to the corresponding sub-word of said result word."

VI. According to the appellant, the subject-matter of amended claim 1 corresponding to claim 1 of the auxiliary request filed with the submission of 21 August 2002, was clearly novel and inventive over the prior art.

Document D3 disclosed a parallel digital arithmetic device operating on sub-words. However, the device operated as a binary adder only; it was not designed to perform any averaging or shifting operation on sub-word level.

The invention was not just about concatenating instructions for adding and shifting data bits. It added the function of sub-word averaging without much increasing the complexity of a conventional parallel adder. This was achieved by additional hardware in the form of a number of adding and multiplexer sections specifically configured to operate as a least significant bit stage, an interior bit stage, and a most significant bit stage.

The device of document D3, unable to perform sub-word averaging, was clearly different from the invention in particular in respect to the use of multiplexers. There was no element for shifting a carry overflow of a partial sum back to the corresponding sub-word. The invention involved complex operations; merely combining the adder of document D3 with any conventional shifter like the one shown in document D4 would simply not result in a functioning device.

The other documents cited during examination, D1 and D2, disclosed arithmetic units for adding two numbers and then shifting the result to provide the average of the two numbers. However, the units operated on a single word level. They did not deal with the specific problems encountered when operating in parallel on a number of sub-words and they gave no suggestion how to handle carry overflows at the sub-word boundaries.

VII. The appellant requested in the statement of grounds of appeal

1. that the decision given by the examining division in the official letter of 13 December 2002 be reversed on the basis of the claims 1 to 10 annexed to the statement of grounds;

2. that the appellant be given the opportunity to file further arguments and/or amendments in case that the Board of Appeal is reluctant to allow the request under 1);

3. that a term for oral proceedings be arranged in case that the Board of Appeal cannot grant the request under 1).

Reasons for the Decision

1. The appeal is admissible.

2. The appeal is allowable since in the Board's judgement the decision of the examining division in refusing the application for lack of inventive step cannot be upheld, but ought to be reversed. Moreover, the decision is flawed by serious procedural violations, which too justifies to set aside the decision under appeal and to reimburse the appeal fee.

Allowability of claim 1

Amendments

3. The new claims filed with the statement of grounds directly correspond to the claims submitted to the examining division as auxiliary request on 21 August 2002. In claim 1, the only amendment (apart from a minor clarification) is that the feature "wherein a most-significant bit multiplexer (121) is provided at each sub-word boundary for shifting a carry overflow of the sum back to the corresponding sub-word of said result word" has been added at the end of the claim. This feature was apparently subject to the first instance examination since the main request on which the examining division decided in substance already included this feature.

Since, therefore, the amendments do not entail any significant changes to the invention as previously claimed, the Board has no concerns with admitting and considering amended claim 1 on its merits.

4. The requirements of Article 84 and 123(2) EPC are met: Up to the first occurrence of the word "wherein", claim 1 has, except for reference signs added and some minor amendments, the same wording as claim 1 originally filed. The remaining part of claim 1 starting with the word "wherein" defines adding sections and a configuration of multiplexers which have a clear support in Figures 3 and 4 (in particular multiplexers 121 to 124 and 201) in combination with column 6, line 22 to column 9, line 45 (citations refer to the A-publication). These features define the essential aspects of the "additional hardware required to perform averaging computations" described in column 6, line 22 ff. Moreover, the claim wording is sufficiently clear to allow the Board to examine the claimed invention on its merits (for some amendments still considered necessary by the Board see point 12 below).

Invention

5. The claimed invention concerns a type of parallel processor architecture in which an arithmetic logic unit performs, in response to a (common) instruction either an adding operation or an averaging (divide by two) operation in parallel on multiple data items. These data items have a lower precision (sub-words) than the full datapath width of the unit would allow (see A-publication, column 2, line 7 to column 3, line 10). The circuit features defined in claim 1 allow the unit to perform both operations essentially in a single machine cycle either on the full data width or at the sub-word level. The claimed structure can be implemented at low costs, it is efficient and flexible, and it has important applications in image processing (see A-publication, column 2, lines 35 to 37 and column 9, line 46 to column 10, line 30, and column 10, lines 45 to 52).

Novelty

6. The claimed invention has novelty in respect to the prior art cited in the first instance (Article 54 EPC).

Documents Dl and D2 disclose arithmetic logic units each of which comprises a number of adding sections (D1, for example, Figure 2: 16-bit CPU formed of four four-bit CPU slices; D2, Figures 5 and 6: signal averaging circuit comprising parallel arrangement of 4-bit binary adder and shift register). These units apparently add numbers and are suitable to shift the result and provide the average of the input numbers. Although these units have a 4-bit slice structure they cannot perform these functions individually at the 4-bit sub-word level since the carry-out and carry-in between two slices are connected directly, or via a logic designed to behave merely as carry look-ahead unit (see D1, Figure 2: Cn+4-Cn, Figure 3: Cn+x-Cn; document D2, Figure 6: C).

This is an important difference to the invention as claimed where the multiplexers handle the carry and overflow bits between the adding sections such that either a parallel averaging or a parallel adding operation can be achieved at sub-word level (or selectively under further instruction control on the entire word length).

Document D3 discloses a parallel digital adder which like the present invention allows independent operations at double word, word or sub-word level (byte or other data segments). To this end the carry logic allows for disabling carry transmit signals (see Figure 17, gates 120-127). The main difference to the invention is that the adder is not suitable to carry out any averaging or dividing function, nor even any shifting operation. This follows at the sub-word level from the carry and control circuitry which does, for example, not allow to shift a carry overflow from a sub-word adding stage back to the partial sum.

Document D4 discloses an analog-to-digital converter averaging every two samples of digitized input data. However, the A/D converter does not operate on sub-words nor can it be controlled to switch between adding and averaging sample data.

The remaining documents cited in the first instance proceedings disclose even more remote prior art; they are clearly not pertinent to the claimed invention.

Inventive step

The subject-matter of claim 1 is also not obvious from the available prior art (Article 56 EPC).

7. The assessment of inventive step normally starts from the closest piece of prior art and the technical problem solved for evaluating the inventive contribution provided by the claimed invention over the prior art. In the present case it might be arguable what this closest prior art is: an averaging or an adding unit, document D1 or document D3, for example. Since however the common instruction multiple sub-word processing is determinative of the functions provided by the claimed invention, the Board considers document D3 as the appropriate starting point for assessing inventive step.

8. In respect to the arithmetic logic unit disclosed in document D3 the invention is characterized in that the adding means generate, selectively, the sum and the sum divided by two of sub-words in response to a corresponding instruction and in that each of the adding sections has associated multiplexers and in particular a most significant bit multiplexer provided at each sub-word boundary for shifting a carry overflow of the partial sum back to the corresponding sub-word of the result word.

9. By these features the arithmetic logic unit is able to perform two operations, adding and averaging, selectively in response to common instructions at sub-word level (see A-publication, column 2, lines 29 to 42, and column 6, lines 22 to 30). The technical problem solved by the invention in respect to document D3 can thus be seen in providing the "additional hardware" required to perform averaging computations on the common instruction multiple data processor of document D3.

10. The carry and shift logic using multiplexers in essentially three different functions as defined in claim 1 solves this problem. The prior art cited does not nearly disclose the technical problem, nor does it hint to the necessary modifications of the carry and shift logic to implement the averaging operation at sub-word level. The self-evidence and common workbench character of these features as quoted by the examining division appear to be mere allegations, unfounded and untenable at least in the light of the prior art cited.

11. A different definition of the technical problem or a different starting point in the prior art would not result in a different assessment of inventive step. Adding to the functionality of a device, as argued by the examining division, and in particular endowing an adding device with an averaging function might indeed be considered obvious as a general idea of improving the prior art.

However, this could be done in various ways, for example by using dedicated hardware or a flexible software solution. But first, there is no hint in the prior art that the combination of adding and averaging functions should be implemented at the sub-word level. Second, there is no hint in the prior art cited how to design the hardware in order to provide an arithmetic logic unit which can be selectively operated in an adding and averaging mode at sub-word level (and optionally at full data path width) while avoiding complex modifications of the existing adder structures.

The examining division failed, despite the appellant's repeated and reasoned submissions, to provide any reasoned argument, let alone any evidence or proof that the skilled person striving to improve the functionality of a prior art device like the one of document D3 would first select the averaging function for this purpose, then decide to implement this function at sub-word level, and finally arrive at a specific hardware-solution as claimed, all these simply by applying the self-evident and the common workbench practice.

12. Hence, the Board judges that claim 1 is allowable on the basis of the prior art cited by the first instance. As a minor clarification, the term "interior multiplexer" at the end of the claim should, however, be amended to read "interior bit multiplexer" (see e.g. column 7, lines 1/2, 17/18 and column 8, line 27 of the A-publication).

Moreover, it appears to the Board that the present dependent claims and the description need adaptation to comply with the subject-matter of claim 1.

Procedural errors

13. The decision of the examining division is not reasoned as required by Rule 68(2) EPC.

The provision of Rule 68(2) EPC is restricted to "decisions of the European patent office which are open to appeal", which underlines the function of the reasoned decision as object and basis of appeal proceedings. Citing file documents is not a proper substitute for giving reasons in the decision, otherwise the mandatory provisions of Rule 68(2) EPC would be rather pointless. According to the practice of the EPO, the reasons given in the decision should thus be "complete and independently comprehensible, i.e. generally without references" (see Guidelines for Examination in the EPO, E-X, 5). Only exceptionally, where a clear-cut line of reasoning pertinent to the decision can be found in a file document, a plain reference might be acceptable and sufficient.

The Guidelines (loc.cit.) also state that "(t)he need for complete and detailed reasoning is especially great when dealing with contentious points which are important for the decision". Indeed, it must be clear from the decision why the substantial arguments submitted by the applicant failed to persuade the examining division to withdraw the objections.

14. In the present case, the reasons given in the decision under appeal do not meet the requirements: they are so incomplete and obscure that the Board is forced to speculate on how the examining division arrived at the conclusion or why the detailed arguments and comments submitted by the applicant in response to the objections had not been accepted. The sweeping reference to the records at the end of the decision, stating "(f)urther details are set out in the summons and the minutes to the oral proceedings", does not cure the lack of reasoning in the decision, this being all the more the case considering the content of the records referred to.

15. At a first glance, the examination seems to have been properly conducted: in three communications and, according to the minutes, also in the oral proceedings the examining division clearly communicated to the applicant, and upheld the objection of inventive step and the prior art on which the objection was based.

A closer inspection of the records, however, shows that regarding the decisive difference to the prior art, namely the combination of adding and averaging functions at a sub-word level, the reasons for lack of inventive step as presented by the examining division during the whole first instance procedure did not go beyond a sweeping judgment resorting to the self-evident, to a "common workbench implementation feature", to a "juxtaposition of known devices" and to a cursory reference to prior art documents.

16. Despite the applicant's submissions of reasoned arguments to the contrary, the examining division simply reiterated its general allegations and sweeping statements. This conduct - independent from the question whether the examining division was right or not on the merits - amounts to the denial of giving reasons and eventually deprived the applicant of the possibility to present meaningful comments on the grounds and evidence which proved to be decisive for the fate of the application.

17. Such a conduct does not comply with the right to be heard as enshrined in Article 113(1) EPC, which is a substantial procedural violation under the practice and case law of the EPO.

The procedural errors alone justify reversal of the decision under appeal. Moreover, reimbursement of the appeal fee is considered equitable for reasons of the substantial procedural violation (Rule 67 EPC).

18. Since claim 1 of the appellant's request has been found basically allowable by the Board, and hence no negative decision has been given on this request, the appellant's further requests for an opportunity to file additional arguments and/or amendments and for the arrangement of oral proceedings in case the decision under appeal could not be reversed on the basis of the present claims need not be considered at this stage of the proceedings.

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 for further prosecution.

3. The appeal fee is to be reimbursed.