Path: Home => AVR-Überblick => Binäre Berechnungen => Hardware Multiplikation
AT90S8515

Binäre Hardware Multiplikation in AVR Assembler


Alle ATmega, AT90CAN and AT90PWM haben einen Multiplikator an Bord, der 8- mal 8-Bit-Multiplikationen in nur zwei Taktzyklen durchführt. Wenn also Multiplikationen durchgeführt werden müssen und man sicher ist, dass die Software niemals in einem AT90S- oder ATtiny-Prozessor laufen werden muss, sollte man diese schnelle Hardware-Möglichkeit nutzen. Diese Seite zeigt, wie man das macht.
Es gibt hier folgende Abteilungen:
  1. 8-mit-8-Bit-Zahlen
  2. 16-mit-8-Bit-Zahlen
  3. 16-mit-16-Bit-Zahlen
  4. 16-mit-24-Bit-Zahlen

Hardware Multiplikation von 8-mal-8-Bit Binärzahlen

Register 8-mal-8 Diese Aufgabe ist einfach und direkt. Wenn die zwei Binärzahlen in den Registern R16 und R17 stehen, dann muss man nur folgende Instruktion eingeben:

mul R16,R17

Weil das Ergebnis der Multiplikation bis zu 16 Bit lange Zahlen ergibt, ist das Ergebnis in den Registern R1 (höherwertiges Byte) und R0 (niedrigerwertiges Byte) untergebracht. Das war es auch schon.

Programm 8-mal-8 Das Programm demonstriert die Simulation im Studio. Es multipliziert dezimal 250 (hex FA) mit dezimal 100 (hex 64) in den Registern R16 und R17.
8 mal 8 Ergebnis Die Register R0 (LSB) und R1 (MSB) enthalten das Ergebnis hex 61A8 oder dezimal 25,000.
8 mal 8 Zyklen Und: ja, die Multiplikation braucht bloß zwei Zyklen, oder 2 Mikrosekunden bei einem Takt von einem MHz.

Zum Seitenanfang

Hardware Multiplikation von 16- mit 8-Bit-Zahl

Sind größere Zahlen zu multiplizieren? Die Hardware ist auf 8 Bit beschränkt, also müssen wir ersatzweise einige geniale Ideen anwenden. Das ist an diesem Beispiel 16 mal 8 gezeigt. Verstehen des Konzepts hilft bei der Anwendung der Methode und es ist ein leichtes, das später auf die 32- mit 64-Bit-Multiplikation zu übertragen.

Register 16-mal-8 Zuerst die Mathematik: eine 16-Bit-Zahl lässt sich in zwei 8-Bit-Zahlen auftrennen, wobei die höherwertige der beiden Zahlen mit dezimal 256 oder hex 100 mal genommen wird. Für die, die eine Erinnerung brauchen: die Dezimalzahl 1234 kann man auch als die Summe aus (12*100) und 34 betrachten, oder auch als die Summe aus (1*1000), (2*100), (2*10) und 4. Die 16-Bit-Binärzahl m1 ist also gleich 256*m1M plus m1L, wobei m1M das MSB und m1L das LSB ist. Multiplikation dieser Zahl mit der 8-Bit-Zahl m2 ist also mathematisch ausgedrückt:

m1 * m2 = (256*m1M + m1L) * m2 = 256*m1M*m2 + m1L*m2

Wir müssen also lediglich zwei Multiplikationen durchführen und die Ergebnisse addieren. Zwei Multiplikationen? Es sind doch drei * zu sehen! Für die Multiplikation mit 256 braucht man in der Binärwelt keinen Hardware-Multiplikator, weil es ausreicht, die Zahl einfach um ein Byte nach links zu rücken. Genauso wie in der Dezimalwelt eine Multiplikation mit 10 einfach ein Linksrücken um eine Stelle ist und die frei werdende leere Ziffer mit Null gefüllt wird.

Beginnen wir mit einem praktischen Beispiel. Zuerst brauchen wir einige Register, um
  1. die Zahlen m1 und m2 zu laden,
  2. für das Ergebnis Raum zu haben, das bis zu 24 Bit lang werden kann.

;
; Testet Hardware Multiplikation 16-mit-8-Bit
;
; Register Definitionen:
;
.def Res1 = R2 ; Byte 1 des Ergebnisses
.def Res2 = R3 ; Byte 2 des Ergebnisses
.def Res3 = R4 ; Byte 3 des Ergebnisses
.def m1L = R16 ; LSB der Zahl m1
.def m1M = R17 ; MSB der Zahl m1
.def m2 = R18 ; die Zahl m2

Zuerst werden die Zahlen in die Register geladen:

