Die DE 3631992 C2 offenbart einen Kryptographieprozessor zum Durchführen des RSA-Public-Key-Kryptosystems. Hierbei wird eine modulare Exponentiation mit einer Basis, einem Exponen- ten und einem Modul in eine Vielzahl von Drei-Operanden- Additionen zerlegt. Die drei Operanden umfassen einen Modulo- peranden N, einen Multiplikanden-Operanden C und einen Zwi- schenergebnis-Operanden Z. Durch entsprechende Verschie- bung/Gewichtung der drei Operanden vor der Addition kann eine durch einen Multiplikations-Look-Ahead-Algorithmus und einen Reduktions-Look-Ahead-Algorithmus beschleunigte Multiplikati- on/Reduktion durchgeführt werden.

Fig. 7 zeigt einen Ausschnitt aus dem Addierwerk, das gewis- sermaßen das Herz des Kryptographieprozessors darstellt, der in der DE 3631992 C2 dargestellt ist. Im einzelnen zeigt Fig.

7 zwei aufeinanderfolgende Bit-Slices, um die zwei Summenbits i-1 und i zu berechnen, und zwar aus den drei Eingangsoperan- denbits Ci, Ni, Zi bzw. Ci1, Ni-1, Zi-, bzw. aus Ci_2, Ni2 und Zi-2.

Die Drei-Operanden-Addition von C, N, Z wird, auf Bitebene betrachtet, in eine zweistufige Operation zerlegt. Zur Aus- führung der ersten Stufe der Operation ist ein Drei-Bit- Halbaddierer 80 vorgesehen, wobei jedem Drei-Bit-Halbaddierer 80 ein Zwei-Bit-Volladdierer 81 nachgeschaltet ist. Der Drei- Bit-Halbaddierer liefert zwei Ausgangsbits xi, yi, wobei die Ausgangsbits xi, yi in die nachgeschalteten Zwei-Bit- Volladdierer so eingespeist werden, wie es in Fig. 7 darge-

stellt ist. Im einzelnen wird in jedem Zwei-Bit-Volladdierer eines Bit-Slices das niederwertige Bit yi am Ausgang des Drei-Bit-Halbaddierers mit dem hochwertigen Bit der um eine Ordnung niedrigeren Drei-Bit-Halbaddiererstufe (xi1) in dem Zwei-Bit-Volladdierer 81 kombiniert, um ein Summenbit 82 so- wie ein Übertragbit 83 zu berechnen. Die Drei-Operanden- Addition wird also in zwei Abschnitte unterteilt. Im ersten Abschnitt wird an jeder binären Stelle eine Summe der drei Bits der Operanden gebildet. Die Summe kann die Werte von 0 bis 3 (in Dezimaldarstellung) annehmen. Die Summe ist also binär mit den zwei Bits x, y darstellbar. Da die Summe an je- der Stelle gebildet wird, können aus den zwei Summenbits zwei neue Zahlen zusammengestellt werden.

Im zweiten Abschnitt werden die beiden Zahlen auf übliche Art und Weise durch den Zwei-Bit-Volladdierer 81 addiert. Die Verschaltung, derart, daß ein Zwei-Bit-Volladdierer immer zwei Ausgangsbits von zwei unterschiedlichen Drei-Bit- Halbaddierern als Eingabe erhält, führt zu einer Verlängerung des Rechenwerks um ein Bit.

Der in Fig. 7 gezeigte Drei-Operanden-Addierer ist dahinge- hend problematisch, daß weder eine Sicherung der Eingangsope- randen C, N, Z noch eine Sicherung der"Zwischenoperanden"x, y vorgesehen ist. Dies ist dahingehend problematisch, daß be- sonders in dem normalen Fall, in dem alle Schaltungen in CMOS-Logik ausgeführt sind, das Umschalten eines Bits von 0 auf 1 bzw. von 1 auf 0 zu einem Stromimpuls führt, der be- ginnt, wenn ein Bit-Zustand umgeschaltet wird. Bekanntlich verbrauchen CMOS-Schaltungen im statischen Zustand keinen Strom. Im Umschaltzustand haben sie jedoch einen Stromver- brauch. Dieser Stromverbrauch ist durch eine Leistungsanalyse eruierbar. Damit ist es grundsätzlich möglich, Informationen über C, N, Z abzuleiten, um beispielsweise auf den geheimen Schlüssel Rückschlüsse zu ziehen, der in einer RSA-Operation verwendet wird.

Ein Angreifer könnte beispielsweise durch Aufnahme des Strom- profils ermitteln, ob eine Umschaltung von 0 auf 1 oder von 1 auf 0 stattgefunden hat. Bei einer ungesicherten Schaltung würde immer dann eine Umschaltung eines Bits auftreten, wenn im Stromprofil eine Stromspitze erkennbar ist. Ein Angreifer kann daher das gesamte Umschaltverhalten eines Rechenwerks anhand des Stromprofils nachvollziehen. Der Angreifer bräuch- te dann lediglich noch ein einziges Bit in einer ganzen Se- quenz, um daraus rekonstruieren zu können, ob die Umschaltung von einer"1"auf eine"0"oder umgekehrt stattgefunden hat.

Bestimmte CMOS-Schaltungen haben ferner die Eigenschaft, daß die Umschaltung von 0 auf 1 einen anderen Stromverbrauch mit sich zieht als die Umschaltung von 1 auf 0. In diesem Fall sieht ein Angreifer durch einen Vergleich von zwei unter- schiedlichen Stromspitzen unmittelbar, welche Bits im Rechen- werk verarbeitet worden sind.

Als Abwehrmaßnahme gegen solche Leistungsanalyseangriffe wur- de vorgeschlagen, eine sogenannte Dual-Rail-Technik einzuset- zen. Bei der Dual-Rail-Technik wird prinzipiell betrachtet jeder Signalweg doppelt ausgeführt. Auf dem ersten Signalweg wird beispielsweise ein Signal x normal verarbeitet. Auf dem zweiten, in demselben Chip integrierten, Signalweg wird nicht das Signal x verarbeitet, sondern das komplementäre Signal x. Dies führt dazu, daß immer dann, wenn in der Signallei- tung ein Übergang von beispielsweise 0 auf 1 stattfindet, in der anderen Leitung, also der zweiten"Rail", ein komplemen- tärer Übergang stattfindet. Für jeden Bitübergang finden da- her auf beiden Leitungen immer beide Übergänge statt. Dies führt dazu, daß für Schaltungen, bei denen Übergänge von 0 auf 1 und 1 auf 0 unterschiedlich viel Strom brauchen, nicht mehr eruierbar ist, ob ein Übergang von 0 auf 1 oder von 1 auf 0 stattgefunden hat. Dies liegt daran, daß das Strompro- fil für jeden Schaltungsübergang eine Spitze enthält, die die Überlagerung des Stromverbrauchs der beiden Rails ist. Die Dual-Rail-Technik liefert eine hohe Sicherheit, jedoch mit

dem Nachteil, daß alle Schaltungen normalerweise doppelt aus- geführt werden müssen und daß der Leistungsverbrauch der ge- samten Schaltung ebenfalls doppelt so hoch ist. Dafür ist die Schaltung jedoch bereits in gewissem Umfang gegenüber Lei- stungsanalyseattacken immun.

Wird lediglich eine Dual-Rail-Technik eingesetzt, so ist an- hand des Stromprofils immer noch zu erkennen, ob ein bestimm- tes Bit von 0 auf 1 bzw. von 1 auf 0 übergegangen ist oder im Vergleich zum vorigen Taktzyklus gleichgeblieben ist. Im Fal- le eines Bitübergangs ist nämlich eine Leistungsspitze er- sichtlich. Die Leistungsspitze ist jedoch nicht ersichtlich, wenn ein Bit von einem Zyklus zum nächsten beispielsweise auf 1 oder auf 0 geblieben ist, sich also nicht verändert hat.

