Forum: Digitale Signalverarbeitung / DSP / Machine Learning Welches LFSR für Weisses Rauschen?


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Markus W. (elektrowagi78) Benutzerseite


Lesenswert?

Ich möchte mit einem solchen Register ein möglichst gutes weisses 
Rauschen erzeugen. Bei der Durchsicht der einschlägigen Dokumente (WP, 
XI, ED) sowie etlicher universitärer Schriften findet sich immer das 
Postulat, dass mit eben jenen LFSR ein weisses Rauschen zu erzeugen sei, 
allerdings fehlt überall der Beleg oder formelle Beweis. Ich hätte mir 
einen Screenshot eines Spektrum Analyzers gewünscht, denn es kann kaum 
sein, dass alle Registerformen und Rückkoppelungen genau Dasselbe 
liefern. Leider ist auch bei offiziellen Publikationen von Instituten 
kaum etwas Genaues zu finden. Die Bandbreite der vorgestellten 
Schaltungsvarianten reicht vom 5BIT- über ein 32er mit gold code für AES 
bis hin zu einem 168er für Sateliten-Rauschsignal-Codierung.

Ich nehme an, dass längere Shift-Register mit mehr Rückkopplungen ein 
besseres Resultat liefern, kann das aber auch nicht mathematisch 
belegen, daher habe ich begonnen, mit einigen zu experimentieren, finde 
aber alles andere, als ein glattes weisses Rauschen. Es gibt fast immer 
starke einzelne peeks im Spektrum, je nachdem, wie man das Bit 
auswertet. Da scheint es auch unterschiedliche Ansätze zu geben: Ich 
habe es bisher einfach selbst als Ausgang genommen, benutze also das 
digitale Signal in Vollaussteuerung und bekomme von einem SR ein Signal 
mit der maximalen Bandbreite i.A. der eingespeisten HF-Taktfrequenz. Nun 
gibt es aber auch Implementierungen, welche mehrere solcher LFSR 
parallel benutzen, um gleich mehrere Bits in time zu erzeugen, welche 
dann zusammengefügt, ein z.B. 8 Bit Rauschen ergeben.

Welches wäre der ideale Weg, um ein möglichst breitbandiges Rauschen zu 
erzeugen, welches ich dann anschließend filtern kann?

Die Bandbreite sollte mindestens 10MHz haben und optimalerweise bis nach 
0 herunterreichen. Als Taktgenerator steht ein 10MHz-Frequenznormal zur 
Verfügung. Da ein FPGA eingesetzt werden darf, wäre auch eine PLL 
machbar, mit der ein 300MHz-System laufen könnte. Mehrere LFSR sind 
ebenfalls kein Problem. Wir haben Platz ohne Ende, brauchen nur eine 
brauchbare Lösung. Als Filter wären sowohl digitale Filter, als auch 
Quarzfilter in Analogtechnik oder eben beides zulässig.

Beitrag #6677551 wurde von einem Moderator gelöscht.
von ... (Gast)


Lesenswert?

Vergiss LFSR.

Nimm ein Verfahren, dass die Maechtigkeit* des reellen Zahlenraums 
nutzt.
Das Suchwort zum Testen: "diehard".



*) das ist eine zahlentheoritische Definition

von Ingo W. (uebrig) Benutzerseite


Lesenswert?

Markus W. schrieb:
> Ich nehme an, dass längere Shift-Register mit mehr Rückkopplungen ein
> besseres Resultat liefern, kann das aber auch nicht mathematisch
> belegen, daher habe ich begonnen, mit einigen zu experimentieren, finde
> aber alles andere, als ein glattes weisses Rauschen. Es gibt fast immer
> starke einzelne peeks im Spektrum, je nachdem, wie man das Bit
> auswertet. Da scheint es auch unterschiedliche Ansätze zu geben: Ich
> habe es bisher einfach selbst als Ausgang genommen,

Dafür sollte die Wiederholrate (1/Zykluszeit) weit unter der von dir 
gewünschten, unteren Grenzfrequenz liegen, bedingt also ein langes LFSR.
Was die Lage der Abgriffe angeht, gibt es tatsächlich "schlechte" 
Kombinationen, die nicht den gesamten Wertebereich ausschöpfen. 
Ausgewählte "gute", auch bei sehr langen Registern, findet man in dieser 
AN:
http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
Wenn du das dann mit 300MHz laufen lassen kannst, dann reicht es 
tatsächlich, ein beliebiges Bit abzugreifen und durch einen 10MHz 
Tiefpass zu schicken.

von Sebastian B. (Gast)


Angehängte Dateien:

Lesenswert?

Moin,

ein LFSR liefert ein Kammspektrum, Abstand der Spektrallinien ist 
1/Periodendauer. Mit einer sehr langen Sequenz bekommt man die 
Spektrallinien nah zusammen.

