二进制数据的码制与校验 - NOTE & BLOG
    二进制数据的码制与校验
    15 March, 2024

    原码,反码,补码和移码的概念,以及奇偶校验、海明码的校验方法。

    码制

    计算机中的二进制数据有四种表达方式:原码、反码、补码和移码。都是计算机中用来表示和处理有符号数的方法,它们各自解决了在使用二进制表示有符号数时遇到的问题。

    1. 原码(Sign-Magnitude)

      原码最早的表示方法,最高位表示符号,其余位表示数值大小。但是原码存在一个问题,就是有两个表示零的数值,即正零和负零,还有,对于加减运算的结果还要比较两数大小做特殊处理,这增加了运算和比较的复杂性。

      原码的主要优点在于简单,但是由于表示零的问题,使得其在实际应用中不太方便。

    2. 反码(One's Complement)

      为解决原码表示中的加减结果符号的问题,引入了反码。在反码中,负数的表示方式是将对应正数的各个位取反得到的。所以,两个反码数的加减操作都可以统一为加法操作,符号位参与运算,得到结果的符号位。

      反码解决了原码表示中结果符号位的问题,但是在进行加减运算时,需要考虑到正零和负零的问题。

    3. 补码(Two's Complement)

      为解决反码表示中加减法运算的正负零的问题,引入了补码。补码的表示方法是在反码的基础上,将所有位取反后再加 11

      由于补码中的 00 只有一种表达方式,所以对于运算,可以避免正负零的问题。

    4. 移码(Bias or Excess-N): 在浮点数表示中,指数部分通常采用移码表示。移码是为了解决浮点数在比较大小时能够直接利用整数的大小比较,而不需要额外的运算。

      移码通过设置一个偏置值,将原本的无符号整数表示为有符号整数,使得其可以直接与整数进行比较大小,简化了比较的过程。

    这些不同的表示方法之所以存在,是为了在有限的位数内更有效地表示和处理有符号数,并且在进行运算和比较时保持简单和高效。不同的表示方法在不同的场景下有其各自的优缺点,选择合适的表示方法取决于具体的应用需求和硬件设计考量。

    下面分别介绍他们的具体表示方法和计算方式,假设二进制数为 X(2)X_{(2)},机器的字长为 nn

    原码表示

    • XX 为纯整数
      • 当为正数时,最高位为 00,剩余n1n-1X(2)X_{(2)}
      • 当为负数时,最高位为 11,剩余n1n-1X(2)X_{(2)}
    • XX 为纯小数
      • 当为正数时,最高位为 00,剩余n1n-1X(2)X_{(2)}
      • 当为负数时,最高位为 11,剩余n1n-1X(2)X_{(2)}
    • XX00,存在 +0+00-0 两种表示法。
    • 加法规则:先判断符号位,若相同,则绝对值相加,结果符号位不变;若不同,则做减法,绝对值大的数减去绝对值小的数,结果符号位与绝对值大的数相同。
    • 减法规则:两个原码表示的数相减,首先将减数的符号取反,然后将被减数与符号取反后的减数按原码加法进行运算。(同号求差,异号求和)

    反码表示

    • XX 为纯整数
      • 当为正数时,最高位为 00,剩余n1n-1X(2)X_{(2)}
      • 当为负数时,将 X(2)X_{(2)} 的绝对值按位取反。
    • XX 为纯小数
      • 当为正数时,最高位为 00,剩余n1n-1X(2)X_{(2)}
      • 当为负数时,将 X(2)X_{(2)} 的绝对值按位取反。
    • XX00,存在 +0+00-0 两种表示法。
    • 加减法:[X+Y]=[X]+[Y],[XY]=[X]+[Y][X+Y] = [X] + [Y],[X-Y] = [X] + [-Y]。符号位要作为数的一部分一起参加运算,符号位产生的进位要丢掉。

    补码表示

    • XX 为纯整数
      • 当为正数时,最高位为 00,剩余n1n-1X(2)X_{(2)}
      • 当为负数时,最高位为 11,剩余n1n-1X+1(2)X + 1_{(2)}
    • XX 为纯小数
      • 当为正数时,最高位为 00,剩余n1n-1X(2)X_{(2)}
      • 当为负数时,最高位为 11,剩余n1n-1X+1(2)X + 1_{(2)}
    • XX00,只有一种表示法,例如当 n=8n=8时,为 0000000000000000
    • 加减法:[X+Y]=[X]+[Y],[XY]=[X]+[Y][X+Y] = [X] + [Y],[X-Y] = [X] + [-Y]。符号位要作为数的一部分一起参加运算,符号位产生的进位要丢掉。

    移码表示

    规定偏移量为 (2n1)(2)(2^{n-1})_{(2)}

    • XX 为纯整数,则为 X(2)+(2n1)(2)X_{(2)} + (2^{n-1})_{(2)}
    • XX 为纯小数,则为 X(2)+1(2)X_{(2)} + 1_{(2)}
    • XX00,只有一种表示法,例如当 n=8n=8时,为 1000000010000000
    • 实际上,当偏移量为 (2n1)(2)(2^{n-1})_{(2)} 时,只需要将补码的最高位取反,即可得到对应的移码表示。 也就是说,移码和补码的最高位互为相反数。
    • 加法和减法的运算方式与补码相同。

    定点数

    定点整数的小数点在最低位之后。对于定点小数,若有符号位,则小数点在符号位之后,若无符号位,则小数点在最高位之前。

    以上表示方法中,对于定点整数,

    • 原码和补码的表示范围为:[(2n11),2n11][-(2^{n-1}-1),2^{n-1}-1]
    • 补码和移码的表示范围为:[2n1,2n11][-2^{n-1},2^{n-1}-1]
    • 它们都可以表示 2n2^{n} 个数

    对于定点小数,

    • 原码和补码的表示范围为:[(12(n1)),12(n1)][-(1-2^{-(n-1)}),1-2^{-(n-1)}]
    • 补码和移码的表示范围为:[(12(n1)),12(n1)][-(1-2^{-(n-1)}),1-2^{-(n-1)}]
    • 它们都可以表示 2n12^{n-1} 个数

    浮点数

    浮点数可以由阶码 EE 和尾数 FF 表示,其中阶码由 RR 位的移码表示,尾数由 MM 位的补码表示。则可以表达二进制数 2EF2^{E} * F

    能表达的范围为 [2(2R1),(12M+1)(2(2R1))][-2^{(2^R-1)},(1-2^{-M+1})*(2^{(2^R-1)})]

    校验码

    奇偶校验

    奇校验指的是在校验位上加 11 使得二进制数中所有 11 的个数位奇数。偶校验亦同理。但奇校验只能检测奇数位出错的编码,无法检测偶数位出错的编码。偶校验同理。

    海明码

    海明码在 nn 位二进制数据中插入 kk 个校验位。且满足 2k1n+k2^{k}-1≥ n+k

    以检验数据 11001100 为例,首先确定校验码的位置,利用以上公式得知 k=3k=3。依次使用 2i,i=0,1,2,32^{i},i =0,1,2,3计算得到校验码的位置为 1,2,41,2,4。这也是海明码校验位的下标。把这些下标的二进制写出来。

    124
    001001010010100100

    再用 * 代替上表中的 00 用于通配符。

    124
    1**11*1*11**

    再写出 11n+kn+k 的二进制序列,也就是 114+3=74+3=7

    十进制数二进制序列
    11001001
    22010010
    33011011
    44100100
    55101101
    66110110
    77111111

    然后用通配表通配以上数字

    124
    1**11*1*11**
    0011001(1)0102010(2)1004100(4)
    0113011(3)0113011(3)1015101(5)
    1015101(5)1106110(6)1106110(6)
    1117111(7)1117111(7)1117111(7)

    然后得出待定海明码表

    H7H_{7}H6H_{6}H5H_{5}H4H_{4}H3H_{3}H2H_{2}H1H_{1}
    1100

    因此我们可以确定

    • H1H_{1} 负责 1,3,5,71,3,5,7 位数的校验
    • H2H_{2} 负责 2,3,6,72,3,6,7 位数的校验
    • H4H_{4} 负责 4,5,6,74,5,6,7 位数的校验

    现在开始确定 H1,H2,H4H_{1},H_{2},H_{4}的校验位值。如果是偶校验:

    • H3,H5,H7H_{3},H_{5},H_{7}11的个数为奇数 因此H1=1H_{1}=1
    • H3,H6,H7H_{3},H_{6},H_{7}11的个数为偶数 因此H2=0H_{2}=0
    • H5,H6,H7H_{5},H_{6},H_{7}11的个数为偶数 因此H4=0H_{4}=0

    如果是奇校验,将以上校验位取反即可。

    最后得到完整的海明码

    H7H_{7}H6H_{6}H5H_{5}H4H_{4}H3H_{3}H2H_{2}H1H_{1}
    11110000000011

    检验错误,只需要将校验位与被校验位求异或运算

    G1=H1(H1H3H5H7)G2=H2(H2H3H6H7)G3=H4(H4H5H6H7)G_{1}=H_{1} \oplus (H_{1} \oplus H_{3} \oplus H_{5} \oplus H_{7}) \\ G_{2}=H_{2} \oplus (H_{2} \oplus H_{3} \oplus H_{6} \oplus H_{7}) \\ G_{3}=H_{4} \oplus (H_{4} \oplus H_{5} \oplus H_{6} \oplus H_{7})

    采用偶校验时 G3G2G1G_{3}G_{2}G_{1} 应当为 000000,奇校验应当为 111111。如果不全为 00 或者 11 ,那么对应的位置就发生了差错,将对应位置上的数据取反即可。

    凡有所学,皆成性格

    Share with the post url and description