Coding and Error Checking of Binary Data

    Mar 15, 2024

    Concepts of Sign-Magnitude, One's Complement, Two's Complement, and Excess-n Notation, along with Parity Check and Hamming Code Error Detection Methods for Binary Data

    Coding Methods

    There are four ways to represent binary data in computers: sign-magnitude, one's complement, two's complement, and excess-n notation. These methods are used to represent and process signed numbers in computers, each solving the problems encountered when using binary to represent signed numbers.

    1. Sign-Magnitude:

      Sign-magnitude was the earliest method used for representation. The highest bit represents the sign, while the remaining bits represent the magnitude. However, sign-magnitude has a problem: there are two representations for zero, positive zero and negative zero. Moreover, special processing is required to compare the results of addition and subtraction, which adds complexity to operations and comparisons.

      The main advantage of sign-magnitude is its simplicity, but the problem of representing zero makes it inconvenient for practical applications.

    2. One's Complement:

      To address the issue of the sign bit in sign-magnitude representation, one's complement was introduced. In one's complement, the representation of negative numbers is obtained by taking the complement of each bit of the corresponding positive number. Therefore, addition and subtraction operations for two one's complement numbers can be unified as addition operations, with the sign bit participating in the operation, and the sign bit of the result being determined by the operation.

      One's complement solves the problem of the sign bit in sign-magnitude representation. However, when performing addition and subtraction operations, the issue of positive zero and negative zero still needs to be considered.

    3. Two's Complement:

      To address the issue of positive and negative zero in one's complement representation, two's complement was introduced. In two's complement, all bits are complemented based on one's complement representation, and then 11 is added.

      Since there is only one representation for zero in two's complement, the problem of positive and negative zero is avoided during operations.

    4. Excess-N Notation (Bias): Excess-N notation is commonly used to represent the exponent part of floating-point numbers. Excess-N notation is introduced to enable direct comparison of floating-point numbers with integers without the need for additional operations.

      Excess-N notation sets a bias value to represent unsigned integers as signed integers, enabling direct comparison with integers and simplifying the comparison process.

    These different representation methods exist to more effectively represent and process signed numbers within a limited number of bits, while keeping operations and comparisons simple and efficient. The choice of representation method depends on specific application requirements and hardware design considerations.

    Below, we will introduce their specific representation methods and calculation methods, assuming the binary number is X(2)X_{(2)}, and the machine's word length is nn.

    Sign-Magnitude Representation

    • If XX is a pure integer
      • When it is positive, the highest bit is 00, and the remaining n1n-1 bits are X(2)X_{(2)}.
      • When it is negative, the highest bit is 11, and the remaining n1n-1 bits are X(2)X_{(2)}.
    • If XX is a pure fraction
      • When it is positive, the highest bit is 00, and the remaining n1n-1 bits are X(2)X_{(2)}.
      • When it is negative, the highest bit is 11, and the remaining n1n-1 bits are X(2)X_{(2)}.
    • If XX is 00, there are two representations: +0+0 and 0-0.
    • Addition rule: First, determine the sign bit. If the signs are the same, add the absolute values, and the sign of the result remains unchanged; if the signs are different, perform subtraction, and the sign of the result is the same as the sign of the absolute value of the larger number.
    • Subtraction rule: Subtracting two numbers represented by sign-magnitude, first negate the sign of the subtrahend, then perform sign-magnitude addition on the minuend and the negated subtrahend. (Subtract numbers with the same sign; add numbers with different signs)

    One's Complement Representation

    • If XX is a pure integer
      • When it is positive, the highest bit is 00, and the remaining n1n-1 bits are X(2)X_{(2)}.
      • When it is negative, take the complement of each bit of X(2)X_{(2)}.
    • If XX is a pure fraction
      • When it is positive, the highest bit is 00, and the remaining n1n-1 bits are X(2)X_{(2)}.
      • When it is negative, take the complement of each bit of X(2)X_{(2)}.
    • If XX is 00, there are two representations: +0+0 and 0-0.
    • Addition and subtraction: [X+Y]=[X]+[Y],[XY]=[X]+[Y][X+Y] = [X] + [Y],[X-Y] = [X] + [-Y]. The sign bit is considered as part of the number, and any carry generated by the sign bit is discarded.

    Two's Complement Representation

    • If XX is a pure integer
      • When it is positive, the highest bit is 00, and the remaining n1n-1 bits are X(2)X_{(2)}.
      • When it is negative, the highest bit is 11, and the remaining n1n-1 bits are X+1(2)X + 1_{(2)}.
    • If XX is a pure fraction
      • When it is positive, the highest bit is 00, and the remaining n1n-1 bits are X(2)X_{(2)}.
      • When it is negative, the highest bit is 11, and the remaining n1n-1 bits are X+1(2)X + 1_{(2)}.
    • If XX is 00, there is only one representation, for example, when n=8n=8, it is 0000000000000000.
    • Addition and subtraction: [X+Y]=[X]+[Y],[XY]=[X]+[Y][X+Y] = [X] + [Y],[X-Y] = [X] + [-Y]. The sign bit is considered as part of the number, and any carry generated by the sign bit is discarded.

    Excess-N Notation (Bias)

    A bias value of (2n1)(2)(2^{n-1})_{(2)} is set.

    • If XX is a pure integer, it is X(2)+(2n1)(2)X_{(2)} + (2^{n-1})_{(2)}.
    • If XX is a pure fraction, it is X(2)+1(2)X_{(2)} + 1_{(2)}.
    • If XX is 00, there is only one representation, for example, when n=8n=8, it is 1000000010000000.
    • In fact, when the bias value is (2n1)(2)(2^{n-1})_{(2)}, only the complement of the highest bit of the two's complement needs to be taken, to obtain the corresponding excess-n notation representation. In other words, the highest bits of the two's complement and excess-n notation are each other's complements.
    • Addition and subtraction operations are the same as two's complement.

    Fixed-Point Numbers

    For fixed-point numbers, the decimal point is after the lowest bit. For fixed-point fractions, if there is a

    sign bit, the decimal point is after the sign bit; if there is no sign bit, the decimal point is before the highest bit.

    Among the above representation methods, for fixed-point integers,

    • The representation range of sign-magnitude and two's complement is [(2n11),2n11][-(2^{n-1}-1),2^{n-1}-1].
    • The representation range of two's complement and excess-n notation is [2n1,2n11][-2^{n-1},2^{n-1}-1].
    • They can both represent 2n2^{n} numbers.

    For fixed-point fractions,

    • The representation range of sign-magnitude and two's complement is [(12(n1)),12(n1)][-(1-2^{-(n-1)}),1-2^{-(n-1)}].
    • The representation range of two's complement and excess-n notation is [(12(n1)),12(n1)][-(1-2^{-(n-1)}),1-2^{-(n-1)}].
    • They can both represent 2n12^{n-1} numbers.

    Floating-Point Numbers

    Floating-point numbers are represented by exponent EE and mantissa FF, where the exponent is represented by RR bits of excess-n notation, and the mantissa is represented by MM bits of two's complement. The binary number 2EF2^{E} * F can be expressed.

    The range that can be expressed is [2(2R1),(12M+1)(2(2R1))][-2^{(2^R-1)},(1-2^{-M+1})*(2^{(2^R-1)})].

    Error Checking Codes

    Parity Check

    Parity check refers to adding 11 to the check bit so that the number of 11s in the binary number is odd. The same applies to even parity. However, odd parity can only detect coding errors in odd-numbered bits, and cannot detect coding errors in even-numbered bits. Even parity is the same.

    Hamming Code

    Hamming codes insert kk check bits into nn bits of binary data. And satisfy 2k1n+k2^{k}-1≥ n+k.

    Taking the checked data 11001100 as an example, first determine the position of the check bits, and use the above formula to determine that k=3k=3. Calculate the positions of the check bits using 2i,i=0,1,2,32^{i},i =0,1,2,3. These are the subscripts of the Hamming code check bits. Write down the binary representations of these subscripts.

    124
    001001010010100100

    Then use * to replace 00 in the above table to use as a wildcard.

    124
    1**11*1*11**

    Write down the binary sequence from 11 to n+kn+k, which is from 11 to 4+3=74+3=7.

    DecimalBinary
    11001001
    22010010
    33011011
    44100100
    55101101
    66110110
    77111111

    Then use the wildcard table to match the numbers.

    124
    1**11*1*11**
    001(1)001(1)010(2)010(2)100(4)100(4)
    011(3)011(3)011(3)011(3)101(5)101(5)
    101(5)101(5)110(6)110(6)110(6)110(6)
    111(7)111(7)111(7)111(7)111(7)111(7)

    Then, the Hamming code table to be determined is obtained.

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

    Therefore, we can determine that

    • H1H_{1} is responsible for the parity check of bits 1,3,5,71,3,5,7.
    • H2H_{2} is responsible for the parity check of bits 2,3,6,72,3,6,7.
    • H4H_{4} is responsible for the parity check of bits 4,5,6,74,5,6,7.

    Now, let's determine the values of H1,H2,H4H_{1},H_{2},H_{4}. If it is even parity:

    • H3,H5,H7H_{3},H_{5},H_{7}, the number of 11s is odd, so H1=1H_{1}=1.
    • H3,H6,H7H_{3},H_{6},H_{7}, the number of 11s is even, so H2=0H_{2}=0.
    • H5,H6,H7H_{5},H_{6},H_{7}, the number of 11s is even, so H4=0H_{4}=0.

    If it is odd parity, simply take the complement of the above check bits.

    Finally, the complete Hamming code is obtained.

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

    To check for errors, simply perform XOR operations on the check bits and the bits to be checked:

    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})

    If even parity is used, G3G2G1G_{3}G_{2}G_{1} should be 000000, and for odd parity, it should be 111111. If it is not all 00 or 11, an error has occurred, and the data bit corresponding to the error should be flipped.