#import "@local/mytemplate:1.0.0": *
#import "@preview/physica:0.9.2": *

*数字电路——用电压来编码信息*

电压优点：
- 容易产生
- 检测需要大量工程知识
- 稳态功率可能较低（追求为0） 
电压缺点：
- 容易受环境影响
- 需要直流连接

#figure(
  image("pic/2024-03-21-08-37-06.png", width: 80%),
  caption: [
    信号的处理过程
  ],
)

数据处理——运算
- 模拟的信号在处理过程中会有噪声干扰
- *数字系统具有抗干扰能力（tolerance）*
  - 数字电路的特点：#footnote[导线不认为是数字电路元件，它没有这个特性]
    - 接受的输入信号可以有一定的噪声
    - 输出的信号是标准的0，1
  - 0，1之间有一定的容错能力，存在一个Forbidden Zone（要求比较小）
  - 由于离散化的处理，电路规模剧增

= 信息和编码

== 信息

信息熵（Claude Shannon）：对于一个有$M$个可能状态的系统，一个信息给出了其中$N$个状态的信息量，则信息熵$H$定义为：
$
H = log_2(N/M)
$
例如：
- 一个硬币的信息熵为$log_2(2/1)=1$bit

== 编码Encoding

编码描述了为信息分配表征的过程 
- 要选择适当、高效的编码

影响多个层面的设计 
- 机制（设备、使用的组件数量） 
- 效率（使用的比特）
- 可靠性（噪音） 
- 安全性（加密）

+ 数制：表示数量的规则
  - 每一位的构成
  - 从低位向高位的进位规则
  - 二进制：补码编码
+ 码制：用不同数码表示不同事物时遵循的规则。例如：学号，身份证号，车牌号。。。
  - 目前，数字电路中都采用二进制
  - 表示数量时称二进制
  - 表示事物时称二值逻辑

Huffman编码：根据字符出现的频率，将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示

= 逻辑代数基础

基本逻辑运算；基本公式，表示方法化简

*逻辑运算*：当二进制代码表示不同逻辑状态时，可以按一定的规则进行推理运算。

== 三种基本运算

#figure(
  table(
    columns: (auto, auto, auto),
    inset: 10pt,
    align: horizon,
    [*与*],[*或*],[*非*],
  )
)

=== 与

条件同时具备，结果发生。

真值表：

#grid(
  columns: (1fr, 1fr),
  [#figure(
    table(
      columns: (auto, auto, auto),
      align: horizon,
      [*A*],[*B*],[*AB*],
      [0],[0],[0],
      [0],[1],[0],
      [1],[0],[0],
      [1],[1],[1],
    ),
    caption: [*AB*的真值表],
  )],
  [
    #figure(
      image("pic/2024-03-26-09-29-49.png", width: 30%),
      caption: [
        与门的逻辑电路
      ],
    )
  ]
)



=== 或

条件任一具备，结果发生。

真值表：

#grid(
  columns: (1fr, 1fr),
  [#figure(
    table(
      columns: (auto, auto, auto),
      align: horizon,
      [*A*],[*B*],[*A+B*],
      [0],[0],[0],
      [0],[1],[1],
      [1],[0],[1],
      [1],[1],[1],
    ),
    caption: [*A+B*的真值表],
  )],
  [
    #figure(
      image("pic/2024-03-26-09-30-26.png", width: 30%),
      caption: [
        或门的逻辑电路
      ],
    )
  ]
)

=== 非

条件不具备，结果发生。

真值表：

#grid(
  columns: (1fr, 1fr),
  [#figure(
    table(
      columns: (auto, auto),
      align: horizon,
      [*A*],[*A'*],
      [0],[1],
      [1],[0],
    ),
    caption: [*A'*的真值表],
  )],
  [
    #figure(
      image("pic/2024-03-26-09-30-50.png", width: 30%),
      caption: [
        非门的逻辑电路
      ],
    )
  ]
)

=== 几种常用的复合逻辑运算

#figure(
  table(
    columns: (auto, auto, auto),
    inset: 10pt,
    align: horizon,
    [*与非*],[*或非*],[*与或非*],
    [
      #figure(
        image("pic/2024-03-26-09-32-16.png", width: 45%),
      )
    ],
    [
      #figure(
        image("pic/2024-03-26-09-32-34.png", width: 45%),
      )
    ],
    [
      #figure(
        image("pic/2024-03-26-09-33-04.png", width: 45%),
      )
    ],
  )
)

=== 异或

条件不同时具备，结果发生。

真值表：

