基本概念与逻辑门⚓︎

注：由于实际内容比教材内容少，因此对课程内容分类如下：

基本概念与逻辑门

Chap.1 Introductory Concepts
Chap.2 Number Systems, Operations, and Codes
Chap.3 Logic Gates
Chap.4 Boolean Algebra and Logic Simplification

组合逻辑

Chap.5 Combinational Logic Analysis
Chap.6 Functions of Combinational Logic

时序逻辑

Chap.7 Latches, Flip-Flops, and Timers
Chap.8 Counters

555定时器

本部分内容为：基本逻辑与逻辑门.

数字量与模拟量⚓︎

数字量⚓︎

数字量（digital quantity）是一类在时间和数值上都离散的量（having a discrete set of values）；模拟量（analog）是一类在时间和数值上都连续的量（having continuous values）。

模拟量⚓︎

很多时候，模拟信号和数字信号之间需要相互转换，我们一般将数模转换简称为D/A或DAC，将模数转换简称为A/D或ADC。

想要将模拟量转化为数字量，一般需要经过采样、保持、量化、编码的过程。注意，经过采样的模拟信号是阶梯信号，不是数字信号。

采样，即按照一定的时间间隔取出模拟量上的数值点；

保持，即将信号在两次取样之间的值固定为上一次取样的值；

量化，即将一定区间范围内的模拟信号取样值统一的按照某一整数值来处理

比特、电路逻辑和信号⚓︎

比特和电路逻辑⚓︎

二元系统中的任一数位（each of the two digits in the binary system），称为一个比特（bit）。

在数字信号系统中，0或1都分别是一个比特。同时，这两个比特分别使用高、底电平中的一种来表示。

如果用高电平（HIGH）表示1，低电平（LOW）表示0，那么这种电路逻辑被称为正逻辑（positive logic）；相反的，如果用高电平（HIGH）表示0，低电平（LOW）表示1，那么这种电路逻辑被称为负逻辑（negative logic）。

实际上，所谓的高低电平并不是一个两个严格的电压，而是一段电压范围。

如上图所示，在上下两个电压范围内的电压值，都会被分别视为高、低电平，而两者中间存在一段互不相交的范围，这一部分的电压值将被视为无效的电压值。

脉冲信号⚓︎

如上图所示，由低电平变化为高电平的脉冲，称为正脉冲（positive-going pulse）；由高电平变化为低电平的脉冲，称为负脉冲（negative-going pulse）。

每次脉冲都有前沿（leading edge）和后沿（trailing edge），无论是正脉冲还是负脉冲，首次出现电平变化时产生前沿，最后再次出现电平变化时产生后沿。

需要注意的是，上图的脉冲是一种理想的模型，实际中的脉冲信号存在着抖动等问题，不会像上图那样规整，下面会简单介绍实际中的脉冲信号图形。

如上图所示，对于实际中的脉冲，我们对其的一些物理量进行定义。

上升时间（rise time）从脉冲振幅（pluse amplitude）的10%上升到90%所花费的时间

下降时间（fall time）从脉冲振幅（pluse amplitude）的90%下降到10%所花费的时间

脉冲宽度（pulse width）从达到脉冲振幅50%到再次下降到50%所花费的时间

脉冲序列⚓︎

脉冲序列分为周期序列和非周期序列，简单介绍一下周期序列。

周期序列的典型代表就是时钟信号，他常常被作为数字系统的基准。

在一个周期信号周期内，正脉冲宽度占整个周期宽度的百分比，称为占空比（duty cycle）

数制⚓︎

常用的进制与其表示⚓︎

B：二进制（binary） O：八进制（octal） D：十进制（decimal） H：十六进制（hexadecimal）

制转换⚓︎

十进制转二进制(Decimal-To-Binary Conversion)⚓︎

反复利用除法除以\(2\)，将得到的余数逆序写出即可.以下是一个例子\((12)\)：

\[ \begin{align*} 12\div 2&=6\cdots 0\\ 6\div 2&=3\cdots 0\\ 3\div 2&=1\cdots 1\\ 1\div 2&=0\cdots 1\\ \end{align*} \]

余数逆序排列为1100，因此\(12_{(10)}=1100_{(2)}\).

若有小数部分，则连续将小数部分乘以\(2\)，不断取出整数部分，然后顺序排序，直到最终余0或者达到要求位数为止，例如0.3215：

\[ \begin{align*} 0.3125\times 2&=0.625\\ 0.625\times 2&=1.25\\ 0.25\times 2&=0.5\\ 0.5\times 2&=1\\ \end{align*} \]

于是，\(0.3125_{(10)}=0.0101_{(2)}\).

二进制转十进制⚓︎

各数位的值乘以其权重即可.

数的表示⚓︎

无符号数(Unsigned Number)⚓︎

原码⚓︎

十进制数对应的二进制数，称为这个数的原码.

最低有效位LSB（least significant bit）：二进制数码的最右侧一位

最高有效位MSB（most significant bit）：二进制数码的最左侧一位

反码(1's complements)⚓︎

将某数的原码逐位按\((0,1)\mapsto(1,0)\)的方式映射，所得的二进制编码就称为原码所对应数的反码.

补码(2's complements)⚓︎

取某一个数的补码，进行如下运算：

\[ \text{补码}=\text{反码}+1, \]

得到的结果就是这个数的补码.

除了这种方法，我们也可以从原码直接获得补码：

将原码从从左到右第一个值为1的数位往左的所有数位取反，往右的所有数位保持不变，即可获得其补码

符号数(Signed Number)表示⚓︎

符号-数值形式(Sign-Magnitude Form)⚓︎

以8位为例，第一位为符号位(Sign bit)，后七位为数值位(Magnitude bits).对于符号位，规定：正为0，负为1.数值位就是这个数的二进制表示.

这种表示下，欲写出其对应的十进制的值，首先确定后七位表示的数值，而后根据符号位添加正负号.

反码形式(1's Complement Form)⚓︎

对于正数而言，其反码形式表示就是其符号-数值形式的表示.对负数而言，其反码形式是该负数对应正数的反码形式.

这种表示下，欲写出其对应的十进制，先按权重得出第一步结果，而后再加一.例如：

\[ \begin{align*} 11101000&=1\times(-2^7)+1\times 2^6+1\times 2^5 +\cdots +1\times 2^3+\cdots+0\times 2^0{\color{red}+1}\\ &=-24{\color{red}+1}\\ &=-23. \end{align*} \]

注：这里加权的最高位看做\(-2^7\)

补码形式(2's Complement Form)⚓︎

对于正数而言，其补码形式依旧是其符号-数值形式的表示.但是对于负数而言，是其对应正数的补码.

写出这种形式下编码对应的十进制数与上述反码形式类似，除了最后不再需要\(+1\)，即直接按照加权写出即可.

注：这里加权的最高位看做\(-2^7\)

表示范围⚓︎

上述三种情况下，所能表示的最多组合数一共有\(2^8\)种.推广开来，对于\(n\)个比特位(或者说\(\dfrac{n}{8}\)个字节)，一共具有的组合数为

\[ \textrm{Total Combinations}=2^n, \]

对于补码形式其可以表示的范围包含

\[ \textrm{Range}=-(2^{n-1})\ \textrm{to}\ (2^{n-1}-1). \]

一共可以表示\(2^n\)个不同的数字

相比之下，符号-数值形式和反码形式的表示范围仅包含：

\[ \textrm{Range}=-(2^{n-1}-1)\ \textrm{to}\ (2^{n-1}-1). \]

即，只能表示\(2^{n}-1\)个不同的数字，原因是零在这两种情况下具有两种表示方法.

符号数的运算⚓︎

计算机中表示数码的形式主要是补码，因此主要讨论补码的计算方式。

加法与减法⚓︎

加法和减法，本质上是一致的，一个数减另一个数，可以转换为加它的对应补码的形式，即将减法转化为加负数的形式。

对于补码而言，加法直接将两个数的补码相加，并舍去超过最高位数的数字，即可得到其结果的补码，例如：

\[ 0110+1011=10001 \rightarrow 0001 \\ 6+(-5)=1 \rightarrow 0001 \]

但是需要注意的是，如果计算的结果超过了数码可以表示的上限或者下限，那么就无法得到正确的结果，这种现象称为数据溢出（overflow condition），例如：

\[ 0110+0101=1011 \\ 6+5=-5 \]

在上述的例子中，由于左边计算的结果超过了正数的上限“+7”，因此在计算后得到了显然错误的结果，这就是溢出现象。

乘法与除法⚓︎

乘除法的根本是加减法，因此可以预测，其计算也可以通过补码形式来计算，而事实上也确实如此。

两个补码形式数的乘除法，可以直接按正常方式乘除法，舍去多余的位数，得到结果的补码（前提是不可以数据溢出），例如\(2\times 3=6\)：

\[ \begin{align*} &0010\\ \times&0011\\ \hline &0010\\ 0&010\\ \hline &0110 \end{align*} \]

在上述例子中，直接使用补码计算了“\(2\times3\)”,而结果也确实是其结果“6”的补码

其他的编码与数制⚓︎

十六进制数⚓︎

与二进制的关系⚓︎

二进制与十六进制的转化是十分方便的，从右向左，每四位二进制数对应十六进制数的一位

十六进制的反码/补码⚓︎

对于十六进制数的取反，按照如下对照：

\[ 0,1,2,3,4......D,E,F \]

\[ F,E,D.......4,3,2,1,0 \]

将十六进制数的每一位取反，即可得到其对应的反码

在此基础上，对反码的结果“\(+1\)”即可得到补码，这和二进制数是一样的

BCD码⚓︎

在四位二进制数构成的16个编码中，选取10个来表示0-9，这样的一系列编码称为BCD码

下表是一些常见的BCD码

其中，前三种简单易懂，四个数字分别表示个四位的权重，只要主义0-4均以0开头，5-9均以1开头，就可以根据其权重算出对应的值即可

余三码，可以看做在8421码的基础上对应加三得到，即8421用来二进制0-9表示十进制对应数，而余三码用了3-12来表示十进制的0-9

最后的余三循环码，则是在余三码的基础上，进行循环操作所得到

格雷码⚓︎

格雷码可以由二进制数获得，只要将二进制数向右移动一位，并与自身不进位相加即可获得，例如：

\[ \begin{align*} 10110010\\ +\quad 1011001\\ \hline 11101011 \end{align*} \]

则二进制数“10110010”对应的格雷码是“11101011”

逻辑门⚓︎

逻辑门的表示方法⚓︎

符号表示法（standard logic symbol）⚓︎

下表展示了所有逻辑门对应的符号

其中类似第三列的表示法一般称为rectangle outline symbol，而类似第四列的形状各不相同的表示法一般称为distinctive shape symbol

真值表表示（truth table）⚓︎

展示了所有可能输入对应的输出结果的表格称为真值表

时序图（timing diagram）⚓︎

展示多个信号波在时序下的相互关系的图，称为时序图

用时序图表示逻辑门，能更好的表示长时间尺度上输入信号与输出信号之间的关系，以及逻辑门的工作状态

逻辑表达式（logic expression）⚓︎

用字母表示信号，并按照布尔代数的规则表示输出和输入信号之间关系的表达式称为逻辑表达式

非门(NOT, inverter)⚓︎

输出信号和属于信号始终相反。

其真值表为：

INPUT	OUTPUT
\(0\)	\(1\)
\(1\)	\(0\)

非门的逻辑表达式为

\[ X=\overline{A}, \]

读作“非A”或者“A bar”.

与门(AND)⚓︎

与门可以接受多个输入，当且仅当所有输入都为\(1\)时，输出\(1\)；否则输出\(0\).

与门的逻辑表达式为

\[ X=AB, \]

在计算上，有着和乘法相同的性质，因此称为逻辑乘法(Boolean multiplication).

或门(OR)⚓︎

一个或门可以有多个输入，当其中至少存在一个输入为\(1\)时，或门输出\(0\)；当且仅当所有输入都为\(0\)时，输出\(0\).

或门的逻辑表达式为

\[ X=A+B. \]

与非门(NAND)⚓︎

与非门接受多个输入，当所有输入都为\(1\)时，输出\(0\)；否则输出\(1\).

与非门的逻辑表达式为

\[ X=\overline{AB}. \]

与非门的效果可以由一个与门与一个非门等效替代.

或非门(NOR)⚓︎

或非门接受多个输入，当存在至少一个输入为\(1\)时，输出\(0\)；否则输出\(1\).

其逻辑表达式为

\[ X=\overline{A+B}. \]

或非门可以由一个或门和一个非门等效替代.

异或门(Exclusive-OR)⚓︎

异或门接受两个输入，当两个输入相同时，输出\(0\)；否则输出\(1\).

其逻辑表达式为

\[ X=\overline{A}B+A\overline{B}=A\oplus B. \]

同或门(Exclusive-NOR)⚓︎

同或门接受两个输入，当两个输入不同时，输出\(0\)；否则输出\(1\).

其相当于一个异或门与一个非门的组合.

逻辑表达式为

\[ X=\overline{\overline{A}B+A\overline{B}}=\overline{A\oplus B}. \]

逻辑代数运算(Logic Algebra)⚓︎

基本逻辑运算⚓︎

逻辑加法和逻辑乘法⚓︎

我们定义布尔值的加法和乘法满足如下的规则：

\[ \begin{cases} 0+0=0,\\ 0+1=1,\\ 1+0=1,\\ 1+1=1, \end{cases} \]

\[ \begin{cases} 0\cdot 0=0,\\ 0\cdot 1=0,\\ 1\cdot 0=0,\\ 1\cdot 1=1, \end{cases} \]

逻辑代数定律(Laws of Boolean Algebra)⚓︎

交换律(Commutative Laws)：

\[ A+B=B+A,\quad AB=BA, \]

结合律(Assocaitive Laws)：

\[ (A+B)+C=A+(B+C),\quad (AB)C=A(BC), \]

分配率(Distributive Law)：

\[ A(B+C)=AB+AC. \]

运算规则（rules of boolean algebra）⚓︎

对于布尔值\(A\)、\(B\)和\(C\)，有如下关系成立：

\(A+0=A\)
\(A+1=1\)
\(A\cdot 0=0\)
\(A\cdot 1=A\)
\(A+A=A\)
\(A+\overline{A}=1\)
\(A\cdot A=A\)
\(A\cdot\overline{A}=0\)
\(\overline{\overline{A}}=A\)
\(A+AB=A\)

证明

\[ \begin{align*} A+AB&=A(1+B)\\ &=A. \end{align*} \]

\(A+\overline{A}B=A+B\)

证明

\[ \begin{align*} A+\overline{A}B&=(A+AB)+\overline{A}B\\ &=(AA+AB)+\overline{A}B\\ &=AA+AB+A\overline{A}+\overline{A}B\\ &=(A+\overline{A})(A+B)\\ &=A+B. \end{align*} \]

\((A+B)(A+C)=A+BC\)

证明

\[ \begin{align*} (A+B)(A+C)&=AA+AC+AB+BC\\ &=A+AC+AB+BC\\ &=A(1+C)+AB+BC\\ &=A+AB+BC\\ &=A(1+B)+BC\\ &=A+BC. \end{align*} \]

\(AB+\overline{A}C+BC=AB+\overline{A}C\)

证明

\[ \begin{align*} AB+\overline{A}C+BC&=AB+\overline{A}C+(ABC+\overline{A}BC)\\ &=(AB+ABC)+(\overline{A}C+\overline{A}BC)\\ &=AB+\overline{A}C. \end{align*} \]

德摩根定律(DeMorgan's Theorems)⚓︎

对于布尔值\(A\)和\(B\)，始终有如下关系成立：

\[ \overline{AB}=\overline{A}+\overline{B},\quad \overline{A+B}=\overline{A}\overline{B}. \]

这称为德摩根定律.

取反原理⚓︎

德摩根定理进一步拓展，可以得到更加一般的取反方式：

对于一个布尔变量\(F\)，将其表达式中所有的运算量与运算符按照以下规则变化

\[ \begin{cases} \cdot \rightarrow + \\ + \rightarrow \cdot \\ 0 \rightarrow 1 \\ 1 \rightarrow 1 \\ A \rightarrow \overline{A} \end{cases} \]

则可得到\(\bar{F}\)

在使用这种取反方法时，应注意一下两条规则：

规则1：取反后运算顺序不可改变

例：

\[ F=\overline{A}\overline{B}+CD+1 \]

\[ \downarrow \\ \]

\[ \overline{F}=(A+B)\cdot(\overline{C}+\overline{D})\cdot 0 \]

在\(F\)中，乘法的运算优先于加法，因此在反演之后，需要添加括号来保证乘法变化后对应的加法被优先计算

规则2：对于同时覆盖多个变量的取反，不做变动

例：

\[ F=\overline{B+\overline{C}+\overline{D+\overline{E}}} \]

\[ \downarrow \]

\[ \overline{F}=\overline{B}\cdot C\cdot \overline{\overline{D}\cdot E} \]

对于同时覆盖了\(D\)和\(E\)的取反号，不做处理，直接保留

布尔表达式的形式⚓︎

与或式(Sum-of-Products, SOP)⚓︎

如果布尔表达式由布尔值乘积之和构成，那么称为与或式(SOP).例如：\(ABC+\overline{A}C\)就是SOP.

在SOP表达式中所有出现过的布尔值的集合称为布尔表达式的域(domain of a boolean expression).

如果SOP式中每一项都完全覆盖了这个表达式的域，那么称之为标准的与或式(the Standard SOP Form)，这些项也称为最小项.最小项的二进制表达式满足对应关系：\(1\)对应\(A\),\(0\)对应\(\overline{A}\).对于任意一个SOP表达式，我们可以利用\(A+\overline{A}=1\)来补足未出现的布尔值，例如：

\[ \begin{align} AB+ABC&=AB(C+\overline{C})+ABC\\ &=ABC+AB\overline{C}. \end{align} \]

或与式(Product-of-Sums, POS)⚓︎

如果布尔表达式由布尔值和之乘积构成，那么称为或与式(POS).例如：\((\overline{A}+C)(B+C)\)就是POS.

如果POS式中每一项都完全覆盖了这个表达式的域，那么称之为标准的或与式(the Standard POS Form).这些因子也称为最大项.最大项的二进制表达式满足对应关系：\(0\)对应\(A\),\(1\)对应\(\overline{A}\).对于任意一个POS表达式，我们可以利用\((A+B)(A+C)=A+BC\)来补足未出现的布尔值，例如：

\[ \begin{align} (A+\overline{B})(A+B+C)&=(A+\overline{B}+C\overline{C})(A+B+C)\\ &=(A+\overline{B}+C)(A+\overline{B}+\overline{C})(A+B+C). \end{align} \]

SOP与POS的互化⚓︎

对于给定的SOP表达式，找到每一项对应的二进制表示，而后找出所有二进制情况中剩下的二进制表达，这些表达就是POS中每个因子，例如：

对于SOP表达式

\[ \overline{A}\overline{B}\overline{C}+\overline{A}B\overline{C}+\overline{A}BC+A\overline{B}C+ABC, \]

每一项对应的二进制表示是

\[ 000+00+011+101+111, \]

剩下的二进制表达还有\(001\)、\(100\)和\(110\)，因此POS表达式为

\[ (A+B+\overline{C})(\overline{A}+B+C)(\overline{A}+\overline{B}+C). \]

SOP和POS与真值表的关系⚓︎

根据真值表，我们可以快速写出标准的SOP和POS表达式.

对于SOP表达式，我们找到真值表中所有输出为\(1\)的输入情况，每种输入情况对应的最小项之和就是SOP表达式.

对于POS表达式，我们找到真值表中所有输出为\(0\)的输入情况，每种输入情况对应的最大项之积就是POS表达式.

卡诺图(The Karnaugh Map)⚓︎

定义⚓︎

卡诺图类似于真值表，能够反映出对于不同输入的逻辑表达式的结果.对于一个具有\(n\)个逻辑变量的卡诺图，其一般具有\(2^n\)个方格，以下是一个具有\(4\)个逻辑变量的卡诺图.

其中，用\(m_i\)来代表第\(i\)个方格，对应关系满足：

\[ i_{(10)}=\overline{ABCD}_{(2)}. \]

相邻的方格(Cell Adjacency)⚓︎

对于相邻方格，他们所代表的最小项需要逻辑相邻.即，仅有一个逻辑变量发生了改变.例如：上图中，\(m_0\)与\(m_4\)相邻，即只有逻辑变量\(A\)发生了改变.

注意：对于卡诺图边缘的方框，例如上图中的\(m_1\)，其左侧的方格我们看做是\(m_9\).这样一来，具有\(4\)个逻辑变量的卡诺图的每个方格都有三个相邻的方格.一般而言，对于具有\(n\)个逻辑变量的卡诺图，其具有\(n\)个相邻的方格.

卡诺图与逻辑表达式⚓︎

标准形式的SOP、POS⚓︎

由于卡诺图与真值表本质上反映了相同的信息，因此根据卡诺图写出标准形式的SOP(POS)与根据真值表写SOP(POS)类似.

最简形式的SOP⚓︎

化简成最简形式的SOP，采取画方格(方格中的元素为\(1\))的形式，一般而言，这样的方格需要包含\(2^n(n\in\mathbb{N}^*)\)个元素.例如上图可分为两个方格：

\[ S_1=\{m_i|i=0,2,4,6,8,10,12,14\}, \]

\[ S_2=\{m_j|j=8,9,10,11,12,13,14,15\} \]

其中，\(S_1\)的公共特征是\(D=0\)；\(S_2\)的特征是\(A=1\)，于是其逻辑表达式为

\[ F=A+\overline{D}. \]

最简形式的POS⚓︎

仍如上图所示，我们仍旧采取画方格的形式，只不过此时我们画出的元素应该为\(0\).对于上图，我们画出一个方格：

\[ S_1=\{M_i|i=1,3,5,7\}, \]

这时，其对应的特征是\(A=0,D=1\)，其对应的最大项为\(A+\overline{D}\)，于是其POS为