Section 7.2.1.1: Generating All n-Tuples

Exercise 19. [23] [23] (The octacode.) Let g(x) = x3 + 2x2 + x −1. a) Use one of the algorithms in this section to evaluate zu0zu1zu2zu3zu4zu5zu6zu∞, a polynomial in the variables z0, z1, z2, and z3, summed over all 256 polynomials (v0 +v1x+v2x2 +v3x3)g(x) mod 4 = u0 +u1x+u2x2 +u3x3 +u4x4 +u5x5 +u6x6 for 0 ≤v0, v1, v2, v3 < 4, where u∞is chosen so that 0 ≤u∞< 4 and (u0 + u1 + u2 + u3 + u4 + u5 + u6 + u∞) mod 4 = 0. b) Construct a set of 256 16-bit numbers that differ from each other in at least six different bit positions. (Such a set, first discovered by Nordstrom and Robinson [Information and Control 11 (1967), 613–616], is essentially unique.)

Verified: yes
Solve time: 2m26s

---

Solution

Let $g(x)=x^3+2x^2+x-1$ in $\mathbb{Z}_4[x]$, so $-1\equiv 3 \pmod 4$, hence

$$ g(x)=x^3+2x^2+x+3. $$

Let

$$ v(x)=v_0+v_1x+v_2x^2+v_3x^3,\qquad 0\le v_i<4, $$

and define

$$ u(x)=u_0+u_1x+\cdots+u_6x^6+u_\infty x^\infty \equiv v(x)g(x)\pmod 4, $$

where $u_\infty$ is chosen so that

$$ u_0+u_1+\cdots+u_6+u_\infty \equiv 0 \pmod 4. $$

The mapping $v\mapsto u$ is $\mathbb{Z}4$-linear, so the exponent vector $(u_0,\dots,u_6,u\infty)$ is a linear function of $(v_0,v_1,v_2,v_3)$. Writing the required sum

$$ \sum_{v_0,v_1,v_2,v_3} z_0^{u_0}z_1^{u_1}\cdots z_6^{u_6}z_\infty^{u_\infty}, $$

we group terms by linearity.

For each $i\in{0,1,2,3}$, let $e_i$ be the input vector with $v_i=1$ and all other $v_j=0$. Then by linearity, the contribution of $v$ factorizes over coordinates, and the whole sum becomes a product over $i$ of one-variable geometric sums in a monomial determined by the $i$th column of the transformation.

Action of multiplication by $x^i g(x)$

Compute

$$ x^i g(x)=x^{i+3}+2x^{i+2}+x^{i+1}+3x^i. $$

Case $i=0$

$$ g(x)=3 + x + 2x^2 + x^3. $$

Hence

$$ (u_0,u_1,u_2,u_3,u_4,u_5,u_6)=(3,1,2,1,0,0,0), $$

and

$$ u_0+\cdots+u_6=7\equiv 3 \pmod 4,\qquad u_\infty\equiv -3\equiv 1 \pmod 4. $$

Thus the monomial contribution is

$$ A_0=z_0^3 z_1 z_2^2 z_3 z_\infty. $$

Case $i=1$

$$ xg(x)=3x + x^2 + 2x^3 + x^4, $$

so

$$ (u_1,u_2,u_3,u_4)=(3,1,2,1), $$

and again the sum is $7\equiv 3\pmod 4$, hence $u_\infty=1$. Therefore

$$ A_1=z_1^3 z_2 z_3^2 z_4 z_\infty. $$

Case $i=2$

$$ x^2g(x)=3x^2 + x^3 + 2x^4 + x^5, $$

giving

$$ (u_2,u_3,u_4,u_5)=(3,1,2,1),\qquad u_\infty=1, $$

so

$$ A_2=z_2^3 z_3 z_4^2 z_5 z_\infty. $$

Case $i=3$

$$ x^3g(x)=3x^3 + x^4 + 2x^5 + x^6, $$

giving

$$ (u_3,u_4,u_5,u_6)=(3,1,2,1),\qquad u_\infty=1, $$

so

$$ A_3=z_3^3 z_4 z_5^2 z_6 z_\infty. $$

Factorization of the sum

For each fixed $i$, the contribution of $v_i\in{0,1,2,3}$ is multiplication by $A_i^{v_i}$. Therefore

$$ \sum_{v_0,v_1,v_2,v_3} \prod_{i=0}^3 A_i^{v_i}

\prod_{i=0}^3 \left(\sum_{t=0}^3 A_i^t\right). $$

Hence the required polynomial equals

$$ (1+A_0+A_0^2+A_0^3)(1+A_1+A_1^2+A_1^3)(1+A_2+A_2^2+A_2^3)(1+A_3+A_3^2+A_3^3), $$

with

$$ \begin{aligned} A_0 &= z_0^3 z_1 z_2^2 z_3 z_\infty,\ A_1 &= z_1^3 z_2 z_3^2 z_4 z_\infty,\ A_2 &= z_2^3 z_3 z_4^2 z_5 z_\infty,\ A_3 &= z_3^3 z_4 z_5^2 z_6 z_\infty. \end{aligned} $$

$$ \boxed{ \prod_{i=0}^3 \left(1+A_i+A_i^2+A_i^3\right) } $$

(b) Construction of 256 binary 16-bit words

Each quaternary vector $(u_0,\dots,u_7)\in \mathbb{Z}_4^8$ produced in part (a) is mapped to a binary vector in ${0,1}^{16}$ by the Gray isometry

$$ 0\mapsto 00,\quad 1\mapsto 01,\quad 2\mapsto 11,\quad 3\mapsto 10. $$

Apply this coordinatewise to obtain a binary word of length $16$:

$$ (u_0,\dots,u_7)\longmapsto (u_0',u_0'',u_1',u_1'',\dots,u_7',u_7''). $$

This map preserves Lee weight and Lee distance, so for any two quaternary vectors $u,v$,

$$ d_L(u,v)=\nu(u'-v')=\nu(u'\oplus v'). $$

The code obtained from all $4^4=256$ inputs $v$ is therefore a binary code of size $256$ in ${0,1}^{16}$. The Lee distance properties of the underlying octacode imply minimum Lee distance $4$, and under the Gray map this becomes Hamming distance at least $6$ between distinct binary images.

Thus the required set is precisely the Gray image of the octacode:

$$ \boxed{\text{all 16-bit Gray images of the 256 quaternary codewords}}. $$

This yields a set of $256$ binary strings of length $16$ with pairwise Hamming distance at least $6$. ∎