Zur Abwehr von Angriffen, die auf diesem Effekt basieren, wurde vorgeschlagen, die Dual-Rail-Technik um einen Prechar- ge/Predischarge-Modus zu ergänzen. Die Schaltung wird abwech- selnd in einem Datenmodus und einem Vorbereitungsmodus (Precharge/Predischarge) betrieben. Jedem Datenzyklus geht ein Vorbereitungszyklus voraus, in dem im Falle von Precharge beide Rails, also beispielsweise x und x auf"1"vorgeladen werden, um dann, in dem Datenmodus, zu verarbeitende komple- mentäre Eingangssignale in die beiden Rails zu speisen. Dies führt dazu, daß immer, von einem Datenzyklus zu einem Vorbe- reitungszyklus oder von einem Vorbereitungszyklus zu einem Datenzyklus, genau die gleiche Anzahl von Übergängen statt- findet. Ist der Vorbereitungsmodus als Predischarge-Modus ausgeführt, so werden im Vorbereitungsmodus alle Eingangsda- ten nicht, wie im Precharge, auf 1 initialisiert, sondern auf 0"vorentladen". Dann findet ebenfalls von einem Vorberei- tungszyklus zu einem Datenzyklus und umgekehrt genau dieselbe Anzahl von Übergängen statt.

Wie es bereits ausgeführt worden ist, wird für die Ausführung von modularen Operationen, wie z. B. Addition oder Multipli- kation, beispielsweise im Rahmen kryptographischer Algorith- men, wie RSA oder elliptische Kurven, ein Drei-Operanden-

Addierer benötigt. Diese Operationen müssen aus den verschie- denen Gründen vom Addierwerk sicher gegenüber Power-Attacken ausgeführt werden. Da kryptographische Berechnungen äußerst rechenaufwendig sind, muß das Addierwerk eine hohe Leistung haben. Da insbesondere in der Kryptographie lange Operanden verarbeitet werden müssen, wobei die Operandenlänge bei el- liptischen Kurven im Bereich zwischen 100 und 200 Bits liegt und im Bereich von RSA zwischen 1.024 und 2.048 Bits liegt, hat das Rechenwerk selbst eine große Bitlänge, um die an das Rechenwerk gestellten Anforderungen nach Schnelligkeit zu er- reichen.

Um das in Fig. 7 gezeigte Rechenwerk, das ausschnittweise zwei Bit-Slices eines größeren Rechenwerks mit beispielsweise 2300 Bit-Slices zeigt, gegenüber kryptographischen Attacken sicherer zu machen, ist es zunächst erforderlich, die Ein- gangsoperanden C, N, Z in Dual-Rail-Technik den 3-Bit- Halbaddierern 80 zuzuführen.

Eine noch bessere Sicherheit besteht darin, nicht nur eine Dual-Rail-Technik anzuwenden, sondern eine Dual-Rail-Technik mit Precharge bzw. Pre-Discharge zu verwenden. Hierbei wech- selt immer ein Datentakt mit einem sogenannten Vorbereitungs- takt ab. In einem Datentakt ist beispielsweise das Bit Ci gleich 0 oder 1, während das komplementäre Bit, das auf der "zweiten Rail"zugeführt wird, und mit Ci bezeichnet wird, komplementär zu dem Bit Ci ist. In einem dem Datentakt nach- geordneten Vorbereitungstakt wird im Falle eines Precharge als Vorbereitungsmodus eine Aufladung beider Leitungen auf z.

B. Vdd durchgeführt, was beispielsweise dem logischen Zustand "1"entsprechen könnte. Beide Dual-Rail-Leitungen haben im Vorbereitungsmodus somit den gleichen Wert. Im Falle eines Discharge könnten beide Leitungen Ci und Ci auf das Potential Vss gebracht werden, das typischerweise das Erdungspotential ist, wobei das Erdungspotential bei'dem vorliegenden Beispiel einer logischen"0"entspricht. Selbstverständlich kann Vss

auch einer logischen"1"entsprechen. Dann würde Vdd einer logischen"0"entsprechen.

Konsequenterweise müßten dann die Bits xi und yi bzw. xi1 und Yi-l ebenfalls in Dual-Rail-Technik mit Precharge zu den ent- sprechenden nachgeschalteten 2-Bit-Volladdierern 81 zugeführt werden, wobei wieder immer ein Datentakt einem Vorbereitungs- takt folgt. Ausgangsseitig würden dann die Übertragbits C 83 und die Summenbits 82 ebenfalls in Dual-Rail-Technik mit Precharge/Pre-Discharge aus dem 2-Bit-Volladdierer herausge- führt werden.

So genügt es jedoch für eine optimale Sicherheit nicht nur, daß die Eingangsleitungen in die Elemente 80 und 81 und die Ausgangsleitungen aus den Elementen 80 und 81 in Dual-Rail- Technik ausgeführt sind. Statt dessen ist es ferner wichtig, daß auch die Schaltungen 80,81 selbst als Dual-Rail- Schaltungen ausgeführt sind. Dies kann dadurch erreicht wer- den, daß der 3-Bit-Halbaddierer 80 und jeder 2-Bit- Volladdierer 81 doppelt vorhanden ist und so ausgebildet ist, daß der erste 3-Bit-Halbaddierer 80 beispielsweise mit den nicht-invertierten Operandenbits Ci, Ni und Zi rechnet, um xi und yi zu erhalten. Der zweite 3-Bit-Halbaddierer 80 für den- selben Bit-Slice würde dann mit den invertierten Bits Ci, N1 und Zi arbeiten, um z. B. die invertierten Ausgangsbits x und Yi zu erhalten. Selbstverständlich sind jegliche Kreuzkombinationen denkbar, so daß der erste 3-Bit- Halbaddierer so ausgebildet ist, um aus den nicht- invertierten Eingangsbits die invertierten Ausgangsbits zu berechnen und umgekehrt.

Dasselbe müßte für den 2-Bit-Volladdierer 81 durchgeführt werden, um eine optimal sichere Schaltung in einem Bit-Slice eines Langzahlrechenwerks für eine RSA-Berechnung mit Mo- dullängen von 1024 Bits, 2048 Bits etc. zu erreichen. Solche Rechenwerke werden zur Ausführung von modularen Operationen, wie z. B. Addition und Multiplikation, beispielsweise im Rah-

men kryptographischer Algorithmen wie RSA oder elliptische Kurven benötigt. Eine 3-Operanden-Addition, die der 3- Operanden-Addierer, der in Fig. 7 ausschnittweise gezeigt ist, ausführt, besteht darin, einen ersten Summand C zu einem zweiten Summand Z hinzu zu addieren, und schließlich den Mo- dul N je nach Look-Ahead-Vorschrift zu addieren oder zu sub- trahieren. Diese Operationen müssen, wie es ausgeführt worden ist, vom Addierwerk sicher gegenüber Power-Attacken ausge- führt werden.

Es ist unmittelbar einsichtig, daß kryptographische Berech- nungen äußerst rechenaufwendig sind. Daher besteht neben der Sicherheit auch die Anforderung an das Rechenwerk, daß es ei- ne hohe Leistung hat, dahingehend, daß es möglichst wenig Re- chenzeit benötigt bzw. im Falle von begrenzten Ressourcen, wie beispielsweise auf einer Chipkarte, noch mit einer er- träglichen Rechenzeit hochsichere Operationen ausführen kann.

Da die Arithmetik kryptographischer Operationen eine Lang- zahlarithmetik ist, hat, wie es ausgeführt worden ist, das Rechenwerk selbst eine große Bitlänge, um überhaupt eine ge- forderte Leistung zu erreichen. So wird davon ausgegangen, daß jeder Bit-Slice einer Stelle eines Moduls entspricht, da- hingehend, daß alle Stellen in entsprechende Hardware-Bit- Slices"abgebildet"sind. Lediglich diese maximal parallele Ausführung garantiert in den meisten Fällen eine ausreichende Performance.

Im Hinblick auf die geforderte maximale Parallelität und an- dererseits im Hinblick auf die Kosten für'den Chip, der ein solches Rechenwerk umfaßt, und auch im Hinblick auf andere an die Chipfläche angelegten Begrenzungen ist es zwingend not- wendig, das Rechenwerk sehr flächensparend zu entwerfen. Es wird also prinzipiell ein Rechenwerk benötigt, das eine hohe Leistung hat, das außerdem sicher ist, und das eine minimale Fläche benötigt.

Die vorstehenden drei Anforderungen widersprechen sich jedoch dahingehend, daß eine maximale Sicherheit durch Dual-Rail- Technik mit einem doppelten Flächenaufwand des Rechenwerks sehr teuer erkauft werden muß.

Die Aufgabe der vorliegenden Erfindung besteht darin, einen Halbaddierer zu schaffen, der einerseits sicher ist und ande- rerseits einen erträglichen Flächenaufwand mit sich bringt.

