Phần cứng - Chapter 3: Digital logic structures

Chapter 3Digital Logic Structures Transistors Logic gates & Boolean logic Combinational logic Storage Elements MemoryTransistorsAn electronic switchlike light switch or faucetswitches between insulator and conductor switch is closed (conducts) between A & B depending on the voltage on G (gate)Open switch: no current flowsClosed switch: current flows2ABGABGNClosed if gate is “on”Open if gate is “off”POpen if gate is “on”Closed if gate is “off”ABGCMOS TransistorsCMOS= Complementary Metal-Oxide SemiconductorStandard type for digital applicationsTwo types: N (negative) and P (positive)N and P transistors operate in inverse modes32.9 v0 vOutInInverter GateWhen the input is on (In = high voltage), the P-type transistor is open and the N-type is closed, so the output is off (Out = low voltage).Vice-versa: when the Input is off (In = low voltage), the output is connected to the high voltage.PN4NOR GateCAB2.9 v0 v0 vPNPN5NOR Gate - Operation2.9 v0 v0 vPNP 0 v 0 v2.9 v2.9 v0 v0 vNPN2.9 v2.9 v0 vN0 v0 vPNPN2.9 v2.9 v0 v0 vP6OR GateDA B C= a NOR gate followed by an inverter7NAND & AND GatesA B C D 8Logic Gates & SymbolsNote: gates can have more than two inputs.Inverter (=NOT)inverts 0 to 1 and 1 to 0AND gatec is 1 only if both a and b are 1abcOR gatec is 1 if either a or b is 1abcNAND gatec is 0 only if both a and b are 1abcNOR gatec is 0 if either a or b are 1abc9De Morgan’s LawA and B = not((not A) or (not B))A or B = not((not A) and (not B))CompletenessAND, OR and NOT are sufficient to represent any truth table.Actually: AND & NOT, or OR & NOT are separately sufficient.So: all we need are NOR or NAND gates.==10Representation of Logic FunctionsA logic function can be represented asa truth tablea logic expressiona logic circuitExampleabcdf00000000100010100111010000101001101011111000010011101001011111000110111110111111bacdf11Types of Logic StructuresTwo types of logic structures (devices)Storage structures: permit the storage of information (1 bit).Decision structures: can make a decision but do not remember what it was: gates belong to this category.Combinational logica logic structure is combinational if it is constructed from decision elements only: gates or other combinational logic structures.the output of a combinational logic structure depends strictly on its current input.Three examplesDecoderMultiplexer (MUX)Full adder12DecoderAn n input decoder has 2n outputs.Outputi is 1 iff the binary value of the n-bit input is i.At any time, exactly one output is 1, all others are 0.1, iff A,B is 00AB1, iff A,B is 011, iff A,B is 101, iff A,B is 11i = 0i = 1i = 2i = 313Multiplexer (MUX)In general, a MUX has2n data inputsn select (or control) linesand 1 output.It behaves like a channel selector. A 4-to-1 MUX: Out takes the value of A,B, C or Ddepending on the value of S (00, 01, 10, 11)S[1:0]ABCDOutABCDOutS0S114AdderHalf Adder2 inputs2 outputs: sum and carryFull Adderperforms the addition in column i3 inputs: ai, bi and ci2 outputs: si and ci+1ci is the carry in from bit position i-1ci+1 is the carry out to bit position i+1Half-adder truth table15Gate Level Full Adder16Full Adder - Expressionswhere- verify that this corresponds to the gate-level implementation.17A 4-bit Ripple-Carry Adder18Carry Lookahead AdditionWe can pre-compute the carryThe carry in bit 4 (C4) is 1 if any two of A3, B3 or C3 are 1.P3 is called the propagate bit, and G3 the generate bitSo every carry bit can be pre-computed using all the previous inputs.Pre-computation can be done in 2 gate delays.19Storage Elements: R-S LatchThe R-S LatchThe output (a) of the R-S latch can be set to 1 by momentarily setting S to 0 while keeping R at 1.If S is set to 1 the output stays at 0.10Conversely, the output can be set to 0 by keeping S at 1 and momentarily setting R to 0.When R is set back to 1, the output stays at 0.100101The flip-flop (R-S latch) is a bi-stable element20Storage Elements: Gated D LatchThe R-S LatchThe gated D larch is an extension of the R-S latchTwo inputs: data (D) and write enable (WE)When the WE (write enable) is set to 1, the output of the latch is set to the value of D.The output is held until WE is “asserted” (set to 1) again.21RegistersA 4-bit register made of four D latches22Memory - 1Address Spacen bits allow the addressing of 2n memory locations.Example: 24 bits can address 224 = 16,777,216 locations (i.e. 16M locations).If each location holds 1 byte then the memory is 16MB.If each location holds one word (32 bits = 4 bytes) then it is 64 MB.A large number of addressable fixed size locations23Memory - 2AddressabilityComputers are either byte or word addressable - i.e. each memory location holds either 8 bits (1 byte), or a full standard word for that computer (typically 32 bits, though now many machines use 64 bit words).Normally, a whole word is written and read at a time:If the computer is word addressable, this is simply a single address location.If the computer is byte addressable, and uses a multi-byte word, then the word address is conventionally either that of its most significant byte (big endian machines) or of its least significant byte (little endian machines). 24Building a MemoryEach bitis a gated D-latchEach locationconsists of w bits (here w = 1)w = 8 if the memory is byte addressableAddressingn locations means log2n address bits (here 2 bits => 4 locations)decoder circuit translates address into 1 of n addressesWEA[1:0]D25Memory ExampleA 22 by 3 bits memory:two address lines: A[1:0]three data lines: D[2:0]one control line: WEOne gated D-latch26Using Memory Building BlocksBuilding an 8K byte memory using chips that are 2K by 4 bits. CS = chip select:when set, it enables the addressing, reading and writing of that chip.This is an 8KBbyte addressable memorydecoderCSCSCSCSCSCSCSCSA10-A0A12-A112K x 4 bits2K x 4 bits2K x 4 bits2K x 4 bits2K x 4 bits2K x 4 bits2K x 4 bits2K x 4 bits27Memory One Word WideUse the previous memory block of 8K x 1 byte to build a memory that is 64K words, with each location one word of 32 bits.what are the address lines if the memory is word addressed? or byte addressed?A? - A?decoderA? - A?8K x 1B28Finite-State MachinesOutput is a function of the input and the stateThe function is computed by the combinatorial logic circuitThe state is stored in the storage elementThe state is also a function of itself and the inputCombinational Logic CircuitStorageElementoutputinput29FSM ExampleThree groups of lights to be lit in a sequence: group 1 on, groups 1 & 2 on, all groups on, all off.The lights are on only if the main switch is on.Four states: so we need two bits to identify each state.DETOURCombinational Logic CircuitTwo bit Storageswitchclock22out1out2out3all ongrp 1,2 onall offgrp 1 on1100010,101101100Sd[1:0]30FSM ExampleWhen is group 1 on?in states 01, 10 and 11 - but only when the switch is on!When do we switch to the next state?at every clock cycle the two bits are updatedd[1:0] is the state at the next clock cycle; it is a function of the input (switch) and the current state.can you come up with a logic expression for d0 and d1?31The LC-2 as a Finite State Machine32Data Path of the LC-233