Chapter 39: Numeration Systems

The expression of numerical quantities is something we tend to take for granted. This is both a good and a bad thing in the study of electronics. It is good, in that we’re accustomed to the use and manipulation of numbers for the many calculations used in analyzing electronic circuits. On the other hand, the particular system of notation we’ve been taught from grade school onward is not the system used internally in modern electronic computing devices, and learning any different system of notation requires some re-examination of deeply ingrained assumptions.

First, we have to distinguish the difference between numbers and the symbols we use to represent numbers. A number is a mathematical quantity, usually correlated in electronics to a physical quantity such as voltage, current, or resistance. There are many different types of numbers. Here are just a few types, for example:

Different types of numbers find different application in the physical world. Whole numbers work well for counting discrete objects, such as the number of resistors in a circuit. Integers are needed when negative equivalents of whole numbers are required. Irrational numbers are numbers that cannot be exactly expressed as the ratio of two integers, and the ratio of a perfect circle’s circumference to its diameter (π) is a good physical example of this. The non-integer quantities of voltage, current, and resistance that we’re used to dealing with in DC circuits can be expressed as real numbers, in either fractional or decimal form. For AC circuit analysis, however, real numbers fail to capture the dual essence of magnitude and phase angle, and so we turn to the use of complex numbers in either rectangular or polar form.

If we are to use numbers to understand processes in the physical world, make scientific predictions, or balance our checkbooks, we must have a way of symbolically denoting them. In other words, we may know how much money we have in our checking account, but to keep record of it we need to have some system worked out to symbolize that quantity on paper, or in some other kind of form for record-keeping and tracking. There are two basic ways we can do this: analog and digital. With analog representation, the quantity is symbolized in a way that is infinitely divisible. With digital representation, the quantity is symbolized in a way that is discretely packaged.

You’re probably already familiar with an analog representation of money, and didn’t realize it for what it was. Have you ever seen a fund-raising poster made with a picture of a thermometer on it, where the height of the red column indicated the amount of money collected for the cause? The more money collected, the taller the column of red ink on the poster.

This is an example of an analog representation of a number. There is no real limit to how finely divided the height of that column can be made to symbolize the amount of money in the account. Changing the height of that column is something that can be done without changing the essential nature of what it is. Length is a physical quantity that can be divided as small as you would like, with no practical limit. The slide rule is a mechanical device that uses the very same physical quantity — length — to represent numbers, and to help perform arithmetical operations with two or more numbers at a time. It, too, is an analog device.

On the other hand, a digital representation of that same monetary figure, written with standard symbols (sometimes called ciphers), looks like this:

Unlike the "thermometer" poster with its red column, those symbolic characters above cannot be finely divided: that particular combination of ciphers stand for one quantity and one quantity only. If more money is added to the account (+ $40.12), different symbols must be used to represent the new balance ($35,995.50), or at least the same symbols arranged in different patterns. This is an example of digital representation. The counterpart to the slide rule (analog) is also a digital device: the abacus, with beads that are moved back and forth on rods to symbolize numerical quantities:

Let’s contrast these two methods of numerical representation:

Interpretation of numerical symbols is something we tend to take for granted, because it has been taught to us for many years. However, if you were to try to communicate a quantity of something to a person ignorant of decimal numerals, that person could still understand the simple thermometer chart!

The infinitely divisible vs. discrete and precision comparisons are really flip-sides of the same coin. The fact that digital representation is composed of individual, discrete symbols (decimal digits and abacus beads) necessarily means that it will be able to symbolize quantities in precise steps. On the other hand, an analog representation (such as a slide rule’s length) is not composed of individual steps, but rather a continuous range of motion. The ability for a slide rule to characterize a numerical quantity to infinite resolution is a trade-off for imprecision. If a slide rule is bumped, an error will be introduced into the representation of the number that was "entered" into it. However, an abacus must be bumped much harder before its beads are completely dislodged from their places (sufficient to represent a different number).

Please don’t misunderstand this difference in precision by thinking that digital representation is necessarily more accurate than analog. Just because a clock is digital doesn’t mean that it will always read time more accurately than an analog clock, it just means that the interpretation of its display is less ambiguous.

Divisibility of analog versus digital representation can be further illuminated by talking about the representation of irrational numbers. Numbers such as π are called irrational, because they cannot be exactly expressed as the fraction of integers, or whole numbers. Although you might have learned in the past that the fraction 22/7 can be used for π in calculations, this is just an approximation. The actual number "pi" cannot be exactly expressed by any finite, or limited, number of decimal places. The digits of π go on forever:

It is possible, at least theoretically, to set a slide rule (or even a thermometer column) so as to perfectly represent the number π, because analog symbols have no minimum limit to the degree that they can be increased or decreased. If my slide rule shows a figure of 3.141593 instead of 3.141592654, I can bump the slide just a bit more (or less) to get it closer yet. However, with digital representation, such as with an abacus, I would need additional rods (place holders, or digits) to represent π to further degrees of precision. An abacus with 10 rods simply cannot represent any more than 10 digits worth of the number π, no matter how I set the beads. To perfectly represent π, an abacus would have to have an infinite number of beads and rods! The tradeoff, of course, is the practical limitation to adjusting, and reading, analog symbols. Practically speaking, one cannot read a slide rule’s scale to the 10th digit of precision, because the marks on the scale are too coarse and human vision is too limited. An abacus, on the other hand, can be set and read with no interpretational errors at all.

Furthermore, analog symbols require some kind of standard by which they can be compared for precise interpretation. Slide rules have markings printed along the length of the slides to translate length into standard quantities. Even the thermometer chart has numerals written along its height to show how much money (in dollars) the red column represents for any given amount of height. Imagine if we all tried to communicate simple numbers to each other by spacing our hands apart varying distances. The number 1 might be signified by holding our hands 1 inch apart, the number 2 with 2 inches, and so on. If someone held their hands 17 inches apart to represent the number 17, would everyone around them be able to immediately and accurately interpret that distance as 17? Probably not. Some would guess short (15 or 16) and some would guess long (18 or 19). Of course, fishermen who brag about their catches don’t mind overestimations in quantity!

Perhaps this is why people have generally settled upon digital symbols for representing numbers, especially whole numbers and integers, which find the most application in everyday life. Using the fingers on our hands, we have a ready means of symbolizing integers from 0 to 10. We can make hash marks on paper, wood, or stone to represent the same quantities quite easily:

For large numbers, though, the "hash mark" numeration system is too inefficient.

The Romans devised a system that was a substantial improvement over hash marks, because it used a variety of symbols (or ciphers) to represent increasingly large quantities. The notation for 1 is the capital letter I. The notation for 5 is the capital letter V. Other ciphers possess increasing values:

If a cipher is accompanied by another cipher of equal or lesser value to the immediate right of it, with no ciphers greater than that other cipher to the right of that other cipher, that other cipher’s value is added to the total quantity. Thus, VIII symbolizes the number 8, and CLVII symbolizes the number 157. On the other hand, if a cipher is accompanied by another cipher of lesser value to the immediate left, that other cipher’s value is subtracted from the first. Therefore, IV symbolizes the number 4 (V minus I), and CM symbolizes the number 900 (M minus C). You might have noticed that ending credit sequences for most motion pictures contain a notice for the date of production, in Roman numerals. For the year 1987, it would read: MCMLXXXVII. Let’s break this numeral down into its constituent parts, from left to right:

Aren’t you glad we don’t use this system of numeration? Large numbers are very difficult to denote this way, and the left vs. right / subtraction vs. addition of values can be very confusing, too. Another major problem with this system is that there is no provision for representing the number zero or negative numbers, both very important concepts in mathematics. Roman culture, however, was more pragmatic with respect to mathematics than most, choosing only to develop their numeration system as far as it was necessary for use in daily life.

We owe one of the most important ideas in numeration to the ancient Babylonians, who were the first (as far as we know) to develop the concept of cipher position, or place value, in representing larger numbers. Instead of inventing new ciphers to represent larger numbers, as the Romans did, they re-used the same ciphers, placing them in different positions from right to left. Our own decimal numeration system uses this concept, with only ten ciphers (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) used in "weighted" positions to represent very large and very small numbers.

Each cipher represents an integer quantity, and each place from right to left in the notation represents a multiplying constant, or weight, for each integer quantity. For example, if we see the decimal notation "1206", we known that this may be broken down into its constituent weight-products as such:

Each cipher is called a digit in the decimal numeration system, and each weight, or place value, is ten times that of the one to the immediate right. So, we have a ones place, a tens place, a hundreds place, a thousands place, and so on, working from right to left.

Right about now, you’re probably wondering why I’m laboring to describe the obvious. Who needs to be told how decimal numeration works, after you’ve studied math as advanced as algebra and trigonometry? The reason is to better understand other numeration systems, by first knowing the how’s and why’s of the one you’re already used to.

The decimal numeration system uses ten ciphers, and place-weights that are multiples of ten. What if we made a numeration system with the same strategy of weighted places, except with fewer or more ciphers?

The binary numeration system is such a system. Instead of ten different cipher symbols, with each weight constant being ten times the one before it, we only have two cipher symbols, and each weight constant is twice as much as the one before it. The two allowable cipher symbols for the binary system of numeration are "1" and "0," and these ciphers are arranged right-to-left in doubling values of weight. The rightmost place is the ones place, just as with decimal notation. Proceeding to the left, we have the twos place, the fours place, the eights place, the sixteens place, and so on. For example, the following binary number can be expressed, just like the decimal number 1206, as a sum of each cipher value times its respective weight constant:

This can get quite confusing, as I’ve written a number with binary numeration (11010), and then shown its place values and total in standard, decimal numeration form (16 + 8 + 2 = 26). In the above example, we’re mixing two different kinds of numerical notation. To avoid unnecessary confusion, we have to denote which form of numeration we’re using when we write (or type!). Typically, this is done in subscript form, with a "2" for binary and a "10" for decimal, so the binary number 11010₂ is equal to the decimal number 26₁₀.

