chapter 4

Coding of Data Signals

Chapter 3 explored techniques of transforming a continuous analog waveform

into a data signal. The present chapter assumes that we start with a data signal.

If data are transmitted through a channel and received at a remote point,

errors will occur occasionally. These errors are caused by the channel, and the

mechanism of this was discussed in Chap. 2. If each individual symbol in the

data signal were unrelated to every other symbol, an error in any one of them

would represent an error in the overall data signal. There would be no way to

correct the symbol error at the receiver. This is an undesirable situation.

It is possible to transform the data signal in a way that will reduce the

probability of data errors. This transformation is known as coding. We will

take a particular string of symbols representing a data signal and change it to

a different string of symbols. Before discussing the actual coding rules, it is

necessary to introduce some concepts from information theory. These are needed

to help assess the value of a particular coding scheme. We then establish some

limits upon code performance in order to put us in a position to evaluate the

efficiency of a particular code. Then we explore several particular classes of

coding, including block, Huffman, and convolutional codes. Finally, we examine

a particular species of code known as the cyclic code, which will prove most

important in data communications.

4.1 INFORMATION THEORY-INTRODUCTION

There are a number ofreasons for wanting to change the form ofa data (digital)

signal prior to transmission. In the case of English-language text, we start with

a data signal having about 40 distinct messages (the letters of the alphabet,

119
120 Coding of Data Signals Chap. 4

integers, and punctuation). We could transmit this using a signal alphabet

consisting of 40 distinct voltage waveforms. This is rarely done, for the follow­

ing reasons. First, the receiver would be complex, having to distinguish among

40 possible received signals. Second, with 40 possible received waveforms, the

receiver would often make a mistake i n distinguishing between messages. Third,

since some signals (e.g., those corresponding to e or space) occur much more

often than others, the transmission is inefficient, as we prove shortly. Yet

another reason for not sending letter by letter would occur if a degree of privacy

is required and one wished an unauthorized listener not to be able to listen in

on the conversation.

A more likely approach to sending text is to first decide upon an alphabet

of transmitted elements (perhaps this will be binary, with only two possible

elements), and then to code the various possible messages into code words com­

prised of elements from the alphabet. Let us restate the major reasons for

performing this coding operation: (1) to achieve higher transmission efficiency,

(2) to simplify the transmitter and receiver design, (3) to decrease errors, and (4)

to provide potential for privacy in transmission.

We concentrate upon two types of coding in this chapter: block and

convolutional. The student should be aware that entire textbooks are devoted

to coding, and one can approach the subject much more deeply than we intend

to do herein. Our intent in this chapter is to illustrate various techniques of

reducing data to binary information. Since we have previously learned to reduce

analog information to binary form (Chap. 3), following the current discussion

we will be in a position to spend some time exploring techniques of sending a

train of l ' s and O's.

4.2 MEASURE OF INFORMATION

The more information a message contains, the more work we are going to have

to do to transmit it from one point to another. Some nontechnical examples

should help to illustrate an intuitive concept of information prior to our rigorous

definition.

Suppose you enjoy Mexican cuisine. You enter your favorite restaurant

to order the following: one cheese enchilada, one beef taco, one order of beans,

one order of rice, two com tortillas, butter, a sprig of parsley, chopped green

onions, and a glass of water. Instead of this entire list being written out long­

hand, the person taking the order probably communicates something of the

form "one number 2 combination." Stop and think about this. Rather than

attempting to decide whether to transmit the specific words via English spelling

or by some form of shorthand, a much more basic approach has been taken.

Let us look at another example.

A popular form of communication is the telegram. Have you ever called

Western Union to send a wedding congratulations telegram? If so, you found

Sec. 4.2 Measure of Information 121

that they try to sell you a standard wording such as "Heartiest congratulations

upon the joining of two wonderful people. May your lives together be happy

and productive. A gift is being mailed under separate cover." In the early

days of telegraphy, the company noticed that many wedding telegrams sounded

almost identical to that presented above. A primitive approach to transmitting

