Structured Sequences

National Instruments has partnered with Prentice Hall to bring you large portions of in-depth technical topics from several PTR RF and Communications books, including Digital Communications: Fundamentals and Applications, 2nd Edition. This series of content is designed for a broad range of audiences, from experts who want to review a specific topic to students who need easy-to-understand documentation for their projects.

For the complete list of RF topics, please visit the RF and Communications Resource Main Page.

6.3 STRUCTURED SEQUENCES

In Section 4.8 we considered digital signaling by means of M = 2^k signal waveforms

(M-ary signaling), where each waveform contains k bits of information. We saw

that in the case of orthogonal M-ary signaling, we can decrease P_B by increasing M

(expanding the bandwidth). Similarly, in Section 6.1 we showed that it is possible to

decrease P_B by encoding k binary digits into one of M orthogonal codewords. The

major disadvantage with such orthogonal coding techniques is the associated inefficient

use of bandwidth. For an orthogonally coded set of M = 2^k waveforms, the required

transmission bandwidth is M/k times that needed for the uncoded case. In

this and subsequent sections we abandon the need for antipodal or orthogonal

properties and focus on a class of encoding procedures known as parity-check

codes. Such channel coding procedures are classified as structured sequences because

they represent methods of inserting structured redundancy into the source

data so that the presence of errors can be detected or the errors corrected. Structured

sequences are partitioned into three subcategories, as shown in Figure 6.1:

block, convolutional, and turbo. Block coding (primarily) is treated in this chapter,

and the others are treated in Chapters 7 and 8 respectively.

6.3.1 Channel Models

        6.3.1.1 Discrete Memoryless Channel

A discrete memoryless channel (DMC) is characterized by a discrete input

alphabet, a discrete output alphabet, and a set of conditional probabilities P( j|i)

(1 ≤ i ≤ M, 1 ≤ j ≤ Q), where i represents a modulator M-ary input symbol, j represents

a demodulator Q-ary output symbol, and P( j| i) is the probability of receiving

j given that i was transmitted. Each output symbol of the channel depends only on

the corresponding input, so that for a given input sequence U = u₁, u₂, . . . , u_m, . . . ,

^uN, the conditional probability of a corresponding output sequence Z = z₁, z₂, . . . ,

z_m, . . . , z_N may be expressed as

In the event that the channel has memory (i.e., noise or fading that occurs in

bursts), the conditional probability of the sequence Z would need to be expressed

as the joint probability of all the elements of the sequence. Equation (6.12) expresses

the memoryless condition of the channel. Since the channel noise in a memoryless

channel is defined to affect each symbol independently of all the other

symbols, the conditional probability of Z is seen as the product of the independent

element probabilities.

6.3.1.2 Binary Symmetric Channel

A binary symmetric channel (BSC) is a special case of a DMC; the input and

output alphabet sets consist of the binary elements (0 and 1). The conditional probabilities

are symmetric:

and

Equation (6.13) expresses the channel transition probabilities. That is, given that a

channel symbol was transmitted, the probability that it is received in error is p

(related to the symbol energy), and the probability that it is received correctly is

(1 − p). Since the demodulator output consists of the discrete elements 0 and 1, the

demodulator is said to make a firm or hard decision on each symbol. A commonly

used code system consists of BPSK modulated coded data and hard decision demodulation.

Then the channel symbol error probability is found using the methods

discussed in Section 4.7.1 and Equation (4.79) to be

                                               

where E_c/N₀ is the channel symbol energy per noise density, and Q(x) is defined in

Equation (3.43).

When such hard decisions are used in a binary coded system, the demodulator

feeds the two-valued code symbols or channel bits to the decoder. Since the decoder

then operates on the hard decisions made by the demodulator, decoding with

a BSC channel is called hard-decision decoding.

6.3.1.3 Gaussian Channel

We can generalize our definition of the DMC to channels with alphabets that

are not discrete. An example is the Gaussian channel with a discrete input alphabet

and a continuous output alphabet over the range . The channel adds noise

to the symbols. Since the noise is a Gaussian random variable with zero mean and

variance , the resulting probability density function (pdf) of the received random

variable z, conditioned on the symbol u_k (the likelihood of u_k), can be written as

for all z, where k = 1, 2, . . . , M. For this case, memoryless has the same meaning as

