Dimensionierung Antialiasing-Filter

Hallo Ruediger,

Und scheinbar sein Forschungsbereich danach wie ueblich so ziemlich auseinandergefallen :-(

Newsbeitrag

in der tat hört es sich eher nach der russichen Bauernmethode (dass ist der Name unter der ich sie kenne) an. Die ist aber nichts anderes die normale Multiplikation (ggf. "geloopunrollt"). Falls du doch was anderes meinst Rüdiger, würde ich gerne mehr davon hören (link reicht).

Florian

"Florian Stock" schrieb:

Ja, hat auch diesen Namen, sie kann aber wesentlich schneller sein als die Standardmethode (die mit der fixen loop), sag' ich gleich noch was zu).

Donald E. Knuth erwähnt sie z.B. auf S.400 seines 2. Bandes "Art of Computer programming" (2. Aufl.) in Zusammenhang mit einer ähnlichen Methode für x^n, ich tippsere mal ab:

"It..." [der andere Algorithmus, rk] "...is closely related to a procedure for multiplication which was used by Egyptian mathematicians as early as 1800 B.C. [...] This is a practical method for multiplication by hand, since it involves only the simple operations of doubling, halving, and adding. It is often called the "Russian peasant method" of multiplications, since Western visitors to Russia in the nineteenth century found the method in wide use there."

Steve Jobs hatte sie in seinen allerersten Apfel eingebaut (in den Basicinterpreter) und nennt sie "den indischen Algorithmus", weil man ihn auch schon in vedischen Schriften findet. Dort findet man übrigens sehr viele hochinteressante Rechenmethoden, klar, "unsere" Ziffern, die wir "arabische Ziffern" nennen weil wir sie von den Arabern 'ge- klaut' äh kulturübernommen haben nennen die Araber selbst "indische Ziffern", weil sie sie wiederum aus Indien haben. Auch diese ganzen Rechenmethoden finden sich natürlich schon bei den Erfindern "unserer" Zahlen, klar...

Europa hat bis ins ausgehende Mittelalter noch mit römischen Zahlen gerechnet und jetzt soll mal einer schnell hier schriftlich XIX * LXIII vorrechnen :)

Was die Wikipedia unter "vedischem Algorithmus" anführt ist aber nicht, was ich hier meine, gibt wie gesagt viele Algorithmen von den Erfindern 'unserer' Zahlen:

Ich führ' den indischen Algorithmus mal kurz vor für die, die ihn vielleicht noch nicht kennen.

Möchte ich zwei Zahlen multiplizieren, z.B. 13 mal 8, dann nehme ich die

13*8 = 26*4 = 52*2 = 104*1 ... fertig.

Ich bitte zu beachten, dass es vier Schritte waren und eine Addition kam diesmal nicht vor, nur verdoppeln/halbieren was Digitalrechner, gerade auch die allerkleinsten unter ihnen (uC) ja besonders gut und schnell können (shiften).

Noch einen: 33 * 4

Im Vergleich zum oft zu sehenden Standardalgorithmus, der immer eine fixe Schleife abnudelt *kann* der Algorithmus deutlich schneller sein, nie aber langsamer.

Wenn jetzt einer ruft: "Ah, der Trick war ja dass du in die rechte Hand immer eine glatte Zweierpotenz... haha, durchschaut!" dann modifiziere ich meine Vorführung noch etwas, dann isses die benutzte Methode von der es etliche Variationen gibt (Mit Addition, mit Subtraktion geht auch aber warum soll ein armer Programmierer unnötig Zweierkomplementieren?)

Wenn ich nicht 33*4 sondern 33*5 rechnen soll, tschja...

Da die Zahl in der rechten Hand ungerade ist, kann ich sie schlecht halbieren ohne Rest, also zerlege ich:

33*4 kenne ich schon bzw. kann ich rechnen :), muss ich also nur 33 hinzuaddieren zum Ergebnis. 165. Noch einen oder zwei:

17*13 = 17*12 + 17*1 = 34*6 + 17 = 68*3 + 17 = 68*2 + 68*1 + 17 = 136*1 (ah, ich bin fertig mit half/double) + 68 + 17 = 221

(Stimmt das auch, wo ist mein TR? *g*)

Immer wenn der zu halbierende Faktor ungerade ist (bit0 gesetzt) kommt halt eine Addition noch ins Spiel.

Seite 3 ist auch nett, eine der Variationen der Methode bzw. eigentlich identisch :)

Was man oft in Fixpointbibliotheken sieht, z.B AN617, Fixpointroutinen von und für microchip 16Cxx ist das abnudeln einer festen Schleife, für

Copypasteprobe aus genannter Quelle, siehe auch Flussdiagramme p.11:

; *** 08x08 Bit Multiplication Macros ***

SMUL0808L macro MOVLW 0x07 MOVWF LOOPCOUNT MOVF AARGB0,W LOOPSM0808A RRF BARGB0, F

Ja, AARGH :)

Erster Befehl lädt den Schleifenzähler mit der Zahl 7, das ergibt dann 8 feste Schleifendurchläufe. Bei den 32bit-Routinen steht dann da die magic number 31 u.s.w.

Oder UMUL in 68hc11 eForth, liegt hier grad zufällig griffbereit rum, genau das gleiche Elend:

• multiply

• um* ( u u -- ud )
• unsigned multiply. return double product.

fcc 'UM*' umsta nop jmp dolst fdb dolit,0,swap,dolit,15,tor

umst1 fdb dup,uplus,tor,tor fdb dup,uplus,rfrom,plus,rfrom fdb qbran,umst2 fdb tor,over,uplus,rfrom,plus umst2 fdb donxt,umst1 fdb rot,drop,exit

(Anfang ist nur für 'linked list' Verwaltung, die erste Zeile der Routine ist die vor dem UMPFF, äh, umst1 mit dem dolit(eral) 15 --> das ist der Schleifenzähler für 16bit Multiplikation)

Wohin man guckt, überall das gleiche Elend *g*

"Joerg" schrieb:

Na ja, die Elektrotechnik gibts hier schon noch und es geht ihr auch recht gut, wie ich höre. Die scheinen mir quietschmunter zu sein... :)

Klar, es kommt ein neuer Prof. der seine eigenen Leute mitbringt und auch andere Forschungsschwerpunkte setzt u.s.w. Uni eben!

Anders muss ja erstmal nicht schlechter sein, nur anders! {wenn man jetzt mal politischen Vorgaben ausser Acht lässt :}

Hallo Ruediger,

Aber den WDF Schwerpunkt nicht mehr.

Das ist in der Industrie wohltuend anders. Dort aendert sich die Produktpalette normalerweise nicht, nur weil ein neuer Boss kommt. Und wenn, dann recht langsam.

Gibt es bei Euch diesen unsinnigen "Proporz" immer noch?

Ein Institut hat aber auch keine Kunden, die man verprellen könnte. Und wenn doch, gibt es heutzutage meist längst ein Spin-Off.

Ich finde schon, daß man dem Professor die Freiheit lassen sollte, an dem zu forschen was _er_ für forschenswert hält[1].

Gruß Henning

Hallo Henning,

Die Kunden sind in diesem Fall viele Wissenschaftler und Ingenieure. Ich denke, jedes Institut hat in dieser Hinsicht eine Art Mandat. So aehnlich wie es z.B. die Deutsche Welle bei Euch hat und IMHO leider nicht mehr besonders gut erfuellt.

Sehe ich ein wenig anders. In der Industrie laesst man uns diese Freiheit auch nicht. Klar muss man seine eigenen Ideen einbringen koennen, aber behutsam. Das in Academia oft uebliche Umlegen des dicken Projektschalters auf "Aus" halte ich nicht fuer gut.

Das sollten Institute. Stanford macht das recht schoen, auch wenn ich deren Gebaren in Sachen IP Verteidigung nicht so galant finde. Die fertigen inzwischen eine ganze Reihe von Labormessgeraeten. Hatte vor einem Monat das Vergnuegen, zwei davon zu benutzen. Dies erzieht Stundenten und viele andere dort zu einer "Industrie-Denke", die sie spaeter im Beruf brauchen.

Das ist im Prinzip nichts anderes als die Standardmethode, nur dass du nach jedem Shift-Add Schritt schaust, ob noch "Rest" vorhanden ist, und ggf. abbrichst.

Dass das schneller ist, muss aber nicht sein.

Da du weisst, dass es z.B. konstant 8 Iterationen sind, kannst du die Schleife entrollen und sparst so in jedem Schritt den Vergleich und den Sprung. Jetzt kommts natürlich auf die Architektur an, was Sprung und Vergleich kostet, aber ich denke du bist fast immer schneller mit den 8 Iterationen (bei Worst-Case Betrachtung vermutlich sogar bei jeder Architektur).

Das unrollen ist hier der Knackpunkt, und ich habe mir mal dein Beispiel genauer angesehen (ich kenne mich damit nicht so genau aus, darum vergib mir wenn ich die Daten falsch interpretiert habe).

in der Quelle gibts gibts auch (weiter unten) die Funktionen ohne L hinten (ich habe keine Ahnung wann welche benutzt werden), die es genau so machen (wenn ich das while als Assembler/Preproz-Direktive richtig interpretiere).

