About Reed-Solomon

Hi all,

just out of curiosity, I was digging into the RS codes,
mainly for RAID-6 purposes.

So, I was wondering about the possibility of increasing
the parity of such RAIDs.

Looking around a found a document describing a 3 parity
disks RAID, possible name RAID-7, if you want.

The description there seems quite specific, i.e. it does
describe 3 parities, but it seems to hint that a fourth
one would not be so trivial, like the first 3.

Namely, the GF generator for the 4th one does not seem
to follow the 2^n rule.

If I understood it correctly (maybe not, hence the question
here), the first 3 generators are 1, 2 and 4, but the 4th
is not 8...

So what is it? And how to find the 5th and so on?

As a side question, RS codes allow to find where an error
occurred (within certain statistical limits, of course).
For RAID-6, it is quite trivial to calculate where one
error is, but that method is specific to 2 parities.
I guess there is a generic method which, from 2n parities
can detect up to n error *positions*.
I was not able to find how, maybe I was just not looking
for the correct item (I guess a terminology issue).

So, any help would be appreciated.

Thanks a lot in advance.

P.S.: no, it is not an homework, I'm not a student. Some
of you may even remember me, I used to post here...

bye,

-- 

piergiorgio

On Apr 14, 10:19�am, Piergiorgio Sartor
<piergiorgio.sartor.this.should.not.be.u...@nexgo.REMOVETHIS.de>
wrote:


>
> Looking around a found a document describing a 3 parity
> disks RAID, possible name RAID-7, if you want.

RAID-7 is a proprietary method developed by a possibly
defunct corporation. _You_ have access to a document,
but since you coyly refuse to reveal even its name, let
alone its URL,  expecting people to answer such detailed
questions is preposterous.

> As a side question, RS codes allow to find where an error
> occurred (within certain statistical limits, of course).
> For RAID-6, it is quite trivial to calculate where one
> error is, but that method is specific to 2 parities.
> I guess there is a generic method which, from 2n parities
> can detect up to n error *positions*.

RS codes are about the only practically useful codes that
have the property known as Maximal Distance Separable.
MDS codes are unique in allowing correction of t errors
with 2t parities, and non-MDS codes cannot match this
performance: in general, with 2t parities, far fewer that
t errors can be corrected. In other words, the generic
method you are thinking about is essentially the RS decoding
algorithm.

Dilip Sarwate

Hi Dilip,

On 04/15/2012 03:42 AM, dvsarwate wrote:
[...]
> RAID-7 is a proprietary method developed by a possibly
> defunct corporation. _You_ have access to a document,

RAID-7 could be named any RAID which can
recover 3 HDDs failures.
I know there is/was a company proposing
such solution. I did not mean them, but the
general concept of it.
That is, if I write RAID-8, it means 4
parities, RAID-9 means 5 and so on.

> but since you coyly refuse to reveal even its name, let

What are you trying to say, here?
Since nobody asked, how could have I refused something?
Or are you trying to insult/flame?

Anyway, if you're curious, the document name
is "001-manasse.ppt". I guess you can find by
simple search and download.
The URL I do not have, any more...

> alone its URL,  expecting people to answer such detailed
> questions is preposterous.

If you feel like that, you might consider
to refrain to answer.

[...]
> RS codes are about the only practically useful codes that
> have the property known as Maximal Distance Separable.
> MDS codes are unique in allowing correction of t errors
> with 2t parities, and non-MDS codes cannot match this
> performance: in general, with 2t parities, far fewer that
> t errors can be corrected. In other words, the generic
> method you are thinking about is essentially the RS decoding
> algorithm.

Meaning what?

Do you have any more detailed *practical* documentation
on how to proceed? That is, the algorithm with some
examples would be nice.

What I have are n data bytes and k parity bytes.
Note that n+k << 255.

I can recompute the parities from the data.
If I know which data byte is missing/corrupted
I can recompute it using the parities.
Same for parities, of course.

