Silician Sketchbook

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 0x1D 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.

Simon Haykin is old. Without any estimate whatsoever, finally seeing him at a distinguished lecture last Thursday (in the Mechanical Engineering building) was even more shocking. All I knew was that he wrote digital signal processing books – books that I managed to get by without purchasing because homework questions were posted in full online. I also inferred, from a book I saw sitting on a bookshelf during a co-op term, that he was the expert on adaptive signal processing, specifically adaptive equalizers.

In fact, the subject of his talk was an extension of something more fundamental than adaptive equalization. In his preamble while someone searched for a microphone (which he wound up not needing too much), he talked about how he got into adaptive signal processing in the first place. Adaptive meant flexibility, a robust means of getting a handle on an unknown and constantly changing environment. But adaptive signal processing, like equalizers, just means handling channel conditions. He was going for something much more ambitious: equalizing the channel, adjusting transmission and reception for optimal throughput/spectral efficiency/power, even finding unused blocks of spectrum with which to communicate in.

I was aware of software defined radio around 2002, right around the time when Haykin began a serious push for research in the area. SDR is only a means, though, and at the time was the domain of amateur radio for improving reception of narrowband voice or simple digital transmission. Cognitive radio, which was the case that he was making that afternoon, is a more general concept. How one goes about it, through hardware, software, or a mix, is implementation details.

The lecture was all about why cognitive radio (and cognitive radar), and some of the projects ongoing at his lab in McMaster University, so the whole thing bordered on non-technical. I had to leave before he got to the last part.

In his view, the holy grail of cognitive radio is to have the transceiver learn, through feedback of channel conditions and frequency use, in something almost like how humans learn, the implication being that our brains are like Bayesian systems. My interpretation is that through continuous learning, the transceiver can figure out if there are users around, or what kind of noise is corrupting which parts of the spectrum, and select modulation, bandwidth, transmit power, and forward error correction as appropriate. The US army has long been grappling with implementing such a flexible system under the JTRS.

He paraphrased Nokia’s CEO as saying that, in the next 10 years or so, wireless communications networks, 4G and beyond, will take place on cognitive radio platforms. That’s compelling, but pretty ambitious especially from a mobile terminal’s point of view. Cognitive radio will likely be achieved by more software than hardware, but overall both will be thrown at the problem in large quantities, the implication being that power consumption goes way up all else being equal. Mobile cognitive radio boosters are betting on advances in battery life (massive capacitors, miniature combustion engines or fuel cells) as well as extremely low power transistors that can deliver the same or better switching speed compared to today’s fab processes (carbon nanotubes?).

I continue to follow SDR to some extent, not because of the benefits in being flexible, but for the reasons that I think FPGA’s are cool despite being a bit clunky and generally inferior to full-custom ASIC design: both lower barriers to entry.  A combination of SDR and FPGA technology enables something like GNU Radio, which enables people to build their own ATSC tuners.  Sometimes the hardest part in doing radio signal processing is getting an infrastructure to do radio signal processing.