Exercise 2.14: Petersen Algorithm?

• Return to book

Schneller Algorithmus zur Decodierung von Reed–Solomon–Codes

Im Theorieteil zu Kapitel 2.5 haben wir 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 LNTwww verzichtet.

Hinweise:

• Die Aufgabe bezieht sich auf das Kapitel Fehlerkorrektur nach Reed–Solomon–Codierung.
• Die obige Grafik aus [Bos98] 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.

Fragebogen

1

Bei welchen Codes wird die Syndromdecodierung eingesetzt? Bei den

	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 Fehler,
	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

Solution

(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, die auf der Seite Schnelle Reed–Solomon–Decodierung kurz zusammengefasst sind. Der BCJR– und der Viterbi–Algorithmus beziehen sich dagegen auf die Decodierung von Faltungscodes – siehe Kapitel 3.4.

Die Grafik auf der Angabenseite zeigt den Berlekamp–Massey–Algorithus (BMA). Die Erklärung zu dieser Abbildung finden Sie in [Bos98] ab Seite 73.