Marten van Dijk
Consultant, Inventor, Researcher, Applied Mathematician, & Computer Scientist
Error Correction:
Cooperating codes in optical storage make use of Reed-Solomon (RS) codes. These are maximum distance
separable (MDS) codes. Their theory has led to efficient encoding and decoding algorithms. Unfortunately,
their length is determined by the field over which they work, an RS code over GF(q^m) has length q^m-1.
In practical applications (shortened) RS codes over GF(2^8) are used. Hence, their length is bounded from
above by 2^8-1. In the future we may like to use codes over GF(2^8) which are much longer. One option is
to use a code with code words from an RS code over GF(2^{10}) such that the last two rows in their matrix
representation are all zero. This is what we call a subspace subcode of the RS code over GF(2^{10}). Such
a subcode has length n=2^{10}-1 and its codewords can be seen as vectors over GF(2^8). A practical decoding
rule exists. We showed how to make encoding practical [1].
If soft decision information is available, it may be advanteous to decode RS codes by means of an iterative
errors and erasures decoding algorithm (in generalized minimum distance decoding). By using a behavioral
system theoretic framework we classified and proved the correctness of all published iterative errors and
erasures decoding algorithms of RS codes [2]. Notice that nowadays we know from the work of Koetter and
Vardy how to use Sudan's algorithm to process soft decision information leading to a much better
performance.
Other research in the area of algebraic codes is the construction of a new self-dual code [3] and the
construction of binary quasi-cyclic codes using quaternary BCH-codes [4].
For broadcast satellite communication we use convolutional codes. Typically, these codes push a bit error
rate (BER) of 10^{-1}-10^{-2} down to a BER of 10^{-5}-10^{-6}. We analyzed a symbol by symbol
a-posteriori probability (APP) decoding algorithm for convolutional codes invented by Johannesson and
Zigangirov which only uses forward recursions [5]. We proved the convergence of this algorithm by using
the theory of non-negative matrices. Furthermore, we showed that simplifications of this algorithm
described in the log-domain lead to other well-known sub-optimal APP decoding algorithms demonstrating
the relationship between them.
We also studied parallel concatenated codes. In a parallel concatenated convolutional (PCC) code, an
information sequence is encoded by a first convolutional encoder, and an interleaved version of the
information sequence is encoded by a second convolutional encoder. The situation in which we require that
both convolutional encoders end in the all-zero state was investigated. There is a group-theoretical
characterization of all interleavers having this property [6,7].
The iterative decoding of PCC codes uses log-likelihood ratios (LLR), which measure the reliability of a
bit being a zero versus being a one. Mismatches in the output LLRs are, for example, generated by a
decoder which is implemented by using approximations during its computations. We propose a
post-processing of output LLRs to correct part of the mismatches and show how this improves the
performance of the iterative decoding [8].
[1] M. van Dijk and L. Tolhuizen, Efficient encoding for a class of subspace subcodes,
IEEE Trans. on Inform. Theory 45, 2142-2146, 1999.
[2] M. Kuijper, M. van Dijk, H. Hollmann, and J. Oostveen, A unifying system theoretic framework for
errors and erasures Reed-Solomon decoding,
14th International Symposium on Applied Algebra and Error-Correcting Codes (AAECC) 2001, 343-352,
2001.
[3] M. van Dijk, S. Egner, M. Greferath, and A. Wassermann, On two doubly even self-dual binary binary
codes of length 160 and minimum weight 24,
IEEE Trans. on Inform. Theory 51(1), p. 408-411, 2005. The abstract ``On binary linear [160, 80, 24]
codes'' appeared in the Proceedings of ISIT 2003, p. 162, 2003.
[4] M. van Dijk and J. Keunig, A quaternary BCH-code based binary quasi-cyclic code construction,
Proc. of the 19th Symposium on Information Theory in the Benelux, 83-90, 1998.
[5] A.G.C. Koppelaar and M. van Dijk, Symbol by symbol APP decoding with a generalized Viterbi decoder,
Proc. of the ITW'99, Kruger National Park, South Africa, June 20-25, 1999, p. 95, 1999.
[6] M. van Dijk, S. Egner, R. Motwani, and A. Koppelaar, Simultaneous zero-tailing of parallel
concatenated codes, IEEE Trans. on Inform. Theory 49(9), p. 2236-2241, 2003. An abstract appeared in the
Proceedings of ISIT 2000, June 25-30, p. 368, 2000.
[7] M. van Dijk and R. Motwani, Generalised Trellis Termination,
2nd International Symposium on Turbo Codes and Related Topics, Brest, France, September 2000, 255-258,
2000.
[8] M. van Dijk, A.J.E.M. Janssen, and A. Koppelaar, Correcting systematic mismatches in computed
log-likelihood ratios, European Transactions on Telecommunications 14, p. 227-244, 2003.
© 2009 Marten van Dijk .
All rights reserved.