Faltungscode decodieren nach Viterbi Algorithmus

  • VB.NET

Es gibt 12 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Faltungscode decodieren nach Viterbi Algorithmus

    Hi an die vb paradise community,

    ich hoffe jemand hat hier eine Idee wie ich mein Thema in einen Code umwandeln kann.

    kurz zur Erläuterung was ich brauche...

    In eine TextBox wird die Empfangsfolge z.b. 1001100111 eingegeben.

    es soll durch den Viterbi Algorithmus die mit größter Wahrscheinlichkeit gesendete Folge ermittelt werden und die richtige Folge in eine RichTextBox ausgegeben werden inklusive aller möglichen Folgen (längerer Weg).


    am besten erkennt man die Schritte anhand des Trellisdiagramm was ich euch mal zu Veranschaulichung abfotografiert habe...


    ...siehe Anhang...


    wie in Beispiel 3 zu sehen ist der Startpunkt bei Punkt D = 11, von dort aus geht man mit 10 zu C oder mit 01 zu D.
    Der Weg D -> C ergibt im Vergleich 10 zu 10 = 0 Fehler und der Weg D -> D ergibt 10 zu 01 = 2 Fehler

    man geht so von Punkt zu Punkt bis Taktschritt 5 bzw. zum Ende und erhält für jeden mögliche Folge eine Fehleranzahl (akkumulierte Hamming Distanz)

    die Folge mit den geringsten Fehlern soll als wahrscheinlich gesendete Folge ausgegeben werden, in diesem Fall wäre es die Folge 10 01 00 01 11 mit 1 Fehler.


    was ich also brauche ist eine Möglichkeit diese Abfolge in meinem Programm durchlaufen zu lassen, sodass die Empfangsfolge mit den einzelnen Schritten überprüft wird und die Anzahl der Fehler und der gegangene Pfad gespeichert wird (array?)

    wie ich den Empfangscode einlese habe ich schon...


    VB.NET-Quellcode

    1. codewort = TextBox1.Text
    2. codelaenge = TextBox1.Text.Length
    4. Dim codearray(codelaenge - 1) As Byte
    6. For i As Byte = 0 To codelaenge - 1
    7. codearray(i) = codewort.Substring(i, 1)
    8. Next



    es fehlt mir "nur" noch diese Abfrage.

    Die Ausgabe in die RichTextBox sollte am Ende nicht das Problem sein, da ich dafür schon ein paar fertige Syntax geschrieben/benutzt habe.


    ich danke schon mal allen die mir helfen können/wollen...
    Bilder

    • folie1.png

      948,37 kB, 1.089×597, 170 mal angesehen

    • folie2.png

      635,3 kB, 1.068×384, 149 mal angesehen

    • folie3.png

      710,92 kB, 800×543, 159 mal angesehen

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „TDCroPower“ ()

    Willkommen im Forum. :thumbup:
    Kannst Du bitte Deine Bilder auf einem werbungsfreien Server laden, z.B. vb-paradise.de? ==> Dateianhänge
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    OK.
    Willst Du einen vorhandenen Algorithmus in Code gegossen bekommen? Das wäre nicht die feine englische Art, denn wenn Du hier einen fertigen Algorithmus abgreifst und in der Schule / im Seminar einen einser bekommst, es aber nicht selbst gemachgt hast.
    Was ist nun eigentlich Dein Problem?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    hehe um eine eins im schule/seminar geht es mir nicht ;)


    es muss ja kein fertiger Code sein, sondern könnte mir ein schups in die richtige Richtung schon viel weiterhelfen. Vielleicht kenne ich eine Funktion etc bei Visual Basic nicht die mir dabei hilft...


    das vergleichen 2er Codes also 10 mit 01 etc. ist für mich auf Codebasis nicht das Problem... habe den Blockcode Teil schon fertig und da sieht es bei mir schon so aus...

    VB.NET-Quellcode

    1. Dim fehleranzahl(7) As Integer
    2. Dim position(7, 6) As Integer
    4. 'Fehleranzahl und Position markieren
    5. For x As Byte = 0 To codelaenge - 1
    6. For y As Byte = 0 To codelaenge
    7. If codearray(x) <> checkarray(y, x) Then
    8. fehleranzahl(y) += 1
    9. position(y, x) += 1
    10. End If
    11. Next
    12. Next



    ich habe mir schon Gedanken gemacht wie ich diesen Weg gehe...

    ich schreibe die Schrittfolge die vom Knoten A, B, C und D gehen in einen Array um sie abzufragen, lese dann die ersten 2 Bits von der Empfangsfolge und vergleiche sie mit den jeweiligen 2 Bitfolgen des Knoten.

    dabei müsste ich Aufzeichnen wieviele Fehler auf diesem Weg auftreten, diese in ein fehleranzahl array eintragen und dazu den gegangenen Weg mitschreibe...

    in diesem Fall sind es ja 5 Knotenabfragen pro Folge, also dürfte vielleicht aussehen..


    Knoten 1:

    Weg 1: 10 mit 10 vergleichen, neuen Knotenpunkt erkennen, Fehleranzahl schreiben, 10 in Folgenweg schreiben
    Weg 2: 01 mit 10 vergleichen, neuen Knotenpunkt erkennen, Fehleranzahl schreiben, 01 in Folgenweg schreiben


    Knoten 2:

    Weg 1 + 10 mit 01 vergleichen, neuen Knotenpunkt erkennen, Fehleranzahl schreiben, 10 in Folgenweg addieren
    Weg 1 + 01 mit 01 vergleichen, neuen Knotenpunkt erkennen, Fehleranzahl schreiben, 01 in Folgenweg addieren

    Weg 2 + 10 mit 01 vergleichen, neuen Knotenpunkt erkennen, Fehleranzahl schreiben, 10 in Folgenweg addieren
    Weg 2 + 01 mit 01 vergleichen, neuen Knotenpunkt erkennen, Fehleranzahl schreiben, 01 in Folgenweg addieren


    ... usw.

    OK. Ich hab Deinen Alogo noch nicht durchstiegen, aber das ist vielleicht nicht nötig.
    Arbeite nicht mit Arrays, sondern mit List(Of WAS_DU_HALT_BRAUCHST). Da ist die Dimension unwichtig, Du addest lediglich ein neues Element hinten dran.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    wenn ich den jeweiligen Pfad in eine List(Of) eintrage und nach jedem Knoten den vorrigen Wert + dem neuen 2er Bit addiere sollte es ja ungefähr so aussehen oder...?

    VB.NET-Quellcode

    1. List einträge
    3. 'Knoten 1
    4. 10
    5. 01
    7. 'Knoten 2
    8. 1010
    9. 1001
    11. 0110
    12. 0101
    14. 'Knoten 3
    15. 101000
    16. 101011
    17. 100100
    18. 100111
    20. 011010
    21. 011001
    22. 010110
    23. 010101
    25. 'Knoten 4
    26. 10100000
    27. 10100011
    28. 10101100
    29. 10101111
    31. 10010010
    32. 10010001
    33. 10011110
    34. 10011101
    36. 01101000
    37. 01101011
    38. 01100100
    39. 01100111
    41. 01011010
    42. 01011001
    43. 01010110
    44. 01010101
    46. 'Knoten 5
    47. 1010000000
    48. 1010000011
    49. 1010001100
    50. 1010001111
    52. 1010110010
    53. 1010110001
    54. 1010111110
    55. 1010111101
    57. ....



    ich hoffe du weißt damit ungefähr wie der Algorithmus aussehen muss bzw. wie die Abläufe seien müssen ;)

    Das ist ja noch anders als ich dachte.
    Wenn Du in Knoten denkst, kannst Du auch eine XML-Datei (XDocument) und als Anzeige ein TreeView verwenden. Da lässt sich die Knotenstruktur gut drin abbilden.
    Aber:
    Was soll da eigentlich rauskommen?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    siehst du in Folie 3 am unteren Rand...

    es wird als "Vergleichsbitfolge" z.b. 10 01 10 01 11 eingegeben, durch den Viterbi Algorithmus wird diese Empfangsfolge auf ihre Richtigkeit überprüft. Es werden dabei die Folgen durchgelaufen die Auftreten können und mit der Empfangsfolge verglichen um die richtige gesendete Folge heraus zu finden...

    bei dem Beispiel 10 01 10 01 11 ist die richtige Folge 10 01 00 01 11, da sie die kleinste Differenz zum Empfangen hat.

    Das heißt, es interessiert nur Knoten 5 :?:
    Den kannst Du Dir doch ganz schnell ausrechnen und dann die Binär-Vergleiche mit And / Or / Xor vornehmen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    das habe ich mir eben auch gedacht :P

    ich müsste dann jeweils den 5ten Knoten für den Anfang A, B, C und D ausrechnen, da es verschiedene Bitfolgen sind.


    hast du vielleicht eine Idee wie ich das als Code ausrechnen kann oder soll ich es mir wie eben per Hand/Kopf aufzeichnen und dann alle Bitfolgen für den jeweiligen Startpunkt speichern!?


    edit:

    so ich habe dann mal ein wenig angefangen den Anfang zu coden...

    zuerst die eingegebenen Werte einlesen...

    VB.NET-Quellcode

    1. 'Initialisierung der Variablen bitfolge und folgenlaenge als String
    2. Dim bitfolge As String = TextBox2.Text
    3. Dim folgenlaenge As Byte = TextBox2.Text.Length
    4. Dim zustand As String = TextBox3.Text



    schreibe dann die empfangene Bitfolge in einen array, ist für mich später einfacher beide Bitfolgen zu vergleichen

    VB.NET-Quellcode

    1. 'Initialisierung eines Arrays bitfolgearray mit der Größe der Bitfolgenlänge
    2. Dim bitfolgearray(folgenlaenge - 1) As Byte
    5. 'empfangene Bitfolge in einen Array übergeben
    6. For i As Byte = 0 To folgenlaenge - 1
    7. bitfolgearray(i) = bitfolge.Substring(i, 1)
    8. Next


    gibt es eine Möglichkeit das man die Werte die man in ein mehrdimensionales Array schreiben will nicht nebeneinander, sondern in Blöcken untereinander schreibt? Bei 32 Bitfolgen wird es sonst ein wenig unübersichtlich...

    VB.NET-Quellcode

    1. 'Initialisierung der Vergleichsbitfolgen in mehrdimensionale Arrays
    2. Dim checkarray(,) As Byte = {}
    3. Dim startA(,) As Byte = {{0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,1,1},....}
    4. Dim startB(,) As Byte = {{0,0,1,0,0,0,0,0,0,0}, {0,0,1,0,0,0,0,0,1,1},....}
    5. Dim startC(,) As Byte = {{1,0,0,0,0,0,0,0,0,0}, {1,0,0,0,0,0,0,0,1,1},....}
    6. Dim startD(,) As Byte = {{1,0,1,0,0,0,0,0,0,0}, {1,0,1,0,0,0,0,0,1,1},....}


    Den Codierzustand bzw. Startpunkt festlegen und Vergleichswerte in das checkarray schreiben um damit weiter zu arbeiten

    VB.NET-Quellcode

    1. Select Case zustand
    2. Case "00"
    3. checkarray = startA
    4. Case "10"
    5. checkarray = startB
    6. Case "01"
    7. checkarray = startC
    8. Case "11"
    9. checkarray = startD
    10. Case ""
    11. checkarray = startA
    12. End Select



    weiteres muss ich nur auf diesen Fall anpassen...


    eine Frage bleibt mir noch im Hinterkopf, wie kann ich den Vergleichscode mit den wenigstens Unterschieden erkennen und später herauspicken?

    ich leg bei der Überprüfung einen array fehleranzahl(y) += 1 mit dazu der mir auf der position y=Bitfolge die Anzahl der Fehler mitzählt...

    wie kann ich am Ende aus den 32 Feldern des Arrays den Wert auslesen der am niedrigsten ist? Gibt es dafür einen Befehl?


    edit2:

    so hier noch mein Code für die Fehlersuche

    VB.NET-Quellcode

    1. Dim arraylaenge As Byte = checkarray.Rank
    3. 'Initialisierung der Arrays fehleranzahl
    4. Dim fehleranzahl(arraylaenge - 1) As Integer
    6. 'Fehleranzahl berechnen
    7. For x As Byte = 0 To folgenlaenge - 1
    8. For y As Byte = 0 To arraylaenge - 1
    9. If bitfolgearray(x) <> checkarray(y, x) Then
    10. fehleranzahl(y) += 1
    11. End If
    12. Next
    13. Next



    funktioniert soweit auch alles...

    mir fehlt nur noch das Feedback wegen der Erkennung der niedrigsten Fehleranzahl und die Frage wegen der Schreibweise für die Initialisierung des mehrdimensionalen Arrays.

    Dieser Beitrag wurde bereits 8 mal editiert, zuletzt von „TDCroPower“ ()

    so ich habe bis hierhin eigentlich alle meine Probleme lösen können :thumbsup:

    habe auch eine Lösung gefunden um den kleinsten Fehlerwert zu finden und zu markieren für die Ausgabe...

    VB.NET-Quellcode

    1. 'niedrigste Fehleranzahl erkennen und Index speichern
    2. Dim MinWert, MinWertIndex As Integer
    3. MinWert = fehleranzahl(0)
    4. MinWertIndex = 0
    6. For i As Byte = 0 To arraylaenge
    7. If fehleranzahl(i) < MinWert Then
    8. MinWert = fehleranzahl(i)
    9. MinWertIndex = i
    10. End If
    11. Next


    ... funktioniert tadellos !


    ich hoffe mir kann jemand die Ausgabe vereinfachen, da ich sie aktuell wie ich finde sehr kompliziert und in diesem Fall unübersichtlich vollziehe.

    hier mal meine Lösung kurz wie ich es mache...

    VB.NET-Quellcode

    1. Dim check As String = ""
    3. For i As Byte = 0 To folgenlaenge - 1
    4. check += checkarray(MinWertIndex, i).ToString
    5. Next
    7. RichTextBox2.Text = check



    in dem Teil davor war diese Methode noch "machbar", jedoch bei 32 Ausgabewerten inklusive den zwischenschritten wirkt es ein wenig "hässlich"..

    hier mal komplett wie ich es davor gemacht habe bei 8 Codewörtern...

    VB.NET-Quellcode

    1. 'Initialisierung der check* Strings für die Ausgabe
    2. Dim check0 As String = ""
    3. Dim check1 As String = ""
    4. Dim check2 As String = ""
    5. Dim check3 As String = ""
    6. Dim check4 As String = ""
    7. Dim check5 As String = ""
    8. Dim check6 As String = ""
    9. Dim check7 As String = ""
    12. 'die checkar Array Werte werden in die dazugehörige check* Variable geschrieben
    13. For i As Byte = 0 To codelaenge - 1
    14. check0 += checkarray(0, i).ToString
    15. check1 += checkarray(1, i).ToString
    16. check2 += checkarray(2, i).ToString
    17. check3 += checkarray(3, i).ToString
    18. check4 += checkarray(4, i).ToString
    19. check5 += checkarray(5, i).ToString
    20. check6 += checkarray(6, i).ToString
    21. check7 += checkarray(7, i).ToString
    23. Next
    26. 'Ausgabe der Werte und Informationen in die RichTextBox bzw. das Ausgabefenster
    27. RichTextBox1.Text = "Auswertung" + vbCrLf +
    28. "==========================" + vbCrLf +
    29. "Empfangener Wert:" + vbCrLf + vbCrLf +
    30. codewort + vbCrLf +
    31. "==========================" + vbCrLf +
    32. "Codewortlänge:" + vbCrLf + vbCrLf +
    33. codelaenge.ToString + vbCrLf +
    34. "==========================" + vbCrLf +
    35. "Hamming Distanz:" + vbCrLf + vbCrLf +
    36. "d = " + hamdistanz.ToString + vbCrLf +
    37. "==========================" + vbCrLf +
    38. "Bitfehler korrigierbar:" + vbCrLf + vbCrLf +
    39. "t = " + bitfehler.ToString + vbCrLf +
    40. "==========================" + vbCrLf +
    41. "Fehleranzahl:" + vbCrLf + vbCrLf +
    42. "A: " + check0 + " : Fehler = " + fehleranzahl(0).ToString + vbCrLf +
    43. "B: " + check1 + " : Fehler = " + fehleranzahl(1).ToString + vbCrLf +
    44. "C: " + check2 + " : Fehler = " + fehleranzahl(2).ToString + vbCrLf +
    45. "D: " + check3 + " : Fehler = " + fehleranzahl(3).ToString + vbCrLf +
    46. "E: " + check4 + " : Fehler = " + fehleranzahl(4).ToString + vbCrLf +
    47. "F: " + check5 + " : Fehler = " + fehleranzahl(5).ToString + vbCrLf +
    48. "G: " + check6 + " : Fehler = " + fehleranzahl(6).ToString + vbCrLf +
    49. "H: " + check7 + " : Fehler = " + fehleranzahl(7).ToString + vbCrLf +
    50. "==========================" + vbCrLf +
    51. "Fehler ist an der Position:" + vbCrLf +
    52. positionausgabe.ToString + vbCrLf + vbCrLf +
    53. "Codewort wurde korrigiert in..." + vbCrLf + vbCrLf +
    54. checkkorrektur + vbCrLf



    kann mir da jemand sagen wie man es vereinfachen kann...

    Ist die

    TDCroPower schrieb:

    minimalste(n) Fehleranzahl
    kleiner als die minimale Fehleranzahl :?: :D
    Deine Arrays kannst Du so schreiben (mit Leerzeichen + Unterstrich hinten dran)

    VB.NET-Quellcode

    1. Dim startA(,) As Byte = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, _
    2. {0, 0, 0, 0, 0, 0, 0, 0, 1, 1}, _
    3. {0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, _
    4. {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}}
    Lass Deinen Algo erst einmal funktionieren, bevor Du anfängst, die Ausgabe schön zu machen.
    Trenne außerdem die GUI von den Daten, pack alles, was die Daten betrifft, in eine separate Klasse, triggere von außen die Berechnung an und hol die fertigen Ergebnisse dann ab.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

Facebook
Telefonspende