Archive for January, 2010

Voltage gradients in embedded systems

Sunday, January 24th, 2010 Nigel Jones

Today’s’ post was prompted by an excellent comment from Phil Ouellette in a recent newsletter from Jack Ganssle. In a nutshell Phil was advocating strobing switches with an alternating voltage waveform, rather than a direct voltage in order to minimize corrosion and premature switch failure. This happens to be an area in which I have some experience and so I thought I’d extend the concept a little bit and also give you some food for thought.

The basic idea behind Phil Ouellette’s comments is that if one has a bias voltage between two pins (such as between switch contacts), and if this bias is always in one direction (i.e. DC), then the bias can act so as to drive an electrochemical reaction. The exact results of this electrochemical reaction vary (corrosion, dendrite growth etc.), but the net result is normally the same – namely an unwanted short circuit between two pins.

These problems arise particularly on products that have to operate in humid environments and / or products that have to spend a very long time under power over their expected operational life.

So what can be done about this? Well the most important thing to understand is that it is voltage gradient (volts per meter) that is the driving force in this problem and that furthermore, voltage gradient is a vector quantity and thus its direction is important. With this understanding, it should be clear that to minimize these types of problems, one has to minimize the integral of the voltage gradient over time. To do this one has three basic choices:

  1. Minimize the voltage
  2. Maximize the separation
  3. Modulate the voltage

Let’s take a look at each of these in turn:

Minimize the voltage
Clearly technology is progressing in the right direction for us here, as 5V systems are rapidly becoming extinct and 1.8V systems becoming more common place. Thus all other things being equal, the voltage gradient between any two pins on a 5V system will be 2.8 times greater than on a 1.8V system. Thus if you are designing a system where corrosion is a concern you will do yourself a big favor for opting for as low a voltage system as you can. However, see the caveat below.

Note also that given that what counts is minimizing the voltage over time, it follows that you can normally improve the system performance by powering down systems that are not needed at any given time. This also of course saves you power and thus is a highly recommended step.

Maximize the separation
This is by far and away the toughest problem. Twenty years ago, ICs ran on 5V and had 0.1 inch lead spacing, giving a maximum voltage gradient between pins of 5 / 0.00254 = 1969 V/m. Today, a typical 1.8V IC has a lead spacing of 0.5 mm giving a maximum voltage gradient of 1.8 / 0.0005 = 3600 V/m. Thus the voltage gradient between pins on a typical IC has gone up – despite the decrease in the operating voltage. Thus if selecting a low voltage part means that you must use a fine lead pitch part, then you are almost certainly shooting yourself in the foot!

Other areas where you can increase separation without too much pain is in the selection of passive components. For example a 1206 resistor has a much lower voltage gradient than an 0402 resistor, and an axial leaded capacitor is usually preferable to a radially leaded device. As a result, when I’m designing systems that have potential corrosion issues I really prefer to use larger components. Of course this can put you into conflict with marketing and production.

Modulate the voltage
The method suggested by Phil Ouellette is reasonably straightforward for something like a switch. However, if one generalizes the problem to all the components on the board, then it becomes a much more complex problem. For example, consider an address bus to an external memory. The most significant address lines will presumably change state at a much lower frequency than the low order address lines. Indeed it is not uncommon for a system that has booted up and is running normally to be in a situation where the top two or three address lines never change state. Now if they are all at the same state (for example high), then no voltage gradient exists between them and so there is no problem. However if the lines are say High – Low – High, then the voltage gradient is as bad as it gets – and you have a potential problem. There are of course various solutions to this particular problem. The easiest solution is to ensure that the most significant address lines are routed to non contiguous pins on the memory chip (sometimes known as address scrambling) so that high frequency address lines are adjacent to low frequency lines. A much more difficult problem is to link the application so that all address lines are guaranteed to toggle at a reasonable frequency…

Another interesting example comes when one performs microcontroller port pin assignment. Normally one has little choice about certain pin assignments – but for the remainder one has free rein. The next time you find yourself in this position you may want to try performing the assignment so as to minimize the voltage gradients. I think you will find it to be a very challenging task.

Anyway, I hope this has given you some food for thought. Please let us know via the comments section if you have faced any of these types of problems and how you solved them.

Home

A tutorial on lookup tables in C

Monday, January 11th, 2010 Nigel Jones

