www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Multiplizieren mit sqrt(2)/2 in Schieben und Addieren


Autor: romanua (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich studiere die FFT-Routine aus www.renan.org/ARM/doc/Apps16pdf.pdf ,
bzw. die ARM-Optimierungstips aus dem Dokument.

Es steht auf Seite 14, dass die Autoren Multiplikation durch sqrt(2)/2
in Shifts und Adds machen. Wie macht man das?


Danke,
r.

Autor: Jan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sqrt2 ist ja 2^2 also
2 = 0b0010 ins quadrat =4
4 = 0b0100 also einfach einmal linksschieben
z.B.
a=0x02
a=a<<1
wäre sqrt

Autor: romanua (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jan, Danke fuer die Erklaerung.

Ich habe mich, glaube ich, nicht ganz klar ausgedrueckt. Unter sqrt(2)
meinte ich 2^(1/2).

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
(die Hälfte von Wurzel von zwei ) ist identisch mit (eins durch Wurzel
von zwei)  und beträgt etwa 0,707.
Ich habe mal auf dem AVR ein Näherung von (Wurzel zwei minus 1)mittels
Schieben und addieren berechnet:

;* 106/256 is an approximation of Sqrt(2)-1 = 0.4142
  clr  TempH    ; (1) multiply by 106
  lsl  TempL    ; (1) 106 = 2+8+32+64
  rol  TempM    ; (1) = "*2"
  mov  VectL,TempL  ; (1)
  mov  VectM,TempM  ; (1) add to vector
  clr  VectH    ; (1)
  lsl  TempL    ; (1)
  rol  TempM    ; (1)
  lsl  TempL    ; (1)
  rol  TempM    ; (1) = "*8"
  add  VectL,TempL  ; (1)
  adc  VectM,TempM  ; (1) add to vector
  lsl  TempL    ; (1)
  rol  TempM    ; (1)
  lsl  TempL    ; (1)
  rol  TempM    ; (1) = "*32", high byte = 0
  add  VectL,TempL  ; (1)
  adc  VectM,TempM  ; (1) add to vector
  lsl  TempL    ; (1)
  rol  TempM    ; (1) = "*64"
  rol  TempH    ; (1) now we need a 3rd byte
  add  VectL,TempL  ; (1)
  adc  VectM,TempM  ; (1) add to vector
  adc  VectH,TempH  ; (1)

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es ging um einen AD-gewandelten 12 Bit breiten Messwert in TempL/TempH,
das Ergebnis wird noch durch 256 geteilt, indem das niederwertigste
Ergebnis-Byte VectL weggelassen wird.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
für (Wurzel_zwei)/2 = 0,70710678118654752440084436210485..
wäre die nächste 8Bit-Näherung 181/256 = 0,70703125
mit 16 Bit: 46341/65536 = 0,7071075439453125

Autor: romanua (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,  Christoph,

Danke fuer den Ansatz. Ich hatte vor sqrt(2)/2 =0.707106781
als 181/256=0.70703125 zu berechnen. Das waere dann
1-2^(-2)-2^(-5)-2^(-7)-2^(-8).

Sagen wir mal, wir wollen x*sqrt(2)/2=x/sqrt(2)=x*0.707106781
berechnen.

ldr r1,=x
mov r2,r1
sub r2,r1,LSR #2
sub r2,r1,LSR #5
sub r2,r1,LSR #5
sub r2,r1,LSR #8

Direkt wurde ich es so machen (x ist 16 bit lang):

ldr r1,=x
ldr r2,=46341 @; Round( sqrt(2)*2^15 )
mul r2,r1,r2
mov r3,r3,LSR #16

das macht r3=x*0.707108

Ich frage mich jetzt, ob das nicht schneller ist, besonders wenn man
bedenkt, dass man ldr r2,=23170 "reusen"  kann.

Autor: Kai (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo

Wie wärs so:
1. Mit 181 Multiplizieren (kann mann ja auch durch verschieben und
addieren machen)
2. Ergebnis durch 256 teilen (= das niederwertigste Byte weglassen)
(eventuell vorher 128 addieren, um Rundungsfehler zu vermeiden)

Der Fehler ist nach meiner Rechnung 0,01 Prozent.

Autor: romanua (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,Kai,

Danke fuer den Vorschlag.

Ich frage mich, ob es an sqrt(2)/2 etwas besonderes gibt, da  die
Autoren des Papers diesen Fall angeblich mit einer separaten Routine
behandeln.


So, wie wir oben vorgeschlagen haben, kann man eigentlich jede
irrationale Zahl annaehern.

Ich wuerde  erwarten, dass die sqrt(2)/2 auf eine Weise berechnen, auf
die man andere Faelle nicht berechnen kann.  Ich konnte aber nichts im
Netz finden.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.