How can I detect which byte (data+parity) is
corrupted, given that the recomputed parities
do not match the received ones?

The two parities method calculate the difference
between the P,Q received and P',Q' recomputed with
the current data set. Given that both P,Q are
not the same, P!=P' and Q!=Q'.
That is dP=P+P' and dQ=Q+Q' (of course + and - are
the same if this GF).
Of course the cross case reveal parity error or
data (very likely) correct.

After that, the dQ/dP ratio returns the g^j value,
which, after the log operation, returns j, that
is the (assumed) corrupted byte position.

This algorithm does not seem to me to scale to any
number of parities. I might be wrong, of course.

bye,

-- 

piergiorgio

On Apr 15, 6:04�am, Piergiorgio Sartor
<piergiorgio.sartor.this.should.not.be.u...@nexgo.REMOVETHIS.de>
wrote:
> Hi Dilip,
>
> On 04/15/2012 03:42 AM, dvsarwate wrote:
> [...]
>
> > RAID-7 is a proprietary method developed by a possibly
> > defunct corporation. _You_ have access to a document,
>
> RAID-7 could be named any RAID which can
> recover 3 HDDs failures.
> I know there is/was a company proposing
> such solution. I did not mean them, but the
> general concept of it.
> That is, if I write RAID-8, it means 4
> parities, RAID-9 means 5 and so on.
>
> > but since you coyly refuse to reveal even its name, let
>
> What are you trying to say, here?
> Since nobody asked, how could have I refused something?
> Or are you trying to insult/flame?
>
> Anyway, if you're curious, the document name
> is "001-manasse.ppt". I guess you can find by
> simple search and download.
> The URL I do not have, any more...
>
> > alone its URL, &#4294967295;expecting people to answer such detailed
> > questions is preposterous.
>
> If you feel like that, you might consider
> to refrain to answer.
>
> [...]
>
> > RS codes are about the only practically useful codes that
> > have the property known as Maximal Distance Separable.
> > MDS codes are unique in allowing correction of t errors
> > with 2t parities, and non-MDS codes cannot match this
> > performance: in general, with 2t parities, far fewer that
> > t errors can be corrected. In other words, the generic
> > method you are thinking about is essentially the RS decoding
> > algorithm.
>
> Meaning what?
>
> Do you have any more detailed *practical* documentation
> on how to proceed? That is, the algorithm with some
> examples would be nice.
>
> What I have are n data bytes and k parity bytes.
> Note that n+k << 255.
>
> I can recompute the parities from the data.
> If I know which data byte is missing/corrupted
> I can recompute it using the parities.
> Same for parities, of course.
>
> How can I detect which byte (data+parity) is
> corrupted, given that the recomputed parities
> do not match the received ones?
>
> The two parities method calculate the difference
> between the P,Q received and P',Q' recomputed with
> the current data set. Given that both P,Q are
> not the same, P!=P' and Q!=Q'.
> That is dP=P+P' and dQ=Q+Q' (of course + and - are
> the same if this GF).
> Of course the cross case reveal parity error or
> data (very likely) correct.
>
> After that, the dQ/dP ratio returns the g^j value,
> which, after the log operation, returns j, that
> is the (assumed) corrupted byte position.
>
> This algorithm does not seem to me to scale to any
> number of parities. I might be wrong, of course.
>
> bye,
>
> --
>
> piergiorgio

Tempted though I am to pull a Vlad, I will not flame your response.

Single error correction is relatively easy; multiple error correction
is
much harder, and the complexity increases as t^2 where t is the number
of errors. In particular, going from a 3-error-correcting system to a
4-error-correcting system requires almost twice the effort.

You can find a very efficient RS decoding algorithm, suitable for
correcting any number of errors up to half "the number of parities"
(rounded down to an integer if #parities is odd) detailed in the
paper whose URL is given below. This is not patent-protected, and
the algorithm has been implemented by several different companies
who will gladly sell you IP cores and the like or develop MATLAB
programs geared to your particular set of parameters, etc.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.4985

Dilip Sarwate

Hi Dilip,

On 04/15/2012 03:05 PM, dvsarwate wrote:
[...]
> Tempted though I am to pull a Vlad, I will not flame your response.

Hope not! :-)

