T 0479/94 (OKI ELECTRIC/Random number generator) 31-07-1995
Download and more information:
Random number generator
Inventive step (yes)
Procedural violation - (yes)
I. The appellant contests the decision of the Examining Division to refuse European patent application No. 90 302 630.0.
II. The refusal was issued on 28 January 1994 following a single official communication dated 28 July 1993 to which the appellant had filed a reply on 29 October 1993 (dated 26 October 1993). The refused claim 1 reads as follows:
A random number generator comprising oscillator means for generating clock pulse signals and a plurality of number generating means, for generating signals representing numbers in response to the clock pulse signals, to thereby generate a random number,
Characterised in that
the number generating means each include a counter for counting clock pulse signals to generate respective count values, the random number generator is formed in a clocked logic integrated circuit including a bus and read signal producing means connected for causing the number generating means to output the current count values of the counters, and said current count values are applied directly to said bus.
This claim is distinguished from the claim 1 filed on 22. June 1991 (in response to the search report) and criticized in said single communication in that it is in the two-part form and in that it is stated that the count values of the counters, and not as in the former claim the number generating means, are applied directly to the bus.
III. The reason for the refusal was that the subject-matter of independent claim 1 filed with the reply on 29. October 1993 lacked an inventive step having regard to the following prior art documents:
D1: IBM Technical Disclosure Bulletin Vol. 28, No. 6 November 1985, pages 2303 and 2304, and
D2: JP-A-61 163435 (abstract).
III. (a) It was said in the decision that the sole difference noted in claim 1 compared to the former claim lay in the delimitation thereof against the teaching of D1. In paragraph VI, it was said that (refused) claim 1 was considered to correspond in substance to claim 1 as filed on 22 June 1991. The Examining Division, therefore, referred to its single communication and stated that in said communication it had been considered that claim 1 filed on 22 June 1991 did not involve an inventive step for the following reasons (arguments (a) to (c) are identical to those in said single communication):
"(a)... D1 describes a random number generator... (see D1, figure) for generating random numbers comprising oscillator means (see D1, page 2304, lines 3-5) for generating clock pulses independent of said system clock, and a plurality (two) of number generating means (see D1, figure, references 1-4) for generating random numbers in response to the clock pulse signals, bus means (see D1, figure, bunch of lines connecting each shift register to the corresponding data selector, and a read signal (IORD*) producing means for causing the number generating means to output the random number directly onto the bus.
(b) Document D1, which is considered to represent the most relevant state of the art, discloses a device from which the subject-matter of claim 1 differs only in that said number generating means of D1 do not comprise a counter and in that the random number generator of D1 is not formed in a "clocked logic integrated circuit".
(c) The integration feature is not considered as a feature adding any inventive contribution to the prior art. The technique of integrating circuits is well known in the field. Integrating the device of D1 is in accordance with the skilled person's needs. No particular effect occurs apart from those which can be contemplated in advance directly linked to integration."
The decision (paragraph VI) went on to repeat the following arguments from the said single communication, however, with a change in substance in the sentence containing the expression printed with bold letters (the original text of the corresponding expression in the said single communication is given in brackets):
"The feature relating to the number generating means incorporating a counter is a matter of normal design procedure since it is known, e.g. in document D2, that number generating means incorporating a counter have already been employed for the same purpose i.e. generating random numbers. Thus, a counter used in the present application ["the number generating means incorporating a counter"] is considered as being equivalent to the number generator implemented as a combination of a shift register and an EXOR gate described in document D1 and can be interchanged with that feature where circumstances make it desirable and thus provide the same effect. The skilled person would thus be led automatically to a device as claimed in claim 1.
It thus appears that the combination of features defined in claim 1 as filed with applicant's letter dated 22 June 1991 does not involve an inventive step according to Article 56 EPC."
It was, moreover, stated at the end of paragraph VI that "Since independent claim 1 as filed with applicant's letter dated 26 October 1993 corresponds in substance to independent claim 1 as filed with applicant's letter dated 22 June 1991 [should be: filed on 22 June 1991] the same opinion applies to current independent claim 1".
III. (b) After the above statement concerning lack of inventive step, the Examining Division in its decision met some of the appellant's (then applicant's) arguments in its letter dated 26. October 1993, and made (under paragraph VII) for the first time in the proceedings the following alternative interpretations of the device disclosed in D1, discussing, in particular, which parts of the device disclosed in D1 should be identified as the "bus" and the "random number generator":
- The selector means of D1 could be considered to be part of the bus of D1 so that one could consider that the output of the random number generator was directly applied to the bus.
- Instead one could consider that the selector means of D1 were included within the random number generator. Also in this case the current values of the outputs were directly applied to the bus.
- Were the selectors to be expanded to enable all data to be passed, then the selectors, in fact, would "disappear".
IV. The applicant lodged an appeal against this decision on 25. March 1994, paying the appeal fee the same day. In its grounds of appeal, filed on 1 June 1994, the appellant submitted that the manner in which the application had been rejected constituted a substantial procedural violation and that the decision was ill-founded.
V. In a communication pursuant to Article 110(2) EPC, dated 26. September 1994, the rapporteur expressed the preliminary view that it would not be possible to set aside the contested decision.
VI. On 3 February 1995 the appellant submitted further arguments as well as a new set of claims.
As regards inventive step, the appellant's arguments may be summarised as follows. It was not reasonable to mosaic D1 and D2. D1 described a complex circuit for generating a random number including two shift registers, two sets of EXOR gates, two data selectors and an AND gate. D2, on the contrary, required a counter, a RAM and an arithmetic circuit. Neither document provided any hint that its contents should be modified on the basis of the disclosure of the other. Furthermore, counters were deterministic devices and generally avoided when a source of random number was required. The inadequacy of directly using the output of one counter was recognised in D2 since a RAM was used to shuffle bits of the counter output when a large number was required; it would have gone against the teaching of D2 to omit the RAM. The present invention, however, solved the problem in an alternative way by using two counters directly coupled to the system bus. This was non-obvious in spite of the use of two shift registers in D1 since in this document the purpose of doubling the circuits was not to improve the randomness of the generated number.
In respect of a procedural violation ,the appellant submitted inter alia that the Examining Division had introduced new grounds on which it had had no opportunity to comment in its statement of reasons for the decision to refuse.
VII. In a second communication, the rapporteur indicated that an amended main claim might be judged allowable. If such a claim was filed, the issue of procedural violation might be decided in favour of the appellant.
VIII. On 22 May 1995 the appellant filed amendments to the description and the claims in accordance with the Board's communication. Claim 1 reads (omitting the reference signs):
A data processing integrated circuit comprising data processing circuitry including a system bus and a system clock, and a random number generator, wherein the random number generator comprises oscillator means arranged to produce clock pulse signals independent of the system clock, a plurality of counters arranged to generate numbers by counting the clock pulse signals and read out means responsive to a read signal from the processing circuitry to apply the counter contents directly to the system bus.
IX. The appellant requests the grant of a patent on the basis of the following documents:
Claims:
1. to 4 filed on 22 May 1995
Description:
Pages 4 to 9 as originally filed,
Pages 1 to 3 filed on 22 May 1995
Drawings:
Sheets 1/3 to 3/3 as originally filed
1. The appeal is admissible.
2. Amendments
2.1. The Board is satisfied that the amendments to the application do not infringe Article 123(2) EPC.
2.2. The one-part form of claim is considered appropriate, since the cited references do not disclose a data processing integrated circuit - in particular one having a system clock - in the sense of the invention, which integrated circuit has to be provided with a random number generator (cf. the introductory part of the description, the first ten lines).
3. Inventive step
3.1. D1 describes a random number generator based on three elements (integrated circuits), namely a shift register, EXOR gates, and a data selector. The shift register and the EXOR gates cooperate to form an eight-bit number on the outputs of the register; of these eight bits, four are selected under the control of a binary signal from a microcomputer applied to the data selector. The three elements thus make up a unit which delivers a four-bit random number. The random number generator comprises two such units so that an eight-bit number is accessible on the outputs of the pair of data selectors.
3.2. D2 describes a random number generator comprising a counter, a RAM, and an "arithmetic circuit". The counter keeps running until a random number is requested. The current counter value is stored in the RAM. This number is not output directly; instead, its low-order bits - which change more quickly and are therefore more "random" than the high-order bits - are extracted and applied as output signal. Alternatively, if the full number of bits are required, the low-order bits and high-order bits are switched.
3.3. Since the invention as claimed in claim 1 is clearly novel with regard to D1 and D2 and also non-obvious with regard to D1 and D2 taken separately, the question of inventive step boils down to the question whether the skilled person would have combined the teachings of D1 and D2, and whether in such a case he would have arrived at the invention as claimed.
In its communication dated 14 March 1995, the Board's provisional view was that the prior art identified by D1 did not appear to provide the closest prior art. Nevertheless, were it to be considered that the starting point of the invention was the teaching of D1, the technical problem could be regarded as the simplifying of a comparatively complex circuit in order to save space on an integrated chip (cf. the description of the present application, pages 1 and 2).
With this problem in mind, the skilled person would search for a suitable replacement circuit. He would discover D2 which suggests using a free-running counter for generating a random number. Clearly such a counter, although simple, would not be ideal; as the appellant has pointed out, if random number requests are made at regular intervals the output will consist of a repeating pattern of numbers. However, this sole drawback would probably not have led the skilled person - who would have expected that a design simplification could only be achieved by accepting a certain quality reduction - to disregard D2. Instead, the simplicity of the counter in D2 compared with the shift registers and gates in D1 could, in the Board's view, have been a clear incentive to contemplate a combination of the two teachings.
3.4. It remains however to examine whether an obvious combination of D1 and D2 actually results in the subject-matter of claim 1.
In D1, each half of the random number generator consists of a shift register, EXOR gates and a data selector. The Board estimates that the skilled person would have considered replacing these circuits by the arrangement known from D2, which includes not just a counter but also a RAM and an "arithmetic unit".
The subject-matter of claim 1 differs from such a straight-forward combination in particular in that the counter contents are applied directly to the system bus. This feature, the appellant argues, was not obvious since the RAM and the arithmetic circuit are vital for the proper functioning of the random number generator of D2.
3.5. The Board agrees with this view. D2 does not teach that the output of the counter should be used directly as a representation of a random number; instead, by means of a RAM and an arithmetical circuit, bits are either omitted or switched before being output on the system bus. This measure serves to increase the degree of randomness of the generated numbers. The two circuits thus appear essential for the proper working of the circuit. The skilled person would not have omitted them without a good reason for doing so. In the Board's view, the existence of such a reason has not been demonstrated. Certainly, the overall technical problem consists in achieving a simplification of a random number generator, but such a general aim cannot be regarded as a sufficient incentive to exclude an essential part of a prior art device.
Thus, a combination of D1 and D2 does not yield the subject-matter of claim 1. It follows that the present invention involves an inventive step.
4. Procedural violation
4.1. The Examining Division issued a single communication before refusing the present patent application (see paragraph II above). In said communication, the main argument was that the subject-matter of claim 1 lacked an inventive step for the reason that it would have been obvious to substitute the number generating means incorporating a counter known from D2 for the generator implemented as a combination of a shift register and an EXOR gate described in document D1 (see paragraph III(a) above wherein the cited parts of the decision are repetitions - with an exception as shown - taken from the said single communication). The communication stated in conclusion that it appeared to be difficult to overcome all the objections raised in the communication and that it would appear that the application should be refused.
However, it was stated that "should the applicant nevertheless regard some particular matter as patentable an independent claim including such particular matter should be filed [the numeration has been introduced by the Board]
(i) taking account of Rule 29(1) and (7), 27(1)(b) [based on D1 and D2] and (c) EPC.
The applicant should also indicate in the letter of reply
(ii) the difference vis à vis the state of the art and
(iii) the significance thereof especially concerning the requirements of Article 54(1) and (2), and 56."
4.2. In reply to said single communication, the appellant (applicant) filed a new main claim on 29 October 1993 in the two-part form, delimited against the teaching of D1 and having reference signs within parentheses. It contained the feature that the count values of the counters are applied directly to the bus. This constituted a limitation of the previous version of claim 1 according to which the output of the number generating means (including counters) were applied directly to the bus. This difference was pointed out in the accompanying letter.
The appellant (applicant), moreover, expressed the opinion that the "bunch of lines connecting each shift register to the corresponding data selector" in D1 which had been identified by the Examining Division as a bus could not be regarded as a bus; the appellant thereby referred to Collins English Dictionary to prove his point. The appellant also, having regard to the fact that the Examining Division had identified in the device according to D1 a combination of a shift register and a set of EXOR gates as a number generating means in the sense of claim 1, pointed out that the function of such combination could not be compared with the function of the counters according to claim 1, since according to D1, even when considering the said bunch of lines as a bus, the values output by the shift registers were further processed by data selectors.
The appellant (applicant), moreover, submitted that also D2 taught that further processing of the count values by means of a RAM was required and that the skilled person would not consider using the count values directly without the application of inventive skill (page 2, second full paragraph, last sentence; page 3, top).
Moreover, it was pointed out in the reply that claim 1 was directed to a random number generator circuit which was integrated onto a chip having a different primary function, the performance of which might require the use of random numbers. The simple circuit of the present invention required a very little area on a chip and, therefore, was much more suitable than an "added on" functional block. The prior art did not teach the integration of a random number generator with a circuit having another primary function.
4.3. In view of the foregoing, the appellant (applicant) tried to overcome all the objections mentioned in the Examining Division's communication by
- filing the claim in the two-part form having reference signs and suggesting that the description should be adopted once allowable claims were indicated;
- amending claim 1 by the limiting feature that "said current count values are applied directly to the bus";
- clearly explaining the difference between the subject-matter of claim 1 and the devices of the two prior art documents at issue, in particular pointing out that the Examining Division's identification of the "bus" in D1 could not be correct and that the random number generator in D2 had a RAM connected to the output;
- indicating the significance of said difference in considering inventive step;
It is considered that the amendment of the claim changed the subject-matter of the claim considerably having regard to the teaching of the documents cited. This amendment was clearly intended to restrict the claim, bearing in mind both the teaching of D1 and that of D2, since these documents did not show counters outputting count values directly onto a bus. Although the appellant (applicant) did not agree with the Examining Division's identification of "bus", he pointed out that - would said identification be accepted - the combination of D1 and D2 could still not lead to the invention, because the values output from the shift register (number generating means) in D1 required further processing (by the selector) in the random number generator of D1. Also the count values of the device of D2 were further processed (by a RAM).
By complying with the invitation of the Examining Division to amend claim 1 and to defend it in the light of the prior art, it appears that the appellant (then applicant) hoped to overcome objections as regards inventive step. The efforts of the appellant are therefore considered to represent a bona fide attempt to overcome these objections.
4.4. According to Article 113(1) EPC, the decisions of the European Patent Office may only be based on grounds or evidence on which the parties concerned have had an opportunity to present their comments.
Arguably, the expression "based" leaves some freedom to an Examining Division to complete or refine in a decision an argument which has been presented before. However, if an independent claim has been amended to include features which the Examining Division has not previously considered, a further communication will normally have to be sent before a decision to refuse is taken. Exceptions to this principle would be limited to cases when the amendments are trivial or of a purely clarifying nature; an additional remark in the decision would then hardly form the basis for the argumentation.
4.5. It appears that the real decision concerning the inventive step of the subject-matter of claim 1 is given in paragraph VI of the appealed decision (see III(a), above). The decision is distinguished from the said single communication in that a shift was made from the original expression "the number generating means incorporating a counter" to "the counter used in the present application". Apparently this change was provoked by the new feature introduced into the claim. The Examining Division apparently considered this shift in the language as a refinement in the argumentation.
The Board, however, does not share this view. The original expression related to the number generator means disclosed in D2. That number generator comprises a counter the output of which is connected to a RAM, the output of which in turn is connected to an arithmetical circuit. It would seem that the Examining Division was of the opinion that the number generator according to D2 after the amendment of claim 1 would not fit when combining the teachings of D1 and D2 and, therefore, changed its reasoning. The substance of this reasoning, however, was new and the appellant (applicant) did not have an opportunity to present its comments on this new ground, which was new at the least in the sense that the interpretation of the most relevant document was changed in order to attack the inventive step of the invention.
It is, moreover, noted that the Examining Division, in this part of the decision (paragraph VI - cf. III(a) above), did not address the appellant's (applicant's) arguments according to which the bunch of lines identified as a "bus" in D1 by the Examining Division could not be considered to be a bus. Therefore, even if the said shift register is identified (together with the set of EXOR gates) as a counter it is not clearly understood from the decision (i.e. paragraph VI - cf. III(a) above) how the skilled person could be led to the invention, since the device according to D1 has selectors, further processing the outputs of the shift register.
It appears in fact, that also the additional arguments in paragraph VII in the decision (corresponding to III(b) above), following the statement of lack of inventive step (paragraph VI - cf.III(a) above), have to be considered as part of the decision - and not only as an alternative argumentation - since all these arguments are aimed at shifting the "bus" from being the said bunch of lines between the data selector and the shift register - as proposed in the said single communication - to be the output of the selector. These arguments, however, are all new and the appellant (applicant) had no possibility to present any counter arguments thereto.
3.6. The Board, therefore, considers that the Examining Division's comments, advanced for the first time in the decision, were indeed the basis for at least part of the decision since they were aimed at refuting newly presented arguments. Thus the appellant did not have an opportunity to present its comments with regard to the grounds of refusal of the amended claim 1. This is, however, both necessary and appropriate in the light of Articles 113(1) and 96(2) and the requirements according to Rule 51(2) and (3) EPC.
All this amounts to a substantial procedural violation which renders the contested decision void.
This also constitutes a procedural violation within the meaning of Rule 67 EPC and it is clearly equitable that the appeal fee should be refunded in the circumstances of this case.
ORDER
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the Examining Division with the order to grant a patent on the basis of the current application documents.
3. Reimbursement of the appeal fee is ordered.