Lair Of The Multimedia Guru

2006-06-02

Optimal (A)DPCM encoding

ADPCM in general encodes differences between samples using a small number of possible difference values and adapts which values are allowed depending upon past difference values
( … we all know that)

ADPCM encoders normally work based on the principle that they select the best possible difference between the last sample and the current sample while ignoring both future and past, thats not optimal at all

a viterbi based encoder would select the optimal sequence of differences which minimize some distortion measure like the sum of squares, it achives this by successively finding the optimal encodings up to a specific state or in other words
instead of keeping a single sequence of encoded differenes of the past samples and then encoding the next difference
we keep track of the optimal sequence of differences/encoded bitstream up to the current sample for every state (0..88 step + a few sample values around the ideal one) next we just calculate the optimal bitstreams up to the next sample using the current sample and the optimal ones up to the last sample

maybe a concrete example would help, we use non adaptive DPCM here but the principle is the same …

lets say we have some input samples 0,2,6,4,-4
and our example encoder can encode +4,+1,-1,-4 differences
a conventional encoder would output 0,1,5,4, 0 distortion=18
optimal would be 1,2,6,2,-2 distortion=9
if we would force the first output to 1 and then use a conventional encoder 1,2,6,5, 1 distortion=27

viterbi encoder:

1. iteration
-2              distortion 4
-1              distortion 1
 0              distortion 0
 1              distortion 1
 2              distortion 4
2. iteration
 1, 0           distortion 5
 0, 1           distortion 1
 1, 2           distortion 1
-1, 3           distortion 2
 0, 4           distortion 4
3. iteration
-1, 3, 4        distortion 6
 0, 1, 5        distortion 2
 1, 2, 6        distortion 1
-1, 3, 7        distortion 3
 0, 4, 8        distortion 8
4. iteration
 1, 2, 6, 2     distortion 5
-1, 3, 7, 3     distortion 4
 0, 1, 5, 4     distortion 2
 1, 2, 6, 5     distortion 2
 0, 1, 5, 6     distortion 6
5. iteration
not possibl,-6
not possibl,-5
not possibl,-4
not possibl,-3
 1, 2, 6, 2,-2  distortion 9
Filed under: Uncategorized — Michael @ 20:18

Powered by WordPress