G_G’d by overthinking…

After 3 weeks of not having a Sun-legacy account at Oracle, I finally got to do real work this week. I was charged with writing some Verilog common modules for the ASIC the group’s working on.

One of these modules was the Parity generator/checker. The basic concept of a parity generator/checker is that, a device on an integrated circuit (IC) communicates with another via electrical signals through interconnects. While these signals are traveling through the interconnects, noise can corrupt and change the signal value (which is either 0 or 1). So when the receiving device gets the message, it would want to know whether it is corrupted.

A good way to check is for the first device to send a bunch of “parity bits”, which are computed from the actual values. This way, the receiving device can calculate the parity bits from the received message, and compare those parity bits against the parity bits it received. If the calculated parity bits don’t match with the received parity bits, then the receiver knows an error has occurred.

Now there are many ways one can generate parity bits. Usually this is done by a function called ‘XOR’.  XOR(A,B)=1 if A!=B. XOR(A,B)=0 if A==B. This operation can be done to an arbitrary number of bits within a message of n-bits.

Because of this, for a message of n-bits, we can have parity bits of varying lengths, depending on the application. My job was to write a module that can generate the write parity bits, given the message length n, and parity-length p.

The algorithm I decided on is basically have a group length of g, obtained from the integer division of n/p. Then the parity bits would be obtained from taking successive g bits of the message (the last group would have n-g*(p-1) bits). Since a divider is very expensive in hardware, I devised a scheme to right shift both n and p, until p=1. At which point g is taken to be whatever m becomes at the moment if p is even, or whatever m becomes minus 1 if p is even.

This was a pretty elegant algorithm in my opinion. However, to fully implement this in hardware, I would have to use a bunch of flip-flops and a clock signal and make sure that the timing is correct, which involved figuring out the timing of the generate function in Verilog.

Upon which I asked my supervisor and learned that, only modules generating parity bits from a predetermined set of n and p would be instantiated…this means I don’t have to do any of that fancy bit-shifting…and that I could simply use the ‘/’ function in my code, since Verilog would figure out the quotient upon instantiation and before hardware synthesis.

This post seems a bit convoluted…but I just want to remember my stupid mistake (even though I learned a lot about parity and hardware division in the process). Maybe someone may find the algorithm useful…


About collapsedwavefn

I have a lot of thoughts. Some of them I'd like to share.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s