字符编码

ASCII

7位二进制编码，占用1个字节

字符数：128

UTF-8

有效位数 字节1 字节2 字节3 字节4 字节5 字节6
7 0ddddddd / / / / /
11 110ddddd 10dddddd / / / /
16 1110dddd 10dddddd 10dddddd / / /
21 11110ddd 10dddddd 10dddddd 10dddddd / /
26 111110dd 10dddddd 10dddddd 10dddddd 10dddddd /
31 1111110d 10dddddd 10dddddd 10dddddd 10dddddd 10dddddd

好处：

  • 变长编码
  • 字符长度由首字节确定
  • 可以自同步（首字节一定不同于后续字节！）
  • 可扩展性强

字体表示

  • 点阵字体
  • 矢量字体

数值表示

整数（定点数）

  • 正数：全部相同
  • 原码：符号位为1，后跟绝对值
  • 反码：x_neg = ~(x_pos)
  • 补码：x_neg = ~(x_pos) + 1

需要知道的内容：零扩展/符号扩展、大端/小端

浮点数 IEEE 754 标准

符号位$s$、阶码exp、尾数frac

v=(−1)sM2Ev = (-1)^s M 2^E
类型 阶码 尾数 $E$ $M$
非规格化数 全0 任意 1 - Bias 0.frac
规格化数 不是全0或全1 任意 exp - Bias 1.frac
无穷大 全1 全0 / /
NaN 全1 非全0 / /

其中Bias为偏置量2k−1−12^{k-1}-1，其中kk为阶码位数

简单的记忆方式：最小有效阶码00和最大有效阶码2k−22^k-2的平均数

浮点数运算的基本方法

  1. 计算阶码
  2. 尾数移位（仅加减法）
  3. 计算尾数
  4. 规格化
  5. 舍入，可能再次进行规格化
  6. 进行阶码溢出检查

浮点数的特点

  • 加法不可结合
  • “判等”不完全可信

检验纠错码

码距（最小码距）：合法码之间最小的二进制位差异数目

码距为1的编码没有纠错能力

奇偶校验码

增加一位使1为奇(偶)数个

海明校验码

动机：k个数据位和r个校验位，使得k+r位中任何一位出错可以发现并改正，任何两位同时出错可以发现，但不能改正

思路：保证每个数据位对应不同的校验位组合

于是有，2r≥k+r+12^r\geq k+r+1（为什么+1？因为r位全部正确的情形不能用来表示错误）

增加一位用以区分一位错和两位错：2r−1≥k+r2^{r-1}\geq k+r

海明码实现方案

校验位安排

  • 数据位、校验位从1开始统一编号
  • 在1、2、4、8、…位放置校验位
  • 预留一位校验位作为总校验位放在最后

如对k=3,r=4k=3, r=4，排序为

P1P2D1P3D2D3P4P_1 P_2 D_1 P_3 D_2 D_3 P_4

其中$P_4$为总校验位

校验位组合

  • 将数据位的编号写成2的幂的和
  • 校验位为所有含有此2的幂的数据位的异或
  • 总校验位为其他所有位的异或

对上面的例子，有

P1=D1⊕D2P_1 = D_1 \oplus D_2 P2=D1⊕D3P_2 = D_1 \oplus D_3 P3=D2⊕D3P_3 = D_2 \oplus D_3 P4=D1⊕D2⊕D3⊕P1⊕P2⊕P3P_4 = D_1 \oplus D_2 \oplus D_3 \oplus P_1 \oplus P_2 \oplus P_3

译码方案

  • 计算S位：把校验位和对应的位异或
  • 若S位含1则出现错误
S1=P1⊕D1⊕D2S_1 = P_1 \oplus D_1 \oplus D_2 S2=P2⊕D1⊕D3S_2 = P_2 \oplus D_1 \oplus D_3 S3=P3⊕D2⊕D3S_3 = P_3 \oplus D_2 \oplus D_3 S4=P4⊕D1⊕D2⊕D3⊕P1⊕P2⊕P3S_4 = P_4 \oplus D_1 \oplus D_2 \oplus D_3 \oplus P_1 \oplus P_2 \oplus P_3

若至多两位出错，则S位分为以下三种情况：

  • 四位S全为零，则无错
  • S4S_4为1，其他不全零，则一位错，其他三位对应2的幂求和的位置即为出错的位
  • S4S_4为0，其他不全零，则两位错

海明码的码距为4