Applying Viterbi algorithm to compensate for ISI in PSK31

Question

I am implementing a receiver for the amateur radio mode PSK31. It is effectively a BPSK modulation with a pulse shape of a raised cosine twice the width of one symbol. Here are four consecutive pulses, with 4 samples per symbol, as they would be transmitted:

The trouble is matched filtering introduces ISI. 4 pulses again, after a matched filter in the receiver:

If my understanding is correct, the issue here is one pulse is non-zero at the ideal decision point of the adjacent pulses.

However, my thinking is this is predictable, and the interference never extends beyond the adjacent symbols. So if the previous and next symbols are known the ISI can be cancelled by subtraction of the interfering adjacent pulses.

The trouble is the previous symbol isn't known with certainty. I think the Viterbi algorithm is a possible solution. And I've watched some videos on the algorithm and think I understand how the algorithm works, given a particular trellis.

What I don't understand is how to apply the Viterbi algorithm to this particular problem. The material I've found is either theoretical with math that blows my head off, or some other application of the algorithm. Could someone please provide an intuitive, practical explanation in this context?

Answer 1

(After some deliberation, I have a guess at answering my own question. Someone tell me if I'm wrong.)

The first step is to look at the contribution of each pulse at the decision point. The filter is normalized so a single pulse results in 1. And in this particular case, the tails of adjacent pulses work out to 1/6.

We can then look at any possible combination of three pulses, summing their contributions together. If we say the three pulses are $x_{n-1},\ x_{n},\ x_{n+1}$, then the output $y_n$ at the decision point is:

$$ y_n = 1/6\:x_{n-1} + x_{n} + 1/6\:x_{n+1}$$

To give some examples:

• 111: 1/6 + 1 + 1/6 = 1.33
• 010: -1/6 + 1 + -1/6 = 0.67
• 110: 1/6 + 1 + -1/6 = 1

Say state 01 means the previous bit was a 0, and the one before a 1. We can then ask, "if we add another bit, what does the output become?" For example, if the next bit is a zero that yields 001, with an output of -1 according to the formulation above.

We can then build a state table:

╔═══════╦═══════╦════════╗
║ input ║ state ║ output ║
╠═══════╬═══════╬════════╣
║     0 ║    00 ║ -1.33  ║
║     1 ║    00 ║ -1     ║
║     0 ║    01 ║ -1     ║
║     1 ║    01 ║ -0.67  ║
║     0 ║    10 ║ 0.67   ║
║     1 ║    10 ║ 1      ║
║     0 ║    11 ║ 1      ║
║     1 ║    11 ║ 1.33   ║
╚═══════╩═══════╩════════╝

And the associated trellis diagram:

The notation "0/-1.33" means "to send a 0 from this state, the output is -1.33".

Either the magnitude or the square of the difference between the observed values and the expected values can be used as the metric. The Viterbi algorithm will find the path through the trellis with the lowest metric regardless of what metric is used, as long as it's something that monotonically increases with the distance between observation and expected.

The Viterbi algorithm can then be followed in the usual way to determine the most likely sequence that explains the received signal, knowing how adjacent pulses will influence the received values.

I've found these videos especially helpful in understanding the evaluation of the Viterbi algorithm:

• Viterbi Algorithm, by AppBooke Xperience
• Viterbi Algorithm, by Keith Chugg