DE1217108B - Rechengeraet zum Logarithmieren von Binaerzahlen - Google Patents

Description

BUNDESREPUBLIK DEUTSCHLAND

DEUTSCHES

PATENTAMT

AUSLEGESCHRIFT

Int. Cl.:

Deutsche Kl.

G06f

42m-14

s? m_q

Nummer: 1217108 U£^

Aktenzeichen: E 30012IX c/42 m

Anmeldetag: 31. August 1965

Auslegetag: 18. Mai 1966

Die Erfindung betrifft ein Rechengerät zum Ermitteln des Logarithmus zur Basis zwei von Binärzahlen N unter Benutzung der Näherung

1Og₂A? = log₂ [2*<1+jc)] = k+log₂(l+x)^k+x;

bei ganzzahligen k und O^x<Cl mit Hilfe eines Schieberegisters, in dem χ durch so-oft-faches Verschieben von N gebildet wird, bis die höchstwertige gültige Ziffer aus dem Register fällt, wobei in einem Zähler die Verschiebeschritte als Maß für k gezählt werden.

Rechengeräte bestimmen den Logarithmus einer Zahl entweder durch Reihenentwicklung, durch Rekursionsformeln oder unter Benutzung der obengenannten Näherungsbeziehung (IRE-Transactions EC-Il, 1962, S. 512 bis 517). Während die ersteren Verfahren sich insbesondere für Universalrechenmaschinen eignen und die Rechengenauigkeit nur durch den Programm- und Zeitaufwand beschränken, ist das letztgenannte Verfahren speziell für Kleinrechengeräte entwickelt worden, die mit weitgehend festem Programm arbeiten und in der Meß- und Regeltechnik eingesetzt sind. Wegen des einfachen Rechenablaufs reduziert sich hierbei der äußere Aufwand auf ein einziges Register und einen Zähler, in denen nach wenigen Elementarschritten das Endergebnis ermittelt ist, dafür ist aber der maximal mögliche Fehler nicht unerheblich:

^Rimax(x) = Iog₂(l +x) -x = 0,086 für χ - 0,44.

Die Erfindung löst die Aufgabe, das obenerwähnte einfachste Rechengerät derart zu erweitern, daß der materielle Aufwand noch so begrenzt bleibt, daß es sich weiterhin als Spezialrechner für die Meß- und Regeltechnik eignet, dessen Rechengenauigkeit jedoch wesentlich über der durch die obige Näherung gegebenen liegt.

Die Erfindung besteht darin, daß das Schieberegister akkumulationsfähig ist und mit einer Korrektureinrichtung verbunden ist, die auf den Wert χ abhängig von den höchstwertigen Binärstellen von χ verschiedene Korrekturgrößen (Konstante und Funktionen von x) aufaddiert und daß zur Bildung der Funktionen von χ ein weiteres schiebefähiges Register vorgesehen ist, in das zu Beginn der Korrekturprozedur χ gesetzt wird, um später je nach gewünschter Korrektur in Normal- oder Inversionsform und in geeigneter Stellenzuordnung additiv dem ersten Schieberegister zugeführt zu werden.

Nachfolgend wird die Erfindung an einem Modell Rechengerät zum Logarithmieren von Binärzahlen

Anmelder:

Europäische Atomgemeinschaft (EURATOM),

Brüssel

Vertreter:

Dr.-Ing. E. Hoffmann, Dipl.-Ing. W. Eitle
und Dr. rer. nat. K. Hoffmann, Patentanwälte,
München 8, Maria-Theresia^Str. 6

Als Erfinder benannt:
Michel Combet, Travedona;^; ■
Hans H. van Zonneveld, Brenta;
Leo A. M. Verbeek, Taino (Italien)

des erfindungsgemäßen Rechengeräts mit Hilfe der Fig. 1 bis 3 näher erläutert, von denen

F i g. 1 ein logisches Schaltbild des gesamten Rechengeräts zeigt,

F i g. 2 die Verdrahtung der Programmsteuereinheit des Geräts in schaltalgebraischer Schreibweise sowie
F i g. 3 ein erläuterndes Diagramm.

