Other Convolutional Decoding Algorithms

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.

7.5 OTHER CONVOLUTIONAL DECODING ALGORITHMS

         7.5.1 Sequential Decoding

Prior to the discovery of an optimum algorithm by Viterbi, other algorithms had been

proposed for decoding convolutional codes. The earliest was the sequential decoding

algorithm, originally proposed by Wozencraft [24, 25] and subsequently modified by

Fano [2]. A sequential decoder works by generating hypotheses about the transmitted

codeword sequence; it computes a metric between these hypotheses and the received

signal. It goes forward as long as the metric indicates that its choices are likely; otherwise,

it goes backward, changing hypotheses until, through a systematic trial-and-error

search, it finds a likely hypothesis. Sequential decoders can be implemented to work

with hard or soft decisions, but soft decisions are usually avoided because they greatly

increase the amount of the required storage and the complexity of the computations.

Consider that using the encoder shown in Figure 7.3, a sequence m = 1 1 0 1 1

is encoded into the codeword sequence U = 1 1 0 1 0 1 0 0 0 1, as shown in Example

7.1. Assume that the received sequence Z is, in fact, a correct rendition of U. The

decoder has available a replica of the encoder code tree, shown in Figure 7.6, and

can use the received sequence Z to penetrate the tree. The decoder starts at the

time t₁ node of the tree and generates both paths leaving that node. The decoder

follows that path which agrees with the received n code symbols. At the next level

in the tree, the decoder again generates both paths leaving that node, and follows

the path agreeing with the second group of n code symbols. Proceeding in this

manner, the decoder quickly penetrates the tree.

Suppose, however, that the received sequence Z is a corrupted version of U.

The decoder starts at the time t₁ node of the code tree and generates both paths

leading from that node. If the received n code symbols coincide with one of the

generated paths, the decoder follows that path. If there is not agreement, the decoder

follows the most likely path but keeps a cumulative count on the number of

disagreements between the received symbols and the branch words on the path

being followed. If two branches appear equally likely, the receiver uses an arbitrary

rule, such as following the zero input path. At each new level in the tree, the decoder

generates new branches and compares them with the next set of n received

code symbols. The search continues to penetrate the tree along the most likely path

and maintains the cumulative disagreement count.

If the disagreement count exceeds a certain number (which may increase as

we penetrate the tree), the decoder decides that it is on an incorrect path, backs out

of the path, and tries another. The decoder keeps track of the discarded pathways

to avoid repeating any path excursions. For example, assume that the encoder in

Figure 7.3 is used to encode the message sequence m = 1 1 0 1 1 into the codeword

sequence U as shown in Example 7.1. Suppose that the fourth and seventh bits of

the transmitted sequence U are received in error, such that:

Let us follow the decoder path trajectory with the aid of Figure 7.23. Assume

that a cumulative path disagreement count of 3 is the criterion for backing up and

trying an alternative path. On Figure 7.23 the numbers along the path trajectory

represent the current disagreement count.

1. At time t₁ we receive symbols 11 and compare them with the branch words

leaving the first node.

2. The most likely branch is the one with branch word 11 (corresponding to an

input bit one or downward branching), so the decoder decides that input bit

one is the correct decoding, and moves to the next level.

3. At time t₂, the decoder receives symbols 00 and compares them with the

available branch words 10 and 01 at this second level.

4. There is no “best” path, so the decoder arbitrarily takes the input bit zero (or branch

word 10) path, and the disagreement count registers a disagreement of 1.

5. At time t ₃, the decoder receives symbols 01 and compares them with the

available branch words 11 and 00 at this third level.

6. Again, there is no best path, so the decoder arbitrarily takes the input zero

(or branch word 11) path, and the disagreement count is increased to 2.

7. At time t₄, the decoder receives symbols 10 and compares them with the

available branch words 00 and 11 at this fourth level.

8. Again, there is no best path, so the decoder takes the input bit zero (or

branch word 00) path, and the disagreement count is increased to 3.

9. But a disagreement count of 3 is the turnaround criterion, so the decoder

“backs out” and tries the alternative path. The disagreement counter is reset

