HartungGorre Verlag
Inh.: Dr.
Renate Gorre D78465
Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartunggorre.de

S

Series in Signal and Information Processing, Vol. 20
edited by HansAndrea Loeliger
Maja Ostojic
Multitree
Search Decoding of
Linear Codes
1.
Auflage/1^{st} edition 2011. XII, 94 Seiten/pages, € 64,00.
ISBN 9783866283633
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 lowdensity parity check codes are also
presented.
The different code trees are explored with a new search algorithm. The
algorithm is similar to the Malgorithm 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 lowdensity 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 sumproduct decoder for lowdensity parity check codes.
When the sumproduct 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 sumproduct decoding attempt. This can be repeated multiple times
for different subsets of bits. The resulting decoder significantly outperforms the
sumproduct decoder.
Keywords: Linear codes, lowdensity parity check codes, tree search, branch and
bound, informed search, depthfirst search, A^{*}search, bestfirst search, convolutional codes, sequential decoding.
Reihe "Series
in Signal and Information Processing" im HartungGorre Verlag
Buchbestellungen in Ihrer
Buchhandlung, bei www.amazon.de
oder direkt:
HartungGorre Verlag /
D78465 Konstanz
Telefon: +49 (0) 7533
97227 Telefax: +49 (0) 7533 97228
http://www.hartunggorre.de eMail: verlag@hartunggorre.de