When is Viterbi's algorithm practical?

Question

Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

The internal state is kept in six memory registers. Each time another bit is input, the values in the registers are shifted to the right. For example, if 111 is input and the initial state is all zeros, then the internal state, written left to right, will become 100000, 110000, and 111000, after the first, second, and third bits have been input, respectively. The output bits will be 11, followed by 10, and then 01. It takes seven shifts to flush an input completely so that it does not affect the output. The constraint length of this code is thus $k=7$.

A convolutional code is decoded by finding the sequence of input bits that is most likely to have produced the observed sequence of output bits (which includes any errors). For small values of $k$, this is done with a widely used algorithm developed by Viterbi (Forney, 1973). The algorithm walks the observed sequence, keeping for each step and for each possible internal state the input sequence that would have produced the observed sequence with the fewest errors. The input sequence requiring the fewest errors at the end is the most likely message.

My question is about this part:

For small values of $k$, this is done with a widely used algorithm developed by Viterbi (Forney, 1973).

My question is how do they determine whether the value of $k$ is considered small or big? What is the threshold value for $k$? For example, length of this code is 7 and they considered it a small value. How about $10$? How about $20$? Are they considered small values or large values? I'm curious about the threshold value of $k$.

Answer 1

There is no threshold of $k$. Viterbi's algorithm has a certain complexity. For small enough $k$, you will be able to run Viterbi's algorithm on the given hardware at the given speed. For larger values of $k$, Viterbi's algorithm would be too slow. The exact threshold depends on your hardware (its capabilities, and how much "space" is available to implement the algorithm), and on the required speed. Viterbi's algorithm is optimal, and so it should probably be preferred over other algorithms when the constraints allow using it.