Multiplikation bei Mikrocontrollern

Routinensammlung und Gewusst-wie für Mikrocontroller

Multiplikation bei Mikrocontrollern

Betrachtet wird hier nur die Ganzzahlmultiplikation.

0. Grundlagen

Bei der Ganzzahlmultiplikation gilt folgende Regel der Bitbreiten:

Faktor1 * Faktor2 = Produkt
m bit * n bit = (m+n) bit

Im Gegensatz zur Strichrechnung expandiert also stets die Bitbreite.
Hochsprachen verdecken (=verschenken!) diese innewohnende Eigenschaft!

Eine direkte Verarbeitung von Zweierkomplementzahlen ist unzweckmäßig und deshalb selten implementiert (außer bei neueren Controllern); deshalb vorher in Vorzeichen+Betrag umrechnen!

1. Multiplikation mit [(kleinen) Potenzen von] Zwei

Diese werden durch Linksschieben erledigt. — 1x Linksschieben = Multiplikation mit 2 = Addition mit sich selbst.
Bei neueren Mikrocontrollern ist der Geschwindigkeitsvorteil gegenüber eingebauten Multiplikationsbefehlen bei mehr als einem Bit oftmals dahin!

Vorher ist ggf. ein Byte vorzeichenrichtig „vorn“ anzuhängen. Solange nichts überläuft, braucht ansonsten das Vorzeichen nicht beachtet zu werden, alles bleibt richtig!

µC	Neues höchstwertiges Byte/Word bei Zweierkomplement
8051	mov C,ACC.7 ;a=altes MSB subb a,ACC ;neues MSB
PIC	clrf R ;neues MSB btfsc R,7 ;R=altes MSB decf R,f ;neues MSB (0FFh)
ATtiny ATmega	add R,R ;R=altes MSB (wird zerstört) sbc R,R ;neues MSB (0 oder 0FFh)
C166	movbs R₁₆,R₈ ;von 8 auf 16 Bits erweitern
C166	bmov C,R₁₆.15 ;altes HI-Word MSB nach PSW.1 subc R₁₆,R₁₆ ;neues HI-Word (0 oder 0FFFFh)

R bezeichnet das jeweilige (MSB- oder NSB-) Register

An der niederwertigsten Bitposition ist eine Null einzuschieben, bei den höherwertigen ist das Übertragsbit einzuschieben. Anstelle von Schiebebefehlen eignet sich auch der Additionsbefehl. Wenn auch nur, um Verwirrung beim blutjungen Kodeleser zu stiften.

µC	niedrigstes Byte	höhere Bytes
8051	clr C rlc a	rlc a
8051	add a,ACC	addc a,ACC
PIC	bcf STATUS,C rlf R,f	rlf R,f
ATtiny ATmega	lsl R	rol R
ATtiny ATmega	add R,R	adc R,R
C166	add R,R	addc R,R
C166	shl R,#1	addc R,R

R bezeichnet das jeweilige Register

Bei Potenzen von Zwei müssen die o.g. Befehle in einer Schleife ausgeführt werden.

Beachte: Bei Überlauf kommt schlichtweg eine falsche Zahl heraus. Bei Zweierkomplement ist auch das Vorzeichen Glückssache.

2. Multiplikation mit [Potenzen von] 256 (=2⁸!)

Die Lösung dazu ist derartig trivial, dass sie oft nicht für voll genommen wird: Es wird byteweise „uminterpretiert“, bei gleich bleibender Bitbreite muss hinten ein Null-Byte hinzugesetzt (oder hinzugedacht) werden.

3. Multiplikation (oder auch Division) mit Wertetabelle

Bei hinreichend kleinem Umfang der infrage kommenden Faktoren (Faustregel: £256) kann eine sog. Look-Up-Table („Schlag-Nach-Tabelle“) Verwendung finden. Der zweite Faktor ist zweckdienlich eine Konstante; somit ist die Tabelle eindimensional. Der Speicherverbrauch: Alle denkbaren Faktoren mal Byte-Breite des Ergebnisses.

