Exercise 2.14: Petersen Algorithm?

• Return to book

Grafik aus [Bos98]:
(1)   Fast decoding algorithm for RS codes.
(2)   It is therefore not the Petersen algorithm!

In the chapter  "Error correction after Reed-Solomon coding"  the decoding of Reed–Solomon codes with the Petersen algorithm  was treated.

• Its advantage is that the individual steps are traceable.
• Very much of disadvantage is however the immensely high decoding expenditure.

Already since the invention of Reed–Solomon coding in 1960, many scientists and engineers were engaged in the development of algorithms for Reed–Solomon decoding as fast as possible, and even today Algebraic Decoding  is still a highly topical field of research.

In this exercise, some related concepts will be explained. A detailed explanation of these procedures has been omitted in  $\rm LNTwww $ .

Hints:

• 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.

Questions

1

For which codes is syndrome decoding used? For

	binary block codes,
	Reed–Solomon codes,
	convolutional codes.

2

What is most complex in the Petersen algorithm?

	Checking if there are (one or more) errors at all,
	the localization of the errors,
	the determination of the error value.

3

Which terms refer to Reed–Solomon decoding?

	The Berlekamp–Massey algorithm,
	the BCJR algorithm,
	the Euclidean algorithm,
	frequency domain methods based on the DFT,
	the Viterbi algorithm.

Solution

Solution

(1)  Correct is the answer 1:

• In principle, a syndrome decoder would also be possible with RS codes, but with the large codeword lengths $n$ common here, extremely long decoding times would result.
• For convolutional codes (these work serially) syndrome decoding makes no sense at all.

(2)  As can be seen from the discussion in the theory section, error localization involves by far the greatest effort   ⇒   Answer 2.

(3)  Correct answers 1, 3, and 4:

• These procedures are summarized on the "Fast Reed–Solomon decoding" page.
• The BCJR– and Viterbi algorithms, on the other hand, refer to "Decoding of convolutional codes".
• The graphic on the information page shows the Berlekamp–Massey algorithm (BMA).
• The explanation of this figure can be found in the reference book [Bos98]: "Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998" from page 73.