Forums

history of coding

Started by RichD June 10, 2019
Recently I attended a coding seminar.  The speaker 
very briefly reviewed the relevant history;  
first Hamming codes, ~1960: BCH codes, ~1970: convolutional, 
1995: polar, 2002:  LDPC

Clue me in - what was the advance in each case? 
I worked on a BCH project once, that seemed fairly 
efficient, how is it, or other algorithms, deficient?


--
Rich
RichD  <r_delaney2001@yahoo.com> wrote:

>Recently I attended a coding seminar. The speaker >very briefly reviewed the relevant history; >first Hamming codes, ~1960: BCH codes, ~1970: convolutional, >1995: polar, 2002: LDPC
>Clue me in - what was the advance in each case? >I worked on a BCH project once, that seemed fairly >efficient, how is it, or other algorithms, deficient?
I think you need to check out Berlekamp, "Key Papers in the Development of Coding Theory", IEEE Press. Especially the introduction. But, it does not cover developments as recent at Polar and modern LDPC codes. BCH codes were significant in that one could, for the first time, systematically construct native codes of a given redundancy and distance that had an algebraic decoding method. Steve
On Mon, 10 Jun 2019 12:51:17 -0700 (PDT), RichD
<r_delaney2001@yahoo.com> wrote:

>Recently I attended a coding seminar. The speaker >very briefly reviewed the relevant history; >first Hamming codes, ~1960: BCH codes, ~1970: convolutional, >1995: polar, 2002: LDPC > >Clue me in - what was the advance in each case? >I worked on a BCH project once, that seemed fairly >efficient, how is it, or other algorithms, deficient? > > >-- >Rich
You'll probably find different histories out there from different sources, as the lineage of some of these aren't all that clear. It's like asking when the FFT algorithm was invented...you may get vastly different answers. BTW, one of the biggest breakthroughs, Turbo Codes, aren't even mentioned, and they were the first case where somebody actually approached theoretical capacity with a practical code. Polar Codes were kind of an offshoot of that (one of many) that came much later. Turbo Codes were first published around 1994 and caused quite a flurry of research as a result. LDPCs, on the other hand, were published in 1963 by Gallagher, but weren't fully demonstrated to be capacity-approaching codes until after Turbo Codes were published and there was renewed interest in iterative decoding algorithms. Usually the motivations for different types of coding revolved on optimizing one or more of: Power efficiency - usually expressed as BER vs Eb/No - with Capacity being the benchmark metric Bandwidth Efficiency - Decent performance without high code overhead. Metrics here are a bit different as it involves a value judgement between the error efficiency metric and the bandwidth efficiency metric. Packet Error Rate (PER) or Block Error Rate (not to be confused with Bit Error Rate)- For many network or batch applications or applications with an access protocol, transmission error metrics may be more important than power efficiency metrics. Sometimes these metrics are more important for block-oriented codes. Complexity - If you can't build it or fit it in your system or the circuit takes too much power to run, it isn't of much value. This involves a judgement about various things, but it is an important consideration in many cases. I'm including power consumption in this tradeoff. Latency - If it takes forever to decode, it may not be useful. So the motivations that led to the "advances" in each may have been subtle or big or obvious or not, and sometimes were unrelated between different code types. Also, different codes work for different types of error distributions, e.g., block codes like BCH or Reed-Solomon tend to be used when there are clumped errors, but convolutional codes may be more desirable when the error rate is higher but the errors are more randomly distributed. Output error distributions matter, too, so there are all kinds of different evaluation criteria that get applied, and in any particular "innovation" it's important to understant what motivated the advance in order to understand where it may be or not be relevant. Anyway, it's a complex topic with a lot of interesting twists and perspectives and if you're really interested in it I'll suggest researching different histories. There were a number of good historical surveys published in the late 90s after Turbo Codes were getting accepted as finally having reached the Holy Grail of reaching Capacity, since that was recognized as a historically significant step. Some of those surveys did a really good job of capturing how the technology had advanced to that point...I wish I had a link or reference for you, but I don't.
On June 10, Eric Jacobsen wrote:
>>Recently I attended a coding seminar. The speaker >>very briefly reviewed the relevant history; >>first Hamming codes, ~1960: BCH codes, ~1970: convolutional, >>1995: polar, 2002: LDPC >> what was the advance in each case? > > one of the biggest breakthroughs, Turbo Codes, aren't even > mentioned, and they were the first case where somebody actually > approached theoretical capacity with a practical code.
Yes, my mistook, Turbo codes were invented in 1995. What's the key idea there? My understanding is that capacity requires exponentially long blocks, with commensurate decoding times.
> LDPCs, on the other hand, were published in 1963 by Gallagher, but > weren't fully demonstrated to be capacity-approaching codes until > after Turbo Codes were published and there was renewed interest in > iterative decoding algorithms.
Iterative decoding is also above my pay grade -
> Complexity - If you can't build it or fit it in your system or the > circuit takes too much power to run, it isn't of much value. This > involves a judgement about various things, but it is an important > consideration in many cases.
hmmmm... we're talking software, so if the digital hardware is given a priori, I don't see these considerations as substantial.
> Also, different codes work for different types > of error distributions, e.g., block codes like BCH or Reed-Solomon > tend to be used when there are clumped errors, but convolutional codes > may be more desirable when the error rate is higher but the errors are > more randomly distributed.
The convolutional codes are really challenging, with deep number theory roots, although the algorithms can be implemented in a recipe fashion... monkey see, monkey do...
> a number of good historical surveys published in the late 90s after > Turbo Codes were getting accepted as finally having reached the > Holy Grail of reaching Capacity, since that was recognized as a > historically significant step.
Something like a tutorial survey in a IEEE journal, "A history of coding theory" -- Rich
Eric Jacobsen <theman@ericjacobsen.org> wrote:

