Forums

Practical differences between BCH and Reed-Solomon codes?

Started by gct July 30, 2009
So I've got a Reed-Solomon codec that will work for a range of code
parameters, and I'm looking to extend it (or at least use it as a starting
point) for a binary BCH decoder that is similarly flexible.  I thought I'd
bounce my understanding of the practical differences between BCH and RS
codes off of comp.dsp to see if I'm missing any important points.


Primary Difference 1:
To calculate the generator polynomial for Reed-Solomon, you can simply
build a polynomial that has roots at powers of alpha from a^m0 to
a^(m0+2*T-1) where alpha is a primitive element in the field.  

For BCH, however, you calculate the generator as the least-common-multiple
of the minimal polynomials associated with the first 2*T powers of alpha
(where the minimal polynomial has coefficients in GF(2) and is the
lowest-degree polynomial p(x) where p(a^i) == 0)

Once you have the generator polynomials, encoding is the same for both,
neglecting the difference in symbol sizes.  


Primary Difference 2:
For syndrome calculation in RS, it's sufficient to treat the codeword as a
polynomial and evaluate it at a^i to calculate Si (1 < i < 2*T).  This can
be accomplished easily with a bank of 2*T MACCs in the finite field.

For BCH, you have to calculate the syndrome polynomials as Si(x) = v(x)
mod Mi(x) where Mi is again the minimal polynomial for a^i and v(x) is the
received codeword.  With those calculated, you can then evaluate each Si(x)
at a^i to get the syndrome values.

My understanding is then I can use those syndrome values with the same
Berlekamp-Massey algorithm used in Reed-Solomon to calculate the
error-locator (presumably with an optional erasure locator as a seed). 
Once I have the error locator L(x), I can find the roots, which tell me the
locations of the errors, and then flip the bits at those locations to
correct the codewords.

Does this sound right?  Have I missed any important details?
On Jul 30, 4:59&#2013266080;pm, "gct" <smcal...@gmail.com> wrote:
<material snipped>
> > Primary Difference 2: > For syndrome calculation in RS, it's sufficient to treat the codeword as a > polynomial and evaluate it at a^i to calculate Si (1 < i < 2*T). &#2013266080;This can > be accomplished easily with a bank of 2*T MACCs in the finite field.
I don't know what MACC means, but general-purpose finite-field multipliers are *not* needed for syndrome evaluation. In syndrome calculations, one input to each multiplier is fixed, and so the multiplier structure simplifies considerably (it is just a bunch of XOR gates instead of lots of AND gates and XOR gates)
> For BCH, you have to calculate the syndrome polynomials as Si(x) = v(x) > mod Mi(x) where Mi is again the minimal polynomial for a^i and v(x) is the > received codeword. &#2013266080;With those calculated, you can then evaluate each Si(x) > at a^i to get the syndrome values.
It is not *necessary* to find v(x) mod Mi(x), though of course it is perfectly OK to do so. You can evaluate v(x) at a^i just as with RS codes. Look at things like latency in addition to hardware costs and evaluate the trade-offs carefully. Hope this helps Dilip Sarwate
>On Jul 30, 4:59=A0pm, "gct" <smcal...@gmail.com> wrote: ><material snipped> >> >> Primary Difference 2: >> For syndrome calculation in RS, it's sufficient to treat the codeword
as =
>a >> polynomial and evaluate it at a^i to calculate Si (1 < i < 2*T).
=A0This =
>can >> be accomplished easily with a bank of 2*T MACCs in the finite field. > >I don't know what MACC means, but general-purpose finite-field >multipliers are *not* needed for syndrome evaluation. In syndrome >calculations, one input to each multiplier is fixed, and so the >multiplier structure simplifies considerably (it is just a bunch of >XOR gates instead of lots of AND gates and XOR gates) >
MACC is just Multiply-ACCumulate (in the finite field), and you're absolutely right about the constant-variable multipliers. I just let my synthesis tools take care of the constant folding ;)
>> For BCH, you have to calculate the syndrome polynomials as Si(x) =3D
v(x)
>> mod Mi(x) where Mi is again the minimal polynomial for a^i and v(x) is
th=
>e >> received codeword. =A0With those calculated, you can then evaluate each
S=
>i(x) >> at a^i to get the syndrome values. > >It is not *necessary* to find v(x) mod Mi(x), though of course >it is perfectly OK to do so. You can evaluate v(x) at a^i just as >with RS codes. Look at things like latency in addition to >hardware costs and evaluate the trade-offs carefully. >
Ah that is surprising, I haven't been able to find many good sources on BCH codes online (and of course my digital comms book is at a friends house), that's good to know though.
>Hope this helps > >Dilip Sarwate >
gct <smcallis@gmail.com> wrote:

