Download

Encoding & Modulation Techniques

If transmission media were perfect, we would not have to worry about errors in data communications. Unfortunately, that is not the case. Noise spikes and other types of interference can change 1s to 0s and 0s to 1s during transmission. A short 20 ms click on a telephone line may be annoying during a telephone conversation, but it is unlikely to disrupt voice communication. However, if data are being sent over the line at 4800 b/s, that same click may destroy 240 data bits. A number of techniques have been developed to detect and sometimes to correct errors.

All of the methods of detecting errors involve the transmission of redundant data. Redundant data are data that are not necessary to the information content of the transmission. Redundant data could be omitted and communication would still take place. Error checking schemes compare the redundant data to see if they agree. If they do agree, it is likely that no error has occurred. If they do not agree, it is almost certain that an error has occurred. Encoding & Modulation Techniques

The simplest way to deal with errors is to let the receiving operator correct them. This method takes advantage of the fact that human language itself is redundant. For example, suppose the following sentence is sent over a news service communication system as part of a news story : Encoding & Modulation Techniques

THE DOWNTOWN BRANCH  OF THE BANK OF CENTERVILLE WAS ROBBED OF MORE THAN $4000 LAST NIGHT.

If the transmission is sent to Baudot, and the first bit of the second W in the word DOWNTOWN is changed by a noise spike, the message will be received as :

THE DOWNTOAN BRANCH OF THE BANK OF CENTERVILLE WAS ROBBED OF MORE THAN $4000 LAST NIGHT. Encoding & Modulation Techniques

It would not be difficult for the receiving operator to realize that DOWNTOAN is not a word and to make the necessary correction before publishing the story. There is enough reduntant information in the message to do that. However, if the character 4 in the sentence is affected by noise, and the message is received as :

THE DOWNTOWN BRANCH OF THE BANCK OF CENTERVILLE WAS ROBBED OF MORE THAN $8000 LAST NIGHT. Encoding & Modulation Techniques

the receiving operator will know that there is an error in the message but will probably not know how to fix it. There is enough redundant information in the message to detect the error, but there is not enough to correct it.

In most of today’s data communication systems, the only types of errors that humans are expected to correct are typing errors. Most communication systems detect and correct errors that occur after the information leaves the keyboard.

Echoplex

Echoplex is a simple form of error detection that relies on redundant transmission to help the sending operator make corrections. It is commonly used on full–duplex communications systems in which each character is sent as it is typed into the transmitting terminal. Almost anyone who has used a computer and a modem has used echoplex. As the receiving terminal receives each character, it retransmits or echoes it back to the transmitting terminal where it appears on that termianal’s screen. The operator checks the character on the screen to see if it has been echoed correctly. If there is an error, the operator presses the backspace key to erase the erroneous character and then types the correct one. Encoding & Modulation Techniques

The advantage of echoplex is its simplicity. It does not require complex circuitry, and it is easy to implement. One disadvantage of echoplex is that it relies on a human operator to detect and correct errors. Another disadvantage is that it makes inefficient use of the communications channel, because the same information is transmitted in both directions. Although echoplex is commonly used to correct typing errors in communication systems that transmit information as the operator types it into a terminal, it is not used in other types of communications systems.

Parity

Parity is one of the simplest forms of automatic error detection and is frequently used with the ASCII code. Although ASCII is a 7–bit code, a redundant bit, called a parity bit, is often added to the ASCII character. The parity bit is placed in the most significant bit (bit 7) position. There are two types of parity – odd and even. If even parity is used, every 8–bit data word in a message contains an even number of binary 1s. If odd parity is used, every word has an odd number of 1s. As the parity bit is added to the ASCII character by the sending terminal, it is either set or cleared to form the correct parity.

Neither type of parity has an advantage over the other in most communications systems, and both are widely used. However, the transmitting and receiving terminals must use the same type of parity, and all characters sent between those two terminals must have the same type of parity.

Example 5–6

The following ASCII characters are sent : 110 0001, 111 0010 and 110 0101. If the characters are transmitted with odd parity, where parity bit is added to each character, a 1 or a 0? What is the ASCII code for each character in hexadecimal including theparity bit ?

Solution

