MULTILEVEL AND THREEDIMENSIONAL NANOMAGNETIC RECORDING - Bio-Inspired and Nanoscale Integrated Computing - page 194

The existing methods of code design can be divided into three different
categories. In the first group of graph-based techniques, a linear code is associated
with some bipartite graph, with code symbols on the one side and their parity
checks on the other. Iterative decoding is then used similar to belief propagation in
neural networks. This method combines relatively simple processing and powerful
performance; however, it becomes efficient only on the relatively long blocks of
thousand bits. The lack of analytical tools required to estimate low output error
rates (of 10 12 and less) is another drawback of iterative techniques.
The second group employs algebraic methods. Here a code consists of a set of
polynomials of some limited degree taken over a Galois field; a string of all values
of a specific polynomial is called a codeword. This technique is especially efficient
for large (nonbinary) alphabets and leads to the optimum Reed-Solomon (RS)
codes, which are currently designed into most storage systems. However, RS codes
have relatively high complexity in correcting multiple errors. This excessive
complexity combined with long operations in Galois fields can slow down the
overall performance, especially in multilevel signaling, which requires multiple
error correction.
Finally, the third group consists of various concatenated techniques, which
combine good short codes into the longer ones. Invented by Forney over 40 years
ago, this technique still manifests itself as one of the most efficient, thanks to
simple decoding procedures of multiple error correction. To further reduce
decoding complexity, we intend to design new concatenated techniques using
simple constituent codes.
6.3.3. Reed-Muller Codes and Their Recursive Decoding
The technique that will be used in the project has some similarities with general
concatenated design. The main new feature will employ constituent codes that can
be considered as ''self-contained'' recursive constructions. Such constructions—
already known in coding theory—preserve all the properties of the shorter,
building codes. These recursive techniques result in a simple, low complexity
decoding, which repeatedly employs the same code properties multiple times on
increasing lengths.
Reed-Muller (RM) codes represent the most notable example of recursive
constructions and have been explored for five decades. These codes also yield a
simple recursive decoding, which has been recently designed and analyzed in
papers [56-59]. Namely, any RM code (m, r) of length n=2 m and distance
d=2 m r can be obtained from the two RM codes (m 1, r 1) and (m 1, r)1of
length n/2. The decoding process can be relegated further using four RM codes of
length n/4. After a few steps, the decoder finally arrives at the trivial end codes
RM(m r, 0) or RM(r, r), which are either fully redundant (repetition codes) or
nonredundant (full codes). For both types, it is easy to use powerful ML decoding.
On the other hand, the received channel symbols are only recalculated in all
intermediate recursive steps without any decoding. Due to this, decoding