>dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote:
>
>>On Jul 31, 1:44�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.
>> 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
Reply by dvsa...@yahoo.com●July 31, 20092009-07-31
On Jul 31, 1:44�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. �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
>> 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.
>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
Reply by gct●July 31, 20092009-07-31
>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?
Reply by dvsa...@yahoo.com●July 30, 20092009-07-30
On Jul 30, 7:28�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. �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
>>> 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
Reply by gct●July 30, 20092009-07-30
>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
>
Reply by dvsa...@yahoo.com●July 30, 20092009-07-30
On Jul 30, 4:59�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). �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. �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
Reply by gct●July 30, 20092009-07-30
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?