;
; Lade Register
;
.equ m1 = 10000
;
	ldi m1M,HIGH(m1) ; obere 8 Bits von m1 in m1M
	ldi m1L,LOW(m1) ; niedrigere 8 Bits von m1 in m1L
	ldi m2,250 ; 8-Bit Konstante in m2

16 mal 8 laden Die beiden Zahlen sind in R17:R16 (dez 10000 = hex 2710) und R18 (dez 250 = hex FA) geladen.

Dann multiplizieren wir zuerst das niedrigerwertige Byte:

;
; Multiplikation
;
	mul m1L,m2 ; Multipliziere LSB
	mov Res1,R0 ; kopiere Ergebnis in Ergebnisregister
	mov Res2,R1

16 mal 8 LSB Die LSB-Multiplikation von hex 27 mit hex FA ergibt hex 0F0A, das in die Register R0 (LSB, hex A0) und R1 (MSB, hex 0F) geschrieben wurde. Das Ergebnis wird in die beiden untersten Bytes der Ergebnisregister, R3:R2, kopiert.

Nun folgt die Multiplikation des MSB mit m2:

	mul m1M,m2 ; Multiplizere MSB

16 mal 8 MSB Die Multiplikation des MSB von m1, hex 10, mit m2, hex FA, ergibt hex 2616 in R1:R0.

Nun werden zwei Schritte auf einmal gemacht: die Multiplikation mit 256 und die Addition des Ergebnisses zum bisherigen Ergebnis. Das wird erledigt durch Addition von R1:R0 zu Res3:Res2 anstelle von Res2:Res1. R1 wird zunächst schlicht nach Res3 kopiert. Dann wird R0 zu Res2 addiert. Falls dabei das Übertragsflag Carry nach der Addition gesetzt ist, muss noch das nächsthöre Byte Res3 um Eins erhöht werden.

	mov Res3,R1 ; Kopiere MSB des Ergebnisses zum Ergebnis-Byte 3
	add Res2,R0 ; Addiere LSB des Ergebnisses zum Ergebnis-Byte 2
	brcc NoInc ; Wenn Carry nicht gesetzt, springe
	inc Res3 ; erhoehe Ergebnis-Byte 3
NoInc:

16 mal 8 Ergebnis Das Ergebnis in R4:R3:R2 ist hex 2625A9, was dezimal 2500000 entspricht (wie jeder sofort weiß), und das ist korrekt.

16 mal 8 Zyklen Der Zykluszähler zeigt nach der Multiplikation auf 10, bei 1 MHz Takt sind gerade mal 10 Mikrosekunden vergangen. Sehr viel schneller als die Software-Multiplikation!


Zum Seitenanfang

Hardware Multiplikation einer 16- mit einer 16-bit-Binärzahl

Register 16-mit-16 Nun, da wir das Prinzip verstanden haben, sollte es einfach sein die 16-mal-16-Multiplikation zu erledigen. Das Ergebnis benötigt jetzt vier Bytes (Res4:Res3:Res2:Res1, untergebracht in R5:R4:R3:R2). Die Formel lautet:

m1 * m2 = (256*m1M + m1L) * (256*m2M + m2L)
= 65536*m1M*m2M + 256*m1M*m2L + 256*m1L*m2M + m1L*m2L

Offensichtlich sind jetzt vier Multiplikationen zu erledigen. Wir beginnen mit den beiden einfachsten, der ersten und der letzten: ihre Ergebnisse können einfach in die Ergebnisregister kopiert werden. Die beiden mittleren Multiplikationen in der Formel müssen zu den beiden mittleren Ergebnisregistern addiert werden. Mögliche Überläufe müssen in das Ergebnisregister Res4 übertragen werden, wofür hier ein einfacher Trick angewendet wird, der einfach zu verstehen sein dürfte. Die Software:

;
; Test Hardware Multiplikation 16 mal 16
;
; Definiere Register
;
.def Res1 = R2
.def Res2 = R3
.def Res3 = R4
.def Res4 = R5
.def m1L = R16
.def m1M = R17
.def m2L = R18
.def m2M = R19
.def tmp = R20
;
; Lade Startwerte
;
.equ m1 = 10000
.equ m2 = 25000
;
	ldi m1M,HIGH(m1)
	ldi m1L,LOW(m1)
	ldi m2M,HIGH(m2)
	ldi m2L,LOW(m2)
;
; Multipliziere
;
	clr R20 ; leer, fuer Uebertraege
	mul m1M,m2M ; Multipliziere MSBs
	mov Res3,R0 ; Kopie in obere Ergebnisregister
	mov Res4,R1
	mul m1L,m2L ; Multipliziere LSBs
	mov Res1,R0 ; Kopie in untere Ergebnisregister
	mov Res2,R1
	mul m1M,m2L ; Multipliziere 1M mit 2L
	add Res2,R0 ; Addiere zum Ergebnis
	adc Res3,R1
	adc Res4,tmp ; Addiere Uebertrag
	mul m1L,m2M ; Multipliziere 1L mit 2M
	add Res2,R0 ; Addiere zum Ergebnis
	adc Res3,R1
	adc Res4,tmp
