Hi, Does anyone have any references on puncturing BCH codes? Is there a closed form solution for the effect puncturing has on a the codes minimum distance? Is puncturing even done on BCH codes? It seems puncturing a Reed-Solomon code is fairly common, but I am unable to find any mention of punctured BCH codes anywhere. thanks, -Sam
Puncturing BCH codes
Started by ●June 20, 2007
Reply by ●June 21, 20072007-06-21
On Jun 20, 6:36 pm, samke...@gmail.com wrote:> Hi, > > Does anyone have any references on puncturing BCH codes? Is there a > closed form solution for the effect puncturing has on a the codes > minimum distance? Is puncturing even done on BCH codes? It seems > puncturing a Reed-Solomon code is fairly common, but I am unable to > find any mention of punctured BCH codes anywhere.Punctures are treated as erasures at the receiver. BCH is a block code, therefore it is governed by the standard relationship: d_min >= 2v + e + 1 where v is the maximum correctable errors, and e is the number of erasures. See e.g. Section 3.4 of Lin & Costello, "Error Control Coding", 2nd ed. -- Oli
Reply by ●June 21, 20072007-06-21
Oli Charlesworth wrote:>>Does anyone have any references on puncturing BCH codes? Is there a >>closed form solution for the effect puncturing has on a the codes >>minimum distance? Is puncturing even done on BCH codes? It seems >>puncturing a Reed-Solomon code is fairly common, but I am unable to >>find any mention of punctured BCH codes anywhere. > > > Punctures are treated as erasures at the receiver. BCH is a block > code, therefore it is governed by the standard relationship: > > d_min >= 2v + e + 1It is not quite so simple. Puncturing is a sort of shortening of the code. The resultant code can have higher Dmin then the original code. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●June 21, 20072007-06-21
On Thu, 21 Jun 2007 10:30:25 -0500, Vladimir Vassilevsky <antispam_bogus@hotmail.com> wrote:> > >Oli Charlesworth wrote: > >>>Does anyone have any references on puncturing BCH codes? Is there a >>>closed form solution for the effect puncturing has on a the codes >>>minimum distance? Is puncturing even done on BCH codes? It seems >>>puncturing a Reed-Solomon code is fairly common, but I am unable to >>>find any mention of punctured BCH codes anywhere. >> >> >> Punctures are treated as erasures at the receiver. BCH is a block >> code, therefore it is governed by the standard relationship: >> >> d_min >= 2v + e + 1 > >It is not quite so simple. Puncturing is a sort of shortening of the >code. The resultant code can have higher Dmin then the original code.I'm used to Puncturing and Shortening meaning two different things for algebraic codes: If one deletes parity bits and substitutes erasures in the decoder, that's Puncturing. If one encodes with zeroes stuffed in some of the data bit field and then the codeword is transmitted without those zeroes, that's Shortening. In this case one doesn't need to substitute erasures since it was known that the encoding was done with zeroes, so the zeroes are replaced, with full confidence in a soft decoder. The effects can be characterized a bit differently. Clearly either reduces Dmin.> > >Vladimir Vassilevsky > >DSP and Mixed Signal Design Consultant > >http://www.abvolt.comEric Jacobsen Minister of Algorithms Abineau Communications http://www.ericjacobsen.org
Reply by ●June 21, 20072007-06-21
On Jun 21, 4:30 pm, Vladimir Vassilevsky <antispam_bo...@hotmail.com> wrote:> Oli Charlesworth wrote: > >>Does anyone have any references on puncturing BCH codes? Is there a > >>closed form solution for the effect puncturing has on a the codes > >>minimum distance? Is puncturing even done on BCH codes? It seems > >>puncturing a Reed-Solomon code is fairly common, but I am unable to > >>find any mention of punctured BCH codes anywhere. > > > Punctures are treated as erasures at the receiver. BCH is a block > > code, therefore it is governed by the standard relationship: > > > d_min >= 2v + e + 1 > > It is not quite so simple. Puncturing is a sort of shortening of the > code. The resultant code can have higher Dmin then the original code.Perhaps this is a misunderstanding in terminology, but I was under the impression that code shortening and puncturing were two different things. I understood "shortening" to be the use of a systematic (n, k) code, but where the first z input symbols are always zero, and therefore do not need to be transmitted. Therefore, we have a systematic (n-z, k- z) code, which has a d_min which is greater or equal to the original code. I understood "puncturing" to mean use of a systematic (n, k) code as normal, but then we only transmit (n-e) of the output symbols. At the receiver, the missing symbols are treated as erasures, which reduces the error-correction power by (e/2). Even if z=e for these two examples, their performance will not be the same. -- Oli
Reply by ●June 21, 20072007-06-21
On Jun 21, 6:34 pm, Eric Jacobsen <eric.jacob...@ieee.org> wrote:> On Thu, 21 Jun 2007 10:30:25 -0500, Vladimir Vassilevsky ><...snipped...>> > If one encodes with zeroes stuffed in some of the data bit field and > then the codeword is transmitted without those zeroes, that's > Shortening. In this case one doesn't need to substitute erasures > since it was known that the encoding was done with zeroes, so the > zeroes are replaced, with full confidence in a soft decoder. > > The effects can be characterized a bit differently. Clearly either > reduces Dmin.Shortening does not reduce d_min. All the transmitted codewords are members of the original (non-shortened) code, and so must be separated by at least d_min. -- Oli
Reply by ●June 21, 20072007-06-21
Eric Jacobsen wrote:>>>Punctures are treated as erasures at the receiver. BCH is a block >>>code, therefore it is governed by the standard relationship: >>> >>> d_min >= 2v + e + 1 >> >>It is not quite so simple. Puncturing is a sort of shortening of the >>code. The resultant code can have higher Dmin then the original code. > > > I'm used to Puncturing and Shortening meaning two different things for > algebraic codes: > > If one deletes parity bits and substitutes erasures in the decoder, > that's Puncturing.From the standpoint of the code properties, there is absolutely no difference which bits are deleted from the codeword. All bits are equivalent. What does matter is the resultant number of codewords after the deletion. If the number of codewords is less then in the original code, this is shortening. If it is equal to the original code, this is puncturing.> If one encodes with zeroes stuffed in some of the data bit field and > then the codeword is transmitted without those zeroes, that's > Shortening. In this case one doesn't need to substitute erasures > since it was known that the encoding was done with zeroes, so the > zeroes are replaced, with full confidence in a soft decoder. > > The effects can be characterized a bit differently. Clearly either > reduces Dmin.The shortening of the code can increase Dmin, because only a subset of the strongest words from the original code can be used. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant Napoleon of Science http://www.abvolt.com
Reply by ●June 21, 20072007-06-21
On Thu, 21 Jun 2007 11:55:57 -0700, Oli Charlesworth <catch@olifilth.co.uk> wrote:>On Jun 21, 6:34 pm, Eric Jacobsen <eric.jacob...@ieee.org> wrote: >> On Thu, 21 Jun 2007 10:30:25 -0500, Vladimir Vassilevsky >> ><...snipped...> >> >> If one encodes with zeroes stuffed in some of the data bit field and >> then the codeword is transmitted without those zeroes, that's >> Shortening. In this case one doesn't need to substitute erasures >> since it was known that the encoding was done with zeroes, so the >> zeroes are replaced, with full confidence in a soft decoder. >> >> The effects can be characterized a bit differently. Clearly either >> reduces Dmin. > >Shortening does not reduce d_min. All the transmitted codewords are >members of the original (non-shortened) code, and so must be separated >by at least d_min.Doh. That's correct. Shoulda thought a little longer... ;) I think Vladimir's actually right that shortening can increase Dmin by reducing the number of codewords used. Or at least it could be expected to reduce the average distance, since if Dmin was still between two codewords of the remaining set it wouldn't change. One could comfortably say that it improves the distance spectrum. ;) Eric Jacobsen Minister of Algorithms Abineau Communications http://www.ericjacobsen.org
Reply by ●June 21, 20072007-06-21
On Thu, 21 Jun 2007 21:45:37 GMT, Vladimir Vassilevsky <antispam_bogus@hotmail.com> wrote:> > >Eric Jacobsen wrote: > > >>>>Punctures are treated as erasures at the receiver. BCH is a block >>>>code, therefore it is governed by the standard relationship: >>>> >>>> d_min >= 2v + e + 1 >>> >>>It is not quite so simple. Puncturing is a sort of shortening of the >>>code. The resultant code can have higher Dmin then the original code. >> >> >> I'm used to Puncturing and Shortening meaning two different things for >> algebraic codes: >> >> If one deletes parity bits and substitutes erasures in the decoder, >> that's Puncturing. > > From the standpoint of the code properties, there is absolutely no >difference which bits are deleted from the codeword. All bits are >equivalent.It can matter depending on the decoder used. If the decoder treats erasures differently than errors (which some do), then one may benefit by judicious use of puncturing.>What does matter is the resultant number of codewords after the >deletion. If the number of codewords is less then in the original code, >this is shortening. If it is equal to the original code, this is >puncturing.That's another way to look at it, I suppose.>> If one encodes with zeroes stuffed in some of the data bit field and >> then the codeword is transmitted without those zeroes, that's >> Shortening. In this case one doesn't need to substitute erasures >> since it was known that the encoding was done with zeroes, so the >> zeroes are replaced, with full confidence in a soft decoder. >> >> The effects can be characterized a bit differently. Clearly either >> reduces Dmin. > >The shortening of the code can increase Dmin, because only a subset of >the strongest words from the original code can be used.That's true but I think one has to choose the codewords or shortening pattern carefully to assure that that remains true. If the codewords defining Dmin are still part of the reduced set then the shortening won't affect Dmin. The code performance could still be expected to improve due to improvement in the average distance or the distance spectrum, though.> > >Vladimir Vassilevsky > >DSP and Mixed Signal Design Consultant >Napoleon of Science > >http://www.abvolt.comEric Jacobsen Minister of Algorithms Abineau Communications http://www.ericjacobsen.org
