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.

This work was sponsored by NSF grant CCF-0514881, Qualcomm, Sony, and the Lee Center for Advanced Networking.