Silician Sketchbook

For why and reference material, see Part 1.

So first off, the d and e vectors. Recall that multiplication of terms is accomplished by an AND gate since the operands are bits, and addition is accomplished by an XOR gate. I’ll go over the construction of d, but the same steps apply for e as well.

def gen_d(m):
    a = ['a[%i]' % i for i in xrange(m)]
    a.reverse()
    a = a + [False for i in xrange(m-1)]
    L = []
    for i in xrange(m):
        L.append(a[-m:])
        a.pop()

    b = ['b[%i]' % i for i in xrange(m)]
    d = [' ^ '.join([s for s in map(cond_and, L[i], b) if s != ''])
         for i in xrange(m)]

    return ['d%i = ' % i + d[i] for i in xrange(m)]

The only parameter is m, which is the m in GF(2^m), so for GF(256), m = 8.

First, I need to construct the L matrix, which is m by m. I use something similar to a sliding window to construct the rows of L, popping the trailing element out on each iteration to shift the window to the left.

What’s interesting to note is that instead of padding the row with zeros, like in the paper, I used a boolean. I could have also used an empty string, but it’s better to play it safe and use an explicit boolean. On the other hand, a non-empty string evaluates to “True.”

To do the matrix multiplication, I use map on a row of L and the vector b. The function that is applied to pairs of elements is below:

def cond_and(x, y):
    if x:
        return '(%s and %s)' % (x, y)
    return ''

To make the equation strings a bit cleaner, if the row element is False (i.e. 0) then an empty string is returned. Otherwise, it constructs the product term of the row element and the vector element. The string builder filters out those empty strings when xor-ing the product terms together.

Lastly, the appropriate d_i term is placed at the beginning of each equation, and a list is returned. To print out the entire list, try print '\n'.join(gen_d(8))

To generate the terms in e, the exact same steps occur, except that the U matrix is m-1 by m, and so the number of equations is m-1.

def gen_e(m):
    a = ['a[%i]' % i for i in xrange(m)]
    a.reverse()
    a = [False for i in xrange(m-1)] + a[:-1]

    U = []
    for i in xrange(m):
        U.append(a[-m:])
        a.pop()

    b = ['b[%i]' % i for i in xrange(m)]
    e = [' ^ '.join([s for s in map(cond_and, U[i], b) if s != ''])
         for i in xrange(m-1)]

    return ['e%i = ' % i + e[i] for i in xrange(m-1)]

When you print out the terms for d and e one after the other, you see how they could interlock, hence the very regular layout of the multiplier.

Code to generate Q^T is below.

def Q_transpose(prim):
    mul = gf_256.mul_table(prim)
    m = 8
    alphas = [1]
    for i in xrange(1, 15):
        alphas.append(mul[2][alphas[i-1]])

    combinations = [to_bits(i) for i in xrange(256)]
    x = [0 for i in xrange(256)]
    for i in xrange(256):
        k = reduce(gf_add, map(multiply, combinations[i],
                               alphas[:m]))
        x[k] = combinations[i]

    Q = [0 for i in xrange(7)]
    for i, j in zip(xrange(7), alphas[m:]):
        Q[i] = x[j]

    Q = numpy.array(Q)
    Q_t = Q.transpose()
    return Q_t

Right off the bat you see that I generate a finite field multiplication look-up table based on the primitive polynomial (i.e. 0x1D). In the interests of keeping things concise, I’m not going to give the code to generate such a table, but you may find Wikipedia useful for coding that stuff yourself.

I’m too lazy to write out equation (5) so look it up yourself. But the important points is that Q can only have binary elements, so multiplication is really just an on/off switching, and since we’re in the finite field, addition is XOR.

I never figured out why people always use “primitive element” and “α” when they could just say “2″, because that’s what it really is in all practical finite fields. So I construct a vector containing the powers of 2 within the finite field, by repeated multiplication using the look-up table.

Since there are only 256 possible linear combinations of α⁰ … α⁷, I use a brute force approach, converting 0 … 255 into boolean vectors.

def to_bits(byte):
    ret = []
    for i in xrange(8):
        ret.append(bool(byte & 1))
        byte = byte >> 1
    return ret

Now in Python, you can mix types to a certain extent. I’m using the property that a boolean can multiply with an integer, with the result being either the integer itself (if the boolean was True) or 0 (if the boolean was False). I’m not going to post the code to the multiply function.

The list of products are reduced, i.e. summed using XOR. I’m not going to post the code to the gf_add function.

In this fashion, I compute the result of all possible linear combinations, and pick the ones that equal to α⁸ … α¹⁴. numpy makes it easy to convert a list of lists into an array and then transpose it. If you use Python on Linux, chances are good that you already have numpy, or even scipy.

To implement c = d + Q^Te, see below:

def gen_c(Q_t):
    e = ['e%i' % i for i in xrange(7)]
    c = []
    for i in xrange(8):
        t = ' ^ '.join([s for s in map(multiply, Q_t[i], e) if s != ''])
        s = 'c%i = d%i ^ %s' % (i, i, t)
        c.append(s)
    return c

I use the exact same multiply function without regard for typing. Python returns an empty string if the boolean operand is False, and the string itself if the boolean operand is True, so a simple filter gets rid of the terms that are not needed.

To verify, you can copy and paste the code blocks for d, e, and c into a function that takes a, b as arguments, and returns an integer that the resulting c elements represent. Then you can repeatedly call that function with all possible inputs and verify the result against the multiplication look-up table. I leave all that as an exercise for the reader.

With a bit of tweaking to the above code, or just find/replace, you can use the code blocks as the body of a VHDL entity or Verilog module. That is also an exercise for those inclined. Of course, for multiplication by a constant the logic could be simplified beforehand, but I would be perfectly fine with the synthesizer optimizing that stuff out.

This entry was posted on Monday, September 22nd, 2008 at 1:09 am and is filed under education, hardware, software.You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.