it does in Section 6.3.1.1, and Equation (6.12) can be used to obtain the conditional

probability for the sequence Z.

When the demodulator output consists of a continuous alphabet or its quantized

approximation (with greater than two quantization levels), the demodulator

is said to make soft decisions. In the case of a coded system, the demodulator feeds

such quantized code symbols to the decoder. Since the decoder then operates on

the soft decisions made by the demodulator, decoding with a Gaussian channel is

called soft-decision decoding.

In the case of a hard-decision channel, we are able to characterize the detection

process with a channel symbol error probability. However, in the case of a

soft-decision channel, the detector makes the kind of decisions (soft decisions) that

cannot be labeled as correct or incorrect. Thus, since there are no firm decisions,

there cannot be a probability of making an error; the detector can only formulate a

family of conditional probabilities or likelihoods of the different symbol types.

It is possible to design decoders using soft decisions, but block code softdecision

decoders are substantially more complex than hard-decision decoders;

therefore, block codes are usually implemented with hard-decision decoders. For

convolutional codes, both hard- and soft-decision implementations are equally

popular. In this chapter we consider that the channel is a binary symmetric channel

(BSC), and hence the decoder employs hard decisions. In Chapter 7 we further discuss

channel models, as well as hard- versus soft-decision decoding for convolutional

codes.

6.3.2 Code Rate and Redundancy

In the case of block codes, the source data are segmented into blocks of k data bits,

also called information bits or message bits; each block can represent any one of 2k

distinct messages. The encoder transforms each k-bit data block into a larger block

of n bits, called code bits or channel symbols. The (n − k) bits, which the encoder

adds to each data block, are called redundant bits, parity bits, or check bits; they

carry no new information. The code is referred to as an (n, k) code. The ratio of redundant

bits to data bits, denoted (n − k)/k, within a block is called the redundancy

of the code; the ratio of data bits to total bits, k/n, is called the code rate. The code

rate can be thought of as the portion of a code bit that constitutes information. For

example, in a rate 1/2 code, each code bit carries 1/2 bit of information.

In this chapter and in Chapters 7 and 8 we consider those coding techniques

that provide redundancy by increasing the required transmission bandwidth.

For example, an error control technique that employs a rate 1/2 code (100%

redundancy) will require double the bandwidth of an uncoded system. However, if

a rate 3/4 code is used, the redundancy is 33% and the bandwidth expansion is only

4/3. In Chapter 9 we consider modulation/coding techniques for bandlimited

channels where complexity instead of bandwidth is traded for error performance

improvement.

6.3.2.1 Code-Element Nomenclature

Different authors describe an encoder’s output elements in a variety of ways:

code bits, channel bits, code symbols, channel symbols, parity bits, parity symbols.

The terms are all very similar. In this text, for a binary code, the terms “code bit,”

“channel bit,” “code symbol,” and “channel symbol” have exactly the same meaning.

The terms “code bit” and “channel bit” are most descriptive for binary codes

only. The more generic names “code symbol” and “channel symbol” are often preferred

because they can be used to describe binary or nonbinary codes equally well.

Note that such code symbols or channel symbols are not to be confused with the

grouping of bits to form transmission symbols that was done in previous chapters.

The terms “parity bit” and “parity symbol” are used to identify only those code

elements that represent the redundancy components added to the original data.

6.3.3 Parity-Check Codes

        6.3.3.1 Single-Parity-Check Code

Parity-check codes use linear sums of the information bits, called parity symbols

or parity bits, for error detection or correction. A single-parity-check code is constructed

by adding a single-parity bit to a block of data bits. The parity bit takes on the

value of one or zero as needed to ensure that the summation of all the bits in the codeword

yields an even (or odd) result. The summation operation is performed using

modulo-2 arithmetic (exclusive-or logic), as described in Section 2.9.3. If the added

parity is designed to yield an even result, the method is termed even parity; if it is designed

to yield an odd result, the method is termed odd parity. Figure 6.8a illustrates

a serial data transmission (the rightmost bit is the earliest bit). A single-parity bit is

added (the leftmost bit in each block) to yield even parity.

At the receiving terminal, the decoding procedure consists of testing that the

modulo-2 sum of the codeword bits yields a zero result (even parity). If the result is

found to be one instead of zero, the codeword is known to contain errors. The rate of