> Dilip Sarwate wrote,
>>On Jul 30, 4:59=A0pm, "gct" <smcal...@gmail.com> wrote:
>>> For BCH, you have to calculate the syndrome polynomials >>> as Si(x) = v(x) mod Mi(x) where Mi is again the minimal >>> polynomial for a^i and v(x) is the received codeword. With >>> those calculated, you can then evaluate each > S= i(x) at a^i >>> to get the syndrome values.
>>It is not *necessary* to find v(x) mod Mi(x), though of course >>it is perfectly OK to do so. You can evaluate v(x) at a^i just as >>with RS codes. Look at things like latency in addition to >>hardware costs and evaluate the trade-offs carefully.
Yet a third, slightly different approach is to calculate the remainder v(x) mod G(x), where G is the code generator, and then evaluate this remainder at each a^i. This can be attractive if the code rate is high.
>Ah that is surprising, I haven't been able to find many good sources on >BCH codes online (and of course my digital comms book is at a friends >house), that's good to know though.
The description in Lin and Costello is pretty straightforward, but any of the standard texts will cover this adequately. Steve
On Jul 30, 7:28&#2013266080;pm, spop...@speedymail.org (Steve Pope) wrote:

> Yet a third, slightly different approach is to calculate the > remainder v(x) mod G(x), where G is the code generator, and > then evaluate this remainder at each a^i. &#2013266080;This can be attractive > if the code rate is high.
The issue with regard to the "divide by Mi(x)" or "divide by G(x)" approaches is one of latency. It takes n clock cycles to do either type of division if the bits are entering the decoder serially. **Then** the remainder has to be evaluated at a^i (typically by Horner's rule) which requires a *further* deg Mi or deg G clock cycles. On the other hand, evaluating v(x) at a^i via Horner's rule requires n clock cycles only, and we are done. As is common in legal circles, time is usually of the essence, which is why I suggested that looking at latency *and* hardware complexity and evaluating the tradeoffs carefully is worthwhile. If one is programming a general-purpose microprocessor or, God forbid, MATLAB to do the calculations, then the "divide by Mi(x)" or "divide by G(x)" can be more efficient, but for VLSI implementation, the "evaluate v(x) at a^i directly" approach is likely to be the best. --Dilip Sarwate
>On Jul 30, 7:28=A0pm, spop...@speedymail.org (Steve Pope) wrote: > >> Yet a third, slightly different approach is to calculate the >> remainder v(x) mod G(x), where G is the code generator, and >> then evaluate this remainder at each a^i. =A0This can be attractive >> if the code rate is high. > >The issue with regard to the "divide by Mi(x)" or "divide by G(x)" >approaches is one of latency. It takes n clock cycles to do >either type of division if the bits are entering the decoder serially. >**Then** the remainder has to be evaluated at a^i (typically by >Horner's rule) which requires a *further* deg Mi or deg G clock >cycles. On the other hand, evaluating v(x) at a^i via Horner's >rule requires n clock cycles only, and we are done. As is >common in legal circles, time is usually of the essence, which is >why I suggested that looking at latency *and* hardware complexity >and evaluating the tradeoffs carefully is worthwhile. > >If one is programming a general-purpose microprocessor >or, God forbid, MATLAB to do the calculations, then the >"divide by Mi(x)" or "divide by G(x)" can be more efficient, >but for VLSI implementation, the "evaluate v(x) at a^i >directly" approach is likely to be the best. > >--Dilip Sarwate > >
Ah excellent point, thank you. Since I've already got a syndrome unit that does the polynomial evaluation, I'll probably stick with that. I'm a little fuzzy still because the symbols will be in GF(2), and the alpha powers are in GF(2^M), to use horner's rule, I'll just pad the input bits with zeros to put them in the extension field and proceed normally, correct?
dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote:

>On Jul 30, 7:28&#2013266080;pm, spop...@speedymail.org (Steve Pope) wrote:
>> Yet a third, slightly different approach is to calculate the >> remainder v(x) mod G(x), where G is the code generator, and >> then evaluate this remainder at each a^i. &#2013266080;This can be attractive >> if the code rate is high.
>The issue with regard to the "divide by Mi(x)" or "divide by G(x)" >approaches is one of latency. It takes n clock cycles to do >either type of division if the bits are entering the decoder serially.
Actually, it takes only k clock cycles to compute this remainder.
>**Then** the remainder has to be evaluated at a^i (typically by >Horner's rule) which requires a *further* deg Mi or deg G clock >cycles.
Yes, this takes n-k clock cycles. On the other hand, evaluating v(x) at a^i via Horner's
>rule requires n clock cycles only, and we are done.
True, so both approaches take n clock cycles. Not that there aren't other, smaller differences entering into it. Steve
On Jul 31, 1:44&#2013266080;am, spop...@speedymail.org (Steve Pope) wrote:

> >The issue with regard to the "divide by Mi(x)" or "divide by G(x)" > >approaches is one of latency. &#2013266080;It takes n clock cycles to do > >either type of division if the bits are entering the decoder serially. > > Actually, it takes only k clock cycles to compute this remainder.
If the bits are entering the decoder serially, it takes n clock cycles to get them all into the decoder. So I am not sure how one can get the remainder of "v(x) divided by Mi(x)" or "v(x) divided by G(x)" in just k clock cycles. Perhaps Steve Pope will elucidate further. --Dilip Sarwate
dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote:

>On Jul 31, 1:44&#2013266080;am, spop...@speedymail.org (Steve Pope) wrote:
>> Actually, it takes only k clock cycles to compute this remainder.
>If the bits are entering the decoder serially, it takes n clock cycles >to get them all into the decoder. So I am not sure how one can get >the remainder of "v(x) divided by Mi(x)" or "v(x) divided by G(x)" >in just k clock cycles. Perhaps Steve Pope will elucidate further.
Sure. After those first k received bits, you will have computed a value which, when added (xor'ed) with the remaining received bits (which are the check locations) will be the remainder R(x). Since this addition is a trivial operation, you can start evaluating R(x) by Horner's method as these final check bits start coming in, and you will have the resulting syndrome by the same point in time that you would have, had you evaluated v(x) directly. So -- at least typically -- there is no difference in latency between the two methods; the one method has more polynomial shift register operations over GF(2) while the other has more time spent in Horner's method in GF(2^m). I have however often done it the way you suggest. The two methods are competitive. The important thing (for latency) is to have all the syndromes available immediately after receiving the last symbol from the channel. Steve
>dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote: > >>On Jul 31, 1:44&#65533;am, spop...@speedymail.org (Steve Pope) wrote: > > >>> Actually, it takes only k clock cycles to compute this remainder. > >>If the bits are entering the decoder serially, it takes n clock cycles >>to get them all into the decoder. So I am not sure how one can get >>the remainder of "v(x) divided by Mi(x)" or "v(x) divided by G(x)" >>in just k clock cycles. Perhaps Steve Pope will elucidate further. > >Sure. After those first k received bits, you will have computed a value >which, when added (xor'ed) with the remaining received bits >(which are the check locations) will be the remainder R(x). Since >this addition is a trivial operation, you can start evaluating R(x) >by Horner's method as these final check bits start >coming in, and you will have the resulting syndrome by the same point >in time that you would have, had you evaluated v(x) directly. > >So -- at least typically -- there is no difference in latency >between the two methods; the one method has more polynomial >shift register operations over GF(2) while the other has more >time spent in Horner's method in GF(2^m). > >I have however often done it the way you suggest. The two methods >are competitive. The important thing (for latency) is to have >all the syndromes available immediately after receiving the last >symbol from the channel. > >Steve > >
Actually division by g(x) to get the remainder and treat that as error polynomial won't work. It will give another codeword but not the desired codeword. You can verify this. But a simple way to see this is incorrect is that the remainder has degree less that of g(x) which means it can only change bits of the received codeword upto it, so if errors occured elsewhere it cannot correct them. Has anyone written a c or matlab program to find the hamming distance of a block code ? I know its possible to write on, but if one already available, might as well simply use it.