Digitale Signalverarbeitung Vorlesung 6 - Quantisierungseffekte · 2018. 11. 16. · Diese VL: Betrachtung der nichtlinearen E ekte, die sich durch endliche Wortbreiten ergeben

Festkomma- vs. FließkommaarithmetikKoeffizientenquantisierung

SignalquantisierungVermeidung von Uberlaufgrenzzyklen

Digitale SignalverarbeitungVorlesung 6 - Quantisierungseffekte

Arbeitsgruppe Kognitive Signalverarbeitung

19. November 2018

Siehe Skript, Kapitel 8Kammeyer & Kroschel, Abschnitt 4.4

1 / 44



1 Festkomma- vs. Fließkommaarithmetik

2 Koeffizientenquantisierung

3 SignalquantisierungBetrachtung als lineares System: InternesQuantisierungsrauschenExakte Betrachtung: Grenzzyklen

4 Vermeidung von UberlaufgrenzzyklenStrenge SkalierungApproximierte SkalierungSimulation

2 / 44



Bisher: Lineare Darstellung von Systemen.

Diese VL: Betrachtung der nichtlinearen Effekte, die sichdurch endliche Wortbreiten ergeben.

4 / 44



Festkomma- vs. Fließkommaarithmetik

Grundsatzliche Entscheidung

Festkommaarithmetik Fließkommaarithmetik

RAM und klein groß

ROM-Bedarf

Rechenzeit schnell langsam

Energiebedarf niedrig hoch

Fehler- groß: Quantisierung + klein

anfalligkeit Overflow

Entwicklungszeit langer kurzer

5 / 44



Festkommaarithmetik auf DSPs

Gesucht fur Festkommarechnung:Zahlendarstellung fur DSPs, die

beliebig genau

reelle Zahlen (positiv und negativ) darstellen kann,

und deren arithmetische Operationen (Summe, Differenz,Produkt, Quotient) mit geringem Aufwand in Hardware zuimplementieren sind.

Losung: Zweierkomplementdarstellung im sogenannten FractionalFormat.

6 / 44



Zweierkomplementdarstellung im Fractional-Format

Jede reelle Zahl x(k0) lasst sich mit beliebiger Genauigkeit durch

x(k0) = Xm

(−w0 +

∞∑i=1

wi2−i

)(1)

als Zweierkomplementzahl darstellen.

w0 ist das Vorzeichenbit, Xm ist ein Skalierungsfaktor.

Damit alle Werte aus x(k) dargestellt werden konnen, muss gelten

Xm > maxk0 |x(k0)| (2)

7 / 44



Fractional-Format

Bei endlicher Wortlange W wird aus

x = Xm

(−w0 +

∞∑i=1

wi2−i

)(3)

nun ein quantisiertes Signal

xQ = Xm

(−w0 +

W−1∑i=1

wi2−i

)(4)

mit der Auflosung Xm2−(W−1).Diese Darstellung von Zahlen im Bereich von ±1 durch[w0 . . .wW−1] bezeichnet man als Fractional-Format.

8 / 44



Effekt der Koeffizientenquantisierung

Der Effekt der Koeffizientenquantisierung ist abhangig von derRealisierung der Ubertragungsfunktion.Bei der Direktform erhalt man aus

H(z) = zn−m∑m

µ=0 bµzm−µ∑n

ν=0 aνzn−ν . (5)

dann

H(z) = zn−m∑m

µ=0 [bµ]Qzm−µ∑n

ν=0 [aν ]Qzn−ν. (6)

mit [aν ]Q als quantisierte Version von aν .Problem: Jede Null- & Polstelle ist von allen Koeffizientenabhangig.→ Oft besser zu optimieren: Entkopplung durch 3. oder 4.kanonische Form.

10 / 44



Mogliche Pollagen in Systemen zweiter Ordnung

Das quantisierte System hat folgende Ubertragungsfunktion

H(z) =[b0]Qz

2 + [b1]Qz1 + [b2]Q

z2 + [a1]Qz1 + [a2]Q. (7)

Wenn das System zwei konjugiert komplexe Pole besitzt, die alsz∞ = ρ∞e±jα∞ geschrieben werden konnen, gilt

