WO1993025959A1 - Verfahren und anordnung zum bilden der summe einer kette von produkten - Google Patents

Verfahren und anordnung zum bilden der summe einer kette von produkten Download PDF

Info

Publication number
WO1993025959A1
WO1993025959A1 PCT/NL1993/000117 NL9300117W WO9325959A1 WO 1993025959 A1 WO1993025959 A1 WO 1993025959A1 NL 9300117 W NL9300117 W NL 9300117W WO 9325959 A1 WO9325959 A1 WO 9325959A1
Authority
WO
WIPO (PCT)
Prior art keywords
arrangement
register
product
output
sum
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/NL1993/000117
Other languages
English (en)
French (fr)
Inventor
Harald Bauer
Johannes Schuck
Karl Hellwig
Dietmar Lorenz
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Philips Intellectual Property and Standards GmbH
Koninklijke Philips NV
Original Assignee
Philips Patentverwaltung GmbH
Philips Electronics NV
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Philips Patentverwaltung GmbH, Philips Electronics NV filed Critical Philips Patentverwaltung GmbH
Priority to KR1019940700362A priority Critical patent/KR100271074B1/ko
Priority to DE59309652T priority patent/DE59309652D1/de
Priority to JP6501341A priority patent/JPH07501167A/ja
Priority to EP93916269A priority patent/EP0598112B1/de
Priority to US08/190,068 priority patent/US5602766A/en
Publication of WO1993025959A1 publication Critical patent/WO1993025959A1/de
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G06F7/5443—Sum of products

