Begrenzung und Sättigung bei Mikrocontrollern

Es geht hierbei um die Absicherung vor Überlaufeffekten. Gerade in der Regelungstechnik lassen sich nicht immer Übersteuerungen vermeiden, dann ist Begrenzung und Sättigung nützlich.

Bei der Sättigungsarithmetik von Zweierkomplementzahlen gibt es folgende Fälle zu unterscheiden:

Begrenzung⚓

Hierbei geht es um die Einschränkung eines Wertebereiches einer Zahl, unabhängig von ihrer Herkunft, also Punkt- und Strichrechnung.
Beispielsweise: if (i>10) i=10;

Begrenzung ist in Hochsprachen sehr einfach formulierbar. Siehe Beispiel.

Eine Begrenzung ist auch zweckmäßig bei Bitbreiten-Verringerung; der Übergang zu „Sättigung“ ist in diesem Fall fließend.

Makro-Sammlung (zum Rauskopieren):

PIC	AVR ATmega		8051
1 Byte in W	1-Byte-Operanden	2-Byte-Operanden	1 Byte in A
signed X = Maximum aus X und U (untere Grenze) vzb. `if (x<u) x=u;`
Vermeiden!	ZeilennummernUmbruch .macro maxs1 ;X,U cp @0,@1 brge pc+2 mov @0,@1 .endm .macro maxs1k ;X,U cpi @0,@1 brge pc+2 ldi @0,@1 .endm	.macro maxs2 ;XH,XL, UH,UL cp @1,@3 cpc @0,@2 brge pc+2 movw @0:@1,@2:@3 .endm .macro maxs2k ;XH,XL, U cpi @1,LOW(@2) mov temp,HIGH(@2) cpc @0,temp brge pc+3 ldiw @0,@1, @2 .endm	maxs1 macro RA,RB local e mov a,RA clr c subb a,RB swap a rr a xrl a,PSW jnb ACC.2,e mov a,RB mov RA,a e: endm
signed X = Minimum aus X und O (obere Grenze) vzb. `if (x>=o) x=o;`
Vermeiden!	.macro mins1 ;X,U cp @0,@1 brlt pc+2 mov @0,@1 .endm .macro mins1k ;X,U cpi @0,@1 brlt pc+2 ldi @0,@1 .endm	.macro mins2 ;XH,XL, UH,UL cp @1,@3 cpc @0,@2 brlt pc+2 movw @0:@1,@2:@3 .endm .macro mins2k ;XH,XL, U cpi @1,LOW(@2) mov temp,HIGH(@2) cpc @0,temp brlt pc+3 ldiw @0,@1, @2 .endm	mins1 macro RA,RB local e mov a,RB clr c subb a,RA swap a rr a xrl a,PSW jb ACC.2,e mov a,RB mov RA,a e: endm
signed X = Eingrenzung von X zwischen U und O vzb. `if (x<u) x=u; if (x>=o) x=o;`
Vermeiden!	.macro lims1 ;X,U,O maxs1 @0,@1 mins1 @0,@2 .endm .macro lims1k ;X,U,O maxs1k @0,@1 mins1k @0,@2 .endm	.macro lims2 ;XH,XL, UH,UL, OH,OL maxs2 @0,@1, @2,@3 mins2 @0,@1, @4,@5 .endm .macro lims2k ;XH,XL, U, O maxs2k @0,@1, @2 mins2k @0,@1, @3 .endm	lims1 macro x,u,o maxs1 x,u mins1 x,o endm
unsigned X = Maximum aus X und U (untere Grenze) vzl. `if (x<u) x=u;`
	.macro maxu1 ;X,U cp @0,@1 brsh pc+2 mov @0,@1 .endm .macro maxu1k ;X,U cpi @0,@1 brsh pc+2 ldi @0,@1 .endm	.macro maxu2 ;XH,XL, UH,UL cp @1,@3 cpc @0,@2 brsh pc+2 movw @0:@1,@2:@3 .endm .macro maxu2k ;XH,XL, U cpi @1,LOW(@2) mov temp,HIGH(@2) cpc @0,temp brsh pc+3 ldiw @0,@1, @2 .endm	maxu1 macro RB ;X ist in A cjne a,RB,$+3 jnc $+4 mov a,RB endm
unsigned X = Minimum aus X und O (obere Grenze) vzl. `if (x>=o) x=o;`
	.macro minu1 ;X,U cp @0,@1 brlo pc+2 mov @0,@1 .endm .macro minu1k ;X,U cpi @0,@1 brlo pc+2 ldi @0,@1 .endm	.macro minu2 ;XH,XL, UH,UL cp @1,@3 cpc @0,@2 brlo pc+2 movw @0:@1,@2:@3 .endm .macro minu2k ;XH,XL, U cpi @1,LOW(@2) mov temp,HIGH(@2) cpc @0,temp brlo pc+3 ldiw @0,@1, @2 .endm	minu1 macro RB ;X ist in A cjne a,RB,$+3 jc $+4 mov a,RB endm
unsigned X = Eingrenzung von X zwischen U und O vzl. `if (x<u) x=u; if (x>=o) x=o;`
	.macro limu1 ;X,U,O maxu1 @0,@1 minu1 @0,@2 .endm .macro limu1k ;X,U,O maxu1k @0,@1 minu1k @0,@2 .endm	.macro limu2 ;XH,XL, UH,UL, OH,OL maxu2 @0,@1, @2,@3 minu2 @0,@1, @4,@5 .endm .macro limu2k ;XH,XL, U, O maxu2k @0,@1, @2 minu2k @0,@1, @3 .endm	limu1 macro u,o ;X ist in A maxu1 x,u minu1 x,o endm
signed char X = Begrenzung(signed short X)
Vermeiden!	.macro cwbs ;XH,XL subi @1,0x80 ;80h addieren sbci @0,0xFF breq pc+4 ;High-Teil 0: OK ldi @1,0xFF brge pc+2 ;wenn N^V == 0 ldi @1,0 subi @1,0x80 ;wieder vzb. .endm		cwbs macro XH,XL local e mov a,XL add a,#80h mov a,XH adc a,#0 jz e mov XL,#7Fh swap a rr a xrl a,PSW jnb ACC.2,e inc XL e: endm

Sättigung⚓

Hierbei geht es um die Vermeidung eines Überlaufs nach einer Strichrechenoperation. Siehe auch Sättigungsarithmetik.

Beispielsweise: vzl. 0x90 + 0xA0 = 0x130 0x30 ⇒ 0xFF, hier im Beispiel vzb. 80 + 80 = 160 -96 => 127

Beispiel-Nr.	1	2	3	4	5	6	7
1. Summand	-15	3	5	-5	-127	-127	127
2. Summand	3	-3	10	-10	-1	-2	1
Summe (8 bit)	-12	0	15	-15	-128	127	-128
Überlauf-Flag V	0	0	0	0	0	1	1
Übertrags-Flag C	0	1	0	1	1	1	0
Negativ-Flag N	1	0	0	1	1	0	1
Korrektur	-	-	-	-	⇒-127	⇒-127	⇒127

Sättigung ist in Hochsprachen nicht direkt verfügbar! Mancher Leser wird entsprechende MMX- oder SSE2-Befehle kennen.

Makro-Sammlung (zum Rauskopieren):

PIC	AVR ATmega		8051
1 Byte in W	1-Byte-Operanden	2-Byte-Operanden	1 Byte in A
Vermeiden! Ausweich auf vzl. += vzb.	.macro sats1 ;A brvc 1f ldi @0,0x7F brmi 1f ldi @0,0x80 1: .endm	.macro sats2 ;AH,AL brvc 1f ldiw @0,@1, 0x7FFF brmi 1f ldiw @0,@1, 0x8000 1: .endm	sats1 macro jnb PSW.2,$+8 rlc a mov a,#80 subb a,#0 endm
vzb. Sättigung nach Addition oder Subtraktion vzb. Zahlen unter Vermeidung von -128 bzw. -32768
Vermeiden! Ausweich auf vzl. += vzb.	.macro sats1a ;A brvs 2f cpi @0,-128 brne 3f 1: ldi @0,-127 rjmp 3f 2: brcs 1b ldi @0,+127 3: .endm	.macro sats2a ;AH,AL brvs 2f cpiw @0,@1,-32768 brne 3f 1: ldiw @0,@1,-32767 rjmp 3f 2: brcs 1b ldiw @0,@1,+32767 3: .endm	nicht implementiert
vzl. Sättigung nach Addition vzl. Zahlen
satu1a macro SKPNC movlw 0FFh endm	.macro satu1a ;A brcc 1f ldi @0,0xFF 1: .endm	.macro satu2a ;AH,AL brcc 1f ldiw @0,@1, 0xFFFF 1: .endm	satu1a macro jnc $+4 mov a,#0FFh endm
vzl. Sättigung nach Subtraktion vzl. Zahlen
satu1s macro SKPNC movlw 0 endm	.macro satu1s ;A brcc 1f ldi @0,0x00 1: .endm	.macro satu2s ;AH,AL brcc 1f ldiw @0,@1, 0x0000 1: .endm	satu1s macro jnc $+3 clr a endm
vzl. Sättigung nach Addition vzl. (A) + vzb. (B)
Der High-Teil des zweiten (vzb.) Summanden muss angegeben werden
satus1 macro B btfsc B,7 goto $+4 skpnc movlw 0FFh goto $+3 skpc movlw 0 endm	.macro satus1 ;A, B sbrc @1,7 rjmp 1f brcc 2f ldi @0,0xFF rjmp 2f 1: brcs 2f ldi @0,0x00 2: .endm	.macro satus2 ;AH,AL, BH sbrc @2,7 rjmp 1f brcc 2f ldiw @0,@1, 0xFFFF rjmp 2f 1: brcs 2f ldiw @0,@1, 0x0000 2: .endm	satus1 macro ;2. Operand in B jb B.7,$+9 jnc $+9 mov a,0FFh sjmp $+5 jc $+3 clr a endm
vzb. Sättigung nach Addition vzb. (A) + vzl. (B)
Vermeiden! Auflösbar durch Inversion des MSB vor und nach der Rechnung mit vzl. Sättigung.

