Viterbi's contribution

Santosh:

The so-called VA or Viterbi Algorith for maximum likelihood sequence
estimation
is nothing more than the technique of traversing *all* paths through the
[decoding]
lattice while calculating and recording the probability of each path
matching the
correct one.

At the appropriate time the path with the highest probablility is chosen.
i.e. the VA
is simply an exhaustive search of all possible lattice paths to find the one
path most likely.

Of all the different techniques for mathematical optimization, exhaustive
search is the
least subtle and least efficient.  Examine *all* of the possible outcomes
and pick the
best one.   No shortcuts!

The so-called VA is not a very subtle method of optimization, but it's all
that is
available for this particular communications problem!

Taking nothing away from either of Andrew Viterbi or Dave Forney, but...
IMHO using
the "fancy" name ["VA"] for what is simply an "exhautive search" is
misleading to students
who first encounter it's use.  i.e. It would be better to tell simply tell
beginning students of
decoding methods, we "do an exhaustive search" rather than we "do the
Viterbi Algorithm".

Later one could tell the student that "do an exhaustive search of the
lattice" was
"named" the "Viterbi Algorithm" in honor of Andrew Viterbi by Dave Forney
since Viterbi
was the one who first proposed doing an exhaustive search of the lattice to
find the "best"
estimate for the transmitted sequence!

BTW... is that not what any simple minded lay person would have proposed
doing?
It surely doesn't take a Ph.D Professor to propose searching everything to
find the best!

The VA... a "tempest in a teapot", "much ado about nothing", or... "what's
in a name?"

I am sure that Andrew Viterbi would much rather have had Dave Forney name
any of his
other more important contributions to communications science after him.

BTW... I have the same complaint about the "name" Hertz [Hz], was not the
older
term "cycles per second" more appropriate and more easily understood by
beginning
students.

Yes I agree that we must "honor" the "Masters" but do we have to rename the
obvious?

Thoughts, comments?

:-)

--
Peter
Consultant
Indialantic By-the-Sea, FL.


"santosh nath" <santosh.nath@ntlworld.com> wrote in message
news:6afd943a.0308082323.3c6792a5@posting.google.com...
> "Peter Brackett" <ab4bc@ix.netcom.com> wrote in message
news:<bh1c9g$e7e$1@slb9.atl.mindspring.net>...
> > KBC:
> >
> > [snip]
> > "kbc" <kbc32@yahoo.com> wrote in message
> > news:a382521e.0308072354.234834dc@posting.google.com...
> > > What is Viterbi's claim to fame - only the Viterbi algorithm ?
> > >
> > > Has  he invented any  other theorem or circuit or algorithm ?
> > >
> > > He is a life fellow of ieee, right ?
> > >
> > > What criteria is there to  promote from fellow to life fellow ?
> > >
> > >               shankar
> > [snip]
> >
> > Andrew Viterbi has made many original contributions to communications
> > technology.
> >
> > Unfortunately the "one" which is named after him, the so-called "Viterbi
> > Algorithm" is not
> > a unique contribution of his, indeed it is not that unique.
> >
> > Dave Forney wrote an IEEE Proceeding's article which named this
algorithm
> > the "Viterbi
> > Algorithm".  Andrew Viterbi never called it that!
>
> Hi Peter,
>
> G. David Forney,Jr, a MIT Phd, is one of the pioneers of modern
> communication theory. Viterbi has to be grateful to him since he
> introduced the representation of convolutional codes by trellis
> diagrams, and proved the optimality of the Viterbi algorithm. I think
> he also introduced the idea of concatenated convolution codes and
> contributed towards serially concatenated codes(?). Turbo codes  , on
> the other handhand,  has paralell concatenation with intermidiate
> interleaver and gained the attention of the industry very rapidly. He
> is also one of the pioneers to introduce  veterbi equalizer (not same
> as decoder!!) to mitigate ISI from the fading channels.
>
> Secondly, why you guys are not mentioning Marcov(for Hidden Marcov
> Model) since
> Viterbi algorithm is  a special case of HMM with simple assumptions
> -is n't?
>
> Regards,
> Santosh
>
>
>
>
> >
> > The so-called "Viterbi Algorithm" which is a maximum likelihood sequence
> > estimation
> > algorthim is nothing more nor less than an "exhaustive search" of all
> > possible lattice
> > paths seeking the one with the maximum likelihood!  Not very subtle!
> > Exhaustive
> > search is the "dumbest" of all possible optimization methods.  This
> > technique of
> > "exhaustive search" of all possible solutions until the optimum is found
is
> > often called
> > "dynamic programming".  The so-called Viterbi Algorithm is nothing more
nor
> > less
> > than the "dynamic programming" or "exhaustive search" algorithm.
> >
> > Nothing unique, novel or subtle about it!  Just search over all possible
> > solutions
> > and then choose the one with the least cost!
> >
> > Just as with Einstein, who never won an award for "Relativity" but did
win
> > awards
> > for lesser  works, Andrew Viterbi is unfortunately remembered by having
his
> > name
> > attached to an algorithm which he did not invent and which was not even
> > novel
> > or unique, and this unfortunate circumstance was perpetrated by another
> > person
> > [Dave Forney] writing an article about the exhaustive search algorithm
and
> > calling
> > it the Viterbi Algorthim simply because Andrew Viterbi had suggested
doing
> > an
> > exhautive search!
> >
> > So much for celebrity.
> >
> > OTOH... any literature search will uncover the many unique contributions
of
> > Andrew Viterbi to communications sciences!  It's just that the only one
> > named
> > for him is not that important and was not even discovered or invented by
> > him!