Definitions

  • the invention relates to a method for forming the sum of a chain of products from two numbers in each case, which are fed one after the other, each intermediate result of the sum formation being buffered, and to an arrangement for forming the sum of a chain of products from a first one and a second value, with a memory arrangement for storing a number of values with a predetermined first number of bits, a clock-controlled control arrangement for controlling the writing of values into registers, a first register arrangement for recording two values to be multiplied with each other, a multiplier arrangement with two
  • Inputs that are connected to the first register arrangement and a downstream product register with an output for twice the first number of bits, an adder arrangement with two sum inputs for each of the first number of bits, one of which can be coupled to the output of the product register and a downstream sum register made up of at least two partial sum registers for each of the first number of bits, with an output which can be coupled to the other input of the adder arrangement.
  • the object of the invention is to provide a method of the type mentioned at the outset which enables the formation of the sum of a chain of products with little effort and at only a slightly reduced speed.
  • This object is achieved according to the invention in that the product which arises in each individual multiplication is added to the intermediate result in two steps, in that in the first step only the digits of lowest value of the product are added to the corresponding digits in the intermediate result and the first partial result sum is temporarily stored and in the second step the remaining digits of higher value of the product are added to the corresponding remaining digits of the subtotal and the transfer of the first partial sum and the resulting second partial sum is temporarily stored, with a different one of the numbers to be multiplied immediately afterwards being fed in becomes.
  • Another object of the invention is to provide an arrangement of the type mentioned at the outset which enables the formation of the sum of a chain of products with less effort and with only a slightly reduced speed.
  • the memory arrangement (12) is connected to the first register arrangement (16, 18) for the first number of bits via only one data bus (14) and in that the control arrangement (10) is set up to alternate in to work a first and a second clock time and in the first clock time the first number of bits of lowest value at the output of the product register (22) and the content of the second partial sum register (32) to the inputs of the adder arrangement (26) and at the end of this cycle time one of the first values (B j ) into the register arrangement (16) and at the output of the adder arrangement ( 26) to write in the existing new partial sum in the second partial sum register (32) and in the second cycle time to add the first number of bits of the highest value at the output of the product register (22) and the content of the first partial sum register as well as a buffered transfer of the adding arrangement (26) and at the end of this cycle time one of the second values (A i + 1 ) into the register arrangement (16, 18) and the second partial sum available at the output of the adding arrangement (2
  • Each complete partial sum is thus formed in two cycle times, so that the processing speed is halved overall. For this, however, only a simple data bus is required, over which the values to be processed are transmitted one after the other, and an addition arrangement with only the simple word width is also sufficient, which determines the partial sums in succession in the two cycle times. Since initially only the partial sum is formed from the least significant bits, the carryover from the first partial sum is available for the formation of the second partial sum. This means that no rounding error, since all existing locations are evaluated actually borrowed, while the exact result "-Will finally taken from the second partial sum register can.
  • FIG. 2 shows the chronological sequence of the individual values that occur at different points within the block diagram according to FIG. 1.
  • a control arrangement 10 generates two control signals T1 and T2 on lines 8 and 9, which alternate cyclically. Furthermore, the control arrangement 10 generates addresses for addressing an output 11
  • connection 11 is drawn twice here, since it actually consists of a number of parallel lines via which the bits of an address are transmitted in parallel. This also applies to the data connections, which are also drawn twice, and which likewise actually consist of several lines, via which the bits of one data word are transmitted in parallel.
  • the writing into these registers is controlled by control signals on lines 8 and 9.
  • the outputs 17 and 19 of the registers 16 and 18, which are intended to accommodate the factors to be multiplied with one another, are connected to the inputs of a multiplication arrangement "20, which, within one cycle time, produce the complete product of the two the connections 17 : and 19 supplied values chansefc and the product outputs at the output 21.
  • This has twice the word width, ie twice the number of bits of the supplied factors. This is the only point within the arrangement according to FIG. 1 at which a double word width occurs, and the connection 21 is connected to the input of a product register 22 which is also designed for this double word width.
  • connections 23 and 29 are connected to the product register 22, of which the connection 23 carries the bits with the highest significance and the connection 29 carries the bits with the lowest significance, i.e. each connection has the simple word width.
  • the connections 23 and 29 lead to a multiplexer which, controlled by a control signal on the line 8, connects the connection 23 or the connection 29 to an input 25 of an adder arrangement 26.
  • the other input 35 of the adder arrangement 26 is connected to the output of a second multiplexer 34.
  • the sum output 27 of the adder 26 leads in parallel to the inputs of two partial sum registers 30 and 32, which are alternately controlled for writing via the control lines 8 and 9.
  • a carry memory 28 is also provided, in which the carry over at the control line 8 is written parallel to the second total register at the output 27a of the adder arrangement 26.
  • the outputs 31 and 33 of the partial sum registers 30 and 32 lead to the two inputs of the multiplexer 34, which is controlled via the control line 8, either the output 31 ⁇ sai-ünen with the output 37 of the transfer memory 28 or the output 33 with the second input 35 of the Adding arrangement 26 connects.
  • the output 31 also leads to the processing of the chain of products that are sought. However, it is often expedient if the content of register 32 can also be read out and fed to other elements.
  • Time t 0 at the end of a second cycle time T2 thus represents an arbitrarily selected time within the processing of the chain of products.
  • the one factor A i of the product P- currently being formed which during this Cycle time T2 from the
  • Memory arrangement 12 has been read out, written into the register 16, * by the rising signal on the line 8 for the first clock time T1. At the same time, the previous product P i . 1 in the product register 22. wrote.
  • the partial sum registers 30 and 32 are not yet considered in detail here.
  • the second value B i of the product to be formed is read out of the memory arrangement 12 and fed to the input of the register 18 via the data bus 14.
  • the multiplexer 24 is controlled by the low signal on the control line 9 during this cycle time in such a way that the connection 29 with the least significant bits of the product P is coupled to the input 25 of the adder arrangement 26, and at the same time the one controlled in the same way Multiplexer 34 the output 33 of the partial sum register 32 coupled to the input 35 of the adder 26.
  • the second value B 1 is then read out and written into the register 18 at the time t 1 .
  • the first product P 1 can then be formed, which is written into the product register 22 at the time t 2 .
  • the product P 1 can be processed in the already observed manner, whereby during this previous 1 processing step, the TOIL, total register 30 and 32 must of course be deleted, ie they must contain the value zero. In this way, the sum of a chain of products is formed, the full accuracy being retained without rounding errors and nevertheless only one adder being required for the simple word width.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computational Mathematics (AREA)
  • Computing Systems (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Complex Calculations (AREA)

Abstract

Bei der digitalen Signalverarbeitung wird häufig die Summe einer Kette von Produkten benötigt, wobei deren Bildung möglichst schnell erfolgen soll. Bekannte Signalprozessoren verwenden häufig zwei getrennte Datenbusse, über die die jeweils zu multiplizierenden Werte parallel zugeführt werden, wobei vorausgesetzt wird, daß diese Werte von verschiedenen Quellen, beispielsweise von verschiedenen Speichern stammen, und da ein Produkt von zwei Binärzahlen die doppelte Anzahl von Stellen hat, wird daher auch ein Addierer mit der doppelten Wortbreite verwendet. Um diesen erheblichen Aufwand bei nur geringer Verringerung der Verarbeitungsgeschwindigkeit zu reduzieren, wird erfindungsgemäß vorgeschlagen, einen Addierer mit nur einfacher Wortbreite zu verwenden und die Bits höchster und niedrigster Wertigkeit des Produktes in zwei aufeinanderfolgenden Taktphasen zu verarbeiten, wobei dann gleichzeitig die zu multiplizierenden Werte nacheinander zugeführt werden können.

Description

BESCHREIBUNG
Verfahren und Anordnung zum Bilden der Summe einer Kette von Produkten
Die Erfindung betrifft ein Verfahren zum Bilden der Summe einer Kette von Produkten aus je zwei Zahlen, die nachein¬ ander zugeführt werden, wobei jedes Zwischenergebnis der Summenbildung zwischengespeichert wird, sowie eine Anord¬ nung zum Bilden der Summe einer Kette von Produkten aus jeweils einem ersten und einem zweiten Wert, mit einer Speicheranordnung zum Speichern einer Anzahl von Werten mit einer vorgegebenen ersten Anzahl Bits, einer taktge¬ steuerten Steueranordnung zum Steuern des Einschreibens von Werten in Register, einer ersten Registeranordnung zum Aufnehmen von jeweils zwei miteinander zu multipli- zierenden Werten, einer Multiplizieranordnung mit zwei
Eingängen, die mit der ersten Registeranordnung verbunden sind, und einem nachgeschalteten Produktregister mit einem Ausgang für die doppelte erste Anzahl Bits, einer Addier¬ anordnung mit zwei Summeneingängen für je die erste Anzahl Bits, von denen der eine mit dem Ausgang des Produkt¬ registers koppelbar ist, und einem nachgeschalteten Sum¬ menregister aus wenigstens zwei Teilsummenregistern für je die erste Anzahl Bits, mit einem Ausgang, der mit dem anderen Eingang der Addieranordnung koppelbar ist.
Derartige Verfahren treten häufig auf bei der digitalen Signalverarbeitung, beispielsweise beim Filtern von Signalverläufen, und derartige Anordnungen werden bei vielen Vielzweck-Signalprozessoren verwendet. Um Signal- folgen mit hoher Frequenz verarbeiten ~ ιx können, weisen übliche SignalProzessoren zwei Datenbusse auf, um in jeder Taktzeit ein
Figure imgf000003_0001
Produkt bilden zu können. Da dieses Produkt außerdem die doppelte Anzahl Bits, d.h. die doppelte Wortbreite aufweist, ist die Addieranordnung auch für die doppelte Wortbreite ausgelegt. Dies stellt jedoch einen relativ hohen Aufwand dar.
Aufgabe der Erfindung ist es, ein Verfahren der eingangs genannten Art anzugeben, die die Bildung der Summe einer Kette von Produkten mit wenig Aufwand bei nur wenig ver¬ ringerter Geschwindigkeit ermöglicht.
Diese Aufgabe wird erfindungsgemäß dadurch gelöst, daß das bei jeder einzelnen Multiplikation entstehende Produkt in zwei Schritten zum Zwischenergebnis addiert wird, indem im ersten Schritt nur die Stellen niedrigster Wertigkeit des Produkts zu den entsprechenden Stellen des Zwischener¬ gebnisses addiert und die dabei entstehende erste Teil- summe zwischengespeichert wird und im zweiten Schritt die restlichen Stellen höherer Wertigkeit des Produkts zu den entsprechenden restlichen Stellen der Zwischensumme und dem Übertrag der ersten Teilsumme addiert und die dabei entstehende zweite Teilsumme zwischengespeichert wird, wobei in jedem Schritt eine andere der unmittelbar anschließend zu multiplizierenden Zahlen zugeführt wird.
Eine weitere Aufgabe der Erfindung besteht darin, eine Anordnung der eingangs genannten Art anzugeben, die das Bilden der Summe einer Kette von Produkten mit weniger Aufwand bei nur wenig verringerter Geschwindigkeit ermöglicht.
Diese Aufgabe wird erfindungsgemäß dadurch gelöst, daß die Speicheranordnung (12) über nur einen Datenbus (14) für die erste Anzahl Bits mit der ersten egisteranordnung (16,18) verbunden ist und daß die Steueranordntiag (10) eingerichtet .Eist, um abwechselnd in einer ersten und einer zweiten Taktzsit zu arbeiten und in der ersten Taktzeit die erste Anzahl Bits niedrigster Wertigkeit am Ausgang des Produktregisters (22) und den Inhalt des zweiten Teil¬ summenregisters (32) den Eingängen der Addieranordnung (26) zuzuführen und am Ende dieser Taktzeit einen der ersten Werte (Bj) in die Registeranordnung (16) und die am Ausgang der Addieranordnung (26) vorhandene neue Teilsumme in das zweite Teilsummenregister (32) einzuschreiben und in der zweiten Taktzeit die erste Anzahl Bits höchster Wertigkeit am Ausgang des Produktregisters (22) und den Inhalt des ersten Teilsummenregisters sowie einen zwi- schengespeicherten Übertrag der Addieranordnung (26) zuzu¬ führen und am Ende dieser Taktzeit einen der zweiten Werte (Ai+1) in die Registeranordnung (16,18) und die am Ausgang der Addieranordnung (26) vorhandene zweite Teilsumme in das erste Teilsummenregister sowie das von der Multipli- zieranordnung (20) gebildete Produkt in das Produktre¬ gister (22) einzuschreiben.
Jede vollständige Teilsumme wird dabei also in zwei Takt¬ zeiten gebildet, so daß die Verarbeitungsgeschwindigkeit insgesamt halbiert ist. Dafür ist jedoch nur ein einfacher Datenbus erforderlich, über den die zu verarbeitenden Werte nacheinander übertragen werden, und es ist ferner auch eine Addieranordnung mit nur der einfachen Wortbreite ausreichend, die die Teilsummen in den beiden Taktzeiten nacheinander bestimmt. Da zunächst nur die Teilsumme aus den Bits niedrigster Wertigkeit gebildet wird, steht für die Bildung der zweiten Teilsumme der Übertrag aus der ersten Teilsumme jeweils zur Verfügung. Dadurch entstehen keine Rundungsfehler, da alle vorhandenen Stellen tatsäch- lieh ausgewertet werden, während das genaue Ergebnis schließlich dem zweiten Teilsummenregister entnommen -werden"kann.
Ein Ausführungsbeispiel der Erfindung-wird nachstehend anhand der Zeichnung näher erläutert», Es zeigen Fig. 1 ein Blockschaltbild der wichtigsten Teile einer erfindungsgemäßen Anordnung,
Fig. 2 die zeitliche Folge der einzelnen Werte, die an verschiedenen Stellen innerhalb des Blockschaltbildes nach Fig. 1 auftreten.
In Fig. 1 erzeugt eine Steueranordnung 10 zwei Steuer¬ signale Tl und T2 auf den Leitungen 8 und 9, die sich zyklisch abwechseln. Ferner erzeugt die Steueranordnung 10 an einem Ausgang 11 Adressen zur Adressierung einer
Speicheranordnung 12. Die Verbindung 11 ist hier doppelt gezeichnet, da diese tatsächlich aus einer Anzahl paralleler Leitungen besteht, über die die Bits einer Adresse parallel übertragen werden. Dies gilt auch für die ebenfalls doppelt gezeichneten Datenverbindungen, die ebenfalls tatsächlich aus mehreren Leitungen bestehen, über die die Bits jeweils eines Datenworts parallel über¬ tragen werden.
Der Datenanschluß der Speicheranordnung 12, die auch aus mehreren einzelnen Speichern einschließlich gegebenenfalls Festwertspeichern bestehen kann, ist mit einem Datenbus 14 verbunden, an den außer weiteren, nicht dargestellten Einrichtungen eines Prozessors die beiden Register 16 und 18 parallel angeschlossen sind. Das Einschreiben in diese Register wird durch Steuersignale auf den Leitungen 8 und 9 gesteuert.
Die Ausgänge 17 und 19 der Register 16 und 18, die zum Aufnehmen der miteinander zu multiplizierenden Faktoren bestimmt sind, sind mit den Eingängen einer Multip}izier- anordnung"20 verbunden, die innerhal -einer Taktzeit-das voll-ständige Produkt der beiden über die Verbindungen 17 :und 19 zugeführten Werte bildsefc und das Produkt am Aus- gang 21 abgibt. Dieses weist die doppelte Wortbreite, d.h. die doppelte Anzahl Bits der zugeführten Faktoren auf. Dies ist die einzige Stelle innerhalb der Anordnung nach Fig. 1, an der eine doppelte Wortbreite auftritt, und die Verbindung 21 ist mit dem Eingang eines Produkt- registers 22 verbunden, das ebenfalls für diese doppelte Wortbreite ausgelegt ist.
An das Produktregister 22 sind ausgangsseitig zwei Ver¬ bindungen 23 und 29 angeschlossen, von denen die Ver- bindung 23 die Bits höchster Wertigkeit und die Verbin¬ dung 29 die Bits niedrigster Wertigkeit führt, d.h. jede Verbindung hat die einfache Wortbreite. Die Verbin¬ dungen 23 und 29 führen auf einen Multiplexer, der über ein Steuersignal auf der Leitung 8 gesteuert die Verbin- düng 23 oder die Verbindung 29 mit einem Eingang 25 einer Addieranordnung 26 verbindet. Der andere Eingang 35 der Addieranordnung 26 ist mit dem Ausgang eines zweiten Multiplexers 34 verbunden.
Der Summenausgang 27 des Addierers 26 führt parallel auf die Eingänge zweier TeilSummenregister 30 und 32, die über die Steuerleitungen 8 und 9 abwechselnd zum Einschreiben angesteuert werden. Bei dem zweiten TeilSummenregister 32 ist ferner ein Ubertragspeicher 28 vorgesehen, in den parallel zum zweiten Summenregister der am Ausgang 27a der Addieranordnung 26 auftretende Übertrag über die Steuer¬ leitung 8 eingeschrieben wird.
Die Ausgänge 31 und 33 der Teilsummenregister 30 und 32 führen auf die beiden Eingänge des Multiplexers 34, der über die Steuerleitung 8 gesteuert entweder den Ausgang 31 ^ sai-ünen mit de Ausgang 37 des Ubertragspeichers 28 oder den Ausgang 33 mit dem zweiten Eingang 35 der Addieranord¬ nung 26 verbindet. Der Ausgang 31 führt ferner aππ EJa e der Verarbeitung der Kette von Produkten die gesucht® Stimme. Es ist jedoch häufig zweckmäßig, wenn auch der Inhalt des Registers 32 ausgelesen und anderen Elementen zugeführt werden kann.
Die Funktion der Anordnung nach Fig. 1 wird nun anhand des schematischen Zeitdiagramms in Fig. 2 erläutert, in der die Zahlen vor den einzelnen Zeilen die Signale bzw. Werte auf den Verbindungen bzw. die Inhalte der Blöcke mit den betreffenden Bezugszeichen angeben. Mit der Anordnung nach Fig. 1 sollen Skalarprodukte, also Ausdrücke der Form
-V
*=Σ , B± i=l ermittelt werden. Die einzelnen Werte Ai und B^ liegen gespeichert vor, da sie zu definierten Zeitpunkten benötigt werden. Die Zwischensummen, die nach der Auf- summierung jedes neuen Produktes Pi = A • B^ entstehen, werden jeweils zwischengespeichert, wobei die vorher¬ gehenden Zwischensumme überschrieben wird. Die nach dem letzten Produkt gebildete Zwischensumme ist dann gleich¬ zeitig das Endergebnis.
Bei dem Zeitdiagramm in Fig. 2 wird zunächst davon ausge¬ gangen, daß die ersten Produkte bereits verarbeitet sind und die entsprechende Zwischensumme gebildet ist. Der
Zeitpunkt t0 am Ende einer zweiten Taktzeit T2 stellt also einen willkürlich gewählten Zeitpunkt innerhalb der Ver¬ arbeitung der Kette von Produkten dar. Zu diesem Zeit¬ punkt tQ wird der eine Faktor Ai des aktuell zu bildenden Produkts P-, der während dieser Taktzeit T2 aus der
Speicheranordnung 12 ausgelesen wurde, in das Register 16 eingeschrieben,*und zwar durch das ansteigende Signal auf der Leitung, 8 für die erste Taktzeit Tl. Gleichzeitig wird das in der Multiplizieranordnung 20 ge-feildete vorher- gehende Produkt Pi.1 in das ProduktregÜster 22 einge- . schrieben. Die Teilsummenregister 30 und 32 werden an dieser Stelle noch nicht näher betrachtet.
In der folgenden Taktzeit Tl nach dem Zeitpunkt t0 wird der zweite Wert Bi des zu bildenden Produktes aus der Speicher¬ anordnung 12 ausgelesen und über den Datenbus 14 dem Ein¬ gang des Registers 18 zugeführt. Durch das niedrige Signal auf der Steuerleitung 9 während dieser Taktzeit wird der Multiplexer 24 so gesteuert, daß die Verbindung 29 mit den Bits niedrigster Wertigkeit des Produktes P dem Ein¬ gang 25 der Addieranordnung 26 gekoppelt ist, und gleichzeitig wird über den in gleicher Weise gesteuerten Multiplexer 34 der Ausgang 33 des Teilsummenregisters 32 mit dem Eingang 35 der Addieranordnung 26 gekoppelt. Diese bildet während der Taktzeit Tl die Teilsumme SL i.1 und gibt diese gegen Ende der Taktzeit Tl am Ausgang 27 ab.
Am Ende der Taktzeit Tl, nämlich zum Zeitpunkt t.,, wenn das Signal auf der Steuerleitung 8 niedrig und auf der Steuer- leitung 9 hoch wird, wird die so gebildete Hälfte niedrigster Wertigkeit der Teilsumme in das zweite Summen¬ register 32 eingeschrieben, und gleichzeitig wird das über den Ausgang 27a abgegebene Übertragsignal in den Übertrag¬ speicher 28 eingeschrieben. Außerdem wird der zweite Faktor Bj des zu bildenden Produktes in das Register 18 eingeschrieben. Ferner werden die beiden Multiplexer 24 und 34 umgeschaltet, so daß nun der Eingang 25 der Addier¬ anordnung 26 die Bits höchster Wertigkeit des Produktes Pi.1 am Ausgang 23 des Produktregisters 22, dessen Inhalt unverändert geblieben ist, empfängt, und gleichzeitig empfängt der Eingang 35 der Addieranordnung 26 die im ersten Teilsummenreg,i_st«r 3,Q enthaltenen Bits höherer Wertigkeit der vorhergehenden Teilsumme sowie außerdem den am Aufgang 37 abgegebenen Übertrag aus dem Übertrag- Speicher 28, so daß nun der Teil höchster Wertigkeit der neuen Zwischensumme in der Addieranordnung 26 gebildet und am Ausgang 27 abgegeben wird, und gleichzeitig bildet die Multiplizieranordnung 20 das nächste Produkt P,, da nun beide Werte Ai und B1 in den Registern 16 und 18 vorliegen. Außerdem adressiert die Steueranordnung 10 den ersten
Wert Ai+1 für das folgende Produkt Pi+1 und führt diesen Wert über den Bus 14 u.a. dem Register 16 zu.
Am Ende der Taktzeit T2, zum Zeitpunkt t2, wird nun das Steuersignal auf der Leitung 8 hoch, so daß der Wert Ai+1 in das Register 16 eingeschrieben wird, und gleichzeitig wird das vom Multiplizierer 20 am Ausgang 21 abgegebene Produkt Pf in das Produktregister 22 eingeschrieben, und ferner wird der Teil höchster Wertigkeit der vorhergehenden Zwischensumme S1^, in das erste Teilsummenregister 30 eingeschrieben. Damit ist die Verarbeitung des Pro¬ duktes P1.1 abgeschlossen, und das nun im Produktregister 22 enthaltene Produkt Pi kann weiterverarbeitet werden.
Dies geschieht in der zweiten dargestellten Taktphase Tl, in der der Multiplexer 24 wieder umgeschaltet wird und die Bits niedrigster Wertigkeit des Produktes P, am Ausgang 29 des Produktregisters 22 dem Eingang 25 der Addieranord¬ nung 26 zuführt. Gleichzeitig erhält der andere Eingang 35 der Addieranordnung 26 die vorhergehende Teilsumme SL i.1 über den Multiplexer 34 vom Ausgang 33 des zweiten Teil¬ summenregisters 32, und die neue Teilsumme niedrigster Wertigkeit S1, wird am Ausgang 27 der Addieranordnung 26 erzeugt und am Ende der Taktzeit Tl, zum Zeitpunkt t3, in das zweite Teilsummenregister 32 eingeschrieben. Gleich¬ zeitig wird im übrigen der zweite ^Wert Bi+1, der während der Taktze-it Tl ausgelesen wurde, in .das Register 1° einge¬ schrieben.
In der dritten dargestellten Taktzeit T2 wird nun am Ausgang 21 des Multiplizierers 20 das folgende gültige Produkt Pi+1 gebildet, und gleichzeitig werden dem Ein¬ gang 25 der Addieranordnung 26 die Bits höchster Wertig¬ keit aus dem Produktregister 22 und dem Eingang 35 die vorhergehende Teilsumme höchster Wertigkeit S1^.., des ersten Teilsummenregisters 30 sowie das Übertragsignal vom Über- tragspeicher 28 zugeführt, so daß die neue Teilsumme höchster Wertigkeit S^ am Ausgang 27 der Addieranord¬ nung 26 gebildet wird. Diese wird am Ende der dritten dargestellten Taktzeit T2 wieder in das erste Teilsummen¬ register 30 eingeschrieben.
Dieser Vorgang setzt sich zyklisch fort, bis alle Produkte der Kette berechnet und durch Aufakkumulieren in die Teil- Summenregister verarbeitet sind. Wie aus Fig. 2 zu erkennen ist, erfolgt die Verarbeitung dabei nach dem Fließbandprinzip, d.h. während ein Produkt gebildet wird, wird gleichzeitig die vorhergehende Teilsumme gebildet und die Werte des nachfolgenden Produktes zugeführt. Am Anfang, d.h. bei der Bildung des ersten Produktes Plf sind daher einige Verarbeitungsschritte vorab erforderlich.
Diese sind aus Fig. 2 ersichtlich, wenn i = 1 gesetzt wird. Das bedeutet, daß vor dem Zeitpunkt t0 zunächst der eine Wert A1 ausgelesen und zum Zeitpunkt tQ in das
Register eingeschrieben werden muß. Danach wird der zweite Wert B1 ausgelesen und zum Zeitpunkt t1 in das Register 18 eingeschrieben. Danach kann das erste Produkt P1 gebildet werden, das zum Zeitpunkt t2 in das Produktregister 22 eingeschrieben wird. Nun kann das Produkt P1 in der bereits beseht--!e enen Jtfeise verarbeitet werden, wobei während dieser vorhergehenden1 Verarbeitung^schritte dio To.il- , Summenregister 30 und 32 selbstverständlich gelöscht sein müssen, d.h. sie müssen den Wert Null enthalten. Auf diese Weise wird die Summe einer Kette von Produkten gebildet, wobei die volle Genauigkeit ohne Rundungsfehler erhalten bleibt und dennoch nur ein Addierer für die ein¬ fache Wortbreite erforderlich ist.

Claims

PATENTANSPRÜCHE
1. Verfahren zum Bilden der Summe einer Kette von Produkten aus je zwei Zahlen, die nacheinander zugeführt werden, wobei jedes Zwischenergebnis der Summenbildung zwischengespeichert wird, dadurch gekennzeichnet. daß das bei jeder einzelnen Multi¬ plikation entstehende Produkt in zwei Schritten zum Zwischenergebnis addiert wird, indem im ersten Schritt nur die Stellen niedrigster Wertigkeit des Produkts zu den entsprechenden Stellen des Zwischenergebnisses addiert und die dabei entstehende erste Teilsumme zwischengespeichert wird und im zweiten Schritt die restlichen Stellen höherer Wertigkeit des Produkts zu den entsprechenden restlichen Stellen der Zwischensumme und dem Übertrag der ersten Teilsumme addiert und die dabei entstehende zweite Teil- summe zwischengespeichert wird, wobei in jedem Schritt eine andere der unmittelbar anschließend zu multipli¬ zierenden Zahlen zugeführt wird.
2. Anordnung zum Bilden der Summe einer Kette von Pro- dukten aus jeweils einem ersten und einem zweiten Wert, mit einer Speicheranordnung zum Speichern einer Anzahl von Werten mit einer vorgegebenen ersten Anzahl Bits, einer taktgesteuerten Steueranordnung zum Steuern des Einschrei- bens von Werten in Register, einer ersten Registeranord- nung zum Aufnehmen von jeweils zwei miteinander zu multi¬ plizierenden Werten, einer Multiplizieranordnung mit zwei Eingängen, die mit der ersten Registeranordnung verbunden sind, und einem nachgeschalteten Pro'duktregister mit einem Ausgang ür die doppelte erste Anzahl Bits, einer Add.ϊer- anordtaNαng mit zwei Summeπeingängen für- je die erste Anzahl Bits, v.on. denen der eine -mit dem Ausgang des Produkt- regis ers koppelbar ist, und einem nachgeschalteten Su - menregister aus wenigstens zwei Teilsummenregistern für je die erste Anzahl Bits, mit einem Ausgang, der mit dem anderen Eingang der Addieranordnung koppelbar ist, dadurch gekennzeichnet, daß die Speicheranordnung (12) über nur einen Datenbus (14) für die erste Anzahl Bits mit der ersten Registeranordnung (16,18) verbunden ist und daß die Steueranordnung (10) eingerichtet ist, um abwechselnd in einer ersten und einer zweiten Taktzeit zu arbeiten und in der ersten Taktzeit die erste Anzahl Bits niedrigster Wertigkeit am Ausgang des Produktregisters (22) und den
Inhalt des zweiten Teilsummenregisters (32) den Eingängen der Addieranordnung (26) zuzuführen und am Ende dieser Taktzeit einen der ersten Werte (B^ in die Register¬ anordnung (16) und die am Ausgang der Addieranordnung (26) vorhandene neue Teilsumme in das zweite TeilSummenregister (32) einzuschreiben und in der zweiten Taktzeit die erste Anzahl Bits höchster Wertigkeit am Ausgang des Produkt¬ registers (22) und den Inhalt des ersten Teilsummen¬ registers sowie einen zwischengespeicherten Übertrag der Addieranordnung (26) zuzuführen und am Ende dieser Takt¬ zeit einen der zweiten Werte (Ai+1) in die Registeranordnung (16,18) und die am Ausgang der Addieranordnung (26) vor¬ handene .zweite Teilsumme in das erste Teilsummenregister sowie das von der Multiplizieranordnung (20) gebildete Produkt in das Produktregister (22) einzuschreiben.
3. Anordnung nach Anspruch 2, dadurch gekennzeichnet, daß zwischen dem Ausgang des Pro¬ duktregisters (22) und dem einen Summeneingang der Addier- anordnung (26) ein erster Multiplexer (24) und zwischen den Ausgängen der Teilsummenregister (30, 32) und dem anderen Eingang der Addieranordnung (26;) ein zweiter Mul¬ tiplexer (34) geschaltet„ist, und daß die St^uJ?ranordnung (10) eingerichtet, ist, um die Multiplexer zwischen jeder Taktzeit umzuschalten.
PCT/NL1993/000117 1992-06-06 1993-06-04 Verfahren und anordnung zum bilden der summe einer kette von produkten Ceased WO1993025959A1 (de)

Priority Applications (5)

Application Number Priority Date Filing Date Title
KR1019940700362A KR100271074B1 (ko) 1992-06-06 1993-06-04 연쇄곱의 합산 방법 및 장치(Process and configuration for establishing the sum of a chain of products)
DE59309652T DE59309652D1 (de) 1992-06-06 1993-06-04 Verfahren und anordnung zum bilden der summe einer kette von produkten
JP6501341A JPH07501167A (ja) 1992-06-06 1993-06-04 一連の積の和を形成する方法および装置
EP93916269A EP0598112B1 (de) 1992-06-06 1993-06-04 Verfahren und anordnung zum bilden der summe einer kette von produkten
US08/190,068 US5602766A (en) 1992-06-06 1993-06-04 Method of and device for forming the sum of a chain of products

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE4218769A DE4218769A1 (de) 1992-06-06 1992-06-06 Verfahren und Anordnung zum Bilden der Summe einer Kette von Produkten
DEP4218769.9 1992-06-06

Publications (1)

Publication Number Publication Date
WO1993025959A1 true WO1993025959A1 (de) 1993-12-23

Family

ID=6460574

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/NL1993/000117 Ceased WO1993025959A1 (de) 1992-06-06 1993-06-04 Verfahren und anordnung zum bilden der summe einer kette von produkten

Country Status (6)

Country Link
US (1) US5602766A (de)
EP (1) EP0598112B1 (de)
JP (1) JPH07501167A (de)
KR (1) KR100271074B1 (de)
DE (2) DE4218769A1 (de)
WO (1) WO1993025959A1 (de)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2718866A1 (fr) * 1994-04-19 1995-10-20 Sgs Thomson Microelectronics Dispositif de calcul arithmétique et logique et procédé de commande.
EP0829803A3 (de) * 1996-09-13 1998-04-29 Itt Manufacturing Enterprises, Inc. Digitaler Signalprozessor und Verfahren zur Durchführung einer Multiplikation mit einem digitalen Signalprozessor
FR2775368A1 (fr) * 1998-02-26 1999-08-27 Sgs Thomson Microelectronics Coprocesseur d'arithmetique modulaire permettant de realiser des operations non modulaires rapidement

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
AU5706696A (en) * 1995-04-12 1996-10-30 Boltunov, Alexandr Yurievich Method and device for computing product sums
US5784306A (en) * 1996-06-28 1998-07-21 Cirrus Logic, Inc. Parallel multiply accumulate array circuit
US5847981A (en) * 1997-09-04 1998-12-08 Motorola, Inc. Multiply and accumulate circuit
US6484194B1 (en) * 1998-06-17 2002-11-19 Texas Instruments Incorporated Low cost multiplier block with chain capability
US7266580B2 (en) * 2003-05-12 2007-09-04 International Business Machines Corporation Modular binary multiplier for signed and unsigned operands of variable widths

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0173383A1 (de) * 1984-08-14 1986-03-05 Telecommunications Radioelectriques Et Telephoniques T.R.T. Prozessor zur Verarbeitung von Daten verschiedener Darstellungsarten und geeignetes Multipliziergerät für einen solchen Prozessor

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4809212A (en) * 1985-06-19 1989-02-28 Advanced Micro Devices, Inc. High throughput extended-precision multiplier
US4754421A (en) * 1985-09-06 1988-06-28 Texas Instruments Incorporated Multiple precision multiplication device
JPH07113886B2 (ja) * 1987-05-11 1995-12-06 株式会社日立製作所 演算回路

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0173383A1 (de) * 1984-08-14 1986-03-05 Telecommunications Radioelectriques Et Telephoniques T.R.T. Prozessor zur Verarbeitung von Daten verschiedener Darstellungsarten und geeignetes Multipliziergerät für einen solchen Prozessor

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
EDN ELECTRICAL DESIGN NEWS Bd. 26, Nr. 7, 1. April 1981, NEWTON, MASSACHUSETTS US Seiten 153 - 163 W. BUCKLEN ET AL. 'Single-chip digital multipliers form basic DSP building blocks' *
EDN ELECTRICAL DESIGN NEWS Bd. 32, Nr. 12, 11. Juni 1987, NEWTON, MASSACHUSETTS US J. TITUS 'MAC chips' Seiten 114 - 122, 124, 126 *

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2718866A1 (fr) * 1994-04-19 1995-10-20 Sgs Thomson Microelectronics Dispositif de calcul arithmétique et logique et procédé de commande.
EP0678807A1 (de) * 1994-04-19 1995-10-25 STMicroelectronics S.A. Arithmetische und logische Rechnungseinrichtung und Steuerungsverfahren
US5657262A (en) * 1994-04-19 1997-08-12 Sgs-Thomson Microelectronics, S.A. Arithmetic and logic computation device and control method
EP0829803A3 (de) * 1996-09-13 1998-04-29 Itt Manufacturing Enterprises, Inc. Digitaler Signalprozessor und Verfahren zur Durchführung einer Multiplikation mit einem digitalen Signalprozessor
US5898604A (en) * 1996-09-13 1999-04-27 Itt Manufacturing Enterprises, Inc. Digital Signal Processor employing a random-access memory and method for performing multiplication
FR2775368A1 (fr) * 1998-02-26 1999-08-27 Sgs Thomson Microelectronics Coprocesseur d'arithmetique modulaire permettant de realiser des operations non modulaires rapidement
EP0939362A1 (de) * 1998-02-26 1999-09-01 STMicroelectronics S.A. Koprozessor für moduläre Arithmetik mit einer schnellen Ausführung von nicht-modulären Operationen
US6341299B1 (en) 1998-02-26 2002-01-22 Stmicroelectronics S.A. Modular arithmetic coprocessor enabling the performance of non-modular operations at high speed

Also Published As

Publication number Publication date
EP0598112B1 (de) 1999-06-16
JPH07501167A (ja) 1995-02-02
DE59309652D1 (de) 1999-07-22
US5602766A (en) 1997-02-11
KR100271074B1 (ko) 2000-11-01
DE4218769A1 (de) 1993-12-09
EP0598112A1 (de) 1994-05-25

Similar Documents

Publication Publication Date Title
EP0115609B1 (de) Schaltungsanordnung zur Adressierung der Speicher mehrerer datenverarbeitender Einrichtungen in einem Mehrprozesssorsystem
DE2756890C2 (de) Schaltungungsanordnung zur Steuerung der Datenübertragung zwischen einer zentralen Verarbeitungseinheit und einer Mehrzahl peripherer Einheiten
DE1549476B2 (de) Anordnung zur ausfuehrung von divisionen
DE2730328B2 (de) Schaltungsanordnung zur Feststellung des bestübereinstimmenden Datenworts von in einem Datenwort-Speicher gespeicherten Datenworten mit einem Suchwort
DE1549477B1 (de) Einrichtung zur schnellen akkumulation einer anzahl mehr stelliger binaerer operanden
DE2854782C2 (de) Datenverarbeitungssystem und Verfahren zum Ersetzen eines Datenblocks in einem Schnellspeicher
DE3148099C2 (de) Anordnung zum Erkennen einer Digitalfolge
DE2524749C2 (de) Digitale Filteranordnung
DE2150751A1 (de) Digitaler Sinus-Kosinus-Generator
DE3507584C2 (de)
EP0099142B1 (de) Verfahren und Anordnung zum Demodulieren eines frequenzmodulierten Eingangssignals
WO1993025959A1 (de) Verfahren und anordnung zum bilden der summe einer kette von produkten
DE69112434T2 (de) Kurvengenerator.
DE3486073T2 (de) Vektorverarbeitungsgeraet.
DE2451235A1 (de) Schaltungsanordnung fuer ein digitales filter
DE1187402B (de) Anordnung zum parallelen Addieren dreier binaerer Zahlen
DE3535215C2 (de)
DE69230924T2 (de) Multiplizierer-Schaltungen mit seriellem Eingang
DE2214053A1 (de) Verfahren und Vorrichtung zum Steuern einer numerisch gesteuerten Werkzeugmaschine entlang einer Kreisbahn
DE19637369C2 (de) Digitaler Signalprozessor mit Multipliziereinrichtung und -Verfahren
DE2253746A1 (de) Modul-signalprozessrechner
DE1181459B (de) Multiplikationsschaltung fuer elektronische Zifferrechenmaschinen
DE4014767A1 (de) Verfahren zum gewinnen eines elektrischen signals durch korrelation
DE1234055B (de) Anordnung zur Addition oder Subtraktion
DE3609056A1 (de) Zaehlerschaltkreis

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP KR US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE

WWE Wipo information: entry into national phase

Ref document number: 1993916269

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 08190068

Country of ref document: US

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWP Wipo information: published in national office

Ref document number: 1993916269

Country of ref document: EP

WWG Wipo information: grant in national office

Ref document number: 1993916269

Country of ref document: EP