[一 数制和编码](#一 数制和编码)

[二 定点数](#二 定点数)

一 数制和编码

1.数制相互转换

2.BCD码

3.字符与字符串

4.校验码

• 奇偶校验
• 海明码
• 循环冗余校验码

1.数制相互转换

1.1 r进制到十进制

1.2 二进制到八进制、十六进制

1.3 十进制到r进制

2.BCD码

3.字符与字符串

3.1 字母存储

3.2 汉字存储

4.校验码

4.1 奇偶校验

4.2 海明码

4.2.1 求解步骤

（1）确定校验码位数

• \(2^k\ge n+k+1（n+k为任何一位都可能出错，还有1种正确状态）\)
• n个信息位；k个校验位，校验码有\(2^k\)种状态;

（2）确定校验码位置

• \(P_i\)放在\(2^{i-1}\)的位置上，其余按顺序

• 信息位\(D_4D_3D_2D_1（1010）\)，校验位\(P_3P_2P_1\)，海明码为\(H_7H_6H_5H_4H_3H_2H_1\)

  

（3）求校验位的值

• 由\(H_i\)位置\(i\)算出对应的二进制码

• 从右到左按列\(h\)观察，选出所有为1的\(H_i\)。找出\(H_i\)对应的信息位\(D_j\)，对所有\(D_j\)进行异或运算，则可得出对应的\(P_h\)

  

（4）纠错

• 对校验方程进行计算

• 若出现偶校验错误，将结果\(S_3S_2S_1\)转为十进制，对应位置即为错误位置

  

4.2.2 检错与纠错

• 检错能力：2；纠错能力：1

• 全体校验

  当两个跳变时，无法根据对应的位置确定它就是出错位。即上面无法区别是1位错还是2位错。所以引入全校验位，在最后面加上\(P_全\)，该值是由原始数据得出偶校验码。

  现在对传输的数据进行一次全体偶校验进行分析

  

4.3 循环冗余校验码

CRC。数据发送、接受方约定一个“除数”，保证余数为0

4.3.1 求CRC码

（1）确定长度与二进制码

• 信息码长度K；
• 校验码R=生成多项式最高次幂；
• 校验码位数N=K+R
• 二进制码：生成多项式的系数

（2）由模2除法求CRC码

• 信息码低位补R个0（右侧）
• 模2除法
  • 被除数：信息位+R个0
  • 除数：二进制码
  • 除的时候看最高位作为商，减的时候用异或运算。
  • 余数比被除数少一位，余数结果为校验位
• CRC码：信息位+校验位

4.3.2 检错与纠错

• 示例

  

• 检错：

  可检测出所有奇数个错误；

  可检测出所有双比特的错误；

  可检测出所有小于等于校验位长度的连续错误；

• 纠错：

  K个信息位，R个校验位，若生成多项式选择得当，且 \(2^R\ge K+R+1\)，CRC码可纠正1位错。

二 定点数

1.定点数的表示

2.定点数运算

• 补码作用
• [移位运算](#2.2 移位运算)
• [加法运算](#2.3 加减运算)

1.定点数的表示

表示范围

2.定点数运算

2.1 补码作用

减法换加法，减少硬件成本（ALU无需集成减法器）

\(带余除法：\\x=qm+r\\x~mod~12=r\\（q为整数，r为余数，m为模。类似周期，即要在r相等的情况下找到x）\)

• 模余数相同的数是同一类，等价。即可知-3和9在模12的条件下是等价的。
• 互为补数：两个数的绝对值=模。减去一个数即加上这个数的补数。也就是\(10+(-3)\)可转换成\(10+9\)再取模。
• 而计算机是以\(2^8(1,00000000)\)为模的，[a]补=模-|a|=全部取反再+1

2.2 移位运算

2.2.1 算数移位

补码的算数移位

• 正数和原码一致

• 由于负数补码=反码末位+1。所以反码最右边连续的1会因进位变成0，直到第一个0。故负数补码最右边的1及其右边与原码一致。而其左边与反码一致。所以造成了：

  • 右移（同反码）：高位补1，低位舍弃。
  • 左移（同原码）：低位补0，高位舍弃。

加法举例

2.2.2 逻辑移位

RGB值例子：例如用3B储存102、139、133

102的二进制数储存进去并向左移动16位

139的二进制数储存进去并向左移动8位

133的二进制数储存进去

相加得3B的RGB值

2.2.3 循环移位

2.3 加减运算

2.3.1 溢出判断

• 方法一：一位符号位

  \[V=AB\overline{S}+\overline{AB}S\\加数的符号位为：A、B；结果的符号位S：（乘法表示与，加法表示或） \]

• 方法二：一位符号位，根据进位情况判断

  \[V=C_1\oplus C_s\\ 结果的最高数值位的进位：C_1；符号位的进位：C_s； \]

• 方法三：双符号位

  \[V=S_{s1}\oplus S_{s2}\\正数符号位：00；负数符号位11;\\结果的两个符号位分别是S_{s1}S_{s2} \]

  ==>V=0无溢出；V=1溢出

2.3 乘法运算

乘数从左到右依次乘以被乘数，每次都要错位

• 原码一位乘法

  符号位进行异或运算

  数值位取绝对值进行乘法运算

  ACC乘积高位

  MQ乘数、乘积低位

  X被乘数

  ACC置0

  MQ最右一位开始：1-》ACC+被乘数；0-》ACC加上0

  通过ALU，结果放在ACC寄存器

  ACC MQ逻辑右移。之后运算过程像上面一样

  部分积：逻辑右移后放在MQ的位

  重复数值位n次

  结果：ACC与MQ组合，第一位为符号位，后面为小数部分

  处理符号位

  对于整数的，符号位是最右边的一位

  ---n论加法，移位

  --根据MQ最低位确定加什么。加法可能是+0、+[x]原码

• 补码一位乘法

  n轮加法，移位，再一次加法

  --根据MQ最低位和辅助位确定加什么。

  ​ 辅助位-最低位=1----+0

  ​ 辅助位-最低位=0----+[x]补

  ​ 辅助位-最低位=-1----+[-x]补

  --算数右移

  --正负不用异或约定