Diese Aufgabe wird durch einen Halbaddierer gemäß Anspruch 1 gelöst.

Der vorliegenden Erfindung liegt die Erkenntnis zugrunde, daß der 3-Bit-Halbaddierer z. B. in einer Bit-Slice eines kom- pletten 3-Operanden-Addierers nicht in kompletter Dual-Rail- Technik ausgeführt wird, also doppelt auf einer Schaltung im- plementiert wird, sondern daß statt dessen gewissermaßen eine "One-Hot"-Realisierung des Halbaddierers eingesetzt wird, welche dazu führt, daß der Halbaddierer flächensparender aus- geführt werden kann und dennoch eine je nach Ausführungsform adäquate Sicherheit gegen Power-Attacken erreicht. Ein erfin- dungsgemäßer Halbaddierer zum Addieren von Bits von zumindest drei Eingangsoperanden, um zumindest zwei Ausgabebits zu er- halten, umfaßt für jedes Ausgabebit eine Schaltstufe, wobei die Schaltstufe ausgebildet ist, um gemäß einer Halbaddierer- vorschrift für das entsprechende Ausgabebit abhängig von den Bits der Eingangsoperanden ein Rechenpotential an einen Aus- gang der Schaltstufe durchzuschalten, wobei das Rechenpoten- tial an dem Ausgang das Ausgabebit oder eine invertierte Ver- sion des Ausgabebits darstellt. Der Halbaddierer umfaßt fer- ner für jedes Ausgabebit eine Ausgabestufe, die der Schaltstufe für dieses Ausgabebit nachgeschaltet ist. Die Ausgabestufe umfaßt einen ersten Ausgang und einen zweiten Ausgang, wobei in einem Datenmodus an dem ersten Ausgang das Ausgabebit ausgebbar ist, und wobei in dem Datenmodus an dem zweiten Ausgang eine invertierte Version des Ausgabebits aus- gebbar ist, und wobei die Ausgabestufe ferner wirksam ist, um

in einem Vorbereitungsmodus den ersten Ausgang und den zwei- ten Ausgang auf dasselbe Vorbereitungspotential zu bringen, wobei sich das Vorbereitungspotential von dem Rechenpotential unterscheidet.

Der erfindungsgemäße Halbaddierer ist dahingehend flächenspa- rend, daß die Schaltstufe lediglich ein Ausgabebit berechnen muß, wobei es von der Implementierung abhängt, ob die Schaltstufe das Ausgabebit selbst oder die invertierte Versi- on des Ausgabebits liefert. Es ist einsichtig, daß die gefor- derte Information sowohl im Ausgabebit als auch im invertier- ten Ausgabebit enthalten ist.

Das entsprechende von der Schaltstufe nicht berechnete kom- plementäre Bit wird dann in der Ausgabestufe erzeugt, und zwar bereits im Vorbereitungsmodus, also im Precharge-bzw.

Pre-Discharge-Modus. Je nach Implementierung wird dann im Da- tenmodus lediglich ein Ausgabebit der Ausgabestufe, nämlich entweder das Ausgabebit selbst oder die invertierte Version des Ausgabebits gegenüber dem Precharge-Zustand umgeladen, so daß in dem Datenmodus der Halbaddierer ein Bit ausgibt, das durch die Schaltstufe berechnet worden ist und gegenüber dem Precharge-Modus umgeladen worden ist, während das andere Bit im Datenmodus denselben Wert hat wie im Vorbereitungsmodus und bereits in dem dem Datentakt vorhergehenden vorberei- tungstakt erzeugt worden ist.

Die erfindungsgemäße Schaltung ist dahingehend flächenspa- rend, daß die Schaltstufe das invertierte Bit oder das nicht- invertierte Bit je nach Implementierung berechnet, und nicht beide Bits berechnen muß. Das zweite Bit wird dann in der Du- al-Rail-Precharge/Pre-Discharge-Ausgangsstufe erzeugt.

Die erfindungsgemäße Schaltung ist ferner dahingehend vor- teilhaft, daß sie transistorarm implementiert werden kann.

Dies ist dann der Fall, wenn die Schaltstufe derart ausgebil- det wird, daß durch sie das Rechenpotential abhängig von den

drei Eingangsoperanden an einen Ausgang auf einem von ver- schiedenen Pfaden durchschaltet. Für jede Pfad-Verzweigung wird es bevorzugt, dieselbe Anzahl von Transistoren zu neh- men, so daß jeder durch die Schaltstufe implementierbare Pfad von dem Rechenpotential zu einem Ausgang eine gleiche Anzahl von Transistorumschaltungen mit sich bringt, so daß von außen anhand des Leistungsprofils nicht ersichtlich ist, welchen Pfad die Schaltstufe genommen hat. Es ist daher anhand des Stromverbrauchs nicht ersichtlich, welche Eingangsoperanden im aktuellen Rechenzyklus anliegend waren.

Die erfindungsgemäße Schaltung ist ferner dahingehend vor- teilhaft, daß sie eine hohe Flexibilität ermöglicht. So wird für jedes Ausgabebit eine eigene Schaltstufe vorgesehen. Eine Stromsicherheit ist bereits dann erreicht, wenn die Anzahl von Transistoren in einem Pfad in einer Schaltstufe gleich der Anzahl von Transistoren von anderen Pfaden in derselben Schaltstufe ist. Es muß jedoch keine Gleichheit der Transi- storen von einer Schaltstufe zur nächsten Schaltstufe vorhan- den sein. Daher können beliebige Halbaddierer-Vorschriften für einzelne Bits implementiert werden, ohne daß ein Transi- stor-Overhead dahingehend vorhanden ist, daß z. B. alle Schaltstufen dieselbe Anzahl von Transistoren haben müssen.

Durch Implementation beliebiger Halbaddierer-Vorschriften im Hinblick auf die ausgangsseitige Codierung des Halbaddierer- Ergebnisses (binäre Gewichtung, Gray-Code, Dezimalgewichtung etc. ) kann daher immer eine optimal transistorarm entworfene Schaltstufe gefunden werden.

Darüber hinaus ist die erfindungsgemäße Schaltung querstro- marm und im idealen Fall sogar querstromfrei, da immer nur Umladungen von einem einzigen Ausgangsknoten der Ausgabestufe erforderlich sind. So wird bereits immer ein Ausgabebit im Vorbereitungsmodus gewissermaßen auf Verdacht berechnet, wäh- rend im Datenmodus nur ein einziges Bit der zwei Ausgabebits einer Ausgabestufe umgeladen werden muß. Diese Umladung fin-

det ohne Querstrom vom hohen Potential (z. B. Vdd) zum nied- rigen Potential (Vss) statt und hat zudem einen geringen Stromverbrauch im Vergleich zu dem Fall, bei dem immer zwei Ausgabebits umgeladen werden müssen. Die erfindungsgemäße Schaltung ist somit nicht nur querstromarm sondern auch in ihrem insgesamten Stromverbrauch günstig, was insbesondere für Anwendungen von Vorteil ist, bei denen beispielsweise ei- ne Chipkarte keine autarke Spannungsversorgung in Form einer Batterie hat, wie z. B. Kontaktlosanwendungen.

Die erfindungsgemäße Schaltung ist ferner günstig implemen- tierbar, da die einzelnen Stufen nicht in vollständiger CMOS- Technik implementiert werden müssen. Es reichen statt dessen für die einzelnen Stufen entweder ausschließlich NMOS- Transistoren oder PMOS-Transistoren. Es werden jedoch nicht unbedingt in allen Stufen beide Transistorsorten benötigt, wie es dagegen bei einem vollständigen CMOS-Design der Fall ist, bei dem einem PMOS-Transistor immer ein entsprechender Komplementärtransistor (NMOS-Transistor) zugeordnet ist.

Die erfindungsgemäße Schaltung ist ferner dahingehend flexi- bel, daß das Rechenpotential, das durch die Schaltstufe gemäß den Eingangsoperanden an einen Ausgang durchgeschaltet wird, das hohe Potential Vdd oder das niedrige Potential Vss sein kann. Wird für das Rechenpotential das hohe Potential Vdd ge- wählt, so muß für das Vorbereitungspotential in der Ausgabe- stufe das andere Potential, also im vorliegenden Fall das niedrige Potential Vss verwendet werden. Wird dagegen in der Schaltstufe als Rechenpotential das niedrige Potential Vss verwendet, so muß in der Ausgabestufe ein Vorbereitungspoten- tial verwendet werden, das sich von dem Rechenpotential un- terscheidet. Im letzteren Fall wäre dies das hohe Potential Vdd.

