RPN Scientific Calculator: Tweaks

Recently I was able to get some new components and took the chance to make a few tweaks to the calculator. First of all, I hooked up a new 20x4 character LCD to replace the 16x2 version I was using before. It is gray with black letters and I like how it looks. With this I will be able to make the bottom row of the screen a menu like the kind some of the later HP calculators use. The LCD itself came with male headers so it can be plugged into a breadboard, but there was no convenient place to put it so I decided to run wires from the headers to the breadboard instead. The LCD worked fine at first but quickly became corrupted after I wound the wires into a loop to make them neater. This was causing crosstalk and the problem disappeared when I separated the wires.

I also added a CMOS 555 timer to generate the negative voltage for the LCD. This frees up a microcontroller pin that I am now using to independently drive the input shift register of the RAM. Now I can read the external RAM and the keyboard at the same time without worrying about coordinating interrupts. In order to save energy I decided to use the smallest capacitor and the largest value resistors I could for the timer. Unfortunately, none of the resistor values I had on hand would give me the 30 Hz or so the microcontroller was generating. 48 Hz was the closest I could get using a 0.1 uF capacitor and 100k ohm resistors for R1 and R2. Adding a 470 ohm resistor to the output of the 555 gave a good contrast and should also keep the contrast constant if I try to run everything from a battery later.

The last thing I did was to expand the CORDIC tables to 32 bits wide instead of 16. Using a 16 bit wide table gives around 14 decimal places of accuracy which is sufficient for calculating logarithms. A problem arises, however, when that logarithm is used to calculate things like exponents because those 14 places of accuracy also include the whole part of the answer. A simple calculation like 8^9 only offers 5 decimal places of accuracy after the decimal since the whole part is 9 digits long. The new version takes about 6 seconds to calculate "atan(tan(37))" This is very slow so I will let the user set the precision in settings.

RPN Scientific Calculator: More CORDIC Routines

After finishing the CORDIC routine for logarithms I started on the CORDIC routine for trig functions. For this I needed a different look up table and a different function, but it didn't take up much room in the flash. The table for pre-computed logarithms is stored compactly in flash and the same routine that unpacks it into the external memory is also used to unpack the trig table. With this I can calculate sine, cosine, tangent, and arctangent. It should also be possible to calculate arcsine as well but I haven't tried yet.

To test these new function I tried calculating atan(tan(37)). When using 16 decimal places for the calculations this gives the answer 36.9999999999999781, which is pretty accurate. Unfortunately, this took over two seconds, which is just too slow. The logarithm and powers of e functions were at least twice as fast. In order to speed things up I tried to eliminate as many reads and writes to the external memory as I could. One thing I didn't notice when I wrote the original functions is that the loop condition for a for loop is recalculated each iteration. When the condition depends on a variable in external memory, the variable is fetched on every iteration, which is wasteful if the variable hasn't changed. After changing the code to use local copies of external variables whenever possible, I was able to cut down external memory access by almost 25%.

25% wasn't quite enough so I looked at the code I was using to right shift. This allows me to divide numbers by 2 quickly but takes some extra coding since shifting in BCD is a little more complicated than a normal binary shift. Because of the extra work involved in keeping everything straight during BCD shifting, I was doing shifts one bit at a time. This means a 58 bit shift, for example, would simply do 58 shifts of 1 bit each. As you can imagine this is not efficient and was a big part of the slow down in the code. My solution was to use as many 4-bit shifts as needed, then a few 1 bit shifts at the end to finish it off.

Shifting by 4 bits in BCD is fairly easy. As you probably know, shifting by 4 bits is the same as dividing by 16, and dividing by a number (16 in this case) is the same as summing the results of dividing each decimal place by that number. Since there are only 10 possibilities (0-9) for each decimal place, I stored the results of dividing each possibility by 16 in a look up table and used that to sum the results. Here is an example:

789 ÷ 16 = 700/16 =   4375
                  80/16 =     5000
             +     9/16 =      5625
                               49.3125

