Fehlererkennungsverfahren fuer Datenuebertragung

Am 07.08.2012 14:25, schrieb Tobias Baumann:

Es happert etwas bei mir mit deiner Arithmetik. 30 Bits, davon 25 Nutzdaten und nur 2 übrig. Was ist denn mit den übrigen 3? Ansonsten reichen 2 Bits nicht um eindeutig Bitfehler zu erkennen. Ich würde mal versuchen einen CRC zu berechnen, vielleicht CRC-32 (Ethernet), allerdings mit 2 Bits sind da keine Bäume auszureisen. Natürlich kannst du auch die Blöcke 1-14 und 16-29 mit jeweils einem Paritätbit versehen. Besser als nüscht.

Waldemar

--
My jsme Borgové. Sklopte ¨títy a vzdejte se. Odpor je marný.

2 Bit's sind nicht viel. Als ersten Test fände ich schon mal wichtig, dass 0000 und FFFF (Kurzschlüsse oder andere häufig auftretende Fälle) auf jeden Fall als Fehler erkannt werden.

Lies mal hier was dazu, eventuell etwas besser als reine Parity, könnte sogar Fehler korrigieren:

M.

Am 07.08.2012 14:39, schrieb Waldemar Krzok:

Ein Bit benoetige ich als Markierungsbit das jetzt neue Daten kommen (sowas wie ein data enable) und die anderen beiden sind reserviert fuer zukuenftige Anwendungen.

Beim CRC habe ich bedenken das ich das nicht direkt berechnen kann und ich mehrere Zyklen brauche zum berechnen und anschliessend wieder pruefen. Sofern dies der Fall sein sollte scheidet das Verfahren sofort aus.

Matthias Weingart schrieb:

Besser auf jeden Fall, aber deutlich aufwändiger in der Decodierung. Und wenn selbst ein CRC schon zu viel ist...

Gruß Henning

Tobias Baumann schrieb:

Hallo,

und was passiert wenn das Markierungsbit falsch ist?

Mit 2 Prüfbits für 25 Datenbits ist nicht viel möglich, ich wäre mir da nichtmal sicher das Doppelfehler immer erkannt werden können.

Man könnte z.B. die 25 Datenbits in zwei Gruppen zu je 12 und 13 Bit einteilen und für jede Gruppe ein Parity Bit vorsehen. Wenn ein Doppelfehler brav ist und sich schön auf beide Gruppen verteilt kann man ihn auch als Doppelfehler erkennen, sind beide Fehler in einer Gruppe wird kein Fehler erkannt.

Bye

Am 07.08.2012 15:48, schrieb Tobias Baumann:

CRC ist streamfähig. Es wird lediglich ein speicherregister benötigt. Eine Initialisierungfunktion, eine Funktion die ein byte durchschleust, eine Funktion die das Ergebnis liefert. Üblich sind CRC-16 und CRC-32

Es gibt hunderte Implementierungen der verschiedensten Arten und Programmiersprachen.

Bernd

Bernd Laengerich :

Ja, neben logischen Operationen (XOR) braucht eine CRC noch ein paar (logische) Shift-Befehle. Eigentlich nicht sehr aufwendig. Ist eben nur ne Frage, ob man eine vernünftige CRC2 gebastelt bekommt. Man könnte sich mal ansehen, ob es ausreicht, nur zwei Bits einer CRC8 zu verwenden.

M.

Am 07.08.2012 16:43, schrieb Matthias Weingart:

Ist ein bisschen dünn. Ich wollte auch eher die Bedenken mit mehreren Passes und ggf. "großer" buffer dafür zerstreuen. CRC-2 könnte aber immerhin besser als reine Paritätsbits sein.

Bernd

Nein.

Die Anzahl möglicher Generatorpolynome für CRC2 ist doch wohl äußerst überschaubar. Man sieht sofort, daß keins davon besser sein kann, als einfach zwei Paritäten (nix anderes als CRC1) über jeweils die Hälfte der Nutzbits zu bilden.

BTW: Der Trick besteht dann in der guten Wahl der Bits für die beiden Hälften. Man sollte idealerweise die Art der zu erwartenden Störungen kennen, bevor man das entscheidet.

Kennt man sie nicht, trifft (wenig überraschend) der reine Zufall die beste Wahl für das im Schnitt aller möglichen Störungen beste Ergebnis.

Tobias Baumann schrieb:

Wichtige Grundlage zur Wahl einer geeigneten Methode ist die Hamming-Distanz [1]. Bei nur zwei Bit Redundanz wird dir eine CRC [2] mangels geeignetem Generatorpolynom nicht viel nützen, je nach Art der zu erwartenden Störungen ist es sinnvoll, einfach zwei getrennte Parity-Werte über zwei Blöcke zu bilden, oder eine kompliziertere Berechnung der Redundanzbits einzuplanen.

Die Anforderung, keine zusätzlichen Takte für die Berechnung und Prüfung der Redundanzinformationen zu erfordern, erfüllen Parity wie CRC, beide lassen sich Bit für Bit aus einem gespeicherten Statuswert und dem aktuellen Datenbit bestimmen.

