Reply by Piergiorgio Sartor April 17, 20122012-04-17
Hi Dilip,

On 04/17/2012 01:34 AM, dvsarwate wrote:
[...]
> used for computations. You need to understand some > theory of finite fields to grasp what is going on.
I think you're right, maybe I should dig a bit more into GF, but I was hoping in some practical "recipe" easy to understand. BTW, about GF, what could be good reference to start from? Thanks again, bye, -- piergiorgio
Reply by dvsarwate April 16, 20122012-04-16
On Apr 16, 2:08�pm, Piergiorgio Sartor
<piergiorgio.sartor.this.should.not.be.u...@nexgo.REMOVETHIS.de>
wrote:
> On 04/15/2012 03:05 PM, dvsarwate wrote: > [...] > > >http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.4985 > > Hi Dilip, > > thanks again for the paper. > > I just went through the first part of it, which is, > for me, the most interesting one. > > Being a novice in the field, the introduction part > was really enlightening, for me. > > Anyhow, I'm used to see RS coding as product of an > identity matrix, on top of a (partial) Vandermonde > one, by the input data vector. > Thus generating a systematic coding. > > The partial Vandermonde is usually made of rows (or > columns) taken from the generic Vandermonde matrix of > GF generators. > That is the columns of: > > 1 &#4294967295; &#4294967295; &#4294967295; 1 &#4294967295; &#4294967295; 1 &#4294967295; &#4294967295; ... &#4294967295; &#4294967295;1 > x0 &#4294967295; &#4294967295; x1 &#4294967295; &#4294967295; x2 &#4294967295; &#4294967295;... xk-1 > x0^2 &#4294967295; x1^2 &#4294967295; x2^2 &#4294967295;... xk-1^2 > ... > x0^k-1 x1^k-1 x2^k1 ... xk-1^k-1 > > Being in RAID GF(256), it seems that x0=1 (RAID-5) and > x1=2 for RAID6. > For 3 parities RAID it would be x2=4, I guess. > > Now, my question would be how are the GF generators xi > chosen or calculated? > > Are they simply 2^j? I guess not... > > Sorry for the long boring post, I'm trying to explain > my limited knowledge as clearly as I can. > > Thanks again, > > bye, > > -- > > piergiorgio
The matrix used to encode a systematic RS code is not the same as the matrix used to compute the syndrome. Systematic encoding uses polynomial division; syndrome computation uses polynomial evaluation. Both processes are described in the paper you are reading. The notion of $2^i$ has no meaning in the Galois field used for computations. You need to understand some theory of finite fields to grasp what is going on. Dilip Sarwate Dilip Sarwate
Reply by Piergiorgio Sartor April 16, 20122012-04-16
On 04/15/2012 03:05 PM, dvsarwate wrote:
[...]
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.4985
Hi Dilip, thanks again for the paper. I just went through the first part of it, which is, for me, the most interesting one. Being a novice in the field, the introduction part was really enlightening, for me. Anyhow, I'm used to see RS coding as product of an identity matrix, on top of a (partial) Vandermonde one, by the input data vector. Thus generating a systematic coding. The partial Vandermonde is usually made of rows (or columns) taken from the generic Vandermonde matrix of GF generators. That is the columns of: 1 1 1 ... 1 x0 x1 x2 ... xk-1 x0^2 x1^2 x2^2 ... xk-1^2 ... x0^k-1 x1^k-1 x2^k1 ... xk-1^k-1 Being in RAID GF(256), it seems that x0=1 (RAID-5) and x1=2 for RAID6. For 3 parities RAID it would be x2=4, I guess. Now, my question would be how are the GF generators xi chosen or calculated? Are they simply 2^j? I guess not... Sorry for the long boring post, I'm trying to explain my limited knowledge as clearly as I can. Thanks again, bye, -- piergiorgio
Reply by Eric Jacobsen April 15, 20122012-04-15
On Sun, 15 Apr 2012 13:14:07 -0700 (PDT), dvsarwate
<dvsarwate@yahoo.com> wrote:

>On Apr 15, 1:38=A0pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote: > > >> Dilip, that link appears to be broken. =A0 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>
That's useful, thanks!
>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
Yes, I realized that as soon as I saw it. ;) Eric Jacobsen Anchor Hill Communications www.anchorhill.com
Reply by dvsarwate April 15, 20122012-04-15
On Apr 15, 1:38&#4294967295;pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:


> Dilip, that link appears to be broken. &#4294967295; 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
Reply by Piergiorgio Sartor April 15, 20122012-04-15
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
Reply by Eric Jacobsen April 15, 20122012-04-15
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
Reply by Piergiorgio Sartor April 15, 20122012-04-15
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
Reply by Eric Jacobsen April 15, 20122012-04-15
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
Reply by Piergiorgio Sartor April 15, 20122012-04-15
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