Hartung-Gorre Verlag Inh.: Dr. Renate Gorre D-78465 Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de

S

Series in Signal and Information Processing, Vol. 20
edited by Hans-Andrea Loeliger

Maja Ostojic

Multitree
Search Decoding of
Linear Codes

1. Auflage/1^st edition 2011. XII, 94 Seiten/pages, € 64,00.
ISBN 978-3-86628-363-3

Tree search algorithms have a long history in computer science. In the coding literature, tree search algorithms have traditionally been used for decoding convolutional codes. Convolutional codes are linear codes with a special structure. Classic tree search decoders (most notably the sequential decoder) search one code tree in which the bits are ordered sequentially.

We propose a multitree search decoder for arbitrary linear codes. We develop several algorithms for constructing code trees from the parity check matrix of a linear code. We propose algorithms that generate code trees, in which the bits appear in random order. We also show how to generate code trees specially designed to decode a given sequence received from a noisy channel. In such code trees, the ordering of the bits depends on the received sequence. Multiple code trees can be generated for each code and sequence. Specialized code trees for low-density parity check codes are also presented.

The different code trees are explored with a new search algorithm. The algorithm is similar to the M-algorithm for convolutional codes; it explores a code tree with limits on the breadth of the explored subtree. An evaluation function is used to decide which node to expand at each depth. We present an evaluation function for general linear codes and an improved evaluation function for low-density parity check codes. Both are optimized for the proposed search algorithm.

The proposed multitree search decoder achieves near optimal performance for short block codes.

For longer block lengths, we propose to use tree search decoding to improve the standard sum-product decoder for low-density parity check codes. When the sum-product decoder fails to find a codeword, a tree search is used to decode a subset of bits. The channel messages for these bits are then replaced by the decisions found in the tree search in an additional sum-product decoding attempt. This can be repeated multiple times for different subsets of bits. The resulting decoder significantly outperforms the sum-product decoder.

Keywords: Linear codes, low-density parity check codes, tree search, branch and bound, informed search, depth-first search, A^*-search, bestfirst search, convolutional codes, sequential decoding.

Reihe "Series in Signal and Information Processing" im Hartung-Gorre Verlag

Buchbestellungen in Ihrer Buchhandlung, bei www.amazon.de

oder direkt:

Hartung-Gorre Verlag / D-78465 Konstanz

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228

http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de