The Nordstrom-Robinson code: representation over GF(4) and efficient decoding

摘要

We show that the Nordstrom-Robinson (1968) code may be represented as the union of binary images of two isomorphic linear (4,2,3) codes over GF(4). Certain symmetries of the unique quaternary (4,2,3) quadracode are discussed. It is shown how the properties of the Nordstrom-Robinson code itself, such as weight distribution, distance invariance, and the well-known representation as the union of eight cosets of the (16,5,8) Reed-Muller code, may be easily rederived from these symmetries. In addition we introduce a decoding algorithm for the Nordstrom-Robinson code which involves projecting its codewords onto the codewords of the quadracode. The algorithm is simple enough to enable hard-decision decoding of the Nordstrom-Robinson code by hand. Furthermore we present an algorithm for maximum-likelihood soft-decision decoding of the Nordstrom-Robinson code based on its representation over GF(4). The complexity of the proposed algorithm is at most 205 real operations. This is, to the best of our knowledge, less than the complexity of any existing decoder, and twice as efficient as the fast maximum-likelihood decoder of Adoul (1987). We also investigate several related topics, such as bounded-distance decoding, sphere-packings, and the (20,2048,6) code.