mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik LSFR was ist das überhaupt?


Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,
ich habe eine knifflige Aufgabe bekommen und bin mir noch nicht so ganz 
sicher ob und wie das geht.
Es geht darum, das ich über den UART eines AT90CAN128 einen String oder 
eine Bitfolge schicke, die ich an einem anderen Controller des selben 
Typs wieder empfangen soll. Dieser Contoller soll die Bittfolge nun 
einer LSFR (Was immer das auch ist) unterziehen und wieder an den Sender 
zurückschicken. Dieser soll nun die Bitfehler über die Zeit ermitteln.
Weiß von euch jemand was eine LSFR ist? Ist das ein bestimmtes Register 
oder ein Algorithmus?
Wie kann ich in meinem Fall sowas am besten implimentieren? Das senden 
und empfangen der beiden UARTS geht schon, die Bitfehlerermittlung noch 
nicht.....
Gibts da irgendwo C Code?

Danke schon mal

Autor: rene (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das sind Linear Feedback Shift Register. Sie werden zur Erzeugung von 
Pseudozufallssequenzen benutzt. Siehe auch
http://www.ibrtses.com/simulations/lfsr.html

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ rene (Gast)

>Das sind Linear Feedback Shift Register. Sie werden zur Erzeugung von
>Pseudozufallssequenzen benutzt. Siehe auch
>http://www.ibrtses.com/simulations/lfsr.html

Der OP schrieb aber LSFR und nicht LFSR. Wechsstaben verbuchselt? ;-)

MFG
Falk

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sry...
LFSR ist schon richtig.
Besitzt mein AT90CAN128 ein solches Register?
Kann ich mit diesem Contoller soetwas überhaupt machen?

Autor: rene (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man kann die Funktion einfach mit Software nachbilden. Je nach Zweck 
nimmt man Laengere oder Kuerzere. Hier denk ich sollten 16bit genuegen.

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Rene,

ja ich denke 16Bit sind ausreichend für meine Zwecke.
Ich hab jetzt mal ein bisschen Gegoogled aber ich versteh noch nicht 
ganz wie das ganze funktionieren soll.
Beispiel:
Ich nehme die Zahl 0x15 und sende sie auf den UART. Der andere Contoller 
empfängt die Zahl und lässt die LFSR Funktion darüber laufen. Das 
Ergebiss sendet er wie der an den Sender zurück. In der zwischenzeit hat 
der Sender das selbe mit der 0x15 gemacht und vergleicht nun das 
empfangene mit dem selber berechneten. Hieraus lässt sich nun die 
Bitfehlerwahrscheinlichkeit bestimmen?? Hab ich das richtig verstanden? 
:-)

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hat irgendwer eine C Funktion auf Lager, mit der ich eine solche LFSR 
softwaremäßig realisieren kann?
Wäre mir ne rießen Hilfe...

Autor: 1313 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das mit der Bitfehlerwahrscheinlichkeit. Ein LFSR ist ein funktion, die 
Eine lange Folgen von bits erzeugt, die man kennt. Ich hab den 
gelisteten Ansatz nicht gekannt, und auch nicht verstanden. Daher 
koennen beide seiten die LFSR laufen lassen, und vergleichen mit dem was 
kommt. Dan muss man 2 Dinge Zaehlen, alle Bits und die Falschen bits. 
Der Quotient ist die Fehlerrate

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also könnte ich mit einer LFSR die Bitfehlerwahrscheinlichkeit meiner 
Übertragungsstrecke bestimmen?
Wie muss eine solche Funktion aussehen? Hat jemand Code dazu??

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

Bewertung
0 lesenswert
nicht lesenswert

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Christoph, hast Du mit einem LSFR schonmal etwas gemacht?
Wie muss eine solche Schiebefkt in C aussehen?

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

