Coding Gain: (7,4) Hamming Code?

Started by Phil September 22, 2004
Main question:
- what is the coding gain for a (7,4) Hamming Code?

Additional questions:
- is there a web resource where tables (or some other format) can be
found containing coding gain info for Hamming and or other error
correction codes?
- are there texts that contain comprehensive tables of good codes and
their coding gains?

I'm not so interested in exotic codes that are mainly in academia or
used for space comms.

Regards,
Phil
D. R. E. Blahut, "Error-Correcting Codes for Digital Signal Processing".  Is
really good as far as I remember - got to be worth a try.

Best of Luck - Mike

"Phil" <phil_simulink@sympatico.ca> wrote in message
news:1f010577.0409221644.ffa2f43@posting.google.com...
> Main question: > - what is the coding gain for a (7,4) Hamming Code? > > Additional questions: > - is there a web resource where tables (or some other format) can be > found containing coding gain info for Hamming and or other error > correction codes? > - are there texts that contain comprehensive tables of good codes and > their coding gains? > > I'm not so interested in exotic codes that are mainly in academia or > used for space comms. > > Regards, > Phil
On an AWGN channel, at 10^-9 BER, about 0.5 dB coding gain. It's not a good 
code for this application.

    -- Tom


"Phil" <phil_simulink@sympatico.ca> wrote in message 
news:1f010577.0409221644.ffa2f43@posting.google.com...
> Main question: > - what is the coding gain for a (7,4) Hamming Code? > > Additional questions: > - is there a web resource where tables (or some other format) can be > found containing coding gain info for Hamming and or other error > correction codes? > - are there texts that contain comprehensive tables of good codes and > their coding gains? > > I'm not so interested in exotic codes that are mainly in academia or > used for space comms. > > Regards, > Phil
On 22 Sep 2004 17:44:19 -0700, phil_simulink@sympatico.ca (Phil)
wrote:

>Main question: >- what is the coding gain for a (7,4) Hamming Code?
As TOM mentioned, in AWGN it's not great. That's such a short code that one shouldn't expect much out of it, but you haven't mentioned an application or an expected channel. We're assuming AWGN.
>Additional questions: >- is there a web resource where tables (or some other format) can be >found containing coding gain info for Hamming and or other error >correction codes? >- are there texts that contain comprehensive tables of good codes and >their coding gains? > >I'm not so interested in exotic codes that are mainly in academia or >used for space comms. > >Regards, >Phil
Another good reference is Telecommunication Systems Engineering by Lindsey and Simon. It's a hard read, but has a lot of good reference stuff like code tables. I'm not sure whether this code is in there or not. Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
Good point.  I wasn't thinking very clearly when I made my original post.

The scenario under consideration is AWGN at a BER = 10^-3 for a coherent
BPSK system.

I'm going to see if I can get my hands on any of the references over the
weekend.

Regards,
Phil


"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message
news:415300bf.681469140@news.west.cox.net...
> On 22 Sep 2004 17:44:19 -0700, phil_simulink@sympatico.ca (Phil) > wrote: > > >Main question: > >- what is the coding gain for a (7,4) Hamming Code? > > As TOM mentioned, in AWGN it's not great. That's such a short code > that one shouldn't expect much out of it, but you haven't mentioned an > application or an expected channel. We're assuming AWGN. > > >Additional questions: > >- is there a web resource where tables (or some other format) can be > >found containing coding gain info for Hamming and or other error > >correction codes? > >- are there texts that contain comprehensive tables of good codes and > >their coding gains? > > > >I'm not so interested in exotic codes that are mainly in academia or > >used for space comms. > > > >Regards, > >Phil > > Another good reference is Telecommunication Systems Engineering by > Lindsey and Simon. It's a hard read, but has a lot of good reference > stuff like code tables. I'm not sure whether this code is in there or > not. > > Eric Jacobsen > Minister of Algorithms, Intel Corp. > My opinions may not be Intel's opinions. > http://www.ericjacobsen.org
"TOM" <noname@noprovider.nodomain> wrote in message 
news:QAA4d.11969$464.9955@trnddc01...
> On an AWGN channel, at 10^-9 BER, about 0.5 dB coding gain. It's not a > good code for this application. > > -- Tom
The asymptotic coding gain for a rate R code that corrects t errors is R(t+1) for hard-decision decoding which works out to 8/7 or nearly 0.58 dB for the (7,4) Hamming code.
On Fri, 24 Sep 2004 10:52:22 -0500, "Dilip V. Sarwate"
<sarwate@YouEyeYouSee.edu> wrote:

> >"TOM" <noname@noprovider.nodomain> wrote in message >news:QAA4d.11969$464.9955@trnddc01... >> On an AWGN channel, at 10^-9 BER, about 0.5 dB coding gain. It's not a >> good code for this application. >> >> -- Tom > > >The asymptotic coding gain for a rate R code that corrects t errors >is R(t+1) for hard-decision decoding which works out to 8/7 or >nearly 0.58 dB for the (7,4) Hamming code.
Dilip, what do use to do this sort of analysis? I'm always trying to figure out reasonable ways to estimate either capacity or gain as a function of rate and block length. Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message 
news:41545d1d.37163703@news.west.cox.net...
> On Fri, 24 Sep 2004 10:52:22 -0500, "Dilip V. Sarwate" > <sarwate@YouEyeYouSee.edu> wrote:
>>The asymptotic coding gain for a rate R code that corrects t errors >>is R(t+1) for hard-decision decoding which works out to 8/7 or >>nearly 0.58 dB for the (7,4) Hamming code. > > Dilip, what do use to do this sort of analysis? I'm always trying to > figure out reasonable ways to estimate either capacity or gain as a > function of rate and block length.
Drawing from R. E. Blahut's Algebraic Codes for Data Transmission book (Cambridge Univ. Press), Chapter 12, the argument is essentially as follows. For DPSK, the BER is exponentially decreasing (of the form exp(-E/No)). However, for coded DPSK, this formula gives the raw error rate on the channel, and the E to be used is actually R.Eb where R is the code rate. If the code corrects t errors, (t << n), then the word error rate (probability decoder output dataword is incorrect) is dominated by the probability that there are t+1 channel errors, which has probability (n choose t+1) p^{t+1} (1-p)^{n-t-1} which is for all practical purposes of the form p^{t+1} = [exp(-R.Eb/No)]^{t+1} = exp(-R(t+1).Eb/No). The BER is bounded above by the word error rate, and so for a given BER specification, the coded system requires an SNR (Eb/No) smaller by a factor R(t+1) which is the coding gain. Hope this helps. (If not, wave hands vigorously while re-reading the argument... :-) )
Dilip,

Thanks for the explanation.  I have seen a similar relationship (Gc Rc*dmin) in "Communication Systems Engineering" by Proakis and Salehi, but
the 'why' was not clear.

I'll be waving my hands this evening when I re-read your post.

Phil


"Dilip V. Sarwate" <sarwate@YouEyeYouSee.edu> wrote in message
news:cj1pgd$9km$1@news.ks.uiuc.edu...
> > "Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message > news:41545d1d.37163703@news.west.cox.net... > > On Fri, 24 Sep 2004 10:52:22 -0500, "Dilip V. Sarwate" > > <sarwate@YouEyeYouSee.edu> wrote: > > >>The asymptotic coding gain for a rate R code that corrects t errors > >>is R(t+1) for hard-decision decoding which works out to 8/7 or > >>nearly 0.58 dB for the (7,4) Hamming code. > > > > Dilip, what do use to do this sort of analysis? I'm always trying to > > figure out reasonable ways to estimate either capacity or gain as a > > function of rate and block length. > > Drawing from R. E. Blahut's Algebraic Codes for Data Transmission > book (Cambridge Univ. Press), Chapter 12, the argument is essentially > as follows. For DPSK, the BER is exponentially decreasing (of the form > exp(-E/No)). However, for coded DPSK, this formula gives the raw > error rate on the channel, and the E to be used is actually R.Eb where > R is the code rate. If the code corrects t errors, (t << n), then the
word
> error rate (probability decoder output dataword is incorrect) is dominated > by the probability that there are t+1 channel errors, which has
probability
> (n choose t+1) p^{t+1} (1-p)^{n-t-1} which is for all practical purposes > of the form p^{t+1} = [exp(-R.Eb/No)]^{t+1} = exp(-R(t+1).Eb/No). > The BER is bounded above by the word error rate, and so for a given > BER specification, the coded system requires an SNR (Eb/No) > smaller by a factor R(t+1) which is the coding gain. > > Hope this helps. (If not, wave hands vigorously while re-reading the > argument... :-) ) > >
Dilip,

