数字逻辑-第五章-常见数字模块-更新-DDCA-Ch5-2课件

1、Digital Design and Computer Architecture, 2nd EditionChapter 5David Money Harris and Sarah L. Harris常见数字模块Digital Design and Computer ArChapter 5 : TopicsIntroduction引言Arithmetic Circuits算术电路Number Systems数制系统Sequential Building Blocks 时序电路模块Memory Arrays存储器阵列Logic Arrays逻辑阵列Chapter 5 : TopicsIntrod

2、uctioDigital building blocks:数字模块Gates, multiplexers, decoders, registers, arithmetic circuits, counters, memory arrays, logic arrays逻辑门电路、多路选择器、译码器、寄存器、算术运算电路、计算器、存储器阵列、逻辑阵列Building blocks demonstrate hierarchy, modularity, and regularity:Hierarchy of simpler componentsWell-defined interfaces and f

3、unctionsRegular structure easily extends to different sizesIntroduction引言说明了层次化、模块化、规整化的原则复杂模块可以用层次化的方法由更简单的模块（如逻辑门电路、多路选择器、译码器等）组成。每个模块都有定义好的接口，当底层实现不重要时，可以被视为黑盒。每一个规整结构的模块都应易于扩展为不同规模。Digital building blocks:数字模块In1-Bit Adders一位加法器图5-1 1 位半加器图5-3 1位全加器1-Bit Adders一位加法器图5-1 1 位半加器图1-Bit Adders一位加法器图

4、5-1 1 位半加器图5-3 1位全加器1-Bit Adders一位加法器图5-1 1 位半加器图1-Bit Adders一位加法器图5-1 1 位半加器图5-3 1位全加器1-Bit Adders一位加法器图5-1 1 位半加器图Types of carry propagate adders (CPAs):Ripple-carry (slow)Carry-lookahead (fast) 先行进位加法器Prefix (faster) 前缀加法器Carry-lookahead and prefix adders faster for large adders but require more

5、hardware SymbolMultibit Adders (CPAs)多位加法器进位传播加法器的类型行波进位加法器图5-4 进位传播加法器对于大位数相加，先行进位加法器和前缀加法器更快，但是需要更多的硬件Types of carry propagate adderChain 1-bit adders together连续串联一位全加器Carry ripples through entire chain行波进位通过整个链Disadvantage: slow缺点是速度慢Ripple-Carry Adder行波进位加法器图5-5 32位行波进位加法器Chain 1-bit adders toge

6、ther连续串tripple = NtFA where tFA is the delay of a full adderRipple-Carry Adder Delay行波进位加法器的延迟其中tFA是一个全加器的延迟Ripple-Carry Adder Delay行波进位加法Compute carry out (Cout) for k-bit blocks using generate and propagate signals计算输出进位Cout 对k位块用G和P两个信号Some definitions:一些定义Column i produces a carry out by either

7、generating a carry out or propagating a carry in to the carry outGenerate (Gi) and propagate (Pi) signals for each column:Column i will generate a carry out if Ai AND Bi are both 1. Gi = Ai BiColumn i will propagate a carry in to the carry out if Ai OR Bi is 1.Pi = Ai + BiThe carry out of column i (

8、Ci) is: Ci = Ai Bi + (Ai + Bi )Ci-1 = Gi + Pi Ci-1Carry-Lookahead Adder先行进位加法器如果Ai和Bi都是1，第i列产生一个输出如果Ai或者Bi为1，第i列会产生一个进位输出如果加法器的第i列会产生一个进位Gi，或者传播进位输入Pi Ci-1 ，它就会产生进位输出Ci Compute carry out (Cout) for kStep 1: Compute Gi and Pi for all columns Step 2: Compute G and P for k-bit blocksStep 3: Cin propaga

