Mind-boggling math: BCD (binary coded decimal)
Over the last few months I've come to the conclusion that most of us have an innate faith that we understand the concepts behind BCD (binary coded decimal), but that in reality the majority of us don't have a clue.
Why is BCD of interest? Isn't all data stored as binary floating-point? Well, actually, no, it's not. As fate would have it, more of the world's data is stored in BCD, or one of its more efficient cousins such as Chen-Ho encoding, than in any other form. Apart from anything else, this is because most financial data has to be represented this way by law. (Financial institutions often need to perform calculations involving tenths of dollars or tenths of cents, but the binary equivalent of 1/10, for example, is a repeating pattern of 1s and 0s that degrades accuracy over the course of multiple operations.)
Furthermore, although they may not be as compute-efficient as their binary-floating-point counterparts, in many ways BCD representations are a whole lot easier to work with. In fact, I was amazed to learn that just about every handheld calculator on the planet—even the "scientific" and "engineering" versions—is based internally on BCD representations.
Of course, the core concept underlying BCD is simple: We use the binary patterns 0000 through 1001 in a 4-bit nybble (or nibble if you wish) to represent a decimal digit with a value of 0 through 9 (). And that's all there is to it…not!
Let's assume that we are using an 8-bit byte to represent two BCD digits (): What range of numbers can we support? Well, if we opt for an unsigned form in which we can represent only positive values, then #00 to #99 equates to 0 to +99 in decimal (). (Note that we'll use the '#' character to indicate BCD values.)
When it comes to representing negative numbers, there are two main possibilities. The first is a sign-magnitude form, in which a 0 or a 9 in the most-significant BCD digit indicates a positive or negative value, respectively, while any remaining digits (just one in our example) represent the magnitude. Thus, in the case of our 2-nybble byte, we can represent #00 through #09 and #90 through #99 in sign-magnitude BCD, which equates to +0 through +9 and –0 through –9, respectively (). In addition to the fact that we now have positive and negative versions of zero, this approach offers a somewhat limited range of values and just feels clunky.
Some folks take the previous concept a bit further and "munge" it into a sort of pseudo-tens-complement form, but it really isn't. In the case of true tens complement, the most-significant digit represents both a sign and a quantity. For example, with regard to our 8-bit byte, the BCD values #00 through #49 would be used to represent positive values in the range 0 through +49. A BCD value of #50 actually represents a negative value of –50; a BCD value of #51 represents –50 + 1 = –49; a BCD value of #52 represents –50 + 2 = –48; and so on, up to a BCD value of #99 which represents –50 + 49 = –1. Thus, using this scheme, our two-BCD-digit byte can be used to represent decimal values in the range –50 to +49 ().
Pretty cool, eh? In my next column we'll look at performing math operations using these tens-complement values, and I will pose a question that had me pondering furiously for several days.
Clive "Max" Maxfield is the co-author of "How Computers Do Math" (ISBN: 0471732788) featuring the pedagogical and phantasmagorical virtual DIY Calculator (www.DIYCalculator.com). In addition to being a hero, trendsetter, and leader of fashion, Max is widely regarded as being an expert in all aspects of computing and electronics (at least by his mother).