A while back I wrote a blog posting on using lookup tables as a means of writing efficient C. Since then, every day someone looking for basic information on lookup tables ends up on this blog – and I suspect goes away empty handed. To help make their visits a bit more fruitful I thought I’d offer some basic information on how best to implement look up tables in C. Given that this blog is about embedded systems design, my answers are of course embedded systems centric.

So what is a lookup table? Well a lookup table is simply an initialized array that contains precalculated information. They are typically used to avoid performing complex (and hence time consuming) calculations. For example, it is well known that the speed of CRC calculations may be significantly increased by use of a lookup table. A suitable lookup table for computing the CRC used in SMBUS calculations is shown below. (Note that the SMBUS consortium refers to their CRC as a PEC)

uint8_t pec_Update(uint8_t pec)
{
static const __flash uint8_t lookup[256] =
{
0x00U, 0x07U, 0x0EU, 0x09U, 0x1CU, 0x1BU, 0x12U, 0x15U,
0x38U, 0x3FU, 0x36U, 0x31U, 0x24U, 0x23U, 0x2AU, 0x2DU,
0x70U, 0x77U, 0x7EU, 0x79U, 0x6CU, 0x6BU, 0x62U, 0x65U,
0x48U, 0x4FU, 0x46U, 0x41U, 0x54U, 0x53U, 0x5AU, 0x5DU,
0xE0U, 0xE7U, 0xEEU, 0xE9U, 0xFCU, 0xFBU, 0xF2U, 0xF5U,
0xD8U, 0xDFU, 0xD6U, 0xD1U, 0xC4U, 0xC3U, 0xCAU, 0xCDU,
0x90U, 0x97U, 0x9EU, 0x99U, 0x8CU, 0x8BU, 0x82U, 0x85U,
0xA8U, 0xAFU, 0xA6U, 0xA1U, 0xB4U, 0xB3U, 0xBAU, 0xBDU,
0xC7U, 0xC0U, 0xC9U, 0xCEU, 0xDBU, 0xDCU, 0xD5U, 0xD2U,
0xFFU, 0xF8U, 0xF1U, 0xF6U, 0xE3U, 0xE4U, 0xEDU, 0xEAU,
0xB7U, 0xB0U, 0xB9U, 0xBEU, 0xABU, 0xACU, 0xA5U, 0xA2U,
0x8FU, 0x88U, 0x81U, 0x86U, 0x93U, 0x94U, 0x9DU, 0x9AU,
0x27U, 0x20U, 0x29U, 0x2EU, 0x3BU, 0x3CU, 0x35U, 0x32U,
0x1FU, 0x18U, 0x11U, 0x16U, 0x03U, 0x04U, 0x0DU, 0x0AU,
0x57U, 0x50U, 0x59U, 0x5EU, 0x4BU, 0x4CU, 0x45U, 0x42U,
0x6FU, 0x68U, 0x61U, 0x66U, 0x73U, 0x74U, 0x7DU, 0x7AU,
0x89U, 0x8EU, 0x87U, 0x80U, 0x95U, 0x92U, 0x9BU, 0x9CU,
0xB1U, 0xB6U, 0xBFU, 0xB8U, 0xADU, 0xAAU, 0xA3U, 0xA4U,
0xF9U, 0xFEU, 0xF7U, 0xF0U, 0xE5U, 0xE2U, 0xEBU, 0xECU,
0xC1U, 0xC6U, 0xCFU, 0xC8U, 0xDDU, 0xDAU, 0xD3U, 0xD4U,
0x69U, 0x6EU, 0x67U, 0x60U, 0x75U, 0x72U, 0x7BU, 0x7CU,
0x51U, 0x56U, 0x5FU, 0x58U, 0x4DU, 0x4AU, 0x43U, 0x44U,
0x19U, 0x1EU, 0x17U, 0x10U, 0x05U, 0x02U, 0x0BU, 0x0CU,
0x21U, 0x26U, 0x2FU, 0x28U, 0x3DU, 0x3AU, 0x33U, 0x34U,
0x4EU, 0x49U, 0x40U, 0x47U, 0x52U, 0x55U, 0x5CU, 0x5BU,
0x76U, 0x71U, 0x78U, 0x7FU, 0x6AU, 0x6DU, 0x64U, 0x63U,
0x3EU, 0x39U, 0x30U, 0x37U, 0x22U, 0x25U, 0x2CU, 0x2BU,
0x06U, 0x01U, 0x08U, 0x0FU, 0x1AU, 0x1DU, 0x14U, 0x13U,
0xAEU, 0xA9U, 0xA0U, 0xA7U, 0xB2U, 0xB5U, 0xBCU, 0xBBU,
0x96U, 0x91U, 0x98U, 0x9FU, 0x8AU, 0x8DU, 0x84U, 0x83U,
0xDEU, 0xD9U, 0xD0U, 0xD7U, 0xC2U, 0xC5U, 0xCCU, 0xCBU,
0xE6U, 0xE1U, 0xE8U, 0xEFU, 0xFAU, 0xFDU, 0xF4U, 0xF3U
};
pec = lookup[pec];
return pec;
}

