一个逻辑学定理：任何复杂的逻辑关系式，都可以分解成为一个多项式

知识分子为了更好的知识生活 ID：The-Intellectual

●●●

一个人品不错的朋友发了九张美食照片，当然点赞数不胜数，也有不少朋友的点赞和评论。“大葱小米粥的煎饼卷让人垂涎欲滴”、“蘑菇炖鸡是我的最爱”、“红油麻椒太地道了，除了螺蛳狮面，我总是一勺”等。等等。 小小的手机屏幕顿时似乎闻到了很多。

这些夸奖，在我这个厨艺渣渣的电子老师眼里，除了默默吞咽口水，还可以当数字逻辑的好教材，可以用来说明一个逻辑定理：任何复杂的逻辑关系都可以分解变成多项式。如何分解，我们稍后再讲（见下文第二部分）。逻辑关系表达式的这一特性是人们设计“通用”数字逻辑器件的基础。对于《知识分子》的读者来说，在科研工作中设计和制作实验设备是一项非常实用的基本技能。

提到“万能”，大部分读者的第一反应大概是认为我们在卖“药丸”。我们使用逻辑器件来生成数字逻辑，而我们需要的数字逻辑关系是千变万化的。逻辑器件如何满足不同用户不断变化的需求？这实际上是近几十年来电子工程和计算机技术面临的一个无法回避的问题。

在本文中，我们首先回顾过去 20 到 30 年半导体电子器件的发展，以了解造成此问题的原因。然后讨论了解决这个问题的一些想法和解决方案。在众多的解决方案中，现场可编程门阵列（FPGA）相对成熟，实现门槛也相对较低，因此得到了广泛的应用。其实很多研究人员迟早会在自己的科学实验中用到FPGA，希望通过这篇文章做一个简单的介绍。

为什么要全能？

集成电路的技术在不断的进步，我们可以在一个芯片上集成的晶体管数量越来越多。但这也给设计师带来了麻烦。这么多晶体管使它们做什么？

在集成电路发展初期，人们将晶体管组合成一些常见的逻辑单元，如与门、或门、寄存器等。在每个集成电路芯片中，都放置了几个这样的功能模块。模块的输入和输出端通过引脚连接到集成电路外部，用户通过印刷电路板将这些端口连接起来，形成所需的逻辑电路。如图1所示。

►图1：早期带有集成电路的逻辑板

随着集成电路制造工艺和技术的进一步发展，人们可以将门电路、寄存器等更多功能模块放入同一个芯片中，但是这些模块应该如何连接呢？如果按照张三（用户A）的需求连接，这个IC很难卖给李四（用户B）。即使找到了用户 A 和 B 都能接受的解决方案可编程逻辑器有哪些，也很难让王二麻子（用户 C）满意。) 需求。随着集成电路集成度的逐渐提高，这一矛盾越来越突出。

你可能会说这并不简单，每个用户都可以根据自己的需要设计自己的集成电路。这确实是一个解决方案。这种由用户根据自己的需要设计的集成电路称为ASIC（Application Specific Integrated Circuit）。在工业界，我们看到很多厂商为自己的产品设计专用集成电路，实现智能控制、通讯、计算等各种功能，甚至用在儿童玩具中。

对于集成电路之类的东西，量产时每个集成电路芯片的成本都不会太高。但制作光刻掩模、调整设备、设置工艺参数的一次性成本非常高。因此，只有在大批量生产的情况下，一次性成本才能摊销，经济上可行。

在科研领域，大多数情况下，上千套的各种实验装置是不会被复制的，因此专用集成电路往往是不可用的。只有在核物理和高能物理中，由于探测器需要很多通道，才有可能用专用集成电路实现对探测单元信号的放大、处理和数字化等功能。

除了科研领域，即使在工业界，对小批量逻辑电路的需求也很大。这种需求导致了“通用”或通用可编程逻辑器件的出现。

如何实现全能？