the code can be expressed as k/(k + 1). Do you suppose the decoder can automatically

correct a digit that is received in error? No, it cannot. It can only detect the presence

of an odd number of bit errors. (If an even number of bits are inverted, the parity test

will appear correct, which represents the case of an undetected error.) Assuming that

 

Figure 6.8 Parity checks for serial and parallel code structures. (a) Serial structure. (b) Parallel structure.

 

all bit errors are equally likely and occur independently, we can write the probability

of j errors occurring in a block of n symbols as

where p is the probability that a channel symbol is received in error, and where

is the number of various ways in which j bits out of n may be in error. Thus, for a

single-parity error-detection code, the probability of an undetected error P_nd with a

block of n bits is computed as follows:

Example 6.1 Even-Parity Code

Configure a (4, 3) even-parity error-detection code such that the parity symbol

appears as the leftmost symbol of the codeword. Which error patterns can the code

detect? Compute the probability of an undetected message error, assuming that all

symbol errors are independent events and that the probability of a channel symbol

error is p=10⁻³.

Solution

The code is capable of detecting all single- and triple-error patterns. The probability

of an undetected error is equal to the probability that two or four errors occur anywhere

in a codeword.

6.3.3.2 Rectangular Code

A rectangular code, also called a product code, can be thought of as a parallel

code structure, depicted in Figure 6.8b. First we form a rectangle of message bits

comprising M rows and N columns; then, a horizontal parity check is appended to

each row and a vertical parity check is appended to each column, resulting in an

augmented array of dimensions (M + 1) × (N + 1). The rate of the rectangular code

k/n can then be written as

                                          

How much more powerful is the rectangular code than the single-parity code,

which is only capable of error detection? Notice that any single bit error will cause

a parity check failure in one of the array columns and in one of the array rows.

Therefore, the rectangular code can correct any single error pattern since such an

error is uniquely located at the intersection of the error-detecting row and the

error-detecting column. For the example shown in Figure 6.8b, the array dimensions

are M = N = 5; therefore, the figure depicts a (36, 25) code that can correct a

single error located anywhere in the 36-bit positions. For such an error-correcting

block code, we compute the probability that the decoded block has an uncorrected

error by accounting for all the ways in which a message error can be made. Starting

with the probability of j errors in a block of n symbols, expressed in Equation

(6.15), we can write the probability of a message error, also called a block error or

word error, for a code that can correct all t and fewer error patterns as

where p is the probability that a channel symbol is received in error. For the example

in Figure 6.8b, the code can correct all single error patterns (t = 1) within the

rectangular block of n = 36 bits. Hence, the summation in Equation (6.18) starts

with j = 2:

When p is reasonably small, the first term in the summation is the dominant one;

Therefore, for this (36, 25) rectangular code example, we can write

The bit error probability PB depends on the particular code and decoder. An approximation

for PB is given in Section 6.5.3.

6.3.4 Why Use Error-Correction Coding?

Error-correction coding can be regarded as a vehicle for effecting various system

trade-offs. Figure 6.9 compares two curves depicting bit-error performance versus

Figure 6.9 Comparison of typical coded versus uncoded error performance.

 

E_b/N₀. One curve represents a typical modulation scheme without coding. The

second curve represents the same modulation with coding. Demonstrated below

are four benefits or trade-offs that can be achieved with the use of channel coding.

6.3.4.1 Trade-Off 1: Error Performance versus Bandwidth

Imagine that a simple, inexpensive voice communication system has just been

developed and delivered to a customer. The system does not use error-correction

coding. Consider that the operating point of the system can be depicted by point A

in Figure 6.9 (E_b/N₀ = 8 dB, and P_B = 10⁻² ). After a few trials, there are complaints

about the voice quality; the customer suggests that the bit-error probability should

be lowered to 10⁻⁴. The usual way of obtaining better error performance in such a

system would be by effecting an operating point movement from point A to, say,

point B in Figure 6.9. However, suppose that the E_b/N₀ of 8 dB is the most that is

available in this system. The figure suggests that one possible trade-off is to move

the operating point from point A to point C. That is, “walking” down the vertical

line to point C on the coded curve can provide the customer with improved error

performance. What does it cost? Aside from the new components (encoder and decoder)

needed, the price is more transmission bandwidth. Error-correction coding

