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.

About these ads

Pages: 1 2

One Response 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: