n301/cs12MidTerm n301.tplt Let's Review What is an algorithm? Why is this important? Computer History Brief overview Charles Babbage Lady Lovelace Analytic Engine Concepts-
input
processing
storage
output World War II ENIAC Grace Hopper What is a computer? It is a Universal Information Manipulator Is a computer universal? How is it ‘universal’? Information Manipulator Analog Analog Devices Analog Information Digital Digital Devices Digital Information Computers – digital or analog? We think of computers as digital devices The digital nature of computers gives them their characteristics – limited precision but extreme accuracy Information computers understand They understand numbers – more accurately 0’s and 1’s which is technically on or off in regards to fluctuations in electronic voltages Binary storage Any mechanical device that exhibits yes/no behavior is referred to as a switch A computer is essentially a huge number of switches Voltages is an analog property, but forcing the circuitry to accept it as one of two values makes the computer a digital system Computer and Base 2 On and Off, 1 and 0, voltages Base 2 works just like base 10, but instead of using powers of 10 it uses powers of 2 Binary Example

Decimal Value	Binary Value	2^3	2^2	2^1	2^0
		8s	4s	2s	1s
1	1	0	0	0	1
2	10	0	0	1	0

Binary A base-2 positional numbering system The value of a digit depends not only on it absolute value but also on its specific position within a number Example: Base 10
3, 873 is (3*10^3) + (8*10^2) + (7*10^1) + (3*10^0) or
3000 + 800 + 70 + 3 Simple Table

2^8	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
256	128	64	32	16	8	4	2	1

Converting Decimal to Binary Understanding how we get there by example Convert 67 to binary
- use the table as a tool for conversion Other numbering systems Octal – base 8 Hexadecimal – base 16 Octal How this relates to computers
- byte is a eight-bit binary number It takes exactly one byte to specify one character is ASCII (American Standard Code for Information Interchange) ASCII What is it?
- each character on a computer is assigned a unique binary code number The computers use a code called ASCII, in which an eight-bit binary number represents each character – thus one byte (2^8 or 256) Hexadecimal – base 16 Uses for hexadecimal – colors Values – 0 - F Other Numbers Twos Compliment Floating Point Twos Compliment In decimal notation, a negative number is preceded by a ‘-‘ (minus sign) This is not possible in binary, so we declare one bit to be a sign bit and the rest of the number to be the quantity The complement of a number in a given base can be defined as the difference between each digit of the number and the maximum digit value for the base. Example: Base 10
number is 26 compliment is 73 which is 9-2 = 7 and 9-6 = 3 or the compliment of 73 Floating Point /1 If x is any real number, its normal form representation is,
x = f * 10^E Example:
125.32 = 0.12532 * 10³
-125.32 = -0.12532 * 10³
0.65 = 0.65 * 10⁰ Floating Point/2 The number f of the representation is called the mantissa and the E is the exponent Example

sign of mantissa					sign of exponent
d1	d2	d3	d4	d5	d6	d7	d8
	digits of mantissa					digits of exponent

Sign/magnitude notation Binary digits can be used to represent not only whole numbers but also other forms of data, including signed integers, decimal numbers and characters. To represent signed integers, we can use the leftmost bit to represent the sign, 0 meaning + and 1 meaning - Examples: The number –49 would be represented as:
1  110001
-    49 What about the binary number 1000000 and the binary number 0000000? Ones Complement Possible solution to the problem The names comes from the fact that it is obtained by subtracting each digit of the input number from 1 However, two’s complement is the better solution – this is when 1 is added to the ones-complement Adding Negative Numbers Let’s calculate: 4 + (-6) using twos complement:

- 8	4	2	1
0	1	0	0
1	0	1	0

Floating Point Also known as scientific notation The number 1,023,487₁₀ is 1.023487 * 10⁶ The number 0.1023487₁₀ is 1.023487 * 10^-1 Conversion table (floating pt.)

1/2	1/4	1/8	1/16	1/32
.5	.25	.125	.0625	.03125

Examples: Convert .625 into binary
.625 * 2 = 1.250 (extract the 1)
.250 * 2 = 0.500 (extract the 0)
.500 * 2 = 1.000 (extract the 1) The digits extracted are taken in the order extracted. In this case, the result is .101 (1/2 + 1/8 = 5/8 = .625) Errors One source of errors is converting back and forth between decimal and binary Example:
calculate .6 + .6
first convert to binary .6
.1001100110011…… Do the math Find the sum
    .10011001
  +.10011001
  1.00110010 Convert back So, 1.00110010 converts to 1 + 1/8 + 1/16 + 1/128 = 1.195 (actual sum = 1.2) Error = 1.2 – 1.195 = .005 due to round off error made during conversions Normalized form In normalized form the leading 1 appears next to the decimal point. Example:
.11001001 Scientific notation Avagadro’s number: N_a = 6.022 * 10 ²³ Floating point A BBBB C DD form (8 bits) A = sign of the mantissa | BBBB = mantissa | C = sign of the exponent | DD = exponent Example:
+.1011 * 2⁺³
0 | 1011 | 0 | 11 Example

sign of mantissa					sign of exponent
A	B	B	B	B	C	D	D
	digits of mantissa					digits of exponent

Boolean logic Deals with manipulating the logical values true and false True would be represented by the binary value 1 False would be represented by the binary value 0 Boolean Identities Or gate Several ways to write ‘or’
- OR ex: a OR b
- ‘+’ ex: a + b
- ‘v’ ex: a v b
- or gate OR truth table Lets build a truth table for A or B The OR gate The logical operation of an OR gate is:

Identity	Name
x + x = x x * x = x	Idempotent laws
x + 0 = x x * 1 = x	Identity laws
x + 1 = 1 x * 0 = 0	Dominance laws
x + y = y + x xy = yx	Commutative laws
(x + y) + z = x + (y + z) x(yz) = (xy)z	Associative laws
x + yz = (x + y )(x + z) x(y + z) = xy + xz	Distributive laws

A	B	A OR B
false	false	false
true	false	true
false	true	true
true	true	true

Not gate Ways to write ‘not’
- NOT ex: NOT a
- ‘¬’ ex: a ¬ b
- not gate NOT truth table Let's build the NOT truth table The NOT gate The logical operation of a NOT gate is:

A	¬A
false	True
True	False

And gate Several ways to write ‘and’
- AND ex: a AND b
- ‘*’ ex: a * b
- ‘^’ ex: a ^ b
- ab
- and gate AND truth table Let's build the AND truth table The AND gate The logical operation of an AND gate is:

A	B	A ^ B
false	false	false
false	true	false
true	false	false
true	true	true

Virtual Logic Gate Basic logic gates using Virtual Reality Let's practice Build the truth table for A OR ¬ B Tools Eck's Logic Circuit Tool