Note that the first three entries of each column form the binary numbers 0 to 7. The message row vector, M, is defined as

where a, b, c, and d are the 4 message bits and the p's are parity bits to be defined. A received message vector is tested by forming the syndrome vector, S, defined by

To code a message, we set the parity bits such that S is identically 0 (mod 2); that is p4 + b + c+d<= 0

(The parity bits are located as indicated in Eq. (8-2) so that only one new parity bit is involved in each component of Eq. (8-4) and the message is easy to code.) When a message vector is received, the syndrome vector is calculated. If S = 0, we assume that no error occurred. If S4 = 1, we assume that a single error occurred and the binary number SiS2S3 gives the number of the component of M which is in error. If S4 = 0 and one or more of the other syndrome bits is I, then two bits of M are incorrect, and the error is detectable but uncorrectable. It is possible for errors in more than two bits to be undetected or incorrectly corrected.

To illustrate the above Hamming code, assume that we wish to send the message 1100. From Eq. (8-4) we choose the parity bits such that the 8-component message vector is 00111100. If an error occurs in bit 5 (counting the left-most as bit 0), then the received message is 00111000. The syndrome of the received message is 1011. Because S4=l, we assume there is a single error in bit 101=5 and the corrected message vector is 00111100, from which we extract our original message (1100) from bits 3, 5, 6, and 7.

If the probability of an error in any bit is 1%, then the probability of at least one error in a 4-bit message is approximately 4%. If a single parity bit is added, errors will occur in approximately 5% of the messages, which must then be discarded, and undetected errors in two message bits will occur in approximately 0.25% of the messages. If the 8-component Hamming code is used, errors in one bit which are then corrected will occur in approximately 8% of the messages. Errors in two of the message bits for which M must be discarded will occur in approximately 0.64% of the messages, and undetected errors in three or more bits will occur in approximately 0.05% of the messages. Thus, even simple error-correcting codes improve the amount of information correctly transmitted and reduce the probability of undetected errors.

Error-checking and self-correcting codes can be costly in terms of the number of bits required. Therefore, their use is justified only when the possibility of error is large. Because errors increase with transmission distance, these additional bits are frequently used for lunar and interplanetary missions. For an extended discussion of error-correcting codes, see Peterson and Weldon [1972] or Ryder [1967],

Often the natural binary code is used to represent a particular range of positive values, with a sign bit provided to allow representation of negative numbers. Normally, the sign bit is set to 0 for the positive values, although occasionally I is used. In either case, a negative number can be represented in natural binary or as either the one's or two's complement of the corresponding positive number. The one's complement is obtained by inverting every bit, i.e., changing each original 0 to 1 and each original 1 to 0. The two's complement is obtained by inverting every bit and adding 1 to the result. Computers often use the two's complement form for negative numbers because, with fixed-length arithmetic of n bits, the two's complement of x is 2" — x. Thus, the two's complement behaves much like the negative of the number; for example, the sum of a. binary number and its two's complement is zero. Table 8-6 shows four methods of representing positive and negative binary numbers, using four bits. Note than when two's complement is used, only one representation of zero is possible, and the largest magnitude of a negative number is one greater than the largest positive value.

A major factor in the choicc of a digital code is whether the sensor is digital or analog. Using a code such as those previously described, digital sensors generate

Table 8-6. Alternative Representations of Positive and Negative Binary Numbers

decimal equivalent

dne's complement sign bit • 0 for .

two's complement sign bit -0 for •

one's complement sign bit - 1 for -

natural binary sign bit » 0 poh *

0 0

Post a comment