Silician Sketchbook

Apparently, light snow soils pants. Imagine what will happen when we get our first snow storm.

I mean, come on, we haven’t even had a snow storm this fall/winter season, and people drive like 10 cm is already on the ground and quickly accumulating.

Let’s make one thing clear: the roads were not icy, they were not slushy, they were and are wet. When it rains I still see people doing 10-15 km/h above the limit, i.e. PRO DRIVER coming through. I guess they’re not so PRO if they curl up into a fetal position when they see snow that melts on contact with the pavement.

I had to take side roads, it was so bad. And the funny thing was, the side roads were very lightly traveled. I guess panicking drivers like to herd together and crawl together. When the snow really hits the fan, I’d like to see how they handle the local hill feature at their paltry 2 km/h and truly poor traction conditions.

This is the second or third time we’ve seen snow in the past few weeks.  Maybe people’s attention spans are short.

Even people in a Skype channel are treating this like it’s A Big Deal. Snow tires means driving like it’s summer? Seriously? I drove around like it’s summer in my all-seasons today. Puhleaze. I refrained from comment except to note that my winter tires continue to reside in the basement, where they have sat for the past two winters.

Maybe I ignore common sense at my own peril, but my winter tires and I don’t really get along. For one, they’re heavy, and it shows every time I have to accelerate from a stop or even take my foot off the accelerator for a moment. Mileage takes a hit as a result. Perhaps newer winter tires drive better, but the ones I have certainly do not turn a winter wonderland into a sun-kissed summer.

Most importantly, they don’t help me. They could help you, but they certainly don’t help me. I have narrowly avoided close calls in slushy to icy conditions not by coming to a stop, but by pulling quickly to the shoulder. These tires stand no chance with black ice, absolutely none. I’d rather drive my sub-optimal all-seasons and know what I’m getting into rather than think I’m king of the road with winter tires.

For those who drive around the city anyway, it’s not hard to stay out of trouble with all-seasons. Proper tire pressure, slow application of throttle, low torque/gearing for starts and stops, is that’s required from an operational standpoint. Good visibility and safe following distance are needed whether you have winter tires or not.

And if the weather is really bad, or if you know that it’s going to get really bad, then stay home. Call in sick. If you really have to be somewhere that’s not the airport, take the bus, a vehicle that’s guaranteed to have more traction than you’ll ever get out of your winter tires.

Piled Higher and Deeper is a very QFT worthy comic strip, but this one in particular reminds me of what my macroeconomics professor said during one lecture.

Graduating? Economy going to tank? Stay in school, anyway you can.

The rationale was that job prospects, while not non-existent, were going to be harder to come by, and when the they pick up you will be in competition with younger graduates with current experience versus whatever you received 2+ years prior.

Ninja Edit: Nice follow.

When one of the channels on a headset drops out, and you have to fiddle with the wires to find the sweet spot such that it’ll come back, you know that the headset is on its last legs. But I’m not about to go and buy a new headset just yet. The one I was using was not really mine at first, and I wound up claiming it because no one else was using it.

I’ve since gone back to my original headset, but there was a reason why I stopped using it in the first place, which I’ve just rediscovered.

For one, the foam piece that covered the microphone spontaneously came off, but that’s not a big deal. More troublesome was that one day, the headset decided to switch to mono, and at the time I couldn’t figure out why.

A cool side-effect of having the headphones magically go mono is that the vocal channel of a song is either heavily attenuated or outright eliminated. And it turns out that if I twist the headphone connector around enough, I can likewise ditch the karaoke channel and get the vocals.

The novelty doesn’t last very long, but fortunately I can get stereo back by pulling the connector out slightly. One side is slightly attenuated as a result, but it’s better than being completely blindsided in a game.

I was late in getting home last night, like pretty much everyone else. I was one of those thousands of people that crowded Yonge and Bloor, although I wasn’t so silly as to step into the middle of the street and block traffic and shuttle buses.

Times like these, it’s good to not have tunnel vision (the irony). I was entertaining the idea of slipping back into the station, doubling back to the Spadina line via the Bloor-Danforth trains, and going north to Lawrence West station. I could then head east to Lawrence station where the subway was still operating northbound. A lot of people did wind up doing something similar, and it’s a shame that more didn’t.

I, on the other hand, took the Bloor line east instead, because east was where I needed to be anyway. I haven’t been on the Bloor line in a while, and the sad truth is I’ve been spoiled by the Yonge-University line’s speed and longer inter-station distances. I’m not sure how anyone could be spoiled by Yonge-University, but there you go.

As I stepped out of the subway station the other day, I think I saw a bike theft in progress. The thief was riding in the middle of the road, and narrowly missed an oncoming (blue) University Health Network bus. The victim ran past me on the sidewalk shouting.

I’m not sure how that went over seeing as how a police station is in the direction the bike was traveling, but I didn’t exactly stop to see.

Not that big a fan of bicycles myself; bike lanes here can safely accommodate only one, while sidewalks can be 4 persons wide along main avenues. Plus there’s the bonus of not having a bicycle to safeguard, although grad students get to store their bicycles in the grad common area, or potentially their lab/office.

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. 0×1D). 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.

So for various reasons, it turns out that I don’t really need Reed-Solomon codes for what I’ll be doing, but I still have more than a passing interest in the decoding side of things, if only for hobby reasons.

You can make the case that the fundamental building block for a Reed-Solomon decoder is the finite field multiplier. Addition in GF(2^m) is easy — just xor — but multiplication is another story entirely. The multiplier itself is dependent upon the field primitive polynomial, so that’s why you don’t see embedded FFM blocks on an FPGA, or even a general purpose processor for that matter.