Der erfindungsgemäße Halbaddierer trägt somit zu einem siche- ren, leistungskräftigen und flächenminimalen 3-Operanden- Addierer bei. Die Operanden, die an dem 3-Operanden-

Rechenwerk anliegen, sind typischerweise in Speicherelemen- ten, wie z. B. SRAM-Zellen gespeichert und werden in Dual- Rail-Ausführung zu dem Rechenwerk geführt, um eine Sicherheit gegenüber Power-Attacken zu erreichen. Da der Volladdierer, der sich an den Halbaddierer anschließt, kompakt in Dual- Rail-Precharge-Logik ausgeführt werden kann, können auch die Verbindungen zwischen dem Halb-und Volladdierer ihrerseits in Dual-Rail-Logik mit Precharge/Pre-Discharge-Technik ausge- führt sein. Der flächenminimale und sichere erfindungsgemäße Halbaddierer basiert auf der"One-Hot"-Realisierung. Für je- des anliegende Bitpattern wird in jeder Schaltstufe genau ein Pfad geschaltet. Im Falle von zwei Ausgabebits wird daher für jedes Bitpattern der drei anliegenden Operanden zwei Pfade geschaltet. Diese zwei Pfade sind notwendig, um für die Aus- gabestufe jeweils ein Bit zu berechnen, während das andere Bit durch die Ausgabestufe selbst gewissermaßen erzeugt wird, d. h. aus dem vorausgehenden Vorbereitungsmodus"übernommen" wird. Für jedes beliebige anliegende Bitpattern am Eingang ist die insgesamte Summe der umzuladenden Kapazitäten gleich.

Damit läßt sich das anliegende Bitpattern während der Schalt- vorgänge im Halbaddierer nicht von außen erkennen.

Erfindungsgemäß wird es bevorzugt, zur Erreichung einer mög- lichst hohen Leistung die zu schaltenden Pfade mit möglichst wenig Transistoren auszustatten. Dies kann individuell für jede Schaltstufe je nach Halbaddierervorschrift beliebig durchgeführt werden, so daß nicht eine Schaltstufe, die eine komplexere Halbaddierervorschrift hat, die Transistorzahl für eine andere Schaltstufe, die eine weniger komplexe Halbaddie- rervorschrift hat, gewissermaßen"diktiert".

Der erfindungsgemäße Halbaddierer wird in seiner bevorzugten Form als 3-Operanden-Addierer mit drei Eingangsoperanden ver- wendet, um zwei Ausgabebits in binärer Gewichtung zu erzeu- gen. Durch Hintereinanderschalten von mehreren solchen 3- Operanden-Addierern können beliebige N-Operanden-Addierer beispielsweise zur Ausführung eines nicht nur drei-fachen

sondern eines N-fachen ZDN-Algorithmus eingesetzt werden. Mit einem solchen N-Operanden-Addierer, der aus mehreren hinter- einander geschalteten erfindungsgemäßen 3-Operanden-Addierern aufgebaut ist, läßt sich die Performance pro Chipfläche noch einmal steigern, und zwar mit einem Flächen-Overhead, der un- terproportional zum Performance-Gewinn ist.

Der erfindungsgemäße Halbaddierer hat jedoch auch das Poten- tial, als direkter N-Operanden-Addierer ohne Verwendung von hintereinander geschalteten 3-Operanden-Addiererelementen eingesetzt zu werden, indem andere Halbaddierer-Vorschriften für z. B. mehr als zwei Ausgabebits z. B. gemäß entsprechen- der Wahrheitstabellen für einen beispielsweise 7-Operanden- Addierer eingesetzt werden. Ein 7-Operanden-Addierer bei- spielsweise hat maximal sieben Einsen, wenn alle sieben Ein- gangsoperandenbits gleich 1 sind. Die dezimale Zahl 7 ist durch insgesamt drei Ausgabebits in binärer Gewichtung dar- stellbar. Ein 7-Operanden-Halbaddierer würde daher bereits mit drei Ausgabebits auskommen.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend Bezug nehmend auf die beiliegenden Zeich- nungen detailliert erläutert. Es zeigen : Fig. 1 ein Blockschaltbild eines Halbaddierers mit einer beliebigen Anzahl von Eingangsoperanden und einer entsprechenden Anzahl von Ausgabebits ; Fig. 2 eine Tabelle zu möglichen Kombinationen des Rechen- potentials, des Vorbereitungspotentials und einer entsprechenden Transistortechnologie ; Fig. 3 eine Wahrheitstabelle für einen 3-Operanden- Halbaddierer mit zwei Ausgabebits SUM1 und SUMO ; Fig. 4 eine schematische Darstellung von Schaltstufen mit unterschiedlichen Rechenpotentialen ;

Fig. 5a ein Beispiel für Pfade durch die Schaltstufen für ein bestimmtes Operanden-Bitmuster ; Fig. 5b eine beispielhafte Darstellung verschiedener Pfade durch Schaltstufen für ein alternatives Operanden- Bitmuster ; Fig. 6 ein Blockschaltbild auf Transistorebene für einen bevorzugten Halbaddierer gemäß der vorliegenden Er- findung mit Dual-Rail-Eingangsstufe, zwei Schaltstufen und zwei Ausgabestufen ; und Fig. 7 ein bekannter 3-Operanden-Addierer mit entsprechend verschalteten 3-Bit-Halbaddierern und 2-Bit- Volladdierern für Bit-Slices eines Langzahlrechen- werks.

Fig. 1 zeigt ein schematisches Blockschaltbild eines erfin- dungsgemäßen Halbaddierers zum Addieren von Bits von mehreren Eingangsoperanden, die in Fig. 1 derart dargestellt sind, daß sie einer Eingangsstufe 10 zugeführt werden. Die Eingangsope- randen sind in Fig. 1 mit C, N, Z bezeichnet, wobei eine be- liebige weitere Anzahl von Eingangsoperanden der Eingangsstu- fe 10 zugeführt werden können. Die Eingangsstufe ist primär wirksam, um die Eingangsoperanden an in Fig. 1 gezeigte n Schaltstufen 12a, 12b, 12c zu verteilen. Die Schaltstufe 12a ist dem Ausgangsbit 0 zugeordnet, das auch als Bit SUMO be- zeichnet wird. Das dazu komplementäre Bit SUMO ist in Fig. 1 ebenfalls ausgangsseitig dargestellt. Die Schaltstufe 12b ist dem Ausgangsbit 1 zugeordnet, das auch als Bit SUM1 bezeich- net wird. Das dazu komplementäre Bit SUM1 ist in Fig. 1 ebenfalls ausgangsseitig dargestellt. Die Schaltstufe 12c ist für das Ausgangsbit n vorgesehen. Dies wird auch als Bit SUMn bezeichnet. Das hierzu komplementäre Bit SUMn ist in Fig. 1 ebenfalls ausgangsseitig dargestellt. Jeder Schaltstufe 12a, 12b, 12c ist eine Ausgabestufe 14c zugeordnet, wie es aus

Fig. 1 ersichtlich ist. Insbesondere ist die Ausgabestufe 14a der Schaltstufe 12a für das Bit 0 nachgeordnet. Die Ausgabe- stufe 14b ist der Schaltstufe 12b für das Bit 1 nachgeordnet.

Die Ausgabestufe 14c ist der Schaltstufe 12c für das Bit n nachgeordnet.

Wie es aus Fig. 1 ersichtlich ist, ist ferner jeder Schaltstufe ein Rechenpotential für diese Schaltstufe zuführ- bar, wie es durch die Rechenpotentialanschlüsse 16a, 16b und 16c dargestellt ist. Prinzipiell ist jeder Schaltstufe ein eigenes Rechenpotential zuführbar, das bei einem bevorzugten Ausführungsbeispiel entweder ein hohes Potential Vdd oder ein niedriges Potential Vss ist. Aus Gründen der Schaltungsimple- mentierung wird es jedoch bevorzugt, jeder Schaltstufe das- selbe Rechenpotential 16c, 16b, 16a zuzuführen, das entweder Vss oder Vdd ist. Existiert. die Möglichkeit, daß die imple- mentierte Schaltung mehr als zwei Potentiale hat, so können auch von Vss bzw. Vdd abweichende Rechenpotentiale den Schaltstufen 12a, 12b, 12c zugeführt werden.

