Forums

Viterbi's contribution

Started by kbc August 8, 2003
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. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
> 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. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
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