The subscripts are not mathematical operation symbols like superscripts (exponents) are. All they do is indicate what system of numeration we’re using when we write these symbols for other people to read. If you see "3₁₀", all this means is the number three written using decimal numeration. However, if you see "3¹⁰", this means something completely different: three to the tenth power (59,049). As usual, if no subscript is shown, the cipher(s) are assumed to be representing a decimal number.

Commonly, the number of cipher types (and therefore, the place-value multiplier) used in a numeration system is called that system’s base. Binary is referred to as "base two" numeration, and decimal as "base ten." Additionally, we refer to each cipher position in binary as a bit rather than the familiar word digit used in the decimal system.

Now, why would anyone use binary numeration? The decimal system, with its ten ciphers, makes a lot of sense, being that we have ten fingers on which to count between our two hands. (It is interesting that some ancient central American cultures used numeration systems with a base of twenty. Presumably, they used both fingers and toes to count!!). But the primary reason that the binary numeration system is used in modern electronic computers is because of the ease of representing two cipher states (0 and 1) electronically. With relatively simple circuitry, we can perform mathematical operations on binary numbers by representing each bit of the numbers by a circuit which is either on (current) or off (no current). Just like the abacus with each rod representing another decimal digit, we simply add more circuits to give us more bits to symbolize larger numbers. Binary numeration also lends itself well to the storage and retrieval of numerical information: on magnetic tape (spots of iron oxide on the tape either being magnetized for a binary "1" or demagnetized for a binary "0"), optical disks (a laser-burned pit in the aluminum foil representing a binary "1" and an unburned spot representing a binary "0"), or a variety of other media types.

Before we go on to learning exactly how all this is done in digital circuitry, we need to become more familiar with binary and other associated systems of numeration.

Let’s count from zero to twenty using four different kinds of numeration systems: hash marks, Roman numerals, decimal, and binary:

Neither hash marks nor the Roman system are very practical for symbolizing large numbers. Obviously, place-weighted systems such as decimal and binary are more efficient for the task. Notice, though, how much shorter decimal notation is over binary notation, for the same number of quantities. What takes five bits in binary notation only takes two digits in decimal notation.

This raises an interesting question regarding different numeration systems: how large of a number can be represented with a limited number of cipher positions, or places? With the crude hash-mark system, the number of places IS the largest number that can be represented, since one hash mark "place" is required for every integer step. For place-weighted systems of numeration, however, the answer is found by taking base of the numeration system (10 for decimal, 2 for binary) and raising it to the power of the number of places. For example, 5 digits in a decimal numeration system can represent 100,000 different integer number values, from 0 to 99,999 (10 to the 5th power = 100,000). 8 bits in a binary numeration system can represent 256 different integer number values, from 0 to 11111111 (binary), or 0 to 255 (decimal), because 2 to the 8th power equals 256. With each additional place position to the number field, the capacity for representing numbers increases by a factor of the base (10 for decimal, 2 for binary).

An interesting footnote for this topic is the one of the first electronic digital computers, the Eniac. The designers of the Eniac chose to represent numbers in decimal form, digitally, using a series of circuits called "ring counters" instead of just going with the binary numeration system, in an effort to minimize the number of circuits required to represent and calculate very large numbers. This approach turned out to be counter-productive, and virtually all digital computers since then have been purely binary in design.

To convert a number in binary numeration to its equivalent in decimal form, all you have to do is calculate the sum of all the products of bits with their respective place-weight constants. To illustrate:

The bit on the far right side is called the Least Significant Bit (LSB), because it stands in the place of the lowest weight (the one’s place). The bit on the far left side is called the Most Significant Bit (MSB), because it stands in the place of the highest weight (the one hundred twenty-eight’s place). Remember, a bit value of "1" means that the respective place weight gets added to the total value, and a bit value of "0" means that the respective place weight does not get added to the total value. With the above example, we have:

If we encounter a binary number with a dot (.), called a "binary point" instead of a decimal point, we follow the same procedure, realizing that each place weight to the right of the point is one-half the value of the one to the left of it (just as each place weight to the right of a decimal point is one-tenth the weight of the one to the left of it). For example:

When I returned with the whiteboard, I set it down on the table and said "Can you tell me what the difference is between a number and a numeral, Pat?"

"Hmmm…​" said Pat. "I know that a number is used to indicate the amount of something and that numerals have something to do with digits like 1, 2 and 3, but I am not sure exactly what the difference is between a number and a numeral."

"This is not unusual," I said "because most people are not aware that there is a distinction and even those that do often use these terms interchangeably in everyday life. However, in order to properly explain why the bytes in the Dump command’s output have letters in them, we need to precisely define what a number is and what a numeral is and we must also determine how they are related. This information lies within the realm of mathematics and the deeper one goes into the field of computing, the more mathematics one needs to know."

"I don’t know Professor," said Pat "I don’t understand mathematics very well and it is not one of my favorite subjects. Are you sure that a person needs to know a lot of mathematics in order to program computers?"

"The more mathematics a person knows," I said "the more effective programmer they will be. Perhaps the reason you do not understand mathematics very well is that you have not been exposed to it in a way that matches your learning style. It is my opinion that one of the best ways to learn mathematics is to study mathematics and programming at the same time. If you would like, I will integrate mathematics into our discussions on programming and maybe you will find that you will learn it easier this way. What do you think?"