Die Schaltstufen 12a, 12b, 12c sind wirksam, das ihnen zuge- führte Rechenpotential 16a, 16b, 16c an einen Ausgang 18a, 18b, 18c zuzuführen, wobei das zu dem Ausgang 18a, 18b, 18c zugeführte Spannungspotential das Ausgabebit oder eine inver- tierte Version des Ausgabebits darstellt.

An dieser Stelle sei darauf hingewiesen, daß das Ausgabebit als logisches Bit aufgefaßt wird, also als logische"0"oder als logische"1". Wird dem Ausgang 18a der Schaltstufe 12a das Rechenpotential 16a aufgrund einer durch die Schaltstufe 12a gebildeten leitfähigen Verbindung von dem Eingang 16a zu dem Ausgang 18a zugeführt, so kann der an dem Ausgang 18a an- liegende Spannungswert entweder das logische Ausgabebit SUMO der nachgeschalteten Ausgabestufe 14a darstellen oder das in- vertierte Bit SUMO darstellen, je nach gewählter Implemen- tierung.

Die Ausgabestufe 14a empfängt als Eingangssignal das Signal auf dem Ausgang 18a der Schaltstufe sowie als weiteres Ein- gangssignal ein Vorbereitungspotential an einem Anschluß 20a.

Entsprechend ist die Situation für die Ausgabestufen 14b und 14c, die ihre Vorbereitungspotentiale über Eingänge 20b bzw.

20c empfangen. Jede Ausgabestufe umfaßt zwei Ausgänge 22a, 22b. Entsprechend umfaßt die Ausgabestufe 14b für das Bit 1 ebenfalls zwei Ausgänge 24a, 24b. Analogerweise umfaßt auch die Ausgabestufe 14c für das Bit n ebenfalls zwei Ausgänge 26a, 26b. Der Ausgang 22a der Ausgabestufe 14a für das Bit 0 liefert das invertierte Ausgabebit SUMO. Entsprechend lie- fert der Ausgang 22b der Ausgabestufe 14a das nicht- invertierte Ausgabebit SUMO.

Der in Fig. 1 gezeigte Halbaddierer umfaßt ferner eine Steu- ereinrichtung 28 zum Einstellen eines Datenmodus und eines Vorbereitungsmodus, wobei im Vorbereitungsmodus entweder ein Precharge-Modus oder ein Pre-Discharge-Modus gefahren werden kann. Das Vorhandensein eines Datenmodus bzw. eines Vorberei- tungsmodus wird durch Steuerleitungen 28a, 28b, 28c den Aus- gabestufen 14a, 14b bzw. 14c signalisiert. Optionalerweise ist die Eingangsstufe 10 ebenfalls im Datenmodus bzw. Vorbe- reitungsmodus betreibbar. Dies signalisiert die Steuerein- richtung 28 der Eingangsstufe über eine weitere Steuerleitung 28d.

Im Datenmodus liegt an einem Ausgang einer Ausgabestufe das Ausgabebit in nicht-invertierter Form an, also SUMO, SUM1 bzw. SUMn. An dem anderen Ausgang liegt im Datenmodus eine invertierte Version des Ausgabebits an, also SUMO, SUM1 bzw.

SUMn.

Die Ausgabestufen sind ferner wirksam, um in einem Vorberei- tungsmodus an einem Ausgang und an dem anderen Ausgang das- selbe Vorbereitungspotential, das der Ausgabestufe über den entsprechenden Eingang 20a, 20b bzw. 20c zugeführt wird, an- zulegen, wobei sich erfindungsgemäß das Vorbereitungspotenti-

al, das einer Ausgabestufe beispielsweise über den Eingang 20a zugeführt wird, von dem Rechenpotential unterscheidet, das der Schaltstufe, die der betrachteten Ausgabestufe vorge- schaltet ist, z. B. über den Eingang 16a zugeführt wird. Der Vorbereitungsmodus wird bei dem in Fig. 1 gezeigten Ausfüh- rungsbeispiel den einzelnen Ausgabestufen von der Steuerein- richtung 28 über die Steuerleitungen 28a, 28b bzw. 28c signa- lisiert.

Im nachfolgenden wird anhand von Fig. 2 auf bevorzugte Kombi- nationen von Rechenpotential, Vorbereitungspotential und Transistortechnologie eingegangen. Wird als Rechenpotential einer Schaltstufe (Eingang 16a) das hohe Potential Vdd einer Schaltung zugeführt, so ist das der nachgeschalteten Ausgabe- stufe unterschiedliche Vorbereitungspotential das niedrige Potential Vss. Das Zuführen des niedrigen Potentials Vss als Vorbereitungspotential führt zu einem Pre-Discharge in der Ausgabestufe (z. B. 14a), so daß im Vorbereitungsmodus beide Bits SUMO, SUMO einen niedrigen Spannungszustand haben und damit bei dem hier dargestellten Beispiel eine logische"0" darstellen.

Im Datenmodus wird von der Schaltstufe 12a dann das hohe Re- chenpotential Vdd der Ausgabestufe 14a als Bit SUMO oder Bit SUMO zugeführt, und zwar je nach Bitmuster der drei Ein- gangsoperandenbits, so daß dann, im Datenmodus, lediglich ein Ausgangsbit SUMO bzw. SUMO umladen wird, d. h. von dem logi- schen Zustand"0"in den logischen Zustand"1"umgeändert wird.

In dem Fall, in dem als Rechenpotential Vdd genommen wird, und als Vorbereitungspotential Vss genommen wird, wird als Transistortechnologie die PMOS-Technologie bevorzugt, da die PMOS-Transistoren günstiger ein hohes Rechenpotential durch- schalten.

Wird dagegen im anderen Fall als Rechenpotential das niedrige Potential Vss genommen, und wird dann konsequenterweise als Vorbereitungspotential das hohe Potential Vdd genommen, so findet in der Ausgabestufe ein Precharge-Modus statt, dahin- gehend, daß die beiden Ausgabebits SUMO, SUMO der Ausgabe- stufe 14a, beispielsweise eine logische"1"darstellen. Durch die Schaltstufe wird das niedrige Potential Vss entweder als Bit oder Bit der Ausgabestufe 14a zugeführt, die dann ledig- lich eines der beiden Ausgangsbits SUMO oder SUMO in den niedrigen Zustand umlädt, also von einer logischen"1"in ei- ne logische"0"verändert. In diesem Fall wird in der Schaltstufe als Transistortechnologie die NMOS-Technologie bevorzugt, da diese am besten dafür geeignet ist, niedrige Spannungspotentiale durchzuschalten.

Fig. 3 zeigt in Tabellenform eine bevorzugte Halbaddierervor- schrift für einen 3-Operanden-Addierer, um für jedes Bitmu- ster der Eingangsoperanden Ci, Ni und Zi entsprechende Aus- gangsbits SUM1, SUMO zu berechnen. Die Halbaddierervorschrift in Fig. 3 ist als"Einsen-Zähler"ausgebildet, wobei die An- zahl von Einsen durch die Bits SUMO, SUM1 in binärer Gewich- tung dargestellt werden. Die beiden Ausgangsbits SUM1 und SUMO stellen somit eine binäre Zahl dar, wobei das Bit SUM1 das MSB dieser binären Zahl ist, und wobei das Bit SUMO das LSB dieser Zahl ist. Die beiden Ausgangsbits SUM1 und SUMO stellen daher in binärer Codierung die Anzahl von Einsen ei- nes jeden Bit-Patterns der Eingangsoperanden dar. Lediglich in dem Fall, in dem alle drei Eingangsoperanden eine logische "1"haben, sind beide Bits SUM1 und SUMO gesetzt, was der bi- nären Zahl"11"entspricht, die in dezimaler Darstellung gleich der Zahl 3 ist.

Für Fachleute ist es offensichtlich, daß anhand der Systema- tik von Fig. 3 beliebige N-Operanden-Halbaddierer aufgebaut werden können. Wird beispielsweise ein 7-Operanden- Halbaddierer aufgebaut, so wird zur Darstellung des maximalen Falls, in dem alle sieben Operanden eine logische"1% 1 haben,

eine Anzahl von drei Ausgabebits benötigt, da die binäre Zahl "111"der dezimalen Zahl"7"entspricht.