needs redundancy. If we assume that the system is a real-time communication

system (such that the message may not be delayed), the addition of redundant bits

dictates a faster rate of transmission, which of course means more bandwidth.

6.3.4.2 Trade-Off 2: Power versus Bandwidth

Consider that a system without coding, operating at point D in Figure 6.9

(E_b/N₀ = 14 dB, and P_B = 10⁻⁶), has been delivered to a customer. The customer has

no complaints about the quality of the data, but the equipment is having some

reliability problems as a result of providing an E_b /N₀ of 14 dB. In other words, the

equipment keeps breaking down. If the requirement on E_b /N₀ or power could be

reduced, the reliability difficulties might also be reduced. Figure 6.9 suggests a

trade-off by moving the operating point from point D to point E. That is, if errorcorrection

coding is introduced, a reduction in the required E_b /N₀ can be achieved.

Thus, the trade-off is one in which the same quality of data is achieved, but the

coding allows for a reduction in power or E_b /N₀. What is the cost? The same as

before—more bandwidth.

Notice that for non-real-time communication systems, error-correction coding

can be used with a somewhat different trade-off. It is possible to obtain improved

bit-error probability or reduced power (similar to trade-off 1 or 2 above) by paying

the price of delay instead of bandwidth.

6.3.4.3 Coding Gain

The trade-off example described in the previous section has allowed a reduction

in E_b /N₀ from 14 dB to 9 dB, while maintaining the same error performance.

In the context of this example and Figure 6.9, we now define coding gain. For a

given bit-error probability, coding gain is defined as the “relief” or reduction in

E_b/N₀ that can be realized through the use of the code. Coding gain G is generally

expressed in dB, such as

where (E_b /N₀)_u and (E_b /N₀)_c represent the required E_b /N₀, uncoded and coded,

respectively.

6.3.4.4 Trade-Off 3: Data Rate versus Bandwidth

Consider that a system without coding, operating at point D in Figure 6.9

(E_b/N₀ = 14 dB, and PB = 10⁻⁶) has been developed. Assume that there is no problem

with the data quality and no particular need to reduce power. However, in this

example, suppose that the customer’s data rate requirement increases. Recall the

relationship in Equation (5.20b):

                                                          

If we do nothing to the system except increase the data rate R, the above expression

shows that the received E_b/N₀ would decrease, and in Figure 6.9, the operating

point would move upwards from point D to, let us say, some point F. Now, envision

“walking” down the vertical line to point E on the curve that represents coded

modulation. Increasing the data rate has degraded the quality of the data. But, the

use of error-correction coding brings back the same quality at the same power level

(P_r /N₀). The E_b /N₀ is reduced, but the code facilitates getting the same error

probability with a lower E_b /N₀. What price do we pay for getting this higher data

rate or greater capacity? The same as before—increased bandwidth.

6.3.4.5 Trade-Off 4: Capacity versus Bandwidth

Trade-off 4 is similar to trade-off 3 because both achieve increased capacity.

A spread-spectrum multiple access technique, called code-division multiple access

(CDMA) and described in Chapter 12, is one of the schemes used in cellular telephony.

In CDMA, where users simultaneously share the same spectrum, each user

is an interferer to each of the other users in the same cell or nearby cells. Hence,

the capacity (maximum number of users) per cell is inversely proportional to

E_b/N₀. (See Section 12.8.) In this application, a lowered E_b/N₀ results in a raised capacity;

the code achieves a reduction in each user’s power, which in turn allows for

an increase in the number of users. Again, the cost is more bandwidth. But, in this

case, the signal-bandwidth expansion due to the error-correcting code is small compared

with the more significant spread-spectrum bandwidth expansion, and thus,

there is no impact on the transmission bandwidth.

In each of the above trade-off examples, a “traditional” code involving redundant

bits and faster signaling (for a real-time communication system) has been assumed;

hence, in each case, the cost was expanded bandwidth. However, there

exists an error-correcting technique, called trellis-coded modulation, that does not

require faster signaling or expanded bandwidth for real-time systems. (This technique

is described in Section 9.10.)

Example 6.2 Coded versus Uncoded Performance

Compare the message error probability for a communications link with and without

the use of error-correction coding. Assume that the uncoded transmission characteristics

