机内代码集运算
zKing 2018-11-19 专业知识
# 数的进制
- 二进制
- 十进制
- 八进制
- 十六进制
# 原码、反码、补码、移码（增码）
# 带符号数的表示
通常的做法时约定一个数的最高位为符号位，若该为位0，则表示整数；若该位位1，则表示负数
# 原码
用最高位表示符号位，数值部分用二进制绝对值表示
# 反码
- 正数： X[ 原 ]=X[ 反 ]
- 负数： X[ 原 ] 除了符号位外，其他各位逐位取反
# 补码
- 正数： X[ 原 ]=X[ 补 ]
- 负数： X[ 原 ] 取得反码后，最后在末尾 +1
- 【X[ 补 ] 】[ 补 ] = X [ 原 ]
# 移码
- 无论正数、负数，在补码的基础上，对符号位取反。
- 一般用做浮点数的阶码，引入的目的时为了保证浮点数的机器零为全0
# 定点数和浮点数
# 定点数
- 定点整数
- 小数点的位置固定在最低位的右边，不占位
- 定点小数
- 小数点的位置固定在符号位与最高数值位之间，表示一个纯小数
# 浮点数
- 用类似科学计数法来表达，即
- N=M*（R的 e 次方）
- M 称为尾数，R 称为基数，e 为阶码（指数）
- 比如 1001.101 的规范浮点数表达式为 1.001101 x 2³
- 浮点数利用指数达到了浮动小数点的效果，从而灵活地表达更大范围的实数
# 校验码
# 编码体系
指一种编码方式中所有合法码字的集合
# 编码效率
合法码字占所有码字的比率
# 码距
- 一个编码系统中任意两个合法的编码之间的不同的二进制位的数目
- 该编码系统的任意两个编码之间的距离的最小值
- 码距时衡量一种编码方式的抗错误能力的一个指标
- 码距越大，抗错误能力越高
- 码距越小，抗错误能力越低
# 误码
数字信息在传输和存取的过程中，由于各种意外情况的发生，数据可能会发生错误
# 奇偶校验
# 奇校验
被传输的有效数据中“1”的个数是奇数个，校验位填“0”，否则填“1”
# 偶校验
被传输的有效数据中“1”的个数是偶数个，校验位填“0”，否则填“1”
# 总结
- 奇偶校验较简单，串口通信中使用奇偶校验作为数据校验的方法
- 使用一位奇偶校验的方法能够检测出一位错误，但无法判断是哪一位出错
- 当发生两位同事出错的情况时，奇偶校验也无法检测出来
- 所以，奇偶校验常用于对少量数据的校验，如一个字节
# 海明码（必考）
# 定义
- 海明码时奇偶校验的一种扩充。
- 和奇偶校验的不同之处在于海明码采用多位校验码的方式
- 海明码能够查错，也能纠错，但当出现两位错误时，海明码只能查错
- 表示：信息码和校验码组成
# 公式
- 可查出多少位错误
- 可以发现“≦ 码距 - 1 ”位的错误
- 可以纠正多少位错误
- 可以纠正“< 码距 / 2 ”位的错误
- 若能纠正 n 位错误，所需最小的码距应该是“ 2n+1 ”
# 原理
在数据中间加入几个校验码，码距均匀拉大，当某一位出错，会引起某个校验位的值发生变化
# 不等式
- 信息码个数为 m，校检码个数为k，可以表示 2 的 k 次方个信息
- 1 个信息用来表示“没有错误”，其余 2 的 k 次方 -1 个表示数据中存在错误
- 如果满足 2 的 k次方 -1 ≧ m +k
- 则在理论上 k 个校验码就可以判断是哪一位（包括信息码和校验码）出现了问题
# 编码规则
- 校验码依次放在第 2 的 i 次方位，其中，i=0,1,2,3....，其余位为信息位
- 从右往左进行放置校验码
- 公式
- B 为信息码和校验码组成后的列数，顺序从右往左，下标为1开始
- ⊕ 为异或，相同为假，相异为真
- 若校检码个数为 3，信息码个数为 4
- B1 =B3 ⊕ B5 ⊕ B7
- B2 =B3 ⊕ B6 ⊕ B7
- B4 =B5 ⊕ B6 ⊕ B7
- 若以上三个校验都成立，则说明没有出现错误
- 若不成立，说明有错，从三个方程式右边的值，可以判断哪一位出错
- 方法：从下往上看，组成二进制数，如：100，则说明是第4位出错
# CRC校验码（循环冗余校验码）（必考）
广泛地在网络通信及磁盘存储式采用
# 多项式
- 在循环冗余校验（CRC）码中，无一例外地要提到多项式的概念
- 一个二进制数可以以一个多项式来表示
- 如 1011 可以表示成 X³+X+1
- 多项式的最高幂次位 n，则转换位二进制数有 n+1 位
# 编码组成
- 海明码的校验位是嵌套的
- 循环冗余码式拼接的
- 编码的组成由 K 位信息码，加上 R 位的校验码（R 同时是多项式的最高幂次）
# 校验码的生成
- 将 K 位数据 C(x) 左移 R 位，给校验位留下空间，用 0 来补充，得到移位后的码 C1
- 将码 C1 除以 （生成多项式转换得到的二进制），得到 R 位的余数 【也可理解为异或运算】
- 该余数，即为校验码 M
- CRC码则由 信息码 C(x) 与 M 拼接而成
# 附加
- 循环冗余校验码的纠错能力取决于 K 值和 R 值。
- 在实践中，K 值往往取得非常大，远远大于 R 值，提高了编码效率，在这种情况下，CRC码只能检错而不能纠错
- 一般来说，R位生成多项式可以检测出所有双错、奇数位错和突发错位小于或等于 R 的突发错误