T 0498/02 (Relative address calculations/FUJITSU) of 7.7.2004

Summary of Facts and Submissions

I. European patent application number 96 103 171.3 claiming a priority from 1995 generally relates to the field of processor design and, more specifically, to the execution of a relative control transfer instruction comprising an opcode and an instruction displacement field.

II. In the first instance, before the examining division, the applicant sought protection for a method of, and an apparatus for, calculating the target address of a relative control transfer instruction, the calculation using a sign extended displacement having D+1 bits and the instruction address. According to the method the target address was formed by determining a lower order and a higher order address portion, the lower order address portion by summing a D bits, lower order portion of the instruction address to the sign extended displacement, and the higher order address portion by either incrementing, decrementing or keeping unchanged the higher order portion of the instruction address, depending on the value of two control flags, the so- called en and op flags. These control flags were formed by the second highest order bit (op flag) and the third highest order bit (en flag) of the sum.

III. The examining division raised an obviousness objection relative to the US patent US-A-4 203 157 (document D1) published in 1980. In a decision posted in writing on 16. October 2001, the examining division refused the application for lack of inventive step. Having regard to document D1, the novel features were seen in the sign extension of the displacement, in adding less bits to the displacement than its length, and in the use of different control bits for the modification of the most significant part of the instruction address. The control bits op flag and en flag, however, produced the same results as corresponding control bits in document D1. The en flag directly corresponded to the result of the exclusive-OR operation carried out on the sign bit and the carry over from the 8-bit addition. The functionality of the op flag was the same as that of the separate use of the sign of the displacement in document D1. Choosing between these two alternative control signals was a normal design option.

IV. On 17 December 2001, the applicant filed a notice of appeal against the refusal decision, including an order for payment of the appeal fee. A written statement setting out the grounds of appeal and amended claims were filed on 21 January 2002.

V. In oral proceedings held before the Board on 7 July 2004, the appellant filed a further amended set of claims, claim 1 reading as follows:

"1. A method of calculating a target address from an address of a relative control transfer instruction and a displacement, the address having W bits and the displacement (320) being part of the relative control transfer instruction and having D bits, the method comprising the following sequence of steps:

(1) precomputing the lower order bits of the target address by:

(1a) sign extending (110) the displacement by one bit to produce a sign extended displacement having D+1 bits; and

(1b) adding (112) a first set (412) of bits comprising D-l lowest order bits of the relative control transfer instruction address to the sign extended displacement to form a sum having D+2 bits, the sum including a set of low order bits of the target address and two flag bits (en flag; op flag);

(2) storing (114) the D+1 lower order bits of the sum;

(3a) incrementing (222) a second set (330) of bits comprising the W-D+l highest order bits of the relative control transfer instruction address to form a prefix of the target address having W-D+1 bits if a second highest order bit (op flag) of the sum is low and a third highest order bit (en flag) of the sum is high;

(3b) decrementing (218) the second set (330) of bits to form the prefix if the second highest order bit (op flag) of the sum is high and the third highest order bit (en flag) of the sum is high;

(3c) setting the prefix equal to the second set (330) of bits if the third highest order bit (en flag) of the sum is low; and

(4) appending (214, 220, 224) to the prefix a third set (358) of bits comprising the D-1 lowest order bits of the sum which had been stored in step (2) to form the target address."

VI. In the oral proceedings on 7 July 2004, as well as before in a written communication annexed to the summons to attend oral proceedings, the Board expressed doubts regarding inventive step of the claimed invention in the light of document D1. In the oral proceedings, the Board drew the appellant's attention to the circumstance that a one bit adder whose carry was discarded was functionally an exclusive-OR gate and that therefore the 8-bit ALU 28 in combination with the exclusive-OR gate in document D1 fulfilled the claim definition of an adder adding D+1 bits comprising D-l lowest order bits of the relative control transfer instruction address to the D+1 bits of the sign extended displacement.