Thanks for that.  I don't work with (n,k,t) type codes with a fixed
correcting capability enough to have thought of this, but it makes
sense.  For more general codes, like CC or LDPC or whatever, it's
still a problem to try to sort this stuff out.

Cheers,

Eric

On Fri, 24 Sep 2004 13:37:01 -0500, "Dilip V. Sarwate"
<sarwate@YouEyeYouSee.edu> wrote:

> >"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message >news:41545d1d.37163703@news.west.cox.net... >> On Fri, 24 Sep 2004 10:52:22 -0500, "Dilip V. Sarwate" >> <sarwate@YouEyeYouSee.edu> wrote: > >>>The asymptotic coding gain for a rate R code that corrects t errors >>>is R(t+1) for hard-decision decoding which works out to 8/7 or >>>nearly 0.58 dB for the (7,4) Hamming code. >> >> Dilip, what do use to do this sort of analysis? I'm always trying to >> figure out reasonable ways to estimate either capacity or gain as a >> function of rate and block length. > >Drawing from R. E. Blahut's Algebraic Codes for Data Transmission >book (Cambridge Univ. Press), Chapter 12, the argument is essentially >as follows. For DPSK, the BER is exponentially decreasing (of the form >exp(-E/No)). However, for coded DPSK, this formula gives the raw >error rate on the channel, and the E to be used is actually R.Eb where >R is the code rate. If the code corrects t errors, (t << n), then the word >error rate (probability decoder output dataword is incorrect) is dominated >by the probability that there are t+1 channel errors, which has probability >(n choose t+1) p^{t+1} (1-p)^{n-t-1} which is for all practical purposes >of the form p^{t+1} = [exp(-R.Eb/No)]^{t+1} = exp(-R(t+1).Eb/No). >The BER is bounded above by the word error rate, and so for a given >BER specification, the coded system requires an SNR (Eb/No) >smaller by a factor R(t+1) which is the coding gain. > >Hope this helps. (If not, wave hands vigorously while re-reading the >argument... :-) ) > >
Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
Dilip,

Thanks for that.  I don't work with (n,k,t) type codes with a fixed
correcting capability enough to have thought of this, but it makes
sense.  For more general codes, like CC or LDPC or whatever, it's
still a problem to try to sort this stuff out.

Cheers,

Eric

On Fri, 24 Sep 2004 13:37:01 -0500, "Dilip V. Sarwate"
<sarwate@YouEyeYouSee.edu> wrote:

> >"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message >news:41545d1d.37163703@news.west.cox.net... >> On Fri, 24 Sep 2004 10:52:22 -0500, "Dilip V. Sarwate" >> <sarwate@YouEyeYouSee.edu> wrote: > >>>The asymptotic coding gain for a rate R code that corrects t errors >>>is R(t+1) for hard-decision decoding which works out to 8/7 or >>>nearly 0.58 dB for the (7,4) Hamming code. >> >> Dilip, what do use to do this sort of analysis? I'm always trying to >> figure out reasonable ways to estimate either capacity or gain as a >> function of rate and block length. > >Drawing from R. E. Blahut's Algebraic Codes for Data Transmission >book (Cambridge Univ. Press), Chapter 12, the argument is essentially >as follows. For DPSK, the BER is exponentially decreasing (of the form >exp(-E/No)). However, for coded DPSK, this formula gives the raw >error rate on the channel, and the E to be used is actually R.Eb where >R is the code rate. If the code corrects t errors, (t << n), then the word >error rate (probability decoder output dataword is incorrect) is dominated >by the probability that there are t+1 channel errors, which has probability >(n choose t+1) p^{t+1} (1-p)^{n-t-1} which is for all practical purposes >of the form p^{t+1} = [exp(-R.Eb/No)]^{t+1} = exp(-R(t+1).Eb/No). >The BER is bounded above by the word error rate, and so for a given >BER specification, the coded system requires an SNR (Eb/No) >smaller by a factor R(t+1) which is the coding gain. > >Hope this helps. (If not, wave hands vigorously while re-reading the >argument... :-) ) > >
Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
Dilip,