For odd parity, the total number of binary 1s in each character, including the parity bit is odd. The first character, 110 0001 has three 1s, which is already odd parity. Therefore, a parity bit of 0 is added in the MSB position to make the complete 8–bit data character 0110 0001, or $61. The second character, 111 0010 has an even number of 1s. The sending terminal adds a binary 1 as a parity bit to make the total number of 1s odd. The resulting ASCII character, including the parity bit , is 1111 0010, or $F2. The third character, 110 0101, also requires a 1 for odd parity, which makes the complete data character 1110 0101, or $E5.

The receiver checks the parity of each incoming ASCII character to see if it is correct. If the receiver is programmed to receive odd parity, every incoming data word must have odd parity. If it is programmed to receive even parity, every incoming data word must have even parity. If one bit in a data character gets changed by noise during transmission, the parity of the received character will be incorrect. When incorrect parity is received, it is called a parity error. For example, suppose a communications system uses even parity and that the ASCII character 1011 1000 is sent. If a noise spike changes bit 1, the character will be received as 1011 1010, which has odd parity. This is a parity error.

How a communication system responds to parity errors depends on how the terminals have been programmed. In a half–duplex or full–duplex system, the receiving terminal may send a message back to the transmitting terminal requesting that the entire message containing the error be retransmitted. In a simplex system, the receiving terminal cannot send messages back to the transmitting terminal, so there is no way for it to request retransmission. In such a case, the terminal may be programmed to print a star (*) on the screen to let the receiving operator know that an error has occurred.

A parity error is generated when an odd number of bits is changed during transmission, but no parity error is generated when an even number of bits is changed. For example, suppose 2 bits are changed by noise during transmission so that the character 1011 1000 is received as 1011 1110. Although the receiver character contains two errors, both the received character and the character that was originally sent have even parity. The receiving terminal does not generate a parity error, and the data error is not detected.

Like all methods of error detection, parity adds redundant information ot the data stream. A disadvantage of parity is that it detects only errors that affect an odd number of bits in a data word. An advantage of parity is that it is simple to implement. Because of its simplicity, parity is widely used.

Horizontal and Vertical Parity Check

A better method of detecting errors involves using a combination of horizontal and vertical parity checks. The simple parity check discussed in Section 5–2–2 is a horizontal parity check. Vertical parity is calculated for all of the bits with the same bit number in a block of data. After a block of data has been sent, the transmitting terminal calculates a parity bit for bit 0 of all of the characters in the block, another parity bit for bit 1 of all of the characters, and so on. The vertical parity bits are transmitted as a block check character (BCC) at the end of the block of data.

Either even or odd parity may be used for both the horizontal and vertical parity bits. The same parity may be used for both, or one of them may have even parity, and the other may have odd parity. However, the transmitting and receiving terminals must use the same parity scheme. For illustration, the horizontal parity in Table 1 is even, and the vertical parity is odd. Bits 0 through 6 in the figure are the ASCII code for the information transmitted. Notice that even the parity bit of the BCC passes both the vertical and horizontal parity check.

Table 1

A short message using even character and odd column parity

P	b6	b5	b4	b3	b2	b1	b0	ASCII Character
1	1	1	0	0	1	0	0	d
1	1	1	0	0	0	0	1	a
0	1	1	1	0	1	0	0	t
1	1	1	0	0	0	0	1	a
1	0	1	0	0	0	0	0	SP
0	1	1	0	0	0	1	1	c
0	1	1	0	1	1	1	1	o
1	1	1	0	1	1	0	1	m
1	1	1	0	1	1	0	1	m
1	1	0	0	0	0	1	1	BCC

 

The receiver checks the horizontal parity of each character as it is received. The receiver also generates its own BCC and compares it with the check character received at the end of the block of data. The two should be identical. If they are not,  an error has occurred, and the receiver can request that the sending terminal retransmit the block of data.

However, the combination of horizontal and vertical parity checking does more than detect errors. It also allows the receiver to correct single–bit errors without requesting further information from the transmitter, a process known as forward error correction (FEC). Table 2 shows the data block of Table 1, but bit 1 of the SP, or space, character has been altered by noise. Both the horizontal parity check for the space character and the vertical parity check for bit 1 fail. Therefore, bit 1 of the SP character must be in error. The receiver can correct the error by changing the 1 back to a 0.

Table 2 :Bit 1 of the SP character fails both character and column parity checks

and is therefore in error.