9、tes through each k-bit propagate/generate blockCarry-Lookahead Addition先行进位加法 由输入的A，B算出每一位的G，P 计算k位块的G和P (由各位的G，P算出每一位的GN:0，PN:0 ） 由每一位的GN：0，PN：0与Cin算出每一位的Cout，S。 其中第1，3步显然是可以并行处理的，计算的主要复杂度集中在了第2步。Step 1: Compute Gi and Pi for Example: 4-bit blocks (G3:0 and P3:0) : G3:0 = G3 + P3 (G2 + P2 (G1 + P1G

10、0 ) P3:0 = P3P2 P1P0Generally, Gi:j = Gi + Pi (Gi-1 + Pi-1 (Gi-2 + Pi-2Gj ) Pi:j = PiPi-1 Pi-2PjCi = Gi:j + Pi:j Ci-1Carry-Lookahead Adder先行进位加法器见中文书p173Example: 4-bit blocks (G3:0 an32-bit CLA with 4-bit Blocks由8个4位块组成的32位先行进位加法器图5-6 32位先行进位加法器（CLA）；4位CLA模块32-bit CLA with 4-bit Blocks由8For N-bit CL

11、A with k-bit blocks:一个分解成k位块的N位加法器延迟为 tCLA = tpg + tpg_block + (N/k 1)tAND_OR + ktFAtpg : delay to generate all Pi, Gi 为单独一个生成产生信号P和传播G的门电路（一个单独的AND或者OR门电路）tpg_block :delay to generate all Pi:j, Gi:j 为在k位块中生成产生信号Pi:j和输出信号Gi:j的延迟tAND_OR :delay from Cin to Cout of final AND/OR gate in k-bit CLA block

12、为在k位CLA块中Cin从AND/OR逻辑到Cout的延迟An N-bit carry-lookahead adder is generally much faster than a ripple-carry adder for N 16Carry-Lookahead Adder Delay先行进位加法器的延迟当N 16时，先行进位加法器一般总会比行波进位加法器块很多For N-bit CLA with k-bit blockSubtracter减法器图5-9 减法器；电路符号、实现减法非常简单：改变减数的符号，然后做加法。改变二进制补码的符号就是翻转所有的位，然后加一Subtracter减法

13、器图5-9 减法器；电路符号、实现Comparator: Equality相等比较器图5-11 4位相等比较器；电路符号，实现电路符号实现相等相等Comparator: Equality相等比较器图5-11Copyright 2007 Elsevier5-Comparator: Less Than小于比较器图5-12 N位数量比较器Copyright 2007 Elsevier5-17Copyright 2007 Elsevier5-F2:0Function000A & B001A | B010A + B011not used100A & B101A | B110A - B111SLTArit

14、hmetic Logic Unit (ALU)算术逻辑单元图5-14 算术逻辑单元电路符号表5-1 ALU操作SLT：小于置位操作，set if less thanCopyright 2007 Elsevier5-18Copyright 2007 Elsevier5-F2:0Function000A & B001A | B010A + B011not used100A & B101A | B110A - B111SLTALU Design算术逻辑单元设计图5-15 N位算术逻辑单元表5-1 ALU操作SLT：小于置位操作，set if less thanCopyright 2007 Elsev

15、ier5-19Copyright 2007 Elsevier5-Configure 32-bit ALU for SLT operation: A = 25 and B = 32Set Less Than (SLT) Example图5-15 N位算术逻辑单元小于置位操作SLT例子 见p179，例5.3配置一个32位算术逻辑单元用于SLT操作，假设A=25，B=32，写出控制信号和输出Y。Copyright 2007 Elsevier5-20Copyright 2007 Elsevier5-Configure 32-bit ALU for SLT operation: A = 25 and B

16、 = 32A B, so Y should be 32-bit representation of 1 (0 x00000001)F2:0 = 111F2 = 1 (adder acts as subtracter), so 25 - 32 = -7-7 has 1 in the most significant bit (S31 = 1)F1:0 = 11 multiplexer selects Y = S31 (zero extended) = 0 x00000001.Set Less Than (SLT) Example小于置位操作SLT例子图5-15 N位算术逻辑单元Copyright

17、 2007 Elsevier5-21Copyright 2007 Elsevier5-Logical shifter: shifts value to left or right and fills empty spaces with 0sEx: 11001 2 =Ex: 11001 2 =Ex: 11001 2 =Rotator: rotates bits in a circle, such that bits shifted off one end are shifted into the other endEx: 11001 ROR 2 =Ex: 11001 ROL 2 =Shifter

18、s移位器 见中文书p179逻辑移位器：左移或者右移数，以0填充空位算术移位器：和逻辑移位器一样，不过在算术右移时会把原先数据的最高标志位填充在新数据的最高标志位上。循环移位器：循环转换数字，从一端移走的位重新填充到另一端的空位上。Copyright 2007 Elsevier5- 2 = 00110Ex: 11001 2 = 11110Ex: 11001 2 = 00100Rotator: 循环移位器Ex: 11001 ROR 2 = 01110Ex: 11001 ROL 2 = 00111Shifters移位器Logical shifter: 逻辑移位器ShiftersShifter Des

19、ign移位器设计图5-16 4位移位器，左移Shifter Design移位器设计图5-16 4位移位A N = A 2N Example: 00001 2 = 00100 (1 22 = 4)Example: 11101 N = A 2N Example: 01000 2 = 00010 (8 22 = 2)Example: 10000 2 = 11100 (-16 22 = -4)Shifters as Multipliers, Dividers移位器相当于乘法、除法N位左移相当于对一个数乘以2N倍N位的算术右移相当于对一个数除以2N 。A N = A 2N Shifters asPart

20、ial products formed by multiplying a single digit of the multiplier with multiplicandShifted partial products summed to form resultMultipliers乘法图5-17 乘法；十进制，二进制部分积为乘数的一位乘以被乘数的所有位。移位这些部分积，并将它们相加就可以得到最后结果。见中文书p180Partial products formed by mul4 x 4 Multiplier 4*4乘法器图5-18 4*4乘法器；符号，原理，实现4 x 4 Multiplie

21、r 4*4乘法器图5-18 Numbers we can represent using binary representations我们可以用二进制表示数字Positive numbers正数Unsigned binary无符号二进制数Negative numbers负数Twos complement二进制补码Sign/magnitude numbers带符号的原码What about fractions?Number Systems数制系统小数部分有符号定点数可以用二进制补码或者带符号的原码表示Numbers we can represent usingTwo common notatio

22、ns:两种常用表示法Fixed-point: binary point fixedFloating-point: binary point floats to the right of the most significant 1Numbers with Fractions带小数的数- 定点数表示法有一个位于整数和小数位之间的隐含二进制小数点，类似于通常十进制数中位于整数和小数位之间的十进制小数点。- 浮点数：二进制浮点的最右边用1位表示符号。浮点数与科学计数法相似，它解决了整数和小数位长度固定的限制，允许表示一个非常大或者非常小的数。如科学计数法一样，浮点数包含了符号、尾数、基数和阶码。Tw

23、o common notations:两种常用表示法Nu6.75 using 4 integer bits and 4 fraction bits:Binary point is implied二进制小数点隐含了Fixed-Point Numbers定点数系统6.75用4位整数和4位小数位表示图5-21 6.75用4个整数位和4个小数点位表示的定点表示6.75 using 4 integer bits and Represent 7.510 using 4 integer bits and 4 fraction bits.Fixed-Point Number Example定点数系统例子Rep

24、resent 7.510 using 4 integeRepresent 7.510 using 4 integer bits and 4 fraction bits.01111000Fixed-Point Number Example定点数系统例子Represent 7.510 using 4 integeRepresentations:表示Sign/magnitude符号数值Twos complement二进制补码Example: Represent -7.510 using 4 integer and 4 fraction bitsSign/magnitude:Twos compleme

25、nt:Signed Fixed-Point Numbers带符号的定点数Representations:表示Signed FixedRepresentations:表示Sign/magnitude符号数值Twos complement二进制补码Example: Represent -7.510 using 4 integer and 4 fraction bitsSign/magnitude:符号数值11111000Twos complement:补码1. +7.5:011110002. Invert bits: 10000111 3. Add 1 to lsb:+ 1 10001000Sig

26、ned Fixed-Point Numbers带符号的定点数Representations:表示Signed FixedSimilar to decimal scientific notationFor example, write 27310 in scientific notation:273 = 2.73 102In general, a number is written in scientific notation as: M BEM = mantissa尾数B = base基数E = exponent阶码In the example, M = 2.73, B = 10, and E

27、 = 2Floating-Point Numbers浮点数系统浮点数与科学计数法相似。它解决了整数和小数位长度固定的限制，允许表示非常大或者非常小的数。浮点数包含了符号，尾数，基数和阶码Similar to decimal scientific Example: represent the value 22810 using a 32-bit floating point representationWe show three versions final version is called the IEEE 754 floating-point standardFloating-Point

28、Numbers浮点数系统 见中文书p184，例184符号阶码尾数Floating-Point Numbers浮点数系统 Convert decimal to binary (dont reverse steps 1 & 2!):22810 = 111001002 Write the number in “binary scientific notation”:111001002 = 1.110012 27 Fill in each field of the 32-bit floating point number:The sign bit is positive (0)The 8 expone

29、nt bits represent the value 7The remaining 23 bits are the mantissaFloating-Point Representation 1符号阶码尾数浮点数表示Convert decimal to binary (donFirst bit of the mantissa is always 1:22810 = 111001002 = 1.11001 27 So, no need to store it: implicit leading 1Store just fraction bits in 23-bit fieldFloating-

30、Point Representation 2浮点数表示符号阶码小数First bit of the mantissa is aBiased exponent: bias = 127 (011111112) Biased exponent = bias + exponentExponent of 7 is stored as:127 + 7 = 134 = 0 x100001102The IEEE 754 32-bit floating-point representation of 22810 in hexadecimal: 0 x43640000Floating-Point Represen

31、tation 3浮点数表示符号偏置阶码小数Biased exponent: bias = 127 (0Write -58.2510 in floating point (IEEE 754)Floating-Point Example浮点数例子Write -58.2510 in floating poiWrite -58.2510 in floating point (IEEE 754)Convert decimal to binary: 58.2510 = 111010.012Write in binary scientific notation:1.1101001 25Fill in fie

32、lds:Sign bit: 1 (negative)8 exponent bits: (127 + 5) = 132 = 10000100223 fraction bits: 110 1001 0000 0000 0000 0000in hexadecimal: 0 xC2690000Floating-Point Example浮点数例子符号偏置阶码小数Write -58.2510 in floating poiNumberSignExponentFraction0X000000000000000000000000000000001111111100000000000000000000000-

33、 11111111100000000000000000000000NaNX11111111non-zeroFloating-Point: Special Cases浮点数：特殊情况数符号阶码小数NumberSignExponentFraction0X00Single-Precision:单精度32-bit1 sign bit, 8 exponent bits, 23 fraction bitsbias = 127Double-Precision:双精度64-bit1 sign bit, 11 exponent bits, 52 fraction bitsbias = 1023Floating-

34、Point Precision浮点数精度见中文书p185Single-Precision:单精度Floating-POverflow: number too large to be represented上溢Underflow: number too small to be represented下溢Rounding modes: 舍入的模式有DownUpToward zeroTo nearestExample: round 1.100101 (1.578125) to only 3 fraction bitsDown: 1.100Up: 1.101Toward zero:1.100To ne

35、arest:1.101 (1.625 is closer to 1.578125 than 1.5 is)Floating-Point: Rounding浮点数：舍入Overflow: number too large tExtract exponent and fraction bits分开阶码和小数位Prepend leading 1 to form mantissa加上前导1，形成尾数Compare exponents比较阶码Shift smaller mantissa if necessary如果需要，对较小的尾数移位Add mantissas位数相加Normalize mantiss

36、a and adjust exponent if necessary 规整化尾数，并在需要时调整阶码8. Round result结果舍入9. Assemble exponent and fraction back into floating-point format把阶码和小数组合成浮点数Floating-Point Addition浮点数加法Extract exponent and fraction Increments on each clock edgeUsed to cycle through numbers. For example, 000, 001, 010, 011, 100

37、, 101, 110, 111, 000, 001Example uses:Digital clock displaysProgram counter: keeps track of current instruction executingCounters计数器图5-30 计数器电路符号图5-31 N位计数器N位二进制计数器是包含了时钟和复位输入，N位输出Q的时序算术电路。计数器是产生特定的二进制计数序列的电路Increments on each clock edgeCImplementation:Shift a new bit in on each clock edgeShift a bi

38、t out on each clock edge同时，移出一位Serial-to-parallel converter: converts serial input (Sin) to parallel output (Q0:N-1)Shift Registers移位寄存器Symbol:图5-33 移位寄存器电路符号图5-34 移位寄存器电路原理图在每一个时钟上升沿，会从Sin移入一个新的位移位寄存器可以看作串行到并行的转换器Implementation:Shift a new bitEfficiently store large amounts of data3 common types:Dy

39、namic random access memory (DRAM)动态随机存储器Static random access memory (SRAM)静态随机存储器Read only memory (ROM)只读存储器M-bit data value read/ written at each unique N-bit addressMemory Arrays存储器阵列图5-38 一般存储器阵列电路符号存储器阵列：有效存储大量数据地址阵列存储器由一个二维存储器单元阵列构成。存储器可以读取或者写入内容到阵列中的一行。这一行由地址指定。读出或者写入的值称为数据。Efficiently store l

40、arge amount2-dimensional array of bit cells Each bit cell stores one bitN address bits and M data bits:2N rows and M columnsDepth: number of rows (number of words)Width: number of columns (size of word)Array size: depth width = 2N M Memory Arrays存储器阵列图5-38 一般存储器阵列电路符号图5-39 4*3存储器阵列；电路符号，功能存储器由一个二维存储

41、器单元阵列构成。一个有N位地址和M位数据的阵列就有2N行和M列。阵列的深度是行数，宽度是列数，也称为字大小。阵列的大小就是深度*宽度2-dimensional array of bit cel22 3-bit arrayNumber of words: 4Word size: 3-bitsFor example, the 3-bit word stored at address 10 is 100Memory Array Example存储器阵列例子图5-39 4*3存储器阵列；电路符号，功能22 3-bit arrayMemory Array EMemory Arrays存储器阵列图5-40

42、 32Kb阵列：深度=210=1024字，宽度=32位Memory Arrays存储器阵列图5-40 32Kb阵ZMemory Array Bit Cells存储器阵列位单元图5-41 位单元字线存储位位线ZMemory Array Bit Cells存储器阵列位单01ZZMemory Array Bit Cells存储器阵列位单元图5-41 位单元字线存储位位线01ZZMemory Array Bit Cells存储器阵Wordline: 字线like an enablesingle row in memory array read/writtencorresponds to unique

43、addressonly one wordline HIGH at onceMemory Array存储器阵列图5-42 4*3存储器阵列存储器阵列以位单元构成的阵列组成，其中每个位单元存储1位数据。每一个位单元与特定字线和特定位线相连。对于每一个地址位的组合，存储器将字线设置为高电平，并激活此行中的位单元Wordline: 字线Memory Array存储器阵列图Random access memory (RAM): volatileRead only memory (ROM): nonvolatileTypes of Memory存储器类型随机访问存储器：是易失的，即关掉电源时就会丢失数据只

44、读存储器：是非易失的，即没有电源时也可以保存数据Random access memory (RAM): voVolatile: loses its data when power offRead and written quickly快速地读写Main memory in your computer is RAM (DRAM)Historically called random access memory because any data word accessed as easily as any other (in contrast to sequential access memorie

45、s such as a tape recorder)RAM: Random Access Memory随机访问存储器易失的RAM和ROM因为一些历史的原因获得现在的名字，但是现在也不再有意义了。RAM之所以称为随机访问存储器，是因为访问任何数据字的延迟都是相同。ROM之所以称为只读存储器，因为在历史上它只能读，而不能被写入。现在大部分ROM可以读也可以写。Volatile: loses its data when Nonvolatile: retains data when power offRead quickly, but writing is impossible or slow读快，但

46、是不能写或写的慢Flash memory in cameras, thumb drives, and digital cameras are all ROMsHistorically called read only memory because ROMs were written at manufacturing time or by burning fuses. Once ROM was configured, it could not be written again. This is no longer the case for Flash memory and other types

47、 of ROMs.ROM: Read Only Memory只读存储器非易失的Nonvolatile: retains data whenDRAM (Dynamic random access memory)SRAM (Static random access memory)Differ in how they store data:DRAM uses a capacitorSRAM uses cross-coupled invertersTypes of RAM RAM的类型- 动态随机访问存储器DRAM- 静态随机访问存储器SRAM- 动态RAM以电容充放电存储数据，静态RAM使用交叉耦合

48、的反向器对存储DRAM (Dynamic random access meData bits stored on capacitor数据位存储在电容上Dynamic because the value needs to be refreshed (rewritten) periodically and after read:Charge leakage from the capacitor degrades the valueReading destroys the stored valueDRAM动态随机访问存储器图5-45 DRAM存储值充电泄漏读会破坏存储在电容中的位值Data bits

49、 stored on capacitor数DRAM动态随机访问存储器图5-45 DRAM存储值当电容充电到Vdd时，存储位为1当放电到GND时，存储位为0DRAM动态随机访问存储器图5-45 DRAM存储值当电容SRAM静态随机访问存储器图5-46 SRAM位单元SRAM静态随机访问存储器图5-46 SRAM位单元DRAM bit cell:SRAM bit cell:Memory Arrays Review存储器阵列回顾图5-42 4*3存储器阵列DRAM bit cell:SRAM bit cell:MeROM: Dot Notation图5-49 4*3的ROM：点表示法图5-48 包含

50、0和1的ROM位单元随机访问存储器：点表示法ROM: Dot Notation图5-49 4*3的ROROM Storage只读存储器的存储图5-49 4*3的ROM：点表示法ROM Storage只读存储器的存储图5-49 4*3的Data2 = A1 A0Data1 = A1 + A0Data0 = A1A0ROM Logic只读存储器的逻辑图5-49 4*3的ROM：点表示法Data2 = A1 A0ROM Logic只读存储器的Implement the following logic functions using a 22 3-bit ROM:X = ABY = A + BZ =

51、A BExample: Logic with ROMs例子：带只读存储器的逻辑Implement the following logic Implement the following logic functions using a 22 3-bit ROM:X = ABY = A + BZ = A BExample: Logic with ROMs例子：带只读存储器的逻辑Implement the following logic Data2 = A1 A0Data1 = A1 + A0Data0 = A1A0Logic with Any Memory Array带任意存储器阵列的逻辑Data2 = A1 A0Logic with Any Implement the following logic functions using a 22 3-bit memory array:X = ABY = A + BZ = A BLogic with Memory Arrays带存储器阵列的逻辑Implement the following logic Impl