#grid(
  columns: (1fr, 1fr),
  [#figure(
    table(
      columns: (auto, auto, auto),
      align: horizon,
      [*A*],[*B*],[*A⊕B*],
      [0],[0],[0],
      [0],[1],[1],
      [1],[0],[1],
      [1],[1],[0],
    ),
    caption: [*A⊕B*的真值表],
  )],
  [
    #figure(
      image("pic/2024-03-26-09-33-58.png", width: 30%),
      caption: [
        异或门的逻辑电路
      ],
    )
  ]
)

=== 同或

条件同时具备或不具备，结果发生。

真值表：

#grid(
  columns: (1fr, 1fr),
  [#figure(
    table(
      columns: (auto, auto, auto),
      align: horizon,
      [*A*],[*B*],[*A⊙B*],
      [0],[0],[1],
      [0],[1],[0],
      [1],[0],[0],
      [1],[1],[1],
    ),
    caption: [*A⊙B*的真值表],
  )],
  [
    #figure(
      image("pic/2024-03-26-09-34-48.png", width: 30%),
      caption: [
        同或门的逻辑电路
      ],
    )
  ]
)

== 逻辑代数的基本公式和常用公式

=== 基本公式

- $0 A = 0$
- $1 A = A$
- $A A = A$
- $A A' = 0$
- $A B = B A$
- $A (B C) = (A B) C$
- $A (B + C) = A B+A C$
- $(A B)' = A' + B'$[De Morgan's Law]
- $((A)')' = A$
- $1' = 0,0' = 1$
- $1 + A = 1$
- $0 + A = 0$
- $A + A = A$
- $A + A' = 1$
- $A + B = B + A$
- $A + (B + C) = (A + B) + C$
- $A + B C = (A + B)(A + C) $[Distributive Law]
  
    证明：$(A + B)(A + C)= A +A B + A C + B C = A(1 + B +C) + B C$
- $(A + B)' = A' B'$[De Morgan's Law]

其中打方括号的是重要的公式，因为它们建立了和与积的关系。

=== 常用公式

- $A + A B = A$
- $A + A'B = (A + A')(A + B) = A + B$
- $A B + A B' = A$
- $A (A + B) = A$
- $A B + A'C + B C = A B + A'C + B C D = A B + A'C$
- $A(A B)' = A B', A'(A B)' = A'$

== 逻辑代数的基本定理

=== 代入定理

在任何一个包含A的逻辑等式中，若以另外一个逻辑式代入式中A的位置，则等式依然成立。

例如：
$
A + B C = (A + B)(A + C)
$
就有
$
A + B (C D) = (A + B)(A + C D) = (A + B)(A + C)(A + D)
$

=== 反演定理

对任一逻辑式，若将该式中的0换成1，1换成0，将所有的与或非运算符号互换，则所得的逻辑式称为原逻辑式的反逻辑式。

例如：
$
Y = A(B + C) + C D
$
的反逻辑式为
$
Y' &= (A' + B'C')(C' + D')\
    &= A'C' + B' C' + A' D' + B'C' D'\
    &= A'C' + B'C' + A' D'
$

== 逻辑函数及其表示方法

逻辑函数 $Y=F(A,B,C,...)$

——若以逻辑变量为输入，运算结果为输出，则输入变量值确定以后，输出的取值也随之而定。输入/输出之间是一种函数关系。#footnote[在二值逻辑中，输入/输出都只有两种取值0/1。]

各种表示方法之间可以相互转换：
- 真值表
- 逻辑式
- 逻辑图
- 波形图
- 卡诺图
- EDA中硬件描述语言

=== 真值表——厘清思路

#figure(
  table(
    columns: (auto, auto),
    inset: 10pt,
    align: horizon,
    [输入变量 $A B C ...$],[输出 $Y_1 Y_2 ...$],
    [遍历所有可能的输入变量的取值组合],[输出对应的取值],
  )
)

=== 逻辑式——简洁

将输入/输出之间的逻辑关系用与/或/非的运算式表示就得到逻辑式。

=== 逻辑图——电路连接

用逻辑图形符号表示逻辑运算关系，与逻辑电路的实现相对应。

=== 波形图——实验室测试

将输入变量所有取值可能与对应输出按时间顺序排列起来画成时间波形。

#figure(
  image("pic/2024-03-28-08-31-22.png", width: 80%),
  caption: [
    逻辑函数的波形图
  ],
)

===  EDA中的描述方式

HDL (Hardware Description Language)

- specifies logic function only
- Computer-aided design (CAD) tool produces or synthesizes the optimized gates

两种HDLs:
- Verilog
  - developed in 1984 by Gateway Design Automation
  - IEEE standard (1364) in 1995
  - Extended in 2005 (IEEE STD 1800-2017)
- VHDL
  - Developed in 1981 by the Department of Defense
  - IEEE standard (1076) in 1987
  - Updated in 2008 (IEEE STD 1076-2017)

Verilog Modules

```verilog
module example(input logic a, b, c,output logic y);
    assign y = ~a & ~b & ~c | a & ~b & ~c | a & ~b & c;
endmodule
```

#grid(
  columns: (1fr, 1fr),
  [
    #figure(
      image("pic/2024-03-28-08-42-34.png", width: 80%),
      caption: [
        Verilog仿真
      ],
    )],
    [
    #figure(
      image("pic/2024-03-28-08-43-17.png", width: 80%),
      caption: [
        Synthesis
      ],
    )
  ]
)

=== 各种表现形式的相互转换

==== 真值表$<=>$逻辑式

例如真值表：
#figure(
  table(
    columns: (auto, auto, auto, auto),
    align: horizon,
    [*A*],[*B*],[*C*],[*Y*],
    [0],[0],[0],[0],
    [0],[0],[1],[0],
    [0],[1],[0],[0],
    [0],[1],[0],[1],
    [1],[0],[0],[0],
    [1],[0],[1],[1],
    [1],[1],[0],[1],
    [1],[1],[0],[0],
  ),
  caption: [
    逻辑函数的真值表
  ],
)

逻辑式（合取范式）：
$
Y = A'B C + A B'C + B'C
$

例如：
$
A ⊕ B = A'B + A B'
$

==== 真值表$<=>$逻辑式

#figure(
  image("pic/2024-03-28-08-57-33.png", width: 50%),
  caption: [
    逻辑函数的真值表与逻辑图
  ],
)

== 逻辑函数的两种标准形式

+ 最小项之和
+ 最大项之积

*最小项 $m$（Minterm）：*
- $m$是乘积项
- 包含$n$个因子
- $n$个变量均以原变量和反变量的形式在$m$中出现一次

#figure(
  table(
    columns: (auto, auto, auto, auto),
    inset: 10pt,
    align: horizon,
    [*最小项*],[*取值*],[*对应十进制数*],[*编号*],
    [$A'B'C'$],[000],[0],[$m_0$],
    [$A'B'C$],[001],[1],[$m_1$],
    [$A'B C'$],[010],[2],[$m_2$],
    [$A'B C$],[011],[3],[$m_3$],
    [$A B'C'$],[100],[4],[$m_4$],
    [$A B'C$],[101],[5],[$m_5$],
    [$A B C'$],[110],[6],[$m_6$],
    [$A B C$],[111],[7],[$m_7$],
  ),
  caption: [
    三个变量的最小项
  ],
)

*最小项的性质：*
- 在输入变量任一取值下，*有且仅有一个最小项的值为1*。
- *全体最小项之和为1*。
- 任何两个最小项之积为0。
- *两个相邻的最小项之和可以合并*，消去一对因子，只留下公共因子。

把最小项取反，得到最大项。

*最大项 $M$（Maxterm）：*
- $M$是和项
- 包含$n$个因子
- $n$个变量均以原变量和反变量的形式在$M$中出现一次

#figure(
  table(
    columns: (auto, auto, auto, auto),
    inset: 10pt,
    align: horizon,
    [*最大项*],[*取值*],[*对应十进制数*],[*编号*],
    [$A+B+C$],[000],[0],[$M_0$],
    [$A+B+C'$],[001],[1],[$M_1$],
    [$A+B'+C$],[010],[2],[$M_2$],
    [$A+B'+C'$],[011],[3],[$M_3$],
    [$A'+B+C$],[100],[4],[$M_4$],
    [$A'+B+C'$],[101],[5],[$M_5$],
    [$A'+B'+C$],[110],[6],[$M_6$],
    [$A'+B'+C'$],[111],[7],[$M_7$],
  ),
  caption: [
    三个变量的最大项
  ],
)

$
Y &= sum m_i\
Y' &= sum_(k != i) m_k\
Y &= (sum_(k != i) m_k)'\
Y &= product_(k != i) m_k ' = product_(k != i) M_k
$
*最小项之和 = 最大项之积 （二者编号取补）*

== 逻辑函数的化简法

=== 逻辑函数的最简形式

*最简与或：*包含的乘积项已经最少，每个乘积项的因子也最少，称为最简的*与-或逻辑式*。

$
Y_1 &= A B C + B' C + A C D\
Y_2 &= A C + B'C 
$

=== 公式化简法

反复应用基本公式和常用公式，消去多余的乘积项和多余的因子。

例：
$
Y &= A C + B' C +B D' + C D' + A( B + C' ) + A'B C D' + A B' D E\
  &= A C + B' C + B D' + C D' + A(B'C)' + A B' D E\
  &= A C + B' C + B D' + C D' + A + A B' D E\
  &= A + B' C + B D' + C D'\
  &= A + B' C + B D'
$


=== 卡诺图化简法

逻辑函数的卡诺图表示法
- 实质：将逻辑函数的最小项之和的以图形的方式表示出来。
- 以2n个小方块分别代表 n变量的所有最小项，并将它们排列成矩阵，而且使*几何位置相邻的两个最小项在逻辑上也是相邻的*（只有一个变量不同），就得到表示n变量全部最小项的卡诺图。

#grid(
  columns: (1fr, 1fr),
  [
    #figure(
      image("pic/2024-03-28-09-21-03.png", width: 50%),
      caption: [
        2个变量的卡诺图
      ],
    )],
    [
    #figure(
      image("pic/2024-03-28-09-21-16.png", width: 80%),
      caption: [
        3个变量的卡诺图
      ],
    )
  ],
  [
    #figure(
      image("pic/2024-03-28-09-21-36.png", width: 70%),
      caption: [
        4个变量的卡诺图
      ],
    )
  ],
  [
    #figure(
      image("pic/2024-03-28-09-21-58.png", width: 80%),
      caption: [
        5个变量的卡诺图
      ],
    )
  ]
)

其实在卡诺图#footnote[卡诺图的排布不唯一，只需保留相邻]中相邻的最小项并不只是位置相邻的，还包括边界相邻的。

用卡诺图表示逻辑函数
1. 将函数表示为最小项之和的形式$sum m_i$
2. 在卡诺图上与这些最小项对应的位置上添入1，其余地方添0。


#figure(
  table(
    columns: (auto, auto, auto, auto, auto),
    align: horizon,
    [*A B*],[*00*],[*01*],[*11*],[*10*],
    [*00*],[],[1],[],[],
    [*01*],[1],[],[],[1],
    [*11*],[],[],[],[],
    [*10*],[1],[1],[1],[1],
  ),
  caption: [
    逻辑函数的卡诺图
  ],
)

对应的函数为$Y = A'B'C'D + A'B D' +A B'$。

用卡诺图化简函数：
- 依据：具有相邻性的最小项可合并，消去不同因子。
- 在卡诺图中，最小项的相邻性可以从图形中直观地反映出来。*一定是$2^n$*。

合并最小项的原则：
- 两个相邻最小项可合并为一项，消去一对因子
- 四个排成矩形的相邻最小项可合并为一项，消去两对因子
- 八个相邻最小项可合并为一项，消去三对因子

卡诺图化简的原则：
- 化简后的乘积项应包含函数式的所有最小项，*即覆盖图中所有的1*。
- 乘积项的数目最少，即*圈成的矩形最少*。
- 每个乘积项因子最少，即*圈成的矩形最大*。

不唯一性：卡诺图化简的结果不唯一，但是最简的项数是一样的。

#figure(
  image("pic/2024-04-02-08-10-18.png", width: 80%),
  caption: [
    逻辑函数的卡诺图化简
  ],
)

#figure(
  image("pic/2024-04-02-08-10-48.png", width: 80%),
  caption: [
    逻辑函数的卡诺图化简
  ],
)

=== 具有无关项的逻辑函数及其化简

==== 约束项、任意项和逻辑函数式中的无关项

*约束项*：在逻辑函数中，对输入变量取值的限制，在这些取值下为1的最小项称为约束项。

*任意项*：在输入变量某些取值下，函数值为1或为0不影响逻辑电路的功能，在这些取值下为1的最小项称为任意项。

*逻辑函数中的无关项*：约束项和任意项可以写入函数式，也可不包含在函数式中，因此统称为无关项。

==== 无关项在化简逻辑函数中的应用
- 合理地利用无关项，可得更简单的化简结果。
- 加入（或去掉）无关项，应使化简后的项数最少，每项因子最少。从卡诺图上直观地看，加入无关项的目的是为矩形圈最大，矩形组合数最少。

#figure(
  image("pic/2024-04-02-08-23-04.png", width: 80%),
  caption: [
    逻辑函数的卡诺图化简
  ],
)

#figure(
  image("pic/2024-04-02-08-23-45.png", width: 80%),
  caption: [
    逻辑函数的卡诺图化简
  ],
)

=== 机器化简法

机器化简法：奎恩—麦克拉斯基化简法（列表法）——Q—M法

#figure(
  image("pic/2024-04-02-08-26-20.png", width: 80%),
  caption: [
    机器化简法
  ],
)