回到朋友圈的九张美图，我们可以详细分析一下这些好评。“大葱小米粥的煎饼卷让人垂涎欲滴”、“蘑菇炖鸡是我的最爱”、“红油麻椒太地道了，除了螺蛳狮面，我总是一勺”等。等等。

这些赞美中的每一个都可以看作是逻辑关系的复杂多项式中的一个术语。该多项式中的每一项都是通过“与”运算连接的输入变量。并且所有这些项都通过“或”（或）运算连接成多项式。此外，多项式中的某些输入变量在参与其他运算之前可能会进行“非”运算。AND 运算相当于代数多项式中的乘法，OR 运算相当于加法，NOT 运算相当于减号。

比如之前朋友圈的评论可以写成如下逻辑多项式：

美味=（煎饼、大葱和小米粥）

或（蘑菇和小鸡）

或（红油辣椒和（不是（罗狮和面条）））

上述关系中的第三项其实可以进一步分解。为了简化问题，我们忽略了烹调方法，将含有螺蛳和面条两种食材的食物称为螺蛳粉。也就是说，螺蛳粉是螺蛳粉和螺蛳粉两组食物的交集。. 那么什么食物不是螺蛳粉呢？不是螺蛳粉的食物属于没有螺蛳粉的食物集合或没有面条的食物集合。所以：

(not(Lion 和面条))=(not(Lion)) 或 (not(Noodle))

你可能听说过德摩根定理。德摩根定理是一对关系表达式，上面的关系表达式就是其中之一。除了这种“不改变或”关系之外，还有一种“不改变和”关系。感兴趣的读者可以在线搜索“德摩根定律”了解更多信息。

利用德摩根定理，之前朋友圈的评论终于可以展开为：

美味=（煎饼、大葱和小米粥）

或（蘑菇和小鸡）

或（红油辣椒和（不是（罗狮）））

或（红油辣椒和（不是（面条）））

复杂的逻辑关系可以分解为多项式。这一数学结论为我们设计通用逻辑电路器件指明了方向。

FPGA的前身：PAL和GAL

人们开发的第一个通用逻辑器件：可编程阵列逻辑（PAL）是基于前面讨论的逻辑多项式特性设计的。图2是PAL的示意图。

► 图 2：可编程阵列逻辑 (PAL) 原理图

一个 PAL 设备可以接受多个逻辑电平输入，每个输入驱动两条垂直信号线。一路保持原来的逻辑电平，输入高时输出也高，输入低时输出也低。第二信号通过反相器将逻辑电平反相。当输入为高时，输出变为低。当输入为低时，输出为高。也就是说，输入信号发生了变化。“不”操作。

这样，N个输入信号驱动一共2N条垂直信号线，根据用户需要选择性地连接到水平逻辑线。（这里所说的连接实际上是通过二极管或三极管连接的。为简洁起见，我们没有画出相应电路的细节。）

每条水平逻辑线实现一个“与”门功能，即与其相连的所有信号必须同时为逻辑“1”，其输出为“1”。这样，每个水平逻辑行就成为逻辑关系中的一个项目。几条（通常是 8 条）水平逻辑线的输出被送到一个“或”门，这样这个“或”门的输出就变成了一个逻辑多项式的结果。

PAL 设备出厂时，所有的垂直线和水平线的交点都连接在一起。用户根据自己的需要切断不必要的连接点，只保留需要的连接点。这个过程就是编程。这样，PAL就成为了一个“通用”的逻辑器件，可以满足不同用户的需求。

在最早的 PAL 器件中，有些产品使用低熔点金属作为连接点。当用户编程时，不必要的连接点被炸毁。这样的编程过程称为将程序“烧录”到设备中，至今仍在使用。这样的设备显然不能多次编程，只能一次性交易。这类似于早期可编程只读存储器 (PROM) 的情况。

很快，可擦写只读存储器（EPROM）和电可擦写只读存储器（EEPROM）技术扩展到了PAL领域，导致出现了可多次重新编程的逻辑阵列器件。此类设备使用另一个名称：通用阵列逻辑 GAL。