"Okay," replied Pat "we can try this and see what happens."

"Very good, now lets start by defining what numbers and numerals are." I said. " The first thing to understand about numbers is that they do not exist in the physical world. A number is a mathematical concept that exists only in the non-physical world of ideas and its purpose is to describe the amount of something."

"People use numbers every day in the physical world," said Pat "so how could they do this if numbers didn’t exist here?"

I replied "The only way that numbers can be worked with from within the physical world is by using symbols to represent them which are either made of physical matter or make use of certain properties of physical matter. Any symbol (or set of symbols) that is encoded in physical matter, and used to represent a number, is called a numeral. For example, if we wanted to work with the number 5, we could write a '5' on a piece of paper, draw 5 lines next to each other on a piece of paper, tap the top of a table 5 times, say the word 'five', turn on a set of little lights on a computer screen in the shape of a 5, or even arrange a set of transistors in the memory location of a computer into an on/off pattern that represents the number 5…​"

Pat looked at me and blinked, and I smiled and raised an eyebrow…​

"Numbers do not actually exist inside a computer," asked Pat "only numerals that represent numbers do?"

"That is correct." I replied. "I did not want to make the distinction between numbers and numerals during our earlier discussion on contextual meaning in order to make that discussion simpler."

"I can understand how written symbols, sets of lights, and sounds can be used as numerals, but what are transistors and how can patterns of ons and offs be used as numerals?"

"A transistor is an electronic valve that does to the flow of electrons in a conductor what a water valve does to the flow of water in a pipe." I said. "Transistors can also be configured so that they are either all the way on or all the way off, like the light switch for this room." I reached and flicked the light switch on and off a few times to illustrate this point. "The pattern of ons and offs that can be created by a set of transistors in a memory location is able to represent a range of numbers. This pattern is thought of as being arranged in a row like this." I then wrote patterns of ons and offs inside 4 memory locations on the whiteboard. (see Fig. 3)

"The words 'on' and 'off' are somewhat awkward to use for representing these patterns and therefore a simpler numeral system which has the symbol '0' represent an 'off' state and the symbol '1' represent an 'on' state is commonly used. These two symbols represent the on/off state of what is called a bit of information and this is what the memory locations I just drew look like when the words 'on' and 'off' are replaced with bits." (see Fig. 4)

Pat looked at the second diagram then said "These 1’s and 0’s certainly take up less room than the words 'on' and 'off' do. I don’t see yet how they are able to represent numbers, though."

"We will look at that next, then" I said. "Patterns of bits are actually part of a numeral system which is called the binary numeral system and this system matches any pattern of bits with a unique number. The binary numeral system only has 2 symbols in it, 0 and 1, and it is therefore called the base 2 numeral system. Another name for base of a numeral system is radix. Lets start with a set of four bits and see which decimal numerals match the patterns they can be arranged into." I began by writing the words 'Binary' and 'Decimal' on the whiteboard. Then, I wrote 0000 under the word 'Binary' and matched it with the decimal digit 0. Underneath this I wrote 0001 and matched it with the decimal digit 1. (see Fig. 5)

I then wrote the decimal numeral 2 on the next line and started to write the bit pattern that went with it, but then I stopped and said "I am counting the binary numerals up from 0000 to match the decimal numerals that are being counted up from 0. What binary pattern do you think comes next in the sequence to match the decimal numeral 2?"

Pat thought about this question for a while then said "I am not quite sure because we have not counted far enough for me to see if there is a pattern to the sequence."

"There is indeed a pattern to the sequence that the binary numerals go through as they count upwards. This pattern follows the same counting rules that the decimal system does, so lets study these rules with the decimal system first and then apply them to the binary system." I then wrote the decimal digits 0 through 9 on another area of the whiteboard and said the name of each digit as I wrote it "zero, one, two, three, four, five, six, seven, eight, nine, ?…​ ummm, I have a problem Pat. I have run out of decimal digits and I do not know what to do next!" (see Fig. 6)

Pat gave me a strange look then said "Of course, the next numeral in the sequence is 10. Why didn’t you just write a 10 and continue?"

"Tell me what rule you followed to go from 9 to 10 and I will." I replied.

"Well," said Pat "when you need to add one more to the column you are in, but you have run out of digits in that column, you have the column go back to 0 and then add one to the digit in the column which is to the immediate left of the one you are working on."

"And what are the names that are given to these columns in the decimal system?" I asked.

"The initial column is the ones column, to its left is the tens column and to the tens column’s left is the hundreds column. Each time you move left a column, that column represents a place value that is ten times larger than the column you are in."

"Very good Pat." I said. "Lets see if your counting rule solves my problem. Seven, eight, nine, I have run out of decimal digits in the ones column so I roll from 9 around to 0 in the ones column, just like an odometer in an automobile does, and then I add one to the column immediately to the left, which is the tens column." (see Fig 7)

