PRELAB
This week's laboratory investigates cyclic redundancy checking (CRC). CRC code generation is an important tool in computer networking at the data link layer level, since it is at that level that error detection is done by hardware. At a higher layer (transport), error detection is done in software, using a much simpler algorithm to allow speedy processing. In all cases, error detection provides an efficient means of implementing error control for reliable transmission of messages.
Polynomial Arithmetic for CRC Generation
The CRC, or frame check sequence R, is the remainder
of the following binary division:
. M is a k-bit message,
and P is a generating polynomial of degree n.
The remainder, R, is then appended to the message
M to form a (k + n)-bit
frame T to be transmitted.
Polynomial Arithmetic for CRC Reception
At the receiver, the received frame T is divided by the same generating polynomial P. A remainder of 0 indicates no error. Any other remainder is an indication of a burst error. Codes that are generated using shiftback registers and based on generating polynomials can detect 100% of all burst errors up to length n, that is, up to n bits in error, where n is the degree of the generating polynomial P. Higher burst lengths can also be detected, but at a lesser percentage.
Datasheet: 74LS74
[Copyright 1995 National Semiconductor Corporation.
Datasheet June 1989]
Datasheet: 74LS86
[Copyright 1995 National Semiconductor Corporation.
Datasheet June 1989]
Datasheet: 74LS00
[Copyright 1995 National Semiconductor Corporation.
Datasheet June 1989]
Resistors (Ω) | Capacitors (μF) | ||
---|---|---|---|
10 | 1k | 0.001 | 0.01 |
3.9k | 4.7k | 0.033 | 0.047 |
5.1k | 10k | 0.1 | 0.22 |
20k | 51k | 0.33 | 0.47 |
100k | 1M | 1 | 10 |