当用户使用 PAL 或 GAL 时，首先将所需的逻辑关系用一种特殊的语言写成文本文件，然后用专门的计算机软件将逻辑关系简化扩展成多项式，并根据设备的结构，确定保留在设备中。连接点。然后，我们将编译好的结果“烧”到设备中，设备就具备了我们需要的功能，可以焊接到电路板上了。

这种可编程阵列逻辑器件已经存在了30多年，一般来说，历史悠久的电子技术早就应该过时了。不过，我最近搜索了一些电子产品供应商的网站，发现虽然由于注册商标的限制，人们不再使用 PAL 和 GAL 的名称，但仍有制造商在销售类似的可编程器件。在实际工作中，使用这种可编程逻辑器件在电路板上实现一些简单的逻辑电路是非常方便的。

FPGA构建

上述可编程阵列逻辑器件只能在一定限度内实现通用逻辑应用。有时，例如，当逻辑关系多项式的项数超过8时，现有设备无法适应。这就需要我们寻找更通用的逻辑实现方法。

此外，现代 PAL 或 GAL 设备理论上可以擦除和重新编程，但实际上一旦焊接到电路板上，要对其进行修改，就必须对其进行熨烫、重新编程和重新焊接到电路板上，这非常麻烦。（然而，作者确实看到其他同事不幸这样做了。）因此，使用 PAL 或 GAL 之类的设备几乎是轻而易举的事。当器件中的晶体管数量进一步增加时，没有人可以一次正确地设计出复杂的逻辑功能，这就需要给用户提供后悔药，使器件在焊接后仍可以随时重新编程和设置。电路板。也就是说，是现场可编程的。于是人们设计了一种现场可编程门阵列（field-programmable gate array，FPGA）器件。

这种更通用的逻辑实现方式是基于查找表（LUT），几乎所有主流的FPGA产品都使用查找表来实现逻辑功能。大多数 FPGA 产品中使用的查找表包括 4 或 6 条输入线和 1 条输出线。

在实际器件中，每个查找表后面都有一个寄存器（DFF）组成一个逻辑单元，如图3所示。

► 图 3：FPGA 的逻辑单元

该寄存器的作用是暂存查找表输出的逻辑电平，然后传送到下一级的逻辑单元。这样，我们就可以在FPGA中形成多层次的逻辑处理流水线，通过一定的时序来实现更复杂的逻辑或计算功能。

所谓查找表，本质上就是一块小内存。对于4个输入（或6个输入）的查找表，其中有16个（或64个）存储单元，每个存储单元包含一位。查找表的输入线是存储器的地址线。根据这些输入线的不同逻辑组合，存储器指向相应的存储单元，读出那里预先存在的位信息，并驱动输出端产生所需的逻辑功能。

查找表真的是一切吗？真的可以生成任何逻辑函数吗？对于查找表的每个输入，它可能只有两个逻辑电平，低（0） 或高（1））。因此，对于 4 个输入的查找表，最多可能只有 16 个输入逻辑组合。对于每一个逻辑组合，逻辑单元的输出值无非是0或1。因此，无论我们需要生成多么复杂的逻辑关系，只要提前16个存储单元就可以了足以存储对应的 0 或 1 数据。

我们通过下表中列出的几个示例来说明此方法。顺便说一下，这种形式的表称为逻辑真值表。

表中，ABCD为4条输入线对应的逻辑组合，共16条。AND4 是一个 4 输入“与”门逻辑。当 4 条输入线必须全部为 1 时，输出为 1，否则为 0。而 OR4 为 4 输入“或”门逻辑。当 4 条输入线中任意一条为 1 时，输出为 1，只有 4 条输入线全部为 0 时，输出为 0。

第三列的M3V1是一个比较复杂的逻辑关系，可以称为多数和否决逻辑。BCD的三个输入线中，多于两个输入必须为1，输入线A不能为0，或者BCD必须全为1，整个逻辑关系的输出为1。这个很像一家公司的董事会对决议进行投票。要通过决议，普通董事会成员（BCD）必须以简单多数投票，但主席（A）拥有否决权。但是，如果普通董事会成员一致通过，董事长的否决权是没有用的。如果你仔细分析之前的真值表，你可以清楚地看到这个逻辑。