Für Halbaddierer mit einer größeren Anzahl von sieben Operan- den werden daher entsprechend mehr Ausgabebits benötigt, wenn die normale binäre Gewichtung eingesetzt wird.

Aus der Systematik von Fig. 3 ist ferner ersichtlich, daß auch eine andere Codierung eingesetzt werden kann, wenn es für einen speziellen Fall günstig ist. So kann die Bedeutung der Bits SUM1, SUMO beliebig eingestellt werden, dahingehend, daß eine Bitkombination von SUMO und SUM1 als"11"z. B. dar- auf hindeutet, daß die Anzahl von Nullen in den Eingabebits C, N, Z gleich 3 ist, was gleichbedeutend damit ist, daß die Anzahl von Einsen in C, N, Z bei der bestimmten betrachteten Bitkombination gleich 0 ist.

Beliebige weitere Vereinbarungen für die Bits SUM1, SUMO kön- nen getroffen werden. Ferner können je nach Halbaddierervor- schrift weitere (redundante) Bits, z. B. SUM2, SUM3,. .. ver- wendet werden.

Fig. 4 zeigt in schematischer Form eine bevorzugte Ausfüh- rungsform einer Schaltstufe 12a und 12b für einen 3- Operanden-Addierer. In Fig. 4 ist ferner der Fall gezeigt, daß die beiden Schaltstufen 12a, 12b unterschiedliche Rechen- potentiale 16a, 16b haben. So hat die Schaltstufe 12a das niedrige Potential Vss als Rechenpotential. Die Schaltstufe 12b hat dagegen das hohe Potential Vdd als Rechenpotential 16b. Durch gestrichelte Linien 41,42, 43 ist in Fig. 4 dar- gestellt, daß jeder Schaltstufe die Eingangsoperanden (erster Operand, zweiter Operand, dritter Operand) zugeführt werden.

Je nach Gestaltung der in Fig. 3 gezeigten Halbaddierer- Vorschrift bewirkt ein Operand eine Abzweigung des Pfades oder nicht. Wie es rechts in Fig. 4 dargestellt ist, wird ein Pfad waagrecht weitergeführt, wenn der Operand gleich 0 ist.

Ist der Operand dagegen gleich einer logischen"1", so wird,

wie es ebenfalls rechts in Fig. 4 dargestellt ist, der Pfad in einer 45°-Richtung fortgesetzt.

Für eine Kombination von Eingangsoperanden wird durch das in Fig. 4 gezeigte Schaltwerk ein leitfähiger Pfad von dem Po- tential z. B. 16a zu dem nicht-invertierten Ausgang Bit oder zu dem invertierten Ausgang Bit durchgeschaltet, derart, daß das Rechenpotential Vdd bzw. Vss an dem entsprechenden inver- tierten Ausgang oder nicht-invertierten Ausgang anliegt. Es sei darauf hingewiesen, daß das Rechenpotential nie an beiden Ausgängen anliegen kann, da die Schaltstufe derart ausgebil- det ist, daß ein eindeutiger Pfad von dem Rechenpotentialan- schluß 16a beispielsweise zu einem einzigen Ausgang 18a er- halten wird.

Nachfolgend werden anhand der Fig. 5a und 5b zwei jeweils verschiedene Pfade durch die einzelnen Schaltstufen für un- terschiedliche Bitmuster dargestellt.

In Fig. 5a ist beispielhaft der Fall gezeigt, bei dem der er- ste Operand gleich 1, der zweite Operand gleich 0 ist, und der dritte Operand gleich 1 ist. Für die Schaltstufe 14a be- deutet dies, daß ein erster Schaltknoten 50a dahingehend durchlaufen wird, daß eine 45°-Abzweigung genommen wird, da der erste Operand gleich 1 ist. Ein zweiter Schaltknoten 50b wird dahingehend verarbeitet, daß der Pfad waagrecht fortge- führt wird, da der zweite Operand gleich 0 ist. Ein dritter Schaltknoten 50c wird dahingehend durchlaufen, daß wieder ei- ne 45°-Abzweigung genommen wird, da der dritte Operand gleich 1 ist. Dies führt dazu, daß das Rechenpotential Vss ausgangs- seitig das nicht-invertierte Bit der Schaltstufe bestimmt. Im Datenmodus führt ein Spannungszustand Vss für das nicht- invertierte Bit dazu, daß die der Schaltstufe 14a nachge- schaltete Ausgabestufe 14b, die beide Ausgängen 22a, 22b in einem Zustand"1"hatte, das nicht-invertierte Bit SUMO (22b) in den niedrigen Zustand entlädt, während das invertierte Bit SUMO 22a im hohen Zustand bleibt.

Die Schaltstufe 14b hat als Rechenpotential das hohe Potenti- al Vdd. In einem ersten Verzweigungsknoten 52a wird eine 45°- Abzweigung genommen. In einem zweiten Verzweigungsknoten 52b, die dem zweiten Operanden entspricht, wird eine waagrechte Abzweigung genommen. In einem dritten Verzweigungsknoten 52c, die dem dritten Operanden entspricht, wird eine 45°- Abzweigung genommen, so daß schließlich am Ausgang 18b, der dem nicht-invertierten Bit entspricht, das hohe Spannungspo- tential Vdd anliegt. Das hohe Spannungspotential am Ausgang 18b führt dazu, daß in der Ausgabestufe 14b von Fig. 1 das nicht-invertierte Bit SUM1 24b von seinem niedrigen Zustand, den es im Vorbereitungsmodus hatte, auf den logisch hohen Zu- stand gesetzt wird, während das invertierte Bit SUM1 in sei- nem bereits aus dem Vorbereitungsmodus heraus bestehenden Zu- stand, also dem niedrigen Zustand"0"gelassen wird.

Aus der vorstehenden Beschreibung ist ersichtlich, daß die Schaltstufe lediglich ein Bit, also das invertierte bzw. das nicht-invertierte Bit berechnen muß, während das zweite Bit dann durch die Ausgabestufe aus dem vorausgehenden Vorberei- tungsmodus übernommen wird.

Ferner ist ersichtlich, daß z. B. in der Schaltstufe 14a in Fig. 5a acht verschiedene Pfade gemäß den acht verschiedenen Kombinationen der drei Eingangsoperanden gewählt werden kön- nen. Wie es jedoch aus der Schaltstufe 14b von Fig. 5a er- sichtlich ist, führt in dem Fall, in dem bereits der erste Eingangsoperand und der zweite Eingangsoperand gleich 0 wa- ren, in dem also an einem Verzweigungsknoten 52d der Pfad waagrecht fortgesetzt wird, dazu, daß dem dritten Operanden kein eigener Verzweigungspunkt mehr zugeordnet ist. Dies ist ohne weiteres daraus ersichtlich, daß in dem Fall, in dem be- reits der erste und der zweite Operand gleich 0 waren, höch- stens noch eine einzige 1 unter den drei Operanden, nämlich die 1 des dritten Operanden herauskommen kann, was auf jeden Fall dazu führt, daß das Bit SUM1, wie es aus der Wahrheits-

tabelle ersichtlich ist, gleich 0 ist. Das hohe Potential Vdd bestimmt daher den Zustand des invertierten Bits Bit zu ei- ner logischen"1", derart, daß im Datenmodus das nicht- invertierte Bit gleich 0 ist, wie es durch die Wahrheitsta- belle von Fig. 3 gefordert wird.

In Fig. 5b ist eine alternative Bitkombination der drei Ope- randen dargestellt, und zwar der Fall, bei dem alle drei Ope- randen gleich 1 sind. In der Schaltstufe 14a wird der in Fig.

5b eingezeichnete Pfad genommen, der lediglich 45°- Abzweigungen umfaßt. Der Pfad endet schließlich dahingehend, daß das niedrige Potential Vss, das eine logische"0"dar- stellt, am invertierten Bit Bit anliegt. In der Schaltstufe 14b ist bereits anhand der ersten beiden Operanden klar, daß das Bit gesetzt werden muß, so daß das Ergebnis, nämlich Vdd am nicht-invertierten Ausgang 18b der Schaltstufe, nicht mehr vom dritten Operanden abhängt, so daß dem dritten Operanden kein eigener Verzweigungspunkt mehr zugeordnet zu werden braucht.