That may change in the future when Intel introduces AVX with its cryptography accelerating instructions, but even then, from what little I can understand, it doesn’t sound like a single instruction does FFM on a register; you may still have to do the modulo reduction yourself.

Anyway, I’m here today to talk about hardware FFM’s, specifically on 8-bit operands. Google has a tough time finding information on how to design a FFM, although I suppose it all depends on how you ask it. You can find some implementations, like on OpenCores, but I’m not that enthusiastic about having to register for a once totally open site (you can try your luck with BugMeNot though), plus implementations rarely ever convey how they were created.

I finally found a fairly friendly method, in a paper by A. Reyhani-Masoleh and M. A. Hasan. See Low Complexity Bit Parallel Polynomial Basis Multiplication over GF(2^m).

Note that “FFM”, “finite field”, or “Galois” are nowhere to be found in the title. I suppose I am unfamiliar with the nomenclature, which is what made searching for information more difficult.

I think it should also be noted that IEEE papers are generally not freely available, so if it weren’t for Dr. Reyhani-Masoleh’s generosity, you’d have to access the paper through your own, or university’s, subscription to IEEE Xplore.

For the ASIC layout folks, the paper details a very regular structure for the multiplier, so bonus.

From a design standpoint, there are three variables. Two of them, the d and e vectors, depend only on the bit-width so they are constant regardless of the primitive polynomial. How they are combined is determined by the transpose of the Q matrix, and to get at Q you need to solve equation (5).

The elements of Q are constrained to be either 1 or 0, so multiplication is really an on/off operation, and addition is xor. At least for small values of m (the m in GF(2^m)) you can brute force the solution. Also, when working out d and e from the Toeplitz matrices, multiplication is the and operation.

All vectors are indexed starting from 0, i.e. e = [e₀, e₁, ... , e_m-2]. Bit-level multiplication is accomplished with an and gate.

The algorithm lends itself well to code generation, so I wrote my own Python functions to generate and verify the basic bit-level equations. With a bit of find/replace, it’s easy to just port those over to something like VHDL. Here’s a link for a 0×1D multiplier in GF(256), i.e. P(x) = x⁸ + x⁴ + x³ + x² + 1. I think it should synthesize, but without running it through Quartus or ISE, I can’t say for sure. Until I get my hands on an FPGA development board, I’m not really motivated to install either of those packages.

In Part 2, I’ll post my Python code, which I’m more confident in. For now, enjoy the multiplier, whose polynomial is used in ATSC, WiMAX, and DVB Reed-Solomon codes.

Opinions vary, but a TTC subway extension northbound was needed yesterday, or 5+ years ago (and don’t get people started about the extension to York University).  If we’re lucky, we’ll see an extension to the Yonge line north to Highway 7 in eight years (see second last page), of which only five are actual construction.

And if you look at page 7, you’ll notice that this extension is only 6.5 kilometers. So 6.5 km in 8 years. If you believe in Wikipedia, this is something amounting to an improvement over the last extension — the Sheppard line — which was 5.5 km in 8 years.

I don’t know about you, but this seems downright atrocious. To put things in a bit of perspective, construction on the Chunnel was completed in 6 years. So in the time it takes to extend the Yonge line 6.5 km, plus one more year, others have built roughly 50 km of track underwater. Should we, perhaps, be embarrassed?

Okay, so maybe that was a bit of an apple to oranges comparison (and only because the Chunnel is way cooler than a middling subway extension). Comparing subways to subways, in the time it would take to construct our subway extension, the Chinese built an entire line. Line 5 of the Beijing Subway, to be exact, spanning 23 stations and 27.6 km.

In 5 years, the Chinese have also built the first phase of Line 10, and this phase alone is 22 stations and 24.68 km in length.

I mean, come on.

But if there’s a silver lining to all this, is that in their latest expansion, the STM took 5 years to extend their Orange Line 4 km and build 3 new stations. So I guess we can laugh at them for being slow?

For me, the flag presentation during the opening ceremonies of the 2008 Summer Olympic Games was easily its defining moment. It was, really, the epitome of dignity, backstopped by an arrangement that is light years from its revolutionary roots.

And I say all this, knowledgeable of the fact that there was some audio sleight of hand involved.

But you know, I respect the pressure, and the methods, involved in putting on a show, or any kind of display. Sitting in a band, there was no shame in “faking” your way through a technically difficult passage, when the band or a section thereof had to dial down its volume, or if you were just plain tired and you had to stagger play with your chair mate. Whatever it takes to win, right? I suppose, but at the same time, who steps onto the stage to make a fool of themselves? Comedians excepted.

In retrospect, the Italians and the Australians were also feeling heat. We should be so fortunate that, this time around, the admission didn’t come so long after the fact that it doesn’t matter. Maybe.

For those interested, the real voice behind Lin Miao Ke, Yang Peiyi, later performed the same song, backed by the same (recorded) choir, as well as a live children’s vocal ensemble.

So last night, my ISP kicked me off the internet for the rest of the day. Of this, there is little doubt, because some time after midnight, service resumed.

I felt compelled to consume as much of my remaining monthly quota as possible, and I think they caught on. It wouldn’t surprise me if others were attempting the very same thing. I was approaching 20 GB of total traffic when things just ground to a halt. I rebooted my router, I power cycled my modem. No dice.

Occasionally, there would be a burst of speed so I could load the rare web page, but for the most part I was pretty much being denied service. If you squint really hard, you could call it throttling.

Lesson learned: start the spree in advance, and limit to 15 GB days to be on the safe side.