Difference between revisions of "Aufgaben:Exercise 2.14: Petersen Algorithm?"
From LNTwww
m (Text replacement - "[[Kanalcodierung" to "[[Channel_Coding") |
|||
| Line 2: | Line 2: | ||
[[File: P_ID2580__KC_A_2_14_v1.png|right|frame|Grafik aus [Bos98]: <br>'''(1)''' Schneller Decodieralgorithmus für RS–Codes. <br>'''(2)''' Es ist somit nicht der Petersen–Algorithmus!]] | [[File: P_ID2580__KC_A_2_14_v1.png|right|frame|Grafik aus [Bos98]: <br>'''(1)''' Schneller Decodieralgorithmus für RS–Codes. <br>'''(2)''' Es ist somit nicht der Petersen–Algorithmus!]] | ||
| − | Im Kapitel [[ | + | Im Kapitel [[Channel_Coding/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung|Fehlerkorrektur nach Reed–Solomon–Codierung]] wurde die Decodierung von Reed–Solomon–Codes mit dem <i>Petersen–Algorithmus</i> behandelt. |
* Dessen Vorteil ist, dass die einzelnen Schritte nachvollziehbar sind. | * Dessen Vorteil ist, dass die einzelnen Schritte nachvollziehbar sind. | ||
* Sehr von Nachteil ist aber der immens hohe Decodieraufwand. | * Sehr von Nachteil ist aber der immens hohe Decodieraufwand. | ||
| Line 16: | Line 16: | ||
''Hinweise:'' | ''Hinweise:'' | ||
| − | * Die Aufgabe gehört zum Kapitel [[ | + | * Die Aufgabe gehört zum Kapitel [[Channel_Coding/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung| Fehlerkorrektur nach Reed–Solomon–Codierung]]. |
* Die Grafik zeigt das Flussdiagramm eines der bekanntesten Verfahren zur Decodierung von Reed–Solomon–Codes. Um welchen Algorithmus es sich dabei handelt, wird in der Musterlösung zu dieser Aufgabe genannt. | * Die Grafik zeigt das Flussdiagramm eines der bekanntesten Verfahren zur Decodierung von Reed–Solomon–Codes. Um welchen Algorithmus es sich dabei handelt, wird in der Musterlösung zu dieser Aufgabe genannt. | ||
*Die Grafik wurde dem Fachbuch [Bos98]: „Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998” entnommen. Wir danken dem Autor Martin Bossert für die Erlaubnis, die Grafik verwenden zu dürfen. | *Die Grafik wurde dem Fachbuch [Bos98]: „Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998” entnommen. Wir danken dem Autor Martin Bossert für die Erlaubnis, die Grafik verwenden zu dürfen. | ||
| Line 58: | Line 58: | ||
'''(3)''' Richtig sind die <u>Antworten 1, 3 und 4</u>: | '''(3)''' Richtig sind die <u>Antworten 1, 3 und 4</u>: | ||
| − | *Diese Verfahren sind auf der Seite [[ | + | *Diese Verfahren sind auf der Seite [[Channel_Coding/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schnelle_Reed.E2.80.93Solomon.E2.80.93Decodierung| Schnelle Reed–Solomon–Decodierung]] zusammengefasst. |
| − | *Der BCJR– und der Viterbi–Algorithmus beziehen sich dagegen auf die [[ | + | *Der BCJR– und der Viterbi–Algorithmus beziehen sich dagegen auf die [[Channel_Coding/Decodierung_von_Faltungscodes|Decodierung von Faltungscodes]]. |
*Die Grafik auf der Angabenseite zeigt den Berlekamp–Massey–Algorithus (BMA). | *Die Grafik auf der Angabenseite zeigt den Berlekamp–Massey–Algorithus (BMA). | ||
*Die Erklärung zu dieser Abbildung finden Sie im Fachbuch [Bos98]: „Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998” ab Seite 73. | *Die Erklärung zu dieser Abbildung finden Sie im Fachbuch [Bos98]: „Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998” ab Seite 73. | ||
Revision as of 13:57, 9 July 2020
Grafik aus [Bos98]:
(1) Schneller Decodieralgorithmus für RS–Codes.
(2) Es ist somit nicht der Petersen–Algorithmus!
(1) Schneller Decodieralgorithmus für RS–Codes.
(2) Es ist somit nicht der Petersen–Algorithmus!
Im Kapitel Fehlerkorrektur nach Reed–Solomon–Codierung wurde die Decodierung von Reed–Solomon–Codes mit dem Petersen–Algorithmus behandelt.
- Dessen Vorteil ist, dass die einzelnen Schritte nachvollziehbar sind.
- Sehr von Nachteil ist aber der immens hohe Decodieraufwand.
Schon seit der Erfindung der Reed–Solomon–Codierung im Jahre 1960 beschäftigten sich viele Wissenschaftler und Ingenieure mit der Entwicklung möglichst schneller Algorithmen zur Reed–Solomon–Decodierung, und auch heute ist die Algebraische Decodierung noch ein hochaktuelles Forschungsgebiet.
In dieser Aufgabe sollen einige diesbezügliche Begriffe erklärt werden. Auf eine genaue Erklärung dieser Verfahren wurde in $\rm LNTwww $ verzichtet.
Hinweise:
- Die Aufgabe gehört zum Kapitel Fehlerkorrektur nach Reed–Solomon–Codierung.
- Die Grafik zeigt das Flussdiagramm eines der bekanntesten Verfahren zur Decodierung von Reed–Solomon–Codes. Um welchen Algorithmus es sich dabei handelt, wird in der Musterlösung zu dieser Aufgabe genannt.
- Die Grafik wurde dem Fachbuch [Bos98]: „Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998” entnommen. Wir danken dem Autor Martin Bossert für die Erlaubnis, die Grafik verwenden zu dürfen.
Fragebogen
Musterlösung
(1) Richtig ist die Antwort 1:
- Prinzipiell wäre ein Syndromdecoder auch bei RS–Codes möglich, aber bei den hier üblichen großen Codewortlängen $n$ ergäben sich extrem lange Decodierzeiten.
- Bei Faltungscodes (diese arbeiten seriell) macht Syndromdecodierung gar keinen Sinn.
(2) Wie aus den Ausführungen im Theorieteil hervorgeht, ist die Fehlerlokalisierung mit dem weitaus größten Aufwand verbunden ⇒ Antwort 2.
(3) Richtig sind die Antworten 1, 3 und 4:
- Diese Verfahren sind auf der Seite Schnelle Reed–Solomon–Decodierung zusammengefasst.
- Der BCJR– und der Viterbi–Algorithmus beziehen sich dagegen auf die Decodierung von Faltungscodes.
- Die Grafik auf der Angabenseite zeigt den Berlekamp–Massey–Algorithus (BMA).
- Die Erklärung zu dieser Abbildung finden Sie im Fachbuch [Bos98]: „Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998” ab Seite 73.
