- 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.