Aus den Fig. 5a und 5b ist ferner ersichtlich, daß die Anzahl der Verzweigungspunkte, nämlich vier bei der Schaltstufe 14b und fünf bei der Schaltstufe 14a nicht für jede Schaltstufe identisch zu sein braucht. Vielmehr wird eine Schaltstufe mit möglichst wenig Abzweigungspunkten angestrebt, da die Anzahl der Abzweigungspunkte letztendlich die Anzahl der Transisto- ren in der Schaltstufe und damit die wertvolle Chipfläche be- stimmt. Eine Sicherheit gegenüber Leistungsattacken wird je- doch bereits dadurch erreicht, daß jeder Pfad durch eine Schaltstufe dieselbe Anzahl von Verzweigungspunkten umfaßt, wobei jedoch die Anzahl von Verzweigungspunkten von Schaltstufe zu Schaltstufe nicht zwingend gleich zu sein braucht. Eine solche Ungleichheit liefert dem Angreifer le- diglich die Information, daß in zwei Schaltstufen geschaltet worden ist. Diese Information nützt dem Angreifer jedoch nichts, da dieser Sachverhalt ohnehin klar ist. Ein Angreifer kann jedoch nicht erkennen, welcher Pfad in einer Schaltstufe

durchgeschaltet worden ist, um daraus unter Umständen auf die Werte der drei Eingangsoperanden schließen zu können.

Der Übersichtlichkeit halber ist in den Fig. 5a und Fig. 5b rechts noch der zugeordnete Vorbereitungsmodus dargestellt, der durch das einer Ausgangsstufe zugeordnete Vorbereitungs- potential bestimmt wird, das sich erfindungsgemäß von dem Re- chenpotential unterscheidet. So hat die Schaltstufe 14b auf- grund des hohen Rechenpotentials Vdd die Konsequenz zur Fol- ge, daß die zugeordnete Ausgabestufe ein anderes Vorberei- tungspotential hat, nämlich das niedrige Potential Vss, wenn die Schaltung lediglich zwei verschiedene Potentiale zur Ver- fügung stellt.

Analog hierzu hat die Schaltstufe 14a aufgrund des niedrigen Rechenpotentials Vss ein hohes Vorbereitungspotential zur Folge.

Nachfolgend wird anhand von Fig. 6 auf ein bevorzugtes Aus- führungsbeispiel der vorliegenden Erfindung auf Transistore- bene Bezug genommen.

Fig. 6 zeigt modulweise bevorzugte Transistorimplementationen einer Dual-Rail-Eingangsstufe (Block 10 in Fig. 1), von Schaltstufen (Blöcke 12a, 12b von Fig. 1) und Ausgabestufen (Blöcke 14a, 14b von Fig. 1).

Nachfolgend wird auf die Implementierung der Dual-Rail- Eingangsstufe (Block 10 in Fig. 1) eingegangen. Die Dual- Rail-Eingangsstufe in Fig. 6 umfaßt zunächst sechs Eingänge für die drei Operanden Z, N und C als nicht-invertierte Bits und invertierte Bits. Die Bits werden so der Dual-Rail- Eingangsstufe zugeführt, wie es in Fig. 6 ersichtlich ist.

Die Eingangsstufe enthält ferner, wie es in Fig. 1 durch die Leitung 28d angedeutet ist, ein Precharge-Signal Vss, um die Eingangsstufe in dem Vorbereitungsmodus in einen Precharge- Zustand zu fahren, bei dem alle sechs Eingänge auf dasselbe

Potential gebracht werden. Dieses Potential ist, wie es an- hand der Spannungsversorgungssituation in Fig. 6 ersichtlich ist, das hohe Potential, da die Dual-Rail-Eingangsstufe mit dem hohen Potential Vdd an verschiedenen Punkten versorgt wird.

Zur Auslösung des Precharge-Zustands, also im Vorbereitungs- modus, werden die in Fig. 6 als PMOS-Transistoren ausgeführ- ten Transistoren an ihrem Gate mit dem niedrigen Potential Vss versehen, damit sie durchschalten, wie es aus Fig. 6 er- sichtlich ist, um alle Operanden-Bit-Knoten und alle Knoten für invertierte Operandenbits auf das Potential Vdd zu legen.

Im einzelnen umfaßt jede Dual-Rail-Eingangsstufe vier Transi- storen 600,601, 602 und 603, wobei nachfolgend lediglich beispielhaft und repräsentativ für den zweiten und den drit- ten Operand die dem ersten Operand zugeordnete Eingangsstufe dargelegt wird. Die beiden Transistoren 601,600 dienen dazu, im Vorbereitungsmodus, in dem das Precharge-Signal aktiv ist, in dem also Vss auf der Leitung 28d anliegt, die auf der ei- nen Seite der beiden Transistoren anliegende hohe Spannung Vdd auf die Ausgangsknoten 604,605 für das invertierte erste Operandenbit und das nicht-invertierte erste Operandenbit zu legen. Damit werden unmittelbar die beiden Transistoren 603, 602 gesperrt, da sie das hohe Potential Vdd an ihrem jeweili- gen Gate-Anschluß haben.

Im Datenmodus ist dagegen die Leitung 28d auf dem hohen Po- tential Vdd, was dazu führt, daß die beiden Transistoren 601 und 600 wirkungslos sind. Die beiden Transistoren 602,603 dienen zur Stabilisierung der Verhältnisse im Datenmodus. Ist beispielsweise das Operandenbit Ni hoch, so ist der Transi- stor 602 gesperrt, so daß das Potential Vdd auf der einen Seite des Transistors 602 nicht an den Knoten 604 kommen kann. Der Knoten 604 ist nämlich, da er das invertierte Bit Ni des ersten Operanden darstellt, auf einem niedrigen Poten- tial. Dieses niedrige Potential führt dazu, daß der Transi-

stor 603 geöffnet wird. Es fließt jedoch im Idealzustand kein Strom, da der Knoten 605 ebenfalls auf Vdd ist. Der Transi- stor 603 dient jedoch dazu, das hohe Potential auf dem Knoten 605 zu stabilisieren und gegebenenfalls nachzuladen, falls an irgendeiner Stelle Leckströme auftreten.

Die Dual-Rail-Eingangsstufe dient somit dazu, im Vorberei- tungsmodus gleiche Potentiale auf den Bitleitungen zu erzeu- gen, und im Datenmodus die Zustände auf den Bitleitungen zu stabilisieren. Darüber hinaus dient die Dual-Rail- Eingangsstufe dazu, die Operandenbits über Verteilungsschie- nen 611,612 und 613 an die Schaltstufen zu verteilen.

Wie es in Fig. 6 gezeigt ist, sind die beiden Schaltstufen derart ausgebildet, daß sie als Rechenpotential das hohe Po- tential Vdd zugeführt bekommen, wie es durch die Spannungszu- führungen 16a für die erste Schaltstufe und 16b für die zwei- te Schaltstufe gezeigt ist. So besteht die Schaltstufe für das Bit 0, bzw. für das Bit zur Erzeugung des Bits 0 (SUMO 22b oder SUMO 22a) aus insgesamt zehn Transistoren 620-629, wobei immer zwei Transistoren zusammen einen Verzweigungs- punkt der in Fig. 5a und 5b gezeigten Verzweigungspunkte bil- den. Analog hierzu besteht die Schaltstufe für das Bit 1 (SUM1 24b bzw. SUM1 24a) aus lediglich acht Transistoren 630-637, wobei ebenfalls paarweise angeordnete Transistoren immer einen Verzweigungspunkt definieren.

Ferner sei darauf hingewiesen, daß die Situation des Rechen- potentials 16a, 16b gleich dem hohen Potential Vdd der Situa- tion entspricht, die die Schaltstufe 12b in den Fig. 4, 5a und 5b hat. Im einzelnen entsprechen die Transistoren 630 und 631 dem Verzweigungspunkt 52a. Die Transistoren 632,633 ent- sprechen dem Verzweigungspunkt 52b von Fig. 5a. Die beiden Transistoren 634 und 635 entsprechen dem Verzweigungspunkt 52d in Fig. 5a. Schließlich entsprechen die Transistoren 636 und 637 dem Verzweigungspunkt 52c.

Analog hierzu entsprechen in der Schaltstufe für das Bit 0 die beiden Transistoren 620 und 621 dem Verzweigungspunkt 50a von Fig. 5a. Die Transistoren 622,623 entsprechen dem Ver- zweigungspunkt 50b von Fig. 5a. Die Transistor 626 und 627 entsprechen dem Verzweigungspunkt 50c von Fig. 5a.