Thanks for the explanation.  I have seen a similar relationship (Gc Rc*dmin) in "Communication Systems Engineering" by Proakis and Salehi, but
the 'why' was not clear.

I'll be waving my hands this evening when I re-read your post.

Phil


"Dilip V. Sarwate" <sarwate@YouEyeYouSee.edu> wrote in message
news:cj1pgd$9km$1@news.ks.uiuc.edu...
> > "Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message > news:41545d1d.37163703@news.west.cox.net... > > On Fri, 24 Sep 2004 10:52:22 -0500, "Dilip V. Sarwate" > > <sarwate@YouEyeYouSee.edu> wrote: > > >>The asymptotic coding gain for a rate R code that corrects t errors > >>is R(t+1) for hard-decision decoding which works out to 8/7 or > >>nearly 0.58 dB for the (7,4) Hamming code. > > > > Dilip, what do use to do this sort of analysis? I'm always trying to > > figure out reasonable ways to estimate either capacity or gain as a > > function of rate and block length. > > Drawing from R. E. Blahut's Algebraic Codes for Data Transmission > book (Cambridge Univ. Press), Chapter 12, the argument is essentially > as follows. For DPSK, the BER is exponentially decreasing (of the form > exp(-E/No)). However, for coded DPSK, this formula gives the raw > error rate on the channel, and the E to be used is actually R.Eb where > R is the code rate. If the code corrects t errors, (t << n), then the
word
> error rate (probability decoder output dataword is incorrect) is dominated > by the probability that there are t+1 channel errors, which has
probability
> (n choose t+1) p^{t+1} (1-p)^{n-t-1} which is for all practical purposes > of the form p^{t+1} = [exp(-R.Eb/No)]^{t+1} = exp(-R(t+1).Eb/No). > The BER is bounded above by the word error rate, and so for a given > BER specification, the coded system requires an SNR (Eb/No) > smaller by a factor R(t+1) which is the coding gain. > > Hope this helps. (If not, wave hands vigorously while re-reading the > argument... :-) ) > >
"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message 
news:41545d1d.37163703@news.west.cox.net...
> On Fri, 24 Sep 2004 10:52:22 -0500, "Dilip V. Sarwate" > <sarwate@YouEyeYouSee.edu> wrote:
>>The asymptotic coding gain for a rate R code that corrects t errors >>is R(t+1) for hard-decision decoding which works out to 8/7 or >>nearly 0.58 dB for the (7,4) Hamming code. > > Dilip, what do use to do this sort of analysis? I'm always trying to > figure out reasonable ways to estimate either capacity or gain as a > function of rate and block length.
Drawing from R. E. Blahut's Algebraic Codes for Data Transmission book (Cambridge Univ. Press), Chapter 12, the argument is essentially as follows. For DPSK, the BER is exponentially decreasing (of the form exp(-E/No)). However, for coded DPSK, this formula gives the raw error rate on the channel, and the E to be used is actually R.Eb where R is the code rate. If the code corrects t errors, (t << n), then the word error rate (probability decoder output dataword is incorrect) is dominated by the probability that there are t+1 channel errors, which has probability (n choose t+1) p^{t+1} (1-p)^{n-t-1} which is for all practical purposes of the form p^{t+1} = [exp(-R.Eb/No)]^{t+1} = exp(-R(t+1).Eb/No). The BER is bounded above by the word error rate, and so for a given BER specification, the coded system requires an SNR (Eb/No) smaller by a factor R(t+1) which is the coding gain. Hope this helps. (If not, wave hands vigorously while re-reading the argument... :-) )
On Fri, 24 Sep 2004 10:52:22 -0500, "Dilip V. Sarwate"
<sarwate@YouEyeYouSee.edu> wrote:

> >"TOM" <noname@noprovider.nodomain> wrote in message >news:QAA4d.11969$464.9955@trnddc01... >> On an AWGN channel, at 10^-9 BER, about 0.5 dB coding gain. It's not a >> good code for this application. >> >> -- Tom > > >The asymptotic coding gain for a rate R code that corrects t errors >is R(t+1) for hard-decision decoding which works out to 8/7 or >nearly 0.58 dB for the (7,4) Hamming code.
Dilip, what do use to do this sort of analysis? I'm always trying to figure out reasonable ways to estimate either capacity or gain as a function of rate and block length. Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
"TOM" <noname@noprovider.nodomain> wrote in message 
news:QAA4d.11969$464.9955@trnddc01...
> On an AWGN channel, at 10^-9 BER, about 0.5 dB coding gain. It's not a > good code for this application. > > -- Tom
The asymptotic coding gain for a rate R code that corrects t errors is R(t+1) for hard-decision decoding which works out to 8/7 or nearly 0.58 dB for the (7,4) Hamming code.
Good point.  I wasn't thinking very clearly when I made my original post.

