On Generalized Parity Checks

Abstract

An ordinary parity-check is an extra bit p appended to a block (x₁, ..., x_k) of k information bits such that the resulting codeword (x₁, ..., x_k ,p) is capable of detecting one error. The choices for p are p₀  =  x₁ + ... + x_k (mod 2) (even parity) p₁  =  x₁  + ... + x_k + 1 (mod 2) (odd parity) In this paper we consider defining a parity-check if the underlying alphabet is nonbinary. The obvious definition is of course p  =  x₁  + ... + x_k  +  α(mod q). We shall show that this obvious choice is the only choice for q = 2, and up to a natural equivalence the only choice for q = 3. For q ≥ 4, however, the situation is much more complicated.