z2 + [a1]Qz1 + [a2]Q = (z − ρ∞e+jα∞)(z − ρ∞e−jα∞) (8)

= z2 − z2ρ∞ cos(α∞) + ρ2∞. (9)

11 / 44



Mogliche Pollagen in Systemen zweiter Ordnung

Wegen

z2 + [a1]Qz1 + [a2]Q = z2 − z2ρ∞ cos(α∞) + ρ2

∞ (10)

gibt es folgende Entsprechungen:

[a1]Q∧= [−2ρ∞ cos(α∞)]Q = [−2R(z∞)]Q (11)

[a2]Q∧= [ρ2

∞]Q = [|z∞|2]Q . (12)

12 / 44




[a1]Q∧= [−2ρ∞ cos(α∞)]Q = [−2R(z∞)]Q (13)

[a2]Q∧= [ρ2

∞]Q = [|z∞|2]Q (14)

fuhrt bei Quantisierung der Koeffizienten[a1,2]Q = n · Q, n ∈ −2W−1 . . .− 1, 0, 1, 2, 3 . . . 2W−1 − 1 auffolgende mogliche Pollagen:

13 / 44




Pollagen fur quantisierte Koeffizienten

−1 −0.5 0 0.5 1−1

−0.5

0

0.5

1

re(z)

im(z

)

(a) 6 Bit

−1 −0.5 0 0.5 1−1

−0.5

0

0.5

1

re(z)

im(z

)

(b) 8 Bit

14 / 44




Diese Verteilung hat Vor- und Nachteile:

Ungleichmaßige Rasterung fuhrt in manchenFrequenzbereichen zu großen Abweichungen der Pollagenaber genaue Auflosung in der Nahe des Einheitskreises kannnutzlich sein, besonders fur steilflankige Filter.

Andere Filterstrukturen, z.B. die gekoppelte Struktur fuhrenzu gleichmaßiger Verteilung der moglichen Pol-/Nullstellen,siehe Kammeyer & Kroschel (Kapitel 4.4.2) fur mehr Detailsund Referenzen.

15 / 44



Betrachtung als lineares System: Internes QuantisierungsrauschenExakte Betrachtung: Grenzzyklen

Interne Quantisierungsfehler

Wie schon beim Eingangssignal v(k) gibt es auch fur interneSignale und fur das Ausgangssignal zwei Fehlerquellen:

y(k)

yq(k)

Q ymax = 1-2l

E

y(k)

Quantisierungsrauschen Überlastungs-

rauschen

Überlastungs-

rauschen

ymin=-1

Figure: Quantisierungs- und Uberlastungsrauschen.17 / 44




Quantisierung innerhalb des Filters

Innerhalb des Filters werden Signale mit Filterkoeffizientenmultipliziert.

Eine Multiplikation von zwei vorzeichenbehaftetenW -bit-Zahlen fuhrt bei voller Genauigkeit auf eine(2W − 1)-bit-Zahl.

Werden hier die unteren w Bits ignoriert, fuhrt das zu dengleichen Effekten wie die Quantisierung am Eingang desSystems: Innerhalb des Systems entsteht Rauschen, das durchdie weiteren Filterstufen gefiltert wird.

18 / 44




Quantisierung innerhalb des Filters

Zwei Optimierungsmoglichkeiten in Signalprozessoren:

Sogenannte MAC-Einheit 1 mit großerer interner Wortbreite.

proportion of overflow headroom in C67x floating-point DSPs would require 64 interme-diate product bits (24 signal + 24 coefficient + 16 overflow), which would go beyondmost application requirements in accuracy. Fortunately, through exponentiation thefloating-point format enables keeping only the most significant 48 bits for intermediateproducts, so that the hardware stays manageable while still providing more bits of inter-mediate accuracy than the fixed-point format offers. These word widths are summa-rized in Table 1 for several TI DSP architectures.

Table 1. Word widths for TI DSPs

Video and audio data set requirements

