Section 1 Review

It is assumed that you already know how to convert unsigned numbers as follows. Otherwise visit the indicated review tutorials:

• Decimal to Hex
• Hex to Decimal
• Decimal to Binary
• Binary to Decimal
• Hex to Binary
• Binary to Hex

Section 2 Binary Codes

If one system is used to record the information and a different system is used to read the information, then the result will be confusion.

A discrete unencrypted coding system breaks the information to be recorded down into a series of independent symbols from some alphabet and then replaces each symbol by a binary code using the same code table for each symbol. ASCII text is an example.

A coding system is said to be fixed length if the binary code for every symbol has the same length. For example in the ASCII code, each character has a 7 bit code and so the code length is 7 bits.

Given an alphabet coded by n bits in a fixed length binary coding system. Then that alphabet can have at most 2ⁿ symbols in it. This is called the Power Rule.

number of symbols in alphabet = 2^{number of bits in code}

For example, the ASCII character alphabet has 128 = 2⁷ characters in it because the ASCII code uses seven bits.

Section 3 Four Bit Twos Complement

Before considering the completely general twos complement system it will be useful to look at a simple version of that system.

When positive decimal numbers and zero are coded using 4 bit binary numbers, then there is a coding system implied. It is the unsigned 4 bit integer coding system. According to the power rule mentioned above, four bits of code allows only sixteen different symbols in the alphabet - in this case just sixteen different number values. The coding table is as follows:

This is the familiar decimal to unsigned binary conversion table seen in the Base n Notation tutorial.

However, we wish to code negative numbers as well as positive and zero; and we
wish to keep to a 4 bit code, but the Power Rule says that we can only have 16 codes and so:

Some of the positive number codes must be given up to make room for negative number codes.

There are several ways of doing this (signed magnitude, excess, ones complement). We will learn the twos complement coding system. The general theory will come later, but for right now, here is the signed twos complement 4 bit integer coding system for representing both positive and negative decimal numbers.

0 = 0000	4 = 0100	-8 = 1000	-4 = 1100
1 = 0001	5 = 0101	-7 = 1001	-3 = 1101
2 = 0010	6 = 0110	-6 = 1010	-2 = 1110
3 = 0011	7 = 0111	-5 = 1011	-1 = 1111

Notice the following characteristics:

1. All the codes for negative numbers start (on the left) with a 1 bit.
   
   
2. All the codes starting with a 0 are for positive numbers or zero
   
   
3. The codes for positive numbers (and 0) are the same as the ones in the earlier unsigned code table.
   
   
4. The negative numbers in the table can be computed by looking in the same place in the unsigned code table and then subtracting 16
   
   
5. Thus, decoding a twos complement negative code can be done by first decoding it as unsigned and then subtracting 16.
   

Section 4 General Twos Complement

The general n bit signed twos complement coding system can be understood by generalizing the 4 bit system above.

Let n denote the number of bits each code will have. Then let M denote the maximum number of possible codes. According to the Power Rule, this must be:

Then the signed coding system obeys the following principles:

1. Zero and positive numbers less than M/2 are coded just as in the unsigned binary number system.
   
   
2. Zero and positive numbers will always have codes whose leftmost bit is a ZERO.
   
   
3. Negative numbers from -(M/2) up to -1 are coded by taking the second half of the unsigned table and subtracting M from each decimal number there.
   
   
4. Negative numbers will always have codes whose leftmost bit is a ONE.
   
   
5. The leftmost bit of a twos complement binary code is called the sign bit. 0 means positive(or zero) and 1 means negative.
   
   
6. To decode a binary code with positive sign bit, just use unsigned decimal decoding.
   
   
7. To decode a binary code with negative sign bit, first decode as unsigned and then subtract M from the result.
   
   
8. To code a decimal number from 0 to M/2 - 1, just use unsigned coding.
   
   
9. To code a negative number from -(M/2) up to -1, first add M to the number, and then use unsigned coding.
   
   
10. VERY IMPORTANT Numbers outside the above discussed ranges CANNOT be coded correctly. Only the integers in the range:
    
    -(M/2) through (M/2)-1
    
    can be correctly coded.

Section 5 Algorithms

There are four algorithms available:
        Decimal to Signed Binary
        Decimal to Signed Hexidecimal
        Signed Binary to Decimal
        Signed Hexidecimal to Decimal

Convert Decimal to Signed Binary

An algorithm for converting a signed decimal number to twos complement signed binary can be written combining the ideas of steps 8 and 9 of the previous section:

1. Determine how many bits are required in the answer (read the problem maybe?). This will be the parameter n.
2. Decide if the given decimal number is negative or not.
3. If the given decimal number is negative, then go to step 5 below.
4. Otherwise convert the original decimal number (since it is positive) to an n bit binary number and stop.
5. Since the decimal number was negative, add 2ⁿ to it.
6. Now convert that result to an n bit binary number and stop.

Convert Decimal to Signed Hex

An algorithm for converting a signed decimal number to twos complement signed hex can be written combining the ideas of steps 8 and 9 of the previous section:

1. Determine how many bits are required in the answer (it will be four times the number of hex digits required). This will be the parameter n. Note that n counts bits and not hex digits.
2. Decide if the given decimal number is negative or not.
3. If the given decimal number is negative, then go to step 5 below.
4. Otherwise convert the original decimal number (since it is positive) to a hex number. Use leading zeros to get the right number of hex digits and stop.
5. Since the decimal number was negative, add 2ⁿ to it.
6. Now convert that result to a hex number and stop. It should already have the required number of hex digits in it - assuming you did steps 1 and 5 correctly.

Convert Signed Binary to Decimal

An algorithm for converting a signed binary number from two complement to signed decimal can be written combining the ideas of steps 6 and 7 of the previous section:

1. Look at the leftmost bit of the given binary number. It determines the sign of the answer.
2. If it was a1 bit (signalling a negative answer) goto step 4 below.
3. Otherwise, just convert the binary number as unsigned to decimal and stop.
4. The answer needs to be negative. Nonetheless, first convert the binary number as unsigned to decimal.
5. Count the number of bits in the given binary number - call that n.
6. Subtract 2ⁿ from the decimal number from step 4 and stop.

Convert Signed Hex to Decimal

An algorithm for converting a signed hexidecimal number from two complement to signed decimal can be written combining the ideas of steps 6 and 7 of the previous section:

1. Look at the leftmost bit of the equivalent binary for the leftmost hex digit. It determines the sign of the answer.
2. If it was a1 bit (signalling a negative answer) goto step 4 below.
3. Otherwise, just convert the hex number as unsigned to decimal and stop.
4. The answer needs to be negative. Nonetheless, first convert the hex number as unsigned to decimal.
5. Count the number of bits in the given hex number - call that n. Remember that it is four times the number of hex digits.
6. Subtract 2ⁿ from the decimal number from step 4 and stop.

Section 6 The Twos Complement Operation

The "negative" operation is a unary operation for changing the sign of a number.

One way to change the sign for a signed binary number is to decode it to decimal, change the sign of the decimal number, and then code it back to signed binary. That is a lot of work

As an example using 5 bit signed binary (twos complement understood), consider the binary number 10101. Here are the steps just discussed:

• take binary number: 10101
• decode to decimal:
  • first decode unsigned: 21
  • then subtract 2⁵ = 32: -11
• change the sign: 11
• code back to binary: 01011

Surely there is a more direct way to change the sign of a signed binary number.

There is - known as the twos complement operation. Here is how the above example could have been done directly.

• take binary number: 10101
• takes ones complement: 01010 (which is explained below)
• add 1 in binary: 01011 (which is explained below)

You need to know how to take the ones complement. Fortunately that is very easy;

To take the one's complement, just switch all the bits.

In other words, change all 0's to 1's and all 1's to 0's.

You also must be able to add one in binary and in general, addition is something you will learn later. However adding one can be pretty easy. The example above was simple:

        01010
       +    1
       -------
        01011

        00111
       +    1
       -------
        01000

1. take the binary number
2. find its rightmost 1 bit (all its righthand neighbors are zeros)
3. change all bits to the LEFT of that 1 bit using ones complement
4. BUT, leave that 1 bit and all the zeros (if any) to its right ALONE.

• take the binary number: 1011000
• find the rightmost one bit: 101 <1> 000
• do ones complement to the left: 010 1 000
• leave the rest alone: 0101000

Coding Confusion

• For example, if you use Word to record a document, but then try to read it with Notepad, all you will get is garbage.
• If you use Notepad to record a program, and then try to have the computer execute that program, it will fail. The computer hardware (the controller in the CPU) expects the program to be coded in Machine Language. To see a more detailed example go Here.

Confusing ASCII and Machine Language

	Add 5 to register a 

	a=a+5 

	61 3D 61 2B 35

  61 3D   And the content of memory cell #3D into register b
  61 2B   And the content of memory cell #2B into register b
  35 ??   Add the number ?? to register b

Copyright © 1998 Dr. James F. Wirth