On 9 Aug 2003 00:23:36 -0700, santosh.nath@ntlworld.com (santosh nath)
wrote:

>Hi Peter,
>
>G. David Forney,Jr, a MIT Phd, is one of the pioneers of modern
>communication theory. Viterbi has to be grateful to him since he
>introduced the representation of convolutional codes by trellis
>diagrams, and proved the optimality of the Viterbi algorithm. I think
>he also introduced the idea of concatenated convolution codes and
>contributed towards serially concatenated codes(?). Turbo codes  , on
>the other handhand,  has paralell concatenation with intermidiate
>interleaver and gained the attention of the industry very rapidly. He
>is also one of the pioneers to introduce  veterbi equalizer (not same
>as decoder!!) to mitigate ISI from the fading channels.

Santosh,

Code concatenation has been around for a long, long time, both
parallel and serial.   Turbo Codes come in both parallel and serial
flavors, and although they've gained a lot of attention they're still
not very widely used because of the complexity and latency issues
associated with them.  I think other codes may surpass Turbo Codes in
many applications in the future.

I think the contributions you were alluding to were mostly analysis
and performance related, not really seminally defining concatenation.


Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

kbc wrote:
> 
> i dont have half hour to spend on this.
> 
> what do u think is the purpose of a newsgroup ?

Whatever a newsgroup's purpose, it is not to save you ten minutes by
having five people spend ten minutes each. Keep in mind that comp.dsp is
not a subscription service. Every answer you get is from someone being
generous. I won't presume to speak for God, but I tend to help those who
at least try to help themselves.

Your question sounded very much like a veiled way to ask "Who the hell
is this Viterbi guy anyway, that he should be a Life Fellow of the
IEEE?" At any rate, disdain came across to me whether you intended it or
not. One is elected to the honor of Fellow for one's achievements. The
"Life" part comes automatically, from living long enough. I am a Life
Member of the IEEE. All that really means is that I don't have to pay
dues any more. (I'm also a charter member, but that's another matter.)

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
> Jerry Avins <jya@ieee.org> wrote in message news:<3F33D038.2241D50F@ieee.org>...
> > kbc wrote:
> > >
> > > What is Viterbi's claim to fame - only the Viterbi algorithm ?
> > >
> > > Has  he invented any  other theorem or circuit or algorithm ?
> > >
> > > He is a life fellow of ieee, right ?
> > >
> > > What criteria is there to  promote from fellow to life fellow ?
> > >
> > >               shankar
> >
> > Would you like me to teach you how to use Google? Viterbi's first name
> > is Andrew. Look it up.
> >
> > Jerry

Peter Brackett wrote:
> 
  ...
> 
> BTW... I have the same complaint about the "name" Hertz [Hz], was not the
> older
> term "cycles per second" more appropriate and more easily understood by
> beginning
> students.
> 
> Yes I agree that we must "honor" the "Masters" but do we have to rename the
> obvious?
> 
> Thoughts, comments?
> 
For the unit of frequency, it would have been better to honor Steinmetz,
the proponent of AC power distribution (Edison championed DC). Then we
could have used his initials and achieved continuity. His full name, of
course, was Charles Proteus Steinmetz.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

On Fri, 08 Aug 2003 20:38:21 -0400, Peter Brackett wrote:
> The so-called Viterbi Algorithm is nothing more nor less
> than the "dynamic programming" or "exhaustive search" algorithm.

