电路 【教程】如何用最少的逻辑门做出单步组合逻辑

putianyi888

Lv4
创意家
LV
0
 
IP属地
英国
2018/12/23
69
64
  • · 发布于未知
记号
&:与运算符
~:或运算符
泰拉瑞亚里的异或门与异或逻辑不同。因为异或门不满足结合律,所以异或门记作函数 ^() 而不是运算符。
泰拉瑞亚中的异或逻辑可以通过将两根线接到同一个逻辑灯上实现,a 与 b 接到同一个逻辑灯上记为 ab。这种免费的异或逻辑大大增加了单个逻辑门的复杂度。
在未经特殊说明的情况下,组合逻辑的输入为a_1,...,a_n,输出为F。

真值表定义
一个n输入的真值表大小是(n+1)*2^n。有两种方法可以压缩其大小。其一是固定左边n列输入参数的顺序,只保留最后一列向量;其二是只保留使输出为1的输入参数。我们采取第二种记法,例如有三个输入的异或门 ^(a,b,c),当且仅当 (a,b,c)=(1,0,0),(0,1,0),(0,0,1) 这三种情况时异或门的输出是1,所以真值表记为
258
显然可以随意交换真值表的两行,不过这么做没什么意义。

单个逻辑门的真值表
泰拉瑞亚中只有两种不同的组合逻辑门:与门和异或门。

单个与门可以实现的逻辑表达式为 s_1&...&s_r,其中 s_i 是由 {~,a_1,...,a_n} 生成的串。这个与门上的逻辑灯数量比表达式中的“&”符号数量多1。
举例来说,对于三个输入a,b,c,a&b&c,a&~b&~c,a&b,ab&c 和 abc 都可以用单个与门实现:
upload_2019-2-9_22-27-15.png
upload_2019-2-9_22-27-52.png
upload_2019-2-9_22-28-10.png
upload_2019-2-9_22-28-39.png
upload_2019-2-9_22-28-59.png
这五个逻辑的真值表分别是
upload_2019-2-9_22-31-3.png
upload_2019-2-9_22-31-38.png
upload_2019-2-9_22-32-27.png
upload_2019-2-9_22-33-3.png
upload_2019-2-9_22-33-27.png


单个异或门可以实现的逻辑表达式为 ^(s_1,s_2,...,s_r),其中 s_i 如上所述。这里我们举两个例子:^(a,b,c) 和 ^(ab,b,c)
upload_2019-2-9_22-40-18.png
upload_2019-2-9_22-41-15.png


因为逻辑表达式的长度任意,每项的串也有很多可能,单个逻辑门就可以达到非常高的复杂度,甚至于我们平常遇到的大多数情况都可以用单个逻辑门解决。然而知道了这些,并不能帮助我们从一个真值表看出来这个真值表代表的逻辑表达式。例如,给定了一个逻辑表达式 ^(abc,bc,c),写出它的真值表是很容易的,但是如果给出它的真值表,如何知道它代表的是 ^(abc,bc,c) 呢?
 

putianyi888

Lv4
创意家
LV
0
 
IP属地
英国
2018/12/23
69
64
  • · 发布于未知
真值表变换
之前我们已经提到过一种没什么用的变换,即交换真值表的两行。真值表的两列同样也可以交换,不过交换的时候也要交换它们的表头。例如,对于 ab&c 的真值表,我们可以交换它的 b列 和 c列:
变换前:
upload_2019-2-9_22-51-21.png
变换后:
upload_2019-2-9_22-52-13.png


然后我们执行另一种变换:将真值表的一列加到另一列上。这个加法是模二加法:1+1=0+0=0,0+1=1+0=1。两列的表头也要相加,串相加时,直接把两个串连起来,然后删除新串中重复出现的字母,例如 abc+bcd=abcbcd=ad。在上面的例子中,我们接下来把 b列 加到 a列 上:
变换前:
upload_2019-2-9_22-52-13.png
变换后:
upload_2019-2-9_22-56-26.png


变换后的真值表与上一节中 a&b 的真值表相等:
upload_2019-2-9_22-32-27.png

所以我们得出结论,真值表对应的逻辑表达式是 ab&c。

在这个例子里我还有一种变换没有用到,那就是将某一列取反并把“~”加到该列的表头。
对于任何的真值表,我们利用三种变换方法:交换行列、将一列加到另一列、将一列取反。如果可以变换成我们已经熟悉的单个逻辑门的真值表,那么就成功了。最后再举一个例子,这个例子中我将跳过变换的过程,只给出变换的结果。

这是二进制转BCD码的加三移位逻辑,有四个输入abcd和四个输出ABCD,都是从高位到低位。这个逻辑需要做的转换是:
当 abcd 为 0000~0100 时,ABCD=abcd;当 abcd 为 0101~1001 时,ABCD=abcd+0011。如果写成单步逻辑,就变成了

abcdABCD
00000000
00010001
00100010
00110011
01000100
01011000
01101001
01111010
10001011
10011100

我们把A,B,C,D的真值表分离开,并分别变换:
upload_2019-2-9_23-8-55.png
upload_2019-2-9_23-9-38.png
upload_2019-2-9_23-10-13.png
upload_2019-2-9_23-11-26.png


B的真值表变换结果如下,所以 B=ab&~c&~ad
upload_2019-2-9_23-13-14.png


C的真值表变换结果如下,所以 C=^(a,b,cd,bd)
upload_2019-2-9_23-14-18.png


D的真值表变换结果如下,所以 D=^(a,b,bc,bcd)
upload_2019-2-9_23-15-29.png


A的情况有一点复杂。因为真值表变换不会改变真值表的行数,而真值表为五行的单个逻辑门至少是五输入的异或门。这种情况下我们可以增加一些“未定义行”。注意到这个逻辑仅处理 0000~1001 这十个输入,对于 1010~1111 这六个输入,无论怎么输出都可以,反正它们也不会发生。所以我们可以往真值表中增加六行未定义行,以x标记,表示这些行可有可无。
upload_2019-2-9_23-19-47.png


变换可以得到
upload_2019-2-10_13-4-45.png


取出前六行,前六行对应逻辑 A=^(bc,~ad,cd)
至此ABCD四个输出都已经确定,各用一个门,接线如下,红蓝黄绿分别代表abcd,四个逻辑门从左到右分别代表ABCD:
upload_2019-2-10_13-6-13.png


做出的8位二进制转BCD:
upload_2019-2-10_13-6-49.png
 

镜之花棱

Lv2
LV
0
 
IP属地
未知
2019/02/01
2
0
  • · 发布于未知
看不太懂喵,不過還是支持了
 

shota

Lv5
LV
0
 
IP属地
湖北省
2015/08/26
66
20
勋章
1
  • · 发布于未知
感谢贡献~BBSTR有你更精彩!
 

zrxis

Lv3
LV
0
 
IP属地
贵州省
2019/09/12
17
2
勋章
3
  • · 发布于未知
我怀疑就我在学代码
 

* 这是一则由 Google AdSense 自动推荐的广告,与本站无关,不对其真实性与可靠性负责

顶部