Bewertung
0 lesenswert
nicht lesenswert
noch ein Suchbegriff, nicht Ernie sondern BERT
http://en.wikipedia.org/wiki/BERT

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mhh da die BERT`s wohl nicht mit LSFR's gemacht werden ist ein LSFR auch 
nicht die richtige Lösung zu meiner Übertragunsanalyse, sehe ich das 
richtig?

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
LFSR kann man auch als Pseudo Zufalls Generator betrachten, und mit 
sowas kann man BERT machen. Wenn du jetzt noch für dein LFSR die 
richtigen Polynome und Seeds auswählst entsteht eine MLS -> 
http://de.wikipedia.org/wiki/Maximum_Length_Sequence

Und wenn du dir das mal durchliest so erkennst du das statistisch 
betrachtet eine solche MLS alle machbaren Bitkombinationen im Bitstrom 
enthält, also ideal als Generator für BERT. Er simuliert also sehr gut 
die auftretenden Wahrscheinlichkeiten an Bitkombinationen die später bei 
deiner Kommunikation auftreten könnten. Ein LFSR mit 8Bit oder 16Bit 
wäre eine gute Wahl.

Gruß Hagen

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hey voll gut das sich immer einer von euch auskennt :-) Danke Hagen.
Wo bekomme ich jetzt am besten eine C Funktion her, die mir eine solche 
LFSR mit 8 oder 16 Bit macht? Habe selber keine Ahnung, wie ich da am 
besten beim programmieren vorgehen würde...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Beginner wrote:
> Hey voll gut das sich immer einer von euch auskennt :-) Danke Hagen.
> Wo bekomme ich jetzt am besten eine C Funktion her, die mir eine solche
> LFSR mit 8 oder 16 Bit macht? Habe selber keine Ahnung, wie ich da am
> besten beim programmieren vorgehen würde...

Das das immer wieder soooooooo wahnsinnig schwer ist.

Du gibst in http://www.google.com die Suchbegriffe "LFSR C" ein
und findest ein paar Links in denen jemand Code veröffentlicht
hat.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Programmieren ist viel zu früh bei deinem Wissensstand. Als erstes mal 
musst du lernen was LFSRs sind, und wie man sie "berechnet". Denn die 
richtige Wahl und das korrekte Berechnen von nicht reduzierbaren 
Polynomen für die LFSRs steht auch noch auf dem Stundenplan. Ohne solche 
Polynome bekommst du nämlich keine MLS und somit nicht die statistischen 
Eigenschaften der LFSRs die du benötigst. Um solche Polynome zu 
berechnen benötigst du Berechnungen im Galois Field zur Basis 2. Dann 
musst du auch in der Lage sein solche GFs zu faktorisieren. Je nach 
Größe des LFSRs entsteht dann ein Testbitstrom den du komplett 
durchlaufen lassen musst. EIn 8 Bit LFSR als MLS erzeugt also einen 
2^8-1 Bit langen Datenstrom den du über die Leitung schicken musst.

Wenn alles bei dir richtig läuft wirst du bei den möglichen Polynomen 
für 8 Bit LFSRs feststellen das es exakt nur 16 solcher Polynome gibt, 
bzw. 8 und diese als invertierte Kopien nochmal 8 Stück. Bei 12 Bit 
LFSRs gibt es nur 144 solcher Polynome.

Gruß Hagen

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok,
nun mal angenommen ich erzeuge mit einem 8 Bit LSFR Schieberegister und 
einem Polynom eine folge von Zufallszahlen.
Wie kann ich dann am besten meine Übertragungsstrecke testen?
Wenn ich die Zahlen einfach über den UART und den Transceiver schicke, 
weiß ich auf der Empfängerseite ja nicht was ich gesendet habe, ob es 
nun die richgige Zahl ist oder die falsche?
Wie mach ich das am besten? Muss der Empfänger die selben Zahlen 
erzeugen und dann immer mit den empfangenen vergleichen?
Wie berechne ich nun meine Bitfehlerwahrscheinlichkeit?

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es sind deterministische Funktionen, wie bei Wikipedia schon 
geschrieben. Dh. sie sind zu jeder Zeit nach- bzw. sogar 
vorausberechenbar, und das immer wieder.

Was würde passieren wenn zwei Computer nun zum gleichen Zeitpunkt 
unabhängig voneinander das gleiche LFSR benutzen und damit einen 
Bitstrom erzeugen ?

Ja, die beiden Bitströme auf Sender und Empfänger Seite wären dann 
synchron.

Bitfehlerwahrscheinlichkeit: Du zählst die falsch empfangenen Bits und 
diese Anzahl geteilt durch die maximale Länge der MLS (LFSRs) ergibt 
deinen Gesamtfehler. Die Bitfehlerwahrscheinlichkeit ist im Grunde wohl 
ein falscher Ausdruck, auf ein Bit bezogen ist sie nämlich immer 50% aus 
math. Sicht.

Gruß Hagen

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Beginner wrote:
> Ok,
> nun mal angenommen ich erzeuge mit einem 8 Bit LSFR Schieberegister und
> einem Polynom eine folge von Zufallszahlen.
> Wie kann ich dann am besten meine Übertragungsstrecke testen?
> Wenn ich die Zahlen einfach über den UART und den Transceiver schicke,
> weiß ich auf der Empfängerseite ja nicht was ich gesendet habe, ob es
> nun die richgige Zahl ist oder die falsche?

Genau.
Was folgt jetzt daraus?

Es werden wohl beide Seiten die gleichen Berechnungen anstellen
muessen. Die Ergebnisse der Berechnungen werden ausgetauscht
und mit der jeweils eigenen verglichen. Wenn es keinen Fehler
auf der Übertragunsstrecke gab, dann muessen diese identisch
sein. Sind sie es nicht, dann gab es daher einen Fehler.

> Wie berechne ich nun meine Bitfehlerwahrscheinlichkeit?

Indem du die Anzahl der fehlerhaft übertragenen Bits in
Relation zu den insgesamt übertragenen Bits setzt. Wenn du
100 Bits übertragen hast und davon waren 5 fehlerhaft, wie
groß ist dann der Prozentuale Anteil? Frag jetzt aber bitte
nicht nach, wie man einen Prozentwert ausrechnet :-)

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sorry der Nachfrage,

es programmiert eben nicht jeder schon seit 20 Jahren Mikrocontroller in 
C....

Vielen Dank an euch alle, ich denke das müsste ich jetzt in den Griff 
bekommen, hab jedenfalls ziemlich viel dazu gelernt.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Beginner wrote:
> Sorry der Nachfrage,
>
> es programmiert eben nicht jeder schon seit 20 Jahren Mikrocontroller in
> C....

Das hat nichts mit C oder programmieren zu tun sondern mit nachdenken.
Die Antwort wäre diesselbe, wenn 2 deiner Kumpels als Endstellen
fungieren und die zu testende Strecke eine Telephonverbindung
wäre.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn nur der Sender per LFSR seinen Bitstrom erzeugt dann müsste der 
Empfänger einfach nur ein Echo machen. Also alles was er empfängt sendet 
er direkt zurück. Da die gleiche Sequenz an Bits nun zweimal übertragen 
wird musst du deine berechnete Fehlerrate natürlich anpassen ;)

Gruß Hagen

Autor: 1323 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Link von Rene enthaelt die Xilinx Application Notes, die die 
Polynome fuer die Maximum Length Shift Register beschreibt. Die Polynome 
kann man ja nun programmieren. Sollt aufgrund des Schaltbildes nicht 
allzu schwierig sein.

Autor: 1323 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn der Empfaenger nur ein Echo macht, kann man die Fehler der beiden 
Richtungen nicht mehr getrennt erfassen. Muss man das denn ueberhaupt ? 
Wenn nur 2m Kabel dazwischen sind macht das wenig Sinn. Wenn eine 
Funkstrecke, oder ein Internet dazwischen ist moeglichrweise schon.

Autor: Beginner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sind so 20 Meter Kabel dazwischen, bzw. werde ich testen, wieviel Kabel 
ich daziwschen hängen kann, bevor nur noch Müll ankommt..

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Wenn der Empfaenger nur ein Echo macht, kann man die Fehler der beiden
>Richtungen nicht mehr getrennt erfassen. Muss man das denn ueberhaupt ?

Das ist eben die Frage. Ich denke das ein Echo ausreicht wenn man ein 
Kabel austesten möchte. Die Fehlerrate für eine Datebrichtung ist halt 
dann die Hälfte der gemessenen Fehlerrate für beide Datenrichtungen.

Bei einem Kabel wäre das rechnerisch gesehen dann egal, da beide 
Richtungen über das selbe Kabel gehen. Falls aber 2 Kabel, jeweils für 
eine Datenrichtung ein eigenes mit unterschiedlichen Eigenschaften 
benutzt werden dann ändert sich der Sachverhalt.

Ich denke aber das der Lehrmeister (oder wer auch immer) es nicht noch 
komplizierter machen will als notwendig. Die Aufgabe soll es wohl sein 
sich mit LFSRs auseinander zu setzen, und das halte ich für eine gute 
Aufgabe.
Das AHA-Erlebnis bei Beginner wird nämlich sein das er sich stundenlang 
mit komplizierter Theorie über LFSRs, Polynomartihmetik in GF(2) usw. 
beschäftigt hat und am Ende einen 5 Zeiler als Source vorsich sieht ;)

Gruß Hagen

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.