15-110: Fall 2010
Class Notes:  Representation and Communication

• Representation and the Data Abstraction Hierarchy
  
  
• Physical Properties (on/off, light/dark, up/down)
  
  
• Representing a Binary Digit ("bit")
  
  
• Abstraction:   physical properties can represent a binary digit ("bit")
  
  
• Question:  Does "up" represent 0 and "down" 1, or vice versa?
  
  
• Representing a Natural Number
  
  
• Activity:  Count past 5 on one hand (that is, represent positive integers in binary)
  
  
• Question:  How high can you count on one hand?  On two hands?
  
  
• Question:  How many fingers would you need to count to 1 thousand?  1 million?   To an arbitrary natural number N?
  
  
• Activity:  Convert from binary to decimal, and from decimal to binary.
  
  
• Abstraction Hierarchy:  Again, physical properties (such as voltage differences) can represent bits, and bits can represent a Natural Number.
  
  
• Representing an Integer (including negative numbers)
  
  
• Activity:  Count on one hand with negatives
  
  
• Question:  what is a "sign bit"?
  
  
• Question:  The bits 1101 can be 8+4+1=13 or -(4+1)=-5.  How do we know which one is right?
  
  
• Another approach:  represent an Integer using two natural numbers (sign + magnitude)
  
  
• Question:  are there other reasonable approaches?
  
  
• Representing a Rational Number (Fraction)
  
  
• Now we can use Integers, so....   Use two integers:  numerator and denominator
  
  
• Representing a Floating-Point (Decimal) Number
  
  
• Hint:  6.235 can also be written as 6235 x 10^-3 (integers for mantissa and exponent)
  
  
• Representing Playing Cards
  
  
• Activity:  how to represent a Playing Card as two integers?  As one integer?   As K bits?  (How many bits would we need?)
  
  
• Activity:  Variation on the Fitch-Cheney Card Trick (use 7 arbitrary cards to represent an 8th arbitrary card)
  
  
• Question:  Why 7 cards?  Can we use just 6?  5?  Fewer?
  
  
• Representing a Series of Numbers
  
  
• Count-based or sentinel-based
  
  
• Representing A Text Character
  
  
• ASCII  (table and wikipedia article)
  
  
• Unicode (many tables and wikipedia article)
  
  
• Question:  ASCII values range from 0 to 255 -- how many bits are required to represent this range?
  
  
• Question:  one Unicode encoding uses 16 bits -- how many unique characters can be represented in this encoding?
  
  
• Representing a Text String
  
  
• Easy enough:  just a sequence of integers each representing a text character
  
  
• Question:  Convert the text "Yes!" to a count-based sequence of integers using ASCII values.
  
  
• Question:  Convert the zero-terminated sequence of ASCII values to a text string:  73,115,32,105,116,32,52,50,63,0
  
  
• Musical Notes
  
  
• Activity:  How can we represent musical notes from sheet music such as this:
  
  
• Hint:  Here is how jfugue does it:
  
  C5q D5q E5q C5q C5q D5q E5q C5q E5q F5q G5h E5q F5q G5h G5i A5i G5i F5i E5q C5q
  G5i A5i G5i F5i E5q C5q C5q G4q C5h C5q G4q C5h
  
  Well, it actually uses variables in a program to make the patterns clearer:  check this out.
  
  
• And here is that same song converted to zero-terminated ASCII:
  
  67,53,113,32,68,53,113,32,69,53,113,32,67,53,113,32,67,53,113,32,68,53,113,32,69,53,
  113,32,67,53,113,32,69,53,113,32,70,53,113,32,71,53,104,32,69,53,113,32,70,53,113,32,
  71,53,104,32,71,53,105,32,65,53,105,32,71,53,105,32,70,53,105,32,69,53,113,32,67,53,
  113,32,71,53,105,32,65,53,105,32,71,53,105,32,70,53,105,32,69,53,113,32,67,53,113,32,
  67,53,113,32,71,52,113,32,67,53,104,32,67,53,113,32,71,52,113,32,67,53,104,0
  
  
• And here is that same song converted to bits:
  
  01000011 00110101 01110001 00100000 01000100 00110101 01110001 00100000
  01000101 00110101 01110001 00100000 01000011 00110101 01110001 00100000
  01000011 00110101 01110001 00100000 01000100 00110101 01110001 00100000
  01000101 00110101 01110001 00100000 01000011 00110101 01110001 00100000
  01000101 00110101 01110001 00100000 01000110 00110101 01110001 00100000
  01000111 00110101 01101000 00100000 01000101 00110101 01110001 00100000
  01000110 00110101 01110001 00100000 01000111 00110101 01101000 00100000
  01000111 00110101 01101001 00100000 01000001 00110101 01101001 00100000
  01000111 00110101 01101001 00100000 01000110 00110101 01101001 00100000
  01000101 00110101 01110001 00100000 01000011 00110101 01110001 00100000
  01000111 00110101 01101001 00100000 01000001 00110101 01101001 00100000
  01000111 00110101 01101001 00100000 01000110 00110101 01101001 00100000
  01000101 00110101 01110001 00100000 01000011 00110101 01110001 00100000
  01000011 00110101 01110001 00100000 01000111 00110100 01110001 00100000
  01000011 00110101 01101000 00100000 01000011 00110101 01110001 00100000
  01000111 00110100 01110001 00100000 01000011 00110101 01101000
  
  
• Question:  How do we know these bits represent a song?  Could they represent something else?
  
  
• Representing a Pixel
  
  
• black-and-white pixel:  just one bit
  
  
• color pixel:  3 integers (red, green, blue)
  
  
• Question:  How can we represent a color pixel in just a single integer?
  
  
• Representing an Image
  
  
• A 2d array of pixels
  
  
• Question:  How can we represent a 2d array of integers?
  
  
• Activity:  Encode the following 4x4 image (hint:  yellow is a combination of red and green):
  
  
  
• Some Famous Encodings
  
  
• Braille
  
  
  
• Morse Code
  
• Nautical Signal Flags, Semaphore, and Sign Languages
  
• Activity:  The multi-code-machine!
  
  
• UPC Bar Codes
  
  
  
• Text Messaging
  
• YGTBKM!
  
  
• Communication (in brief!)
  
  
• Elements of Communication
  
• Encoding, decoding, error detection, error correction, compression, encryption, authentication, protocols, …
  
  
• Activity:  Parity card trick (error detection and correction)
  
  
• Activity:  Magic number-guessing (encoding and steganographic-like encryption)