edVirtus Reference

What Is Viterbi Decoding?

What Is the Viterbi Algorithm?

Viterbi decoding is an error-correction technique used to recover information encoded by convolutional codes. It employs the Viterbi algorithm to determine the most likely transmitted sequence by examining all possible paths through a code trellis and selecting the one that best matches the received signal. Since its introduction by the American engineer Andrew J. Viterbi in 1967, the Viterbi algorithm has become one of the most important algorithms in digital communications and has been widely used in satellite communications, deep-space probes, mobile telephone systems, digital television, wireless local area networks, and numerous other communication systems.

The purpose of forward error correction (FEC) is to improve communication reliability by adding carefully designed redundancy before transmission. This redundancy allows the receiver to detect and correct errors introduced by noise, interference, fading, and other channel impairments. While block codes encode fixed blocks of data independently, convolutional codes operate continuously, generating parity bits from both the current information bit and a number of preceding bits stored within the encoder. This memory greatly improves error-correction capability but also makes decoding considerably more challenging.

A convolutional encoder can occupy many possible internal states depending upon the contents of its shift registers. As information bits enter the encoder, it moves from one state to another while producing a corresponding sequence of output symbols. At the receiver, the challenge is to determine which sequence of state transitions most likely produced the received signal, even when some of the transmitted bits have been corrupted by noise.

Andrew Viterbi solved this problem by recognising that the possible state transitions could be represented as a trellis diagram. A trellis is a graphical representation of every possible path that the encoder could follow as successive information bits are processed. Each branch corresponds to one possible state transition, while each node represents one of the encoder's possible internal states. The received signal therefore corresponds to one particular path through this trellis, although noise may obscure which path was actually taken.

Rather than examining every possible transmitted sequence individually—a computational task that rapidly becomes impossible for long messages—the Viterbi algorithm performs a highly efficient search. At each stage of the trellis, it calculates a branch metric representing how closely each possible transition matches the received signal. These branch metrics are accumulated into path metrics, which measure the total mismatch along each possible route through the trellis.

The key innovation of the algorithm is that it eliminates unlikely paths continuously as decoding progresses. Whenever two candidate paths arrive at the same state, only the path having the smaller accumulated metric is retained. The discarded path can never become more likely than the surviving path because both future paths from that state would be identical. This simple observation dramatically reduces the computational complexity while guaranteeing that the optimum solution is still obtained.

A useful analogy is navigating through a road network. Suppose several roads converge at the same town. If one route has already taken considerably longer than another to reach that town, there is no reason to continue considering it because every remaining journey from that point onward will be identical. The Viterbi algorithm follows exactly this principle, continually discarding inferior routes while retaining only the most promising candidates.

Eventually, after processing the complete received sequence, the decoder traces backward through the surviving path to recover the most likely transmitted information bits. This procedure is known as traceback. The resulting decoded sequence corresponds to the path having the minimum accumulated metric and therefore the highest probability of representing the original transmission.

One of the principal advantages of the Viterbi algorithm is that it provides maximum-likelihood decoding. Under the assumption of Additive White Gaussian Noise (AWGN), no other decoding algorithm can produce a more probable estimate of the transmitted sequence. This optimum performance made convolutional coding with Viterbi decoding the dominant error-control technique in many communication systems for several decades.

Viterbi decoders may operate using either hard-decision or soft-decision inputs. In hard-decision decoding, the demodulator first decides whether each received bit is a 0 or a 1 before passing the binary decisions to the decoder. The decoder therefore has access only to the bit values themselves. In soft-decision decoding, however, the demodulator also provides information describing the reliability of each received bit, often in the form of log-likelihood ratios (LLRs) or quantized confidence values. Because the decoder can exploit this additional information, soft-decision Viterbi decoding typically provides an improvement of approximately 2 dB compared with hard-decision decoding while using the same convolutional code.

The computational complexity of the Viterbi algorithm depends primarily on the constraint length of the convolutional code. Longer constraint lengths provide improved error-correction capability because the encoder possesses greater memory, but they also increase the number of trellis states and therefore the decoding complexity. Practical communication systems therefore select constraint lengths that provide an appropriate compromise between performance and implementation cost.

Viterbi decoding became particularly important in satellite communications during the 1980s and 1990s. The concatenation of an inner convolutional code decoded by the Viterbi algorithm with an outer Reed–Solomon code provided outstanding performance on noisy satellite channels. This concatenated coding structure was widely adopted in satellite television, digital broadcasting, deep-space communication, and early digital mobile telephone systems.

The algorithm also played a central role in second-generation cellular networks such as GSM, early CDMA systems, Wi-Fi, digital microwave links, and NASA's deep-space communication systems. Its combination of excellent error-correction performance and practical implementation made it one of the defining technologies of the digital communications revolution.

Although modern communication systems increasingly employ turbo codes, low-density parity-check (LDPC) codes, and polar codes, Viterbi decoding remains widely used in many applications requiring moderate block lengths, deterministic decoding latency, and proven reliability. Even where newer coding techniques have replaced convolutional codes, many of the concepts introduced by the Viterbi algorithm continue to influence modern iterative decoding methods.

Interestingly, the Viterbi algorithm has found important applications far beyond communications engineering. Variants of the algorithm are now used in speech recognition, natural language processing, bioinformatics, handwriting recognition, machine learning, digital signal processing, and computational biology. In each case, the objective is similar: determine the most likely sequence of hidden states that produced a sequence of observed measurements.

It is important to distinguish the Viterbi algorithm from convolutional coding. Convolutional coding is the encoding process that introduces redundancy into the transmitted signal. Viterbi decoding is the decoding algorithm that exploits this redundancy to recover the original information. The two are complementary components of the same error-control system.

Today, more than half a century after its invention, Viterbi decoding remains one of the landmark achievements of communications engineering. Its elegant combination of mathematical optimality and practical computational efficiency transformed convolutional coding from a theoretical concept into one of the most successful error-correction techniques ever developed. Few algorithms have had a greater impact on the reliability of modern digital communication systems.

The Viterbi algorithm therefore represents far more than a decoding technique. It demonstrated that sophisticated mathematical optimisation could be performed efficiently enough for real-time communication systems, enabling reliable digital communication over channels previously considered too noisy for practical operation. Its influence continues to extend well beyond communications engineering, making it one of the most significant algorithms of the twentieth century.