Chapter 3 Universal Gates

Universal Gates
Universal Gates are logic gates that can be used to implement other gates such as AND, OR and NOT. It can be created to replace for many types of gates when we build a big and complex digital systems. They are two type of universal gates, which are NAND gate and NOR gate.

NAND Gate can be configured to obtain the other common Boolean expressions.
For examples,

A	B	F=(A.B)’
0	0	1
0	1	1
1	0	1
1	1	0

The output is High(1) when there is at least one of the input is Low(0) and the output is Low(0) when both of the inputs is High(1).

Implementation of NOT, AND, OR and NOR using NAND Gate.

F=A'
Implement as NOT Gate(Hex inverter).

A NOT gate circuit from a NAND gate simply by tying the two inputs(both High or both Low) of the NAND gate together. If the combination of both inputs are High, the output will be Low and conversely. Thus, the circuit behaves exactly as a NOT gate.

F=(A'.B')'=A.B=AB
Implement as AND Gate

An AND gate circuit can create by using two NAND gates. The first NAND gate will implement his own function and the second NAND gate invert the output from the first NAND gate and become the output of AND gate.

F=(A'.B')'=A+B
Implement as OR Gate

An OR gate circuit can create by using three NAND gates. A pair of NAND gates will invert their inputs and the third NAND gate will combine two inputs. If both of the original inputs are Low, then NAND gate will produce Low output. If one/both of the original inputs are High, it will produce High output from the NAND gate.

F=(A+B)'
Implement as NOR Gate

An NOR gate circuit can create by using four NAND gates. The circuit is same as the OR gate circuit with an addition of another NOT gate to invert the output from the third NAND gate.

NOR Gate can be configured to obtain the other common Boolean expressions.
For examples,

A	B	F=(A+B)’
0	0	1
0	1	0
1	0	0
1	1	0

The output is Low(0) when there is at least one of the input is High(1) and the output is High(1) only when both of the input is Low(0)

Implementation of NOT, AND, OR and NAND using NOR Gate.

F=A'

Implement as NOT Gate(Hex inverter).
A NOT gate circuit from a NOR gate simply by tying the two inputs(both High or both Low) of the NAND gate together. If the combination of both inputs are Low, the output is High. Otherwise, the output is Low.

F=[(A+B)']'=A+B

Implement as OR Gate
An OR gate circuit can create by using two NOR gates. The first NOR gate will implement his own function and the second NOR gates invert the output from the first NOR gate and become the output of OR gate.

F=(A'+B')'=[(A.B)']'=(A.B)
Implement as AND Gate
An AND gate circuit can create by using three NOR gates. A pair of NOR gates will invert their inputs and the third NOR gate will combine two inputs. If both of the original input are Low, the NAND gate will produce Low output. If one/both of the original inputs are High, it will produce High output from the third NAND gate.

F=(A.B)'

Implement as NAND Gate
An NAND gate circuit can create by using four NOR gates. The circuit is same as the AND gate circuit which configured by three NOR gate and another NOR gate configured as a NOT gate to invert the output from the third NOR gate.

Chapter 2 Signed Integer Representation

Signed Number Representation

Signed magnitude

MSB

LSB

                                                   Magnitude

A signed-magnitude number has a sign as its left-most bit (also referred to as the high-order bit or the most significant bit) while the remaining bits represent the magnitude (or absolute value) of the numeric value. 

Example:  -39

The MSB integer is represented positive and negative by 0 and 1, and the rest of the integers are magnitude.

In binary, 39 is 0 010 0111.

Therefore the signed magnitude for -39 is 1 010 0111.

NOTE: 

Addition arithmetic calculations on integers that are represented using this notation

(1) If the signs are the same, add the magnitudes and use that same sign for the result;

(2) If the signs differ, you must determine which operand has the larger magnitude. The sign of the result is the same as the sign of the operand with the larger magnitude, and the magnitude must be obtained by subtracting (not adding) the smaller one from the larger one.

Examples:

01001100+00100100

         11       <<<< carries

0  1001100     (76)

0+0100100   +(36)

========   ====

0  1110000   (112)

For this example, there is no overflow because it do not have 7th "carry in" count from the left.



01001100+01100101

1<==11     <<<< carries
0  1001100   (  76)
0+1100101 +(101)
========  ====
0  0110001   (  49)

From the answer, we see an overflow cause the binary calculation obtained the erroneous result 76+101=49.

NOTE:
Signed-magnitude subtraction is carried out in a manner similar to decimal arithmetic, where it is sometimes necessary to borrow from digits in the minuend.

Examples:
01000100 - 00110001

    012  012 << borrows
0  1000100     (68)
0 -0110001    -(49)
========  ====
0  0010011     (19)

We find 01000100 - 00110001 = 00010011 in signed-magnitude representation.

00100100 - 01100100

1   2     << borrows
0   0100100    (36)
0  -1100100   -(90)

========    ====
1   1000000   (-64)