The advantages of using the fixed- and floating-point formats can be illustrated by con-trasting the data set requirements of two common signal-processing applications: videoand audio. Video has a high sampling rate that can amount to tens or even hundredsof megabits per second (Mbps) in pixel data, depending on the application. Pixel datais usually represented in three words, one for each of the red, green and blue (RGB)planes of the image. In most systems, each color requires 8 to 12 bits, thoughadvanced applications may use up to 14 bits per color. Key mathematical operations ofthe industry-standard MPEG video compression algorithms include discrete cosinetransforms (DCTs) and quantization, and there is limited filtering.

Audio, by contrast, has a more limited data flow of about 1 Mbps that results from 24bits sampled at 48 kilosamples per second (ksps). A higher sampling rate of 192 kspswill quadruple this data flow rate in the future, yet it is still significantly less than video.Operations on audio data include infinite impulse response (IIR) and intensive filtering.

Video and audio data set requirements

4 SPRY061

TI DSP(s) Format

Word Width

Signal I/O CoefficientIntermediate

resultC25x fixed 16 16 40

C5x™/C62x™ fixed 16 16 40

C64x™ fixed 8/16/32 16 40

C3x™ floating 24 (mantissa) 24 32

C67x™(SP) floating 24 (mantissa) 24 24/53

C67x(DP) floating 53 53 53Noise-Shaping: Spektrale Formung des Quantisierungs-rauschens (dazu gefilterte Ruckfuhrung des intern bekanntenQuantisierungsfehlers), s. Kammeyer & Kroschel Kap. 4.4.5.

1Multiply-Accumulate-Einheit19 / 44




Nichtlineare Effekte

Ein quantisiertes Filter wird nichtlinear. Es gilt also nicht mehrf (αv) = αf (v)!Daraus ergeben sich zwei wesentliche, neue Probleme:

Sogenannte Grenzzyklen, bei denen das System selbsttatigund mit konstanter Amplitude eine unerwunschte Schwingungproduziert (auch wenn es “eigentlich” stabil ist)

und Skalierungsabhangigkeit – auf einmal ist es nicht mehregal, ob y(k) oder 100y(k) ausgerechnet wird, und das eineoder das andere kann sehr viel geschickter sein.

20 / 44




Grenzzyklen

Es existieren zwei Arten von Grenzzyklen:

Quantisierungsgrenzzyklen, haben ihre Ursache inRundungsfehlern und

Uberlaufgrenzzyklen treten wegen eines Zahlenuberlaufesauf.

21 / 44




Quantisierungsgrenzzyklen

Beispiel:

H(z) =1

1 + az−1=

z

z + a(15)

entspricht der Differenzengleichung

y(k) = v(k)− ay(k − 1). (16)

Quantisierung der Multiplikation ergibt:

y(k) = v(k)− [ay(k − 1)]Q . (17)

22 / 44




Quantisierungsgrenzzyklen

Beispiel:

y(k) = v(k)− [ay(k − 1)]Q . (18)

Wenn v(k) = 0 ist, aber |y(k − 1)| > 0, konnen noch zweiunerwartete Ergebnisse auftreten:

y(k) = −y(k − 1), also ein Grenzzyklus der Frequenz Ωg = πoder

y(k) = y(k − 1) also ein Grenzzyklus mit Ωg = 0.

23 / 44




Quantisierungsgrenzzyklen, Fall 1

Beispiel:

y(k) = v(k)− [ay(k − 1)]Q!

= −y(k − 1). (19)

Da das Eingangssignal = 0 ist, tritt diese Situation auf, wenn

−[ay(k − 1)]Q = −y(k − 1), (20)

also wenn

[ay(k − 1)]Q = y(k − 1) (21)

⇒|y(k − 1)− ay(k − 1)| ≤ Q

2(22)

24 / 44





⇒ (1− a)|y(k − 1)| ≤ Q

2

⇒ |y(k − 1)| ≤ Q

2(1− a)

⇒ IQ ≤ Q

2(1− a), I ∈ N

⇒ I ≤ 1

2(1− a)def= d .

Diese Grenzzyklen konnen sich also nur fur einen bestimmtenWertebereich I ≤ d ausbilden; d wird auch als Deadbandbezeichnet.

