Permutation Decoding of Systematic Codes

A systematic code of block length n is a subspace of the vector space of all possible rows of n symbols chosen from a finite field. In this paper such a code will be called an alphabet, 1 and the sequences belonging to the alphabet will be called letters. The parameters used to describe an alphabet are block length, n, number of information places, k, and error correcting capability, e: n is the number of symbols in each letter, k is the dimension of the alphabet as a vector space, and e is defined by the property that the minimum Hamming distance between two letters is either 2e + 1 or 2e -f 2. It is well known 1 that an alphabet with parameters n,k,e is theoretically capable of correcting all occurrences of ^e errors in a block of length n. However for e > 1, the process of error correction by decoding is complicated, and likely to require expensive equipment. In this paper we 485 486 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1964 describe a new decoding scheme, permutation decoding, which is conceptually simple and quite easy to implement. The decoding procedure consists of a sequence of permutations of the received block of symbols, each of which is followed by a parity check calculation. We can thus make a rough comparison between the complexity of the equipment required for encoding and decoding. The encoder uses one parity check register, and the decoder uses r (or uses one r times), wherer is the number of permutations in the decoding sequence. Real time operation with a constant time delay is possible and perhaps not too expensive.