Die von Matthias genannte Eigenschaft, sowohl den Zustand 'alles 1' als auch 'alles 0' als fehlerhaft zu erkennen, sollte vom gewählten Verfahren auf alle Fälle geleistet werden, alles andere führt die 'Datensicherung' ad absurdum.

Es wird wohl auf Parity hinauslaufen, eventuell kannst du auch noch eins der beiden Bits als 'for future use' freigeben.

Du solltest die Bitfehlerrate deiner Übertragung in die Überlegungen einbeziehen. Befinden sich beide FPGAs auf der gleichen Platine? Warum sollte dann die Datenübertragung unzuverlässiger als die Übertragung eines Datenwortes vom Speicher in eine CPU bei einem normalen PC sein? Falls sie es ist, sollte an den elektrischen Eigenschaften der Übertragung optimiert werden, nicht an dem Fehlererkennungsverfahren. Oder befindet sich eine mehrere Kilometer lange Leitung zwischen den FPGAs? Als Vergleichswert: ISDN-S0-Leitungen haben eine Bitfehlerrate von 1E-10 und dürfen bis 1000m lang sein.

P.

[1] [2]

Am 07.08.2012 14:25, schrieb Tobias Baumann:

Klingt etwas seltsam. Aus deinen Angaben geht auch nicht hervor, wieviel Aufwand denn nun akzeptabel wäre und wie dein Datenformat aussieht.

Mir fällt dazu aber nur mal folgendes ein:

Aus 25 Bit Nutzdaten macht man 4 Worte á 7 Bit + Parity, macht 4 Bytes. Das letzte Byte wird nur teilweise ausgenutzt, aber egal.

Die 4 Bytes werden asynchron übertragen, d.h. 1 Startbit, 7 Datenbits + Parity + 1 Stopbit = 10 Bit

Macht also bis dahin 40 Bit. Das Format kann aber direkt von einem uart oder einem entsprechenden Algorithmus ausgewertet werden. Ich weiss jetzt nicht, wie man das in einem FPGA macht.

Dann kann man noch eine Checksumme bilden, z.B. als einfache Nullsumme und als zusätzliches Byte übertragen. Macht dann 5 Bytes.

Idealerweise hat man noch ein festes Startzeichen, um den Blockanfang zu erkennen.

Aber wie schon geschrieben: mit FPGA kenne ich mich nicht aus, aber so wie beschrieben würde ich es in einem Microcontroller machen.

Gruß

Stefan

Am 08.08.2012 02:05, schrieb Peter Schneider:

Im Moment hab ich diese Variante auch implementiert, einfach um mal vorwaerts zu kommen. Sollte sich was besseres ergeben dann kann ich das ja ohne grossen Aufwand umschreiben und ein neues Bitfile erstellen.

Ein Vorteil was die Paritaetspruefung hat (was mir auch erst gestern aufgefallen ist), ist das ich sehr gut pruefen kann ob 'alles 0' oder 'alles 1' ist. Wenn ich einen geraden und ungerade langen Bitblock nehme dann muessten falls alle Nutzdaten 1 sein sollten, eine der beiden Paritaeten 1 und die andere 0 sein. Sollte nur Einsen bekommen so weiss ich das was faul ist (genauso wie nur 0en).

Die FPGAs befinden sich auf unterschiedlichen Platinen in einem VME Crate. Darauf befindet sich ein sternfoermiger VXS-Bus welcher in der Mitte einen FPGA hat der Informationen von 12 weiteren Boards mit je einem FPGA erhaelt.

Vielen Dank fuer die Links, auf den zweiten bin ich jetzt schon oefters gestossen, aber von dem ersten habe ich noch nie was gehoert. Werde mir das mal in Ruhe durchlesen.

Tobias

Am 07.08.2012 22:30, schrieb Heiko Nocon:

Diesen Weg habe ich jetzt momentan implementiert, damit ich mein Design mal fertigstellen kann (hinterher aendern kann mans ja immer noch).

Die Art der Stoerung kenn ich noch nicht, dazu weren noch Messungen folgend. Ich kann nur die Groessenordnung abschaetzen, wie oft ein Fehler Auftritt.

Dabei ergeben sich auch verschiedene Erkenntnisse. Wenn ich mit einer Rate von 5 MHz meine 30 Bit Datenpakete sende (immer gleiches Paketmuster), dann erhalte ich praktisch nie ein fehlerhaftes Paket (Fehlerrate ca. 10^-9). Wenn ich kontinuierlich Pakete senden mit Pseudo-Randoms dann steigt meine Fehlerrate auf 10^-6.

Bei meinen naechsten Tests werd ich mal auf die fehlerhaften Pakete Triggern und anschauen was so die typischen Fehler sind.

Auf alle Faelle werde ich jetzt wohl die CRC-2 Methode verwerfen da sie mir keine Vorteile bringt.

Vielen Dank,

Tobias

