After reading this article you will learn about: 1. Rules of Data Transmission 2. Analog and Digital Data Transmission 3. Transmission Impairments 4. Modulation 5. Modems 6. Error Detection 7. Error Correction.
Rules of Data Transmission:
The design decisions that concern the rules for data transfer require that one specifies whether data will travel in only one direction or both directions. In case data are required to travel in both directions, is it necessary to enable data to travel in both directions simultaneously?
These issues are addressed by simplex transmission, half duplex transmission and full duplex transmission. In simplex transmission, data travel in only one direction. In half duplex transmission, data travel in both directions, but not simultaneously. In full duplex transmission, the data may travel in both directions simultaneously.
Analog and Digital Data Transmission:
Analog data refer to transmission using analogue signals and digital data refer to data transmitted using digital signals. An analogue signal is a signal whose amplitude varies with time, all the time. Amplitude of a signal at any instant is the value of the signal at that instant in time.
ADVERTISEMENTS:
An analogue signal, therefore, is a signal whose value varies with time. Analog signals arise when a physical waveform, such as an acoustic wave, is converted into an electrical signal. The conversion is effected by a transducer. A microphone that converts sound pressure variations into corresponding voltage or current variations is an example of a transducer.
A discrete-time signal, on the other hand, is defined only at discrete instants of time. Thus, in this case, the independent variable takes on only discrete values which are, usually, uniformly spaced. Consequently, discrete-time signals are described as sequences of samples that may take on a continuum of values.
When each sample of a discrete-time signal is allowed to take on only a finite set of discrete values (that is, it is quantized) and coded, the resulting signal is referred to as a digital signal. The output of a computer is an example of a digital signal. An analogue signal may be converted into a digital form by sampling in time followed by quantizing and coding.
Transmission Impairments:
It is time now to look at different transmission impairments and their reasons.
ADVERTISEMENTS:
Analog signals consist of varying a voltage (sometimes a current) with respect to time to represent an information stream. If the transmission media were perfect, the receiver would receive exactly the same signal that was sent by the transmitter.
Unfortunately, we live in an imperfect world and the media used in transmission are not perfect, so the signal received is not identical to the signal transmitted. This can lead to errors, particularly for digital data. Usually, transmission lines suffer from three different major problems that can cause signal distortion and impairment.
These are:
1. Attenuation,
ADVERTISEMENTS:
2. Delay distortion,
3. Noise.
1. Attenuation:
Attenuation is the loss of energy as the signal propagates outward. In guided media, such as copper wires or optical fibres, the signal weakens logarithmically with the distance. This loss is expressed in decibels per kilometer. It is interesting to note that the amount of energy lost depends on the frequency of transmission.
The result of this frequency dependence can be noted from the following discussion on the performance of digital transmission. Take the Fourier components of a digital signal. Naturally, this will consist of a large number of waves of different frequency. Each component wave, having a different frequency, will be attenuated to a different degree.
ADVERTISEMENTS:
Therefore, the Fourier spectrum of the receiver will be different from that of the transmitter and hence the received signal will be different from the transmitted signal. The effect of this difference will depend on the signal itself.
If the attenuation is too much, the receiver may not be able to detect the signal at all, or the signal may fall below the noise level. In some cases, the attenuation properties are known in advance, so amplifiers can be put in to try to compensate for the frequency-dependent attenuation. This may help, but it cannot restore the signal back to its exact original shape.
2. Delay Distortion:
Delay Distortion is the second cause of transmission impairment. It is caused by the fact that the different Fourier components travel at different speeds. In case of digital data, fast components from one bit may overtake the slow components of a previous bit, thus mixing the two and thus increasing the probability of incorrect reception.
3. Noise:
Noise is the third cause of transmission impairment. Noise consists of the unwanted energy from sources other than the transmitter. Thermal noise may be caused by the random motion of electrons in a wire and is unavoidable. Inductive coupling between two close wires may also be a reason for noise. Sometimes when talking on the telephone, you may hear another conversation in the background.
ADVERTISEMENTS:
This cross talk may be due to inductive coupling, because two wires close to each other may be causing this noise. Then spikes in the power lines may cause impulse noise. Impulse noise may be caused by other reasons also, such as switching of a particular fan or light or because of sparking. In case of digital data, impulse noise may wipe out one or more bits.
Modulation:
Both attenuation and propagation speed are frequency- dependent and therefore, it is desirable to have a small range of frequencies in the signal.
Unfortunately, square waves, as in digital data, have a wide spectrum and are, therefore, subject to strong attenuation and delay distortion. These effects make baseband signalling unsuitable except at very slow speeds and over short distances.
These signals are invariably associated with DC signalling, particularly on telephone lines, hence AC signalling is used. A continuous tone in the 1000-2000 Hz range, called a sine wave carrier, is introduced. Its amplitude, frequency or phase can be modulated to transmit information.
In case the amplitude is used for modulation, different voltages are used to represent 0 and 1 respectively. In frequency modulation, sometimes also called frequency shift keying, two or more different tones are used. In its simplest form in phase modulation, the carrier wave is shifted by 45°, 135°, 215° or 315° at uniformly spaced intervals. Each phase shift transmits two bits of information.
In message transmission over a communication channel, we may use analogue or digital methods. However, the use of digital methods offers several important operational advantages over analogue methods.
These include:
1. Increased immunity to channel noise and external interference,
2. Flexible operation of the system,
3. A common format for transmission of different kinds of message signals (e.g. voice signals, video signals, computer data),
4. Improved security.
These advantages are attained, however, at the cost of increased transmission (channel) bandwidth and increased system complexity.
Modems:
A device that accepts a serial stream of bits as input and produces a modulated carrier as output (or vice versa) is called a modem. The term modem is the shortened form of ‘modulator-demodulator’. It is inserted between the digital computer and the analogue telephone line. This is obviously done by taking samples from the input stream at fixed intervals.
However, in order to increase speed, it may not be possible to merely increase the sampling rate. Recall that the Nyquist theorem states that even with a perfect 3000-Hz line, there is no point in sampling faster than 6000 Hz.
Therefore, in order to get faster modems, more bits per sample (or per baud) have to be taken. Recall that a baud, which is a measure of signalling speed, measures the number of signals transmitted per second.
This is often confused and many people think that it measures the number of bits transmitted per second. This is not so, since each signal may convey several bits. Advanced modems use a combination of modulation techniques.
Some of these are illustrated below:
The Fig. 4.2 above shows marks at 0°, 90°, 180° and 270° with two amplitude levels per phase— amplitudes are indicated by the distance from the origin. The second diagram shows a different modulation scheme.
This scheme, which is often used to transmit 9600 bps over a 2400 baud line, is used to transmit 4 bits per baud. This scheme is called the Quadrature Amplitude Modulation or QAM. Figures like the one above are called constellation patterns. Each high-speed modem has its own constellation pattern.
Pulse Code Modulation:
Pulse Code Modulation is often referred to by its short form PCM. It is one of the digital methods used for transmission of message signals over a communication channel. In PCM, the message signal is sampled, quantized and then encoded.
The sampling operation permits representation of the message signal by a sequence of samples taken at uniformly spaced intervals of time. Quantisation trims the amplitude of each sample to the nearest value selected from a finite set of representation levels. The combination of sampling and quantisation permits the use of a code for transmission of a message pulse.
PCM is complex because the message signal is subjected to a great number of operations. The essential operations in the transmitter of a PCM system are sampling, quantisation and encoding.
The quantising and encoding operations are usually performed in the same circuit, the analog-to-digital converter. The essential operations in the receiver are regeneration of repaired signals, decoding and demodulation of the train of quantised samples.
The operations are usually performed in the same circuit called the digital-to-analogue converter. At intermediate points along the transmission route from the transmitter to the receiver regenerative repeaters are used to regenerate the transmitted sequence of coded pulses in order to combat the accumulated effects of signal distraction and noise.
Quantisation refers to the use of a finite set of amplitude levels and the selection of a level nearest to a particular sample value of the message signal as the representation for it.
This operation combined with sampling permits the use of coded pulses for representing the message signal. It is, in fact, the combined use of quantising and coding that distinguishes pulse code modulation from analogue modulation techniques.
Amplitude Modulation:
In amplitude modulation, two different voltage levels are used to represent 0 and 1 respectively. Suppose we have a sinusoidal carrier wave c(t) defined by
where Ac, the peak amplitude, is called the carrier amplitude and fc, the carrier frequency. Assume also, for the sake of simplicity, that the phase of the carrier wave is 0. In any case, this is within the user’s control since the carrier source is independent of the message source. If m(t) denotes the baseband signal that carries the message specification then we can refer to m(t) as the message signal.
Amplitude modulation is defined as a process in which the amplitude of the carrier wave c(t) is varied linearly with the message signal m(t). While this definition is general, it is advisedly so, because linearity can have different interpretations.
Correspondingly, amplitude modulation can take on different forms, depending on the frequency content of the modulated wave. We can start with the consideration of the standard form of amplitude modulation. This is defined by
where ka is a constant referred to as the amplitude sensitivity of the modulator. A wave that has been so modulated wave is said to be a “standard” Amplitude Wave, because its frequency content is fully representative of amplitude modulation. The amplitude of the time function multiplying cos(2π fct) is called the envelope of the amplitude-modulated wave s(t). Using a(t) to denote this envelope, we may write
The value of kam(t) compared to 1 creates some interesting cases. If its absolute value is less than 1 for all cases of t, then 1 + kam (t) is non-negative for all values of t, then the envelope is
On the other hand, if we have
then we must use Eqn. 4.3 to evaluate the envelope of the AM wave. The maximum absolute value of kam(t) multiplied by 100 is called the percentage modulation. Accordingly, the first case corresponds to a percentage modulation of less than or equal to 100% and the second case to a percentage modulation of more than 100%.
The amplitude modulation process is depicted in the following wave shapes:
The figures above indicate the modulation process. The first figure (Fig. 4.4) depicts the waveform of a message signal m(t). Figure 4.5 depicts an AM wave produced by this message signal for a value of ka for which the percentage modulation is 66.7%. On the other hand, the AM wave shown in figure corresponds to a value of ka for which the percentage modulation is 166.7%.
Comparing the waveforms of these two AM waves with that of the message signal, we may conclude that the envelope of the AM wave has a waveform that bears a one-to-one correspondence with that of the message signal, if and only if, the percentage modulation is less than or equal to 100%.
This correspondence is destroyed if the percentage modulation exceeds 100%. In the latter case, the modulated wave is said to suffer from envelope distortion, and the wave itself is said to be over-modulated.
The complexity of the detector, that is, the demodulation circuit used to recover the message signal from the incoming AM wave at the receiver, is greatly simplified if the transmitter is designed to produce an envelope a(t) that has the same shape as the message m(t). For this requirement to be realised two conditions must be satisfied.
These are:
1. The percentage modulation is less than 100%, so as to avoid envelope distortion.
2. The message bandwidth W, is small compared to the carrier frequency fc, so that the envelope a(t) may be visualised satisfactorily. It is assumed that the spectral content of the message signal is negligible for frequencies outside the interval — W ≤ f ≤ W.
Frequency and Phase Modulation:
One method of modulating a sinusoidal carrier wave is angle modulation in which either the phase or the frequency of the carrier wave is varied according to the message signal, while keeping the amplitude of the carrier wave constant. Frequency modulation is that form of angle modulation in which the instantaneous frequency fc(t) is varied linearly with the message signal m(t) as shown by
where fc represents the frequency of the un-modulated carrier, and the constant kf represents the frequency sensitivity of the modulator in hertz per volt, assuming that m(t) is a voltage waveform.
Phase modulation (PM) is that form of angle modulation in which the angular argument is varied linearly with the message signal m(t) as shown in the following equation:
Modems and Interfaces:
Modems and Interfaces is also required by the computer-telephone combination, is some device that can handle the interface between the two. A modem is an example of this interface. Most of the telephone system is analogue in nature, whereas data generally originates from computers. Also, for most efficient use of the telephone system, digital circuits are required.
This requires a device to convert analogue signals to digital signals and digital signals to analogue signals. This is achieved through a device called a modem. This interface is an example of the physical layer protocol in a network.However, there are fixed standards for such physical layer interfaces.
These are normally known as RS232-C and RS449. RS232-C was a standard originally defined by the Electronics Industries Association and therefore the full name of the RS232-C interface is EIA RS232-C. C refers to the third revision of the original RS232. The international version of this standard is defined by CCITT as V.24, which is similar but more comprehensive than RS232.
In this specification, some of the points defined are:
1. 25 pins must be used, 1 to 13 in the top layer and 14 to 25 in the bottom layer.
2. The width of each pin is 47.04 ± .13 mm (screw centre to screw centre).
3. A voltage less than -3 volt represents a binary 0 and a voltage more than +4 volt represents a binary 1.
4. Data rates should be less than or equal to 20 kbps.
5. Cables should not be longer than 15 metres.
6. Each of the 25 pins have functional specifications which are defined, such as pin 1 for ground, pin 2 for transmit, pin 3 for receive, etc.
7. Protocols or procedural specifications are clearly defined. For example, if the terminal requests to send, the modem answers with clear to send, if it is in a position to receive data and so on.
Sometimes one wishes to connect two computers. This connection will also require an RS232-C interface. Since neither one of them is a modem, a device called a “null modem” is used. This null modem connects the transmission line of one to the receiving line of the other and vice versa. It similarly connects all the necessary lines.
However, over a period of time, the limitation of the data rate and the cable length became irksome and improvements in the standards laid down became imperative. Ultimately, a new standard was developed. This was the RS449 standard and an improvement over the RS232-C standard. For a comparison of the three standards mentioned, the reader is advised to consult Table 1.
This table should be used merely to indicate the types of code, the description of the functions and the pin numbers to which those functions and codes are associated. The table will show what sort of advances in the interface has taken place over the years in interfacing at the level of the physical layer in networks.
These advances can be seen by noting the differences between the RS232-C, its equivalent CCITT standard V.24 and RS449. This table is a standard document and obtainable directly from the United Nations body, the standardisation sector of the International Telecommunication Union (ITU-T). There is, however, an older interface standard that needs to be mentioned.
Many older networks follow a standard called X.25. It was developed in the 1970s by CCITT to provide an interface between public packet-switched networks and their customers. The physical layer protocol, called X.21, specifies the physical, electrical and procedural interface between the host and the network.
Today, very few public networks actually support this standard, because it requires digital (rather than analogue) signalling on the telephone lines. As an interim measure, an analogue interface similar to RS-232 standard was defined.
The data link layer standard has a number of slightly incompatible variations. They are all designed to deal with transmission errors on the telephone line between the user’s equipment—which is the host or terminal—and the public network, which is the router.
The network layer protocol deals with addressing, flow control, delivery confirmation, interrupts and related issues. Basically, it allows the user to establish virtual circuits and then send packets of up to 128 bytes on them.
These packets are delivered reliably and in order. Most X.25 networks work at speeds up to 64 kbps, making them obsolete for many purposes. Nevertheless, they are still widespread. X.25 is connection-oriented and supports both switched virtual circuits and permanent ones.
Error Detection:
The telephone system has three main sets of components:
The switches, the interoffice connections and the local loop. Of these three components, the switches and the interoffice connections have been pretty much digitized and while the local loop is also being digitized, because of the extent and size of this job, it will take a long time.
Therefore, the local loop still largely consists of twisted copper wire and continues to be analogue in nature.
While the extent of errors in the digital components is extremely rare, they are still quite frequent in the local loops. Since wireless communication is expanding rapidly, the error rates are orders of magnitude worse than on the interoffice connections (which are largely trunk and have been replaced largely by fibre optic cabling).
Therefore, transmission errors are likely to continue for quite some time into the future. As a result of this, correction techniques have to be perfected because they have considerable importance in the present scheme of things in the telephone system. The nature of the physical processes that generate these errors is such that errors in some media (e.g. radio) tend to come in bursts rather than individually or singly.
The fact that the errors come in bursts has both advantages as well as disadvantages over single-bit errors. Computer data are always sent in blocks of bits. If the block size is, say 1000 bits, and the error rate is, say 1 in 100000, then if errors were independent and came singly or individually then most blocks would contain an error.
If the errors came in blocks or bursts of 100, however, only one or two blocks in 100, on an average would be affected. This is obviously an advantage. The disadvantage is that in case of error blocks it may be mentioned that they are much more difficult to detect and correct compared to individual errors.
Error Correction:
In order to be able to implement error correction, there are two basic methods. Both methods are based on redundancy. The first method is to send enough redundant data along with each block of data so that the receiver can deduce what the transmitted character must have been.
The second method is to send just enough redundancy so that the receiver can work out that an error has occurred, should such an error occur. The first method is called “error correction” and the second method is called “error detection”.
Error-Correcting Codes:
What is an error? Normally, a frame consists of m bits of data—which is the message—and r redundant bits which are check bits. Therefore, the total length n = m + r bits. Such an n-bit conglomeration is called an n-bit code word.
If you have any two code-words, it is obviously possible to determine how many corresponding bits differ. To determine how many bits differ, just EXCLUSIVE OR the two code-words and count the number of 1 bit in the result. Say, we have two code words 10000101 and 10110001.
If we perform the EXCLUSIVE OR operation on the two, we shall find that 3 bits are different (we will get three is as a result of this EXCLUSIVE OR operation). The number of bit positions in which two code-words differ is called the Hamming distance. Its significance is that if two code-words are at a Hamming distance d apart, it will require d single-bit errors to convert one into the other.
If the message length is m, then there are 2m data messages. In case of most data messages, all 2m messages are legal, but due to the way the check bits are computed, not all of the possible 2m code words are used. In the algorithm for computing the check bits, it is possible to construct a possible list of legal code words and out of these to find the two code words whose Hamming distance is minimum.
This distance is called the Hamming distance for the whole code. The error-detecting and error-correcting properties of a code depend on its Hamming distance. To detect d errors, you need a distance d + 1 code, because with such a code there is no way that d single-bit errors can change a valid code word into another valid code word.
When the receiver sees an invalid code word, it can tell that a transmission error has occurred. Also, to correct d errors, you need 2d + 1 code, because that way the legal code words are so far apart that even with d changes, the original code word is still closer than any other code word, so it can be uniquely determined.
To test the above propositions, consider an example of an error detection—detecting code in which a single parity bit is appended to the data. The parity bit is chosen so that the number of 1 bit in the code word is even (or odd). For example, when 10110101 is sent in even parity by adding a bit at the end, it becomes 101101011, whereas 10110001 becomes 101100010 with even parity.
A code with a single-parity bit has a distance of 2, since any single-bit error produces a code word with the wrong parity. It can be used to detect single errors.
As a simple example of an error-correcting code, consider a code with only four valid code words:
0000000000, 0000011111, 1111100000, 1111111111.
This code has a distance 5, and can, therefore, correct double errors. If the code word 0000000111 arrives, the receiver knows that the original must have been 0000011111. If, however, a triple error changes 0000000000 into 0000000111, the error will not be corrected properly.
Imagine that we want to design a code with m message bits and r check bits that will allow all single errors to be corrected. Each of the 2m legal messages has n illegal code words at a distance 1 from it.
These are formed by systematically inverting each of the n bits in the n-bit code word formed from it. Thus each of the 2m legal messages requires n + 1 bit patterns dedicated to it. Since the total number of bit patterns is 2n, we must have
Using n = m + r, this requirement becomes (m + r + 1) ≤ 2r. Given mi this puts a lower limit on the number of check bits needed to correct single errors. This theoretical lower limit can, in fact, be achieved using a method due to Hamming.
The bits of the code word are numbered consecutively, starting with bit I at the left end. The bits that are powers of two (1, 2, 4, 8, etc.) are check bits. The rest (3, 5, 6, 7, 9, etc.) are filled up with m data bits. Each check bit forces the parity of some collection of bits, including itself, to be even (or odd).
A bit may be included in several parity computations. To see which check bits the data bit in position k contributes to, rewrite A; as a sum of powers of 2. For example, 11 = 1 + 2 + 8 and 29 = 1 + 4 + 8 + 16. A bit is checked by just those check bits occurring in its expansion (e.g. 29 is checked by bits 1, 4, 8, 16).
When a code word arrives, the receiver initializes a counter to zero. It then examines each check bit, k(k = 1, 2,4, 8,…) to see if it has the correct parity. If not, it adds k to the counter. If the counter is zero after all the check bits have been examined and found correct, the code word is accepted as valid.
If the counter is non-zero, it contains the number of the incorrect bit. For example, if check bits 1, 2 and 8 are in error, the inverted bit is 11, because it is the only one checked by bits 1, 2 and 8. The figure below shows some 7-bit ASCII characters encoded as 11-bit code words using a Hamming code. It may be remembered that the data are found in bit positions 3, 5, 6, 7,9, 10 and 11.
Hamming codes can correct only single errors. However, there is a trick that can be used to permit Hamming codes to correct burst errors. A sequence of k consecutive code words are arranged as a matrix, one code word per row. Normally, the data should be transmitted one code word at a time, from left to right. To correct burst errors, the data should be transmitted one column at a time, starting with the leftmost column.
When all k bits have been sent, the second column is sent, and so on. When the frame arrives at the receiver, the matrix is reconstructed, one column at a time.
If a burst error of length k occurs, at most 1 bit in each of the k code words will have been affected, but the Hamming code can correct one error per code word, so the entire block can be restored. This method uses kr. check bits to make blocks of km data bits immune to a single burst error of length k bits.
Error-Detecting Codes:
Error-correcting codes are sometimes used for data transmission. For example, when the channel is simplex, retransmission cannot be requested, but most often error detection followed by retransmission is preferred because it is more efficient. Consider a simple example. Consider a channel on which errors are isolated and the error rate is 10-6 per bit. Let the block size be 1000 bits.
To provide error correction for 1000-bit blocks, 10 check bits are required and, therefore, a megabit of data would require 10,000 check bits. To merely detect a block with a single 1-bit error, 1 parity bit will suffice.
Once every 1000 blocks an extra block (1001 bits) will have to be transmitted. The total overhead for the error detection plus retransmission method is only 2001 bits per megabit of data, versus 10,000 bits for a Hamming code.
If a single-parity bit is added to a block and the block is badly garbled by along burst error, the probability of detecting the error is only 0.5 which should be unacceptable. The odds can be improved substantially by regarding each block to be sent as a rectangular matrix with a column of n bits and a row of k bits. A parity bit is computed separately for each column and affixed to the matrix in the last row.
The matrix is then transmitted one row at a time. When the block arrives, the receiver checks all the parity bits. If anyone is wrong, it requests for retransmission of the entire block.
This method can detect a single burst of length n, since only one bit per column will be changed. However, if bit n + 1 is inverted the entire n + 1 will pass undetected, however, if the first bit is inverted, the last bit is inverted and all other bits are correct.
A burst error, in fact, does not imply that all the bits are wrong—it only implies that at least the first and the last are wrong. If a block is badly garbled by a long burst or by multiple shorter bursts, the probability that any of the ‘n’ columns will have the correct parity, by chance, is 0.56. So the probability of a bad block being accepted when it should not be 2-n.
Cyclic Redundancy Check:
Although this scheme may usually be adequate, another method known as Cyclic Redundancy Code is more widely used. This check also known as the polynomial code or CRC code is, in practice, more commonly used. This check is based on treating bit strings as representations of polynomials with coefficients of 0 and 1 only.
A k-bit string frame is regarded as the coefficient list for a polynomial with k terms, ranging from xk-1 to x°. Such a polynomial is said to be of degree k — 1. The leftmost bit is the coefficient of xk-1 the next bit is the coefficient of x k-2, and so on.
For example, 101001 has 6 bits and thus represents a six-term polynomial with coefficients 1,0, 1, 0. 0, and 1 leading to x5 + x3 + x°. Polynomial arithmetic is done modulo 2, according to the rules of algebraic field theory. There are no carries for addition or borrows for subtraction. Both addition and subtraction are identical to EXCLUSIVE OR. For example
Long division is carried out in the same way as it is in binary except that the subtraction is done modulo 2, as above. A divisor is said “to go into” a dividend if the dividend has as many bits as the divisor.
When the polynomial code method is employed, the sender and the receiver must agree upon a generator polynomial, G(x), in advance. Both the high and the low order bits of the generator must be 1. To compute the checksum for some frame with m bits, corresponding to the polynomial M(x), the frame must be longer than the generator polynomial.
The idea is to append a checksum to the end of the frame in such a way that the polynomial represented by the check-summed frame is divisible by G(x). When the receiver gets the check-summed frame, it tries to divide it by G(x). If there is a remainder, there has been a transmission error.
The algorithm for computing the checksum is as follows:
1. Let r be degree of G(x), append r zero bits to the lower-order end of the frame so that it now contains m + r bits and corresponds to the polynomial.
2. Divide the bit string corresponding to G(x) into the bit string corresponding to xrM(x) using modulo 2 division.
3. Subtract the remainder, which is always smaller than or equal to r, from the bit string corresponding to xrM(x) using modulo 2 subtraction. The result is the check summed frame to be transmitted. This polynomial may be called, say, T(x).
Let us take an example to illustrate the above logic. Assume that we have a frame 1101011011 and
G(x) = x4 + x + 1.
Since T(x) is divisible (modulo 2) by G(x), let us concentrate on this division. In any division problem, if you diminish the dividend by the divisor, what is left over is divisible by the devisor. For example, in base 10, if you divide 216533 by 10209, the remainder is 2144. By subtracting 2144 from 216533 what is left (214389) is divisible by 10209.
Suppose we analyse this operation. What kind of errors will be detected? Suppose a transmission error occurs, so that instead of the bit string for T(x) arriving, T(x) + E(x) arrives. Each 1 bit in E(x) corresponds to a bit that has been inverted. If there are k 1 bits in E(x), k single-bit errors have occurred.
A single-burst error is characterised by an initial 1, a mixture of 0s and Is, and a final 1, with all other bits being 0. As soon as the receiver receives the checksum frame it divides it by G(x), that is, it computes [T(x) + E(x)]/G(x). T(x)/G(x) is 0, so the result of the computation reduces to E(x)/G(x).
Those errors that correspond to polynomials containing G(x) as a factor will slip by; all other errors will be caught. If there has been a single-bit error, E(x) = xi where i determines which bit is in error. If G(x) contains two or more terms, it will never divide E(x), so all single-bit errors will be detected. If there have been two isolated single-bit errors, E(x) = xi + xj, where i > j. This can also be written as E(x) = xi(xl_J + 1).
If we assume that G(x) is not divisible by x, a sufficient condition for all double errors to be detected is that G(x) does not divide xk + 1 for any up to the maximum value of i — j (that is, up to the maximum frame length). Simple, low-degree polynomials that give protection to long frames are known. For example, x15 + x14 + 1 will not divide xk + 1 for any value of k less than 32768.