Dynamic programming and exhaustive search are two different animals.

Exhaustive search does what the name says, and chooses the "best" out of
all possibilities.

Dynamic programming is an algorithm design technique for problems that
have overlapping subproblems.  The "programming" in this cases means that
there is some bookkeeping done that tracks progress, and guides the
algorithm for what to do next.

Basically, if a problem has non-overlapping subproblems, then
divide-and-conquer will be best.  If the subproblems overlap, then dynamic
programming will be best.  If there are no subproblems, then exhaustive
search is the only option.

-- 
Matthew Donadio (m.p.donadio@ieee.org)

eric.jacobsen@ieee.org (Eric Jacobsen) wrote in message news:<3f3555da.257141773@news.earthlink.net>...
> On 9 Aug 2003 00:23:36 -0700, santosh.nath@ntlworld.com (santosh nath)
> wrote:
> 
> >Hi Peter,
> >
> >G. David Forney,Jr, a MIT Phd, is one of the pioneers of modern
> >communication theory. Viterbi has to be grateful to him since he
> >introduced the representation of convolutional codes by trellis
> >diagrams, and proved the optimality of the Viterbi algorithm. I think
> >he also introduced the idea of concatenated convolution codes and
> >contributed towards serially concatenated codes(?). Turbo codes  , on
> >the other handhand,  has paralell concatenation with intermidiate
> >interleaver and gained the attention of the industry very rapidly. He
> >is also one of the pioneers to introduce  veterbi equalizer (not same
> >as decoder!!) to mitigate ISI from the fading channels.
> 
> Santosh,
> 
> Code concatenation has been around for a long, long time, both
> parallel and serial.   Turbo Codes come in both parallel and serial
> flavors, and although they've gained a lot of attention they're still
> not very widely used because of the complexity and latency issues
> associated with them.  I think other codes may surpass Turbo Codes in
> many applications in the future.



Hi Eric,

I have some points which could differ with you article.
We started with Viterbi algorithm- and I mentioned convolution
encoding as
serial or paralell concantention - the reason could be viterbi decoder
is the
most popular optimum decoding scheme for convolution encoders. Could
you name the person who claim to introduce serial concantention
convolution codes before G.D. Forney?

Paralell concantention convolution codes  is termed as "full turbo
coder" as introduced by Berrou et al. I think the term "full" refers
here  iterative
decoder having two APP detectors required for the turbo encoder only
and no other encoders and decoders are supposed to be introduced in
the system.

Now coming to serial concantention issue is rather interesting
investiagted by
Ryan et al for Partial response channel class4(PR4). Here, the outer
encoder is turbo encoder (so as if it is a single encoder) and inner
encoder is PR4 encoder and it is veiwed as a serial concantention. In
the decoding side turbo decoder is outer decoding unit and separate
APP is used for PR channel:

Requirement in PR4: 1. Two paralell convolution encoders and one PR4
encoder
                    2. Three APP detectors in decoding side.

If I am not wrong wideband DS-CDMA for UMTS uses "full turbo codes"
i.e paralell concantention as standard process(James also mentioned
the same thing).

Coming to complexity issue- I guess the Berrou group has come up with
decicated
turbo coder on ASIC so if the computation complexity is consumed by HW
then is it still a problem for commercialization? - I guess somebody
can update us more on the recent implemenations of the turbo coder.

santosh

> 
> I think the contributions you were alluding to were mostly analysis
> and performance related, not really seminally defining concatenation.
> 
> 
> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org

Jerry Avins <jya@ieee.org> wrote in message news:<3F356F53.4E1F3459@ieee.org>...
> Peter Brackett wrote:
> > 
>  ...
> > 
> > BTW... I have the same complaint about the "name" Hertz [Hz], was not the
> > older
> > term "cycles per second" more appropriate and more easily understood by
> > beginning
> > students.
> > 
> > Yes I agree that we must "honor" the "Masters" but do we have to rename the
> > obvious?
> > 
> > Thoughts, comments?
> > 
> For the unit of frequency, it would have been better to honor Steinmetz,
> the proponent of AC power distribution (Edison championed DC). Then we
> could have used his initials and achieved continuity. His full name, of
> course, was Charles Proteus Steinmetz.
> 
> Jerry

While I am sure there may be many opinions regarding what individuals 
should be honored in this fashion, using people's names for designating 
units isn't a very bad idea.