We need to change the sign of the difference, because the subtrahend value are bigger than minuend value. We find that 00100100(36) - 01100100(90) = 11000000(-64) in signed-magnitude representation.

If there are 2 difference sign, then we need to determine which of the value is larger in magnitude. It sign will be the sign of the result.

Example:
10010010 and 00110100

            02 << borrows
0    0110100    (52)
1   -0010010   -(18)
=========  ====
0    0100010    (34)


The final sign of the result will be positive(0) because the value of positive is larger in magnitude. We find that the result is positive sign [0]0100010(34).

One's Complement
In the one's complement representation, all positive integers are represented in their correct binary format. For example "+25" is represented as usual by 00011001. However, its complement "-25" is obtained by invert 0 and 1.
For the example, the one's complement representation of "-25" will be 11100110.

Another example:

+5 ===>>>   00000101
 -5 ===>>>   11111010
NOTE: The 0 and 1 of the most significant bit(MSB) represented positive and negative sign.

Below are some test for one's complement:
The example for sum of minus 9 and plus 11,

+11==> 00001011
  -9==>  11110110
==============
(1)          00000001 << Sum of minus 9 and plus 11.
From the example, we find that the sum of minus 9 and plus 11 by using one's complement is "00000001" that is incorrect and. However, the result of sum should be "00000010", "plus 2" or the result "1" plus the carry of (1).
It did not work. However the one's complement representation does not always gain the correct result. So we will still use another representation which is called two's complement that involved with one's complement.


Two's Complement

