Easily decoded error correcting codes

This thesis is concerned with the decoding aspect of linear block error-correcting codes. When, as in most practical situations, the decoder cost is limited an optimum code may be inferior in performance to a longer sub-optimum code' of the same rate. This consideration is a central theme of the thesis. The best methods available for decoding short optimum codes and long B.C.H. codes are discussed, in some cases new decoding algorithms for the codes are introduced. Hashim's "Nested" codes are then analysed. The method of nesting codes which was given by Hashim is shown to be optimum - but it is seen that the codes are less easily decoded than was previously thought. "Conjoined" codes are introduced. It is shown how two codes with identical numbers of information bits may be "conjoined" to give a code with length and minimum distance equal to the sum of the respective parameters of the constituent codes but with the same number of information bits. A very simple decoding algorithm is given for the codes whereby each constituent codeword is decoded and then a decision is made as to the correct decoding. A technique is given for adding more codewords to conjoined codes without unduly increasing the decoder complexity. Lastly, "Array" codes are described. They are formed by making parity checks over carefully chosen patterns of information bits arranged in a two-dimensional array. Various methods are given for choosing suitable patterns. Some of the resulting codes are self-orthogonal and certain of these have parameters close to the optimum for such codes. A method is given for adding more codewords to array codes, derived from a process of augmentation known for product codes