Programming Praxis

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