In two’s complement, positive integers are represented in standard binary, as in signed magnitude. However, the representation of a negative number is determined as follows: 
(1) compute a binary representation of the magnitude of the number(singed-magnitude), 
(2) flip all the bits(one's complement), and 
(3) add 1. 
For example,
the 8-bit two’s complement representation of 7 is 00000111 (as before) while −7 is represented as follows (using the steps given above):

The positive integer:   0000 0111   ( 7 )
Reflect each bit     :   1111 1000
Add one                :   1111 1001   ( minus 7 )

From the example, we can see that two's complement is evolved from the one's complement.

Example:
An addition between positive 9 and negative 7.

11    111     1   <<< carries
  0    000 1001     (9)
  1  +111 1001     (-7)
===========    ===
  0    000 0010      (2)

The result is 0000 0010, this is a correct answer. However, the 8th "carry into" bit count from the right to left will be discard and this do not result from an overflow condition.

NOTE: When the carry into or out of the most significant bit must be carefully as this may result from an overflow condition.
Overflow will occur in four situations:
1.adding large positive number
2.adding large negative number
3.subtracting a large positive number from a large negative number
4.subtracting a large negative number from a large positive number

Chapter 2 Number System Conversion

Arithmetic for Computers (Number Systems and Operations)

Number System Conversion

There are many type of number system, and here our conversion are focus on only 3 type of number systems which are binary(base 2) number, decimal(base 10) number and hexadecimal(base 16) number.

Positional Number System

Decimal number system is know as a positional number system, because the position for each digits inside the number are important. The position for every digits cannot be change arbitrary even the digits between 2 numbers are same but with the different digit position.

Example:
          357 = 3*(10^2)+5*(10^1)+7*(10^0)
                = 3*100 + 5*10 + 7*1
                = 300+50+7

If we make the digit position become 735, the value for the digit number will has a very different value with 357 value although the digits for the 2 numbers are same. In positional number system, the most left position will be the most large value, however the most right position is the smallest value.

                  ... 1000 ,  100  ,  10  ,   1
                  ... 10^3  , 10^2 ,10^1 , 10^0
The value for each positions are correspond to powers of the base of the number system. So for our decimal number system, which uses base 10, the place value are correspond to power of 10.
Before we start the conversion, let's have a look on number system conversion table.

Binary	Decimal	Hexadecimal
0000	0	0
0001	1	1
0010	2	2
0011	3	3
0100	4	4
0101	5	5
0110	6	6
0111	7	7
1000	8	8
1001	9	9
1010	10	A
1011	11	B
1100	12	C
1101	13	D
1110	14	E
1111	15	F

Binary and Decimal number system conversion

Converting a binary number to decimal number:
Example: 100110
     1       0       0       1       1       0   the binary number
   2^5    2^4    2^3    2^2    2^1    2^0 place values
= 2^5 + 2^2 + 2^1
= 32  +   4  +  2
= 38

OR

1  ==>>  2^5          32
0  ==>>  2^4
0  ==>>  2^3
1  ==>>  2^2            4
1  ==>>  2^1       +   2
0  ==>>  2^0
=================
                             38

The binary system uses base 2, so the place value of the digit of the binary number correspond to power of 2.
The decimal value for the binary number of 100110 is 38(base 10).

For another example: 0.01011
                0.       0         1         0         1         1
              2^0     2^-1     2^-2     2^-3     2^-4     2^-5
           = 2^-2 + 2^-4 + 2^-5
           = 0.25 + 0.0625 + 0.03125
           = 0.34375

Converting a decimal number to binary number:

Example: 375
The calculation for convert decimal number to binary number as below are using an division calculation.
2|375
2|187  1    \
2| 93   1    \\
2| 46   1    \\\
2| 23   0    ----->>        combine all the remainder start from bottom to top:
2| 11   1    ----->>>>    101110111 << is the binary number for 375(decimal number)
2|   5   1    ----->>
2|   2   1    ///
2|   1   0    //
2|   0   1    /
The remainder for the division will be combined and formed into binary number 101110111 which is the binary number converted from 375(decimal number).

For another example: 0.3158
0.40625 * 2 = 0.8125 + 0 \
0.8125   * 2 = 0.625  + 1 \\    Combine all the remainder start from top to bottom:
0.625    * 2 = 0.25     + 0 >> 0.01001 << is the binary number for 0.3158(decimal number).
0.25      * 2 = 0.5      + 0 //
0.5       * 2 = 0          + 1 /
Binary and Hexadecimal number system conversion

Each digit position of the hexadecimal number system is represents a power of 16.
The reason of the common use for hexadecimal number is the relationship between the number 2 and 16. Sixteen is a power of 2(16=2^4). Because of this relationship, each digit of the hexadecimal are converted by each group(4 binary digits) of binary number. This make the conversion between hexadecimal and binary are very easy.

Converting a binary number to hexadecimal number:
Example: 11 1000 0001 1101 1111

0011 1000 0001 1101 1111    The first 2 digits for the binary number(11) do not form a group
   3      8      1      D      F       to convert to hexadecimal number, so we add 2 digits(00) in front of it to
                                           done the conversion.

Therefore, the hexadecimal number converted from 1000 0001 1101 1111(binary number) is 81DF.
For another example: 0.1101 1001 101

0. 1101 1001 1010    The last 3 binary digits do not form a group to convert to hexadecimal,
0.    D       9       A    so we add a digit(0) at behind of it to done the conversion.
Therefore, the hexadecimal number converted from 0.1101 1001 101(binary number) is 0.D9A.

Converting a hexadecimal number to binary number:
Example: ABD
   A     B      D
1010 1011 1101
Therefore, the binary number converted from ABD(hexadecimal number) is 1010 1011 1101.

For another example: 0.3A2
0.    3      A      2
0. 0011 1010 0010
Therefore, the binary number converted from 0.3A2(hexadecimal number) is 0. 0011 1010 001.

Decimal and Hexadecimal number system conversion

Converting decimal number to hexadecimal number:
Example: 110
16|110   6      Combine the number from top to bottom to form a hexadecimal number.
16|  14   E       The hexadecimal number is 6E.

Converting hexadecimal number to decimal number:
Example: AE9
A=10    16^2   ===>>>   10*(16^2)  =  2560
E=14    16^1   ===>>>   14*(16^1)  =    224
9=  9    16^0   ===>>>     9*(16^0)  =+     9
                                                   ======
                                                        2793


Therefore, the decimal number converted from AE9(hexadecimal number) is 2793.

NOTE: The decimal value of hexadecimal can be view from the system number conversion
           table.

Chapeter 2 Floating point

Floating point

1. Representing real numbers in a way that can support a wide range of values.
2. Number in scientific notation (normalized&not normalized)
3. In binary,decimal
4. In general, numbers are represented approximately to a fixed number of significant digits and scaled using an exponent.


 Floating point standard

1.Defined by IEEE std 754-1985
   -IEEE 754-1985 was technical standard for floating-point computation.

2.Develop in response to divergence of representation.

3.Now almost universally adopted

4. The standard provides definitions for single precision and double precision representations.

IEEE Floating-point format

1bit	8bits	23bits
Sign	Exponent	Mantissa/Significand

Single Precision Range:

• 32-bit: 1-bit sign + 8-bit exponent + 23-bit significand

• Range: 2.0 * 10^-38< N < 2.0 * 10^38

• Precision: ~7 significant (decimal) digits

• Used when exact precision is less important

1bit	11bits	52bits
Sign	Exponent	Mantissa/Significand

Double Precision Range:

• 64-bit: 1-bit sign + 11-bit exponent + 52-bit significand
• Range: 2.0 * 10^–308 < N < 2.0 * 10^308
• Precision: ~15 significant (decimal) digits
• Used for scientific computations

The sign(s) of binary floating-point number is represented by a single bit. A 1 bit indicates a negative number, and a 0 bit indicates a positive number.
M is the mantissa (000...000 to 111...111) and E is the biased exponent.
Single precision, bias = 127.
Double precision, bias = 1203.

Value = (-1)^s  x 1.M x 2^(E-bias)

For Example:
Represent  -0.4375
-0.4375=(-1)^1 * 1.11 * 2^(-2)
S=1
Fraction=11000....002
Exponent= -1+bias
Single = -1+127
=126
= 011111102
double= -1+1023
=1022
=011111111102

Single precision:

1

01111110

11000000..00

Double precision:

1

01111111110

11000000000..00