IEEE754-ähnliche NaN und ±∞⚓

Im folgenden betrachten wir 16-bit-Werte mit folgenden Werten:

–32766 … 32766 = normaler Wertebereich mit 0 = Null
±32767 = ±∞
-32768 = NaN

Eine Darstellung für 24 Bit, 32 Bit und mehr ist entsprechend. Für 8 Bit ist das Ganze nicht allzu lohnenswert, da es meistens um Messergebnisse und Filterfunktionen geht, bei denen man das Weiterrechnen nach Überläufen sinnvoll gestalten will.

Diese Zahlendarstellung hat folgende Eigenschaften:

Symmetrischer Wertebereich
Korrekte Funktion des unären Operators – (Negation)
Korrekte Funktion von Vergleichen — bei Ausschluss von NaN

Solange es keine Spezialprozessoren gibt, müssen arithmetische Operationen entsprechend (umständlich!) angepasst werden. Dazu ist es erforderlich:

vor der Operation die Operanden zu bewerten und bei anormalen Zahlen Fallunterscheidungen zu treffen
nach der Operation Überläufe abzufangen

Strichrechnung⚓

Die Tabelle zeigt die Ergebnisse für die beiden (kommutativen) Operanden einer Addition an. Grüne Felder bedeuten, dass die Additionsoperation ausgeführt werden kann und eine Überlaufauswertung (trotzdem) das richtige Ergebnis liefert. Die Addition liefert von sich aus NaN nur beim Aufeinandertreffen von +∞ und –∞.

Ergebnismatrix bei Addition
a b	+	+∞	NaN	–∞	–
+	+	+∞	NaN	–∞	±
+∞	+∞	+∞	NaN	NaN	+∞
NaN	NaN	NaN	NaN	NaN	NaN
–∞	–∞	NaN	NaN	–∞	–∞
–	±	+∞	NaN	–∞	–

Nach der Addition führt ein Überlauf (V-Flag gesetzt) zum Ersetzen durch ±∞, je nach Vorzeichen, entgegengesetzt. Das Ergebnis -32768 wird zu –∞ „angepasst“.

Die Subtraktion ergibt sich durch Addition mit der Negation des zweiten Operanden, fertig.

Punktrechnung⚓

Bei Multiplikation und Division spielt auch die Null eine Sonderrolle.

Ergebnismatrix bei Multiplikation
a b	0	+	+∞	NaN	–∞	–
0	0	0	NaN	NaN	NaN	0
+	0	+	+∞	NaN	–∞	–
+∞	NaN	+∞	+∞	NaN	–∞	–∞
NaN	NaN	NaN	NaN	NaN	NaN	NaN
–∞	NaN	–∞	–∞	NaN	+∞	+∞
–	0	–	–∞	NaN	+∞	+

Bei der (nichtkommutativen) Division ist die obere Zeile der Dividend, die linke Spalte der Divisor. Da es — anders als bei IEEE-Gleitkommazahlen — keine positive und negative Null gibt, kann die Division durch Null nur mit NaN „bestraft“ werden.

Ergebnismatrix bei Division
a b	0	+	+∞	NaN	–∞	–
0	NaN	NaN	NaN	NaN	NaN	NaN
+	0	+	+∞	NaN	–∞	–
+∞	0	0	NaN	NaN	NaN	0
NaN	NaN	NaN	NaN	NaN	NaN	NaN
–∞	0	0	NaN	NaN	NaN	0
–	0	–	–∞	NaN	+∞	+

Implementierung⚓

Optimal wäre eine Verarbeitung in Silizium. Das ist derzeit nur bei FPGAs möglich. Die Vor- und Nachbetrachtung der Operanden lässt sich hervorragend parallelisieren und benötigt nur wenig zusätzliche Chipfläche.

Um sich nicht in diese vielen Fallunterscheidungen zu verzetteln und Byte-Operanden zur Bewertung heranzuziehen, werden kurzerhand nur die letzten drei Bits einer jeden Zahl betrachtet, nach folgender Vorverarbeitung:

 char al=a&7;	// Low-Bits kopieren (∞ und NaN abfangend)
 if (a) {				// wenn nicht Null
  if ((unsigned)a<0x7FFFu) al=2;	// positiv
  else if ((unsigned)a>0x8001u) al=1;	// negativ; auch 6 siehe unten
  else al^=4;				// Bit kippen
 }

(Das ist nicht dasselbe wie Begrenzung = Bitbreitenreduktion!)

Damit hat al folgende praktischen Werte:

al		Bedeutung	Bemerkung
000	0	Null
001	1	negativ	günstig bei Tabellenzugriff
010	2	positiv
011	3	+∞
100	4	NaN
101	5	–∞
110	6	negativ	Alternative für programmatische Auswertung

Die Werte 0, 3, 4 und 5 kommen ohne Berechnungen zu Stande. Damit kann man einen Tabellenzugriff realisieren oder die Auswertung vereinfachen.