"Your counting rules seems to work with the decimal system, lets see what happens when we apply them to the binary system. 0000, 0001, I just ran out of binary digits in the first column, so I 'roll' it around to 0 and add one to the column which is immediately to its left. The new pattern is 0010 and this is correct. Now, what pattern do you think comes next to match the decimal numeral 3?" I asked. (see Fig. 8)

Pat studied the diagram then said "In the decimal system we would continue to the next digit in the sequence in the ones column and it looks like we would do something similar here. I think the next pattern of bits is 0011."

"Correct." I replied. Then I wrote the pattern 0011 on the whiteboard and also added the numeral 4 in the next row in the decimal column. (see Fig. 9)

"What pattern comes next to match the decimal numeral 4, Pat?" I asked.

Pat stared at the digram for a long while. Eventually I said "Perhaps it would be helpful if we see how a similar pattern is handled in the decimal system." I then wrote the number 99 in another section of the whiteboard and said "what number comes next? Follow the counting rules and say them out loud as you do so."

Pat said "The 9 in the ones column rolls around to 0 and one is added to the 9 that is in the tens column. This makes the tens column also roll around to 0 and a 1 is added to the 100s column resulting in the next decimal numeral in the sequence being 100."

"Very good Pat" I said as I wrote the numeral 100 under the 99 on the whiteboard. (see Fig. 10) Now apply the same thinking to the binary numeral 0011."

Pat studied the binary numeral 0011 again and then said "The 1 in the first column rolls around to 0 and then 1 is added to the column to its left. But I don’t know what 1 + 1 is in binary."

"1 + 1 in binary is 10 binary." I said. "After we perform this addition in the second column the result is 0100 (see Fig. 11).

I then filled in the rest of the binary numerals up through 1111 using these counting rules and matched them with their decimal equivalents (see Fig 12)

After Pat studied the binary numerals I had written for a while, I raised my left hand, put all 4 of my fingers down and said "Watch as I count from 1 to 15 in binary." I raised my index finger, said 'one' and then continued counting on my fingers in binary until I reached 15.

Then I said "I would like you to periodically practice counting in binary like this on your fingers because it will help you to become more comfortable with the binary system. Okay?"

"Okay" said Pat.

"Now, I would like to show you some interesting patterns that binary numerals exhibit." I said. Then, I took two pieces of scrap paper and covered all the numerals on the whiteboard except the rightmost column of the binary numerals." (see Fig 13)

"What do the 0’s and 1’s do in the rightmost column, Pat?" I asked.

"They alternate between 0 and 1!" said Pat with excitement.

"Yes they do." I said. "Now, lets see what patterns appear when we look at the rest of the columns in the binary sequence." I then moved the pieces of paper so each of the remaining columns was shown in turn." (see Figs. 14, 15, and 16)

Pat looked at the pattern of 0’s and 1’s that each column contained then said "The second column contains a repeating pattern of two 0’s followed by two 1’s, the third column contains a repeating pattern of four 0’s followed by four 1’s and the fourth column contains a pattern of eight 0’s followed by eight 1’s. Thats cool, I didn’t notice these patterns before."

"Another aspect of sets of bits we can look at is how many patterns a given set of bits can be formed into. For example, how many patterns can be formed by one bit?" I said.

Pat thought about this for a while then said "I am not quite sure what you mean."

I held up my left hand and started moving my index finger up and down. "How many states can one bit be placed into?"

Pat studied my moving finger then said "Two states, with one state being the 0 state and the other state being the 1 state."

"That is right." I replied. I then wrote the sentence '1 bit can form 2 patterns' on the whiteboard and drew the 2 patterns next to it.

"Now, how many states or patterns can 2 bits be placed into?" I asked.

After a few moments of thought Pat began using two fingers to form the patterns 00, 01, 10, and 11. "2 bits can be formed into 4 patterns!" said Pat.

I nodded my head then wrote '2 bits can form 4 patterns' on the whiteboard and drew the 4 patterns next to it.

"The next question you are probably going to ask me is how many patterns can be formed by 3 bits." said Pat.

"You are right," I replied "can you figure it out?"

Pat used 3 fingers and counted the following patterns: 000, 001, 010, 011, 100, 101, 110, and 111.

Pat looked at me and said "3 bits can be formed into 8 patterns. This is fun!"

"I agree, working with binary patterns is fun!" I said, then I added a section related to the patterns that 3 bits could be formed into to the whiteboard. "Can you figure out how many patterns 4 bits can be formed into?"

"I think so." replied Pat. Using 4 fingers, Pat slowly formed them into the following patterns: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, and 1111. "4 bits can be formed into 16 patterns!"

I recorded the information for 4 bits on the whiteboard and then we looked at what had been written so far. (see Fig. 17)

"Do you notice anything interesting about what happens to the number of patterns that can be formed by a set of bits when one more bit is added to the set?" I asked Pat.

Pat looked at each of the sets then said "when we went from 1 bit to 2 bits, the number of patterns that could be formed increased from 2 to 4. When we went from 2 bits to 3 bits, the number of patterns that could be formed increased to 8 and when we went from 3 bits to 4 bits, the number of patterns that could be formed increased to 16…​"

I then said "2, 4, 8, 16…​"