Aber du hast natürlich auch nicht unrecht, es gibt fälle wo die russische/indische Methode schneller sein kann (ich denke allerdings, dass sie eher selten sind), und sie trotzdessen nicht benutzt wird, Grund: Programmierer sind auch nur Menschen (machen Fehler, wissen nicht alles, ...).

Florian

Hallo Joerg,

Joerg schrieb:

eigentlich ist es ganz klar, man kann z.B. in Matlab mit einem Resource Construction Set sehr leicht Windows-mäßige Programme erstellen und hat alle nötigen Libraries mit dabei, dazu noch die Toolboxen, die einem fertig alles Nötige liefern. Der Einarbeitungsaufwand ist da eben minimal. Die Programmiersprache ist allerdings zu allem inkompatibel und nicht portabel.

Ich kann mich noch gut erinnern, wie mal auf Atari in C mit allerdings auch kostenloser Grafik-Library programmiert wurde. Der Arbeitsaufwand war groß und die Fehlersuche schwierig, weil C die Tendenz hat, wild im Speicher rumzuschießen. Sicher gibt es auch für IBM-PC professionelle Software, siehe Visual C oder auch von anderen Firmen, kostet aber auch entsprechend was. Wenn ich z.B. Visual C starte und mal "Hello World" zur Übung "programmieren" möchte, macht der mir ein Megabytes großes Programm daraus. Und dann muß man noch herausfinden, wo man seine eigenen Unterprogramme einklinken muß, erinnere mich gut an ein diesbezügliches Chaos in Borland C.

Sonst wäre es nicht finanzierbar und würde nicht gekauft werden, schon jetzt ist der Anteil der Softwarekosten sehr hoch. Ein anderes Problem betrifft Lizensierung und solche Dinge wie Plattformen. Wir haben z.B. das (von Synopsis fast geschenkt bekommene) ultrateure COSSAP für Sun Solaris. Das kann man nicht zum Einarbeiten mal eben so auf einem beliebigen Rechner installieren, also nutzt es keiner, mittlerweile hat Matlab diese Möglichkeiten auch. Oder ein ARM-Entwicklungssystem, das auf einen Rechner festgenagelt worden ist, das wird 1mal genutzt, dann ist es tot.

Ich überschau das nicht, wie weit die Industriepreise gerechtfertigt sind, das ist allerdings auch kein Massenmarkt. Wir wollten z.B. mal die

mfg. Winfried

Hallo Winfried,

In der Industrie geht das knallhart. Eval-Kit Preise sind nicht so wichtig, die Mengenstaffeln bei uC aber sehr. Wenn da einer $1 drueber liegt, muss man damit eben auch mindestens $1 and anderen Kosten einsparen, sonst wird er nicht genommen. Und wenn es kein 2nd Source gibt, dreht man eh alles dreimal um.

Bei Software sieht man sich bei der Konkurrenz um. Kompatibel ist in Sachen CDA eh so gut wie nichts, also nimmt man, was passt und preislich im Rahmen bleibt.

Hallo Rafael,

Rafael Deliano schrieb:

ja das sieht vom Inhaltsverzeichnis schon sehr interessant aus, viele Themen.

digitale Filter lassen sich leicht simulieren, analoge nicht. Mit Matlab kann man die Wortlängenbegrenzung leicht simulieren und mit Optimierungssoftware wie Falcon die minimale Wortlänge berechnen lassen.

Bei heutigen großen Systemen stößt man bei der Rechnersimulation aber immer schnell an die Grenze.

Ich weiß nicht, warum so viele Leute immer dem neusten modischen Trend hinterherlaufen in der Meinung, das wäre besser. Ich habe hier eine Fortran-Bibliothek von IBM, müßte sogar aus den 60ern stammen, da sind einige sehr brauchbare Programme dabei, die laufen auch heute noch. Einen Grund, die auf C umzusetzen sehe ich nicht, C++ schon garnicht. Und wofür man Objektorientierung braucht, weiß ich nicht, bei Parks-McLellan sind jedenfalls keine Objekte drin.

Ja die Basic-Leute wollen es sich einfach machen, ich treffe immer wieder welche, nur sind deren Programme schon beim Schreiben tot. Und warum das umständliche C in technisch-wissenschaftlichen Programmen benutzt wird weiß ich auch nicht. Ich sehe nur, daß da mit allen möglichen abenteuerlichen Strukturen gebastelt wird und hinterher weiß keiner mehr, warum es nicht funktioniert.

Ich sage immer, nach 10 Jahren Pause kann ich mich hinsetzen und sofort in Fortran programmieren, in C nicht.

Die Leute von Mathworks koppeln sich mit anderen Firmen, bei uns mit Xilinx, man kommt schlecht daran vorbei und wenn es sich durchsetzt, hat es den Verbreitungsgrad unter den Leuten, die es bezahlen können.