are: BPSK modulation, Gaussian noise, P_r /N₀ = 43,776, data rate R = 4800 bits/s.

For the coded case, also assume the use of a (15, 11) error-correcting code that is capable

of correcting any single-error pattern within a block of 15 bits. Consider that the

demodulator makes hard decisions and thus feeds the demodulated code bits directly

to the decoder, which in turn outputs an estimate of the original message.

Solution

Following Equation (4.79), let  and 

be the uncoded and coded channel symbol error probabilities, respectively, where E_b/N₀ is the bit

energy per noise spectral density and E_c /N₀ is the code-bit energy per noise spectral density.

Without coding

and

where the following approximation of Q(x) from Equation (3.44) was used:

The probability that the uncoded message block P^u_M will be received in error is 1 minus

the product of the probabilities that each bit will be detected correctly. Thus,

With coding

Assuming a real-time communication system such that delay is unacceptable, the

channel-symbol rate or code-bit rate R_c is 15/11 times the data bit rate:

and

The E_c /N₀ for each code bit is less than that for the data bit in the uncoded case

because the channel-bit rate has increased, but the transmitter power is assumed to

be fixed:

It can be seen by comparing the results of Equation 6.20 with those of Equation

6.22 that because redundancy was added, the channel bit-error probability has degraded.

More bits must be detected during the same time interval and with the same

available power; the performance improvement due to the coding is not yet apparent.

We now compute the coded message error rate P^c_M, using Equation 6.18:

The summation is started with j = 2, since the code corrects all single errors

within a block of n = 15 bits. An approximation is obtained by using only the first term

of the summation. For p_c, we use the value calculated in Equation 6.22:

By comparing the results of Equation (6.21) with (6.23), we can see that the probability

of message error has improved by a factor of 58 due to the error-correcting code

used in this example. This example illustrates the typical behavior of all such real-time

communication systems using error-correction coding. Added redundancy means

faster signaling, less energy per channel symbol, and more errors out of the demodulator.

The benefits arise because the behavior of the decoder will (at reasonable values

of E_b/N₀) more than compensate for the poor performance of the demodulator.

6.3.4.6 Code Performance at Low Values of E_b/N₀

The reader is urged to solve Problem 6.5, which is similar to Example 6.2. In

part (a) of Problem 6.5, where an E_b/N₀ of 14 dB is given, the result is a messageerror

performance improvement through the use of coding. However, in part (b)

where the E_b/N₀ has been reduced to 10 dB, coding provides no improvement; in

fact, there is a degradation. One might ask, Why does part (b) manifest a degradation?

After all, the same procedure is used for applying the code in both parts of

the problem. The answer can be seen in the coded-versus-uncoded pictorial shown

in Figure 6.9. Even though Problem 6.5 deals with message-error probability, and

Figure 6.9 displays bit-error probability, the following explanation still applies. In

all such plots, there is a crossover between the curves (usually at some low value of

E_b/N₀). The reason for such crossover (threshold) is that every code system has

some fixed error-correcting capability. If there are more errors within a block than

the code is capable of correcting, the system will perform poorly. Imagine that

E_b/N₀ is continually reduced. What happens at the output of the demodulator?

It makes more and more errors. Therefore, such a continual decrease in E_b/N₀

must eventually cause some threshold to be reached where the decoder becomes

overwhelmed with errors. When that threshold is crossed, we can interpret the

degraded performance as being caused by the redundant bits consuming

energy but giving back nothing beneficial in return. Does it strike the reader

as a paradox that operating in a region (low values of E_b/N₀), where one would best

like to see an error-performance improvement, is where the code makes things

worse? There is, however, a class of powerful codes called turbo codes that provide

error-performance improvements at low values of E_b/N₀; the crossover point is

lower for turbo codes compared with conventional codes. (These are treated in

Section 8.4.)

Relevant NI products

Customers interested in this topic were also interested in the following NI products:

• RF and Communication Hardware and Software
  
• Other Modular Instruments (digital multimeters, digitizers, switching, etc...)
• LabVIEW Graphical Programming Environment

For the complete list of tutorials, return to the NI RF and Communications Fundamentals Main page.

Buy the Book

Purchase Digital Communications from Prentice Hall Professional through this link and receive the following:

• Between 15% and 30% Off
• Free Shipping and Handling

Reader Comments | Submit a comment »