Wegen der Verfügbarkeit eingebauter Multiplikationsbefehle und der akzeptablen Geschwindigkeit selbstgeschriebener Routinen kommt die Tabelle für Mikrocontroller so gut wie nie in Betracht!

Für höhere Funktionen, wie Sinus-, insbesondere steil anwachsende Funktionen, wie Quadrat-, Potenz- und Exponentialfunktion, sind Wertetabellen das Mittel der Wahl.

Quadrate lassen sich auch per Multiplikation ermitteln, jedoch sind Wertetabellen für Quadrate oft klein genug.

Hinweis: Lassen Sie sich Tabellen aller Art nach Möglichkeit vom Assembler mittels Wiederholungsanweisungen berechnen! Konstante Tabellen gehören ins Kodesegment.

4. Multiplikation mit eingebautem Multiplikationsbefehl

Dieser Fall erfordert ggf. das Umwandeln einer Zweierkomplement-Zahl in eine Vorzeichen-Betrags-Darstellung.
Voraussetzung für die Anwendbarkeit des eingebauten Befehls ist seine ausreichende Bitbreite:

µC	Verfügbarer Multiplikationsbefehl	Operation	Bitbreiten, Vorzeichen
8051	mul ab	a:b = a * b	8*8=16 vorzeichenlos
PIC16	nicht vorhanden
PIC17	mullw k	PH:PL = w * k	8*8=16 vorzeichenlos
PIC17	mulwf f	PH:PL = w * f	8*8=16 vorzeichenlos
ATtiny	nicht vorhanden
ATmega	mul Rd,Rr	R1:R0 = Rd * Rr	8*8=16 vorzeichenlos
	muls Rd,Rr		8*8=16 Zweierkomplement
	mulsu Rd,Rr		8*8=16 Zweierkomplement (Rd) und vorzeichenlos (Rr)
	Weiterhin stehen diese 3 Typen mit anschließendem Linksschieben (*2, `fmul, fmuls, fmulsu`) zur Verfügung
C166	mulu R1,R2	MD = MDH:MDL= R1 * R2	16*16=32 vorzeichenlos
C166	mul R1,R2	MD = MDH:MDL= R1 * R2	16*16=32 Zweierkomplement

5. Multiplikation breiterer Zahlen mit eingebautem Multiplikationsbefehl

Dieser Fall der Kaskadierung ist bei Mikrocontrollern mit Multiplikationsbefehl dringend anzuraten! Dabei können beide Faktoren beliebig lang sein.

5.1 Bitbreiten-Verdopplung

Beispiel (allgemein gehalten, in C-ähnlicher Syntax) für 32-bit-Produkt aus 2 16-bit-Faktoren eines 8-bit-Mikrocontrollers:

Faktor1 * Faktor2 = Produkt
16 bit * 16 bit = 32 bit
a:b * c:d = ((a*c * 256) + a*d + b*c)* 256 + b*d
p:q=a*c r:s=b*d X:Y=a*d r+=Y q+=X+C p+=C X:Y=b*c r+=Y q+=X+C p+=C
a:b, c:d = Faktoren, p:q:r:s = Produkt, X:Y=Zwischen-Produkt, C=Übertrags-Flag

Faktor1 * Faktor2 = Produkt
16 bit * 16 bit = 32 bit
a:b * c:d = ((ac 256) + ad + bc)* 256 + b*d
p:q=ac r:s=bd X:Y=ad r+=Y q+=X+C p+=C X:Y=bc r+=Y q+=X+C p+=C

Der angegebene Pseudokode funktioniert auf 16-bit-Mikrocontrollern und PCs ebenso für 64-bit-Produkte.

5.2 Bitbreiten-Verdreifachung

24-bit-Register (48-bit-Ergebnisse) sind in Hochsprachen unüblich, jedoch in Assembler vorteilhaft anwendbar.