VII. According to the appellant, the invention was novel and inventive in the light of document D1, since the latter did neither disclose a sign extension of the displacement value, nor the adding operation providing a D+2 bit sum including a set of low order bits of the target address and two flag bits, nor the claimed sequence of steps necessary for carrying out the invention. The incrementing and decrementing operations were, according to the invention, executed only in response to the respective status of the flag bits and did thus neither require any additional storage space nor any superfluous and time-consuming precomputing of incremented or decremented address values like in document D1. The invention was thus distinguished clearly from the prior art address calculation and achieved considerable savings in resources and calculation time.

VIII. The Board announced the decision on the appeal at the end of the oral proceedings on 7 July 2004.

Reasons for the Decision

1. The appeal complies with the requirements of Articles 106 to 108 and Rules 1(1) and 64 EPC and is thus admissible.

Nevertheless, the appeal has to be dismissed since the application does not meet the requirement of inventive step as set out in Articles 52(1) and 56 EPC.

The requirement of inventive step is to be examined, in accordance with the practice and case law of the EPO, on the basis of the problem and solution approach.

Construction of claim 1

2. The problem and solution approach used to apply the inventive step requirement (see Case Law of the Boards of Appeal of the European Patent Office, 4th edition 2001, European Patent Office 2002, Chapter I.D) requires an analysis of the claimed invention and a comparison with the prior art on the basis of the technical features and aspects of the invention for determining the technical contribution provided to the prior art. In the present case, however, the method claims rather refer to mathematical concepts like a method of calculating or the steps of precomputing, sign extending, adding, forming a sum, incrementing, etc. and define abstract data constructs like an "en flag" and "op flag", a "prefix" and a "first (second, third) set of bits comprising D-l lowest (W-D+l highest) order bits".

3. The claim wording, if construed in isolation, might indeed be understood, outside of any technical context, as the definition of a purely abstract mathematical algorithm. Lack of inventive step which was the basis for the decision in first instance is, nevertheless, a viable basis for refusing the application since the claimed subject-matter also includes technical methods using a machine-code algorithm which is to be implemented by means of digital components like those shown in figures 3 to 6 and described in column 5, lines 12 ff. of the present application.

4. In such digital circuits, data are encoded in electrical signals transmitted over separate bit lines. In the light of the embodiments described in the present application, terms like address, displacement, sum, and set of bits should thus be construed as meaning any signal or number of signals encoding information meeting the data definitions on a logical level.

5. Terms like adding or forming a sum in the present context have a meaning different from non-digital arithmetic. The result of the summing operation may include additional sign bits and bits which are not related to the arithmetical sum at all.

Moreover, the definition of the "first set of bits" using the expression "comprising the D-l lowest order bits of the ... address" is normally construed to mean that the first set of bits may be preceded by a number of leading higher order bits having any binary value. The "sum" of which the first set of bits is an addend (present claim 1, step (1b)) may thus have any value in the higher order bits, in particular in the 2nd and 3rd highest order bits which form the en and op flags.

6. Therefore, the definition of the en and op flags in claim 1, step (1b) as result bits of the summing operation leaves the bit values of these flags actually undetermined. It is only through steps (3a) to (3c) that these values are implicitly defined by the use of these bits as condition flags. Since, however, the op flag is not effective if the en flag is zero (low) (see also figure 2, steps 212 to 215), any bit value of the op flag in combination with the en flag not equal 1 (high) meets the claim definitions of these control bits.

7. Finally, the second set of bits is either incremented, decremented or kept unaltered to form the prefix (steps (3a) to (3c) of claim 1), dependent on the values of the en and op flags. Claim 1 only defines the if and why but not the how and when the arithmetic is performed; the claim wording defines a purely logical relationship between flag status and the prefix calculation. The claim wording hence encompasses embodiments where the high order address bits are incremented and decremented, respectively, in advance, in anticipation of a possible carry or borrow carried over from the adding operation. Such an embodiment indeed finds support in the present application, column 5, lines 7 - 11, indicating that "a copy of them (the most significant control transfer instruction address bits) is incremented ... or decremented".

