Packets: For a variety of reasons data in
networks is transmitted in packets, which are sequences of octets (i.e.
bytes). [Two reasons: cheaper to deal with loss or corruption of small
packets than with long full messages; easier to share communication channels
between concurrent communicating entities since there are no long messages
for whose transmission all have to wait.]
Usually packets are transmitted asynchronously, so we need to know
when the packet starts and when it ends [in the case of RS232 characters
we had a start and an end bit]. In general the problem of recognizing start
and end of a packet is called the framing problem.
One possible way to represent a packet is by starting it with a special
character, say SOH = 0x01, and ending it with a special character, say
EOT=0x04. Then one can recognize a packet by looking for these characters.
Of course, we need to make sure that SOH and EOT appear only at the
beginning and end of packets. This is done with byte stuffing: that
is replacing in the data each occurrence of SOH, EOT, and ESC=0x1B, with
ESC SOH, ESC EOT, and ESC ESC respectively (in bit oriented transmission
like in HDLC one encounters bit stuffing).
Frame: This is a packet, when we stress its representation in a particular protocol and hardware technology, for instance in RS-232 or in Ethernet. Frames consist of a header, a body, and possibly a tail. In Ethernet (this is the DIX format used in the original Ethernet) a frame has a header that consists of a preamble, 8 bytes of alternating 0s and 1s used to recognize the beginning of the frame, a destination address, 6 bytes, a source address, 6 bytes, and a frame type field, 2 bytes. The body consists of from 46 up to 1500 bytes. The tail is the CRC (see below error detection) for the header and body, 4 bytes.
Error Detection: Error detection is a form of error control [other forms of error control, for error recovery, one may use Automatic Repeat Request [ARQ]: Positive Acknowledgement, Retransmission after Timeout, Negative Acknowledgement and Retransmission. We will talk more about error control when we discuss data link level protocols.]. In general when a frame is sent, it may be lost in transit or it may be delivered corrupted (one hopes it gets there unchanged). Here we describe three methods that allow the receiver to detect errors, that is, to know with some probability that it has received what the sender sent.
11011110 Data octets
11100110
10101001
=======
10001101 Even parity octet
|6C|6C| "ll"
|6F|20| "o "
|77|6F| "wo"
|72|6C| "rl"
|64|2E| "d."
======
|71|FC| Checksum
Alternatively the checksum can be computed by adding each individual byte and using the carry as an additional addend. Checksums are easy to compute and have a fairly good capacity to detect errors. Unfortunately they do not detect simple forms of errors. For example, suppose that errors reverse the value of the second bit of each word being transmitted. If these words had the same number of 1s and 0s as second bits then the error will not be detected.
Then an irreducible polynomial P (it is for polynomials the same as a prime for numbers) is used to compute the modulo of the data polynomial. This modulo is taken as the CRC and appended to the data. The nice thing is that the modulo can be computed using simple circuits: XOR gates and shift registers initially containing 0. Here is an example of circuit for computing the CRC using as P the polynomial
|In
v X**16 X**12 X**5 1
X------------------>+--------------------------->+----------------------+
^ | | |
| +--+--+--+--+ v +--+--+--+--+--+--+--+ v +--+--+--+--+--+ v
+<--| | | | |<--X<--| | | | | | | |<--X<--| | | | | |<--+
| +--+--+--+--+ +--+--+--+--+--+--+--+ +--+--+--+--+--+
vout
To understand this structure, imagine that we are transmitting a single 1.
Then, since it will be appended to the remainder, it is as if the 1 was
multiplied by X**16, the degree of P. That is we obtain
X**16 1
| |
v v
10000000000000000
the remainder of this when dividing by P is
X**12 X**5 1
| | |
v v v
0001000000100001
which is just P eliminating its leading term. The Xor gates are positioned in the places
where we have the 1s.
When the message (data plus remainder) is received, the data
will cause that same remainder to be computed in the receiver's register. When the
original remainder is received, the two remainders will cancel each other
leaving 0s in the registers.
Here is how things work out for our original data 100100001100101
Arriving |
Bits | Content of registers
=================================
1 0000 0000000 00000
0 0001 0000001 00001
0 0010 0000010 00010
1 0100 0000100 00100
0 1001 0001001 01001
---------------------------------
0 0011 0010011 10011
0 0110 0100111 00110
0 1100 1001110 01100
1 1000 0011101 11001
1 0000 0111011 10010
---------------------------------
0 0001 1110110 00101
0 0011 1101100 01010
1 0111 1011000 10100
0 1110 0110000 01001
1 1101 1100001 10011
---------------------------------
1011 1000011 00110
Thus the message (data plus remainder) is 100100001100101 1011100001100110
More formally, if P(x) is the irreducible polynomial and M(x) is the message we are sending, the circuit operates as if we were sending the code C(x) = (x**r)*M(x) + R(x), where r is the degree of P(x) and R(x) is the remainder of the divisions of (x**r)*M(x) by P(x). Since the dividend is equal to the divisor*quotient + remainder, C(x) is just P(x)*quotient [since R(x) + R(x) is just 0 in binary arithmetic, and P(x) is the divisor). Thus the receiver will receive just P(x)*quotient and dividing it by P(x) will have a zero remainder. Of course if the code is corrupted during transmission the remainder at the receiver will not be 0. In fact, if the error is E(x), the remainder will be E(x)/P(x).