this might be to send the message letter by letter. However, since the wording

is so predictable, why not have a short code for this message. For example,

let's call this particular telegram, "#79." The operator would then simply type

the name of the sender and of the addressee and then #79. At the receiver,

form #79 is pulled from the file and the address and signature are filled in.

Think of the amount of transmission time saved.

As yet a third example, consider the (atypical, I hope) university lecture

in which a professor stands before the class and proceeds to read directly from

the textbook for 2 hours. A great deal of time and effort could be saved if the

professor instead read the message "pages 103 to 120." In fact, if the class

expected this and knew they were past page 100, the professor could shorten

the message to "0320." The class could then read these 1 8 pages on their own

and get the same information. The professor could dismiss the class after 20

seconds and return to more scholarly endeavors.

I think that by now the point should be clear. A basic examination of the

information content of a message has the potential of saving considerable

effort in transmitting that message from one point to another.

Information and Entropy

The modest examples given at the start of this section indicate that, in an

intuitive sense, some relatively long messages do not contain a great deal of

information. Every detail of the restaurant order or the telegram is so com­

monplace that the person at the receiving end can almost guess what comes

next.

The concept of information content of a particular message must now be

formalized. After doing this, we shall find that the less information in a particular

message, the quicker we can communicate the message.

The concept of information content is related to predictability. That is,

the more probable a particular message, the less information is given by trans­

mitting that message. For example, if today were Tuesday and you phoned

someone to tell him or her tomorrow would be Wednesday, you would certainly

not be communicating any information. This is true since the probability of

that particular message is " I . "

The definition of information content should be such that it monotonically

decreases with increasing probability and goes to zero for a probability of

unity. Another property we would like this measure of information to have is

that of additivity. If one were to communicate two (independent) messages in

seque1;1ce, the total information content should be equal to the sum of the
122 Coding of Data Signals Chap, 4

individual information contents of the two messages. Now if the two messages

are independent, we know that the total probability of the composite message

is the product of the two individual probabilities. Therefore, the definition of

information must be such that when probabilities are multiplied together, the

corresponding informations are added. The logarithm satisfies this requirement.

We thus define the information content of a message x as Ix in Eq. (4-1):

(4-l)

In Eq. (4-l ), Px is the probability of occurrence of the message x. This definition

satisfies the additivity requirement, the monotonicity requirement, and for

P; = I , Ix = 0. Note that this is true regardless of the base chosen for the

logarithm.

We usually use base 2 for the logarithm. To understand the reason for

this choice, let us return to the restaurant example. Suppose that there were

only two selections on the menu. Further assume that past observation has

shown these two to be equally probable (i.e., each is ordered half of the time).

The probability of each message is therefore 1;, and if base 2 logarithms are

used in Eq. (4-1), the information content of each message is

I = log,
( I ,
T) = log, 2 = I

Thus, one unit of information is transmitted each time an order is placed.

Now let us think back to digital communication and decide upon an

efficient way to transmit this order. Since there are only two possibilities, one

binary digit could be used to send the order to the kitchen. A "O" could represent

the first dinner, and a " l , ' ' the second dinner on the menu.

Suppose that we now increase the number of items on the menu to four,

with each having a probability of ]. The information content of each message

is now log 4, or 2 units. If binary digits are used to transmit the order, 2 bits
2

would be required for each message. The various dinners would be coded as

00, 0 1 , IO, and II. We can therefore conclude that if the various messages are

equally probable, the information content of each message is exactly equal to

the minimum number of bits required to send the message. This is the reason

for commonly using base 2 logarithms, and, in fact, the unit of information is

called the bit of information. Thus, one would say that in the last example each

menu order contains 2 bits of information.

When all the possible messages are equally likely, the information content

of any single message is the same as that of any other message. In cases where

the probabilities are not equal, the information content depends upon which

particular message is being transmitted.

Entropy is defined as the average information per message. To calculate

the entropy, we take the various information contents associated with the

messages and weight each by the fraction of time we can expect that particular