Turing Complete: 图灵完备，一款数电小游戏

Posted on Edited on In Word count in article: 2.1k Reading time ≈ 7 mins.

OVERTRUE

OVERTRUE是最简单的图灵完备的处理器，即能够读取指令、分情况进行计算或跳转或转移数据，接下来从基础逻辑门开始搭建该架构

基础逻辑电路

基础逻辑门

NAND与非门是最为基础的逻辑门，根据德·摩根定理，能够用它和若干个NOT非门搭建其它三个基础门

  • 它的真值表为$\begin{matrix}0&1&0&1\\0&0&1&1\\1&1&1&0\end{matrix}$，即非$\begin{matrix}1\\1\end{matrix}$得1，否则得0，画法为

  • 通过它可以制造NOT，真值表为$\begin{matrix}0&1\\1&0\end{matrix}$，画法为

  • 对NAND门的输出取反，得到AND与门，逻辑为$\begin{matrix}1\\1\end{matrix}$得1，否则得0，真值表为NAND输出按位取反，画法为

  • 对NAND门的输入取反，得到OR或门，逻辑为非$\begin{matrix}0\\0\end{matrix}$得1，否则得0，真值表为NAND输出左右颠倒，画法为

  • 对OR门的输出取反(或对AND的输入取反)，得到NOR或非门，逻辑为$\begin{matrix}0\\0\end{matrix}$得1，否则得0，真值表为OR输出按位取反，画法为

逻辑门扩展

各个基础逻辑门互相组合，能得到所有24 = 16种真值表，在这里扩展XOR异或门与XNOR同或门：

  • 对OR门与NAND门的输出AND，得到XOR，逻辑为输入不同得1，否则得0，真值表为$\begin{matrix}0&1&0&1\\0&0&1&1\\0&1&1&0\end{matrix}$，画法为1.6.XOR
  • 对XOR门的输出取反(或对NOR门与AND门的输出OR)，得到XNOR，逻辑为输入相同得1，否则得0，真值表为XOR输出按位取反，画法为

其它

通过OR与AND，可实现始终输出高/低电平的电路ON与OFF

通过两个相同类型的基础逻辑门组合，可得到三路输入的对应逻辑门

通过三个XOR门组合，可实现在四路输入奇数个信号时，输出1

算术运算

二进制信号计数与二进制补码

  • 通过三个XOR门组合，使得当四路输入奇数个信号时，接入代表1的二进制输出上
  • 枚举四路输入，使得当四路输入2或3个信号时，接入代表2的二进制输出上
  • 通过三个AND门组合，使得当四路输入全为1时，接入代表4的二进制输出上

总而言之，通过繁琐的排列组合，实现接受255路输入后，输出数值上最多表示255的单字节八位信号

为了方便，依然将这个信号用一点表示，使用分线器解散这个点，使用集线器构建这个点

二进制补码：将一个字节的最后一位视为 − 128后，即有按位取反加1后变为其相反数的特性

半加器与全加器与八位加法器

半加器指对两路1位输入求和，并用两路输出本位和与进位：

  • 一个XOR门得到正确的本位和输出，即在1 + 0 = 1或0 + 1 = 1时输出1
  • 一个AND门得到正确的进位输出，即在1 + 1 = 10时进位

全加器指对三路1位输入求和，并用两路输出本位和与进位：

  • 通过两个XOR门，当输入信号为奇数个时在本位和处输出1
  • 对两路输入通过半加器，当进位为1时，或本位和为1且第三路输入为1时，在全加器进位处输出1

八位加法器接受一个一位输入用于继承上一个八位加法器的进位；接受两个字节输入表示两个参数；输出一个一位信号表示三个数的进位；输出一个字节信号表示除进位外的和：

  • 通过八个全加器与一个集线器即可得到八位加法器
  • 附录中展现了高速八位加法器，能达到61逻辑门、20延迟

通过对第二个输入取相反数，实现减法

数据选择

根据一个1位信号输入来选择两路输入是很有价值的，所以需要开关：

  • 当开关关闭时，既不输出高电平也不输出低电平，处于高阻态
  • 两个开关即可实现数据选择，开关保证了在一路输出时不会受影响另一路影响
  • 除了选择输入外，也可以用开关来选择输出端

数据存储

一位存储器

通过延迟线，能够将该刻的信号延迟到下一刻输出，实现存储器功能：

  • 接受一个代表写入开关的输入和代表待写入数据的输入，且总是输出当前存储的数据
  • 当表示是否写入的输入为0时，选择延迟线的输出，否则选择待写入数据
  • 将这个信号传递给延迟线后进入下一刻，则存储器能通过读取输入判断是否要覆写数据，并在覆写前将旧数据输出

寄存器

通过八个1位存储器，实现寄存器，它额外接受一个代表读取的输入并拥有一个额外的输出端，只有当其为1时，将该刻数据输出到这个输出端上

计时器

想让一个处理器逐个读取指令，需要一个计时器：

  • 本身处于计时模式，每过一刻钟自增固定数值；接受一个代表启动擦写的输入和一个代表待写入数值的输入；始终输出当前时刻的值
  • 通过ON与数据选择器即可实现步进为1的计时器

解码器

所谓解码器，即将所有输入的所有组合输出，例如三位解码器有八位输出，这使得处理器能够处理不同的指令

通过解码器、开关与数据选择器，能够实现根据输入来选择不同运算或直接输出数据

总结

OVERTRUE架构将一条指令看作复制、运算、条件判断、立即数的任意一种，通过解码能够简单地实现读取地址、区分运算等功能，在本架构中通过两位信号四种可能来区分它们，接下来介绍如何实现该架构

在OVERTRUE架构中，能够操作的条件种类较少，主要是与0对比，或总是跳转，如果满足条件，将跳转到某一寄存器所指的地址

这个架构虽然具备自行处理指令的功能，但指令之间是隔离的，即运算功能使用固定的两个寄存器，跳转功能只判断一个固定的寄存器与一个固定的数值，立即数只能传入一个固定的寄存器，都需要通过复制来处理数据，对编写程序是极不友好的，而在之后的LEG框架能够有效提升性能

附录

基础逻辑门

NOT

1.8.NOTp

NOR

1.9.NORp

OR

1.11.ORp

AND

1.10.ANDp

XOR

1.12.XORp

算数运算

一位半加器

1.14.半加器

一位全加器

1.15.全加器

高速八位加法器

1.16.高速加法器

时序逻辑电路基本元件

数据选择器

1.19.数据选择器

计时器

1.17.计时器

三位解码器

1.18.三位解码器