Contributions to the decoding of linear codes over Z4

Abstract

This thesis explores various hard and soft decision decoding techniques for linear codes over Z4, all of which, offer substantial coding gains over classical algebraic decoding. We focus only on codes which are free, i.e., (n, k, d) linear codes whose canonical images over GF(2) are (n, k) linear codes of the same minimum distance d, and use BCH codes in all our computer simulations. In the first part of this thesis, we study the performance of BCH codes under list decoding, a decoding technique that finds a list of codewords falling within a certain Hamming distance, say tau, from the received word where tau exceeds half the minimum distance of the code. Two decoding strategies are presented. The first decoder, D1, is a two-stage hard-decision decoder employing the Guruswami-Sudan (GS) decoder in each stage. Each component GS decoder acts on the binary image of the Z4 code and their combined effort allows more than ceiling(n-sqrt(n(n-d))-1) errors to be corrected with certain probability. Computer simulations verify the superiority of this decoder over its component decoders when used to decode the Z4 code directly. E.g. for a (7,4) BCH code, D1 offers an additional coding gain of about 0.4 dB over the GS decoder at a word-error rate (WER) of 10^-3. The second decoder, D2, is a Chase-like, soft-decision decoder with D1 as its hard-decision decoder. Simulation results for the same code show that this decoder offers an additional coding gain of about 1.5 dB over the GS decoder at a WER of 10^-3. We also demonstrate that decoder D2 can outperform the Koetter-Vardy soft-decision version of the GS decoder. As the GS decoder is applicable to all Reed-Solomon codes and their subfield subcodes, D1 and D2 can therefore be used to decode a broader class of Z4 codes. In the second part of this thesis, we study the performance/complexity trade-offs of two Chase-like decoders for Z4 codes. Unlike decoder D2 however, the hard-decision decoder used in these Chase decoders output a unique codeword rather than a list of codewords. Nevertheless, like D2, they operate based on decoding two copies of a Z4 codeb