第二章 数值与编码

进制转换

任意进制转换

进制转换是信息安全数学基础和数电领域的重要概念。一般情况下，任意进制转换可遵循 $N \Rightarrow 10 \Rightarrow M$ 的路径。

• $N \Rightarrow 10$（转换为十进制）: 对于任意进制数 $N$，将其转换为十进制数，我们依据各数位上的数字乘以对应的权值（即进制的幂次方）并求和。

• $10 \Rightarrow M$（从十进制转换）:

  • 整数部分: 反复除以目标进制数 $R$ 取余数，直到商为 0。余数逆序排列即为目标进制表示。
  • 小数部分: 反复乘以目标进制数 $R$ 取整数部分，直到小数部分为 0 或达到所需精度。整数部分顺序排列即为目标进制表示。

$2^N \rArr 2^M$ 的简便方法

二进制四则运算

WARNING

（此处反码、余码有待补充内容，涉及计组知识，似乎不是数电重点）

加法

二进制加法直接且直观，溢出的位（carry-out bit）将被直接舍弃。

减法

在二进制运算中，负数的表示是一个关键问题。为此，我们引入三种计算机内部常用的二进制数表示方法：原码、反码和补码。

原码、反码、补码：为了电路降本增效而生

Sign-magnitude （原码）, 1’s complement （反码）, 2’s complement （补码）

"降本增效"虽在网络语境中带有讽刺意味，但其背后蕴含的优化思想值得我们借鉴。

对于无符号整数（不考虑浮点数），十进制与二进制的转换已足够满足需求。然而，负数的表示是数电和计算机组成原理中的重要课题，原码、反码、补码是解决这一问题的核心。

名词解释:

• Most Significant Digit (MSD): 最高有效位
• Least Significant Digit (LSD): 最低有效位

原码

原码的表示方法与正常的二进制表示法相似，但最高有效位（MSB）作为符号位：0 表示正数，1 表示负数。

例如：

$$\begin{align*} (5)_{10} &= 00000000000000000000000000000101_2 \\ (-5)_{10} &= 10000000000000000000000000000101_2 \end{align*}$$

原码的缺点在于，判断符号需要额外的 if...else... 逻辑，这对于加法器等基础电路设计来说并不理想。

原码到反码、补码的计算

正数的三种编码相同，负数的三种编码不同。

负数的反码 = 正数的各位取反 负数的补码 = 正数的各位取反+1

补码同样使用最高位作为符号位，但其符号位参与加权运算。

对于一个 N 位的补码，最高位的权重 $w = -2^{N-1}$。

简便求法: 保持符号位不变，对数值位执行“减1取反”操作。

最终效果：

$$\begin{align*} \text{原码} &：B \\ \text{补码} &：2^n - B \quad (\text{对于 } n \text{ 位二进制表示}) \end{align*}$$

为什么补码能够完成加法与减法的统一

你有玩过数电的加法器吗？

一个 8 位加法器，一旦累加到 111 也就是 8，下一个状态本来应该是 1000，但是却由于 overflow 将最高位舍弃，重新回到了 0。

这样的加法器不能简单地用 $f(i+1) = i +1$ 描述，用 $f(i+1) = (i+1) \mod 2^N$ 描述它更为准确。

每一次自增都经历一次取模的过程。运算被封闭在了 $[0, 2^N]$ 的整数环之内。

正数和负数，只不过是沿着 0 这个起点往环的两端跑而已。

原码、反码、补码都只不过是在这个环上以不同的方式划分正数和负数的区间罢了。不过他们的性质就没有补码这么好了。

这一部分详见农哥的 ppt

补码和原码的表示范围（以 8 位为例子）

原码有两个 0（符号位为 0,1 各一个），所以它的范围是 $[-2^7+1, 2^7 - 1]$

补码只有 1 个 0，所以它的范围是 $[-2^7, 2^7 - 1]$

第三周

早期计算机系统，只有硬件 adder，其他运算以软件形式实现.

常用编码

十进制数的二进制编码（Binary-Coded Decimal 勿与 四位一组 BCD 码混淆）

有权码：8421BCD, 2421BCD 无权码：余3码，二五混合码，10中取1码（独热 one-hot code）

可靠性编码

Gray Code

Gray Code 相邻状态只有 1 bit 不同.

• 反射性
• 单位距离 1 bit
• 循环性
• 应用：间跳少，出错概率低；卡诺图

检错和纠错的代价是额外的储存空间使用. 4 bit -> 16 states -> 10 种信息 检错和纠错能力越强，冗余位就越多.

编码规则

在数学上，

binary -> decimal -> mod 10

得到的每个余数编为一个 4 bit 的码.

高位互补，低位对称.

// TODO

n 维体和距离

$$L = 2c + d + 1$$

若 L = 3，

• 方案一：$c=1,d=0$，纠错1位，（额外）检错0位
• 方案二：$c=0,d=2$，纠错0位，（额外）检错2位

c := Correction

d := Detection

若出错概率低，重传开销小，更推荐方案二：检错+重传.

多维体见农哥 PPT P46

奇偶校验

Hamming Code

Error Checking & Correcting

可靠性

补充说明，不做过多要求.

L = 3

CRC 循环冗余码

使用最广的

比如压缩与解压.

数据链路层《计算机网络》

突发错误，mod 2 除法

不做过多要求，大概知道原理.

二维码

对行列都进行校验.

并行/串行线路编码

并行 bus 总线

串行 USB 光纤 网口 DP口

多拍，提高时钟能够提高速率

字符/状态/控制编码

ASCII, GBK, Unicode

开关逻辑代数