6.004-2 Digital abstraction, combinational logic, encoding

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 L02 -Digital Abstraction 1 6.004 – Spring 20092/5/09The Digital Abstraction Handouts: Lecture Slides 1. Making bits concrete 2. What makes a good bit 3. Getting bits under contractmodified 1/30/09 11:46 L02 -Digital Abstraction 2 6.004 – Spring 20092/5/09Concrete encoding of information To this point we’ve discussed encoding information using bits. But where do bits come from? If we’re going to design a machine that manipulates information, how should that information be physically encoded? What makes a good bit? -cheap (we want a lot of them) -stable (reliable, repeatable) -ease of manipulation (access, transform, combine, transmit, store)He said to his friend, "If the British march By land or sea from the town to-night, Hang a lantern aloft in the belfry arch Of the North Church tower as a signal light,--One if by land, and two if by sea;And I on the opposite shore will be, Ready to ride and spread the alarm Through every Middlesex village and farm, For the country folk to be up and to arm." L02 -Digital Abstraction 3 6.004 – Spring 20092/5/09Substrates for computation We can build upon almost any physical phenomenon…Wait! Those last ones might have potential...lanterns polarization of a photon dominos engraved stone tablets Billiard balls E. Coli L02 -Digital Abstraction 4 6.004 – Spring 20092/5/09But, since we’re EE’s… Stick with things we know about: voltagesphasecurrentsfrequency This semester we’ll use voltages to encode information. But the best choice depends on the intended application... Voltage pros: easy generation, detection lots of engineering knowledge potentially low power in steady state Voltage cons: easily affected by environment DC connectivity required? R & C effects slow things downzeroL02 -Digital Abstraction 5 6.004 – Spring 20092/5/09Representing information with voltageRepresentation of each point (x, y) on a B&W Picture: 0 volts: BLACK1 volt:WHITE0.37 volts:37% Gray etc. Representation of a picture: Scan points in some prescribed raster order… generate voltage waveform How much information at each point? L02 -Digital Abstraction 6 6.004 – Spring 20092/5/09Information Processing = ComputationFirst let’s introduce some processing blocks:vCopy vINVv1-vL02 -Digital Abstraction 7 6.004 – Spring 20092/5/09Why have processing blocks? The goal of modular design:What does that mean anyway: • Rules simple enough for a 6-3 to follow… • Understanding BEHAVIOR without knowing IMPLEMENTATION • Predictable composition of functions • Tinker-toy assembly • Guaranteed behavior, under REAL WORLD circumstances Abstraction L02 -Digital Abstraction 8 6.004 – Spring 20092/5/09?Let’s build a system! Copy INVCopy INVCopy INVCopy INVoutput(In Theory) (Reality) inputThree Lego blocks, stacked together.Figure by MIT OpenCourseWare.L02 -Digital Abstraction 9 6.004 – Spring 20092/5/09Why did our system fail? Why doesn’t reality match theory? 1. COPY Operator doesn’t work right 2. INVERSION Operator doesn’t work right 3. Theory is imperfect 4. Reality is imperfect 5. Our system architecture stinks ANSWER:all of the above! Noise and inaccuracy are inevitable; we can’t reliably reproduce infinite information--we must design our system to tolerate some amount of error if it is to process information reliably. L02 -Digital Abstraction 10 6.004 – Spring 20092/5/09The Key to System Design A system is a structure that is guaranteed to exhibit a specified behavior, assuming all of its components obey their specified behaviors.How is this achieved? Contracts! Every system component will have clear obligations and responsibilities. If these are maintained we have every right to expect the system to behave as planned. If contracts are violated all bets are off.L02 -Digital Abstraction 11 6.004 – Spring 20092/5/09The Digital Panacea ... Why digital? … because it keeps the contracts simple! The price we pay for this robustness: All the information that we transfer between modules is only 1 crummy bit! But, we get a guarantee of reliable processing.0 or 1L02 -Digital Abstraction 12 6.004 – Spring 20092/5/09The Digital Abstraction Real World“Ideal” Abstract WorldVolts or Electrons or Ergs or GallonsBits0/1Keep in mind that the world is not digital, we would simply like to engineer it to behave that way. Furthermore, we must use real physical phenomena to implement digital designs!NoiseManufacturingVariations L02 -Digital Abstraction 13 6.004 – Spring 20092/5/09Using Voltages “Digitally” Key idea: don’t allow “0” to be mistaken for a “1” or vice versa Use the same “uniform representation convention” for everycomponent and wire in our digital system To implement devices with high reliability, we outlaw “close calls” via a representation convention which forbids a range of voltages between “0” and “1”. CONSEQUENCE: Notion of “VALID” and “INVALID” logic levelsvolts Valid “0”Valid “1”Forbidden ZoneInvalidL02 -Digital Abstraction 14 6.004 – Spring 20092/5/09A Digital Processing Element StaticdisciplineOutput a “1” if at least 2 out of 3 of my inputs are a “1”. Otherwise, output “0”.I will generate a valid output in no more than 2 minutes after seeing valid inputsinput Ainput Binput Coutput Y Acombinational device is a circuit element that has –one or more digital inputs–one or more digital outputs–afunctional specification that details the value of each output for every possible combination of valid input values –atiming specification consisting (at minimum) of an upper bound tpd on the required time for the device to compute the specified output values from an arbitrary set of stable, valid input valuesL02 -Digital Abstraction 15 6.004 – Spring 20092/5/09A Combinational Digital System A set of interconnected elements is a combinational device if –each circuit element is combinational –every input is connected to exactly one output or to some vast supply of constant 0’s and 1’s –the circuit contains no directed cycles Why is this true? Given an acyclic circuit meeting the above constraints, we can derive functional and timing specs for the input/output behavior from the specs of its components! We’ll see lots of examples soon. But first, we need to build some combinational devices to work with… L02 -Digital Abstraction 16 6.004 – Spring 20092/5/09Wires: theory vs. practice VinVout(voltage close to boundary with forbidden zone) (voltage in forbidden zone: Oops, not a valid voltage!)Does a wire obey the static discipline? Noise: changes voltage… Questions to ask ourselves: In digital systems, where does noise come from? How big an effect are we talking about? VinVinL02 -Digital Abstraction 17 6.004 – Spring 20092/5/09Power Supply Noise +-Integrated circuit R’s and C’s from Aluminum wiring layers Current loads from on-chip devices L’s from chip leads V from: ••IR drop(between gates: 30mV, within module: 50mV, across chip: 350mV) ••L(dI/dt) drop(use extra pins and bypass caps to keep within 250mV) ••LC ringing triggered by current “steps” Power supply L02 -Digital Abstraction 18 6.004 – Spring 20092/5/09Crosstalk CCCOVAVBABIf node B is driven +-AVACOCBVCCCV+=This situation frequently happens on integrated circuits where there are many overlapping wiring layers. In a modern integrated circuit VAmight be 2.5V, CO = 20fF and CC = 10fFVB=0.83V! Designers often try to avoid these really bad cases by careful routing of signals, but some crosstalk is unavoidable. L02 -Digital Abstraction 19 6.004 – Spring 20092/5/09Sequential Interference V from energy storage left over from earlier signaling on the wire: ••transmission line discontinuities(reflections off of impedance mismatches and terminations) [Dally]Fig. 6-17 ••charge storage in RC circuit (narrow pulses are lost due to incomplete transitions) [Dally]Fig. 6-19 [Dally]Fig. 6-20 ••RLC ringing(triggered by voltage “steps”) Fix: slower operation, limiting voltage swings and slew rates L02 -Digital Abstraction 20 6.004 – Spring 20092/5/09Needed: Noise Margins! VinVout(marginally valid) (invalid!) Does a wire obey the static discipline?No! A combinational device must restore marginally valid signals. It must accept marginal inputs and provide unquestionable outputs (i.e., to leave room for noise).volts Forbidden ZoneValid “0”Valid “1”VilVolVihVohVALID INPUT REPRESENTATIONSVALID OUTPUT REPRESENTATIONS NOISE MARGINSThat’s what the small print was about! NoiseThree circuit diagrams and the corresponding voltages.Three A 4/2 4/2 1B B C 1C 500 fF Figures by MIT OpenCourseWare.L02 -Digital Abstraction 21 6.004 – Spring 20092/5/09A Buffer 0011A simple combinational device:Static Discipline requires that the VTC avoid the shaded regions (aka “forbidden zones”), which correspond to valid inputs but invalid outputs.Voltage Transfer Characteristic (VTC): Plot of Vout vs. Vin where each measurement is taken after any transients have died out. VoutVinVilVolVihVohVolVilVihVohNote: VTC does not tell you anything about how fast a device is— it measures static behavior not dynamic behaviorNet result: combinational devices must have GAIN > 1 and be NONLINEAR.L02 -Digital Abstraction 22 6.004 – Spring 20092/5/09Can this be a combinational device? VOUTVIN123450012345(0,5) (1,4) (2.5,1) (3,0.5) VOLVOLSuppose that you measured the voltage transfer curve of the device shown below. Could we build a logic family using it as a single-input combinational device? The device must be able to actually produce the desired output level. Thus, VOL can be no lower than 0.5 V. VIHVIHVILVILVOHVOHVIH must be high enough to produce VOLNow, choose noise margins – find an N and set VOH = VIH + N VIL = VOL + N Such that VIH IN generates VOL or less out; AND VIL IN generates VOH or more out. Try VOL = 0.5 VTry VIH = 3 VTry N = 0.5 VHmmm, it had better be an INVERTER…L02 -Digital Abstraction 23 6.004 – Spring 20092/5/09Summary •Use voltages to encode information •“Digital” encoding •valid voltage levels for representing “0” and “1” •forbidden zone avoids mistaking “0” for “1” and vice versa •gives rise to notion of signal VALIDITY. •Noise •Want to tolerate real-world conditions: NOISE. •Key: tougher standards for output than for input •devices must have gain and have a non-linear VTC •Combinational devices •Each logic family has Tinkertoy-set simplicity, modularity •predictable composition: “parts work whole thing works” •static discipline •digital inputs, outputs; restore marginal input voltages •complete functional spec •valid inputs lead to valid outputs in bounded timeL02 -Digital Abstraction 24 6.004 – Spring 20092/5/09Next time: Building Logic w/Transistors It’s about time! I’d have preferred the dominos…