Bits, bytes, and representation of information• digital representation means that everything is represented by numbers only• the usual sequence:– something (sound, pictures, text, instructions, ...) is converted into numbers by some mechanism– the numbers can be stored, retrieved, processed, transmitted– the numbers might be reconstituted into a version of the original• for sound, pictures, other real-world values– make accurate measurements– convert them to numeric valuesEncoding sound• need to measure intensity/loudness often enough and accurately enough that we can reconstruct it well enough• higher frequency = higher pitch • human ear can hear ~ 20 Hz to 20 KHz– taking samples at twice the highest frequency is good enough (Nyquist)• CD audio usually uses– 44,100 samples / second– accuracy of 1 in 65,536 (= 2^16) distinct levels– two samples at each time for stereo– data rate is 44,100 x 2 x 16 bits/sample= 1,411,200 bits/sec = 176,400 bytes/sec ~ 10.6 MB/minute• MP3 audio compresses by clever encoding and removal of sounds that won't really be heard– data rate is ~ 1 MB/minuteAnalog versus Digital• analog: "analogous" or "the analog of"– smoothly or continuously varying values– volume control, dimmer, faucet, steering wheel – value varies smoothly with something elseno discrete steps or changes in valuessmall change in one implies small change in anotherinfinite number of possible values– the world we perceive is largely analog• digital: discrete values– only a finite number of different values– a change in something results in sudden change from one discrete value to anotherdigital speedometer, digital watch, push-button radio tuner, …– values are represented as numbersDiscrete values vs continuous values• another kind of conversion– letters are converted into numbers when you type on a keyboard– the letters are stored (a Word document), retrieved (File/Open...), processed (paper is revised), transmitted (submitted by email)– printed on paper • letters and other symbols are inherently discrete• encoding them as numbers is just assigning a numeric value to each one, without any intrinsic meaningRepresenting letters as numbers• what letters and other symbols are included?• how many digits/letter?– determined by how many symbols there are– how do we disambiguate if symbols have different lengths?• how do we decide whose encoding to use?• the representation is arbitrary• but everyone has to agree on it – if they want to work togetherImportant ideas• number of items and number of digits are tightly related:– one determines the other– maximum number of different items = base number of digits– e.g., 9-digit SSN: 109= 1 billion possible numbers• interpretation depends on context– without knowing that, we can only guess what things mean– what's 81615 ?What's a bit? What's a byte?• a bit is the smallest unit of information• represents one 2-way decision or a choice out of two possibilities– yes / no, true / false, on / off, M / F, ...• abstraction of all of these is represented as 0 or 1– enough to tell which of TWO possibilities has been chosen– a single digit with one of two values– hence "binary digit"–hence bit• binary is used in computers because it's easy to make fast, reliable, small devices that have only two states– high voltage/low voltage, current flowing/not flowing (chips)– electrical charge present/not present (RAM, flash)– magnetized this way or that (disks)– light bounces off/doesn't bounce off (cd-rom, dvd)• all information in a computer is stored and processed as bits• a byte is 8 bits that are treated as a unitA review of how decimal numbers work• how many digits?– we use 10 digits for counting: "decimal" numbers are natural for us– other schemes show up in some areasclocks use 12, 24, 60; calendars use 7, 12other cultures use other schemes (quatre-vingts)• what if we want to count to more than 10?– 0 1 2 3 4 5 6 7 8 91 decimal digit represents 1 choice from 10; counts 10 things; 10 distinct values– 00 01 02 … 10 11 12 … 20 21 22 … 98 992 decimal digits represents 1 choice from 100; 100 distinct valueswe usually elide zeros at the front– 000 001 … 099 100 101 … 998 9993 decimal digits …• decimal numbers are shorthands for sums of powers of 10– 1492 = 1 x 1000 + 4 x 100 + 9 x 10 + 2 x 1– = 1 x 103+ 4 x 102+ 9 x 101+ 2 x 100• counting in "base 10", using powers of 10Binary numbers: using bits to represent numbers• just like decimal except there are only two digits: 0 and 1• everything is based on powers of 2 (1, 2, 4, 8, 16, 32, …)– instead of powers of 10 (1, 10, 100, 1000, …)• counting in binary or base 2:0 1 1 binary digit represents 1 choice from 2; counts 2 things; 2 distinct values00 01 10 112 binary digits represents 1 choice from 4; 4 distinct values000 001 010 011 100 101 110 1113 binary digits …• binary numbers are shorthands for sums of powers of 211011 = 1 x 16 + 1 x 8 + 0 x 4 + 1 x 2 + 1 x 1= 1 x 24+ 1 x 23+ 0 x 22+ 1 x 21+ 1 x 20• counting in "base 2", using powers of 2Binary (base 2) arithmetic• works like decimal (base 10) arithmetic, but simpler• addition:0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 10• subtraction, multiplication, division are analogousBytes• "byte" = group of 8 bits– on modern machines, the fundamental unit of processing and memory addressing– can encode any of 28= 256 different values, e.g., numbers 0 .. 255 or a single letter like A or digit like 7 or punctuation like $ASCII character set defines values for letters, digits, punctuation, etc.• group 2 bytes together to hold larger entities– two bytes (16 bits) holds 216= 65536 values– a bigger integer, a character in a larger character setUnicode character set defines values for almost all characters anywhere• group 4 bytes together to hold even larger entities– four bytes (32 bits) holds 232= 4,294,967,296 values– an even bigger integer, a number with a fractional part (floating point), a memory address• etc.– recent machines use 64-bit integers and addresses (8 bytes)264= 18,446,744,073,709,551,616Interpretation of bits depends on context• meaning of a group of bits depends on how they are interpreted • 1 byte could be– 1 bit in use, 7 wasted bits (e.g., M/F in a database)– 8 bits storing a number between 0 and 255– an alphabetic character like W or +