10 P. A. HUMBLET
Bursts of k errors, K L (including single errors) will always be detected as they have
E (x) = xl (xk~l - - • + ••• +1) , where / is the order of the lowest order coefficient in error.
Such an E(x) is not divisible by G(x) if G(x) contains an x° term:
Similarly if G(l) is zero then all patterns of odd numbers of errors will be detected as they
have E(l) equal to one.
Finally all patterns of two errors will be detected if xl + 1 is not divisible by G(x),
i N+L—1. This will be the case if G(x) contains a primitive polynomial of degree k, with
2k—\ N+L. (An irreducible polynomial of degree k is primitive over the modulo 2 field if and
only if it divides xn—1 for no n less than 2k—\. Primitive polynomials exist of all degrees.)
Generator polynomials used in practice have the three properties just mentioned; they are the
product of a primitive polynomial of degree L—\ and (x+1).
Another view to look at the problem is to observe that when many errors occur (and modems
often make large numbers of errors when they make any) there is about a chance in 2L that the
error polynomial will be divisible by G(x).
Older international communication standards specify generator polynomials of degree 16, so
that a block hit by a large number of errors has about a chance in 65000 to be accepted as correct.
This is too high in many applications, and more recent standards specify L equal to 32.
5. MULTI-USER SYSTEMS. Users of data communication networks are often bursty; they
may be silent most of the time! For that reason it makes economical sense to share communication
lines between may streams of traffic. Together with each piece of data it is then necessary to send
address information specifying to what stream the data belongs. This is the essential justification
for the use of packet switched networks.
We introduce two new problems that occur in such systems. They are somewhat imprecise,
and whatever is known about their solution does not have enough structure to be concisely
presented in these notes.
First the amount of overhead information carried in packets is far from negligible. It can
dwarf the amount of data! The presence of this overhead loads the lines and causes undesirable
How much of this overhead is necessary has not been properly quantified. In the simplest case
imagine a group of sources with known data generation statistics. They are connected to a single