数据的表示和运算

定点数的表示(原码、反码、补码)

浮点数的表示

其他编码(格雷码、循环码、ASCII码、汉字编码)

检错和纠错

奇偶校验位

表示给定位数的 二进制数中1的个数是奇数还是偶数 的二进制数。奇偶校验位是最简单的错误检测码。

奇偶校验位有两种类型:偶校验位与奇校验位。

如果一组给定数据位中1的个数是奇数,那么偶校验位就置为1,从而使得1的个数是偶数。如果给定一组数据位中1的个数是偶数,那么奇校验位就置为1,使得总的1的个数是奇数。

偶校验实际上是循环冗余校验的一个特例,通过多项式 x + 1 得到1位CRC。

错误检测

如果传输过程中包括校验位在内的 奇数个数据位发生改变 ,那么奇偶校验位将出错表示传输过程有错误发生。因此,奇偶校验位是一种错误检测码,但是由于 没有办法确定哪一位出错 ,所以它不能进行错误校正。发生错误时必须扔掉全部的数据,然后从头开始传输数据。在噪声很多的媒介上成功传输数据可能要花费很长的时间,甚至根本无法实现。但是奇偶校验位也有它的优点,它是 使用一位数据能够达到的最好的校验码 ,并且它仅仅需要一些异或门就能够生成。参见汉明码中关于其它错误校正码的描述。

奇偶校验块

一些冗余磁盘阵列(RAID)使用奇偶校验块实现冗余。如果阵列中的一块磁盘出现故障,工作磁盘中的数据块与奇偶校验块一起来重建丢失的数据。

下面的图表每列表示一个磁盘,假设A1 = 00000111、A2 = 00000101以及A3 = 00000000。A1、A2、A3 异或得到的Ap等于00000010。如果第二个磁盘出现故障,A2将不能被访问,但是可以通过A1、A3与Ap的异或进行重建。

      冗余磁盘阵列
A1        A2        A3
Ap        B1        B2
Bp        C1        C2
C3        C4        Cp

(注意:数据块是格式A#,奇偶校验块是Ap。)

引申

汉明码
TODO
逻辑异或
又称互斥或(exclusive or),当两两数值相同为否,而数值不同时为真。
// 使用异或运算交换两个 int 类型变量的数值。
// 依据是异或运算的自反性 A^B^B = A^0 = A
public void switch(int &a, int &b){
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}
CRC 循环冗余校验

循环冗余校验 CRC

循环冗余校验(英语:Cyclic redundancy check,通称“CRC”)是产生简短 固定位数 校验码的一种散列函数,一般来说,循环冗余校验的值都是32位的整数。

校验码是是两个字节数据流采用 二进制除法 (没有进位,使用XOR来代替减法)相除所得到的余数。其中 被除数 是需要计算校验和的 信息数据流 的二进制表示;除数是一个 长度为 (n+1) 的预定义(短)的二进制数 ,通常用多项式的系数来表示。为了得到CRC,我们首先将其乘以 \(x^n\) ,这里 n 是一个固定多项式的阶数,然后再将其除以这个固定的多项式,余数的系数就是校验码。一般形式:

\[M(x) \cdot x^{n}=Q(x) \cdot K(x) - R(x)\]

这里M(x)是原始的信息多项式。K(x)是n阶的“钥匙”多项式。 \(M(x) \cdot x^{n}\) 表示了将原始信息后面加上 n 个0。R(x)是余数多项式,即是CRC“校验和”。在通信中,发送者在原始的信息数据M后附加上n位的R(替换本来附加的0)再发送。接收者收到M和R后,检查 \(M(x)\ cdot x^{n}+R(x)\) 是否能被 K(x) 整除。如果是,那么接收者认为该信息是正确的。值得注意的是 \(M(x)\cdot x^{n}+R(x)\) 就是发送者所想要发送的数据。这个串又叫做 codeword.

例子

\[{\frac {(x^{3}+x^{2}+x)}{(x+1)}}=(x^{2}+1)-{\frac {1}{(x+1)}}\]
\[(x^{2}+x+1)x=(x^{2}+1)(x+1)-1\]

在上面的等式中, \(x^{2}+x+1\) 表示了本来的信息位是 111 , x+1 是所谓的钥匙,而余数 1`(也就是 :math:`x^{0} )就是CRC. key的最高次为1,所以我们将原来的信息乘上 \(x^{1}\) 来得到 \(x^{3}+x^{2}+x\) ,也可视为原来的信息位补1个零成为 1110