"The number of patterns that can be formed doubles each time one bit is added to a set of bits!" cried Pat.

"Very good Pat!" I said "You are starting to see how these patterns work. Now, how many patterns can a set of 7 bits be formed into?" "7 bits?" asked Pat. "Wow, I am going to have to think about that one. I suppose we could use the pattern doubling method we just discussed, but it would be nice if there were an easier way to figure it out."

"Would you like me to show you how to determine the answer using a calculator?" I asked.

"Yes." said Pat, so I opened a drawer, pulled out a calculator and handed it to Pat.

"1 single bit is able to produce 2 patterns. Enter a single number 2 into the calculator and press the equals button. What is the answer?"

"2." said Pat.

"We also know that 2 bits are able to produce 4 patterns. Enter 2 x 2 into the calculator and tell me what the answer is."

"4." said Pat "I think I see how to do the calculation now!"

"Okay, then use this method to calculate the number of patterns each set of bits from 1 to 7 can produce and write them on the whiteboard." Pat did so and produced this table:

"Notice that 2 x 2 is the same as 2 to the 2nd power 2², 2 x 2 x 2 is the same as 2³, and so on." I then created the following exponents version of Pat’s patterns calculations."

Pat looked at the exponents version of the patterns calculations then said "It looks like an easy way to calculate the number of patterns that a given number of bits can produce is to raise 2 to that power."

"Yes, this is an easy way to perform the calculation. Try using the exponent key on the calculator to determine how many patterns can be produced by 10 bits, 16 bits, and 20 bits."

Pat entered 2¹⁰, 2¹⁶, and 2²⁰ and came up with the answers, 1024, 65536, and 1048576.

I have one more calculation I would like you to perform before we move on, Pat. How many patterns can be generated by 8 bits?"

Pat entered 2⁸ into the calculator and received an answer of 256.

"256," said Pat "that number seems familiar to me."

"It should," I replied "what is the range of numbers that can be held in a typical computer’s memory location?"

"0 through 255." said Pat. "255 is close to 256, but it is off by 1."

"How many patterns can be represented by the decimal numerals 1 through 255?" I asked.

Pat gave me a questioning look and then said "255."

"And if you add to these 255 patterns the pattern that is represented by the numeral 0, how many patterns does this make?"

"256 patterns!" cried Pat. "Do you mean that the reason that a memory location in a computer can only represent a number between 0 and 255 is because a memory location contains 8 bits?"

"Yes!" I replied. "The number of patterns that n bits can produce is 2ⁿ, but the highest number that can be represented by n bits is 2ⁿ-1 because 0 is always counted as one of the patterns. Memory locations can represent numbers between 0 and 255 because 8 bits, which are also called a byte, are capable of producing 256 patterns.

"Computers use binary numerals instead of decimal numerals Pat," I said "because binary numerals are easier to represent with transistors. There is a problem with binary numerals, however, when humans use them."

"What is the problem with them?" asked Pat.

"Let me illustrate the problem with an example." I said. "My telephone number is 740-555-3308, which is easy to remember, but this number encoded in binary is 0111010000000101010101010011001100001000. If you asked me for my telephone number and I said 'zero one one one zero one zero zero zero zero zero zero zero one zero one zero one zero one zero one zero one zero zero one one zero zero one one zero zero zero zero one zero zero zero', do you think you would be able to remember it?

"No way!" cried Pat. "I don’t even think I could remember more than a few 1’s and 0’s!"

"Most humans are not very good at working with binary numerals, Pat, but humans are able to work with decimal numerals very well. It would be nice if decimal numerals were easy to convert into binary numerals and binary numerals were easy to convert into decimal numerals but this is not so."

"No?" said Pat. "What is the problem?"

"Lets look again at the list of 4-bit binary numerals that are matched with the decimal numerals 0 - 15. The binary numerals start with 4 bits and they maintain a regular 4 bits through the end of the pattern. Something irregular happens, however, with the decimal numerals. Do you see what the irregularity is? (see Fig. 18)

Pat looked at the decimal digits then said "The decimal pattern starts with single digits up through 9 and then it switches to 2 digits after that. Is this the irregularity you are talking about?"

"Yes, this is the irregularity. It is caused by the fact that the base 10 numeral system is not a power of 2 and therefore base 2 numerals and base 10 numerals can not be converted into each other very easily. This caused a significant problem for the early computer programmers. What they needed was a numeral system that was similar enough to the decimal system so that humans could work with it easily, but it had to be a power of 2 so that it could be easily converted into binary numerals."

"How did they solve the problem?" asked Pat.

"There are 2 numeral systems that are a power of 2 that were likely candidates." I said. "The first one was the base 8 or octal numeral system and the second one was the base 16 or hexadecimal system. Both numeral systems were satisfactory for use with computers, but the hexadecimal numerals system became more widely used than the octal numeral system over time." I then added a column for the hexadecimal numeral system next to the binary and decimal columns and filled its numerals in as far as 9. I then added question marks for the remainder of the digits. (see Fig. 19)

"What symbols come after 9 in the hexadecimal numeral system?" asked Pat.

