Zahlenbereich bei Addition

[R. K. (uc_student)]

Hallo

Ich versuche ein Mittelwertfilter zu implementieren und bin mir dabei 
nicht im Klaren, wie gross ich meine Signale machen muss.

Das Eingangssignal kommt von einem ADC und hat eine Breite von 14 Bit. 
Dieses wird danach in einen Integer gewandelt, welcher im Bereich 
-20'000...20000 angelegt ist. "AdcInBufxDS" hat also den Bereich 
-20'000...20000.

Wie kann ich dafür sorgen, dass es keinen Überlauf währen der Addition 
gibt?

Ich könnte natürlich den Bereich des AdcInBufxDS auf +-200000 setzen, 
doch dies scheint mir unschön.

Die Division "/8" ist im Moment eine genügend gute Näherung an "/10" und 
viel einfacher.

  FIR_ff : process(ClkxCI, RstxRBI)
  begin
    if RstxRBI = '0' then
      for c in 0 to 9 loop
        AdcInBufxDS(c) <= 0;
      end loop;
    elsif rising_edge(ClkxCI) then
      AdcInBufxDS(9) <= AdcInBufxDS(8);
      AdcInBufxDS(8) <= AdcInBufxDS(7);
      AdcInBufxDS(7) <= AdcInBufxDS(6);
      AdcInBufxDS(6) <= AdcInBufxDS(5);
      AdcInBufxDS(5) <= AdcInBufxDS(4);
      AdcInBufxDS(4) <= AdcInBufxDS(3);
      AdcInBufxDS(3) <= AdcInBufxDS(2);
      AdcInBufxDS(2) <= AdcInBufxDS(1);
      AdcInBufxDS(1) <= AdcInBufxDS(0);
      AdcInBufxDS(0) <= to_integer(unsigned(DataInxDI)) - 8192;

      DataInDecxDO <= NextDataInDecxS;
    end if;
  end process FIR_ff;

  FIR_comb : process(AdcInBufxDS)
  begin
    NextDataInDecxS<= (AdcInBufxDS(9) + AdcInBufxDS(8) + AdcInBufxDS(7) + AdcInBufxDS(6) + AdcInBufxDS(5) + AdcInBufxDS(4) + AdcInBufxDS(3) + AdcInBufxDS(2) + AdcInBufxDS(1) + AdcInBufxDS(0)) /8;
  end process FIR_comb;

[P. K. (pek)]

R. K. schrieb:
> Ich könnte natürlich den Bereich des AdcInBufxDS auf +-200000 setzen,
> doch dies scheint mir unschön.

Du wirst nicht darum herumkommen, aber so schlimm ist das in Tat und 
Wahrheit ja nicht. Das bedeutet nichts anderes als Deinen "signed" Wert 
um 3 Bit aufzubohren (19 statt 16 Bit).

[R. K. (uc_student)]

Also verstehe ich die korrekt:

Die Rechnung funktioniert auf der Registergrösse der Operanden und nicht 
des Resultats.
Ich muss die "AdcInBufxDS" mit dem grossen Bereich initialisieren, damit 
die Rechnung korrekt funktioniert. Den "NextDataInDecxS" kann ich jedoch 
auf den kleinen Bereich setzen.

[Moritz A. (moritz_a)]

Du kannst schon vor der Addition jeden Wert durch 8 teilen. Dauert zwar 
ein Moment länger, aber ich glaube nicht dass die Routine hier 
zeitkritisch ist.

[Clemens S. (zoggl)]

Moritz A. schrieb:
> Du kannst schon vor der Addition jeden Wert durch 8 teilen. Dauert zwar
> ein Moment länger, aber ich glaube nicht dass die Routine hier
> zeitkritisch ist.

und den rest auch aufsummieren, zum schluss dividieren und dazuzählen, 
dann ist es sogar genau.

[P. K. (pek)]

So müsste es gehen:

    SumxD           <= AdcInBufxDS(9) + AdcInBufxDS(8) + 
                       AdcInBufxDS(7) + AdcInBufxDS(6) + 
                       AdcInBufxDS(5) + AdcInBufxDS(4) + 
                       AdcInBufxDS(3) + AdcInBufxDS(2) + 
                       AdcInBufxDS(1) + AdcInBufxDS(0);
    NextDataInDecxS <= SumxD(18 downto 3); -- /8

NextDataInDecxS ist dann wieder ein 16-bit-signed.

Simulieren müsste Aufschluss geben.

[Moritz A. (moritz_a)]

Clemens S. schrieb:
> Moritz A. schrieb:
>> Du kannst schon vor der Addition jeden Wert durch 8 teilen. Dauert zwar
>> ein Moment länger, aber ich glaube nicht dass die Routine hier
>> zeitkritisch ist.
>
> und den rest auch aufsummieren, zum schluss dividieren und dazuzählen,
> dann ist es sogar genau.

Da er achtelt statt zehntelt ist es mit der Genauigkeit hier offenbar 
sowieso nicht so kritisch, daher habe ich den Rest großzügig liegen 
gelassen.

[franke (Gast)]

ähm... Mittelwert ?

Du addiert 10 Zahlen und dividierst durch 8 ??? hä?

Warum nicht 8 Addieren und durch 8 Dividieren. Dann ist es ein 
Mittelwert.


btw... dieser 10fach addieren wird verdammt langsam. Stichwort 
Pipelining.
btw... Division durch acht ist ein Shift, schreib's auch so hin.

gruß

[P. K. (pek)]