引申

二进制除法
TODO
除数和被除数
c = a / b 中,a 为被除数,b 为除数。

汉明距离 (Hamming distance, 码距)

在信息论中, 两个等长字符串 之间的汉明距离(英语:Hamming distance)是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

对于二进制字符串a与b来说,它等于a 异或b以后所得二进制字符串中“1”的个数。

不足:如果要比较两个不同长度的字符串,不仅要进行替换,而且要进行插入与删除的运算,在这种场合下,通常使用更加复杂的编辑距离等算法。

Wikipedia 汉明距离

汉明码 (Hamming code)

简单的奇偶检验码除了不能纠正错误之外,也只能侦测出奇数个的错误。

汉明码是一种线性 纠错码 。在一个7位的信息中,单个位出错有7种可能,因此3个错误控制位就足以确定是否出错及哪一位出错了。

下列通用算法可以为任意位数字产生一个可以 纠错一位 (Single Error Correcting)的汉明码。

  1. 从1开始给数字的数据位(从左向右)标上序号, 1,2,3,4,5…

  2. 将这些数据位的位置序号转换为二进制,1, 10, 11, 100, 101,等。

  3. 数据位的 位置序号中所有为二的幂次方的位(编号1,2,4,8,等,即数据位位置序号的二进制表示中只有一个1)是校验位

  4. 所有其它位置的数据位(数据位位置序号的二进制表示中至少2个是1)是数据位

  5. 每一位的数据包含在特定的两个或两个以上的校验位中,这些校验位取决于这些数据位的位置数值的二进制表示

    • 校验位1覆盖了所有数据位位置序号的二进制表示倒数第一位是1的数据:1(校验位自身,这里都是二进制,下同),11,101,111,1001,等
    • 校验位2覆盖了所有数据位位置序号的二进制表示倒数第二位是1的数据:10(校验位自身),11,110,111,1010,1011,等
    • 校验位4覆盖了所有数据位位置序号的二进制表示倒数第三位是1的数据 :100( 校验位自身 ),101,110,111,1100,1101,1110,1111,等
    • 校验位8覆盖了所有数据位位置序号的二进制表示倒数第四位是1的数据:1000(校验位自身),1001,1010,1011,1100,1101,1110,1111,等
    • 简而言之,所有校验位覆盖了数据位置和该校验位位置的二进制与的值不为0的数。

采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些,但在实践中并没有区别。

校验位一般的规律可以如下表示:

表中只给出了20个编码后的位(5个奇偶校验位,15个数据位)。观察上表可发现一个比较直观的规律:第i个检验位是第2i-1位,从该位开始,检验2i-1位,跳过2i-1位……依次类推。例如上表中第3个检验位p4从第23-1=4位开始,检验4、5、6、7共4位,然后跳过8、9、10、11共4位,再检验12、13、14、15共4位……

要检查某一位的错误,则需检查某一位所包含的所有奇偶校验位。这种错误的模式被叫做伴随式错误。如果所有奇偶校验位是正确的,就没有错误。除此以外的情况,错误的奇偶校验位的位置的和将识别错误的位。例如,如果位置为1、2、8的奇偶校验位指示了一个错误,那么位置为1+2+8=11的位出错了。如果只有一个奇偶校验位指示了错误,那么该奇偶校验位自身出错了。

例子

对11000010进行汉明编码,求编码后的码字。

1.列出表格,从左往右(或从右往左)填入数字,但2的次方的位置不填。

位置      1       2       3       4       5       6       7       8       9       10      11      12      13      14
数据                      1               1       0       0               0       0       1       0
2.把数据行有1的列的位置写为二进制。

位置      1       2       3       4       5       6       7       8       9       10      11      12      13      14
数据                      1               1       0       0               0       0       1       0
二进制                     0011            0101                                            1011
3.收集所有二进制数字,求异或。 {\displaystyle 0011\oplus 0101\oplus 1011=1101} 0011\oplus 0101\oplus 1011=1101

4.把1101依次填入表格中2的次方的位置(低位在左)。

位置      1       2       3       4       5       6       7       8       9       10      11      12      13      14
数据                      1               1       0       0               0       0       1       0
二进制                     0011            0101                                            1011
校验      1       0               1                               1

5.所以编码后的码字是101110010010。

引申

完备码
码率