mfg. Winfried

Hallo Gerhard,

Gerhard Hoffmann schrieb:

beim von mir erwähnten L-Filter wird aber die Phase von den konjugiert komplexen Nullstellen auf der imaginären Achse _nirgends_ gedreht, auch nicht im Sperrbereich. Bei Cauer übrigens auch nicht, das Nennerpolynom erzeugt die schlechte Gruppenlaufzeit.

Früher gab es Leute, die konnten improvisieren und sich fehlende Schaltungen selbst eben zusammenbasteln. Das ist vorbei, heute wird nur noch gekauft. Natürlich hat das auch damit zu tun, daß alles zu komplex geworden ist. Bei mir passiert es außerdem häufig, daß mit dem Drücken des Knöpfchens der Rechner crasht.

Bei uns läuft das auch so ähnlich, der VHDL-Code wird mit Matlab vom System Generator von Xilinx automatisch erzeugt. Wie optimal der ist kann ich schlecht beurteilen, weil keiner da ist, der VHDL wirklich beherrscht und die Zeit hat, solche Unmengen zu programmieren. Allerdings hat mich mal gewundert, was der aus einem einfachen QAM16 Coder gemacht hat, da waren von Hand nur einige Leitungen und 1 Inverter nötig, der VHDL code sah aber vor der Implementierung wie ein riesiges Knäuel von Gattern und Leitungen aus.

Was VHDL-Compiler betrifft, so war ich hier mal in eine Diskussion verwickelt. Auch wenn ich nicht aus der Einarbeitungsphase herausgekommen bin, so stieß ich doch sofort auf Probleme, die mich entweder an der Qualität des Compilers zweifeln ließen oder vielleicht sogar grundsätzlich Schwächen von VHDL aufzeigten.

Aber C bringt doch da keine Vorteile? Mit GNU Fortran bekommst Du solche Programme kostenlos auf jeder Plattform zum laufen. Zu kleine Arrays sind auch kein Problem, nur bei dynamischen Variablen hat Fortran77 Nachteile gegenüber C, da müßte man dann evtl. noch ein malloc() machen. Ich habe auch schon mal einen Fortran nach C-Converter benutzt, das geht, wird aber unlesbar.

abgreifen.

Ja die braucht man alle gleichzeitig, solche Programmsysteme kann man auch nicht mehr selber machen.

Filterdesign-Programm

Habe mir den Link mal gespeichert, danke. Wir selbst haben ja Matlab dafür, aber vielleicht interessiert sich jemand dafür.

mfg. Winfried

"Florian Stock" schrieb:

??? *** Sind es doch nicht, ist doch grad der Witz! ***

Wenn man die Multiplikationsroutine z.B. 255*1 rechnen lässt wird die Schleife nicht ein einziges Mal vollständig durchlaufen, es springt sofort mit dem Ergebnis (das ja schon vorliegt mit der Eingabe) zurück.

Was aber fast überall implementiert ist, rödelt seine Schleifen tapfer ab bis zum erbrechen.

Grund: Vorher steht das Ergebnis nicht stellenrichtig in den Registern, man kann also nicht vorher abbrechen auch wenn nur noch Nullen zu addieren sind!

Ja, aber das frisst ROM den ein Controller nicht hat. Dieses unroll in der AN617 ist mehr als unglücklich, es ist in der Praxis für kleine Controller fast sinnlos.

Nicht nur fast. Die 32x32bit unsigned würde aufgerollt 5376 bytes ROM benötigen, also fünf bis zehnmal mehr als ein typischer 16Cxx überhaupt hat. (Was haben die sich bei microchip da bloss wieder gedacht --- vermutlich gar nix :}

Das ganze Makrogedöns aus der AN617 ist Quark, ich habe mir meine eigenen FX- und FP-Routinen geschrieben, aber war ja nur ein Beispiel.

Erst sagst du, Schleife entrollen wär schneller und jetzt isses doch "fast nie so, bei worst case Betrachtung vermutlich nie so". Was denn nun?

Aber egal, vergiss die entrollte Schleife. Die ist in der Praxis sowieso absolut unnütz hier.

Also: jetzt mal die Multiplikationsroutine 'indisch' ruckizucki aus dem Ärmel, drum' vielleicht auch noch nicht ganz wasserdicht, aber sinngemäß:

a: 64bit Register ; die linke Hand :) b: 32bit Register ; die rechte Hand :) temp: 32 bit Register

beide Argumente liegen in 32 bit in a und b mundgerecht vor dem Aufruf rum bzw. vor.

begin temp := 0 if a 64 bit unsigned fixed point multiply