Moritz A. schrieb:
> Da er achtelt statt zehntelt ist es mit der Genauigkeit hier offenbar
> sowieso nicht so kritisch, daher habe ich den Rest großzügig liegen
> gelassen.

Das eine hat mit dem anderen nichts zu tun. Du verlierst nicht mehr an 
Genauigkeit, wenn Du leicht anders skalierst, falls in der 
darauffolgenden Rechnung die absolute Amplitude keine Rolle spielt.

[HolgerT (Gast)]

Moritz A. schrieb:
> Du kannst schon vor der Addition jeden Wert durch 8 teilen.

..und wirft damit 3 bit seiner 14-bit ADC-Genauigkeit weg. Ob das 
gewollt ist?

[R. K. (uc_student)]

Genau, die Division "/8" ist lediglich eine Skalierung, da es bei der 
späteren Berechnung nicht wirklich auf die absolute Amplitude ankommt 
ist dies vertretbar. Und die Division durch 8 (Ja ich schreibe Division, 
weil es ja nicht wirklich eins reiner shift ist, wegen des signed) ist 
viel einfacher als eine Division durch 10.

Bezüglich Verarbeitungszeit sehe ich überhaupt kein Problem. Ein 
FIR-Filter (also hier das Moving Average Filter) hat nunmal eine 
Verzögerung der "halben Ordnung" dies kann auch durch ein Piplining 
nicht verbessert werden. Oder sehe ich dies etwa falsch?

Die Ungenauigkeit durch die Division ist vertretbar und macht eine 
spätere Implementation auf einem günstigen ASIC-CPLD einfacher.

[Moritz A. (moritz_a)]

Peter K. schrieb:
> Das eine hat mit dem anderen nichts zu tun. Du verlierst nicht mehr an
> Genauigkeit, wenn Du leicht anders skalierst, falls in der
> darauffolgenden Rechnung die absolute Amplitude keine Rolle spielt.

Stimmt, mittlerweile hat der morgendliche Kaffee auch gewirkt :)

[P. K. (pek)]

R. K. schrieb:
> Oder sehe ich dies etwa falsch?

Der Pipelining-Aufwand kommt dann noch oben drauf. Eine "billigere" 
Lösung wäre die Summe zu speichern und jeweils den neuen Wert addieren 
und den ältesten zu subtrahieren. Du kommst so mit 2 Addern aus 
(vergibst Dir aber die Möglichkeit, die Taps in Zukunft zu gewichten).

> Und die Division durch 8 ist viel einfacher als eine Division durch 10.

Falls Du es trotzdem mal genau brauchst: Division durch eine Konstante 
ist nicht so schlimm, das kannst Du immer auf eine Division durch 2^N 
und eine Multiplikation reduzieren...

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Moritz A. schrieb:
> Du kannst schon vor der Addition jeden Wert durch 8 teilen. Dauert zwar
> ein Moment länger, aber ich glaube nicht dass die Routine hier
> zeitkritisch ist.
In Hardware ist eine Division durch eine Zweierpotenz einfach ein 
festes Umverdrahten. Das braucht überhaupt keine "Rechenzeit"...

Eine Division durch 10 könnte man auch mit einer Multiplikation mit 410 
und anschließendem Abschneiden der unteren 12 Bits hinreichend genau (1 
Promille Fehler) hinbekommen...

[Nicolas S. (Gast)]

Lothar Miller schrieb:
> Eine Division durch 10 könnte man auch mit einer Multiplikation mit 410
> und anschließendem Abschneiden der unteren 12 Bits hinreichend genau (1
> Promille Fehler) hinbekommen...

Wo kriegt man eigentlich solche Näherungen her? Reines "Trickreich 
denken" oder gibt es da eine Übersicht über gängige Methoden?

Ich muß gerade an "fast inverse square root" 
(http://en.wikipedia.org/wiki/Fast_inverse_square_root) denken.

[P. K. (pek)]

Nicolas S. schrieb:
> Wo kriegt man eigentlich solche Näherungen her?

Ist überhaupt kein Voodoo, Du willst durch 10 teilen, sprich mit 0.1 
multiplizieren. Jetzt gehst Du wie folgt vor:

1. Multiplizieren mit 2^N * 0.1
2. Weglassen der hintersten N Bits (i.e. teilen durch 2^N)

Den Fehler errechnest Du zu

3. Err = 0.1 / (ganzzahlgerundet(2^N*0.1) / 2^N)

So und jetzt musst Du nur noch N bestimmen, so klein wie möglich 
(Aufwand), so gross wie nötig (Fehler).

[Nicolas S. (Gast)]

Mir ist schon klar, daß der Bruch a/b durch c/(2^d) angenähert wird und 
ich für jedes d ein c finde, das den Fehler minimiert.

Aber wo lernt man solche Tricks?

[P. K. (pek)]

Nicolas S. schrieb:
> Aber wo lernt man solche Tricks?

Du hast ihn soeben hier gelernt...
...ich meinerseits vor ein paar Jahren bei der Arbeit. Solches Zeugs 
pushst Du Dir nicht gezielt in den Kopf, da kommt situationsbezogen 
immer wieder was dazu.

[Nicolas S. (Gast)]

Ich hab's schon befürchtet, daß ich für den Rest meines Lebens Foren 
lesen muß. :-)

[Bildverwursteler (Gast)]

Lothar Miller schrieb:
> Eine Division durch 10 könnte man auch mit einer Multiplikation mit 410
> und anschließendem Abschneiden der unteren 12 Bits hinreichend genau
Na dann aber lieber mal 1638 und zwei Bit mehr weg. Das sind dann 
wirkliche 0,1%