outline

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