"When the hexadecimal numeral system was first created, almost any symbols could have been chosen. It didn’t take long, however, for the creators to realize that the number of symbols they had available to them was limited." I said.

"Why were they limited?" asked Pat.

I responded "What is the most widely used method for humans to input information into a computer?"

"A keyboard," answered Pat "oh, I see, they were limited by the symbols that are on a keyboard."

"Yes, they were." I replied. "They could have used special symbols like #, %, & and * but these would have looked confusing. Eventually they decided that it made the most sense to use the alphabetic characters A, B, C, D, E, and F because they were part of a sequence that people were already comfortable with." I then replaced the question marks on the whiteboard with these alphabetic characters. (see Fig. 20)

What numeral comes after 'F' asked Pat.

"10." I replied. I then extended the table to 21 hexadecimal so Pat could better see how counting in binary and hexadecimal worked.

"So, it is easy to convert binary numerals to hexadecimal and hexadecimal numerals to binary?" asked Pat.

"Very easy." I said. "All you need to do is to use this table to either replace each hexadecimal digit with its 4-bit binary equivalent or to replace each set of 4-bit binary numerals with its hexadecimal equivalent. For example, to convert the binary numeral 111100101010010101111111010111 into hexadecimal, you start at the right side of the numeral then move to the left and break it into sets of 4 bits. If the leftmost group does not have enough bits to form a set of 4, add 0’s to it from the left until a set of 4 is obtained. After the sets of 4 bits have been formed, just use the table to determine what hexadecimal digit is equivalent to each 4 bit set." I had wrote the binary number on the whiteboard as I said this and also performed the conversion process. (see Fig. 21)

"That was easy!" said Pat.

"The resulting hexadecimal number is also reasonably easy to remember. Say the number to yourself a few times and then close your eyes and try saying it aloud." I suggested.

Pat looked at the number for about 10 seconds then closed both eyes and said "3 C A 9 5 F D 7 hey, I did it!"

"It is also easy to convert from hexadecimal to binary. Lets do this with the hexadecimal number B 2 D 7 8 E 0 6. The conversion process is similar, except you replace each hexadecimal digit with its 4-bit binary equivalent." I then showed Pat how to do this on the whiteboard. (see Fig. 22)

"Now I know what those strange looking numbers were when we used the Dump command to look at the emulator’s memory locations." said Pat. "They were the hexadecimal numeral equivalents of the binary numerals that were in each memory location."

"That is correct, Pat." I said. "The next time we meet, we will go back to the memory location dump and study it further."

Because binary numeration requires so many bits to represent relatively small numbers compared to the economy of the decimal system, analyzing the numerical states inside of digital electronic circuitry can be a tedious task. Computer programmers who design sequences of number codes instructing a computer what to do would have a very difficult task if they were forced to work with nothing but long strings of 1’s and 0’s, the "native language" of any digital circuit. To make it easier for human engineers, technicians, and programmers to "speak" this language of the digital world, other systems of place-weighted numeration have been made which are very easy to convert to and from binary.

One of those numeration systems is called octal, because it is a place-weighted system with a base of eight. Valid ciphers include the symbols 0, 1, 2, 3, 4, 5, 6, and 7. Each place weight differs from the one next to it by a factor of eight.

Another system is called hexadecimal, because it is a place-weighted system with a base of sixteen. Valid ciphers include the normal decimal symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, plus six alphabetical characters A, B, C, D, E, and F, to make a total of sixteen. As you might have guessed already, each place weight differs from the one before it by a factor of sixteen.

Let’s count again from zero to twenty using decimal, binary, octal, and hexadecimal to contrast these systems of numeration:

Octal and hexadecimal numeration systems would be pointless if not for their ability to be easily converted to and from binary notation. Their primary purpose in being is to serve as a "shorthand" method of denoting a number represented electronically in binary form. Because the bases of octal (eight) and hexadecimal (sixteen) are even multiples of binary’s base (two), binary bits can be grouped together and directly converted to or from their respective octal or hexadecimal digits. With octal, the binary bits are grouped in three’s (because 2³ = 8), and with hexadecimal, the binary bits are grouped in four’s (because 2⁴ = 16):

We had to group the bits in three’s, from the binary point left, and from the binary point right, adding (implied) zeros as necessary to make complete 3-bit groups. Each octal digit was translated from the 3-bit binary groups. Binary-to-Hexadecimal conversion is much the same:

Here we had to group the bits in four’s, from the binary point left, and from the binary point right, adding (implied) zeros as necessary to make complete 4-bit groups:

Likewise, the conversion from either octal or hexadecimal to binary is done by taking each octal or hexadecimal digit and converting it to its equivalent binary (3 or 4 bit) group, then putting all the binary bit groups together.

Incidentally, hexadecimal notation is more popular, because binary bit groupings in digital equipment are commonly multiples of eight (8, 16, 32, 64, and 128 bit), which are also multiples of 4. Octal, being based on binary bit groups of 3, doesn’t work out evenly with those common bit group sizings.