Die Schaltstufen umfassen ferner eine in Fig. 6 bei 639 ge- zeigte Ausgangsschiene, die gleichzeitig die Eingangsschiene für die nachgeschalteten Ausgabestufen darstellt. Die beiden rechten Leitungen der Ausgangsschiene 639 sind der oberen Ausgabestufe 14b zugeordnet, während die beiden linken Lei- tungen der Ausgabeschiene 639 der unteren Ausgabestufe 40a zugeordnet sind. Es sei darauf hingewiesen, daß die Transi- storen in den Schaltstufen wirksam sind, um lediglich einen Pfad vom Anschluß 16b bzw. 16b zu einer der Leitungen der Ausgabeschiene 40 durchzuschalten. Es ist ferner ersichtlich, daß jeder Pfad dieselbe Anzahl von Transistoren umfaßt, unab- hängig davon, welcher Pfad durch eine Schaltstufe abhängig von dem Bitmuster eingestellt wird.

Aus Fig. 6 ist ferner ersichtlich, daß bei dem gezeigten Aus- führungsbeispiel ein Verzweigungspunkt durch Verwendung eines komplementären Operandenbits zusätzlich zu dem nicht- invertierten Operandenbit implementiert wird. Dies ermöglicht eine einfache Implementierung dahingehend, daß lediglich zwei Transistoren verwendet werden, und daß keine Untersuchung des Bits dahingehend erforderlich ist, ob das Bit eine 0 oder ei- ne 1 hat. Alternativ könnte jedoch auch, obgleich es im Hin- blick auf die Implementation und mögliche Sicherheitseinbußen nicht bevorzugt wird, eine Implementierung eingesetzt werden, bei der lediglich Single-Rail-Operanden den Schaltstufen zu- geführt werden. In diesem Fall würde jeder Verzweigungspunkt eine zusätzliche Einrichtung dahingehend umfassen, um zu un- tersuchen, ob das zugeführte Bit eine 1 oder eine 0 ist, um einen entsprechenden Pfad durchzuschalten. In diesem Fall könnte der erfindungsgemäße Halbaddierer auch zur Single- Rail-Dual-Rail-Konversion verwendet werden, um eingangsseitig

vorliegende Single-Rail-Daten in ausgangsseitige Dual-Rail- Daten zu konvertieren, wobei die ausgangsseitigen Dual-Rail- Daten ferner gemäß der Halbaddierervorschrift von den ein- gangsseitigen Single-Rail-Daten abgeleitet worden sind.

Die Funktionalität der beiden als Schalter fungierenden Tran- sistoren beispielsweise 620 und 621, die den Verzweigungs- punkt 50a in Fig. 5a darstellen, ist ersichtlich, wenn davon ausgegangen wird, daß im Datenmodus immer nur ein Transistor durchschaltet, während der andere Transistor sperrt, so daß immer nur ein Pfad entweder nach oben oder nach unten genom- men wird, jedoch nie zwei Pfade gleichzeitig. Nachdem im Da- tenmodus die beiden Knoten 605 und 604, also die beiden Bits, die im Datenmodus den ersten Operanden darstellen, auf Vdd liegen, sind die Transistoren 620 und 621 im Vorbereitungsmo- dus beide gesperrt, so daß keine Querströme fließen können.

Die Schaltstufe wird somit aufgrund der Tatsache, daß in der Eingangsstufe ein Precharge verwendet wird und in der Schaltstufe PMOS-Transistoren verwendet werden, im Vorberei- tungsmodus automatisch dahingehend deaktiviert, daß keine Querströme von dem Knoten 16a bzw. 16b abfließen können. Wür- de die Dual-Rail-Eingangsstufe einer Discharge-Operation un- terzogen werden, würde es bevorzugt, die Transistoren der Schaltstufen in NMOS-Technik mit entsprechendem Rechenpoten- tial (Vss in diesem Fall) auszuführen.

Nachfolgend wird beispielhaft die transistormäßige Implemen- tierung der Ausgabestufe 14a erörtert, die insgesamt vier Transistoren 640,641, 642 und 643 aufweist. Da als Rechenpo- tential 16a, 16b das hohe Potential Vdd genommen wird, wird in Fig. 6 als Vorbereitungspotential das niedrige Potential Vss 20a verwendet. Entsprechend wird auch bei der zweiten Ausgabestufe 14b als Vorbereitungspotential das niedrige Po- tential Vss verwendet, also ein Potential, das sich von dem Rechenpotential Vdd unterscheidet.

Die Ausgabestufen 14a, 14b werden im Vorbereitungsmodus mit einem Pre-Discharge-Signal beaufschlagt, das aufgrund der Ausführung der Transistoren 640-643 in NMOS-Technik ein hohes Spannungssignal Vdd ist. Im Datenmodus liegt auf der Leitung 28a, 28b dagegen das niedrige Potential Vss an, um die Discharge-Transistoren 641,640 zu sperren.

Wird die Ausgabestufe 14a (genauso wie die Ausgabestufe 14b) dagegen im Vorbereitungsmodus betrieben, so liegt Vdd auf den Leitungen 28a, 28b (die in der tatsächlichen Implementierung als gemeinsame Leitung ausgeführt sind, an. Dies führt dazu, daß die beiden Knoten 22a, 22b auf Vss gelegt werden, da die beiden Transistoren 640,641, die in NMOS-Technik ausgeführt sind, durchgeschaltet werden. Dies führt unmittelbar dazu, daß der Transistor 643 ebenso gesperrt ist wie der Transistor 642. Die Transistoren 643,642 haben daher im Vorbereitungs- modus keine Wirkung. Im Datenmodus sind dagegen, wie es aus- geführt worden ist, die Discharge-Transistoren 640 und 641 gesperrt. Im Datenmodus wird einer der Knoten 22a, 22b auf- grund der Tatsache, daß die Schaltstufe das Potential Vdd 16a entweder auf den Knoten 22a oder auf den Knoten 22b durchge- schaltet hat, hoch. Zur Erläuterung der Funktionsweise der Transistoren 642 und 643 wird davon ausgegangen, daß der Kno- ten 22b hoch ist. Dies führt dazu, daß der Transistor 642 durchgeschaltet wird, um den Knoten 22a sicher auf das nied- rige Potential Vss zu legen. Damit wird gleichzeitig sicher- gestellt, daß der Transistor 643 gesperrt ist, was wiederum bewirkt, daß das Potential Vss, das auf der einen Seite des Transistors 643 anliegt, nicht an dem Knoten 22b anliegen kann, dahingehend, daß der Knoten 22b hoch bleibt, während der Knoten 22a sicher niedrig bleibt, so daß ein eindeutiges Ergebnis erhalten wird, nämlich daß das Bit SUMO hoch ist, während das komplementäre Bit SUMO niedrig ist.

Die Ausgabestufe hat daher neben der Funktionalität des ge- wissermaßen Lieferns des nicht durch die Schaltstufe bestimm- ten Bits im Datenmodus (aufgrund des vorausgehenden Vorberei-

tungsmodus) auch die Funktionalität, im Datenmodus beide Bits und insbesondere das nicht durch die Schaltstufe gelieferte Bit gegenüber Ladungslecks zu stabilisieren.

Ferner hat die erfindungsgemäß bevorzugte Implementierung der Ausgabestufen gemäß Fig. 6 den Vorteil, daß keine Querströme fließen, so daß die erfindungsgemäße Halbaddiererschaltung neben ihrer Eigenschaft der Flächeneffizienz und der Eigen- schaft der hohen Performance auch einen niedrigen Stromver- brauch hat.

Bezugszeichenliste 10 Eingangstufe 12 a-c Schaltstufen 14 a-c Ausgabestufen 16 a-c Rechenpotentialanschlüsse 18 a-c Ausgänge 20 a Anschluß 20 b-c Eingänge 22 a-b Ausgänge 24 a-b Ausgänge 26 a-b Ausgänge 28 Steuereinrichtung 28 a-d Steuerleitungen 40 Ausgabeschiene 41-43 Linien 50 a-c Schaltknoten 52 a-c Verzweigungspunkte 80 Drei-Bit-Halbaddierer 81 Zwei-Bit-Volladdierer 82 Summenbit 83 Übertragbit 600-603 Transistoren 604 Ausgangsknoten 605 Ausgangsknoten 611-613 Verteilungsschienen 620-629 Transistoren 630-637 Transistoren 640-643 Transistoren