to 2.

10. The alternative path is the input bit one (or branch word 11) path at the t₄

level. The decoder tries this, but compared to the received symbols 10, there

is still a disagreement of 1, and the counter is reset to 3.

11. But, 3 being the turnaround criterion, the decoder backs out of this path, and

the counter is reset to 2. All of the alternatives have now been traversed at this

t₄ level, so the decoder returns to the node at t₃, and resets the counter to 1.

12. At the t₃ node, the decoder compares the symbols received at time t₃, namely

01, with the untried 00 path. There is a disagreement of 1, and the counter is

increased to 2.

                                     Figure 7.23 Sequential decoding example.

13. At the t₄ node, the decoder follows the branch word 10 that matches its t4

code symbols of 10. The counter remains unchanged at 2.

14. At the t₅ node, there is no best path, so the decoder follows the upper branch,

as is the rule, and the counter is increased to 3.

15. At this count, the decoder backs up, resets the counter to 2, and tries the

alternative path at node t₅. Since the alternate branch word is 00, there is a

disagreement of 1 with the received code symbols 01 at time t₅, and the

counter is again increased to 3.

16. The decoder backs out of this path, and the counter is reset to 2. All of the

alternatives have now been traversed at this t5 level, so the decoder returns to

the node at t₄ and resets the counter to 1.

17. The decoder tries the alternative path at t₄, which raises the metric to 3 since

there is a disagreement in two positions of the branch word. This time the

decoder must back up all the way to the time t₂ node because all of the

other paths at higher levels have been tried. The counter is now decremented

to zero.

18. At the t₂ node, the decoder now follows the branch word 01, and because

there is a disagreement of 1 with the received code symbols 00 at time t₂, the

counter is increased to 1.

The decoder continues in this way. As shown in Figure 7.23, the final path,

which has not increased the counter to its turnaround criterion, yields the correctly

decoded message sequence, 1 1 0 1 1. Sequential decoding can be viewed as a trialand-

error technique for searching out the correct path in the code tree. It performs

the search in a sequential manner, always operating on just a single path at a time.

If an incorrect decision is made, subsequent extensions of the path will be wrong.

The decoder can eventually recognize its error by monitoring the path metric. The

algorithm is similar to the case of an automobile traveler following a road map. As

long as the traveler recognizes that the passing landmarks correspond to those on

the map, he continues on the path. When he notices strange landmarks (an increase

in his dissimilarity metric) the traveler eventually assumes that he is on an incorrect

road, and he backs up to a point where he can now recognize the landmarks (his

metric returns to an acceptable range). He then tries an alternative road.

7.5.2 Comparisons and Limitations of Viterbi and Sequential Decoding

The major drawback of the Viterbi algorithm is that while error probability decreases

exponentially with constraint length, the number of code states, and consequently

decoder complexity, grows exponentially with constraint length. On the

other hand, the computational complexity of the Viterbi algorithm is independent

of channel characteristics (compared to hard-decision decoding, soft-decision decoding

requires only a trivial increase in the number of computations). Sequential

decoding achieves asymptotically the same error probability as maximum likelihood

decoding but without searching all possible states. In fact, with sequential de-

Figure 7.24 Bit error performance for various Viterbi and sequential decoding schemes using coherent BPSK over an AWGN channel. (Reprinted with permission from J. K. Omura and B. K. Levitt, “Coded Error Probability Evaluation forAntijam Communication Systems,” IEEE Trans. Commun., vol. COM30, no. 5, May 1982, Fig. 4, p. 900. © 1982 IEEE.)

coding the number of states searched is essentially independent of constraint length,

thus making it possible to use very large (K = 41) constraint lengths. This is an

important factor in providing such low error probabilities. The major drawback

of sequential decoding is that the number of state metrics searched is a random

variable. For sequential decoding, the expected number of poor hypotheses and

backward searches is a function of the channel SNR. With a low SNR, more

hypotheses must be tried than with a high SNR. Because of this variability in computational

load, buffers must be provided to store the arriving sequences. Under low

SNR, the received sequences must be buffered while the decoder is laboring to find

