TAOCP 7.2.1.1 Exercise 18

Section 7.2.1.1: Generating All n-Tuples

Exercise 18. ▶ [20] [20] The Lee weight of a vector u = (u1, . . . , un), where each component satisfies 0 ≤uj < mj, is defined to be νL(u) = n  j=1 min(uj, mj −uj); and the Lee distance between two such vectors u and v is dL(u, v) = νL(u −v), where u −v = ((u1 −v1) mod m1, . . . , (un −vn) mod mn). (This is the minimum number of steps needed to change u to v if we adjust some component uj by ±1 (modulo mj) in each step.) A quaternary vector has mj = 4 for 1 ≤j ≤n, and a binary vector has all mj = 2. Find a simple one-to-one correspondence between quaternary vectors u = (u1, . . . , un) and binary vectors u′ = (u′ 1, . . . , u′ 2n), with the property that νL(u) = ν(u′) and dL(u, v) = ν(u′ ⊕v′).

310 COMBINATORIAL SEARCHING 7.2.1.1

Verified: yes
Solve time: 1m56s

---

Solution

Define a mapping $\varphi : {0,1,2,3} \to {0,1}^2$ by

$$ \varphi(0) = (0,0), \quad \varphi(1) = (0,1), \quad \varphi(2) = (1,1), \quad \varphi(3) = (1,0). $$

For a quaternary vector $u = (u_1,\dots,u_n)$ define the binary vector

$$ u' = \big(\varphi(u_1), \varphi(u_2), \dots, \varphi(u_n)\big) \in {0,1}^{2n}. $$

The binary weight $\nu(u')$ is the number of $1$ entries in $u'$. The Lee weight of $u$ is

$$ \nu_L(u) = \sum_{j=1}^n \min(u_j, 4-u_j). $$

Equality of weights

For a single coordinate $x \in {0,1,2,3}$, direct inspection gives

$$ \min(x,4-x) = \begin{cases} 0 & x=0,\ 1 & x=1,\ 2 & x=2,\ 1 & x=3. \end{cases} $$

The Hamming weight of $\varphi(x)$ is

$$ \nu(\varphi(0))=0,\quad \nu(\varphi(1))=1,\quad \nu(\varphi(2))=2,\quad \nu(\varphi(3))=1, $$

so for each $x$,

$$ \nu(\varphi(x)) = \min(x,4-x). $$

Summing over coordinates yields

$$ \nu(u') = \sum_{j=1}^n \nu(\varphi(u_j)) = \sum_{j=1}^n \min(u_j,4-u_j) = \nu_L(u). $$

Distance preservation

Let $u,v \in {0,1,2,3}^n$. Define coordinate differences modulo $4$ by

$$ d_j = (u_j - v_j) \bmod 4 \in {0,1,2,3}. $$

Then

$$ d_L(u,v) = \sum_{j=1}^n \min(d_j,4-d_j). $$

On the binary side, since XOR acts coordinatewise,

$$ u' \oplus v' = \big(\varphi(u_1)\oplus \varphi(v_1), \dots, \varphi(u_n)\oplus \varphi(v_n)\big), $$

so

$$ \nu(u' \oplus v') = \sum_{j=1}^n \nu(\varphi(u_j)\oplus \varphi(v_j)). $$

It suffices to verify the single-coordinate identity

$$ \nu(\varphi(a)\oplus \varphi(b)) = \min((a-b)\bmod 4,;4-((a-b)\bmod 4)). $$

Each value of $(a,b)$ is checked directly. The four codewords $\varphi(0),\varphi(1),\varphi(2),\varphi(3)$ form a 4-cycle in the Hamming graph on ${0,1}^2$:

$$ 00 \to 01 \to 11 \to 10 \to 00. $$

Adjacent vertices differ in Hamming distance $1$, opposite vertices differ in Hamming distance $2$. The Lee metric on ${0,1,2,3}$ is exactly the shortest-path metric on the same 4-cycle under the ordering $0,1,2,3,0$. The map $\varphi$ identifies these two cycles, hence preserves shortest-path distances.

Thus for each coordinate $j$,

$$ \nu(\varphi(u_j)\oplus \varphi(v_j)) = \min(d_j,4-d_j), $$

and summing gives

$$ \nu(u'\oplus v') = \sum_{j=1}^n \min(d_j,4-d_j) = d_L(u,v). $$

This completes the proof. ∎