Reduce memory utilization with sliding-window Viterbi decoding

[argilo]

Currently, approximately 60% (~18.7 MB) of nrsc5's memory utilization is taken up by Viterbi decoding (nrsc5_conv_decode). This is because Viterbi decoding is done in a single long pass on PDUs that can be hundreds of thousands of bits in length. The memory requirement could be vastly reduced by switching to a sliding-window Viterbi decoder which processes bits in small batches.

[TheDaChicken]

I do want to add that doing this can reduce the memory utilization to under almost ~5.12 kilobytes. The golden number apparently for a window is "5*(K−1)"

On FM, K is 7. With 16 bits ints, 64 trellis states. The amount of paths will be 2 * 64 * window size

[argilo]

I think that number is for the carryover between windows, but certainly the memory requirement will be orders of magnitude smaller.

[TheDaChicken]

From my understanding, you carry over 5*(K−1) items of state but ns * 5*(K−1) is how much possible paths to be taken. I could be wrong.

[TheDaChicken]

Ah. Yes, you are correct. You carry over ns * 5*(K−1) = W because those are considered good paths. The total paths is W * 16 bits + ns * W * 16 bits.

[ka9q]

Is the convolutional code punctured? Viterbi decoders for punctured codes require a somewhat longer path memory for the BER to asymptotically reach its minimum value.

[argilo]

Yes, NRSC-5 does use punctured codes. We'll keep that in mind if we switch to sliding-window decoding.