The values 4375, 5000, 5625, etc are stored in the look up table. The sum of these results are stored in local RAM since 6 bytes is enough to keep track of the summing long enough to deal with any carries before finally writing the last byte to the external RAM. Doing it like this I only need to read and write every decimal place once per 4-bit shift. This cuts down the number of external memory accesses down to almost one third of what it was at the beginning and allowed me to calculate atan(tan(37)) in a little over a second. All of this fits in 8.1K of Flash meaning I just broke the halfway mark of what the MSP430G2553 chip I am using can hold. If there is any space left over at the end, I would like to implement a similar 8-bit shift routine as well to speed things up even more.

RPN Scientific Calculator: Division and Logarithms

After rewriting the multiplication function I started on the division routine. There are several ways to do this. I used the subtract and shift method. It takes up a little more than 150 lines of code which makes it about twice as big as the multiplication routine. Unlike with the other operations, with division a maximum number of decimal places has to be specified. It seems unlikely that I would ever need more than 16 places, which makes me think a fixed place format might have worked too. This is still possible if I need to shrink the program size.

The next step is to implement logarithms and powers of e. This will be useful on its own but will also let me calculate powers and roots. One way I found to calculate logarithms is with a Taylor series like this: 

ln[(1+x)/(1-x)]=2(x+x³/3+x⁵/5+x⁷/7+....)

This seems ideal since it only requires one loop and several multiply and divide operations which shouldn't take up much room in Flash. Even with the the MSP430 running at 16MHz, it rook over 3 seconds to calculate ln(7). In an effort to speed things up I examined the code for multiplying and dividing but didn't find much to improve. One thing I did change was the addition routine. I was adding a 0 to the beginning of every result so that there would be room for a 1 if I needed to carry. However, in most cases the 0 wasn't needed and when doing repeated additions during multiplication, the 0s accumulated at the beginning of the result wasting memory. Removing these 0s wasted time so I changed the addition code to only add the 0 when necessary. This still didn't make it much faster, though.

Next, I ran the code on my PC and noticed that it needed to access the external memory over 2 million times to calculate the logarithm to 16 decimal places. Clearly this was the bottleneck. The next idea I tried was the CORDIC method which is ideal for small microcontrollers like the MSP430. This uses a precomputed table and only needs adds and bit shifts, two things that microcontrollers can do much more efficiently than multiplying and dividing. Using this method I can calculate e^x and ln(x) for a wide range of values in less than one second because it only needs about 50,000 accesses to the external memory.

After I finished the ln function but before I started on the e^x function, I noticed that the program was already 6.5k. This is a little concerning since 16k is the max size for the program and there are still many more features to add. One thing that can reduce size is the static keyword. Making all my functions static shrunk the program size down to only 3.7k. After adding some more entries to the CORDIC table, improving the ln function, and adding the e^x function, the program size was back up to almost 6.5k again. This seems very strange since the program is now almost 1,000 lines and the ln functions only takes 50 lines. In fact commenting out the ln function reduces the program down to only 4.4k. Why this one small function should suddenly add more than 2k to my code is not clear but I hope to figure it out soon.

RPN Scientific Calculator: Software Update

Work continues on my calculator. Each byte of a BCD number now holds only one digit instead of two. This eliminates the functions that were needed to align and pad numbers when every byte held two numbers. It also makes calculations a little simpler and reduces the amount of space the functions take up in the Flash.

Another improvement is that arrays can be stored in the external SRAM and accessed similarly to how internal memory is accessed. To read or write anything to the external memory a function has to be used. That means a simple equation like this:

X+=Y*Z-Q;