Der Einfachheit halber wird nachfolgend davon ausgegangen, daß N eine positive Zahl größer oder gleich EINS sei. Das zu beschreibende Gerät läßt sich aber leicht derart modifizieren, daß diese Beschränkung wegfällt. Diese Zahl N wird also zu Beginn des Rechenablaufs in ein Schieberegister eingegeben und darin so lange geschoben, bis die erste gültige Ziffer (d.h. eine EINS) aus dem Register herausfällt. Ein Zähler zählt dabei — beginnend von der Gesamtzahl m der Registerelemente des Registers 13 — abwärts. Da der Schiebevorgang nach m—k Schritten abgebrochen wird, wenn k die ursprüngliche Stelle der höchstwertigen gültigen Ziffer bezeichnet, gibt der Zähler gerade m—(m—k)=k als Endstand wieder. Der Registerinhalt ist dann gerade x. In erster Näherung log^iV) ergibt k-\- χ den Wert des gewünschten Logarithmus.

Für N= 11010,101 beispielsweise ist k=4 (dezimal) und x=0,1010101, also \og_Ai{N) = 100,1010101. Fig. 3 zeigt ein Diagramm, in dem über χ in ausgezogener Linie der log(l+x), in strichpunktierter Linie die erste Näherung gemäß der erwähnten Literaturstelle 1Og^₄₁(I+x) und in regelmäßig unter-

609 569/384

brochener Linie die durch die erfindungsgemäße Erweiterung des Geräts erzielte zweite Näherung log^₂(l+jc) gezeigt ist, wobei die Abweichung von dem Ideal zur besseren Darstellung übertrieben gezeichnet ist.

Man erkennt daraus bereits, daß diese zweite Näherung durch Einteilung von χ in vier Bereiche und durch Linearapproximation innerhalb der Bereiche erzielt wird.

Allgemein gesprochen, ist es für die elektrische Realisierung vorteilhaft, χ in 2" Bereiche einzuteilen, wobei q eine positive ganze Zahl bedeutet. Bereits mit q=2 wird eine wesentliche Verkleinerung des maximalen Fehlers um den Faktor 6 erzielt. Für q=3 könnte man den Maximalfehler nochmals verkleinern. Für das gewählte Ausführungsbeispiel sind folgende Näherungen für die vier Unterbereiche (q=2) vorgesehen:

1. Bereich:

für 0

2. Bereich: Iog₄₂(l + x) — χ +

3. Bereich: log_4a (1

4. Bereich:

+ x) — x + —τ- x

fur

3 1 3

Ί28" ^iurT^^X<T'

für 4- < * < 1 .

4 ^

Hierbei bedeutet χ das durch Inversion aller Binärstellen entstandene Komplement von x. Die Koeffizienten der Korrekturgrößen sind so ausgesucht, daß sie sich in der Digitaltechnik leicht erzeugen lassen.

Trotzdem benötigt man — wie Fig. 1 deutlich zeigt — für die zweite Näherung nicht nur Zähl- und Schieberegister, sondern auch eine Reihe von logischen Verknüpfungsgliedern, Hilfsregistern und eine kleine verdrahtete Programmsteuereinheit.

Im nachfolgenden wird das logische Schaltbild des Rechengeräts gemäß F i g. 1 im einzelnen erläutert, und es wird gezeigt, wie die obenerwähnten Größen gebildet werden und wie die Korrektur ausgeführt wird.

Die Zahl N, deren Logarithmus gesucht ist, wird dem Rechengerät über einen Eingang 11 angeboten. Die ZahliV steht beispielsweise in einem außerhalb des Rechengeräts liegenden Register bereit, aus dem sie schrittweise, beginnend mit der höchstwertigen Stelle, über einen Steuerausgang 12 des Rechengeräts abgerufen wird. Sie gelangen von dem Eingang 11 sowohl in das Schieberegister 13 als auch in ein Hilfsregister 14, in dem später die Korrekturgrößen gebildet werden.

Der bekannte Ablauf zur Bildung des Logarithmus erster Näherung betrifft neben dem erwähnten Schieberegister 13 einen Zähler 15, der vor Beginn des Rechenvorgangs auf die Zahl m=7, die zugleich sein Zählmodul ist, eingestellt wurde.

Dem Schieberegister 13 ist aus später noch zu erläuternden praktischen Gründen ein weiteres gleich großes Schieberegister 16 als Fortsetzung vorgeschaltet, dessen niedrigstwertige Stelle r₈ von einer Programmsteuereinheit 17 daraufhin untersucht wird, ob sie bereits eine gültige EINS-Zifier der Zahl enthält. In diesem Augenblick wird nämlich der von der Programmsteuereinheit über einen Wirkausgang a überwachte Verschiebevorgang abgebrochen; dann stehen im Zähler 15 der Wert k und im Register 13 der Wert χ als Logarithmus erster Näherung bereit.