Names are international as opposed to "sentences" like "cycles per second".
I'm not sure "cycles per second" is as obvious to everyone who don't have
English as their native language (or at least people who's native languages 
don't belong to the indo-european family).

Rune

On Fri, 8 Aug 2003 21:42:26 -0400, "Clay S. Turner"
<physicsNOOOOSPPPPAMMMM@bellsouth.net> wrote:

>
>"Peter Brackett" <ab4bc@ix.netcom.com> wrote in message
>news:bh1c9g$e7e$1@slb9.atl.mindspring.net...
>> Just as with Einstein, who never won an award for "Relativity" but did win
>> awards
>> for lesser  works, > --
>> Peter
>> Consultant
>> Indialantic By-the-Sea, FL.
>>
>
>Peter,
>
>The example with Einstein is a bad one since the Nobel prize has an
>advancement of technology requirement which is much more appropriate to his
>explanation of the photoelectric effect, which is by the way what he won the
>Nobel prize for. While Lorentz and Poincare did a lot for the math behind
>relativity, Einstein took it much furthur than anyone else at the time and
>thusly did a lot of original work. But there was no application to
>technology (then) so there was no prize. So I wouldn't say he got the prize
>for a lessor work, but rather for a more applicable to the rules of the
>prize committee work.
>
>Clay

Hi Clay,
  I once read that Eistein was so confident that 
he'd win the next Nobel prize, that he included the 
not-yet-awarded prize money (to be given to his ex-wife) 
in his Divorce Decree.  

[-Rick-]

Part of Eric's message:
> > Santosh,
> > 
> > Code concatenation has been around for a long, long time, both
> > parallel and serial.   Turbo Codes come in both parallel and serial
> > flavors, and although they've gained a lot of attention they're still
> > not very widely used because of the complexity and latency issues
> > associated with them.  I think other codes may surpass Turbo Codes in
> > many applications in the future.

Part of Santosh's reply:> 
> Coming to complexity issue- I guess the Berrou group has come up with
> decicated
> turbo coder on ASIC so if the computation complexity is consumed by HW
> then is it still a problem for commercialization? - I guess somebody
> can update us more on the recent implemenations of the turbo coder.
> 
I guess I will be digressing  further from the original post. As Eric
said Turbo codes will be replaced. One potential candidate is Low
Density Parity Check Codes. You can do a quick search on LDPC in
IEEExplore. In summary LDPC codes are more easy to implement in
hardware due to the fact that they have massive parallelism.

Yes there are ASIC implementation of Turbo but they don't perform well
in terms of power. Turbo codes and low-density parity check (LDPC)
codes are two general classes of practical codes which can achieve
near Shannon limit ECC. Turbo codes received lot of attention but they
are computationally expensive to decode and don't support parallelism,
which is amenable to hardware implementation. There is a lot more room
for parallelism in the LDPC decoding than in the turbo-decoding
algorithm.

The research on finding better LDPC codes and adapting for them for
different wireless ,storage and network applications is getting
popular in academia(e.g. Texas A&M (wcl.tamu.edu), Berkeley
(http://bwrc.eecs.berkeley.edu) as well as in industry (eg.
Flarion,Agere)

-Choudhary

Rune Allnor wrote:

> Jerry Avins <jya@ieee.org> wrote in message news:<3F356F53.4E1F3459@ieee.org>...
> 
>>Peter Brackett wrote:
>>
>> ...
>>
>>>BTW... I have the same complaint about the "name" Hertz [Hz], was not the
>>>older
>>>term "cycles per second" more appropriate and more easily understood by
>>>beginning
>>>students.
>>>
>>>Yes I agree that we must "honor" the "Masters" but do we have to rename the
>>>obvious?
>>>
>>>Thoughts, comments?
>>>
>>
>>For the unit of frequency, it would have been better to honor Steinmetz,
>>the proponent of AC power distribution (Edison championed DC). Then we
>>could have used his initials and achieved continuity. His full name, of
>>course, was Charles Proteus Steinmetz.
>>
>>Jerry
> 
> 
> While I am sure there may be many opinions regarding what individuals 
> should be honored in this fashion, using people's names for designating 
> units isn't a very bad idea.
> 
> Names are international as opposed to "sentences" like "cycles per second".
> I'm not sure "cycles per second" is as obvious to everyone who don't have
> English as their native language (or at least people who's native languages 
> don't belong to the indo-european family).
> 

I think you missed the punch line there Rune - read the last sentence 
again. ;-)

(Of course young 'uns may never have heard of cps ;-)).

Paul