# [Ffmpeg-cvslog] r5438 - trunk/doc/TODO

Michael Niedermayer michaelni
Thu Jun 1 22:03:22 CEST 2006

```Hi

On Thu, Jun 01, 2006 at 08:40:12PM +0200, Michael Niedermayer wrote:
> Hi
>
> On Thu, Jun 01, 2006 at 08:48:28AM -0700, Mike Melanson wrote:
> > michael wrote:
> > >+- ADPCM: viterbi/trellis based optimal encoder
> >
>
> yes

to clarify this a little, ADPCM in general encodes differences beween
samples using a small number of possible difference values and adapts
which values are allowed depending upon past difference values
( ... we all know that)

all of our current ADPCM encoders work based on the principle that
we select the best possible difference between the last sample and
the current sample while we ignore 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

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
hmm, i am not happy with my explanation, i doubt thats overly easy to
understand :(

maybe a concrete example would help ...

lets say we have some input samples:    0,2,6,4,-4
and our example encoder can encode +4,+1,-1,+4 differences

our current style encoder would output: 0,1,5,4, 0 distortion=18
optimal would be:                       1,2,6,2,-2 distortion=9

if we would start our current encoder at 1 instead of 0 it would output:
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
0, 0           distortion 4
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
1, 2, 6, 6     distortion 5
5. iteration
not possibl,-6
not possibl,-5
not possibl,-4
not possibl,-3
1, 2, 6, 2,-2  distortion 9

[...]
--