Während des Schiebevorgangs wurde zugleich mit dem Schieberegister 13 das Hilfsregister 14 mit dem Wert χ gefüllt. Die höchstwertige gültige Ziffer ist as beim letzten Verschiebeschritt ohne Wirkung aus diesem Hilfsregister herausgefallen. Nun gibt die Steuereinheit über einen Ausgang b einen Impuls ab, der vier UND-Tore 18 bis 21 öffnet. An diesen Toren liegen die vier möglichen Kombinationen der Normal- und Inversausgänge der beiden höchstwertigen Binärstellen von χ an. Demgemäß öffnet sich mit dem Impuls von dem Ausgang b stets eines der vier Tore und setzt damit eines oder mehrere Flip-Flops eines Korrekturregisters 22 in den EINS-Zustand.

Jedes der sieben Flip-Flops dieses Registers entspricht einer von sieben Korrekturoperationen gemäß den oben aufgeführten Korrekturgrößen.

Eines dieser sieben Flip-Flops bewirkt beispielsweise die Addition von dem Inhalt des Registers 13 und J x; es wird eingeschaltet, wenn χ im vierten Bereich liegt. Ein UND-Tor 23 wird durch dieses Flip-Flop aktiviert, wenn die die höchstwertige Stelle des Hilfsregisters eine NULL anzeigt. Der Ausgang dieses Tores ist mit dem Wechseleingang des dritthöchstwertigen Flip-Flops des akkumulationsfähig ausgerüsteten Schieberegisters 13 verbunden, so daß ein Impuls auf dieser Verbindungsleitung das erwähnte Flip-Flop wechselt und gegebenenfalls einen Übertrag in höhere Stellen leitet.

Eine ganz ähnliche Schaltung ist für die anderen Korrekturgrößen vorgesehen, wobei zu beachten ist, daß die Korrekturen mittels Linearfunktion von χ oder χ (davon gibt es vier) vor den Korrekturen mit

. Konstanten (davon gibt es drei) ausgeführt werden.

Die Steuereinheit 17 sorgt für diesen zeitlichen Ablauf und auch dafür, daß nicht gleichzeitig an zwei verschiedenen Stellen Akkumulationsimpulse auf das Schieberegister 13 gegeben werden. Ein Steuerausgang c aktiviert die Korrekturen J χ und J χ zuerst für die höchstwertige Stelle von x, dann aktiviert ein Steuerausgang d die beiden restlichen Korrekturfunktionen von x, worauf die Inhalte der Schieberegister 13 und 16 sowie 14 um eine Binärstelle in Richtung höherwertiger Stellen verschoben werden (durch Aktivierung des Steuerausgangs ä). Dann erfolgt dieselbe Korrektur wie beschrieben mit der zweithöchstwertigen Stelle von x, die sich nun im" Hilfsregister an der höchstwertigen Stelle befindet. Wieder werden

i 217

die Steuerausgänge c und d nacheinander aktiviert. Erst nachdem alle sieben Stellen von χ durch das Hilfsregister 14 gewandert sind, ist die Korrrektur mit den Funktionen von χ vollständig, und der teilkorrigierte Wert ist in das Fortsetzungs-Schieberegister 16 gewandert. Die sieben Schiebeschritte überwacht ein Zähler Z in der Steuereinheit, dessen Endstand erst den Beginn der Korrekturen mit Konstanten zuläßt. Dann werden nämlich nacheinander weitere Steuerausgänge e, f und g aktiviert, die die Korrekturen mit den Konstanten

T^)' ("έ") ^und (w)

(w)

durch Impulse an geeigneter Stelle im Verlängerungsregister 16 veranlassen, falls die zugehörigen Flip-Flops 22 des Korrekturregisters gesetzt waren. Damit befindet sich der korrigierte Wert von χ im Verlängerungsregister, und an einem mit »stop« bezeichneten Ausgang erscheint ein Impuls, der zur Anzeige des Rechenendes nach außen hin Verwendung finden kann. Schließlich ist noch ein von außen ansteuerbarer Ausgang S₀ in der Programmsteuereinheit zu erwähnen, über den das Rechengerät <C—> in Betrieb gesetzt wird (durch Löschen aller Flip-Flops des Geräts). Der Zähler 15, der vor Beginn der Korrekturoperationen bereits den nicht mehr korrekturbedürftigen Wert k angab, ist während der Korrekturoperationen aus Gründen der Programmvereinfachung nochmals um seinen Zählmodul weitergezählt worden, so daß er abschließend wieder den Wert k angibt.

