**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
3-86628-363-6, 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.

Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de

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

**Hartung-Gorre Verlag / D-78465 Konstanz / Germany**

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

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