Data can be corrupted during transmission. Some applications require that errors be detected and corrected.
In a single-bit error, only one bit in the data unit has changed. A burst error means that two or more bits in the data unit have changed.
To detect or correct errors, we need to send extra (redundant) bits with data.
There are two main methods of error correction: forward error correction and correction by retransmission.
We can divide coding schemes into two broad categories: block coding and convolution coding.
In coding, we need to use modulo-2 arithmetic. Operations in this arithmetic are very simple; addition and subtraction give the same results. we use the XOR (exclusive OR) operation for both addition and subtraction.
In block coding, we divide our message into blocks, each of k bits, called datawords. We add r redundant bits to each block to make the length n ::: k + r. The resulting n-bit blocks are called codewords.
In block coding, errors be detected by using the following two conditions:
a. The receiver has (or can find) a list of valid codewords.
b. The original codeword has changed to an invalid one.
The Hamming distance between two words is the number of differences between corresponding bits. The minimum Hamming distance is the smallest Hamming distance between all possible pairs in a set of words.
To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be d min ::: s + 1. To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be dmin ::: 2t + 1.
In a linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword.
A simple parity-check code is a single-bit error-detecting code in which n ::: k + 1 with d
min ::: 2. A simple parity-check code can detect an odd number of errors.
All Hamming codes discussed in this book have dmin ::: 3. The relationship between
m and n in these codes is n::: 2m – 1.
Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword.
A category of cyclic codes called the cyclic redundancy check (CRC) is used in networks such as LANs and WANs.
A pattern of Os and Is can be represented as a polynomial with coefficients of 0 and 1.
Traditionally, the Internet has been using a I6-bit checksum, which uses one’s complement arithmetic. In this arithmetic, we can represent unsigned numbers between o and 2^n -1 using only n bits.
