MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 Graphic showing the text "way digital things work".modified 1/30/09 11:37 6.004 – Spring 20092/3/09Course Mechanics Unlike other big courses, you’ll have NO evening quizzes NO final exam NO weekly graded problem sets Instead, you’ll face Repository of tutorial problems (with answers) FIVE quizzes, based on these problems (in Friday sections) EIGHT labs + on-line lab questions + Design Contest (all labs and olqs must be completed to pass!) ALGORITHMIC assignment of your grade! L01 -Basics of Information 4 6.004 – Spring 20092/3/09How do you build systems with >1G components? Personal Computer: Hardware & Software Circuit Board: 1-8 /system 1-2G devicesIntegrated Circuit: 8-16 /PCB .25M-1G devicesModule: 8-64 /IC .1M-1M devicesCell: 1K-10K /Module 16-64 devicesGate: 2-16 /Cell 8 devicesScheme for representing informationMOSFETFigure by MIT OpenCourseWare.Small image zeroes and ones.diagram of a MOSFET.Figure by MIT OpenCourseWare.L01 -Basics of Information 5 6.004 – Spring 20092/3/09What do we see? •Structure–hierarchical design: –limited complexity at each level –reusable building blocks •What makes a good system design?–“Bang for the buck”: minimal mechanism, maximal function –reliable in a wide range of environments –accommodates future technical improvements •Interfaces –Key elements of system engineering; typically outlive the technologies they interface –Isolate technologies, allow evolution –Major abstraction mechanismL01 -Basics of Information 6 6.004 – Spring 20092/3/09Our plan of attack… Understand how things work, bottom-upEncapsulate our understanding using appropriate abstractions Study organizational principles: abstractions, interfaces, APIs. Roll up our sleeves and design at each level of hierarchy Learn engineering tricks -history -systematic approaches -algorithms -diagnose, fix, and avoid bugs L01 -Basics of Information 7 6.004 – Spring 20092/3/09First up: INFORMATION If we want to design devices to manipulate, communicate and store information then we need to quantify information so we can get a handle on the engineering issues. Goal: good implementations •Easy-to-use •Efficient•Reliable •Secure •…•Low-level physical representations •High-level symbols and sequences of symbols Whirlwind, MIT Lincoln Labs http://www.chick.net/wizards/whirlwind.html L01 -Basics of Information 8 6.004 – Spring 20092/3/09What is “Information”? Information resolves uncertainty.Information is simply that which cannot be predicted. The less predictable a message is, the more information it conveys! information,n. Knowledge communicated or received concerning a particular fact or circumstance.Tell me something new… Two photographs removed due to copyright restrictions. Please see http://www.chick.net/wizards/images/whirlwind.jpg and http://www.chick.net/wizards/images/wwtea.gif.L01 -Basics of Information 9 6.004 – Spring 20092/3/09Quantifying Information (Claude Shannon, 1948) Suppose you’re faced with N equally probable choices, and I give you a fact that narrows it down to M choices. Then I’ve given you log2(N/M)bits of information Examples:information in one coin flip: log2(2/1) = 1 bit roll of 2 dice: log2(36/1) = 5.2 bits outcome of a Red Sox game: 1 bit (well, actually, are both outcomes equally probable?) Information is measured in bits (binary digits) = number of 0/1’s required to encode choice(s) L01 -Basics of Information 10 6.004 – Spring 20092/3/09Encoding Encoding describes the process of assigning representations to informationChoosing an appropriate and efficient encoding is a real engineering challenge Impacts design at many levels -Mechanism (devices, # of components used) -Efficiency (bits used) -Reliability (noise) -Security (encryption) Next lecture: encoding a bit.What about longer messages? L01 -Basics of Information 11 6.004 – Spring 20092/3/09Fixed-length encodings 7bits6.426<=(86)2logbits43223102<=.)(logIf all choices are equally likely (or we have no reason to expect otherwise), then a fixed-length code is often used. Such a code will use at least enough bits to represent the information content.ex. ~86 English characters = {A-Z (26), a-z (26), 0-9 (10), punctuation (11), math (9), financial (4)} 7-bit ASCII (American Standard Code for Information Interchange)ex. Decimal digits 10 = {0,1,2,3,4,5,6,7,8,9} 4-bit BCD (binary coded decimal) L01 -Basics of Information 12 6.004 – Spring 2009Encoding numbers ==1n0iiib2v2112102928272625242322212001111101000003720Octal -base 8 000 -0 001 -1 010 -2 011 -3 100 -4 101 -5 110 -6 111 -7 0x7d0Hexadecimal -base 16 0000 -0 1000 -8 0001 -1 1001 -9 0010 -2 1010 -a 0011 -3 1011 -b 0100 -4 1100 -c 0101 -5 1101 -d 0110 -6 1110 -e 0111 -7 1111 -f Oftentimes we will find it convenient to cluster groups of bits together for a more compact notation. Two popular groupings are clusters of 3 bits and 4 bits. It is straightforward to encode positive integers as a sequence of bits. Each bit is assigned a weight. Ordered from right to left, these weights are increasing powers of 2. The value of an n-bit number encoded in this fashion is given by the following formula: = 20001002730d7L01 -Basics of Information 13 6.004 – Spring 20092/3/09Signed integers: 2’s complement 20212223…2N-2-2N-1……N bits 8-bit 2’s complement example: 11010110 = –27 + 26 + 24 + 22 + 21 = – 128 + 64 + 16 + 4 + 2 = – 42 If we use a two’s complement representation for signed integers, the same binary addition mod 2n procedure will work for adding positive and negative numbers (don’t need separate subtraction rules). The same procedure will also handle unsigned numbers! By moving the implicit location of “decimal” point, we can represent fractions too: 1101.0110 = –23 + 22 + 20 + 2-2 + 2-3 = – 8 + 4 + 1 + 0.25 + 0.125 = – 2.625 “sign bit” “decimal” point Range: – 2N-1 to 2N-1 – 1 L01 -Basics of Information 14 6.004 – Spring 20092/3/09When choices aren’t equally probable When the choices have different probabilities (pi), you get more information when learning of a unlikely choice than when learning of a likely choiceInformation from choicei = log2(1/pi) bits Average information from a choice = pilog2(1/pi)Examplechoiceipi“A” 1/3 “B“ 1/2 “C” 1/12 “D” 1/12 Average information = (.333)(1.58) + (.5)(1) + (2)(.083)(3.58) = 1.626 bits Can we find an encoding where transmitting 1000 choices is close to 1626 bits on the average? Using two bits for each choice = 2000 bits log2(1/pi)1.58 bits 1 bit 3.58 bits 3.58 bits L01 -Basics of Information 15 6.004 – Spring 20092/3/09Variable-length encodings (David Huffman, MIT 1950) choiceipiencoding “A” 1/3 11 “B“ 1/2 0“C” 1/12 100 “D” 1/12 101 BCDA101010Use shorter bit sequences for high probability choices, longer sequences for less probable choices 010011011101Huffman Decoding TreeCBAADAverage information = (.333)(2)+(.5)(1)+(2)(.083)(3) = 1.666 bits Transmitting 1000 choices takes an average of 1666 bits… better but not optimalTo get a more efficient encoding (closer to information content) we need to encode sequences of choices, not just each choice individually. This is the approach taken by most file compression algorithms… BL01 -Basics of Information 16 6.004 – Spring 20092/3/09Data Compression Key:re-encoding to remove redundant information: match data rate to actual information content. A84b!*m9@+M(p“Outside of a dog, a book is man’s best friend. Inside of a dog, its too dark to read…” -Groucho Marx Ideal: No redundant info – Only unpredictable bits transmitted.Result appears random! LOSSLESS: can ‘uncompress’, get back original.A CD (capacity 40MB) and floppy disks 4MB).Figure by MIT OpenCourseWare.Sequence from a book to several disks single disk.L01 -Basics of Information 18 6.004 – Spring 20092/3/09Doesrecompression work? If ZIP compression of a 40MB Bible yields a 4MB ZIP file, what happens if we compress that?-Basics of Information 19 6.004 – Spring 20092/3/09Is redundancy always bad? Encoding schemes that attempt to match the information content of a data stream are minimizing redundancy. They are data compression techniques. However, sometimes the goal of encoding information is to increase redundancy, rather than remove it. Why? •Make the information easy to manipulate (fixed-sized encodings) • Make the data stream resilient to noise (error detecting and correcting codes) L01 -Basics of Information 20 6.004 – Spring 20092/3/09Error detection and correction Suppose we wanted to reliably transmit the result of a single coin flip: Further suppose that during transmission a single-bit error occurs, i.e., a single “0” is turned into a “1” or a “1” is turned into a “0”. Heads: “0” Tails: “1” This is a prototype of the “bit” coin for the new information economy. Value = 12.5¢HINT:if the initial compression works the result hasnoperfectly, redundancy! •Do we get a 400 KB file? •Can we compress that, to get a 40K file?? •Can we compress the whole Bible down to a single bit??? •Is it a 0 or a 1???? Figure by MIT OpenCourseWare.Two people playing the telephone game. The message starts out as 0 and ends up 1.Figure by MIT OpenCourseWare.L01 -Basics of Information 21 6.004 – Spring 20092/3/09Hamming Distance (Richard Hamming, 1950) HAMMING DISTANCE: The number of digit positions in which the corresponding digits of two encodings of the same length are different The Hamming distance between a valid binary code word and the same code word with single-bit error is 1. The problem with our simple encoding is that the two valid code words (“0” and “1”) also have a Hamming distance of 1. So a single-bit error changes a valid code word into another valid code word… 10“heads” “tails”single-bit error L01 -Basics of Information 22 6.004 – Spring 20092/3/09Error Detection What we need is an encoding where a single-bit error doesn’t produce another valid code word. 1100“heads” “tails”0110single-bit error We can add single-bit error detection to any length code word by adding a parity bit chosen to guarantee the Hamming distance between any two valid code words is at least 2. In the diagram above, we’re using “even parity” where the added bit is chosen to make the total number of 1’s in the code word even. Can we correct detected errors? Not yet… If D is the minimum Hamming distance between code words, we can detect up to (D-1)-bit errors L01 -Basics of Information 23 6.004 – Spring 20092/3/09Error Correction 110000“heads” “tails”100010single-bit error 111001101011By increasing the Hamming distance between valid code words to 3, we guarantee that the sets of words produced by single-bit errors don’t overlap. So if we detect an error, we can perform error correction since we can tell what the valid code was before the error happened. • Can we safely detect double-bit errors while correcting 1-bit errors? • Do we always need to triple the number of bits? If D is the minimum Hamming distance between code words, we can correct up to -bit errors 21DL01 -Basics of Information 24 6.004 – Spring 20092/3/09The right choice of codes can solve hard problems Reed-Solomon (1960) First construct a polynomial from the data symbols to be transmittedand then send an over-sampled plot of the polynomial instead of the original symbols themselves – spread the information out so it can be recovered from a subset of the transmitted symbols. Particularly good at correcting bursts of erasures (symbols known to be incorrect) Used by CD, DVD, DAT, satellite broadcasts, etc. Viterbi (1967) A dynamic programming algorithm for finding the most likely sequence of hidden states that result in a sequence of observed events, especially in the context of hidden Markov models. Good choice when soft-decision information is available from the demodulator.Used by QAM modulation schemes (eg, CDMA, GSM, cable modems), disk drive electronics (PRML) L01 -Basics of Information 25 6.004 – Spring 20092/3/09Summary •Information resolves uncertainty •Choices equally probable: •N choices down to M log2(N/M) bits of information •use fixed-length encodings •encoding numbers: 2’s complement signed integers •Choices not equally probable: •choicei with probability pilog2(1/pi) bits of information •average number of bits = pilog2(1/pi)•use variable-length encodings •To detect D-bit errors: Hamming distance > D •To correct D-bit errors: Hamming distance > 2D Next time: •encoding information electrically •the digital abstraction •combinational devices Hand in Information Sheets!