Inventive step

8. Comparing the present invention and prior art document D1, a number of common features emerge.

8.1. Both deal with the calculation of a target address by adding a displacement, which is part of the relative control transfer instruction, to the memory address of the relative control transfer instruction (see for example document D1, abstract).

Step (1)

8.2. More specifically, the two operands in document D1 are a 2's-complement 8 bits offset value and a W = 16 bits address word. The offset value is received from the program memory and transmitted over an 8 bits wide data bus 6 (DB) to an arithmetic logic unit 28 (ALU). The address word is byte-structured in A0-7 and A8-15 transmitted over a low order address bus 2 (ABL) and a high order address bus 10 (ABH), respectively (see document D1, column 4, lines 66 ff. and column 5, lines 1 ff. and figure 1).

The lower order bits of the target address (bits A0-7 on ABL, see document D1, figure 1) are precomputed (first clock cycle following the high to low transition of the clock signal Phi2', see document D1, figure 2 and column 4 , lines 13 ff.).

8.3. Since in document D1 the arithmetic logic unit operates on the lower order byte of the address word and appends the 8 bits sum to the higher order byte in forming the target address, the lower 8 bits of the address word is the "first set of bits comprising D-1 lowest order bits of the relative control transfer instruction" in the sense of present claim 1 (see claim 1, steps (1b) and (4)), which fixes the value of D to be equal 9.

Step (1a)

8.4. In document D1 (see figure 6) a buffer circuit develops a control signal DB7, which encodes the sign bit of the offset value input to the arithmetic logic unit ALU 28. According to the prior art circuit and method of document D1, control signals D76 and DEC are provided at the output of inverter 101 (figure 6) and at the output of inverter 112 (figure 7), respectively, both control signals encode the sign bit of the offset value (see document D1, column 9, lines 2 to 4 and lines 58 to 61).

As explained in point 4 above, the various data constructs in present claim 1 should be construed to include bundles of binary signals on separate signal lines if they meet the respective functional definition. The control signals D76 and DEC together with the binary signals on bus lines DB0-7 encoding the 8 -bit offset word are thus to considered as a "sign extended displacement" in terms of present claim 1.

Step (1b)

8.5. According to document D1, the adding operation is performed in two stages: first the ALU 28 adds two 8 bits wide operands and produces a 8 bit sum value plus a 1 bit carry / borrow encoded in control signal B7C. The second stage, the exclusive OR-gate 117, adds the carry-borrow on B7C to the sign bit encoded in D76 (see document D1, figures 5 and 7 and, for example, column 11, lines 33 to 37).

Present claim 1 does not to specify any specific features of an adding device or summing algorithm, except for the indication of the bit width of the sum. The adder may be designed by means of discrete logic, a mix of discrete and integrated components or a fully integrated circuit.

The Board, therefore, holds that the adding operation as disclosed in document D1, which is performed in two separate components, the ALU 28 and the exclusive-OR 117, meets step (1b) of claim 1, except for the feature that the bit width of the sum produced is one bit wider than in document D1. In the present invention, however, this highest order bit of the sum is not used; in the embodiment of figure 4, for example, the corresponding bit line 428 is shown unconnected (see also column 6, lines 3 to 5 of the application).

8.6. In document D1, the signals produced on the output of the exclusive-OR 118 and the control conductor 66 (DEC signal) carry binary information used to select the output of the INCH block 12 or the TEMPH register 16 onto ABH bus 10, thus in effect forming a prefix of the target address by using the in-, decremented or unaltered high order byte of the relative control transfer instruction address.

The control scheme in document D1 is essentially the same as defined in present claim 1 and described in the embodiment of figure 4. In particular, control signals 118, 66 meet all of the conditions set out for the op and en flag values in steps (3a) to (3c) of the claim. The op flag on line 332 and the en flag on line 334 of figure 4 of the present application differ from the corresponding values of the control signals 118, 66 in document D1 only if both the en and op flag are 0, i.e. when the displacement is negative but the borrow to the higher address portion is zero and no distinction has to be made between a positive or negative displacement in selecting the high order address byte. In the very same situation, the control signal on the output of exclusive-OR gate 117 is low and the DEC signal (on line 66, for example) is high. If no carry or borrow has been produced and no distinction relative to the polarity of the displacement has to be made however, the values of the op flag as well as of the DEC signal are irrelevant from a technical point of view. In any case, this difference needs not be considered further since the subject-matter of claim 1 covers any value of the op flag when en flag equal 0 (see step (3c)).

Step (2)

8.7. The D-1=8 lower order bits of the sum are stored in an output buffer circuitry coupled to the NDB bus 8 (see document D1, column 5, lines 43 to 48). Furthermore, the two control signal are dynamically stored on the respective inputs of gates 112 and 130 (see document D1, figure 7) so that D+1 bits corresponding to the D-1 lower order bits of the sum and the two flag bits of the sum are stored.

Steps (3a) - (3c)

8.8. In document D1 a copy of the high order address bits is incremented or decremented by means of INCH 12, TEMPH 16. and ABH 10 (see document D1, figures 1, 2, and 7 with column 9, lines 5 to 64, and column 11, lines 2 to 26). As indicated above steps (3a) to (3c) of claim 1 encompasses such an embodiment wherein the high order address bits are incremented or decremented in advance, in anticipation of a possible carry or borrow carried over from the adding operation.

Step (4)

8.9. In document D1 the high order address byte output either from block TEMPH register 16 or from INCH block 12. forms the prefix to which a third set of bits, i.e. the low order byte output by ALU 28 onto NDB bus 8 and stored in the output buffer circuitry, comprising the D-1 lowest order bits of the sum is appended.

8.10. In summary, the method of present claim 1 differs from the prior art of document D1 only in the following:

(A) According to claim 1 the displacement has one more bit (D bits) than the lower order part of the target address (D-1 bits), whereas in document D1 the displacement and the lower order byte of the target address have the same bit width (D-1=8).

(B) The sum produced in the adding operation has D+2 bits, the (D+1)th bit apparently being a redundant carry, whereas in document D1 such a redundant (D+1)th bit is not produced at all.

8.11. These differences, however, do not involve an inventive step.

Choosing the bit width of the address and displacement (difference (A)) is a matter of convenience, depending on the hardware and type of processor used. The skilled person knows that the prior art method of document D1 would work for any magnitude of the displacement up to a maximum equal to the maximum of the lower address portion, i.e. for a bit width without the sign bits up to the bit width of the lower address portion (see the example described in document D1, column 3, lines 12 ff. and in particular the statement in column 4, line 66 to column 5, line 5).

Choosing the maximum range of the displacement is a normal design option which, depending on the hardware, may or may not have advantages. In the embodiment of figure 4 of the present application the choice seems to be rather disadvantageous since the D+1 bits adder 420 could have a bit width of one bit less if the sign bit 418 was used directly instead of the op flag 332, like in document D1. On the other hand, starting from the circuit and method of document D1, and having only a nine bits adder available, for example, the skilled person would consider it obvious to sign extend the data at inputs A and B of ALU 28 and to discard the superfluous, highest bit of the sum, thereby fully anticipating the above claim features, without having to modify in any other aspect the method of document D1.

Producing first in the summing operation a D+2 wide value and then discarding the highest order bit (difference (B)) does not solve any technical problem but is rather an unwanted collateral effect of using such an adder circuit, which is oversized by one bit. A physical feature which does not serve any technical purpose, however, does not provide a technical contribution to the prior art which could support the patentability of such an invention.

In summary, the claimed invention relative to the prior art circuit and method of document D1 has the character of a normal design option, which is considered obvious within the realm of general technical knowledge. On the basis of claim 1, the patent application does thus not meet the requirements of Articles 52(1) and 56 EPC.

ORDER

For these reasons it is decided that:

The appeal is dismissed.