P	b6	b5	b4	b3	b2	b1	b0	ASCII Character
1	1	1	0	0	1	0	0	d
1	1	1	0	0	0	0	1	a
0	1	1	1	0	1	0	0	t
1	1	1	0	0	0	0	1	a
1	0	1	0	0	0	1	0	SP
0	1	1	0	0	0	1	1	c
0	1	1	0	1	1	1	1	o
1	1	1	0	1	1	0	1	m
1	1	1	0	1	1	0	1	m
1	1	0	0	0	0	1	1	BCC

 

Unfortunately, the combination of horizontal and vertical parity can reliably perform FEC only on single–bit errors. Errors that involve two or more bits cannot always be corrected. To illustrate, in Table 3, both bit 1 of the SP character and bit 2 of the character c have been changed by noise. Both characters fail horizontal parity checks, and bits 1 and 2 fail their vertical parity checks, but the receiver cannot determine which bits are in error. The error could just as easily be bit 2 of the space character and bit 1 of character c. Even though the receiving terminal cannot perform FEC, at least the receiving terminal can determine that a transmission error has occurred, and it can request that the sending terminal retransmit the entire block of data.

Table 3: Two–bit errors can be detected by a combination of character and column parity checks, but they usually cannot be corrected

P	b6	b5	b4	b3	b2	b1	b0	ASCII Character
1	1	1	0	0	1	0	0	d
1	1	1	0	0	0	0	1	a
0	1	1	1	0	1	0	0	t
1	1	1	0	0	0	0	1	a
1	0	1	0	0	0	1	0	SP
0	1	1	0	0	1	1	1	c
0	1	1	0	1	1	1	1	o
1	1	1	0	1	1	0	1	m
1	1	1	0	1	1	0	1	m
1	1	0	0	0	0	1	1	BCC

No system of error checking is 100% foolproof. Table 4 contains 4 bit erorrs. Bits 1 and 2 of both the SP and c characters have been altered during transmission. Both characters pass their horizontal checks, and both bit positions pass vertical parity checks. Even the combination of horizontal and vertical parity checks has failed to detect the errors.

Parity bits can be generated by software routines in the sending terminal, and they can be checked by software routines at the receiving terminal. However, it is more efficient to generate and check parity bits in hardware. Figure 11 is the schematic of a circuit that can be used to generate horizontal parity bits. The 7 bits of the ASCII character are applied to the inputs labelled bit 0 through bit 6, and a bias bit is applied to the remaining input. If the bias bit is a 1, the correct horizontal parity bit will be generated to give the character odd parity. A bias bit of 0 will cause the circuit to generate the correct horizontal parity bit for even parity. Trace the circuit by assuming a set of inputs to assure yourself that it works.

Parity generator and checker circuits are part of the DTE circuit. They were once constructed from discrete, exclusive OR gates as shown in Figure 11 below, but today they are built into a larger integrated circuit that also performs other communication tasks,

Table 4: Even the combination of character and column parity checks will not detect all errors

P	b6	b5	b4	b3	b2	b1	b0	ASCII Character
1	1	1	0	0	1	0	0	d
1	1	1	0	0	0	0	1	a
0	1	1	1	0	1	0	0	t
1	1	1	0	0	0	0	1	a
1	0	1	0	0	1	1	0	SP
0	1	1	0	0	0	1	1	c
0	1	1	0	1	1	1	1	o
1	1	1	0	1	0	1	1	m
1	1	1	0	1	1	0	1	m
1	1	0	0	0	0	1	1	BCC

Checksums

As illustrated in Table 5, a checksum is the least significant byte of the arithmetical sum of the binary data transmitted. As the data is sent, the transmitting terminals sums it. At the end of the data block, it sends the least significant byte of the sum as an extra character, called the checksum. The receiver generates its own checksum by summing the data as it is received. At the end of the block, it compares the checksum it generated with the checksum it receives from the transmitter. If the two are identical, it is likely that no error occurred. If the two checksums are different, an error has occurred, and the receiver requests that the block of data be resent.

Table 5: The checksum is the least significant byte of the sum of the coded data

Character	EBCDIC
T	$E3
e	$85
r	$99
r	$99
i	$89
b	$82
l	$93
e	$85
Checksum	$BD

Cyclic Redundancy Check (CRC)