Faktor1 * Faktor2 = Produkt
24 bit * 24 bit = 48 bit
a:b:c * d:e:f = (((((a*d * 256) + a*e + b*d)* 256) + a*f + b*e + c*d)*256 + b*f + c*e)*256 + c*f
p:q=a*d r:s=b*e t:u=c*f X:Y=a*e r+=Y q+=X+C p+=C X:Y=b*d r+=Y q+=X+C p+=C X:Y=a*f s+=Y r+=X+C q+=C p+=C X:Y=c*d s+=Y r+=X+C q+=C p+=C X:Y=b*f t+=Y s+=X+C r+=C q+=C p+=C X:Y=c*e t+=Y s+=X+C r+=C q+=C p+=C
a:b:c, d:e:f = Faktoren, p:q:r:s:t:u = Produkt, X:Y=Zwischen-Produkt, C=Übertrags-Flag

Faktor1 * Faktor2 = Produkt
24 bit * 24 bit = 48 bit
a:b:c * d:e:f = (((((ad 256) + ae + bd)* 256) + af + be + cd)256 + bf + ce)256 + cf
p:q=ad r:s=be t:u=cf X:Y=ae r+=Y q+=X+C p+=C X:Y=bd r+=Y q+=X+C p+=C X:Y=af s+=Y r+=X+C q+=C p+=C X:Y=cd s+=Y r+=X+C q+=C p+=C X:Y=bf t+=Y s+=X+C r+=C q+=C p+=C X:Y=c*e t+=Y s+=X+C r+=C q+=C p+=C

Um das Durchreichen des Übertragsflags bei der Addition kommt man nicht sinnvoll herum. Insgesamt werden 9 (3x3) Multiplikationen ausgeführt.

5.2 Bitbreiten-Vervierfachung

Bei den nun folgenden 16 Multiplikationsbefehlen ist eine Ausführung in Schleifen durchaus naheliegend. Für maximale Geschwindigkeit dennoch hier die „lineare“ Form:

Faktor1 * Faktor2 = Produkt
32 bit * 32 bit = 64 bit
a:b:c:d * e:f:g:h = p:q:r:s:t:u:v:w
p:q=a*e r:s=b*f t:u=c*g v:w=d*h X:Y=c*h v+=Y u+=X+C Z=C X:Y=d*g v+=Y u+=X+C Z+=C t+=Z Z=C X:Y=b*h u+=Y t+=X+C Z+=C X:Y=d*f u+=Y t+=X+C Z+=C s+=Z Z=C X:Y=a*h t+=Y s+=X+C Z+=C X:Y=b*g t+=Y s+=X+C Z+=C X:Y=c*f t+=Y s+=X+C Z+=C X:Y=d*e t+=Y s+=X+C Z+=C r+=Z Z=C X:Y=a*g s+=Y r+=X+C Z+=C X:Y=c*e s+=Y r+=X+C Z+=C q+=Z Z=C X:Y=a*f r+=Y q+=X+C Z+=C X:Y=b*e r+=Y q+=X+C Z+=C p+=Z

Faktor1 * Faktor2 = Produkt
32 bit * 32 bit = 64 bit
a:b:c:d * e:f:g:h = p:q:r:s:t:u:v:w
p:q=ae r:s=bf t:u=cg v:w=dh X:Y=ch v+=Y u+=X+C Z=C X:Y=dg v+=Y u+=X+C Z+=C t+=Z Z=C X:Y=bh u+=Y t+=X+C Z+=C X:Y=df u+=Y t+=X+C Z+=C s+=Z Z=C X:Y=ah t+=Y s+=X+C Z+=C X:Y=bg t+=Y s+=X+C Z+=C X:Y=cf t+=Y s+=X+C Z+=C X:Y=de t+=Y s+=X+C Z+=C r+=Z Z=C X:Y=ag s+=Y r+=X+C Z+=C X:Y=ce s+=Y r+=X+C Z+=C q+=Z Z=C X:Y=af r+=Y q+=X+C Z+=C X:Y=be r+=Y q+=X+C Z+=C p+=Z

