3 Generating Hamming Codes

Problem Specification

Generate a Hamming code that fits in b-bit words to code n symbols where the Hamming distance between every two symbol codes is at least d. The Hamming distance between to words is the number of bit positions where they differ.


A b-bit word is modeled by a set  s \subseteq \{1,\ldots,b\} where e \in s means that the bit at position e is set (resp. unset otherwise). The Hamming distance h(a,b) between two words a and b represented as sets s_a and s_b can be computed by subtracting from the word size b the number of elements that is contained (\#(s_a \cap s_b)) resp. is not contained (\#(\{1,\ldots,b\}\backslash (s_a \cup s_b))) in both sets. Thus, the Hamming distance results in

h(a,b) = b - \#(s_a \cap s_b) - \#(\{1,\ldots,b\}\backslash (s_a \cup


The function Hamming returns a solver to generate a Hamming code for NumSymbols symbols in words with Bits bits and a Hamming distance of Distance. The procedure MinDist implements the constraint that the Hamming distance does not exceed the value of Distance. The list Xs holds the sets representing the single codes. The nested loop (ForAllTail and ForAll) imposes MinDist on all pairwise distinct elements of Xs. The distribution employs straightforwardly a naive strategy.

fun {Hamming Bits Distance NumSymbols}       
   proc {MinDist X Y}       
      Common1s = {FS.intersect X Y}
      Common0s = {FS.complIn
                  {FS.union X Y}
                  {FS.value.make [1#Bits]}}
      Bits-{FS.card Common1s}-{FS.card Common0s}>=:Distance
   proc {$ Xs}
      Xs = {FS.var.list.upperBound NumSymbols [1#Bits]}
      {ForAllTail Xs proc {$ X|Y}
                        {ForAll Y proc {$ Z}
                                     {MinDist X Z}
      {FS.distribute naive Xs}

The following code generates a Hamming code for 16 symbols using 7 bit words and ensures a Hamming distance of 2.

 {Map {SearchOne {Hamming 7 2 16}}.1
  fun {$ X}  
     {ForThread 7 1 ~fun {$ Is I}  
                          {FS.reified.isIn I X}|Is  
                       end nil}  

Further, the code is nicely formatted displayed in the Oz Browser.

Tobias Müller
Version 1.4.0 (20080702)