In Fig. 2 ist die Verdrahtung der Programmsteuereinheit in schaltalgebraischer Schreibweise angegeben, aus der sich eindeutig etwa die Realisierung mit Dioden-UND-Toren ergibt: jede Zeile entspricht einem UND-Tor, dessen Ausgang auf die links angegebenen Flip-Flop-Eingänge oder Steuerleitungen einen Impuls sendet, wenn die Kunjunktionsbedingung auf der rechten Seite des Schrägstriches erfüllt ist. In der ersten Zeile beispielsweise ist gesagt, daß ein Sequenzglied S₁ eingeschaltet werden soll und alle Flip-Flops Rn des Rechengeräts ausgeschaltet werden, wenn auf dem Starteingang S₀ ein Impuls erscheint. Die Sequenzglieder S₀ sind Flip-Flops, die automatisch mit jedem der nicht gezeichneten Taktimpulse ausgeschaltet werden oder aber in ungetakteter Technik als monostabile Flip-Flops ausgebildet sind. Außer den bereits erwähnten Steuerausgängen α bis g sind in dieser Fig. 2 noch der Zähleingang Z'₊₁ und die Zählerausgänge z_max und Zmax aufgeführt, die erregt sind, wenn dieser Zähler seinen Endstand sieben erreicht bzw. nicht erreicht hat. Diese Figur gibt also sowohl die interne Schal-

45 tung der Programmsteuereinheit als auch das Flußdiagramm für den Funktionsablauf wieder, so daß abschließend nur noch an Hand eines Zahlenbeispiels gezeigt zu werden braucht, wie die Korrektur an einem praktischen Beispiel vollzogen wird. Ausgehend von dem schon erwähnten Zahlenbeispiel N — 11010,101 wurde schon erläutert, wie daraus in dem Zähler 15 die Zahl 100 und in dem Register 13 in erster Näherung χ = 1010101 entsteht. Beim anschließenden Aktivieren der Leitung b wird allein das UND-Tor 19 geöffnet, wodurch drei Flip-Flops 22 des Korrekturregisters gesetzt werden. Im Laufe

der sieben Korrekturzyklen wird -=- χ hinzugezählt,

wobei der Registerinhalt schrittweise in das Verlängerungsregister 16 wandert. Im Verlängerungsregister steht dann 1011010. Nun folgen nur noch die drei (d.h. effektiv zwei) Korrekturschritte mit Konstanten, und das Endergebnis ist gebildet: der Logarithmus von 11010,101 ist in zweiter Näherung 100,1011101. Wenn die Erfindung auch an Hand des erprobten Ausführungsbeispiels erläutert wurde, so stellt dieses mit all seinen Einzelheiten doch nicht die einzig mögliche Ausführungsform der Erfindung dar. Bezüglich der technischen Realisierung bestehen keinerlei Einschränkungen, und es kann auf die reichhaltige Literatur von logischen Schaltungen, Impulsformern, Flip-Flops und Taktgeneratoren verwiesen werden.

Claims (1)

1. Patentanspruch:

   Rechengerät zum Ermitteln des Logarithmus zur Basis zwei von Binärzahlen N unter Benutzung der Näherung

   log₂AT = Iog₂[2^ft (1+jc)] = k +.Iog₂(l+jc)« k+x

   bei ganzzahligem k und ο <Jjc<Cl mit Hilfe eines Schieberegisters, in dem χ durch so-oft-faches Verschieben von N gebildet wird, bis die höchstwertige gültige Ziffer aus dem Register fällt, wobei in einem Zähler die Verschiebeschritte als Maß für k gezählt werden, dadurch gekennzeichnet, daß das Schieberegister akkumulationsfähig ist und mit einer Korrektureinrichtung verbunden ist, die auf den Wert χ abhängig von den höchstwertigen Binärstellen von χ verschiedene Korrekturgrößen (Konstante und Funktionen von x) aufaddiert, und daß zur Bildung der Funktionen von χ ein weiteres schiebefähiges Register vorgesehen ist, in das zu Beginn der Korrekturprozedur χ gesetzt wird, um später je nach gewünschter Korrektur in Normal- oder Inversionsform und in geeigneter Stellenzuordnung additiv dem ersten Schieberegister zugefügt zu werden.

   Hierzu 1 Blatt Zeichnungen

   609 569/384 5.66 © Bundesdruckerei Berlin