One of the more effective methods of error detection is the cyclic redundancy check (CRC). A circuit that can be used to generate a 16–bit CRC character is shown in Fig.12. Identical CRC circuits are used in the transmitting and the receiving terminals to generate a check character which is highly dependent on all the data that were sent in the block. We will use the CRC circuit in the receiving terminal as our example.

The CRC circuit is initialized with all 0s in the shift registers. Each time a bit is received, every bit in the shift registers is shifted right. Assume that the first bit received is a 1. It is exclusively 0Red in G3 with a 0 shifted out of b0 of the shift register to produce a logical 1 which is in turn shifted into the b15 position of he shift register and continues to shift right as each subsequent bit is received. Four received bits later, it will have been shifted to the b11 position where it will influence the output of exclusive OR gate G1. The output of G1 is shifted to the right until it arrives at the b4 position and influences the output of G2. The G2 output in turn shifts right to the b0 position where it is exclusively 0Red with a  received bit of data to influence the output of G3 and thereby the input to the CRC circuit.

The important thing to recognize is that once a bit is received, it continues to influence the contents of the shift registers in the CRC circuit. If one bit is received incorrectly, it will cause the contents of the CRC shift registers to be different than they would have been if all bits had been received correctly.

As mentioned, the transmitting terminal has a CRC circuit identical to the CRC circuit in the receiver. As each bit is transmitted, a copy of that bit is input into the CRC circuit. At the end of the block of data, the sending terminal transmits the contents of its CRC registers. When the receiver receives the CRC character, it compares it with the contents of its own CRC registers. The two CRC characters should be identical. If they are not, an error has occurred in transmission, and the receiver can request that the sending terminal retransmit the block of data.

Although Fig.12 shows a circuit that generates a 16–bit CRC, 32–bit CRCs are also common in many data communication systems. Twelve–bit and 24–bit CRCs are used in some systems. Like the parity checker circuit, CRC generators are usually not separate circuits as shown in the figure. They are included in a larger integrated circuit that also performs other data communications functions.

Summary

In this chapter, we have looked at codes used in data communications and methods used to detect and sometimes correct errors. Of the codes presented in this chapter, the two that are most commonly used in data communications are ASCII and EBCDIC. Baudot is a 5–bit code, and it was the first code to be widely used for data communications. Baudot has two modes, a letters mode and a figures mode, each with its own character set. The LTRS and FIGS characters are used to shift back and forth between the two modes. Communications systems that once used Baudot have now almost all switched to the ASCII code.

ASCII is a 7–bit code, although a redundant 8–bit, called a parity bit, is sometimes added to detect errors. There is also an 8–bit version of ASCII which is called extended ASCII. ASCII is used both in data communications and to store data in personal computer memories and disks.

EBCDIC is an 8–bit code that was developed by IBM Corporation for use in its larger computers. EBCDIC is also used in equipment that was designed to be compatible with those IBM Computers.

Errors inevitably occur in data transmission. In some systems, those errors tolerated, and nothing is done to correct them. However, a number of schemes been developed to detect and sometimes correct errors. All of these methods are redundant information. In echoplex, the receiving terminal echoes each recent character back to the sending terminal where it appears on the terminal screen, i.e. terminal operator visually inspects each character to make sure that it is correct. Echoplex’s main use is to correct typing errors.

Parity is an extra bit that is added to each data character in the MSB position. The parity bit is set or cleared to ensure that each character either contains an even number of 1s or that each character contains an odd number of 1s. Parity is consequently used with the ASCII code.

A combination of horizontal and vertical parity checks cannot only detect errors, but also allow the receiver to correct single–bit errors, a process known as forward error correction (FEC). This system, in addition to having a parity bit each character, uses a binary check character (BCC) which is transmitted at the end of a block of data.

A checksum is no more than the least significant type of the arithmetical sum of all the binary characters transmitted in a block of data. Both the transmitter and the receiver calculate a checksum, and at the end of a transmission, the sending terminal transmits the checksum which the receiver then compares with its own checksum.

A cyclic redundancy check (CRC) character can be formed by circulating transmitted data through a system of shift registers and exclusive OR gates. Identical circuits are used at the transmitter and receiver. At the end of a block of data, a sending terminal transmits its CRC character, and the receiver compares it with the CRC character that it has generated. If the two CRC characters are different, then error has occurred.

Download