ALGORITHMS FOR DECODING BLOCK CODES

Amer  A. HASSAN

One of the advances in decoding to arise since Shannon's work in 1948 is algebraic decoding, where the decoding problem is that of two computational problems in finite fields:

     - determine the coefficients of the error locator polynomial, and

     -  given the coefficients of the error locator polynomial find its roots.

To be able to use algebraic decoding one imposes restrictions on the receiver such as information loss quantization of amplitude at the output of the demodulator, which forces the code to be suboptimal, and imposing algebraic structure on the code such as linearity and cyclicity. Moreover, if we provide the decoder errors and erasures, then we generally reduce the number of decoding errors at the cost of introducing decoding erasures. Algebraic errors-and-erasures decoding algorithms can be used to correct the resulting errors and erasures. The resulting overall error probability is lower than that attainable with error correction only.

In this thesis we proposed several techniques to enhance the performance of coded digital communications systems by creating an error-and-erasure channel seen by an encoder decoder pair. We started by discussing the general decoding problem of linear block codes. Then we summarized some techniques that could simplify the decoding process on the expense of trading some performance. One technique is concatenated coding which is very attractive to achieve long block codes with low complexity. The error correcting properties of concatenated codes was evaluated in Chapters 3 and 4, for soft decision decoding. We developed two algorithms for coherent reception and noncoherent reception, respectively. These algorithms use errors erasures decoding and make use of several branches with different tentative decisions giving rise to parallel decoding. The set of thresholds Δ _z and H _z (for the coherent and noncoherent cases, respectively) for each algorithm is chosen to optimize the error correcting capability of the code. These algorithms combine the power of soft decision decoding with low complexity, and algebraic decoding. Thus we are able to use soft decision decoding of a long code, something which is prohibitively complex to perform with one decoder.

In Chapter 5 we let the transmitter help in establishing an error erasure channel for a slow Frequency hopped spread spectrum communication system in a Rayleigh faded channel. We transmit a known sequence of test bits in each dwell interval. At the receiver we use the number of errors in these test bits and compare it to a threshold upon which we decide whether to erase the symbols in the corresponding dwell interval or to declare the hop as reliable.

In Chapter 6 we use a concatenated coded system with the inner decoder used to help the outer decoder in whether the received hop is reliable or not. The inner decoder is used for error detection and error correction. As compared to the previous technique, the concatenated coded system is superior in performance. For probability of packet error 10^-6 there is more than 3 dB improvement in the required E_b/N₀ over the test bits case (assuming equal redundancy in each hop and same outer code). The tradeoff between the two systems proposed in Chapters 5 and 6 is that of complexity versus performance. In the first case the generation of side information is very simple. In the second system we need an additional decoder thus increasing hardware and time complexity.