There are several things to note about this declaration.

The use of static
If static was omitted, then this table would be allocated and initialized on the stack every time the function is called. This is very slow (and hence self defeating) and will most likely lead to a stack overflow on smaller systems. As a result, a lookup table that is not declared static is almost certainly a mistake. The only exception that I am aware of to this rule is when the lookup table must be used by multiple modules- and hence must be declared so as to have global scope.

The use of const
By definition a lookup table is used to read data. As a result, writing to a lookup table is almost always a mistake. (There are exceptions, but you really need to know what you are doing if you are dynamically altering lookup tables). Thus to help catch unintended writes to a lookup table, one should always declare the array as const.

Note that sometimes this is superfluous if the array is forced into Flash, as described below.

The use of __flash
If one provides no memory modifier (such as __flash) then many embedded systems compilers will copy the array into RAM (even though it is declared as const). Given that RAM is normally a much more precious resource than Flash, then this is a very bad thing. As a result, one should give a memory specifier such as __flash to force the array to be kept in Flash. Note that the syntax for doing so varies by compiler vendor. __flash is an IAR extension. I’ve also seen CODE (Keil) and ROM (Microchip) among others.

The use of a size specific data type such as uint8_t
Almost by definition lookup tables can consume a lot of space. As a result it is very important that you be aware of exactly how much space is being consumed. The best way to do this is to use the C99 data types so that you know for sure what the underlying storage unit is. As a result, if your data type is ‘int’ then I’d suggest that you are doing yourself a disservice.

Avoidance of incomplete array declarations
You should also note I have explicitly declared the array size as 256. I could of course have omitted this and had the declaration read as static const __flash uint8_t lookup[] = { …};
However, I strongly recommend that you do not do this with lookup tables, as this is your first line of defense against inadvertently declaring the table with the wrong number of initializers.

Range Checking
In this case, range checking of the array indexer is unnecessary as it is an 8-bit entity and the table is 256 bytes. Thus by definition it is not possible to index beyond the end of the array. However, in general one should always range check the indexer before performing the lookup. If you make your index variable unsigned then you can make the check one-sided which aids in keeping the computation speed high. For example:

#define TABLE_SIZE (27u)
uint8_t lookup(uint8_t index)
{
uint16_t value;
static const __flash uint16_t lookup[TABLE_SIZE] =
{
946u, 2786u, … 89u
};
if (index < TABLE_SIZE)
{
value = lookup[index];
}
else
{
//Handle error
}

}

Examples
So where do I use lookup tables? I’ve already mentioned CRC calculations as a common application. Probably my most common usage is for implementing jump tables. I wrote an extremely detailed article about this which I recommend you read if this is your interest. The third area where I often implement lookup tables is when I need to know the value of some complex function, where the independent variable has a limited set of values. To put this into plain English. If I have a typical 8 or 10 bit analog – digital – converter (ADC) and I need to compute say 6.5 * ln(X) where X is the ADC reading, then I’ll often just declare a lookup table that contains the values of 6.5 * ln(X) for all possible X (0 – 255 in the case of an 8 bit ADC). In this case all I need do is index the lookup table with the value of the ADC and I have my result. (The really observant reader will have noticed that 0 is an invalid input to the ln() function and so my previous statement is not entirely correct. Although this can be handled in several ways including range checking or the use of NaN (Not a Number),  I mention it so as to point out that lookup tables do not absolve you of taking care of corner conditions).

Once you get the hang of using lookup tables, particularly if you embrace the idea of very large lookup tables, then you’ll quickly begin to wonder how you ever got along without them.

I’m sure that visitors to this blog would also appreciate hearing about other real world examples of the use of lookup tables – so feel free to tell the world about your experiences in the comments section.

Home