Cryptography Reference
In-Depth Information
Figure 8.6 - Graph of the computation flow for the fast Hadamard transform
N
=8
.
optimization. This technique involves posing the problem of searching for the
most probable word as a problem of minimizing a global cost function, having as
its variables the information bits of the word. This optimization must be done
theoretically in integers, which makes the problem very dicult. The technique
used is to replace these integer variables by real variables. The problem is then
no longer strictly equivalent to the initial problem but it becomes possible to use
classical non-linear optimization techniques, like the gradient method, to search
for the minimum of the cost function.
Another approach introduced by Kschischang and Sorokine [8.17] involves
using the fact that most block codes used in turbo product codes are in fact trellis
codes. It is then possible to use classical(MAP, Max-Log-MAP, ...) algorithms
for decoding trellis codes to obtain the soft decisions of the decoder. This type
of algorithm is an application in the case of the turbo product codes of the
maximum likelihood decoding algorithms of Wolf [8.19].
Another more recently invented algorithm is Kötter and Vardy's [8.10]. This
algorithm is only applicable to very specific codes, mainly including Reed-
Solomon codes and algebraic codes. It is based on the Sudan algorithm [8.18]
which is capable of determining the codewords in a neighbourhood close to the
received word. It is then possible to use conventional weighting techniques. Al-
though the initial version of this algorithm is relatively computation-costly, theo-
retical improvements have been made and this algorithm is even more promising
since Reed-Solomon codes are widely used in the domain of telecommunica-
tions. There are also decoding algorithms based on sub-codes [8.12]. Although
slightly complex at implementation level, these algorithms provide excellent per-