The scenario under consideration is AWGN at a BER = 10^-3 for a coherent
BPSK system.

I'm going to see if I can get my hands on any of the references over the
weekend.

Regards,
Phil


"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message
news:415300bf.681469140@news.west.cox.net...
> On 22 Sep 2004 17:44:19 -0700, phil_simulink@sympatico.ca (Phil) > wrote: > > >Main question: > >- what is the coding gain for a (7,4) Hamming Code? > > As TOM mentioned, in AWGN it's not great. That's such a short code > that one shouldn't expect much out of it, but you haven't mentioned an > application or an expected channel. We're assuming AWGN. > > >Additional questions: > >- is there a web resource where tables (or some other format) can be > >found containing coding gain info for Hamming and or other error > >correction codes? > >- are there texts that contain comprehensive tables of good codes and > >their coding gains? > > > >I'm not so interested in exotic codes that are mainly in academia or > >used for space comms. > > > >Regards, > >Phil > > Another good reference is Telecommunication Systems Engineering by > Lindsey and Simon. It's a hard read, but has a lot of good reference > stuff like code tables. I'm not sure whether this code is in there or > not. > > Eric Jacobsen > Minister of Algorithms, Intel Corp. > My opinions may not be Intel's opinions. > http://www.ericjacobsen.org
On 22 Sep 2004 17:44:19 -0700, phil_simulink@sympatico.ca (Phil)
wrote:

>Main question: >- what is the coding gain for a (7,4) Hamming Code?
As TOM mentioned, in AWGN it's not great. That's such a short code that one shouldn't expect much out of it, but you haven't mentioned an application or an expected channel. We're assuming AWGN.
>Additional questions: >- is there a web resource where tables (or some other format) can be >found containing coding gain info for Hamming and or other error >correction codes? >- are there texts that contain comprehensive tables of good codes and >their coding gains? > >I'm not so interested in exotic codes that are mainly in academia or >used for space comms. > >Regards, >Phil
Another good reference is Telecommunication Systems Engineering by Lindsey and Simon. It's a hard read, but has a lot of good reference stuff like code tables. I'm not sure whether this code is in there or not. Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
On an AWGN channel, at 10^-9 BER, about 0.5 dB coding gain. It's not a good 
code for this application.

    -- Tom


"Phil" <phil_simulink@sympatico.ca> wrote in message 
news:1f010577.0409221644.ffa2f43@posting.google.com...
> Main question: > - what is the coding gain for a (7,4) Hamming Code? > > Additional questions: > - is there a web resource where tables (or some other format) can be > found containing coding gain info for Hamming and or other error > correction codes? > - are there texts that contain comprehensive tables of good codes and > their coding gains? > > I'm not so interested in exotic codes that are mainly in academia or > used for space comms. > > Regards, > Phil
D. R. E. Blahut, "Error-Correcting Codes for Digital Signal Processing".  Is
really good as far as I remember - got to be worth a try.

Best of Luck - Mike

"Phil" <phil_simulink@sympatico.ca> wrote in message
news:1f010577.0409221644.ffa2f43@posting.google.com...
> Main question: > - what is the coding gain for a (7,4) Hamming Code? > > Additional questions: > - is there a web resource where tables (or some other format) can be > found containing coding gain info for Hamming and or other error > correction codes? > - are there texts that contain comprehensive tables of good codes and > their coding gains? > > I'm not so interested in exotic codes that are mainly in academia or > used for space comms. > > Regards, > Phil
Main question:
- what is the coding gain for a (7,4) Hamming Code?

Additional questions:
- is there a web resource where tables (or some other format) can be
found containing coding gain info for Hamming and or other error
correction codes?
- are there texts that contain comprehensive tables of good codes and
their coding gains?

I'm not so interested in exotic codes that are mainly in academia or
used for space comms.

Regards,
Phil