Außerdem fällt das Spektrum zur Abtastrate hin ab. Wenn man die 
Abtastrate deutlich höher wählt, als für die gewünscht Bandbreite 
erforderlich, bekommt man ein recht flaches Spektrum - aber das wurde 
weiter oben schon angesprochen.

Sebastian

von Frequenztheoretiker (Gast)


Lesenswert?

Den Kammfilter habe ich auch noch in Erinnerung und soweit mein 
Verständnis dafür reicht, würde ich annehmen, dass man mehrere solcher 
Generatoren analog mischen (addieren!) können sollte. Sofern abweichende 
Generatorfrequenzen benutzt werden (300, 290, ...) , müssten sich die 
resultierenden Frequenzen in den Bändern verdichten.

von IQ130+ (Gast)


Lesenswert?

Markus W. schrieb:
> Ich möchte mit einem solchen Register ein möglichst gutes weisses
> Rauschen erzeugen. Bei der Durchsicht der einschlägigen Dokumente (WP,
> XI, ED) sowie etlicher universitärer Schriften findet sich immer das
> Postulat, dass mit eben jenen LFSR ein weisses Rauschen zu erzeugen sei,
> allerdings fehlt überall der Beleg oder formelle Beweis.

Dan haste weder im Studium aufgepasst (oder eh das Falsche an der 
falschen Hochschule studiert) oder in die falschen Bücher geschaut.
Meine Empfehlung:
ISBN 978-3-322-99220-8

von Dieter H. (kyblord)


Lesenswert?

weißes Rauschen ist über eine konstante spektrale Leistungsdichte 
definiert. Nach einem wichtigen Theorem ist das gerade die 
Fouriertransformierte der Autokorrelationsfunktion. Für weißes Rauschen 
ist die Autokorrelationsfunktion ein Delta-Impuls. Das heißt die 
Zufallszahlen x(t) sind für t!=0 unkorreliert. Das kriegst du hin, wenn 
du stochastisch unabhängige, identisch verteilte Zufallszahlen 
generierst. Da reicht auch eine {0,1}-Verteilung.

von Markus W. (elektrowagi78) Benutzerseite


Lesenswert?

... schrieb:
> Nimm ein Verfahren, dass die Maechtigkeit* des reellen Zahlenraums
> nutzt.