;
; Multiplikation fertig
;

Die Simulation im Studio zeigt die folgenden Schritte. 16 mit 16 laden Das Laden der beiden Konstanten 10000 (hex 2710) und 25000 (hex 61A8) in die Register im oberen Registerraum ...
16 mit 16 Mult1 Multiplikation der beiden MSBs (hex 27 und 61) und kopieren des Ergebnisses in R1:R0 in die beiden oberen Ergebnisregister R5:R4 (Multiplikation mit 65536 eingeschlossen) ...
16 mit 16 Mult2 Multiplikation der beiden LSBs (hex 10 und A8) und kopieren des Ergebnisses in R1:R0 in die beiden niedrigeren Ergebnisregister R3:R2 ...
16 mit 16 Mult3 Multiplikation des MSB von m1 mit dem LSB von m2, und Addition des Ergebnisses in R1:R0 zu den beiden mittleren Ergebnisregistern, kein Übertrag ist erfolgt ...
16 mit 16 Mult4 Multiplikation des LSB von m1 mit dem MSB von m2, sowie Addition des Ergebnisses in R1:R0 mit den beiden mittleren Ergebnisbytes, kein Übertrag. Das Ergebnis ist hex 0EE6B280, was dezimal 250000000 ist und offenbar korrekt ...
16 mit 16 Zyklen Die Multiplikation hat 19 Taktzyklen gebraucht, das ist sehr viel schneller als die Software-Multiplikation. Ein weiterer Vorteil: die benötigte Zeit ist IMMER genau 19 Taktzyklen lang, nicht abhängig von den Zahlenwerten (wie es bei der Software-Multiplikation der Fall ist) und vom Auftreten von Überläufen (deshalb der Trick mit der Addition von Null mit Carry). Darauf kann man sich verlassen ...


Zum Seitenanfang

4. Hardware Multiplikation einer 16- mit einer 24-Bit-Binärzahl

Register 16-mit-24 Die Multiplikation einer 16-Bit-Binärzahl "a" mit einer 24-Bit-Binärzahl "b" führt im Ergebnis zu einem maximal 40 Bit breiten Ergebnis. Das Multiplizier-Schema erfordert sechs 8-mit-8-Bit-Multiplikationen und das Addieren der Ergebnisse an der richtigen Position zum Gesamtergebnis. Der Assembler-Code dafür:

; Hardware Multiplikation 16 mit 24 Bit
.include "m8def.inc"
;
; Register Definitionen
.def a1 = R2 ; definiere 16-bit Register
.def a2 = R3
.def b1 = R4 ; definiere 24-bit Register
.def b2 = R5
.def b3 = R6
.def e1 = R7 ; definiere 40-bit Ergebnisregister
.def e2 = R8
.def e3 = R9
.def e4 = R10
.def e5 = R11
.def c0 = R12 ; Hilfsregister fuer Additionen
.def rl = R16 ; Laderegister
;
; Load constants
.equ a = 10000 ; Multiplikator a, hex 2710
.equ b = 1000000 ; Multiplikator b, hex 0F4240
	ldi rl,BYTE1(a) ; lade a
	mov a1,rl
	ldi rl,BYTE2(a)
	mov a2,rl
	ldi rl,BYTE1(b) ; lade b
	mov b1,rl
	ldi rl,BYTE2(b)
	mov b2,rl
	ldi rl,BYTE3(b)
	mov b3,rl
;
; Loesche Registers
	clr e1 ; Loesche Ergebnisregister
	clr e2
	clr e3
	clr e4
	clr e5
	clr c0 ; loesche Hilfsregister
;
; Multipliziere
	mul a2,b3 ; Term 1
	add e4,R0 ; addiere zum Ergebnis
	adc e5,R1
	mul a2,b2 ; Term 2
	add e3,R0
	adc e4,R1
	adc e5,c0 ; (addiere moeglichen Ueberlauf)
	mul a2,b1 ; Term 3
	add e2,R0
	adc e3,R1
	adc e4,c0
	adc e5,c0
	mul a1,b3 ; Term 4
	add e3,R0
	adc e4,R1
	adc e5,c0
	mul a1,b2 ; Term 5
	add e2,R0
	adc e3,R1
	adc e4,c0
	adc e5,c0
	mul a1,b1 ; Term 6
	add e1,R0
	adc e2,R1
	adc e3,c0
	adc e4,c0
	adc e5,c0
;
; fertig.
	nop
; Ergebnis sollte sein hex 02540BE400

Die vollständige Abarbeitung braucht

Zum Seitenanfang

©2008 by http://www.avr-asm-tutorial.net