a:b:c:d, e:f:g:h = Faktoren, p:q:r:s:t:u:v:w = Produkt, X:Y=Zwischen-Produkt, C=Übertrags-Flag, Z=Zwischenregister

Das Zwischenregister Z erspart lange Carry-Propagates und ist insbesondere bei Mikrocontrollern mit wenigen Registern (bspw. 8051) vorteilhaft.

Beim ATmega8 ist das Zwischenregister wenig von Vorteil, man kann es partiell einsetzen, bspw. nur in der Spalte für r, das ergäbe dann:

p:q=a*e r:s=b*f t:u=c*g v:w=d*h X:Y=c*h v+=Y u+=X+C t+=C s+=C Z=C X:Y=d*g v+=Y u+=X+C t+=C s+=C Z+=C X:Y=b*h u+=Y t+=X+C s+=C Z+=C X:Y=d*f u+=Y t+=X+C s+=C Z+=C X:Y=a*h t+=Y s+=X+C Z+=C X:Y=b*g t+=Y s+=X+C Z+=C X:Y=c*f t+=Y s+=X+C Z+=C X:Y=d*e t+=Y s+=X+C Z+=C r+=Z q+=C p+=C X:Y=a*g s+=Y r+=X+C q+=C p+=C X:Y=c*e s+=Y r+=X+C q+=C p+=C X:Y=a*f r+=Y q+=X+C p+=C X:Y=b*e r+=Y q+=X+C p+=C

Das Zwischenregister spart hierbei 12 Takte Ausführungszeit (von 96 Takten).

6. Multiplikation vorzeichenbehafteter Zahlen

Der übliche Weg ist es, die vorzeichenbehafteten Operanden vorzeichenlos zu machen und das Ergebnis bei Bedarf wieder zu negieren. Aber es geht auch anders, je nach Fall:

Nutzung eines eingebauten vorzeichenbehafteten Multiplikationsbefehls
bei nur einem vzb. Faktor Sonderfall anwenden: a*b = (a+80h)*b - b*80h, (siehe Tabelle)
hier ist die Unterscheidung zwischen Multiplikand und Multiplikator wichtig, d.h. die Multiplikationsroutine ist nicht kommutativ!
Es lohnt sich aber nur bei konstanten Faktoren.
Trick (für "vzb lang * vzb lang") siehe unten.
Lange Faktoren lassen sich nicht mit vzb. Einzeloperationen verarbeiten!

µC vzb * vzl vzb * vzb vzb lang * vzb lang
8051
add a,#80h mov B,#k mul ab xch a,B sub a,#k*128 xch a,B subb a,#k/2
PIC16
PIC17
addlw 80h mullw k*2 movfw PH sublw k movwf PH
ATtiny
ATmega
mulsu Rd,Rr
muls Rd,Rr
siehe unten
C166
add R1,#8000h mov R2,#k mulu R1,R2 sub MPL,#k*8000h sbc MPH,#k/2
mul R1,R2

µC	vzb * vzl	vzb * vzb	vzb lang * vzb lang
8051	add a,#80h mov B,#k mul ab xch a,B sub a,#k*128 xch a,B subb a,#k/2
PIC16
PIC17	addlw 80h mullw k*2 movfw PH sublw k movwf PH
ATtiny
ATmega	mulsu Rd,Rr	muls Rd,Rr	siehe unten
C166	add R1,#8000h mov R2,#k mulu R1,R2 sub MPL,#k*8000h sbc MPH,#k/2	mul R1,R2

Trick: Getesteter Quelltext für ATmega für Multiplikation "vzb lang * vzb lang"