a likely hypothesis. If the average symbol arrival rate exceeds the average symbol

decode rate, the buffer will overflow, no matter how large it is, causing a loss of

data. The sequential decoder typically puts out error-free data until the buffer

overflows, at which time the decoder has to go through a recovery procedure. The

buffer overflow threshold is a very sensitive function of SNR. Therefore, an important

part of a sequential decoder specification is the probability of buffer overflow.

In Figure 7.24, some typical P_B versus E_b/N₀ curves for these two popular

solutions to the convolutional decoding problem, Viterbi decoding and sequential

decoding, illustrate their comparative performance using coherent BPSK over an

AWGN channel. The curves compare Viterbi decoding (rates 1/2 and 1/3 hard decision,

K = 7) versus Viterbi decoding (rates 1/2 and 1/3 soft decision, K = 7) versus sequential

decoding (rates 1/2 and 1/3 hard decision, K = 41). One can see from Figure 7.24 that

coding gains of approximately 8 dB at P_B = 10⁻⁶ can be achieved with sequential

decoders. Since the work of Shannon [26] foretold the potential of approximately

11 dB of coding gain compared to uncoded BPSK, it appears that the major portion

of what is theoretically possible can already be accomplished.

7.5.3 Feedback Decoding

A feedback decoder makes a hard decision on the data bit at stage j based on metrics

computed from stages j, j + 1, . . . , j + m, where m is a preselected positive integer.

Look-ahead length, L, is defined as L = m + 1, the number of received code

symbols, expressed in terms of the corresponding number of encoder input bits that

are used to decode an information bit. The decision of whether the data bit is zero

or one depends on which branch the minimum Hamming distance path traverses in

the look-ahead window from stage j to stage j + m. The detailed operation is best

understood in terms of a specific example. Let us consider the use of a feedback decoder

for the rate convolutional code shown in Figure 7.3. Figure 7.25 illustrates

the tree diagram and the operation of the feedback decoder for L = 3. That is, in

decoding the bit at branch j, the decoder considers the paths at branches j, j + 1,

and j + 2.

Beginning with the first branch, the decoder computes 2L or eight cumulative

Hamming path metrics and decides that the bit for the first branch is zero if the

minimum distance path is contained in the upper part of the tree, and decides one

if the minimum distance path is in the lower part of the tree. Assume that the received

sequence is Z = 1 1 0 0 0 1 0 0 0 1. We now examine the eight paths from

time t₁ through time t₃ in the block marked A in Figure 7.24, and compute metrics

comparing these eight paths with the first six received code symbols (three

branches deep times two symbols per branch). Listing the Hamming cumulative

path metrics (starting from the top path), we see that they are

                                              Upper-half metrics: 3, 3, 6, 4

                                              Lower-half metrics: 2, 2, 1, 3

We see that the minimum metric is contained in the lower part of the tree. Therefore,

the first decoded bit is one (characterized by a downward movement on the

tree). The next step is to extend the lower part of the tree (the part that survived)

                                      Figure 7.25 Feedback decoding example.

one stage deeper, and again compute eight metrics, this time from t₂ through t₄.

Having decoded the first two code symbols, we now slide over two code symbols to

the right and again compute the path metrics for six code symbols. This takes place

in the block marked B in Figure 7.25. Again, listing the metrics from top path to

bottom path, we find that they are

                                                 Upper-half metrics: 2, 4, 3, 3

                                                 Lower-half metrics: 3, 1, 4, 4

For the assumed received sequence, the minimum metric is found in the lower half

of block B. Therefore, the second decoded bit is one.

The same procedure continues until the entire message is decoded. The

decoder is called a feedback decoder because the detection decisions are fed back

to the decoder in determining the subset of code paths that are to be considered

next. On the BSC, the feedback decoder can perform nearly as well as the Viterbi

decoder [17] in that it can correct all the more probable error patterns, namely all

those of weight (d_f − 1)/2 or less, where d_f is the free distance of the code. An

important design parameter for feedback convolutional decoders is L, the lookahead

length. Increasing L increases the coding gain but also increases the decoder

implementation complexity.

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 »