Viterbi's contribution

On 10 Aug 2003 02:08:10 -0700, santosh.nath@ntlworld.com (santosh
nath) wrote:

>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:

>> 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?

For the specific case of convolutional codes I don't know, but serial
concatenation of codes, which is all I was addressing, has been around
much longer than that.

>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.

I'm not quite sure what you're trying to say here.  I've never heard
the term "full turbo coder" before, and I don't know what an APP
detector is, either, especially not in the encoder.

APP decoders (also called MAP decoders, or implementations of the BCJR
algorithm) are typically used to decode convolutional turbo codes, but
that's true for both parallel and serial concatenated turbo codes with
convolutional constituent codes.

>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).

Yes, there is a 3GPP standardization of a parallel convolutional turbo
code, there is also a DVB-RCS standardization of a duo-binary
convolutional turbo code.  There may be others.

>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.

France Telecom started working with Berrou's students very early on
and there were ASIC solutions for turbo decoding quite a few years
ago.  Several used SOVA decoders instead of APPs in order to save
complexity, and these also reduced the performance a little bit.
There have been other silicon solutions since, and my group at a
previous employer built a hardware prototype for a flexible Turbo Code
for satellite applications about four years ago.  Hardware solutions
have been around, they've just not been efficient.  Turbo codes also
have the so-called "error floor" (which is really a slope change) and
this seems to prevent their acceptance in some applications.


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

On Sat, 09 Aug 2003 18:01:55 -0400, Jerry Avins <jya@ieee.org> wrote:

>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

An old boss of mine, who was quite a character, told me of CPS to
Hertz conversion charts that were popular during the transition in the
terminology.  Wags would hand them out to people as a joke and
statement regarding the intellect of the receiver;  one axis was on a
log scale and one on a linear so that the conversion was on a curve.

I always thought that was pretty funny, actually...


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:<3F356D97.2C9C7F4F@ieee.org>...

> 
> 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.


Troll  and hence ignoring.

Looks like you have some problem.

"kbc" <kbc32@yahoo.com> ha scritto nel messaggio
> Troll  and hence ignoring.
> Looks like you have some problem.
For sure, you are unable to quote decently, my dear, impolite
kbc32@yahoo.com

E.

Paul Russell <prussell@sonic.net> wrote in message news:<HzAZa.10394$dk4.415388@typhoon.sonic.net>...
> 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 ;-)).

I saw it, all right. 

Actually, I've seen old Norwegian documents that uses "cykler per sekund"
or "cps". Although "good" Norwegian ortography has changed quite a bit over 
the last century or so, I think "cps" appears somewhat artificial. I would 
have said "perioder per sekund", since "cykler" (plural of "cyclus") probably 
should be spelled "sykler", (Lat. cyclus -> Norw. syklus), which happens to 
be how the plural form of "sykkel" ("bicycle") is spelled.

Anyway, having a unit designated composed by initials of the honouree 
that by incident matches a nice acronym for an explanation of what's going 
on, would be nice. Provided one is familiar with the language the explanation 
is formulated in. I'm not sure I would very happy with such a convention if 
the language to be used would be Russian, Arabic or Chinese, which I don't 
know. 

Nah, I prefer the names.

Rune

> Paul

eric.jacobsen@ieee.org (Eric Jacobsen) wrote in message news:<3f36e7d7.359999617@news.earthlink.net>...
> On 10 Aug 2003 02:08:10 -0700, santosh.nath@ntlworld.com (santosh
> nath) wrote:
> 
> >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:
>  
> >> 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?
> 
> For the specific case of convolutional codes I don't know, but serial
> concatenation of codes, which is all I was addressing, has been around
> much longer than that.
> 
> >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.
> 
> I'm not quite sure what you're trying to say here.  I've never heard
> the term "full turbo coder" before, and I don't know what an APP
> detector is, either, especially not in the encoder.
> 
> APP decoders (also called MAP decoders, or implementations of the BCJR
> algorithm) are typically used to decode convolutional turbo codes, but
> that's true for both parallel and serial concatenated turbo codes with
> convolutional constituent codes.


I agree -it is not very popular to use detectors instead of decoders
for this particular system - the former one is more genric. But, some
papers  use  detector instead of decoder because of the following
probable reason:

Since turbo decoder is a decoding system itself containing two APP
decoders
it is not a bad idea two call them as detectors to distinguish from
system decoder. I guess I have not mentioned APP at encoder side -if
that means to
you it is my mistake of forming poor sentence.

Conclusion: detector and decoder carries the same meaning in my post.

"Full" means the encoding and  decoding system is entirely turbo
based. As I specified Ryan et al used separarte inner encoder serially
concatenated with
turbo encoder the system is an example of serial concatenation - but
it is mixed.

I am not sure whether Berrou originally proposed both paralell and
Serial concatenation turbo codes - I guess it was paralell only(!)

It would be interesting if you could tell something about performance
comparision of both serial and paralell turbo codes and also bit in
their
complexity sides.

Regards,
Santosh




> 
> >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).
> 
> Yes, there is a 3GPP standardization of a parallel convolutional turbo
> code, there is also a DVB-RCS standardization of a duo-binary
> convolutional turbo code.  There may be others.
> 
> >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.
> 
> France Telecom started working with Berrou's students very early on
> and there were ASIC solutions for turbo decoding quite a few years
> ago.  Several used SOVA decoders instead of APPs in order to save
> complexity, and these also reduced the performance a little bit.
> There have been other silicon solutions since, and my group at a
> previous employer built a hardware prototype for a flexible Turbo Code
> for satellite applications about four years ago.  Hardware solutions
> have been around, they've just not been efficient.  Turbo codes also
> have the so-called "error floor" (which is really a slope change) and
> this seems to prevent their acceptance in some applications.
> 
> 
> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org

In your case its apparent purpose is to give you an opportunity to piss 
people off by wasting their time!

Have a nice day!

Steve


kbc wrote:
> i dont have half hour to spend on this.
> 
> what do u think is the purpose of a newsgroup ?
> 
> 
> 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

The less neat something really is, is the more it needs a good name.

When someone says "how does your error handling work" do you really want 
to say "the receiver gropes around in the dark, trying endless 
possibilities, until it stumbles on its best guess at the actual 
transmitted data". Isn't "we use Viterbi techniques to evaluate the 
maximum likelihood sequence" better? Better still "we use Viterbi 
techniques to evaulate the MLS" avoids a phrase that still sounds like 
vague guessing.

Regards
Steve


Peter Brackett wrote:
> 
> 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!

Paul Russell wrote:
> 
> I think you missed the punch line there Rune - read the last sentence
> again. ;-)
> 
> (Of course young 'uns may never have heard of cps ;-)).

And speaking of punch-lines, for those who haven't heard of cps, I have
assembled a handy-dandy conversion chart:

http://leesburg.bittware.com/hz2cps.html

;-)

-- 
Jim Thomas            Principal Applications Engineer  Bittware, Inc
jthomas@bittware.com  http://www.bittware.com          (703) 779-7770
I'm a man.  But I can change.  If I have to.  I guess.  - Red Green

Jim Thomas wrote:

> And speaking of punch-lines, for those who haven't heard of cps, I have
> assembled a handy-dandy conversion chart:
> 
> http://leesburg.bittware.com/hz2cps.html

I guess, to convert noninteger Hz, like 100.5,
a linear interpolation would be enough... ;-)

bye,

-- 
   Piergiorgio Sartor