>BTW, one of the biggest breakthroughs, Turbo Codes, aren't even >mentioned, and they were the first case where somebody actually >approached theoretical capacity with a practical code. Polar Codes >were kind of an offshoot of that (one of many) that came much later. >Turbo Codes were first published around 1994 and caused quite a flurry >of research as a result. > >LDPCs, on the other hand, were published in 1963 by Gallagher, but >weren't fully demonstrated to be capacity-approaching codes until >after Turbo Codes were published and there was renewed interest in >iterative decoding algorithms.
Hi Eric, I knew you'd add to this thread. :-) Before turbo codes were first published, a bit earlier in the 90's people were getting more and more mileage from iterative decoding of either concatenated codes or product codes. (Concatenated codes in the case of the Deep Space Network, and product codes in optical storage). Chris Heegard has a good exposition of the Deep Space Network work at that time, which was necessitated by a high-gain antenna on one of the space probes failing to deploy. Steve
On Tue, 11 Jun 2019 23:11:05 +0000 (UTC), spope384@gmail.com (Steve
Pope) wrote:

>Eric Jacobsen <theman@ericjacobsen.org> wrote: > >>BTW, one of the biggest breakthroughs, Turbo Codes, aren't even >>mentioned, and they were the first case where somebody actually >>approached theoretical capacity with a practical code. Polar Codes >>were kind of an offshoot of that (one of many) that came much later. >>Turbo Codes were first published around 1994 and caused quite a flurry >>of research as a result. >> >>LDPCs, on the other hand, were published in 1963 by Gallagher, but >>weren't fully demonstrated to be capacity-approaching codes until >>after Turbo Codes were published and there was renewed interest in >>iterative decoding algorithms. > >Hi Eric, > >I knew you'd add to this thread. :-)
Couldn't stay away! ;)
>Before turbo codes were first published, a bit earlier in the 90's >people were getting more and more mileage from iterative decoding of >either concatenated codes or product codes. (Concatenated codes in the >case of the Deep Space Network, and product codes in optical storage). > >Chris Heegard has a good exposition of the Deep Space Network work >at that time, which was necessitated by a high-gain antenna on >one of the space probes failing to deploy.
Divsalar, et al, had tons of stories from JPL on deep space coding, including sending stuff out with encoders that they knew would be good but that they didn't quite have a decoding algorithm for yet. They figured they'd sort it out by the time the craft got far enough away that they needed to use that code. That worked out. Pretty cool.
On Mon, 10 Jun 2019 21:19:16 -0700 (PDT), RichD
<r_delaney2001@yahoo.com> wrote:

>On June 10, Eric Jacobsen wrote: >>>Recently I attended a coding seminar. The speaker >>>very briefly reviewed the relevant history; >>>first Hamming codes, ~1960: BCH codes, ~1970: convolutional, >>>1995: polar, 2002: LDPC >>> what was the advance in each case? >> >> one of the biggest breakthroughs, Turbo Codes, aren't even >> mentioned, and they were the first case where somebody actually >> approached theoretical capacity with a practical code. > >Yes, my mistook, Turbo codes were invented in 1995. >What's the key idea there? My understanding is that >capacity requires exponentially long blocks, with >commensurate decoding times.
That was one idea, but getting practical codes that worked close to capacity was always a bit of a Holy Grail. Turbo Codes were the first to demonstrate that it was possible, and since then a number of codes have been developed (e.g., TPCs, LDPCs, Polar, etc., etc.).
>> LDPCs, on the other hand, were published in 1963 by Gallagher, but >> weren't fully demonstrated to be capacity-approaching codes until >> after Turbo Codes were published and there was renewed interest in >> iterative decoding algorithms. > >Iterative decoding is also above my pay grade -
It's part of the secret sauce, along with soft-decision message-passing, that make the capacity approaching codes work.
>> Complexity - If you can't build it or fit it in your system or the >> circuit takes too much power to run, it isn't of much value. This >> involves a judgement about various things, but it is an important >> consideration in many cases. > >hmmmm... we're talking software, so if the digital >hardware is given a priori, I don't see these considerations >as substantial.
Implementation Complexity matters to software, too. If it can't be computed within a week, it's not a great option, e.g. ;)
>> Also, different codes work for different types >> of error distributions, e.g., block codes like BCH or Reed-Solomon >> tend to be used when there are clumped errors, but convolutional codes >> may be more desirable when the error rate is higher but the errors are >> more randomly distributed. > >The convolutional codes are really challenging, >with deep number theory roots, although the algorithms >can be implemented in a recipe fashion... monkey see, >monkey do...
>> a number of good historical surveys published in the late 90s after >> Turbo Codes were getting accepted as finally having reached the >> Holy Grail of reaching Capacity, since that was recognized as a >> historically significant step. > >Something like a tutorial survey in a IEEE journal, >"A history of coding theory" > >-- >Rich
On June 12, Eric Jacobsen wrote:
>> Yes, my mistook, Turbo codes were invented in 1995. >> What's the key idea there? My understanding is that >> capacity requires exponentially long blocks, with >> commensurate decoding times. > > That was one idea, but getting practical codes that worked close to > capacity was always a bit of a Holy Grail. Turbo Codes were the > first to demonstrate that it was possible, and since then a number of > codes have been developed (e.g., TPCs, LDPCs, Polar, etc., etc.). > >>> a number of good historical surveys published in the late 90s after >>> Turbo Codes were getting accepted as finally having reached the >>> Holy Grail of reaching Capacity, since that was recognized as a >>> historically significant step.
Can you recommend a reference on turbo codes, for self-study? -- Rich
RichD  <r_delaney2001@yahoo.com> wrote:

>Can you recommend a reference on turbo codes, for self-study?
You asked Eric but I'll chime in: Heegard and Wicker, _Turbo Coding_ . It is a no-nonsense reference, you can read it and in a couple days's time be able to write a simulation of a working turbo decoder. Steve
On 23.06.2019 4:30, Steve Pope wrote:
> RichD <r_delaney2001@yahoo.com> wrote: > >> Can you recommend a reference on turbo codes, for self-study? > > You asked Eric but I'll chime in: > > Heegard and Wicker, _Turbo Coding_ . It is a no-nonsense reference, > you can read it and in a couple days's time be able to write a > simulation of a working turbo decoder. > > > Steve >
It's an excellent reference! I would also suggest reading: Todd K. Moon, _Error Correction Coding: Mathematical Methods and Algorithms_ Rolf Johannesson, Kamil Sh. Zigangirov, _Fundamentals of Convolutional Coding_ Gene