> Single error correction is relatively easy; multiple error correction
> is
> much harder, and the complexity increases as t^2 where t is the number
> of errors. In particular, going from a 3-error-correcting system to a
> 4-error-correcting system requires almost twice the effort.

That is what I suspected, and maybe the reason
why more than 3 parities are not (yet) available
as RAID configuration.

> You can find a very efficient RS decoding algorithm, suitable for
> correcting any number of errors up to half "the number of parities"
> (rounded down to an integer if #parities is odd) detailed in the
> paper whose URL is given below. This is not patent-protected, and
> the algorithm has been implemented by several different companies
> who will gladly sell you IP cores and the like or develop MATLAB
> programs geared to your particular set of parameters, etc.
> 
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.4985

Thanks for the link, I'll have a look at it!

bye,

-- 

piergiorgio

On Sun, 15 Apr 2012 06:05:34 -0700 (PDT), dvsarwate
<dvsarwate@yahoo.com> wrote:

...deletia...

>
>Tempted though I am to pull a Vlad, I will not flame your response.
>
>Single error correction is relatively easy; multiple error correction
>is
>much harder, and the complexity increases as t^2 where t is the number
>of errors. In particular, going from a 3-error-correcting system to a
>4-error-correcting system requires almost twice the effort.
>
>You can find a very efficient RS decoding algorithm, suitable for
>correcting any number of errors up to half "the number of parities"
>(rounded down to an integer if #parities is odd) detailed in the
>paper whose URL is given below. This is not patent-protected, and
>the algorithm has been implemented by several different companies
>who will gladly sell you IP cores and the like or develop MATLAB
>programs geared to your particular set of parameters, etc.
>
>http://citeseerx.ist.psu.edu/viewdoc/summary?doi=3D10.1.1.10.4985
>
>Dilip Sarwate

Dilip, that link appears to be broken.   Is there a better one to that
paper?


Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

On 04/15/2012 07:38 PM, Eric Jacobsen wrote:
[...]

> Dilip, that link appears to be broken.   Is there a better one to that
> paper?

Strange, I could download the paper, for
me the link was working, but it seems down
right now...

If you want, I can send the paper vie email.

bye,

-- 

piergiorgio

On Sun, 15 Apr 2012 20:32:40 +0200, Piergiorgio Sartor
<piergiorgio.sartor.this.should.not.be.used@nexgo.REMOVETHIS.de>
wrote:

>On 04/15/2012 07:38 PM, Eric Jacobsen wrote:
>[...]
>
>> Dilip, that link appears to be broken.   Is there a better one to that
>> paper?
>
>Strange, I could download the paper, for
>me the link was working, but it seems down
>right now...
>
>If you want, I can send the paper vie email.
>
>bye,
>
>-- 
>
>piergiorgio

That would be great!  Thanks!


Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

On 04/15/2012 08:56 PM, Eric Jacobsen wrote:
[...]
> That would be great!  Thanks!

Done, please let me know if it does not arrive
(I got a strange error while sending...).

bye

-- 

piergiorgio

On Apr 15, 1:38�pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:


> Dilip, that link appears to be broken. � Is there a better one to that
> paper?

Eric:

Try this one:
<http://www.ifp.illinois.edu/~sarwate/pubs/Sarwate01High.pdf>

or

<http://www.icims.csl.uiuc.edu/~shanbhag/vips/publications/bma.pdf>

For a recent implementation in MATLAB, see

<http://www.mathworks.com/matlabcentral/fileexchange/34877-reed-
solomon-decoder-using-ribm-algorithm/content/RiBMDemo.m>

and for what it's worth, I had e-mailed you a pdf copy of the paper
a few days ago with regard to BCH decoding that we were discussing.

Dilip Sarwate