Aufgaben:Aufgabe 2.14: Petersen–Algorithmus?: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung}}
  
[[Datei: P_ID2580__KC_A_2_14_v1.png|right|frame|Schneller Algorithmus zur Decodierung von Reed–Solomon–Codes  (Grafik aus [Bos98])]]
+
[[Datei: P_ID2580__KC_A_2_14_v1.png|right|frame|Grafik aus [Bos98]: <br>'''(1)''' &nbsp; Schneller Decodieralgorithmus für RS–Codes. <br>'''(2)''' &nbsp; Es ist somit nicht der Petersen&ndash;Algorithmus!]]
Im Kapitel [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung|Fehlerkorrektur nach Reed–Solomon–Codierung]] wurde die Decodierung von Reed&ndash;Solomon&ndash;Codes mit dem <i>Petersen&ndash;Algorithmus</i> behandelt.
+
Im Kapitel&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung|"Fehlerkorrektur nach Reed–Solomon–Codierung"]]&nbsp; wurde die Decodierung von Reed&ndash;Solomon&ndash;Codes mit dem&nbsp; "Petersen&ndash;Algorithmus"&nbsp; 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.
  
  
Schon seit der Erfindung der Reed&ndash;Solomon&ndash;Codierung im Jahre 1960 beschäftigten sich viele Wissenschaftler und Ingenieure mit der Entwicklung möglichst schneller Algorithmen zur Reed&ndash;Solomon&ndash;Decodierung, und auch heute ist die <i>Algebraische Decodierung</i> noch ein hochaktuelles Forschungsgebiet.
+
Schon seit der Erfindung der Reed&ndash;Solomon&ndash;Codierung im Jahre 1960 beschäftigten sich viele Wissenschaftler und Ingenieure mit der Entwicklung möglichst schneller Algorithmen zur Reed&ndash;Solomon&ndash;Decodierung,&nbsp; und auch heute ist die&nbsp; "Algebraische Decodierung"&nbsp; noch ein hochaktuelles Forschungsgebiet.
 +
 
 +
In dieser Aufgabe sollen einige diesbezügliche Begriffe erklärt werden.&nbsp; Auf eine genaue Erklärung dieser Verfahren wurde in unserem&nbsp; "$\rm LNTwww$"&nbsp; verzichtet.
  
In dieser Aufgabe sollen einige diesbezügliche Begriffe erklärt werden. Auf eine genaue Erklärung dieser Verfahren wurde in $\rm LNTwww $ verzichtet.
 
  
  
Zeile 15: Zeile 17:
  
 
''Hinweise:''
 
''Hinweise:''
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung| Fehlerkorrektur nach Reed&ndash;Solomon&ndash;Codierung]].  
+
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung| "Fehlerkorrektur nach Reed&ndash;Solomon&ndash;Codierung"]].
* Die Grafik zeigt das Flussdiagramm eines der bekanntesten Verfahren zur Decodierung von Reed&ndash;Solomon&ndash;Codes. Um welchen Algorithmus es sich dabei handelt, wird in der Musterlösung zu dieser Aufgabe genannt.
+
*Die Grafik wurde dem Fachbuch  [Bos98]: &bdquo;Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998&rdquo; entnommen. Wir danken dem Autor Martin Bossert für die Erlaubnis.
+
* Die Grafik zeigt das Flussdiagramm eines der bekanntesten Verfahren zur Decodierung von Reed&ndash;Solomon&ndash;Codes.&nbsp; Um welchen Algorithmus es sich dabei handelt,&nbsp; wird in der Musterlösung zu dieser Aufgabe genannt.
 +
*Die Grafik wurde dem Fachbuch  [Bos98]: &nbsp; "Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998"&nbsp; entnommen.&nbsp; Wir danken dem Autor Martin Bossert für die Erlaubnis,&nbsp; die Grafik verwenden zu dürfen.
  
  
Zeile 25: Zeile 28:
 
{Bei welchen Codes wird die Syndromdecodierung eingesetzt? Bei  
 
{Bei welchen Codes wird die Syndromdecodierung eingesetzt? Bei  
 
|type="[]"}
 
|type="[]"}
+ den binären Blockcodes,
+
+ binären Blockcodes,
- den Reed&ndash;Solomon&ndash;Codes,
+
- Reed&ndash;Solomon&ndash;Codes,
- den Faltungscodes.
+
- Faltungscodes.
  
 
{Was ist beim Petersen&ndash;Algorithmus am aufwändigsten?
 
{Was ist beim Petersen&ndash;Algorithmus am aufwändigsten?
|type="[]"}
+
|type="()"}
- Überprüfung, ob überhaupt (ein oder mehrere) Fehler vorliegen,
+
- Überprüfung, ob überhaupt&nbsp; $($ein oder mehrere$)$&nbsp; Fehler vorliegen,
+ die Lokalisierung der Fehler,
+
+ die Lokalisierung der Fehlerpositionen,
 
- die Fehlerwertbestimmung.
 
- die Fehlerwertbestimmung.
  
Zeile 40: Zeile 43:
 
- der BCJR&ndash;Algorithmus,
 
- der BCJR&ndash;Algorithmus,
 
