Forums

About Reed-Solomon

Started by Piergiorgio Sartor April 14, 2012
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&#2013266080;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, &#2013266080;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&#2013266080;pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:


> Dilip, that link appears to be broken. &#2013266080; 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