would become this if those variables were stored externally:

 RAM_Write(X,RAM_Read(X)+(RAM_Read(Y)*RAM_Read(Z)-RAM_Read(Q));

This is difficult to decipher and inconvenient to use when writing code. My solution was to make a small program that preprocesses the source code and replaces any variables that should be stored externally with their corresponding read and write commands. These variables are marked off with #pragma directives. #pragma is a note to the compiler to do something special that may be specific to that compiler. If the compiler doesn't recognize the directive, it is ignored. Here is an example of what the preprocessor would do.

This is unprocessed code:

void puts(unsigned char *msg)
{
     #pragma MM_VAR msg
     for (int i=0;msg[i];i++) putchar(msg[i]);
}

int main()
{    
     #pragma MM_OFFSET 200
     #pragma MM_DECLARE
     unsigned char text1[30];
     unsigned char text2[30];
     #pragma MM_END

     text1[0]='A';
     text1[1]=0;
     puts(text1);
}

 This is preprocessed code:

void puts(unsigned char *msg)
{
     #pragma MM_VAR msg
     for (int i=0;RAM_Read(msg+i);i++) putchar(RAM_Read(msg+i));
}

int main()
{    
     #pragma MM_OFFSET 200
     #pragma MM_DECLARE
     unsigned char *text1=(unsigned char*)200;
     unsigned char *text2=(unsigned char*)230;
     #pragma MM_END

     RAM_Write(text1+0,'A');
     RAM_Write(text1+1,0);
     puts(text1);
}

Arrays are converted to pointers that store offsets to the external memory. This way none of the function prototypes have to be changed. The code should work the same way whether the variables are stored in internal or external RAM. External memory can be turned off if needed to make tracking down bugs easier. One disadvantage to this is that function arguments must be either internally or externally stored but a function can't accept both types for one argument. For things that need both I will need a wrapper function. The preprocessor doesn't support all of the C standard since I only spent about a day on it. Adding support for all of the possible ways there are to access a variable would take a lot more work and I wouldn't be likely to use that functionality anyway. Things like variable names that span multiple lines or variable assignments inside of other statements aren't supported but I didn't end up using any of those features in my code.

The new code for adding and subtracting BCD numbers fits in about 2K, including LCD driving code. Using the preprocessor to store all the values externally adds another 500 bytes. The code for multiplication is also much smaller than the last version.

RPN Scientific Calculator: External RAM

The last part of the hardware needed to complete the calculator is external RAM. Even if it does not have any programming capabilities, it will still need more RAM for the stack than the 512 bytes an MSP430G2553 has. Microchip makes 128K SRAM chips that are small and accessible over SPI that would work well for this project. However, I had this parallel SRAM chip from Alliance left over with nothing in mind for it and I decided to use it instead. It needs 8 pins for data so I am using one 74HC595 for output and one 74HC165 for input. The 17 address pins are driven by two more 74HC595s. This only gives 16 outputs so the 17th address pin is tied directly to a microcontroller pin. This will allow me to have two banks of memory, although I don't have any use for that at the moment. Putting this together took a lot of wiring but it wasn't too difficult.

Accessing large amounts of memory like this over serial can be a speed bottleneck, so I decided to use the USCI module of the MSP430 to do hardware SPI and speed up transfers. After learning how it works I saw that it is really easy to set up and convenient to use. As with the shift registers that read the button matrix, I decided to share the clock but to use different latches. The USCI has separate data in and data out pins so those aren't shared. This is handy for reading the 165 shift register because after it is latched you can just push a dummy value out then read the USCI receive buffer. There is a flag to control whether the USCI stores data in MSB (Most Signicant Bit) or LSB format but it can't be set separately for the input and output buffers. This means data goes out with the right orientation but comes in backwards. To remedy this I hooked up the data inputs of the 165 in reverse order to the data bus of the SRAM.

To test the speed of this setup I made a test program to write a pattern to every byte of the RAM then read it back and make sure the values are as expected. This worked fine at 1MHz but the LCD glitched when I tried running at 16MHz. After I fixed that I was able to finish the whole test in about two seconds. That is pretty good throughput for a calculator!

Now that the RAM is working, the hardware part is finished. It is good that I don't have anything else to add since all of the microcontroller pins are taken up. In fact the input shift registers for the SRAM and keypad share the same latch since it is unlikely that they will ever be used at the same time. If I need anything else I will have to use the two remaining bits in the keypad shift register (the keypad only has 6 rows and the LCD only needs 5 bits) or add another shift register. Now I can focus on the programming and worry about hardware again when it is time to make a circuit board. Here is what the hardware looks like now:

RPN Scientific Calculator: Keypad

The next step of the hardware for my calculator is a keypad. I finished this several weeks ago but I haven't posted anything about it because I didn't have any pictures until now.

As you can see, the construction is pretty simple. My local shop had a new kind of perfboard that I wanted to try. It seems to be a little stronger than the kind I used before but still not really stiff like some of the high quality ones I have seen. It took some time to solder this together but it worked well in the end. Only one button connection had to be resoldered.

The circuit is a standard button matrix. A signal is sent through each of the green lines in turn and if any of the buttons are held down the signal will travel out of one of the yellow output lines and be recorded. Each button has a diode to ensure that the signal can only go one way. As you can see from the back side of the board, the columns are connected by solder and the rows by yellow jumpers. After I had soldered most of the columns, I realized that the two legs on each side of this kind of button are connected internally and don't have to be soldered together. The next time I make a button matrix I will leave them unsoldered so I will have room to make the rows out of solder as well. Avoiding jumper wires like I used here will make soldering simpler.

To read the matrix I am using a 74HC165 and a 74HC595 shift register. Output shift registers can easily be chained together but I also found out that an output and input shift register can be chained together as well sharing the same data, clock, and latch lines. Here I decided to use separate latches since the 165 is reading the output of the 595 but they do share data and clock lines which uses less microcontroller pins

Most of the time the shift registers will go unused since scanning the matrix only takes a fraction of a second. To save even more pins I decided to drive the LCD using the 595 shift register as well. This works out as long as communicating with the LCD and reading buttons never overlaps. I will have to take this into consideration if I decide to use an interrupt to read buttons. This also fixed a strange and unsolved issue that would occasionally cause the LCD not to receive commands when it was being driven directly by microcontroller pins.

RPN Scientific Calculator: Multiplication

The next step of the software for my calculator is multiplication. In Binary Coded Decimal (BCD) this is fairly straightforward. Every decimal place of the first number has to be multiplied by every decimal place of the second number. The tricky part is keeping the results lined up and then putting the decimal point in the right place at the end. Here is an example running on the MSP430:

One advantage of BCD is that it avoids the rounding errors that occur in floating point calculations. This quickly becomes apparent when you start multiplying decimal numbers. Even in this example using fairly small numbers there is a rounding error:

Floating Point:
835.2533 x 907.042 = 757609.823739

Binary Coded Decimal
835.2533 x 907.042 = 757609.8237386

For most uses floating point offers enough precision but a scientific calculator should be as accurate as possible, so BCD is a better choice.

While working on this I was able to find a bug in my code for addition and fix it. I also added a function to shift numbers one decimal place so they will be aligned properly for multiplication. This routine is sometimes necessary since each byte holds two decimal numbers. Routines like this take up space in Flash, which is limited to 16K on value-line MSP430s. One way to avoid having to shift numbers is to let each byte represent one number instead of two. Although this would use twice as much RAM, it would simplify programming and use less space in Flash. This is what I will do if I run out of room for the firmware. Right now I plan to use 128K parallel SRAM chips from Alliance, so running out of RAM wouldn't be a problem. (Of course 8k of SRAM would have been enough but I don't have any of those with me.) Another option would be to write all or part of the BCD routines in assembly. This would help a lot since the MSP430 has an op-code to add BCD numbers. It also handles carries natively which is more efficient than storing it in a variable and checking it explicitly like my code does now. Currently, the program is only 3.3K including the part that handles the LCD. How much I can fit in the remaining Flash will determine what changes I make.