;Clevere vzb. Multiplikationsroutine:
;PE: r17:r16 = vzb. Faktor 1
;    r19:r18 = vzb. Faktor 2
;    YH = 0
;PA: r5:r4:r3:r2 = vzb. Produkt (30 bit + Vorzeichen)
;VR: r0-r5, r16-r17
;(a+8000h)(b+8000h) = a*b + a*8000h + b*8000h + 40000000h
;		    = a*b + (a+8000h+b)*8000h
;also:
;a*b = (a+8000h)*(b+8000h) - (a+8000h+b)*8000h
imul16x16:	;(getestet)
;Faktor 1 positiv machen
	subi	r17,0x80
;Faktor 2 positiv machen
	subi	r19,0x80
;vzl. multiplizieren (a+8000h)(b+8000h), evtl. Unterprogramm "mul16x16"
	mul	r16,r18
	movw	r3:r2,r1:r0
	mul	r17,r19
	movw	r5:r4,r1:r0
	mul	r17,r18
	add	r3,r0
	adc	r4,r1
	adc	r5,YH
	mul	r16,r19
	add	r3,r0
	adc	r4,r1
	adc	r5,YH
;Ergebnis korrigieren
	clr	r0
	subi	r19,0x80	;"b" zurückwandeln
	add	r16,r18
	adc	r17,r19		;"a+8000h+b"
	sbrc	r19,7		;Wenn "b" positiv,...
	 clc
	ror	r17		;...Überlaufbit einschieben
	ror	r16
	ror	r0		;()*8000h
	sub	r3,r0
	sbc	r4,r16
	sbc	r5,r17		;subtrahieren
;fertig
	ret

Quadrieren ist etwas leichter, u.a. weil das Ergebnis stets positiv ist:

;PE: r17:r16 = vzb. Zahl
;PA: r5:r4:r3:r2 = Quadrat (30 bit)
;VR: r0-r5, r17,r18
;(a+8000h)² = a² + a*10000h + 40000000h
;also:
;a² = (a+8000h)² - a*10000h - 40000000h
iQuadrat16x16:
;man kommt um Betragsbildung doch herum!
	subi	r17,0x80
	ldi	r18,(0x80-0x40)/2
;Quadrieren der vzl. Zahl, evtl. Unterprogramm (für vzl. mit r18=0!)
	mul	r16,r16
	movw	r3:r2,r1:r0
	mul	r17,r17
	movw	r5:r4,r1:r0
	fmul	r17,r16
	rol	r18		;CY retten
	add	r3,r0
	adc	r4,r1
	adc	r5,r18
;Korrektur
	sub	r4,r16
	sbc	r5,r17
;fertig
	ret

7. Multiplikation mit selbstgeschriebener Routine

Hierbei sind beliebige Bitbreiten realisierbar. Die einfachste Routine multipliziert 8 bit * 8 bit = 16 bit. Selbstgeschriebene Routinen kommen nur für PIC16 und ATtiny, AT90Sxxxx in Betracht!

Die binäre Multiplikation erfolgt genauso wie die schriftliche Multiplikation; durch (bedingte) Addition des (0-oder 1fachen des) linken Faktors und Fortfahren zur nächsten Ziffer von links nach rechts.

Zweierkomplement-Zahlen müssen vorher nichtnegativ gemacht werden; das Vorzeichen des Quotienten ergibt sich aus der XOR-Verknüpfung der höchstwertigen Bits der Faktoren.

Baustelle!

Geplant sind downloadbare Makros für o. g. Mikrocontroller für alle Multiplikationen mit 8-bit- und 16-bit-Faktoren.

8051 PIC AVR C166
n.v. mult.a16
(universelles Makro für alle Bitbreiten) n.v. -

8051	PIC	AVR	C166
n.v.	mult.a16 (universelles Makro für alle Bitbreiten)	n.v.	-

Zur Anwendung kommt die Multiplikation zur Skalierung von Messwerten und ähnlicher Aufbereitung von Zahlen.

haftmann#software, 4.8.2004