# 3 Generating Hamming Codes

Problem Specification

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

Model

A -bit word is modeled by a set where means that the bit at position is set (resp. unset otherwise). The Hamming distance between two words and represented as sets and can be computed by subtracting from the word size the number of elements that is contained () resp. is not contained () in both sets. Thus, the Hamming distance results in

Solver

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.

>     declare
>     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]}}
>        in
>           Bits-{FS.card Common1s}-{FS.card Common0s}>=:Distance
>        end
>     in
>        proc {$ Xs}
>           Xs = {FS.var.list.upperBound NumSymbols [1#Bits]}

>           {ForAllTail Xs proc {$ X|Y}
>                             {ForAll Y proc {$ Z}
>                                          {MinDist X Z}
>                                       end}
>                          end}

>           {FS.distribute naive Xs}
>        end
>     end

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

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

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