读者可能会疑惑，这样的查询表能生成多少种不同的逻辑关系呢？我们可以看到这个查找表中有16个存储单元，每个单元存储一位数据，可以取0或1这两个值。因此，16个存储单元中存储的数据可以有2^ 16 = 65536 种不同的组合，每一种组合本质上都是一种逻辑关系的表达。当然，我们这里假设四根输入线不能相互交换。如果考虑逻辑关系中的交换律，不同逻辑关系的总数并没有那么多。这个总数的计算有点复杂，但至少我们知道这样的查找表足以表达任何四输入（或三、二输入）的逻辑关系。

很多FPGA器件都是基于RAM（随机存取存储器）的，一旦断电，内容就全部丢失。因此，每次上电时，必须将存储在计算机或电路板上其他设备中的数据重新加载到 FPGA 中，并将用户需要的逻辑写入查找表，使 FPGA可根据用户要求工作。从这个角度来看，FPGA不仅可以实现现场可编程，而且必须是现场可编程才能正常使用。FPGA 所需的设置信息通常通过设备上的几个专用引脚以串行数据编码的方式送入。

FPGA与微处理器的异同

有读者可能会问，为什么投票这么复杂？一张一张地清点票还不够吗？

这是一个很好的问题，它揭示了微处理器技术和可编程逻辑器件技术两大领域思维方式的差异。

逐个计数字段是微处理器的一种方法。它的特点是将一个复杂的功能拆解成很多步骤，每一步的处理都非常简单。这样，我们就可以利用可塑性较差的微处理器中相对简单的处理单元，通过复杂多步的程序来实现复杂的功能。我们使用的计算机和智能电子产品都是按照这样的技术路线设计的。

对于可编程逻辑器件，我们尝试将复杂的功能扁平化。对于更复杂的功能，我们通常将它们排列成几个阶段的流水线。

这样做虽然麻烦，但可以方便地并行实现多个数据计算或逻辑处理功能，因此处理速度可以比同等微处理器更快。例如，在前面讨论的投票问题中，使用微处理器至少需要 4 个时钟周期，但使用 FPGA 只需 1 个时钟周期即可得出结果。当然，微处理器的时钟周期很短可编程逻辑器有哪些，通常只有几纳秒。但是在某些应用中，我们真的等不及这几个时钟周期了。比如加速器这样的大型科研设备，一旦某些子系统出现故障，会立即进入停机保护状态，这就需要相应的保护系统判断越快越好。

事实上，我们在这里谈论的“编程”PAL 或 FPGA 是一个历史形成的模糊术语。我们加载到FPGA中的固件并不是一个“程序”，而是对FPGA中各个逻辑单元的功能以及它们之间连接的电路的描述。这种描述通常可以用一种特殊的语言来写，而且每个部分的顺序往往可以任意排列。毕竟，对于一个电路来说，先描述哪一块和后描述哪一块并没有本质的区别。相反。我们为微处理器编写的是一个真正的程序。程序中的每一行对应于微处理器执行的每个处理步骤。通常，这些步骤的顺序不能随意颠倒。

FPGA的实际应用

在科学实验中，FPGA 可以适应许多不同的应用需求。当然，它的应用也有些门槛，但这个门槛是相当低的。一个用户在电脑上下载并安装了一个编译器软件，然后花大约200美元买了一块验证板，如图4所示，可以做很多事情。

►图 4：入门级 FPGA 器件验证板

笔者带了很多高中生，他们经常会花几天到一周的时间来学习初步的编程技巧，让FPGA控制发光二极管发出各种闪光，控制音箱唱歌。下面的视频显示了在验证板上加载此固件的操作。

点击链接观看视频：

期待这篇文章，可以帮助有需要的读者跨过应用的门槛。