Final presentation of the bachelor thesis
Improved Decoding of Partial Unit Memory Codes Using List Decoding of Reed-Solomon Codes
Sven Puchinger (Supervisor: Antonia Wachter-Zeh)

Friday, July 20, 2012, 1:15 pm
Uni West, Room 43.2.227

(Partial) Unit Memory ((P)UM) codes can be seen as convolutional codes with memory m=1. In order to construct convolutional codes with deterministic distance properties and to use efficient existing block decoders, Lee and Lauer introduced (P)UM codes. They provide a possibility to construct convolutional codes based on block codes achieving high decoding performance. There exist several constructions based on Reed-Solomon or BCH codes.

Dettmar and Sorger designed a decoding algorithm for (P)UM codes which uses the efficient Bounded Minimum Distance (BMD) block decoders of the underlying block code and is able to decode up to half the extended row distance.

The Sudan and Guruswami-Sudan algorithms can decode Reed-Solomon codes beyond half the minimum distance. This principle is based on interpolation and factorization and it guarantees to output a list of all codewords within the decoding radius.

In this thesis, the Dettmar-Sorger algorithm is improved by using Guruswami-Sudan's list decoder for the underlying block code instead of BMD block decoders. A bound is shown, for which decoding can be guaranteed. The correctness of the decoding algorithm is proven and an analysis of the worst case and average complexity is done. Additionally, simulations show the performance gain compared to the original Dettmar-Sorger algorithm.