算术逻辑部件 设 计 蒋小龙 2001.7.5
算 术 逻 辑 部 件 设 计 蒋 小 龙 2001.7.5
声明 作此资料为本人个人行为,此资料版权为本人所有。 你可以任意使用,但你非经本人允许不得对此资料内容作任何修改 你因使用此资料所带来任何收益,本人均不染指;因使用此资料所引起的任何不良后果,本人不承担任 何形式的责任 出版物引用,但请注明! 蒋小龙 2001.7.5
1 声 明 作此资料为本人个人行为，此资料版权为本人所有。 你可以任意使用，但你非经本人允许不得对此资料内容作任何修改。 你因使用此资料所带来任何收益，本人均不染指；因使用此资料所引起的任何不良后果，本人不承担任 何形式的责任。 出版物引用，但请注明！ 蒋 小 龙 2001.7.5
目 录 4位加法器 3、4位超前进位链…… 4、16位超前进位链…… 5、更多位超前进位链 3445689 6、算术运算设计…… 7、逻辑操作设计… 9、设计示例1 16位7功能算术逻辑部件 10、设计示例2——4位16功能算术逻辑部件 后记 …20 个人介绍
2 目 录 声明 …………………………………………………………………………………… 1 0、 约定 …………………………………………………………………………………… 3 1、 一位加法器 …………………………………………………………………………… 4 2、 4 位加法器 …………………………………………………………………………… 4 3、 4 位超前进位链 ……………………………………………………………………… 5 4、 16 位超前进位链 ……………………………………………………………………… 6 5、 更多位超前进位链 …………………………………………………………………… 8 6、 算术运算设计 ………………………………………………………………………… 9 7、 逻辑操作设计 ………………………………………………………………………… 10 8、 标识位 ………………………………………………………………………………… 10 9、 设计示例 1 —— 16 位7 功能算术逻辑部件 ………………………………………… 12 10、设计示例2 —— 4 位 16 功能算术逻辑部件 ………………………………………… 15 后记 …………………………………………………………………………………… 20 个人介绍 ……………………………………………………………………………… 21
0、约定 算数据 A:操作数、位串 B:操作数、位串 D:结果数据、位串,与操作数位宽同 Ci:进位、一位,以前操作所产生,本次操作视情况考虑 Co:进位、一位,本次操作产生; C:进位、位串,由操作数生成的进位,不会比操作数位宽小; G:进位生成、位串,与操作数位宽同,具体意义见文中; 进位传输、位串,与操作数位宽同,具体意义见文中 运算符: +:对其两边的数据作加法操作 a+ B 用左边的数据减去右边的数据作 对跟在其后的数据作取补操作,即用0减去跟在其后的数据 B &:对其两边的数据按位作与操作 a& B #:对其两边的数据按位作或操作; A B @:对其两边的数据按位作异或操作 A eB 对跟在其后的数据作按位取反操作; 对运算符的约定只在文中论述的时候有效。 设计示例用 VerilogHDL语言实现,所有的东西符合 VerilogHDL语法。如有疑问,请参阅 VerilogHDL 资料
3 0、约定 运算数据： A：操作数、位串； B：操作数、位串； D：结果数据、位串，与操作数位宽同； Ci：进位、一位，以前操作所产生，本次操作视情况考虑； Co：进位、一位，本次操作产生； C：进位、位串，由操作数生成的进位，不会比操作数位宽小； G：进位生成、位串，与操作数位宽同，具体意义见文中； P：进位传输、位串, 与操作数位宽同，具体意义见文中。 运算符： +：对其两边的数据作加法操作： A + B； -：用左边的数据减去右边的数据作； A - B -：对跟在其后的数据作取补操作，即用0 减去跟在其后的数据； - B &：对其两边的数据按位作与操作； A & B #：对其两边的数据按位作或操作； A # B @：对其两边的数据按位作异或操作； A @ B ~：对跟在其后的数据作按位取反操作； ~ B 对运算符的约定只在文中论述的时候有效。 设计示例用 VerilogHDL 语言实现，所有的东西符合 VerilogHDL 语法。如有疑问，请参阅 VerilogHDL 资料
1、一位加法器 考虑一位全加器。如右图示真值表,D、Co逻辑表达式为 D =AbAcI Co =a&b#a& ci fb ci 0110 a&b#(a# b)& ci 不难作出其逻辑图,此处省略。 位全加器又称“保留进位加法器” 因其简单,是研究其它高性能、高速加法器的 基础。因其简单、快速,是构成其它高速处理 部件的基本元件。其符号如右。 CSR Ci 由真值表可知,若将各位取反,并无影响。 2、4位加法器 CSA CSA CSA CSA 四位加法器可以采用四个一位全加器级连成串行进位加法器。如上图示 对于这种方式,因高位运算必须等低位进位来到后才能进行。因此,它的延迟非常可观。高速运算肯定 无法胜任。 对串行进位加法器研究可得:运算的延迟是由于进位的延迟。基于此,减小进位的延迟非常有效。 下面讨论的超前进位链能有效减少进位的延迟,它由进位门产生进位,各进位彼此独立,不依赖于进位 传播。因此,它的延迟非常小、速度非常高 既然进位已经解决,则加法器值 D=AB@C (2-1) 不存在问题 由此可见,进位的解决是核心
4 1、一位加法器 1、一位加法器 考虑一位全加器。如右图示真值表，D、Co 逻辑表达式为： D = A @ B @ Ci (1-1) Co = A & B # A & Ci # B & Ci (1-2) = A & B # (A # B) & Ci (1-3) 不难作出其逻辑图，此处省略。 一位全加器又称“保留进位加法器”。 因其简单，是研究其它高性能、高速加法器的 基础。因其简单、快速，是构成其它高速处理 部件的基本元件。其符号如右。 由真值表可知，若将各位取反，并无影响。 2、4 位加法器 四位加法器可以采用四个一位全加器级连成串行进位加法器。如上图示： 对于这种方式，因高位运算必须等低位进位来到后才能进行。因此，它的延迟非常可观。高速运算肯定 无法胜任。 对串行进位加法器研究可得：运算的延迟是由于进位的延迟。基于此，减小进位的延迟非常有效。 下面讨论的超前进位链能有效减少进位的延迟，它由进位门产生进位，各进位彼此独立，不依赖于进位 传播。因此，它的延迟非常小、速度非常高。 既然进位已经解决，则加法器值 D = A @ B @ C (2-1) 不存在问题。 由此可见，进位的解决是核心
3、4位超前进位链 千究式(1-3) Co =a&b#(a# b)& Ci (3-1) 可以看出:若A、B均为1,则产生进位输出:若A、B存在1,则进位输出依赖于低位进位Ci。换一种说法: 若A、B均为1,则产生进位;若A、B存在1,则传输(低位进位(Ci) A、B、Ci在本位运算,产生本位值D,向高位进位Co。更一般的 Dn An g Bn g Cn Cn+1 =An Bn #(An Bn)& Cn 令: Gn An Bn (3-4) Pn An t Bn (3-5) 则式(3.-3)为 Cn+1 gn pn cr (3-6) 这样,就引入了进位产生函数(G)、进位传输函数(P)。其意义为:若Gn为1,必定产生进位;若Pn为 1,则向高位传输(低位)进位(Cn),可认为低位进位越过本位直接向高位进位。此处是否说明仍存在进位传播, 使进位延迟无法减小? 以4位超前进位链为例 Cl Go Po Co Go Po& ci #P1 G1 Pl& go# pi& po ci C3=G2#P2&C2 G2#P2&G1#P2&P1&G0#P2&P1&P0&Ci (3-9) C4=G3#P3&C3 G3#P3&G2#P3&P2&G1#P3&P2&P1&G0# P3 p2& pi& po ci 其逻辑图如下: ■ ■■■■■ ■6
5 3、4 位超前进位链 研究式(1-3) Co = A & B # (A # B) & Ci (3-1) 可以看出：若A、B 均为 1，则产生进位输出；若A、B 存在 1，则进位输出依赖于低位进位Ci。换一种说法： 若A、B 均为 1，则产生进位；若A、B 存在 1，则传输(低位)进位(Ci)。 A、B、Ci 在本位运算，产生本位值D，向高位进位Co。更一般的： Dn = An @ Bn @ Cn (3-2) Cn+1 = An & Bn # (An # Bn) & Cn (3-3) 令： Gn = An & Bn (3-4) Pn = An # Bn (3-5) 则式(3.-3)为： Cn+1 = Gn # Pn & Cn (3-6) 这样，就引入了进位产生函数(G)、进位传输函数(P)。其意义为：若 Gn 为 1，必定产生进位；若 Pn 为 1，则向高位传输(低位)进位(Cn),可认为低位进位越过本位直接向高位进位。此处是否说明仍存在进位传播， 使进位延迟无法减小？ 以4 位超前进位链为例： C0 = Ci C1 = G0 # P0 & C0 = G0 # P0 & Ci (3-7) C2 = G1 # P1 & C1 = G1 # P1 & G0 # P1 & P0 & Ci (3-8) C3 = G2 # P2 & C2 = G2 # P2 & G1 # P2 & P1 & G0 # P2 & P1 & P0 & Ci (3-9) C4 = G3 # P3 & C3 = G3 # P3 & G2 # P3 & P2 & G1 # P3 & P2 & P1 & G0 # P3 & P2 & P1 & P0 & Ci (3-10) Co = C4 其逻辑图如下：
可见,将迭代关系去掉,则各位彼此独立,进位传播不复存在。因此,总的延迟是两级门的延迟。其高 速也就自不待言 对式(2-1) D=ABOC (3-11) (C A)&b#a& b)@c (C A)&b#a&(B)#a&A#CB)&b#A&CA&b&B))0 (C A&(a #b)#b)&(A#B)#a&b&(a&B))@c ((C A)#B))&(A# B)#A&b&(A#B)))@c (c(a&b))&(a# b)#a&b&((a b))@ c (A&B)@(A#B)@C(3-12) G@PgC D=A@=GOP@C=(A &B)@(A b)@C (3-14) 此特性对算术逻辑部件的设计非常有用! 4、16位超前进位链 对4位超前进位加法器:二输入数据A、B,进位输入Ci,生成数据D,进位Co。因此,可以用4个4 位超前进位进位链单元串接形成16位进位链。这存在问题,就是单元内虽是超前进位,但单元间却是串行, 存在进位传播问题,延迟不会短,速度也就高不了! 从4位超前进位链得到启示,能否在单元间实行超前进位? 考察第4、8、12、16位的进位,会得到 C4=G3#P3&C3 =(G3#B3&C2#P3&P2&G1#P3&P2&P1&G0)# (P3&P2&P1&P0)&Ci (4-1) C8=G7#P7&C7 (G7#P7&G6#P7&P6&G5#P&P6&P5&G4) (P7&B6&P5&P4)&(G3#P3&C2#P3&P2&G1#P3&P2&P1&G0) P7&P6&P5&P4)&(P3&P2&P1&P0)&Ci (4-2) C12=G11#P11&C11 (G11#P1l&G10#P1l&P10&G9#P11&P10&P9&G8) (P11&P10&P&P8)&(G7#P7&G6#P7&P6&G5#P7&P6&P5&GA)# (P1l&P10&P&P8)&(P7&B6&P5&P4) &G2#P3&P2&G1#P3&P&P1&G0)# (P11&P10&P9&P8) P7&P6&P5&P4)&(P3&P2&P1&P0)&Ci C16=G15#P15&C15 (G15#P15&G14#P15&P14&G13#P15&P4&P13&G12)# (P15&P14&P13&P2) (G1l#Pl1&G10#P11&P10&G9#P11&P10&P9&G8)
6 可见，将迭代关系去掉，则各位彼此独立，进位传播不复存在。因此，总的延迟是两级门的延迟。其高 速也就自不待言。 对式(2-1) D = A @ B @ C (3-11) = ((~ A) & B # A & (~ B)) @ C = ((~ A) & B # A & (~ B) # (~ A) & A # (~ B) & B # A & (~ A) & B & (~ B) # (~ A) & A # (~ B) & B # A & (~ A) & B & (~ B) # (~ A) & A # (~ B) & B # A & (~ A) & B & (~ B)) @ C = ((~ A) & (A # B) # (~ B) & (A # B) # A & B & (~ A) & (~ B)) @ C = (((~ A) # (~ B)) & (A # B) # A & B & (~ (A # B))) @ C = ((~ (A & B)) & (A # B) # A & B & (~ (A # B))) @ C = (A & B) @ (A # B) @ C (3-12) = G @ P @ C (3-13) 可见： D = A @ B @ C = G @ P @ C = (A & B) @ (A # B) @ C (3-14) 此特性对算术逻辑部件的设计非常有用！ 4、16 位超前进位链 对 4 位超前进位加法器：二输入数据 A、B，进位输入 Ci，生成数据 D，进位 Co。因此，可以用 4 个 4 位超前进位进位链单元串接形成 16 位进位链。这存在问题，就是单元内虽是超前进位，但单元间却是串行， 存在进位传播问题，延迟不会短，速度也就高不了！ 从4 位超前进位链得到启示，能否在单元间实行超前进位？ 考察第4、8、12、16 位的进位，会得到： C4 = G3 # P3 & C3 = (G3 # P3 & G2 # P3 & P2 & G1 # P3 & P2 & P1 & G0) # (P3 & P2 & P1 & P0) & Ci (4-1) C8 = G7 # P7 & C7 = (G7 # P7 & G6 # P7 & P6 & G5 # P7 & P6 & P5 & G4) # (P7 & P6 & P5 & P4) & (G3 # P3 & G2 # P3 & P2 & G1 # P3 & P2 & P1 & G0) # (P7 & P6 & P5 & P4) & (P3 & P2 & P1 & P0) & Ci (4-2) C12 = G11 # P11 & C11 = (G11 # P11 & G10 # P11 & P10 & G9 # P11 & P10 & P9 & G8) # (P11 & P10 & P9 & P8) & (G7 # P7 & G6 # P7 & P6 & G5 # P7 & P6 & P5 & G4) # (P11 & P10 & P9 & P8) & (P7 & P6 & P5 & P4) & (G3 # P3 & G2 # P3 & P2 & G1 # P3 & P2 & P1 & G0) # (P11 & P10 & P9 & P8) & (P7 & P6 & P5 & P4) & (P3 & P2 & P1 & P0) & Ci (4-3) C16 = G15 # P15 & C15 = (G15 # P15 & G14 # P15 & P14 & G13 # P15 & P14 & P13 & G12) # (P15 & P14 & P13 & P12) & (G11 # P11 & G10 # P11 & P10 & G9 # P11 & P10 & P9 & G8) #
(P15&P14&P3&P12)&(P1&P10&P9&P8)& (G7#P7&G6#P&P6&G5#P7&P6&P5&G4)井 (P15&P14&P3&P12)&(P1&P10&P9&P8)& P7&B6&P5&P4)&(G3#P3&C2#P3&P&G1#P3&P2&P1&G0)# (P15&P14&P13&P12)&(P1&P10&P&P8) P7&P6&P5&P4)&(P3&P&P1&P0)&Ci GX4=G15#P15&G14#P15&P14&G13#P15&P14&P13&G12 GX3=G11#P11&G10#P11&P10&G9#P11&P10&P9&GS GX2=G7#P7&G6#P7&P6&G5#P7&P6&P5&G4 GⅪ1=G3#P3&G2#P3&P&G1#P3&P2&P1&G0 PX4=P15&P14&P13&P12 PX3=P11&P10&P9&P8 (4-10 PX2=P7&P6&P5&P4 (4-11) PXI= P3& p2& pi& po (4-12) 可得 CA =GXO PXo ci (4-13) C8 =GX1 PXI& gXo t pxi& pxo c (4-14) C12= GX2 PX2 GX1 PX2 pxl gXo pX2 & pxl& pxo ci (4-15) C16 = GX3 PX3& GX2 PX3& PX2& GX1 PX3& px2 pxl& gxo pX3& px2& pxl& pxo ci (4-16) 比较式((4-13)(4-16))与式(3-7)~(3-10),可看出:单元间进位也可用超前进位链完成 6位超前进位链如下: G[15:12]P[15:12]G[11:8]P[11:8]G[7:4]P[7:4 G[3:0]P【3:0 超前进位链 超前进位链 超前进位链 超前进位链 Gx Px C C[16:13] c[2:9 ct8:5 c[4:1] G3 P3 G2 P2 G1 P1 G0 PI 超前进位链
7 (P15 & P14 & P13 & P12) & (P11 & P10 & P9 & P8) & (G7 # P7 & G6 # P7 & P6 & G5 # P7 & P6 & P5 & G4) # (P15 & P14 & P13 & P12) & (P11 & P10 & P9 & P8) & (P7 & P6 & P5 & P4) & (G3 # P3 & G2 # P3 & P2 & G1 # P3 & P2 & P1 & G0) # (P15 & P14 & P13 & P12) & (P11 & P10 & P9 & P8) & (P7 & P6 & P5 & P4) & (P3 & P2 & P1 & P0) & Ci (4-4) 令： GX4 = G15 # P15 & G14 # P15 & P14 & G13 # P15 & P14 & P13 & G12 (4-5) GX3 = G11 # P11 & G10 # P11 & P10 & G9 # P11 & P10 & P9 & G8 (4-6) GX2 = G7 # P7 & G6 # P7 & P6 & G5 # P7 & P6 & P5 & G4 (4-7) GX1 = G3 # P3 & G2 # P3 & P2 & G1 # P3 & P2 & P1 & G0 (4-8) PX4 = P15 & P14 & P13 & P12 (4-9) PX3 = P11 & P10 & P9 & P8 (4-10) PX2 = P7 & P6 & P5 & P4 (4-11) PX1 = P3 & P2 & P1 & P0 (4-12) 可得： C4 = GX0 # PX0 & Ci (4-13) C8 = GX1 # PX1 & GX0 # PX1 & PX0 & Ci (4-14) C12 = GX2 # PX2 & GX1 # PX2 & PX1 & GX0 # PX2 & PX1 & PX0 & Ci (4-15) C16 = GX3 # PX3 & GX2 # PX3 & PX2 & GX1 # PX3 & PX2 & PX1 & GX0 # PX3 & PX2 & PX1 & PX0 & Ci (4-16) 比较式((4-13)~(4-16))与式((3-7)~(3-10))，可看出：单元间进位也可用超前进位链完成。 16 位超前进位链如下：
4位超前进位链如下: P1 GI Po Go 61 实际应用中,最高位进位一般不直接使用,对其要求可降低。本图中,此位需四级门延迟。 综合考察式(4-5)(4-16)及上两幅图,可发现由G、P生成GX、PX有两级门延迟,由GX、PX生成单元 间进位有两级门延迟,再需两级两级门延迟生成最终的进位。因此,总共需六级门延迟 至此,问题已得到解决。 5、更多位超前进位链 对更多位超前进位链可参照上节,形成多级超前进位链树。 以64位超前进位链为例。 可用4位的超前进位链单元构成。第级用16个单元,输出直接的进位;第二级用4个单元,用以形 成第一级单元间进位;第三级用1个单元,为第二级提供单元间进位。这样,形成进位需10级门延迟 二级间需2,二、三级间需2,三、二级间需2,二、一级间需2,第一级输出需2。 也可用8位超前进位链单元构成。第一级用8个单元,输出直接的进位;第二级用1个单元,为第一级 提供单元间进位。这样,形成进位需6级门延迟。 实际上,每增加一级,就需要增加形成GX、PX的时间2,再形成进位需时2,总共增加4。 这是否说明后一种方案就一定快!这不一定。需考虑电路中连线延迟、逻辑门的扇入扇出能力、逻辑门 的延迟等多方面的因素 再考虑32位、128位超前进位链,应如何实现。 在实际应用中,拟制多种方案,考虑多方面因素,得到最优结果 至此,作为高速加法器的核心—一超前进位链——的讨论已完成
8 4 位超前进位链如下： 实际应用中，最高位进位一般不直接使用，对其要求可降低。本图中，此位需四级门延迟。 综合考察式(4-5)~(4-16)及上两幅图，可发现由 G、P 生成 GX、PX 有两级门延迟，由 GX、PX 生成单元 间进位有两级门延迟，再需两级两级门延迟生成最终的进位。因此，总共需六级门延迟。 至此，问题已得到解决。 5、更多位超前进位链 对更多位超前进位链可参照上节，形成多级超前进位链树。 以64 位超前进位链为例。 可用 4 位的超前进位链单元构成。第一级用 16 个单元，输出直接的进位；第二级用 4 个单元，用以形 成第一级单元间进位；第三级用 1 个单元，为第二级提供单元间进位。这样，形成进位需10 级门延迟：一、 二级间需2，二、三级间需2，三、二级间需2，二、一级间需2，第一级输出需2。 也可用8 位超前进位链单元构成。第一级用8 个单元，输出直接的进位；第二级用 1 个单元，为第一级 提供单元间进位。这样，形成进位需6 级门延迟。 实际上，每增加一级，就需要增加形成GX、PX 的时间2，再形成进位需时2，总共增加4。 这是否说明后一种方案就一定快！这不一定。需考虑电路中连线延迟、逻辑门的扇入扇出能力、逻辑门 的延迟等多方面的因素。 再考虑32 位、128 位超前进位链，应如何实现。 在实际应用中，拟制多种方案，考虑多方面因素，得到最优结果。 至此，作为高速加法器的核心——超前进位链——的讨论已完成
6、算术运算设计 减法的数学表达式如下 按代数运算法则以及补码的定义可得: A+(B)-Ci (6-3) A+(B+1-Ci A+B)+1-Ci (6-5) =A+CB)+(1-Ci) (6-6) =A+B)+Ci (6-7) 由此得出的结论: 从被减数A减去减数B以及借位Ci,可以将A加上将B的按位取反的值以及将借位Ci取反的值! 加法的数学表达式 D =A+B+ C (6-8) 比照式(6-7)、(6-8),作出如下结论: 作加法时将A、B、Ci相加,作减法时将B、Ci取反与A相加! 引入一控制信号:as。当其为0时作加法操作;当其为1时作减法操作。见下式 D=A+(as?B: B))+(as Ci (6-9) D =A+asv B)+(as Ci) 6-10 在式(6-9)中,有一运算操作符:?:;其表达式为: 条件?条件为真选项:条件为假选项 用之,因其为一位信号,不能与位串信号B直接操作 在式(6-10)中,有一信号asw,它与信号B位宽相同,它由信号as填充 超前进位链的输入值为G、P。作加法运算时,G、P为: g =a& B (6-11) P=A#B (6-12) 作减法运算时,G、P为: G =A& B) (6-13) P =A#(B) (6-14) 对于可控加减法运算 G =A& asv g B) (6-15) P=A#(asv B) (6-16) 至此,算术运算己得到解决
9 6、算术运算设计 减法的数学表达式如下： D = A - B - Ci (6-1) 按代数运算法则以及补码的定义可得： D = A - B - Ci (6-2) = A + (- B) - Ci (6-3) = A + (~ B + 1) - Ci (6-4) = A + (~ B) + 1 - Ci (6-5) = A + (~ B) + (1 – Ci) (6-6) = A + (~ B) + (~ Ci) (6-7) 由此得出的结论： 从被减数A 减去减数B 以及借位Ci，可以将A 加上将B 的按位取反的值以及将借位Ci 取反的值！ 加法的数学表达式： D = A + B + Ci (6-8) 比照式(6-7)、(6-8)，作出如下结论： 作加法时将A、B、Ci 相加，作减法时将B、Ci 取反与A 相加！ 引入一控制信号：as。当其为0 时作加法操作；当其为 1 时作减法操作。见下式： D = A + (as ? B : (~ B)) + (as @ Ci) (6-9) D = A + (asv @ B) + (as @ Ci) (6-10) 在式(6-9)中，有一运算操作符：? : ；其表达式为： 条件 ? 条件为真选项 : 条件为假选项 用之，因其为一位信号，不能与位串信号B 直接操作。 在式(6-10)中，有一信号asv,它与信号B 位宽相同，它由信号as 填充。 超前进位链的输入值为G、P。作加法运算时，G、P 为： G = A & B (6-11) P = A # B (6-12) 作减法运算时，G、P 为： G = A & (~ B) (6-13) P = A # (~ B) (6-14) 对于可控加减法运算 G = A & (asv @ B) (6-15) P = A # (asv @ B) (6-16) 至此，算术运算已得到解决！