Visualizing Galois Fields (Follow-up)

Visualizing Galois Fields (Follow-up) May 21st, 2012
Patrick Stein

In my previous article, I should have finished by remapping the multiplication and addition tables so that the multiplication table was in cyclic order. In cyclic order, the zeroth column (or row) represents zero and the $(i+1)$ -th column (or row) (for $i \neq 0$ ) represents $a^i$ for some generator $a$ . As such, the multiplication table is simply $0$ in the zeroth row and column and $1 + ((i+j) \mod 255)$ for the spot $(i+1,j+1)$ .

Once resorted by the order of the powers of a generator $a$ , the multiplication table look the same regardless of the $a$ . The addition, however, looks different for different generators. Below are the addition tables for two of them: $a = (1+x)$ on the right and $a = x^3 + x^6 + x^7$ on the left. They make as decent a stereo as any of the other pairs so far.

Here’s the code that I used to generate the remapping for a given generator.

(defun make-cyclic-remapping (fn generator &optional (limit 256))
(let ((to (make-array (list limit) :initial-element 0))
(from (make-array (list limit) :initial-element 0))
(used (make-hash-table :test #'equal)))
;; fill up the lookup tables
(setf (gethash 0 used) t)
(nlet fill-tables ((exp 1) (acc 1))
(when (< exp limit)
(setf (aref to exp) acc
(aref from acc) exp
(gethash acc used) t)
(fill-tables (1+ exp) (funcall fn acc generator))))
;; return a closure around the lookup tables
(when (= (hash-table-count used) limit)
(lambda (direction n)
(ecase direction
(:to (aref to n))
(:from (aref from n)))))))

If you’ve read it, you can probably tell by my code that I’m still under the influence of Let Over Lambda. If you haven’t read it, it is quite worth the read.

Then, I used a modified version of the draw-heightmap function which also takes in the remapping function.

(defun draw-mapped-heightmap (op map filename &optional (limit 256))
(let ((png (make-instance 'zpng:pixel-streamed-png
:color-type :grayscale
:width limit
:height limit)))
(with-open-file (stream filename
:direction :output
:if-does-not-exist :create
:element-type '(unsigned-byte 8))
(zpng:start-png png stream)
(dotimes (xx limit)
(dotimes (yy limit)
(let* ((a (funcall map :to xx))
(b (funcall map :to yy))
(c (funcall map :from (funcall op a b))))
(zpng:write-pixel (list c) png))))
(zpng:finish-png png)))
(values))

nklein software

software development and consulting