Reed-Solomon Decoding with decoding failure signal
Kyutaeg Oh
Hi,
I have designed an RS decoder adopting the modified Euclid's algorithm,
I have one question about flagging [decoder failure] signal...
As you know, this signal means that the given syndrome corresponds to
uncorrectable error pattern. But, how can I get that signal ?
What's the mechanism generating [decoder failure] signal ?
In a reference[1], someone tell something, but it doesn't work..
Is there any method to find that signal, except re-calculating the syndrom..?
Please help me..
Thanks in advance.
Have a nice day.
Kyutaeg Oh ( kt...@filter.snu.ac.kr )
[1] Stephen B. Wicker, Reed-Solomon Codes and Their Applications
pp. 223--224
biju
Comparing the number of roots of the error locator polynoimial with its
degree should work, I think.
--
Biju Sukumaran
Siemens AG, Semiconductor Group
Kyutaeg Oh
biju (bi...@hl.siemens.de) wrote:
: Comparing the number of roots of the error locator polynoimial with its
: degree should work, I think.
Thanks for your reply.
But your recommendation has 2 problems.
1. There may be the case that the number of roots of the error locator poly.
be same as its degree, but the decoder failure occurs.
2. Although not the case, That's not appropriate to real time applications,
because the decoder can't do anything until the comparison finished
( which requires the entire frame length's long).
Thanks again,
Have a nice day.
Thor Arne Johansen
Kyutaeg Oh wrote:
>
> Hi,
>
> I have designed an RS decoder adopting the modified Euclid's algorithm,
> I have one question about flagging [decoder failure] signal...
> As you know, this signal means that the given syndrome corresponds to
> uncorrectable error pattern. But, how can I get that signal ?
> What's the mechanism generating [decoder failure] signal ?
> In a reference[1], someone tell something, but it doesn't work..
>
> Is there any method to find that signal, except re-calculating the syndrom..?
> Please help me..
>
How will re-calculating the syndromes help you?
If you receive more than t errors, the probability of undetected decoder
failures is approx. 1/t!.
Undetected decoder failure is when after applying correction, the
syndromes
compute to zero, but the frame is still in error.
The normal checks for uncorrectable errors are:
* Power of error locator polynomial <= t;
* Power of error-locator polynomial==# of roots (all roots have
multiplicity 1)
* Error position is inside frame (for shortened codes)
> Thanks in advance.
> Have a nice day.
>
> Kyutaeg Oh ( kt...@filter.snu.ac.kr )
>
> [1] Stephen B. Wicker, Reed-Solomon Codes and Their Applications
> pp. 223--224
--
Thor Arne Johansen
Ibas Laboratories, Norway
http://www.ibas.no
Kyutaeg Oh
May be, you say, the decoder-error case.
In decoder-error case, it is of no use to re-calculate the syndromes.
But when decoder-failure occurrs, the syndromes never become to zero.
Isn't it right?
: How will re-calculating the syndromes help you?
Thor Arne Johansen
Kyutaeg Oh wrote:
>
> May be, you say, the decoder-error case.
> In decoder-error case, it is of no use to re-calculate the syndromes.
> But when decoder-failure occurrs, the syndromes never become to zero.
> Isn't it right?
>
I'm not sure I understand what you mean?
Here's how i would do this:
After receiving a frame compute the syndromes:
If any of the syndromes are non-zero we have errors.
If so, compute the error locator polynomial sigma(x)
If the degree of sigma(x) is greater than t then we
have uncorrectable errors. (but we know about it, so it's not a
problem).
If the degree og sigma(x) is less than or equal to t, compute
the roots.
If the number of _distinct_ roots are not equal to the degree of
sigma(x),
then we have uncorrectable errors (but we still know about it).
If we have the right number of distinct roots, we compute the error
locations, and check if they are within the frame (for shortened codes).
If any error location is outside the frame, we have uncorrectable errors
(we still know about it)
If we have the correct number of error locations, and all are within the
frame,
we compute the error magnitudes, and apply correction.
And here comes my point:
There is still a probability (1/t!) that we had uncorrectable errors,
but we
have no way of knowing about it. In other words, if we compute the
syndromes
from the corrected frame, we would get all zero (no errors), while in
truth
the frame is still in error. This is what I called undetected decoder
failure.
To minimize problems with such failures you can either increase t (t!
grows
_fast_), or you could introduce a cross check error detection code. If
you
for instance include a simple CRC into the frame you could use that to
check the RS-decoder.
Hope this helps,
Kyutaeg Oh
Thank you very much.
Yes, you are right.
Most text books call your "undetected decoder failure" as "decoder error".
My path is as follows.
1. Compute syndromes.
2. If any non zero syndrome, perform modified Euclid algorithm
to find error locator polynomial, and error evaluator polynomial.
3. Find roots, and correct errors.
4. Re-calculate the syndromes of the corrected frame.
If, in step 3, the number of roots in frame is not equal to the degree of
the error locator polynomial(smaller number of roots that the degree),
It must be the decoder failure case (Ok, we know it)
But if not that case, in other words, the two numbers are equal,
Can I have the conclusion that the received frame is not eroneous or
has undetected error pattern, say,
when two numbers are equal, can't the re-calculated syndromes of the corrected
frame be zero?
This is waht I want to know.
Have a nice day.
Thor Arne Johansen (th...@ibas.no) wrote:
s...@bob.eecs.berkeley.edu
Kyutaeg Oh <kt...@hdtv.snu.ac.kr> wrote:
>I have designed an RS decoder adopting the modified Euclid's algorithm,
>I have one question about flagging [decoder failure] signal...
>As you know, this signal means that the given syndrome corresponds to
>uncorrectable error pattern. But, how can I get that signal ?
>What's the mechanism generating [decoder failure] signal ?
>In a reference[1], someone tell something, but it doesn't work..
>
>[1] Stephen B. Wicker, Reed-Solomon Codes and Their Applications
> pp. 223--224
As one of the designers of the RS decoder system in the above
reference, I can assure you that the undecodeable detection
algorithm described does indeed work.
Without you telling us more, I can't determine what you're
doing wrong, but here's a couple places where people commonly
make mistakes:
(1) In addition to checking for the undecodeable condition at the
end of Euclid's algorithm, you need to further detect if the roots
of the error locator are not repeated, and are all at valid
locations (and if you're dealing with a shortened RS code,
you have fewer valid locations).
(2) Not all uncorrectable error patterns are detectable. Some
will be misdecoded. You need to allow for this. These
are the error patterns which, if re-encoded, give you the
same syndromes you started with.
Steve
s...@bob.eecs.berkeley.edu
Thor Arne Johansen <th...@ibas.no> wrote:
>Here's how i would do this:
>
>After receiving a frame compute the syndromes:
>If any of the syndromes are non-zero we have errors.
>If so, compute the error locator polynomial sigma(x)
>If the degree of sigma(x) is greater than t then we
>have uncorrectable errors. (but we know about it, so it's not a
>problem).
>If the degree of sigma(x) is less than or equal to t, compute
>the roots.
You've left out a step here. See below.
>If the number of _distinct_ roots are not equal to the degree of
>sigma(x),
>then we have uncorrectable errors (but we still know about it).
>If we have the right number of distinct roots, we compute the error
>locations, and check if they are within the frame (for shortened codes).
>If any error location is outside the frame, we have uncorrectable errors
>(we still know about it)
>If we have the correct number of error locations, and all are within the
>frame,
>we compute the error magnitudes, and apply correction.
That's pretty good, but it's not quite correct. It's close. See
the article authored by Berlekamp et. al. in the reference
(Wicker's Reed-Solomon text) quoted earlier in this thread. It
describes how you also need to apply an undecodeable test to the
outcome of the Euclidean algorithm, prior to solving for the
roots of sigma and performing the other tests you describe.
I know of one Reed-Solomon decoder that was simulated with one
million undecodeable syndrome sets, and a tally was
kept of of the results of each of the different conditions
that flag an undecodeable. The conditions you list above only flagged
about 99.5% of them.
For the Euclidean algorithm, there are probably no literature
references to exactly how this needs to be done, other than Wicker;
so I recommend studying it carefully.
Steve