组合逻辑是一类数字逻辑,其规定的输出值仅取决于当前输入值,而不取决于所存储的先前输入历史。组合电路通过相互连接的逻辑门实现一个或多个布尔函数。常见实例包括加法器、选择器、码制转换器、比较器,以及用于计算处理器下一步操作的逻辑。这里的“当前”描述的是信号稳定后的逻辑关系:物理电路响应输入变化总是需要一定的时间。
组合逻辑与时序逻辑之间的区别是数字设计的基础。时序电路包含状态,通常由寄存器或其他存储元件保存;组合电路则根据输入计算输出,其规定的行为不包含状态保持。数字系统通常将两者交替连接:寄存器保存信息,组合逻辑网络对信息进行变换,再由寄存器锁存结果。
组合逻辑将计算的数学描述与电子硬件中的物理实现联系起来。其研究内容涵盖布尔表示、电路构建、算术结构、优化、时序、实现技术以及验证。同一个逻辑函数可以有多种电路实现方式,而这些实现方式在面积、速度、能耗和可靠性上可能存在显著差异。
逻辑基础与历史发展
一个具有 个二进制输入和 个二进制输出的组合逻辑模块实现了一个函数
每个输出都是输入的布尔函数。例如,三输入多数函数在至少两个输入为 1 时输出 1。它的值仅由输入组合决定:再次施加相同的输入组合,无论此前发生过什么,稳定后的输出都相同。在这一抽象层次上,一个比特恰好只有两种可能的值,尽管物理器件是用电压、电荷或其他可测量物理量的取值范围来表示这两种值的。
其数学基础是布尔代数,由乔治·布尔在 1847 年和 1854 年出版的著作中提出。布尔运算描述二值变量之间的关系。与运算要求两个操作数都为真,或运算要求至少一个操作数为真,非运算则对值取反。这些运算提供了一种代数语言,后来得以应用于开关网络;不过,布尔最初的研究关注的是符号推理,而非电子计算机。
代数与工程之间的关键联系出现在克劳德·香农于 1937 年完成、1938 年发表的硕士论文《继电器与开关电路的符号分析》中。香农展示了如何利用布尔代数分析和综合由电控开关组成的网络。开关的串联和并联结构可以用代数运算来描述,从而可以在构建硬件之前,对逻辑规格进行运算和变换。随着继电器逐渐被真空管、分立晶体管和集成器件取代,这一原理始终适用。
“组合”一词将这类网络与行为取决于内部状态的电路区分开来。例如,触发器可以在用于设定其值的输入消失后,仍然保持两种值中的一种。组合逻辑网络的规格中则没有相应的状态变量。如果某个输出经过逻辑门反馈到自身的输入,所形成的电路可能会保留信息、产生振荡,或表现出依赖时序的行为;这种反馈通常不被视为普通的组合逻辑实现。
物理上的存储效应本身并不会使这一区分失效。每个电子电路节点都具有电容,因此其电压会暂时受到先前状态的影响。组合逻辑行为意味着,在有效工作条件下,经过一段有界的稳定时间后,输出就由所施加的输入唯一确定。因此,这一区分所针对的是设计上对历史状态的逻辑依赖与不可避免的瞬态物理效应之间的差别。
组合逻辑也不应与组合子逻辑混淆。后者是数理逻辑学中的一种形式系统,涉及不含变量的表达式和函数应用。这两个领域都关注组合,但其术语指向数学与计算领域中不同的研究方向。
布尔表达式与表示方法
真值表通过列出所有可能输入组合所对应的输出,来定义一个布尔函数。具有 个输入的电路,其完整真值表有 行,与输出的数量无关。3 个输入需要 8 行,而 32 个输入则需要超过 40 亿行。因此,真值表对于小型功能模块而言既精确又实用,但不适合作为大型数据通路的主要表示方式。
当函数具有可利用的结构时,布尔表达式能提供更紧凑的描述。用并置表示与运算、 表示或运算、上横线表示非运算,则多数函数为
这个表达式采用积之和形式:每个乘积都是一个与项,各乘积之间通过或运算组合。和之积表达式则相反,它将多个或项通过与运算组合起来。这些名称是约定俗成的;布尔加法并非普通的整数加法,因为在或运算下,。
对于真值表中输出为 1 的每一行,分别写出一个最小项,再将这些最小项相或,就能把任意布尔函数写成标准积之和形式。每个最小项都包含全部输入变量,各变量是否取反由对应行的取值决定。标准和之积形式则使用与输出为 0 的各行对应的最大项。这些标准表达式表明,任意有限布尔函数都可以由基本运算构造出来,但它们通常不会得到实际规模最小的电路。
借助布尔恒等式,不同的表达式可以描述同一个函数。德摩根定律指出:
这些定律尤为重要,因为与非门和或非门各自都具有功能完备性:仅使用其中任意一种门,就能实现所有布尔函数。异或是另一种实用的运算,记作 。当两个操作数不同时,其结果为 1,因此特别适合用于奇偶校验和算术运算。
还可以选定一个变量,利用香农展开式分解函数:
其中两个通过固定变量取值得到的函数称为余因子。这个恒等式直接描述了一个二选一选择器,并为决策图及多种综合技术奠定了基础。通过反复分解,可以将一个大型函数转换为由较小决策构成的网络。
表示方式会影响分析的难度。紧凑的公式可能掩盖可共享的子表达式,而门级图则会明确呈现这种共享关系。对于固定的变量顺序,约简有序二叉决策图提供了一种规范表示;只要图的规模保持较小,就能高效地进行等价性检查。不过,它的规模仍可能呈指数增长,而且改变变量顺序也可能使结果发生巨大变化。没有哪一种表示方式能对所有布尔函数都保持紧凑。
选择、译码与码制转换
许多反复使用的组合逻辑结构并不执行算术运算,而是负责组织数据的传送与解读。多路复用器从多个数据输入中选择一路,将其传送至输出端。一个二选一的单比特多路复用器实现如下函数:
其中, 为选择输入。一个 选一的多路复用器通常使用 个二进制选择信号。对于位宽更大的数据字,可以将相同的单比特结构并联,并由同一组选择信号控制。
多路复用器广泛用于处理器和通信硬件。它们用于选择操作数,将不同来源的结果送入共享通路,以及在正常值与异常值之间进行选择。大型选择网络可以由较小的多路复用器组成树形结构。与长链结构相比,平衡树可以减少串行经过的选择级数,不过布线距离、选择信号的分配方式以及可用的实现单元也会影响延迟。
译码器执行与之互补的数据组织任务:将二进制码转换为某一条输出线的有效信号。一个 线— 线译码器为每一种可能的输入码设置一条输出线。在输出高电平有效且使能信号有效的情况下,每个有效的二进制输入都恰好使一条输出线为高电平。例如,2 线—4 线译码器产生四个最小项:、、 和 。低电平有效的译码器则采用相反的输出极性。
译码用于识别指令类别、选择寄存器和识别地址范围。解复用器将一路数据输入送至选定的输出端;它可以看作由数据信号驱动使能端的译码器。反过来,编码器将处于有效状态的输入线转换为二进制码。基本编码器要求输入满足特定条件,通常是恰好只有一条输入线有效。优先编码器则为输入赋予优先次序,因此即使多个输入同时有效,也能确定输出。
码制转换器实现不同表示形式之间的映射,例如二进制码到格雷码的转换,以及用于七段显示器的二进制编码十进制码转换。对于二进制字 ,对应的反射格雷码为
其中, 表示逻辑右移一位。反射格雷码序列中相邻的码字只有一位不同。这一性质在某些接口中很有用,但转换器本身仍然只是一个组合逻辑函数;在彼此独立的时钟域之间安全传输数据,还取决于外围时序电路的设计。
这些模块说明,规格说明必须涵盖异常情况和未使用的情况。编码器必须明确没有请求时的行为。显示码转换器必须为非十进制输入码定义输出,或者确保这些输入码不可能出现。输出有效标志通常承载着仅凭编码结果本身无法明确表达的信息。
算术与比较电路
二进制加法器是组合逻辑计算的一个典型例子。半加器接收两个比特,输出和位与进位:
全加器还接收一个进位输入:
和位输出表示整数相加结果的低位,进位则表示高位。将全加器依次连接,就构成了行波进位加法器,其中每一级的进位输出都接入下一级。
行波进位结构规整、硬件开销小,但进位可能需要传播整个字长。速度更快的架构会并行计算多个位置的进位信息。将进位生成信号和进位传播信号定义为
则有
超前进位加法器和并行前缀加法器以分层方式组合这些关系。Kogge–Stone 网络和 Brent–Kung 网络均于 1973 年提出,是著名的并行前缀结构,在逻辑深度、布线、扇出和节点数量之间各有不同的权衡。它们的逻辑深度为对数级,但这并不意味着实际电路延迟只取决于逻辑门的级数。
减法通常复用加法电路。在二进制补码运算中,对于 -bit result 的模 运算,有
。加减法器可以根据控制条件对第二个操作数逐位取反,并利用初始进位输入实现加 1。无符号进位和有符号整数溢出所指示的情况不同。对于有符号加法,如果两个同号操作数相加得到异号结果,就发生了溢出;仅凭最高位的进位输出,不能判断是否发生有符号溢出。
乘法先生成具有相应位权的部分积,再将其归约为最终的和。在重编码或其他优化之前,无符号 -by- 乘法包含 个基本的位乘积。Wallace 于 1964 年提出的方法和 Dadda 于 1965 年提出的方法,使用进位保留结构来组织部分积归约,将长距离进位传播推迟到最后的加法阶段。乘法可以完全由组合逻辑实现,但实际处理器往往会插入流水线寄存器,或在多个周期内复用算术硬件。
比较器用于判断相等关系或大小关系。判断相等可以通过对对应位进行同或运算,再将各位结果相与来实现。大小比较取决于最高的不同位;对于有符号表示,还需要进行额外处理。桶形移位器使用分级选择网络来实现可变位数的移位,对于一个 -bit word,通常需要 级多路选择器。
算术单元将这些功能与选择逻辑和状态逻辑结合起来。遵循 IEEE 754浮点运算标准的浮点运算还需进行指数比较、对阶、规格化、舍入和特殊值处理。每一步变换都可以由组合逻辑实现,但由于各级之间由寄存器隔开,整个单元可以是时序电路。
逻辑最小化与综合
逻辑综合的任务是将行为描述或布尔函数描述转换为可实现的电路。其中一项核心操作是化简:消除不必要的区分,并找出高效的共享结构。例如:
化简后的函数不再依赖于 。更复杂的例子则涉及不同的分组方式、取反信号,以及多个输出共用的项。优化必须保持所要求的行为,而不只是缩短表达式。
莫里斯·卡诺于 1953 年提出的卡诺图为变量较少的函数提供了一种可视化方法。图中真值表各项的排列方式使得相邻单元格仅有一个输入位不同。将单元格按二的幂次个数分组后,每组便对应一个可消去变化变量的项。卡诺图的边界首尾相接,因此位于相对两侧的单元格也可能相邻。卡诺图适用于教学和小规模设计,但随着变量数量增加,就会变得难以处理。
奎因–麦克拉斯基法为两级逻辑最小化提供了一种系统的表格方法。它先找出质蕴含项,再从中选择一组项,覆盖所有要求输出为真的情况。由于蕴含项和候选覆盖方案的数量可能迅速增长,精确方法的计算代价可能很高。启发式最小化方法,包括 20 世纪 80 年代开发的 Espresso 系列,力求在不穷举搜索全局最优覆盖方案的情况下获得良好结果。
如果系统规范确实允许某些未使用的输入组合对应任意输出,就可以将这些组合表示为无关条件。例如,二进制编码的十进制(BCD)输入仅使用四位二进制数的十六种可能码型中的十种。将其余码型视为无关条件,可以简化十进制显示译码器。但只有在外部环境排除了这些码型,或明确允许它们产生任意行为时,这种优化才是合理的。如果规定了无效输入应得到何种响应,就不能同时又将这一响应视为无关紧要而舍弃。
现代综合通常优化的是多级逻辑网络,而不只是与或表达式。提取公因子可以减少重复: 可以变为 。让多个输出共享中间项可能减少面积,但也可能增加负载,使关键路径变慢。有时,复制逻辑反而能通过分散负载改善时序。因此,最简的符号表达式未必对应最佳的物理电路。
工艺映射将优化后的网络转换为目标单元库所支持的单元。单元库可以包含具有多种驱动能力的与非、或非、异或、多路选择以及复合与或非单元。具体采用哪种实现,取决于输入到达时间、输出负载、面积限制和时序约束。随着物理估算越来越准确,电子设计自动化工具会反复调整结构和单元选择,因此综合是一个工程优化过程,而非一次性的代数化简。
传播延迟、冒险与时钟边界
组合逻辑在设计上不具有记忆功能,但其响应并非瞬时完成。门的传播延迟是在规定的电压阈值和负载条件下,输入变化引起相应输出变化所需的时间。上升沿和下降沿的延迟可能不同。逻辑网络的最大稳定时间取决于其中最长的相关路径,而最小延迟则描述变化最早可能传播到输出的时间。当逻辑网络连接存储元件时,这两者都很重要。
静态时序分析无需枚举所有输入序列,即可估算整个电路的时序。它利用经过表征的单元延迟和互连模型,在图中逐级传播到达时间的上下界。门数较多的路径不一定比门数较少的路径更慢:较大的电容负载、较长的连线、缓慢的输入跳变以及较弱的输出驱动能力,都可能成为主导因素。伪路径是指在相关工作假设下无法被敏化的结构路径;功能性多周期路径则是指规范允许用超过一个时钟周期完成传输的路径。
在同步电路的寄存器到寄存器路径中,简化的建立时间约束为
其中各项分别表示发射寄存器从时钟到输出的延迟、最大组合逻辑延迟、接收寄存器的建立时间,以及为不确定性和不利时钟偏斜等影响预留的裕量。保持时间检查则考察数据是否会在接收寄存器的采样沿之后过早到达。电路即使满足建立时间要求,也仍可能违反保持时间要求。
路径延迟不一致可能引发逻辑冒险,即非预期的输出瞬态变化。考虑
当 时,无论 如何变化,逻辑输出都应保持为 1。如果一个乘积项先变为 0,另一个乘积项随后才变为 1,输出就可能短暂降至 0,产生静态 1 冒险。加入共识项后可得
稳态函数保持不变,但在相关的单输入变化假设下,新增项可以在切换过程中维持输出为 1。
动态冒险是指预期只发生一次输出跳变时,却发生了多次跳变。多个输入发生变化时,还可能经过某些中间输入组合,而这些组合的正确输出与变化前后的输出值均不同;这类功能冒险通常无法仅靠平衡延迟来消除。因此,冒险分析不仅取决于最终的真值表,还取决于对允许的输入变化所作的假设。
在同步数据通路中,只要结果在采样前稳定下来,中间出现的毛刺通常不会影响功能,但仍会消耗开关能量。在异步控制中,或在用作时钟、复位、使能的信号上,短暂脉冲却可能造成持久影响。亚稳态是一个相关但不同的问题:它发生在存储元件中,由违反采样要求引起;对前级组合逻辑网络的布尔描述无法对其建模。
物理实现技术与设计权衡
当代数字集成电路的主流实现技术是互补金属氧化物半导体(CMOS)技术。静态 CMOS 门采用由金属氧化物半导体场效应晶体管构成的互补上拉网络和下拉网络。在 CMOS 反相器中,低电平输入使上拉器件导通、下拉器件关断,从而产生高电平输出;高电平输入则使情况反转。更复杂的网络可以实现与非、或非以及复合逻辑函数。
静态 CMOS 的优势在于,理想情况下,电路处于稳定逻辑状态时,电源轨之间不存在持续导通的直流通路。实际电路仍会消耗漏电功率,而开关切换需要消耗能量来为电容充放电。动态功耗通常可估算为
其中, 为开关活动因子, 为有效开关电容, 为电源电压, 为工作频率。 的确切定义取决于开关活动的计量约定。毛刺会增加开关活动,却不一定对有效计算有所贡献。
仅凭门数量并不能全面衡量实现成本。更大的驱动器能更快地为负载充电,但占用面积也更大,而且会给前级带来更大的输入电容。扇出,即一个信号所驱动负载的数量和大小,可能使电路需要插入缓冲器或复制逻辑。互连线的电阻和电容可能成为延迟的主要来源,尤其是连接芯片上物理位置相距较远的部分时。因此,布局布线会影响布尔逻辑实现的优劣。
专用集成电路通常使用经过特性表征的标准单元库或定制晶体管结构来实现组合逻辑。现场可编程门阵列通常使用可配置查找表、布线资源和专用算术结构。一个 输入查找表可以通过在配置存储器中存储 个真值表值,实现这 个输入的任意单输出布尔函数。这些存储的配置定义了函数;在所建模的组合运算中,它们并不是随运算变化的用户数据状态。
因此,同一逻辑在不同平台上的高效实现形式可能有所不同。适合用复合 CMOS 门实现的表达式,映射到查找表上时可能效率不佳;而算术运算则可能受益于可编程器件的专用进位链。专用乘法器模块和存储器模块的存在,也进一步改变了哪些运算适合由通用逻辑综合实现。
其他电路形式包括传输晶体管网络、传输门多路选择器和动态逻辑。动态门依赖预充电阶段、求值阶段以及暂时存储的电荷,因此其电气工作过程比静态布尔逻辑门更复杂。不过,它们在功能上仍可能是在受控阶段内对组合逻辑表达式求值。因此,必须区分底层的逻辑抽象与实现该抽象所采用的晶体管级方法。
硬件描述与验证
组合电路通常使用 Verilog、SystemVerilog 或 VHDL 等硬件描述语言来描述。连续赋值用于表达信号之间的关系,组合逻辑过程块则描述如何根据输入计算输出。算术表达式、条件选择和 case 语句都可以描述组合硬件。不过,与软件执行不同,生成的硬件可能并行执行许多运算。
一个关键要求是:在每一条相关的控制路径上,每个输出都必须获得确定的值。如果过程描述只在某个条件为真时对输出赋值,那么在条件为假时,要保留先前的值就可能需要锁存器。因此,即使设计者原本打算构建组合电路,源代码也可能导致综合工具推断出存储元件。先进行默认赋值,再针对特定情况显式覆盖,是明确表达完整函数的一种常见方法。SystemVerilog 的 always_comb 结构还支持自动确定敏感信号,并提供额外的语言级检查。
表达式的位宽以及有无符号属性同样重要。如果操作数扩展不正确,或者结果被赋给位宽过窄的目标,那么即使加法在数学上正确,也可能产生不符合预期的硬件结果。拼接、移位、比较和有符号类型转换都有精确定义的语言语义。仅仅让仿真结果与非形式化计算一致还不够,除非该计算也采用相同的有限位宽规则。
仿真通过施加选定的输入模式并观察输出来进行测试,通常还会与参考模型进行比对。对于较小的输入空间,穷举仿真是可行的,但其规模按 增长。较大的模块则采用针对边界情况的定向测试、受约束的随机激励以及断言。算术测试通常重点考察零、最大幅值、进位传播、符号变化和边界移位,因为这些情况会检验实现中的不同部分。
形式验证可以证明两个组合逻辑实现在所有输入赋值下都等价。一种标准构造方法是:将两个实现中每对对应的输出进行异或,再将所有差异信号进行或运算,汇总成一个信号,从而构成一个 miter(等价性比较电路)。如果该信号永远不可能变为 1,两个电路就是等价的。布尔可满足性问题求解器可以搜索使 miter 输出为 1 的输入;这样的输入就是反例。如果不存在这样的输入,并且已证明问题不可满足,那么在所编码的假设条件下,两个实现的结果一致。
功能验证不能替代电气验证或时序验证。逻辑等价的网表仍可能无法满足规定的时钟周期要求、超出功耗限制,或存在有问题的瞬态行为。四态 HDL 仿真还带来了另一层区别:未知值和高阻态用于对不确定性及连接状态建模,并不是数学函数中额外的二进制状态。无关项规定、仿真中的未知值以及物理上不确定的电压,不可视为可以互换的概念。
系统架构与计算极限
大多数实际计算系统都将组合逻辑变换与时序存储结合起来。在有限状态机中,组合式次态逻辑将当前状态和输入映射为接下来要存储的状态。输出逻辑可以只取决于状态,如摩尔型描述;也可以取决于状态和当前输入,如米利型描述。即使次态网络和输出网络都是组合逻辑网络,状态寄存器的存在仍使整个状态机成为时序系统。
中央处理器中包含用于指令译码、操作数选择、算术运算、地址生成和控制决策的组合逻辑结构。寄存器及其他存储结构保存跨时钟周期所需的信息。流水线将一项较长的计算划分为多个阶段,各阶段之间由寄存器隔开。这样可以缩短相邻寄存器之间的组合逻辑延迟,从而提高吞吐率,但也会增加存储和时钟开销,而且通常会使输入到达与相应输出产生之间间隔更多的时钟周期。
同样的区别也能解释迭代式硬件。除法器可以在多个时钟周期内重复使用同一个减法与选择网络,并在每一步之后存储部分结果。另一种设计则可以将这些步骤展开为一个大型组合电路。两者可以实现同一种数学运算,但面积、延迟和吞吐率可能截然不同。对展开后的电路进行流水线化,又形成了第三种设计方案,这说明“运算”与“实现该运算的组合电路”并不是相同的架构概念。
在理论电路复杂度研究中,布尔电路通常被表示为由逻辑门构成的有向无环图。规模统计逻辑门的数量或其他指定资源的用量,深度则衡量相互依赖的逻辑门所构成的最长链。这些量有助于描述并行计算。扇入有界的平衡树可以在对数深度内完成满足结合律的归约运算,而串行链则需要线性深度。所选的门基和扇入限制至关重要:将任意多个输入的与运算视为一个逻辑门,与将每个与门限制为两个输入,得到的是不同的模型。
电路族为每一种输入长度提供一个电路。如果没有一致性要求,各个输入长度对应的电路就可以独立选取;而算法则为所有输入长度提供同一套可有效执行的过程。在将电路资源与通用计算模型上衡量的计算复杂性进行比较时,这一区别十分重要。
具有 个输入、一个输出的布尔函数共有 个。计数论证表明,其中大多数都需要非常大的电路,尽管许多在工程中有用的函数都具有紧凑而规整的实现方式。对于计算某些特定重要函数、且不受结构限制的电路,证明其复杂度的强下界仍是一项重大的理论挑战。在物理设计中,信号传播、布线拥塞、能量耗散以及器件行为的变异还会带来额外限制,而这些资源因素并不能仅由布尔门数量来反映。