The construction

First, suppose $v,w$ are two binary vectors of length $n$. We say $v<w$ in the lexicographical ordering if (a) $v_1<w_1$, or (b) $v_1=w_1$ and $v_2<w_2$, or (c) $v_1=w_1$ and $v_2=w_2$ and $v_3<w_3$, or ... . For example, $(1,1,0,1)<(1,1,1,0)$, First, we want an algorithm which takes a list $L$ of binary vectors of length $n$ and adds to that list the smallest (in the lexicographical ordering) vector of length $n$ which is not in $L$ and which has distance at least $d$ from an element of $L$. Here's the greedy code algorithm to construct a binary lexicode of length $n$ and minimum distance $d$. Input: Integers $n > d > 0$. Output: A binary code of length $n$ and minimum distance $d$.

1. Construct the list $L$ of all binary n-tuples, ordered lexicographically.
2. Let $C=\{(0,...,0)\}$.
3. Let $c$ denote the first element (in the lex ordering) of $L$ which is at least distance $d$ from any other element of $C$, if it exists. If $c$ does not exist then stop and return $C$.
4. $C=C \cap \{c\}$
5. Go to step 3.

Here's some GAP-like ``pseudo-code'' in more detail.

add_vector:=function(L,n,d)
 #adds smallest binary vector of length n 
 #which is at least distance d from any other
 L0:=[]:
 for i from 0 to 2^n-1 do
  LL:=binary representation of i;
  L0:={LL} union L0:
 end for;
 L1:=sort L0 lexicographically;
 for v in L1 do
  L2:=[];
  for y in L1 do
   if y<>v then L2:=[op(L3),y]; fi;
  end for;
  m:=minimum of all Hamming weights of v-w, w in L
  if m >= d then 
   RETURN(L union v);
  end if;
  end for;
 RETURN(L);
 end function;

Next, we need a function which iterates this add_vector procedure over and over.

lexicode_binary:=function(M,n,d)
 #M is the number of elements, n is the length, 
 #d is the min distance
 L:=[];
 for i from 1 to M do
  L:=add_vector(L,n,d):
 end for;
 RETURN(L);
 end function;

For example, L:=lexicode_binary(16,7,3); returns

$\{$[0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 0],

[1, 0, 0, 1, 1, 0, 0], [0, 1, 0, 1, 0, 1, 0],

[0, 0, 1, 0, 1, 1, 0], [0, 0, 1, 1, 0, 0, 1],

[0, 1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1],

[0, 1, 1, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0],

[1, 1, 0, 0, 1, 1, 0], [1, 1, 0, 1, 0, 0, 1],

[1, 0, 1, 0, 1, 0, 1], [0, 1, 1, 0, 0, 1, 1],

[0, 0, 0, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1]$\}$

Exercise 6.2.1   What does L:=lexicode_binary(16,8,3); return? (Go through every step.)

Some more examples of lexicodes.

• with n=8, d=3:
  $$\begin{array}{c} C = \{[0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1... ...0, 0, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1, 0]\} \end{array}$$

• with n=9, d=3:
  $$\begin{array}{c} C = \{[0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1... ...1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 1, 1, 0, 0]\} \end{array}$$

• with n=10, d=3:
  $$\begin{array}{c} C = \{[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1... ...1, 1, 1, 1, 0], [0, 1, 1, 1, 1, 1, 1, 1, 1, 0]\} \end{array}$$

These are all vectors spaces, the first three of dimension $4$ and the last of dimension $5$.

Exercise 6.2.2   What does L:=lexicode_binary(16,8,3); return? (Go through every step.)

Exercise 6.2.3   Construct the lexicode of length $n=5$ and $d=2$.

Exercise 6.2.4   Construct the lexicode of length $n=6$ and $d=2$.

Exercise 6.2.5   Construct the lexicode of length $n=5$ and $d=3$.

Exercise 6.2.6   The first one (a) is equivalent to the Hamming (7,4,3)-code .