+ der Euklidische Algorithmus,
 
+ der Euklidische Algorithmus,
+ Frequenzbereichsverfahren, basierend auf der DFT,
+
+ Frequenzbereichsverfahren,&nbsp; basierend auf der DFT,
 
- der Viterbi&ndash;Algorithmus.
 
- der Viterbi&ndash;Algorithmus.
 
</quiz>
 
</quiz>
Zeile 46: Zeile 49:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Richtig ist die <u>Antwort 1</u>. Prinzipiell wäre ein Syndromdecoder auch bei Reed&ndash;Solomon&ndash;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.
+
'''(1)'''&nbsp; Richtig ist die&nbsp; <u>Antwort 1</u>:
 +
*Prinzipiell wäre ein Syndromdecoder auch bei Reed&ndash;Solomon&ndash;Codes möglich,&nbsp; aber bei den hier üblichen großen Codewortlängen&nbsp; $n$&nbsp; ergäben sich extrem lange Decodierzeiten.
 +
 +
*Bei Faltungscodes&nbsp; $($diese arbeiten seriell$)$&nbsp; macht Syndromdecodierung gar keinen Sinn.
 +
 
 +
 
  
 +
'''(2)'''&nbsp; Wie aus den Ausführungen im Theorieteil hervorgeht,&nbsp; ist die Fehlerlokalisierung mit dem weitaus größten Aufwand verbunden &nbsp; &#8658; &nbsp; <u>Antwort 2</u>.
  
'''(2)'''&nbsp; Wie aus den Ausführungen im Theorieteil hervorgeht, ist die Fehlerlokalisierung mit dem weitaus größten Aufwand verbunden &nbsp;&#8658;&nbsp; <u>Antwort 2</u>.
 
  
  
'''(3)'''&nbsp; Richtig sind die <u>Antworten 1, 3 und 4</u>, die auf der Seite [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schnelle_Reed.E2.80.93Solomon.E2.80.93Decodierung| Schnelle Reed&ndash;Solomon&ndash;Decodierung]] kurz zusammengefasst sind. Der BCJR&ndash; und der Viterbi&ndash;Algorithmus beziehen sich dagegen auf die Decodierung von Faltungscodes &ndash; siehe [[Kanalcodierung/Decodierung_von_Faltungscodes|Kapitel 3.4]].
+
'''(3)'''&nbsp; Richtig sind die&nbsp; <u>Antworten 1, 3 und 4</u>:
 +
*Diese Verfahren sind auf der Seite&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schnelle_Reed.E2.80.93Solomon.E2.80.93Decodierung| "Schnelle Reed&ndash;Solomon&ndash;Decodierung"]]&nbsp; zusammengefasst.
 +
 +
*Der BCJR&ndash; und der Viterbi&ndash;Algorithmus beziehen sich dagegen auf die&nbsp; [[Kanalcodierung/Decodierung_von_Faltungscodes|"Decodierung von Faltungscodes"]].
 +
*Die Grafik auf der Angabenseite zeigt den Berlekamp&ndash;Massey&ndash;Algorithus&nbsp; $\rm (BMA)$.  
  
Die Grafik auf der Angabenseite zeigt den Berlekamp&ndash;Massey&ndash;Algorithus (BMA). Die Erklärung zu dieser Abbildung finden Sie in [https://intern.lntwww.de/cgi-bin/extern/uni.pl?uno=hyperlink&due=entitaet&e_id=41798&hyperlink_typ=entitaet_verweis [Bos98]] ab Seite 73.
+
*Die Erklärung zu dieser Abbildung finden Sie im Fachbuch&nbsp;  "[Bos98]:&nbsp; Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998"&nbsp;  ab Seite 73.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 31. Oktober 2022, 14:33 Uhr

Grafik aus [Bos98]:
(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 unserem  "$\rm LNTwww$"  verzichtet.



Hinweise:

  • 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

1

Bei welchen Codes wird die Syndromdecodierung eingesetzt? Bei

binären Blockcodes,
Reed–Solomon–Codes,
Faltungscodes.

2

Was ist beim Petersen–Algorithmus am aufwändigsten?

Überprüfung, ob überhaupt  $($ein oder mehrere$)$  Fehler vorliegen,
die Lokalisierung der Fehlerpositionen,
die Fehlerwertbestimmung.

3

Welche Begriffe beziehen sich auf die Reed–Solomon–Decodierung?

Der Berlekamp–Massey–Algorithmus,
der BCJR–Algorithmus,
der Euklidische Algorithmus,
Frequenzbereichsverfahren,  basierend auf der DFT,
der Viterbi–Algorithmus.


Musterlösung

(1)  Richtig ist die  Antwort 1:

  • Prinzipiell wäre ein Syndromdecoder auch bei Reed–Solomon–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:

  • Der BCJR– und der Viterbi–Algorithmus beziehen sich dagegen auf die  "Decodierung von Faltungscodes".
  • Die Grafik auf der Angabenseite zeigt den Berlekamp–Massey–Algorithus  $\rm (BMA)$.
  • Die Erklärung zu dieser Abbildung finden Sie im Fachbuch  "[Bos98]:  Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998"  ab Seite 73.