二进制乘除法
二进制乘法:$N$ 进制的乘法本质上就是移位加法。
例如十进制:$1213 = 12 3 + 12 (1\ll1) = 12 3 + 12 * 10 = 36 + 120 = 146$
二进制同理:
$$
\begin{align}
& 1010 * 1101 \
&= (1010 \ll 3) + (1010 \ll 2) + (1010 \ll 0)\
&= 101\ 0000 + 10\ 1000 + 1010 \
&= 1000\ 0010\
\end{align}
$$
二进制除法 加减交替法,详见:http://courseware.eduwest.com/courseware/0013/content/0002/030003.htm
BCD 码
8421 码:利用 8,4,2,1 的权值对每位数进行编码。
例如 $7 = 4 + 2 + 1$ ,编码为 $0111$
例如 $13$ 编码为 $0001\ 0011$。(而不是 $1101$)
8421 码的加法
8421 码进行加法,如果:
- 结果小于 9 则正确。
- 结果大于 9 则错误,需要加 6 修正。
为啥是加 6 修正呢?怎么不是加 5 ?
考虑 $16$ 的十六进制表示:$0001\ 0000$
再考虑 $16$ 的 BCD 表示:$0001\ 0110$
可以发现,当产生进位时,是按照十六进制的规则演算的,而 BCD 是十进制的进位规则,因此需要加 $6$ 从而修正为 BCD 码。对于不是 16 的其它数字,进位(即结果大于等于 10)的时候都需要加 6 修正。这可以通过穷举证明。
格雷码
格雷码的表示范围:$[0,15]$
格雷码的特点:相邻整数之间的格雷码只有一位变化。
格雷码的构造方法:
- $0$ 的格雷码是 $0000$
- 最低位取反得到下一个格雷码。$1: 0001$
- 最右边的 $1$ 左边的位取反得到下一个格雷码 $2: 0011$
- 交替 2,3 两个规则可生成接下来的格雷码。
二进制转格雷码的方法
例如 $0111$,从左往右下标记作 $0, 1, 2, \cdots$
- $g_0 = b_0$
- $gi = b{i} \oplus b_{i-1}$
生成过程:
- $\underbrace{0}_{0}111$
- $\underbrace{01}_{1}11$
- $0\underbrace{11}_{0}1$
- $01\underbrace{11}_{0}$
所以格雷码是 $0100$
格雷码转二进制的方法: 实际上是上述的逆运算
例如:$1011$
- $b_0 = g_0$
- $b_i = gi \oplus b{i-1}$
得到结果:$1101$
循环冗余校验(CRC)
CRC 生成原理:https://www.bilibili.com/video/BV1V4411Z7VA
检验原理:
逻辑门
与门:
或门:
非门:
与非门:
或非门:
异或门:
同或门:
三态门:
布尔代数系统
基本代数定律:
- 交换
- 结合
- 分配
运算法则:
- $A+0=A$
- $A+1=1$
- $A \cdot 0=0$
- $A \cdot 1=A$
- $A+A=A$
- $A+\bar{A}=1$
- $A \cdot A=A$
- $A \cdot \bar{A}=0$
- $\bar{\bar{A}}=A$
- $A+A B=A$
- $A+\bar{A} B=A+B$
- $(A+B)(A+C)=A+B C$
德摩根律:
- \bar{XY} = \bar{X} + \bar{Y}
- $\bar{X+Y} = \bar{X}\bar{Y}$
布尔表达式
- SOP 形式(乘积项之和,析取范式)
- 最小项之和形式(主析取范式):利用的是布尔表达式可穷举
- POS 形式(和项的乘积,或与表达式,合取范式)
- 最大项之积形式(主合取范式)
与非门用作通用件
或非门用作通用件
半加器和全加器
半加器计算两数之和。全加器计算三数之和。输出的是本位和进位。
并行二进制加法器
通过若干进位级联的全加器级联一个半加器,可以得到这种加法器。缺点是进位需要一级一级传输。
超前进位加法器
原理:
首先看普通的并行加法器(如图),其进位输出表达式如下:
全加器 1 :
$$
C{\text {out } 1}=C{\mathrm{g} 1}+C{\mathrm{pl}} C{\text {in } 1}
$$
全加器 2 :
$$
\begin{aligned}
C{\mathrm{in} 2} &=C{\text {out } 1} \
C{\text {out } 2} &=C{\mathrm{g} 2}+C{\mathrm{p} 2} C{\text {in2 }}=C{\mathrm{g} 2}+C{\mathrm{p} 2} C{\text {out } 1}=C{\mathrm{g} 2}+C{\mathrm{p} 2}\left(C{\mathrm{g} 1}+C{\mathrm{pl}} C{\text {in1 }}\right) \
&=C{\mathrm{g} 2}+C{\mathrm{p} 2} C{\mathrm{g} 1}+C{\mathrm{p} 2} C{\mathrm{pl}} C{\text {in } 1}
\end{aligned}
$$
全加器 3:
$$
\begin{aligned}
C{\mathrm{in} 3} &=C{\text {out } 2} \
C{\text {out } 3} &=C{\mathrm{g} 3}+C{\mathrm{p} 3} C{\text {in } 3}=C{\mathrm{g} 3}+C{\mathrm{p} 3} C{\text {out } 2}=C{\mathrm{g} 3}+C{\mathrm{p} 3}\left(C{\mathrm{g} 2}+C{\mathrm{p} 2} C{\mathrm{g} 1}+C{\mathrm{p} 2} C{\mathrm{pl}} C{\text {in1 }}\right) \
&=C{\mathrm{g} 3}+C{\mathrm{p} 3} C{\mathrm{g} 2}+C{\mathrm{p} 3} C{\mathrm{p} 2} C{\mathrm{g} 1}+C{\mathrm{p} 3} C{\mathrm{p} 2} C{\mathrm{pl}} C{\text {inl }}
\end{aligned}
$$
全加器 4:
$$
C{\text {in4 }}=C{\text {out } 3}
$$
$$
\begin{aligned}
C{\text {out } 4} &=C{\mathrm{g} 4}+C{\mathrm{p} 4} C{\text {in } 4}=C{\mathrm{g} 4}+C{\mathrm{p} 4} C{\text {out } 3} \
&=C{\mathrm{g} 4}+C{\mathrm{p} 4}\left(C{\mathrm{g} 3}+C{\mathrm{p} 3} C{\mathrm{g} 2}+C{\mathrm{p} 3} C{\mathrm{p} 2} C{\mathrm{gl}}+C{\mathrm{p} 3} C{\mathrm{p} 2} C{\mathrm{pl}} C{\text {in1 }}\right) \
&=C{\mathrm{g} 4}+C{\mathrm{p} 4} C{\mathrm{g} 3}+C{\mathrm{p} 4} C{\mathrm{p} 3} C{\mathrm{g} 2}+C{\mathrm{p} 4} C{\mathrm{p} 3} C{\mathrm{p} 2} C{\mathrm{g} 1}+C{\mathrm{p} 4} C{\mathrm{p} 3} C{\mathrm{p} 2} C{\mathrm{pl}} C_{\text {in } 1}
\end{aligned}
$$
观察之后就能发现,进位输出只和 $C{\text {in } 1}, C{\mathrm{p} 1}, C{\mathrm{p} 2}, \cdots$ 有关,展开 $C{\mathrm{p} 1}, C_{\mathrm{p} 2}, \cdots$ 又都只和输入的 $A_1, A_2, \cdots , B_1, B_2,\cdots$ 有关
所以可以根据这些表达式设计电路,直接接到各个 $C_{\text {in }$ 端口上,从而实现超前进位。比如这样:
比较器
比较器是这样子的:
用法大家应该秒懂。
四位比较器比较两个八位二进制数