Die Frage wäre, welches. (?

Die DIEHARD Test-Batterie hatte ich auch gefunden. Die wurde sogar hier 
im Forum schon behandelt, nur seltsamerweise ins OT verschoben.
Beitrag "Feststellen wie zufällig Zufallszahlen sind"

Ingo W. schrieb:
> Wenn du das dann mit 300MHz laufen lassen kannst, dann reicht es
> tatsächlich, ein beliebiges Bit abzugreifen und durch einen 10MHz
> Tiefpass zu schicken.
Kann ich. Die Lösung klingt ja schon einmal nicht schlecht.

Sebastian B. schrieb:
> ein LFSR liefert ein Kammspektrum,
Ich nehme an, die Abtastrate in der Grafik liegt bei 3G?

IQ130+ schrieb:
> Dan haste weder im Studium aufgepasst (oder eh das Falsche an der
> falschen Hochschule studiert)
Man kann nicht alles studieren, was einem später als Anforderung über 
den Weg läuft. Aber du kannst wahrscheinlich alles perfekt.

Dieter H. schrieb:
> weißes Rauschen ist über eine konstante spektrale Leistungsdichte
> definiert. Nach einem wichtigen Theorem
Das ist jetzt wieder sehr theoretisch. Habe es trotzdem nachgelesen und 
denke ich auch, verstanden. Nur: Das Wissen um die Verteilung des 
weissen Rauschens (die Definition war mir durchaus geläufig) führt mich 
noch nicht zum idealen LFSR.

von Markus W. (elektrowagi78) Benutzerseite


Lesenswert?

Ich bin aber nun immerhin so weit gediehen, dass ich eine Publikation 
gefunden habe, die aussagt, dass LFSR durchaus den DIEHARD Test von 
Marsaglia überstehen können, wobei es auf die Rückführungen ankommt. 
(wer hätte das gedacht). Einfache LFSR erfüllen die Kriterien nicht.

Leider schweigt sich auch dieses Dokument über ein geeignetes Beispiel 
aus.

Das von oben gelinkte Dokument der Firma Xilinx, welche eine 
Zusammenstellung von Codes bis 168 aufführt (und sich dabei auf Arbeiten 
einer Person aus den 1970er Jahren bezieht) hatte ich bereis eingangs 
mit erwähnt. Die meisten Anordnungen dort arbeiten mit 2-4, maximal 6 
Rückführungen. Über die Qualität wird aber keine Aussage getroffen und 
vom Autor ist auch nichts zu finden.

Ist das ein weißer Fleck?

Ist es das eventuell deshalb, weil es damals noch keine Hardware gab, 
mit der man so rasch und billig Schieben konnte? Die meisten 
PRG-Verfahren, die genannt werden, sind vergleichsweise aufwändige 
Software-Operationen und damit sehr langsam, so intelligent sie auch 
sein mögen.

von Dergute W. (derguteweka)


Lesenswert?

Moin,

Markus W. schrieb:
> Ist es das eventuell deshalb, weil es damals noch keine Hardware gab,
> mit der man so rasch und billig Schieben konnte?

Sicher nicht. Da wurde wahrscheinlich deutlich mehr berechnet und 
weniger ausprobiert (Der LDPC Code, der z.b. in DVB-S2 statt Viterbi 
verwendet wird, ist auch iirc irgendwann in den 1960er Jahren entwickelt 
worden. Gab aber lange keine DSPs, die das mit dem noetigen Speed bei 
wenig Leistung/Kosten rechnen konnten, daher wurde der erst bei DVB-S2 
eingesetzt und nicht bei DVB-S).
Grad' zu den klassischen LFSR muesst's schon ordentlich viel Literatur 
geben. Kann mich noch dran erinnern, dass da mal was dazu in einer 
Regelungstechnikvorlesung an mir vorbeigezogen ist. iirc gab' da auch 
irgendeine Transformation dazu...
Und soo zufaellig sind diese Folgen eben nicht, da kann man (also ich 
grad' natuerlich nicht) ziemlich genau ausrechnen, wie die 
zusammengesetzt sind - also wieviel gleiche bits hintereinander kommen, 
etc. bla.
Was aber nicht bedeuten muss, dass da das Rauschen "schlecht" waere.

Gruss
WK

von Markus W. (elektrowagi78) Benutzerseite


Lesenswert?

Dergute W. schrieb:
> Gab aber lange keine DSPs, die das mit dem noetigen Speed bei
> wenig Leistung/Kosten rechnen konnten,
Exakt das meinte ich.

Dergute W. schrieb:
> Grad' zu den klassischen LFSR muesst's schon ordentlich viel Literatur
> geben.
Dachte ich auch, aber auch da scheitert es an der Rechenleistung, denke 
ich. Das rein mathematisch zu untersuchen, mit z.B. MATLAB, ist sicher 
schwierig, wegen der Datenmengen. Die langen LFSR laufen ja selbst in 
Echtzeit ewig.

Wenn ich mehr Zeit hätte, würde ich mich mal dran machen. Eigentlich 
braucht er nur eine Schleife, die die Länge und Struktur der LFSRs 
umkonfiguriert, eine FFT laufen lässt und die Ergebnisse raustut, bzw 
bewertet.

Ich orientiere mich fürs erste mal an der Xilinx-Tabelle. Wegen der 
Bandbreite wäre die Idee, einfach unterschiedlich lange Ketten parallel 
laufen zu lassen und so gleich mehrere Bits in einem Takt zu bekommen.

Wäre noch die Frage offen, womit man am Besten filtert?

von Dergute W. (derguteweka)


Lesenswert?

Moin,

Markus W. schrieb:
> Dachte ich auch, aber auch da scheitert es an der Rechenleistung, denke
> ich. Das rein mathematisch zu untersuchen, mit z.B. MATLAB, ist sicher
> schwierig, wegen der Datenmengen.

Aeh - das waere nicht rein mathematisch. Rein mathematisch geht z.B. mit 
Karoblock und Bleistift oder Tafel und Kreide. Aber jeweils nur als 
Auslagerungsdatei fuer den menschlichen Hauptprozessor :-)

Hab' grad mal geguckt: Ich hab' da ein Vorlesungsscript Regelungstechnik 
und Systemtheorie II, 4. Auflage 1994 (n. Chr. ;-) ) , Kapitel 4: 
Operatorenrechnung  fuer zeitdiskrete Systeme. Da gehts um Galoiskoerper 
und V-Transformation.
Und da wird als "anschauliche Anwendung" der Operatorenrechnung auf 
Schieberegister und "davon als wichtigster Spezialfall die 
maximalperiodischen Schieberegister" eingegangen.
Das hatte ich im Hinterkopf.
Da wird die Autokorrelation aber nur mal kurz gestreift; auf 
irgendwelche weiteren Rauscheigenschaften wird nicht eingegangen.

Sowas von dem Kaliber, nur vielleicht didaktisch besser aufbereitet, 
meinte ich.

Gruss
WK

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Markus W. schrieb:
> Wäre noch die Frage offen, womit man am Besten filtert?
üblicherweise wird es mit einem CIC dezimiert. Dessen unvollständige 
Oberwellendämpfung wäre zu beachten. Man kann das Signal auch 
runtersampeln /runtergesampelt addieren und so die Spiegelfrequenzen 
nutzen: Dann wird das nach oben abflachende Spektrum um Nyquist herum 
nach unten geklappt und der Gesamtverlauf noch etwas flacher. Des 
weiteren gibt es die Option, sich das Spektum zurechtzubiegen, also mit 
blauem Rauschen (anderer NG + HP) aufzufüttern.

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]
  • [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.

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