## Hamming Codes

### May 22, 2012

We begin with the G and H matrices:

```(define g #( #(1 0 0 0 1 1 1)              #(0 1 0 0 0 1 1)              #(0 0 1 0 1 0 1)              #(0 0 0 1 1 1 0)))```

```(define h #( #(1 0 1 1 1 0 0)              #(1 1 0 1 0 1 0)              #(1 1 1 0 0 0 1)))```

Our first function multiplies two matrices mod 2:

```(define (mmul2 x y) ; matrix multiplication mod 2   (let* ((x-rows (matrix-rows x)) (x-cols (matrix-cols x))          (y-rows (matrix-rows y)) (y-cols (matrix-cols y))          (z-rows x-rows) (z-cols y-cols))     (if (not (= x-cols y-rows))         (error 'mul2 "incompatible matrices")         (let ((z (make-matrix z-rows z-cols 0)))           (for (i x-rows)             (for (j y-cols)               (for (k x-cols)                 (matrix-set! z i j                   (modulo                     (+ (matrix-ref z i j)                        (* (matrix-ref x i k)                           (matrix-ref y k j)))                     2)))))           z))))```

Now it is simple to encode a data word; `mmul2` returns a 1by4 matrix, and `vector-ref` extracts the row into a vector:

```(define (encode c)   (vector-ref (mmul2 (vector c) g) 0))```

Decoding is somewhat harder. S is the result of the matrix multiplication, z is the prospective output, and the `loop` runs over the columns of H, flipping a bit if it finds an error in the first `len` columns or returning the message unchanged after `len` columns:

```(define (decode r)   (let* ((s (mmul2 h (vector-map vector r)))          (len (matrix-rows g))          (z (vector-map (lambda (v) (vector-ref v 0)) (subvector r 0 len))))     (let loop ((c 0))       (cond ((= c len) z)             ((equal? s (column h c))               (vector-set! z c (- 1 (vector-ref z c))) ; flip bit               z)             (else (loop (+ c 1)))))))```

Here’s an example. The input [1 0 0 1] is encoded as [1 0 0 1 0 0 1], and then all eight possibilities, each involving no more than a single bit flip, are shown to decode to the original input [1 0 0 1]:

```> (encode #(1 0 0 1)) #(1 0 0 1 0 0 1) > (decode #(1 0 0 1 0 0 1)) #(1 0 0 1) > (decode #(0 0 0 1 0 0 1)) #(1 0 0 1) > (decode #(1 1 0 1 0 0 1)) #(1 0 0 1) > (decode #(1 0 1 1 0 0 1)) #(1 0 0 1) > (decode #(1 0 0 0 0 0 0)) #(1 0 0 1) > (decode #(1 0 0 1 1 0 1)) #(1 0 0 1) > (decode #(1 0 0 1 0 1 1)) #(1 0 0 1) > (decode #(1 0 0 1 0 0 0)) #(1 0 0 1)```

We used the matrix data type of a previous exercise and wrote utility functions `column`, which extracts a column from a matrix, `vector-map`, which maps a function over the elements of a vector, and `subvector`, which extracts a portion of a vector in a manner similar to `substring`. You can see all the code and run the program at http://programmingpraxis.codepad.org/KfoIdPZG.

In practice, a (7,4) code is not particularly useful because it uses non-standard word lengths. More common is a (12,8) code with a 50% overhead factor, which sends two 8-bit data bytes followed by an 8-bit parity byte that contains two 4-bit parity nybbles. Also in practice, all the matrix calculations are done once, when the program is initialized, and all encoding and decoding is done by table lookups, which makes the program much faster.

Pages: 1 2

### 2 Responses to “Hamming Codes”

1. phil said

i found this sites algorithm easier to understand, http://users.cs.fiu.edu/~downeyt/cop3402/hamming.html
so, that’s what tried to implement.
please make note of the comment at top.
http://pastebin.com/DKvQiJZg

2. […] al mio blog fornisce un’implementazione di un (7,4) codice di Hamming, con la spiegazione: programmingpraxis.com/2012/05/22/hamming-codes. Questo articolo non spiega ciò che l’OP sta […]