Du solltest zumindest irgendwas in jedem Test-Telegramm ändern und sei es nur ein vorangestellter oder enthaltener Telegrammzähler, sonst kannst Du nicht sehen, ob eines komplett verschlabbert wird oder doppelt kommt...

Woran erkennst Du fehlerhafte Pakete? Verstümmelt/verändert oder ganz wech (timeout)?

Saludos (an alle Vernünftigen, Rest sh. sig) Wolfgang

--
Wolfgang Allinger, anerkannter Trollallergiker :) reply Adresse gesetzt!
Ich diskutiere zukünftig weniger mit Idioten, denn sie ziehen mich auf
ihr Niveau herunter und schlagen mich dort mit ihrer Erfahrung! :p
(lt. alter usenet Weisheit)

Am 09.08.2012 13:34, schrieb Wolfgang Allinger:

Bei meinem Test-Telegram habe ich ein 10 Bit Testwort erstellt in dem ich eine alternierende 0-1en Folge habe also 1010101010, dann ein Wort mit hoher 1en Dichte 1111011111 und eins mit hohen 0en Dichte

0000100000. Damit wollte ich pruefen ob meine Hardware mit der verwendeten Frequenz von 500 MHz (DDR Uebertragung) klarkommt und meine Bits richtig gesamplet werden.

Bei dem Test mit den Pseudo-Random-Numbers schicke ich dementsprechend

3mal 10 Bit PRNs.

Also ich pruefe ob mein Paket dem entspricht was ich erwarte, ist dies nicht der Fall dann zaehlt ein Error Counter hoch. Bei PRNs kann ich in der Empfangsseite mein zu erartender Wert berechnen und vergleiche diesen.

Timeouts habe ich bei dem System garkeine, weil ich Daten nur gestreamt sende. Es gibt kein Handshaking (ist fuer unsere Anwendung unbrauchbar).

Viele Gruesse, Tobias

Aus deinen bisherigen Beobachtungen würde ich mal die These generieren, daß die Fehlerquote sehr wahrscheinlich in irgendeiner Art von der Zahl aufeinanderfolgender gleicher Bits in den gesendeten Paketen abhängt.

Deswegen kannst das auch andersrum machen und diese typische Eigenschaft der gesendeten Pakete ändern, das ist wahrscheinlich viel schneller und einfacher zu erledigen als die Erkennung und manuelle Analyse fehlerhaft empfangenen Random-Pakete. Je nach Pegel deines Startbits jeweils eine Versuchsreihe mit folgenden

5 Paketwerten durchlaufen lassen:

SB: 1 0 PW: $aaaaaaaa $55555555 $cccccccc $33333333 $f0f0f0f0 $0f0f0f0f $ff00ff00 $00ff00ff $ffff0000 $0000ffff

Ich wage mal die Prophezeiung, daß es entweder einen durchgängigen Trend in den Fehlerquoten der fünf Pakete geben wird (und dann wird das erste Paket wahrscheinlich das mit der höchsten Fehlerquote sein) oder alternativ einen deutlichen Pik irgendwo in der Mitte.

Ich bin gespannt auf die Ergebnisse. Falls meine Prophezeiung zutrifft, wirst du überrascht sein, wenn ich dir die Konsequenzen aus der Beobachtung erkläre...

Und falls nicht, bin ich zwar erstmal ratlos, aber du kannst ja dann immer noch die fehlerhaft empfangenen Pakete manuell analysieren.

Am 09.08.2012 19:21, schrieb Heiko Nocon:

du überrascht sein, wenn ich dir die Konsequenzen aus der Beobachtung erkläre... Darauf bin auch auch mal gespannt, auch wenn (oder gerade weil) :-) ich das hier nur so "diagonal" mitlese. Lass mich mal raten: Wenn deine Prophezeihung zutrifft, brauchst du Tobias die Konsequenzen gar nicht mehr zu erklären, oder? :-)

Am 09.08.2012 19:21, schrieb Heiko Nocon:

Vielen Dank fuer den Tipp, werde es spaeter noch versuchen.

Damit ich das richtig verstanden habe:

- Erste Versuchsreihe mit SB (= Startbit, oder?) 1 und dem Paket $aaaaaaaa.

- Zweite Versuchsreihe mit SB 1 und Paket $cccccccc

- usw.

Dann die gleiche Prozedure mit SB 0 und Paket $55555555, $33333333, usw.

Bin gespannt was rauskommt und auf deine Erklaerung!

Vielen Dank und Gruesse, Tobias

Genau.

Nein, das war nur als Alternative gedacht, weil ich nicht wusste, welchen Pegel du für dein Startbit verwendest. Eine der beiden Reihen genügt völlig zum Testen. Du wählst halt einfach die, die zu dem schon implementierten Startbit paßt.

Übrigens geht die Tabelle davon aus, daß das höchstwertige Bit des 32Bit-Worts dein Startbit ist, also zuerst gesendet wird, falls das nicht der Fall ist, dreht sich die Zuordnung der Paketwerte zum Pegel des Startbits natürlich um. D.h. bei Beginn mit LSB und SB=1 mußt du logischerweise die Reihe mit $55555555, $33333333 usw. verwenden.