Although the prime intent of octal and hexadecimal numeration systems is for the "shorthand" representation of binary numbers in digital electronics, we sometimes have the need to convert from either of those systems to decimal form. Of course, we could simply convert the hexadecimal or octal format to binary, then convert from binary to decimal, since we already know how to do both, but we can also convert directly.

Because octal is a base-eight numeration system, each place-weight value differs from either adjacent place by a factor of eight. For example, the octal number 245.37 can be broken down into place values as such:

The decimal value of each octal place-weight times its respective cipher multiplier can be determined as follows:

The technique for converting hexadecimal notation to decimal is the same, except that each successive place-weight changes by a factor of sixteen. Simply denote each digit’s weight, multiply each hexadecimal digit value by its respective weight (in decimal form), then add up all the decimal values to get a total. For example, the hexadecimal number 30F.A9₁₆ can be converted like this:

These basic techniques may be used to convert a numerical notation of any base into decimal form, if you know the value of that numeration system’s base.

Because octal and hexadecimal numeration systems have bases that are multiples of binary (base 2), conversion back and forth between either hexadecimal or octal and binary is very easy. Also, because we are so familiar with the decimal system, converting binary, octal, or hexadecimal to decimal form is relatively easy (simply add up the products of cipher values and place-weights). However, conversion from decimal to any of these "strange" numeration systems is a different matter.

The method which will probably make the most sense is the "trial-and-fit" method, where you try to "fit" the binary, octal, or hexadecimal notation to the desired value as represented in decimal form. For example, let’s say that I wanted to represent the decimal value of 87 in binary form. Let’s start by drawing a binary number field, complete with place-weight values:

Well, we know that we won’t have a "1" bit in the 128’s place, because that would immediately give us a value greater than 87. However, since the next weight to the right (64) is less than 87, we know that we must have a "1" there.

If we were to make the next place to the right a "1" as well, our total value would be 64₁₀ + 32₁₀, or 96₁₀. This is greater than 87₁₀, so we know that this bit must be a "0". If we make the next (16’s) place bit equal to "1," this brings our total value to 64₁₀ + 16₁₀, or 80₁₀, which is closer to our desired value (87₁₀) without exceeding it:

By continuing in this progression, setting each lesser-weight bit as we need to come up to our desired total value without exceeding it, we will eventually arrive at the correct figure:

This trial-and-fit strategy will work with octal and hexadecimal conversions, too. Let’s take the same decimal figure, 87₁₀, and convert it to octal numeration:

If we put a cipher of "1" in the 64’s place, we would have a total value of 64₁₀ (less than 87₁₀). If we put a cipher of "2" in the 64’s place, we would have a total value of 128₁₀ (greater than 87₁₀). This tells us that our octal numeration must start with a "1" in the 64’s place:

Now, we need to experiment with cipher values in the 8’s place to try and get a total (decimal) value as close to 87 as possible without exceeding it. Trying the first few cipher options, we get:

A cipher value of "3" in the 8’s place would put us over the desired total of 87₁₀, so "2" it is!

Now, all we need to make a total of 87 is a cipher of "7" in the 1’s place:

Of course, if you were paying attention during the last section on octal/binary conversions, you will realize that we can take the binary representation of (decimal) 87₁₀, which we previously determined to be 1010111₂, and easily convert from that to octal to check our work:

Can we do decimal-to-hexadecimal conversion the same way? Sure, but who would want to? This method is simple to understand, but laborious to carry out. There is another way to do these conversions, which is essentially the same (mathematically), but easier to accomplish.

This other method uses repeated cycles of division (using decimal notation) to break the decimal numeration down into multiples of binary, octal, or hexadecimal place-weight values. In the first cycle of division, we take the original decimal number and divide it by the base of the numeration system that we’re converting to (binary=2 octal=8, hex=16). Then, we take the whole-number portion of division result (quotient) and divide it by the base value again, and so on, until we end up with a quotient of less than 1. The binary, octal, or hexadecimal digits are determined by the "remainders" left over by each division step. Let’s see how this works for binary, with the decimal example of 87₁₀:

The binary bits are assembled from the remainders of the successive division steps, beginning with the LSB and proceeding to the MSB. In this case, we arrive at a binary notation of 1010111₂. When we divide by 2, we will always get a quotient ending with either ".0" or ".5", i.e. a remainder of either 0 or 1. As was said before, this repeat-division technique for conversion will work for numeration systems other than binary. If we were to perform successive divisions using a different number, such as 8 for conversion to octal, we will necessarily get remainders between 0 and 7. Let’s try this with the same decimal number, 87₁₀:

We can use a similar technique for converting numeration systems dealing with quantities less than 1, as well. For converting a decimal number less than 1 into binary, octal, or hexadecimal, we use repeated multiplication, taking the integer portion of the product in each step as the next digit of our converted number. Let’s use the decimal number 0.8125₁₀ as an example, converting to binary:

As with the repeat-division process for integers, each step gives us the next digit (or bit) further away from the "point." With integer (division), we worked from the LSB to the MSB (right-to-left), but with repeated multiplication, we worked from the left to the right. To convert a decimal number greater than 1, with a < 1 component, we must use both techniques, one at a time. Take the decimal example of 54.40625₁₀, converting to binary: