2-数制与码制

数制与数制间的转换

数制

• 基数 $R$：可用数码的个数，数码为 $0,1,\dots ,R-1$。
• 第 $i$ 位的位权为 $R^i$；满 $R$ 进 1，借 1 当 $R$。

$$(N{)}_R=\sum _i{K}_i{R}^i,0\le K_i<R$$

数制	基数	数码	常用标记
二进制（Binary）	2	0、1	B 或下标
八进制（Octal）	8	0~7	Q 或下标
十进制（Decimal）	10	0~9	D 或下标
十六进制（Hexadecimal）	16	09、AF	H、0x 或下标

二进制数

• MSB（Most Significant Bit）：最高有效位，权值最大。
• LSB（Least Significant Bit）：最低有效位，权值最小。

传输方式	特点
串行传输	逐位传送，数据线少；需约定 MSB 或 LSB 先发送
并行传输	各位同时传送，速度快；数据线和收发电路较多

补充：
高速数据传输一般用串行。并行线路多，而且高速时容易出现不同线路信号到达时间不一致（“时延偏斜”）。

数制转换

转换方法

• $R$ 进制转十进制：按权展开。
• 十进制整数转 $R$ 进制：除基取余，逆序读。
• 十进制小数转 $R$ 进制：乘基取整，顺序读。

例：

$$\begin{array}{rl}37& =2\times 18+1\\ 18& =2\times 9+0\\ 9& =2\times 4+1\\ 4& =2\times 2+0\\ 2& =2\times 1+0\\ 1& =2\times 0+1\end{array}\Rightarrow (37{)}_{10}=(100101{)}_2$$

小数部分若不能乘到 0，只能取近似值：

$$(0.39{)}_{10}\approx (0.0110001111{)}_2$$

二进制、八进制与十六进制

转换方法

• 二进制与八进制：三位 B 对应一位 O。
• 二进制与十六进制：四位 B 对应一位 H。
• 八进制与十六进制：通过先转换为二进制再转换
• 以小数点为界分组，不足时在远离小数点的一侧补 0。

例：

$$(57{)}_{10}=(00111001{)}_2=(39{)}_{16}$$ $$(0.625{)}_{10}=(0.101{)}_2=(0.5{)}_8=(0.\mathrm{A}{)}_{16}$$

---

算术运算

无符号二进制数

略

固定位宽与溢出

$n$ 位无符号数的范围为

$$0\le N\le 2^n-1$$

电路只保留最低 $n$ 位（尾款）：

$$N_{\mathrm{存}}=N_{\mathrm{实际}}\mathrm{mod}{2}^n$$

溢出=取模

超出 $n$ 位位宽的溢出相当于对 $2^n$ 取模

---

计算机中数的表示方法

原码

原码最高位表示符号，其余位表示绝对值：
$[+X{]}_{\mathrm{原}}=0|X|,[-X{]}_{\mathrm{原}}=1|X|$

补码

正+用0，负-用1
$-(2^{n-1}-1)\le X\le 2^{n-1}-1$

• 原码有正零 $0000$、负零 $1000$。
• 同号相加，异号比较绝对值后相减，运算器实现复杂

补码

若 $A+B=M$，则 $A$、$B$ 以 $M$ 为模互补：

$$X-A=X-(M-B)\equiv X+B(\mathrm{mod}M)$$

对 $n$ 位二进制系统，$M=2^n$。减法可转化为加上减数的补码

$$[X{]}_{\mathrm{补}}=\{\begin{array}{ll}X,& 0\le X\le 2^{n-1}-1\\ 2^n+X,& -2^{n-1}\le X<0\end{array}$$

补码

负数变换规则：符号位不变，数值位取反 (得到1111)，再在最低位加 1。
$-2^{n-1}\le X\le 2^{n-1}-1$

例： $[+73{]}_{\mathrm{补}}=01001001$，$[-73{]}_{\mathrm{补}}=10110111$。

• 补码只有一个零 $0000$

补码加减

$$[X+Y{]}_{\mathrm{补}}=([X{]}_{\mathrm{补}}+[Y{]}_{\mathrm{补}})\mathrm{mod}{2}^n$$ $$[X-Y{]}_{\mathrm{补}}=([X{]}_{\mathrm{补}}+[-Y{]}_{\mathrm{补}})\mathrm{mod}{2}^n$$

反码

• 正数反码与原码相同。

• 负数反码：原码的数值位逐位取反，符号位不变

• 反码有正零、负零：$[+0{]}_{\mathrm{反}}=00\cdots 0$，$[-0{]}_{\mathrm{反}}=11\cdots 1$。

• 反码的运算

  • 符号位和数值位一起参加运算。
  • 若符号位产生进位，应把该进位加回最低位，循环进位
    $[X+Y{]}_{\mathrm{反}}=[X{]}_{\mathrm{反}}+[Y{]}_{\mathrm{反}}$
    $[X-Y{]}_{\mathrm{反}}=[X{]}_{\mathrm{反}}+[-Y{]}_{\mathrm{反}}$

原码、反码与补码

项目	原码	反码	补码
正数	与真值二进制相同	与原码相同	与原码相同
负数	符号位为 1，数值位为绝对值	原码数值位取反	原码数值位取反再加 1
零的数量	2	2	1
$n$ 位最小值	$-(2^{n-1}-1)$	$-(2^{n-1}-1)$	$-2^{n-1}$
加法	需判断符号	循环进位	直接按二进制相加

位宽

位宽	无符号数	补码有符号数
8 位	$0\sim 255$	$-128\sim 127$
16 位	$0\sim 65535$	$-32768\sim 32767$

• 同一比特模式可有不同解释：${\mathrm{FFFFFFFF}}_{16}$ 作为 32 位无符号数为 $4294967295$，作为补码有符号数为 $-1$。

---

计算机中的码

定点数与浮点数

• 定点数（Fixed Point）：小数点位置固定，且不占存储位。

  • 定点纯整数：小数点隐含在最低位右侧。
  • 定点纯小数：小数点隐含在最高数值位左侧。

• 浮点数（Floating Point）：

$$X=\pm 2^p\times x$$

- 阶码 $p$ 决定数值范围。
- 尾数 $x$ 的位数决定有效精度。

BCD 码

若要表示 $N$ 种信息，所需二进制位数 $n$ 满足

$$2^n\ge N$$

BCD（Binary-Coded Decimal）：用四位二进制代码表示一位十进制数字字符。

十进制数	8421 码	2421 码	余 3 码	余 3 循环码
0	0000	0000	0011	0010
1	0001	0001	0100	0110
2	0010	0010	0101	0111
3	0011	0011	0110	0101
4	0100	0100	0111	0100
5	0101	1011	1000	1100
6	0110	1100	1001	1101
7	0111	1101	1010	1111
8	1000	1110	1011	1110
9	1001	1111	1100	1010

• 8421、2421 码是有权码。
• 余 3 码、余 3 循环码是无权码。
• $n$ 位十进制数的 BCD 占 $4n$ 位。

8421 BCD 加法

每一位十进制数单独相加，先按普通二进制加。

8421 BCD 中，只有 $0000\sim 1001$ 表示十进制 $0\sim 9$。

若相加结果超过 $1001$，或有进位，就加 $0110$；产生的进位传给高一位。

格雷码

• 无权码。
• 相邻代码只有一位不同，适合模拟量转换。
• 不能直接进行算术运算。

字符编码

• ASCII：表示英文字母、数字、标点和控制字符；标准 ASCII 使用 7 位，共 128 个码位。
• Unicode：为字符分配统一码点。
• UTF-8：把 Unicode 码点编码为 1~4 个字节；ASCII 字符的 UTF-8 编码与 ASCII 相同。

检错码与纠错码

• 码重 $w(I)$：码字 $I$ 中 1 的个数。
• 码距 $d(I,J)$：两个码字对应位置不同的个数。
• 最小码距 $d_{\min }$：任意两个有效码字之间的最小距离。

$$I=11101100,J=11000100$$ $$w(I)=5,w(J)=3,d(I,J)=2$$

最小码距的检错、纠错能力

能力	原理	最小码距条件
检错 $s$ 位	若错误不超过 $s$ 位，就不能把 $C$ 直接变成 $C^{\prime }$，所以要有 $s<d_{\min }$。	$d_{\min }\ge s+1$
纠错 $t$ 位	每个有效码字周围半径 $t$ 的纠错区域不能重叠，故 $t+t<d_{\min }$。	$d_{\min }\ge 2t+1$
纠错 $t$ 位并检错 $s$ 位，$s\ge t$	至多 $s$ 位错误不能落入另一个码字半径 $t$ 的纠错区域，故 $s+t<d_{\min }$	$d_{\min }\ge t+s+1$

奇偶校验码

奇偶校验码由信息位和一个校验位(表示奇偶校验)组成：

• 偶校验：使码字中 1 的总数为偶数；
• 奇校验：使码字中 1 的总数为奇数。

奇偶校验的能力

奇偶校验的 $d_{\min }=2$。它能发现任意奇数个位翻转，不能发现偶数个位翻转；只能检错，不能定位或纠错。

五中取二码

五中取二码的每个有效码字有 5 位，且恰好两位为 1：

$$w(C)=2$$

有效码字总数为$\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$，恰好可映射到十进制的 0~9。

海明码

纠错码

略