做计组实验的时候我见过太多人在Logisim里用行波进位加法器交差——仿真能跑出正确结果可一旦被问到关键路径上有几级门延迟为什么不能在更高位上直接并行就答不上来。这篇我带你手把手把4位先行进位加法器Carry Lookahead AdderCLA在Logisim里从零搭出来不只给一张能过的电路图还会讲清楚每一根线为什么这么连、每一个门为什么放在这个位置。适合正在上计算机组成原理课、或者想真正理解加法器内部机制的同学参考搭完之后你再去理解16位、32位CLA基本上就是复制粘贴的事。1. 为什么不用行波进位加法器——先行进位解决的本质问题1.1 行波进位的延迟瓶颈先看一个最基础的事实一个4位行波进位加法器Ripple Carry AdderRCA是把4个全加器串起来的低位全加器产生的进位C1要作为高位全加器的输入C0。这个结构教学上非常好理解但它的致命弱点是进位是逐级传上去的。假设每个门电路的延迟是t一个全加器的进位输出C1要经过两个门延迟才能稳定实际上还要看具体门级实现这里先用理想化模型那么第4位的结果要等C1-C2-C3-C4逐级传递总共需要大约8个门延迟才能出最终结果。如果是32位加法器这个延迟就变成64个门延迟量级。现代CPU里加法器处于ALU的核心位置每一次算术运算都要走一遍这条关键路径64个门延迟对于几百MHz甚至几GHz的时钟来说是完全不可接受的。所以工程上要想办法把进位提前算出来让高位不需要等待低位逐级传递。这就是先行进位carry lookahead的由来。1.2 先行进位的核心思路把进位算出来而不是等出来先行进位的思路很直白既然进位链是串行的瓶颈那我能不能根据输入的A和B直接推导出每一位的进位表达式答案是可以而且逻辑上一点都不复杂。关键洞察是每一位的进位输出只取决于两个东西这一位的输入A、B能否自己产生进位比如A和B都是1那不管低位进位什么这一位必然向高位产生进位这一位能否把低位的进位传递上去比如A和B中有一个是1那低位来的进位会原样传到高位把这两个能力抽象成两个信号一个叫生成信号GGenerate一个叫传播信号PPropagate。有了G和P每一位的进位表达式就可以写成递归形式然后逐层展开让C4直接由C0和各位的G、P组合逻辑算出不再经过中间位的逐级延迟。我在实际教学中发现很多同学卡在抽象这一步——总觉得G、P是凭空冒出来的概念。其实它就是你把全加器的真值表重新归纳了一遍而已下一节详细拆开看。2. 从全加器到G、P信号真值表里藏着的数学2.1 全加器的Si与Ci1表达式先把全加器Full Adder的输入输出关系列清楚。全加器有三个输入A_i、B_i本位的两个加数和C_i来自低位的进位两个输出S_i本位和和C_{i1}向高位的进位。真值表如下A_iB_iC_iS_iC_{i1}0000000110010100110110010101011100111111从这个真值表可以写出S_i A_i XOR B_i XOR C_iC_{i1} A_i·B_i (A_i XOR B_i)·C_i注意C_{i1}这个表达式非常关键它拆成了两部分。第一部分A_i·B_i与C_i无关第二部分(A_i XOR B_i)·C_i和低位的进位有关。这个结构正好对应前面说的生成和传播。2.2 G生成和P传播的物理意义现在定义两个信号G_i A_i · B_iP_i A_i XOR B_i这样一来进位表达式就变成C_{i1} G_i P_i · C_i这个式子的含义非常清楚如果G_i为1说明A_i和B_i都是1那么无论C_i是0还是1本位必然向高位产生进位1。这叫生成。如果P_i为1说明A_i和B_i恰好有一个是1也就是XOR为1那么当C_i为1时本位把进位传上去C_{i1}1当C_i为0时C_{i1}0。也就是说本位把低位的进位原样传递上去。这叫传播。如果G_i和P_i都为0说明A_i和B_i都是0那么无论C_i是什么C_{i1}都是0。用生活化的类比来说G是一个主动制造麻烦的人他自己就能把进位这件事搞出来P是一个传声筒别人喊话他就传别人不喊他就不传。在Logisim里实现这一步非常简单G_i就是一个AND门P_i就是一个XOR门。每个位用一个AND加一个XOR四个位就是四个AND加四个XOR。2.3 四位CLA的进位方程推导有了C_{i1} G_i P_i·C_i这个递推式就可以从C0开始逐层展开C1 G0 P0·C0C2 G1 P1·C1 G1 P1·G0 P1·P0·C0C3 G2 P2·C2 G2 P2·G1 P2·P1·G0 P2·P1·P0·C0C4 G3 P3·C3 G3 P3·G2 P3·P2·G1 P3·P2·P1·G0 P3·P2·P1·P0·C0这就是4位先行进位加法器的核心公式。注意看C4的表达式里所有输入都是G0到G3、P0到P3和C0它们全部来自输入信号A、B不依赖任何中间的进位。也就是说C4可以在一个组合逻辑周期内直接算出来不需要等待C1、C2、C3逐级产生。代价是什么代价是逻辑门的扇入fan-in变大了。C4的表达式里最后一项是5个变量的与在Logisim里需要5输入的AND门或者用多级门来凑。这也是为什么16位、32位加法器不会无限地把展开式写下去——到C16的时候需要17输入的与门或者多层展开门延迟和布线复杂度都会上升。所以工程上通常的做法是4位一组做一个CLA单元然后把多个CLA单元再用行波方式串联或者再做一层组间先行进位。这种分级的思想等你理解了4位版本之后自然就能迁移过去。3. Logisim核心搭建先做进位链再做求和3.1 工程准备位宽、引脚和子电路规划在开始连线之前先把工程规划好避免搭到一半发现端口不够用或者方向不对。第一步打开Logisim新建一个项目主电路默认叫main。我建议的命名方式是主电路就叫CLA_4bit另外建一个子电路叫FullAdder用来封装全加器。虽然全加器也可以用门直接在主电路里搭但封装成子电路之后主电路的连线会清爽很多后期检查也容易定位问题。在Logisim里新建子电路的方法是菜单栏 Project - Add Circuit输入名字FullAdder。进入FullAdder子电路后用Input和Output引脚定义好端口A、B、Cin是输入S、Cout是输出。注意Logisim的引脚默认有方向属性输入引脚默认朝右Facing: East输出引脚默认朝右。建议把输入放在左边、输出放在右边这样子电路封装后在主电路里使用时信号流向最直观。关于端的命名Logisim中子电路的引脚名称就是你在子电路里给Input/Output引脚设置的Label。主电路引用子电路时这些名字会显示在封装块的引脚旁边方便连线识别。所以命名不要偷懒A0、A1这种和In0、In1这种后期排查时效率完全不一样。3.2 用逻辑门搭进位生成单元这一步的目标是对每一位i用AND门算G_i用XOR门算P_i同时用全加器逻辑算S_i。先在FullAdder子电路里把全加器搭好逻辑非常简单用两个XOR门串联S A XOR B然后再XOR Cin。Logisim里XOR门默认是2输入的所以串联两个即可。进位Cout A·B (A XOR B)·Cin需要两个AND门、一个OR门。搭的时候注意一个细节中间那个A XOR B的信号会被用到两次一次是算S一次是算Cout。在Logisim里一个信号可以通过分线或者说连线的分支同时送到两个地方直接把线从XOR输出口再拉一条到AND门即可。不需要复制一份电路也不需要加任何缓冲器。不过如果你担心扇出负载问题实验级别完全不用管。FullAdder的子电路搭好后回到主电路CLA_4bit。这里有两种做法做法A放四个FullAdder实例每个实例的A、B分别接输入S作为输出然后把每个FullAdder的G、P信号引出来。但这样做有个问题FullAdder内部并没有把G和P单独引出你还需要修改子电路额外增加两个输出引脚G_out和P_out。做法B我更推荐的做法不进FullAdder的子电路而是在主电路里对每一位直接用门搭。每一位的电路包含一个AND门输入A_i和B_i输出G_i一个XOR门输入A_i和B_i输出P_i另一个XOR门输入P_i和C_i输出S_i为什么推荐做法B因为这样G_i和P_i这两个信号节点是直接暴露在主电路图上的你可以直接从这些节点拉线到进位链不需要在子电路里拆端口。对于4位来说位数的逻辑重复度不高直接在主电路搭反而直观。如果你非要用子电路封装那就给FullAdder额外增加两个输出引脚G和P内部把G A AND BP A XOR B引出来。这个方案在扩展到16位时会体现优势但第一次学习时不建议。3.3 把四位进位方程落成电路这是整个搭建过程的核心也是最容易连线连到大脑断电的部分。我建议的做法是先画一张纸上草图把C1到C4的表达式列好然后对照表达式逐个搭。C1 G0 P0·C0这个表达式需要一个AND门P0和C0做与然后和一个OR门G0与AND门输出做或组合。输入是P0、G0、C0输出是C1。C2 G1 P1·G0 P1·P0·C0这里有三个乘积项其中P1·P0·C0是三输入的与G1是单变量项P1·G0是二输入的与。严格来说用一个3输入的AND门算P1·P0·C0一个2输入的AND门算P1·G0然后三个输入G1、P1·G0、AND门输出进一个3输入的OR门。Logisim的AND门和OR门都可以在属性里修改输入数量Number of Inputs从2改成3甚至更宽。C3 G2 P2·G1 P2·P1·G0 P2·P1·P0·C0四个乘积项G2是单变量P2·G1是2输入P2·P1·G0是3输入P2·P1·P0·C0是4输入。我的建议是中间项尽量复用前面已经算好的部分积。比如P2·P1·G0这个项可以先用P1和G0做AND得到临时信号T1再用T1和P2做AND。这样能减少门的总数也让连线更清晰。不过Logisim里门数量少到一定程度后差别不大你可以先按表达式原样翻译来搭搭通之后再考虑优化。C4 G3 P3·G2 P3·P2·G1 P3·P2·P1·G0 P3·P2·P1·P0·C0C4是最复杂的最后一项是5输入的与。建议搭C4时从后面往前推先算P3·P2·P1·P0用一个AND门再和C0做AND得到一个5输入的与项。其他项分别用对应位数的AND门最终全部进一个5输入的OR门。搭进位链的时候有一个非常实用的技巧用隧道Tunnel来传递共享信号。比如P0、P1、P2、P3这四个信号会被多个表达式用到如果每个用到的地方都从P0的源头拉一根长线过去主电路图会变成一团乱麻。把P0到P3、G0到G3分别用Tunnel标记在需要的地方再放一个同名TunnelLogisim会自动认为它们连接在一起图上连线可以大幅简化。在Logisim的工具栏里Tunnel的图标是一个类似隧道入口的形状位于基础库里的第二个。放置后双击可以改标签名。注意同名Tunnel才会连通不同名是各自独立的。我用的时候习惯加上前缀比如P_0、P_1、G_0这种避免和后来的信号重名。3.4 加法结果的生成Si的连接方式进位链搭完以后最后一步是把本位和S_i算出来。前面说过S_i P_i XOR C_i。这里的P_i就是A_i XOR B_i这个信号C_i就是进位链里算出来的那一位进位。但C0比较特殊——C0是外部输入不是进位链生成的所以在S0那里直接把外部输入C0接进去即可。每个S_i用一个XOR门S0 P0 XOR C0S1 P1 XOR C1S2 P2 XOR C2S3 P3 XOR C3把每个XOR门的输出接到输出引脚S0、S1、S2、S3。到这里整个4位CLA的计算部分就完成了。注意一个细节C4就是溢出/进位输出信号可以直接引到输出引脚Cout。如果你只做4位加法Cout表示无符号溢出的进位如果是补码加法Cout和最高位进位做异或才是有符号溢出标志这个等你做到ALU部分再考虑。4. 完整连线与电路图对照4.1 引脚布局输入、输出、进位端口我习惯把主电路布局成左边输入、中间逻辑、右边输出的流畅结构。具体来说左边放A0~A3、B0~B3共8个输入引脚以及C0进位输入引脚中间上方是G/P生成逻辑4个AND、4个XOR中间下方是进位链各级AND、OR门的组合右边放S0~S3四个输出引脚以及Cout进位输出引脚Logisim里引脚的方向参数Facing决定信号流向。输入引脚设为Facing East朝右放在最左侧输出引脚设为Facing West朝左放在最右侧。这样做的好处是所有信号从左向右流动跟手绘电路图的习惯一致排查时顺着信号流找问题非常快。还有一个容易被忽视的点引脚的位宽Bit Width默认是1输入引脚A0表示的是A的第0位是单bit信号不需要把位宽改成4。很多新手会把A整体作为一个4位输入引脚然后期望用Splitter去拆位这当然也可以但对于4位CLA教学演示我更推荐直接用4个单bit引脚少一层splitter转换图也更直观。4.2 连接G/P到进位链的走线方案搭建顺序建议是这样第一步先放好A0~A3、B0~B3的输入引脚。从每个A_i和B_i分别接AND门和XOR门AND门输出标记为G_iXOR门输出标记为P_i。建议在G_i和P_i的连线上立即加上Tunnel标签这样后面不需要从源头拉长线。第二步搭建进位链。对照C1到C4的表达式从简单到复杂依次搭。每搭好一个进位输出就把它用Tunnel标成C1、C2、C3这样可以减少大量跨区域的连线。第三步连S_i输出。每个XOR门接P_i和C_i输出接S_i引脚。这里的C_i取自Tunnel标签对应的信号不需要跨越大半个屏幕去拉线。第四步把C4接到Cout输出引脚。这套流程走下来主电路图上只有信号源区域和进位链区域之间有少量跨行长线其他都是局部的短连线视觉上非常干净。我在日志里把这个布局称为满天星布局——因为G/P信号像星星一样散布在各处通过Tunnel的名字互相识别而不是靠物理连线。4.3 完整电路图逐块解读如果你按上面的步骤搭完最终你会得到这样一张电路图分块解读如下A区——G/P生成块4组AND/XOR对每组输入A_i、B_i输出G_i、P_i。这一块没有任何进位输入纯粹是根据A、B本位值判断生成还是传播。B区——C1生成块1个AND门P0·C0、1个OR门G0 AND输出输出C1。C区——C2生成块1个3输入AND门P1·P0·C0、1个2输入AND门P1·G0、1个3输入OR门输出C2。D区——C3生成块1个4输入AND门P2·P1·P0·C0、1个3输入AND门P2·P1·G0、1个2输入AND门P2·G1、1个4输入OR门输出C3。E区——C4生成块1个5输入AND门P3·P2·P1·P0·C0、1个4输入AND门P3·P2·P1·G0、1个3输入AND门P3·P2·G1、1个2输入AND门P3·G2、1个5输入OR门输出C4。F区——求和块4个XOR门每个输入P_i、C_i输出S_i。其中C0直接用外部输入C1~C3用进位链信号C4只做进位输出不参与S计算。我见过不少人搭到D区、E区时就开始烦躁因为门和连线急剧增加。我的建议是每搭完一个区块就停下来仿真一次而不是全部搭完再测。比如搭完C1之后先手动改P0、G0、C0的值确认C1的输出符合真值表再继续搭C2。分块验证能让你在早期就发现方向错误、引脚接错这类低级问题。5. 仿真验证边界数值与随机值双重测试5.1 测试用例设计电路搭完了看起来像模像样但如果直接交作业大概率会被老师或者助教问倒你怎么证明它是正确的所以测试这一步一定要做扎实。先做边界用例测试这一类能快速暴露进位链的致命错误测试ABC0预期S预期C4全000000000000000全111111111011101单bit进位链00010001000100最低位生成00010001100110逐级传播01110001010000最高位溢出11110001000001随机组合110100101100001随机组合211000011011110测试方法很简单在Logisim左下角有输入引脚用鼠标点一下就会切换0/1值观察输出引脚的值是否和预期一致。以逐级传播测试为例A0111B0001。从低位开始A01、B01所以G01C1必然为1A11、B10P11所以C1被传递到C2A21、B20P21C2被传到C3A30、B30G30P30所以C40。最终S1000没有溢出。这个测试最能验证进位链的传递逻辑是否正确。再做逐位扫描测试固定B0001把A从0000递增到1111预期结果就是A1。这样16个用例能覆盖所有可能的低4位加1场景对检查C0到C4的完整传播路径非常有效。5.2 时序与毛刺问题初探仿真通过之后还有一个值得关注的点毛刺glitch。在组合逻辑电路中由于不同路径的门延迟不同输出可能会出现短暂的中间错误状态。比如C4的表达式里有5输入的与门和5输入的OR门不同输入组合下信号到达OR门的时间差会导致C4短暂跳动一下最终才稳定到正确值。在Logisim的仿真环境里默认的仿真模式是理想化的Step Simulation也就是忽略门延迟每个信号变化都是瞬间完成的所以你通常观察不到毛刺。如果你把仿真改为Timed Simulation模式Project - Simulation - Timed就能模拟出门延迟带来的毛刺现象。对教学实验来说毛刺不是错误而是组合逻辑的固有特性。你需要理解的是在真实硬件中加法器输出需要在时钟的建立时间之前稳定下来毛刺必须在那个时刻之前消失。这也是为什么关键路径延迟在CPU设计中如此重要的原因——它决定了时钟频率的上限。如果你的课程要求做时序分析可以在Timed模式下观察C4的信号波形看看不同输入组合下毛刺的形态和稳定时间。6. Logisim实操中的常见坑与我的解决方案6.1 高低位顺序搞反——最隐蔽的错误Logisim里画引脚的时候如果不注意Label很容易把A0和A3的位置搞反。比如你心里想着A[3:0]是A3、A2、A1、A0但实际连的时候把A0放在了最上面、A3放在了最下面最后算出来的数值就是完全错的。我的习惯是在放置引脚时A0到A3、B0到B3、S0到S3都按从上到下递增的顺序排列并且在Label里显式写成A_0、A_1、A_2、A_3而不是a、b、c这种缩写。这个小习惯帮我避免了很多次查半天查不出错的尴尬。6.2 连线交叉不等于连接Logisim里两条线交叉时如果没有出现交点的小圆点那它们就是不连通的。很多新手会把交叉当成连接结果信号莫名其妙不通或者更糟糕——某条线被意外短路。排查方法鼠标悬停在连线上Logisim会高亮显示该连线所连接的所有引脚和元件。如果一个信号应该连通多个门但高亮只显示了部分说明中间有断线点。另外Logisim对连线有自动吸附Snap功能拖拽线头靠近已有连线时会出现提示点松开后才会真正连接。6.3 子电路的引线方向问题如果你决定用子电路封装FullAdder有一个非常容易翻车的点子电路内部引脚的Facing方向决定了它在主电路中作为元件时的端口位置。如果子电路里输入引脚Facing设的是West朝左而你在子电路里把它放在了右侧主电路里封装块的端口位置会很奇怪连起来十分别扭。我的建议是子电路内部输入引脚统一放在左边且Facing设为East朝右输出引脚统一放在右边且Facing设为West朝左。这样封装到主电路后信号流依然保持从左到右。6.4 排查问题的系统化思路如果最终仿真结果不对不要随机猜。我总结了一个系统化的排查顺序第一单独验证每一个全加器/每一位的G和P信号。把B固定为0A设为某个值观察P是不是等于A因为P A XOR 0 AG是不是等于0。这能快速确认G/P生成块没问题。第二验证进位链。把A固定为0000、B固定为0000此时所有G和P都为0C1到C4应该全部是0。然后把A设为1111、B设为0000G0到G3全部为1C1到C4也应该全部是1。第三验证求和块。确认P_i和C_i的连线都正确后S_i应该等于P_i XOR C_i。如果S输出不对优先检查S_i对应的XOR门输入端是否接对了P_i和C_i。这三步走下来90%的问题都能定位到具体区块而不是整个电路糊成一团没法查。6.5 搭完之后的扩展方向4位CLA搭通之后我强烈建议你做一个扩展练习把它封装成一个子电路然后搭建16位加法器——用4个4位CLA作为低层模块再做一级组间先行进位。你会发现这其实就是把4位CLA的设计思路重复了一次只是位变成了组。具体来说每个4位CLA可以向外提供三个信号G_grp组生成、P_grp组传播、Cout组进位输出。其中G_grp和P_grp并不需要在之前搭的电路里显式引出但如果你回到电路图里看完全可以算出这两个值组生成就是G3 P3·G2 P3·P2·G1 P3·P2·P1·G0组传播就是P3·P2·P1·P0。这两个信号跟C4的差别在于它们不包含C0项。理解了这一点再去看多级CLA的设计图你会觉得非常自然。我在给学生上课的时候常说一句话先行进位加法器是用逻辑复杂度换时间的典型例子。它没有改变加法器的功能只是重新组织了计算顺序。你在Logisim里搭的一次又一次连线、改的一次又一次引脚方向最终都会内化成为对时序关键路径扇入扇出这些概念的直观感知。这些直觉是后面理解CPU流水线、乘法器阵列、甚至GPU并行计算的基础。先把这4位搭明白后面的路会顺很多。