25 / 44





⇒ (1− a)|y(k − 1)| ≤ Q

2

⇒ |y(k − 1)| ≤ Q

2(1− a)

⇒ IQ ≤ Q

2(1− a), I ∈ N

⇒ I ≤ 1

2(1− a)def= d .

Sie treten nur auf, wenn 0.5 ≤ a < 1 gilt (fur a = 1 hatten wirnamlich auch im linearen schon ein instabiles System, dieSchwingung ware also kein Grenzzyklus).

26 / 44





Beispiel:

y(k) = v(k)− [ay(k − 1)]Q!

= y(k − 1). (23)

Prinzipiell gelten die selben Uberlegungen wie vorhin, hier fuhrensie auf das gleiche Deadband und auf Koeffizienten−1 < a ≤ −0.5.Insgesamt treten also Quantisierungsgrenzzyklen fur Systeme ersterOrdnung nur dann nicht auf, wenn |a| < 0.5.

27 / 44




Quantisierungsgrenzzyklen vermeiden

Es gibt verschiedene Moglichkeiten zur Vermeidung:

Koeffizienten konnen so gewahlt werden, dass keineGrenzzyklen durch Quantisierung auftreten konnen (sieheAbschnitt 4.4.6 in Kammeyer & Kroschel fur die Bedingungenbei Systemen zweiter Ordnung).

MAC-Einheiten konnen Grenzzyklen zu vermeiden helfen,genau wie

Wellendigitalfilter (Filterstrukturen, die genauer in [1]beschrieben sind.)

28 / 44




Uberlaufgrenzzyklen

Wenn das Signal am Filterausgang den Aussteuerungsbereich desSystems uberschreitet, konnen Uberlaufgrenzzyklen auftreten.Beispiel: Bei Begrenzung der Systemamplituden auf 1 undVerwendung von Zweierkomplementzahlen, mit

y(k) = [v(k)− a1y(k − 1)− a2y(k − 2)]Q (24)

treten Uberlaufgrenzzyklen nur dann nicht auf, wenn sichergestelltist, dass

|−a1y(k − 1)− a2y(k − 2)| < 1 (25)

fur alle Werte von y(k − 1), y(k − 2).

29 / 44




Uberlaufgrenzzyklen

Gefordert:

|v(k)− a1y(k − 1)− a2y(k − 2)| < 1 (26)

fur alle Werte von y(k − 1), y(k − 2), mit v(k) = 0.Es gilt ja auch, |y(k − 1)| ≤ 1, |y(k − 2)| ≤ 1. Daraus konnenwieder zulassige Bereiche fur die Koeffizienten berechnet werden:

|a1|+ |a2| < 1. (27)

30 / 44




Uberlaufgrenzzyklen

Zulassige Bereiche fur die Koeffizienten:

|a1|+ |a2| < 1. (28)

Weil diese Anforderung in der Praxis eine (viel) zu starkeEinschrankung darstellt (diese Koeffizientenwerte decken nur einensehr kleinen Teil der z-Ebene ab), sind andere Losungen notig.

31 / 44




Uberlaufgrenzzyklen

Mogliche Losungen zur Verhinderung von Uberlaufgrenzzyklen:

Sattigungskennlinien - Summierer verhindern Uberlauf perHardware oder Software

Skalierung des Eingangssignals und aller Zwischenwerte.

Oft werden beide Losungen kombiniert - die Skalierung verhindertim Normalfall Uberlaufe, gleichzeitig unterbindet dieSattigungskennlinie im schlimmsten Fall einer doch auftretendenUbersteuerung garantiert Uberlaufgrenzzyklen.

32 / 44



Strenge SkalierungApproximierte SkalierungSimulation

Skalierung

Der Filterausgang

yQ(k) = [h(k) ∗ vQ(k)]Q (29)

soll nicht ubersteuern.Dazu wird im Weiteren angenommen, dass das System mit demFractional-Format arbeitet.

34 / 44




Strenge Skalierung

Durch einen zusatzlichen Skalierungsfaktor c am Eingang desSystems kann eine Ubersteuerung des Ausgangssignalsy(k) = c · vQ(k) ∗ h(k) vermieden werden. Dafur muss gelten:

|y(k)| =

∣∣∣∣∣∞∑

i=−∞c · h(i)vQ(k − i)

∣∣∣∣∣≤

∞∑i=−∞

c |h(i)vQ(k − i)|

≤ c · vmax

∞∑i=−∞

|h(i)|

!< 1.

35 / 44




Strenge Skalierung

Wegen

c · vmax

∞∑i=−∞

|h(i)|!< 1

muss also als Bedingung gelten:

c!<

1

vmax∑∞

i=−∞ |h(i)|=

1∑∞i=−∞ |h(i)|

.

36 / 44




Strenge Skalierung

Tatsachlich muss ja diese Bedingung nicht nur am Ausgang desFilters sondern auch an allen s = 1 . . . S internen Summenknotendes Systems erfullt sein:

c!<

1

maxs=1...S∑∞

i=−∞ |hs(i)|.

Forderung bei strenger Skalierung

37 / 44




Strenge Skalierung

Die Bedingung

c!<

1

maxs=1...S∑∞

i=−∞ |hs(i)|

fuhrt schnell auf sehr kleine Ausgangssignale, die einschlechtes SNR liefern, aber garantiert nie ubersteuert sind.

Andere Methoden liefern mit Approximationen eine großereSkalierung, die manchmal ubersteuern kann.

38 / 44




Approximierte Skalierung

Fur schmalbandige Signale

v(k) ≈ vmax cos(Ω0k)

gilt am Ausgang des Filters

y(k) ≈∣∣∣H(e jΩ0)

∣∣∣ c · vmax cos(

Ω0k + arg(H(e jΩ0)

))

39 / 44





Aus

y(k) ≈∣∣∣H(e jΩ0)


Ω0k + arg(H(e jΩ0)))

ergibt sich dann direkt (fur vmax = 1), dass |y(k)| < 1 falls∣∣∣H(e jΩ0)∣∣∣ c < 1

⇒ c <1

|H(e jΩ0)|

40 / 44





Auch hier muss die Anforderung wieder an allen s = 1 . . . SSummenknoten gelten, außerdem hier auch fur alle moglichenSignalfrequenzen Ω0 ∈ [0, π].So ergibt sich aus

y(k) ≈∣∣∣Hs(e jΩ0)


Ω0k + arg(Hs(e jΩ0)))

:

c!<

1

maxs=1...S,Ω0∈[0,π] |Hs(e jΩ0)|

Forderung bei approximierter Skalierung

41 / 44




Simulation quantisierter Systeme

Genau wie zuvor fur lineare Systeme, werdenRapid-Prototyping-Umgebungen wie Matlab auch fur dieSimulation quantisierter Systeme verwendet.

Das ist sogar von besonderer Bedeutung, weil die vielfaltigenQuantisierungseffekte in ihrer Kombination in komplexenSystemen oft schwer zu analysieren sind.

Besonders effiziente Entwicklung erlaubenHardware-in-the-Loop-Tools, die z.B. die PC-basierteSimulation des Signalverarbeitungssystems direkt an dieexternen Signale und Systeme ankoppeln.

42 / 44




Lernziele

Sie sollten wissen,

was die Vor- und Nachteile von Festkommaarithmetik in derSignalverarbeitung sind,

wie reelle Zahlen im Fractional Format dargestellt werden,

welche Quantisierungs- und Rundungseffekte sich beiendlichen Wortlangen in digitalen Filtern ergeben konnen,

und mit welchen Herangehensweisen - speziellSkalierungsmethoden - man diese analysieren und derennegative Auswirkungen abmildern kann.

43 / 44




Vielen Dank fur Ihre Aufmerksamkeit!

44 / 44




Alfred Fettweis.Wave digital filters: Theory and practice.Proc. IEEE, 4:270–327, 1986.

44 / 44

Documents

Digitale Signalverarbeitung Vorlesung 6 - Quantisierungseffekte · 2018. 11. 16. · Diese VL: Betrachtung der nichtlinearen E ekte, die sich durch endliche Wortbreiten ergeben