Topic: Reed Solomon (Page 1 of 1)

Hey,

is there anybode around who knows a bit about reed solomon codes?

I have a library, and I have some polynom definitions, but I have no clue how to transform
thoso polynom definitions into the parameters I need for the library...

Thanks,
so long,

->Tyberius Prime

From what I've read of them they are an extension of what we used to call cyclic redundancy checks. I wrote some programs to create CRCs back in the '80s but haven't had much exposure to them since.

I'm not sure from your question exactly what you're looking for, but it seems you're looking for an algorithm to interpret a group of Reed-Solomon polynomials to recover the original data. From what I understand you will need to know the generating polynomial to decode them.

Take a look at the following links and see if they give you enough information to get started. I understand enough of the technology to read and understand what is written there, but haven't taken the time to understand it enough to do an implementation

A description of Reed-Solomon Codes
Reed-Solomon software
The history of Reed-Solomon codes
Wikipedia - Reed-Solomon I found this last one to be the lease useful of the group, but it contains some links to other sites on Reed-Solomon that may be useful.

.



-- not necessarily stoned... just beautiful.

Thanks hyperbole. Your emails where quite helpful, I shall actually reply the next couple of days.

What I have on the one hand is this
"The polynomial divisor for generating 5 check
characters is:
g(x) = x5 + 62x4 + 111x3 + 15x2 + 48^x + 228. "

(all GF arithmetic, I suppose).

On the other hand, I need this:

"symsize gives the symbol size in bits, up to 8 for init_rs_char
or 32 for init_rs_int on a machine with 32-bit ints (though such a
huge code would exhaust memory limits on a 32-bit machine). The resulting
Reed-Solomon code word will have 2^symsize - 1 symbols,
each containing symsize bits."
This is 8, I understand that much.

"gfpoly gives the extended Galois field generator polynomial coefficients,
with the 0th coefficient in the low order bit. The polynomial
must be primitive; if not, the call will fail and NULL will be
returned."
?

"fcr gives, in index form, the first consecutive root of the
Reed Solomon code generator polynomial."
???

"prim gives, in index form, the primitive element in the Galois field
used to generate the Reed Solomon code generator polynomial."
???

"nroots gives the number of roots in the Reed Solomon code
generator polynomial. This equals the number of parity symbols
per code block."
I can read that out straight out of a table.


Thanks again for all your time!

Where are you taking these quotes from? Are they part of the documentation or code of the library you mentioned in your first post?

I'm going to assume that gfpoly, fcr, prim, and nroots are the names of variables in your program.

quote:

---

Tyberius Prime said:

"gfpoly gives the extended Galois field generator polynomial coefficients, with the 0th coefficient in the low order bit. The polynomial must be primitive; if not, the call will fail and NULL will be returned."

---

Galois Field Arithmetic (also called Finite Field Arithmetic) is a special kind of arithmetic carried out within fields. For example, each of the terms in your generating function constitutes a field and, assuming each field has eight bits, the arithmetic in each field is performed modulo 256.

gfpoly is a variable that describes to the software the primitive polynomial used to generate the Reed-Solomon polynomials. The term "primitive" here implies that the Galois Field polynomial is relatively prime to any resulting polynomial from the Galois Field Generator. If you look at a Galois Field polynomial, you will see it looks something like g(y) = (y-a*x^0) + (y-b*x^1) + ... + (y-m*x^n). Since each term of this polynomial contains a factor of x^i, it is common practice to simply express the polynomial as the concatenation of the coefficients of the terms where 'i' designates the slot in the array where the coefficient will be stored. For example your generating polynomial could be expressed as 1,62,111,15,48,228. In this case 228 would be placed in th 0th element of the array. With CRCs the x^i factors are all binary and the coefficients are all 0 or 1 so it is possible to place the polynomial in an integer with the 0th bit representing the coefficient of the 0th term and the 1th bit the coefficient of the 1th term, etc.

I assume that your program has used a similar encoding for your coefficients with the 0th coefficient in the 0th byte, the 1th coefficient in the 1th byte, etc.

The resulting polynomial must be relatively prime to the generating polynomial or the generating function will return NULL.

quote:

---

Tyberius Prime said:

"fcr gives, in index form, the first consecutive root of the Reed Solomon code generator polynomial."

---

I assume that fcr is declared as an array and each of the elements of the array contains the coefficient of one term of the resulting polynomial. This function is apparently finding the roots (that is I believe the location on the x-axis where the polynomial crosses the axis) of the generating polynomial. Rather than calculating a single number (as with the roots of x^2) this function is actually finding the root as another polynomial. Such as the roots of a^2x^2 - b^4x^4 are (ax -b^2x^2) and (ax + b^2x^2). Or, the roots of (b^4, 0, a^2, 0, 0) --> (-b^2, a, 0), (b^2, a, 0).

quote:

---

Tyberius Prime said:

"prim gives, in index form, the primitive element in the Galois field used to generate the Reed Solomon code generator polynomial."

---

This is just the generating equation you gave above. I'm not sure what they mean by "in index form". I'd need to see the actual program to figure that out. I suspect they are again storing each of the coefficients of the equation into one byte of an array.

quote:

---

Tyberius Prime said:

"nroots gives the number of roots in the Reed Solomon code generator polynomial. This equals the number of parity symbols per code block."

---

Fortunately, you didn't put a question mark after this quote, because I find it rather confusing. The article at Reed-Solomon Codes says that there are n-k parity symbols in a code block of length n with k data symbols and that it can correct errors in up to (n-k)/2 symbols. Your statement seems to indicate that (n-k)/2 must be proportional to the order of the generating polynomial. Thus with your generating polynomial of order 5, you can only correct errors in up to five symbols per code block. This means you will have ten parity symbols per code block and the smaller the code block, the less likely you are to have un-correctable errors.

.



-- not necessarily stoned... just beautiful.

Thanks Carl!

I really need to read this when I'm awake though, not at the very end of a day...

here's the signature of those parameters, I'm afraid that up there is about all the doc I have
void *init_rs_int(unsigned int symsize,unsigned int gfpoly,unsigned int fcr,
unsigned int prim,unsigned int nroots);

After that it's just calling
void encode_rs_int(void *rs,int *data,int *parity);
int decode_rs_int(void *rs,int *data,int *eras_pos,int no_eras);

int n sized data and n-k sized parity array. eras_pos can be left empty if you don't know anything about them

(Edited by Tyberius Prime on 11-20-2006 22:26)

Based on the signatures of the functions, I'm guessing that what they mean by 'index form' is a bit mask. Each location in the mask that is 0 corresponds to a term in the function with a coefficient of 0. Each bit in the mask that is non-zero (1) corresponds to a term in the equations that is non-zero.

Does the library have a standard table of coefficient it uses? If that is the case, this method of defining the functions begins to make sense. It would also mean that you don't have to worry about picking coefficients that will create a primitive polynomial. The author of the library has already done that work.

If that assumption is correct, then you define the generating function by specifying a bit-mask with the non-zero terms of the function set to 1. THis would be the value passed to gfpoly.

The draw-back to this is that since you have a dataset with a specific generating function, I don't think this library will decode the dataset unless the coefficients of the generating function happen to be the same as the ones used by the library.

I'm just guessing here and may have just made a completely incorrect assumption.

.



-- not necessarily stoned... just beautiful.

I just learned that the polynomial used is X^8 + X^5 + X^3 + X^2 + 1.

that would tranlate to 10010111 as gfpoly, or (stop swapping and give me my calculator, you stupid machine! ) 0x97,
or 151 decimal

No success with the lib at hand, though.

I searched for "first consecutive root" using AltaVista.

That came up with this link that has some useful information. It also references "Phill Karn"

So I did an advanced search for "Phil Karn" "Reed-Solomon" which yielded the following:
Forward Error Correcting Codes - This page references several source files that might be helpful.
Reed-Solomon coding and decoding by Phil Karn
Reed-Solomon coding/decoding package v-1.0
reed_solomon.c

I noticed that the function signatures on these pages look like the ones that you have given. I assume that means that the library you are using was derived from one of these source files so it may be possible to figure out what you need to run the prgram from there.

One of the things I noticed on the first link above is a test of the argument values for the init function

!           195:        if (symsize < 1)
        !           196:                return NULL;
        !           197:        if (fcr < 0 || fcr >= (1<<symsize))
        !           198:                return NULL;
        !           199:        if (prim <= 0 || prim >= (1<<symsize))
        !           200:                return NULL;
        !           201:        if (nroots < 0 || nroots >= (1<<symsize) || nroots > 8)
        !           202:                return NULL;
        !           203:

This gives a clue as to the values you should be supplying for the parameters to te init function. Unfortunately, it then calls a function "down(&rslistlock)" which is not shown on that page so it's hard to tell what the exact values should be. However, I think there is enough information in the other pages to start to figure it out.

.



-- not necessarily stoned... just beautiful.

A nice Ms Tan ( Google groups to the rescue) has supplied me with a working c++ lib - based on the very code by Phil Karn I've been toying with.

Turns out you also need to place the data in a special way in the array you pass to decode.
No all I need to do is write some test cases, then translate to c# then include it and profit

Hyperbole, I sure owe you a beer! And a cookie. And a lot of thanks for taking so much time on helping me.

Show off's

~Sig coming soon~

quote:

---

Tyberius Prime said:

A nice Ms Tan has supplied me with a working c++

---

Could you provide a link?

quote:

---

Tyberius Prime said:

Hyperbole, I sure owe you a beer! And a cookie.

---

My pleasure. It's fun to have an interesting problem as a diversion from time to time.

.



-- not necessarily stoned... just beautiful.

No link right now ( she mailed that to me ), but wait and see...

The Reed-Solomon ECC library he is trying to rip off is called Schifra.
The url is http://www.schifra.com




Arash Partow
________________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

Sorry?
Who's trying to 'rip off' (which in this place is a very negative term, equivalent to stealing
intellectual property) Schifra?

Mr Partow,
Phil's code is flowing around the net since 2002 at least, while your library has been announced
in the news groups a month ago (you can of course put any date you want on your website... archive.org hasn't seen it though).
Are you suggesting he stole your intellectual property?

Now, I didn't even try go get Schifra to run simply because your licence model is
not compatible with releasing *my* code under the GPL for everyone.
(To be truthful: I don't think you can relase your code under the GPL *and* require
some special group to buy a licence. Of course, you can suggest it, you can throw in extras for doing so,
but your website reads as if it was required. But then, IANAL and will stay away from such trouble).

Even if that had not been an issue, your library is pitifully documented. I know you want to
keep the documentation to those buying a licence - but I would not get by in a complex field
such as Reed Solomon coding with just a variant of 'read the examples'.

If you want your library to succed, you'll need to make it more accessible,
especially since it is a rather special purpose library .
That includes
- clearing up the licence issue. How can your code be distributed under the GPL, even if I was not to restrict it to 'non-commercial entities'? Even if that just means clearing up the phrasing on schifra.com. (Usually, even a commercial enterprise can use GPL code, they just need to pass on the GPL to their customers. No need to publish it though)(
- Improve your 'publicly available Schifra resources' - because I for sure couldn't find them.
- Generally be more helpful. Provide a usage example instead of just linking to your webpage. Explain. Explain. Explain.


That's my 2 cents.
So long,

->Tyberius Prime

ok - my bad

quote:

---

(To be truthful: I don't think you can relase your code under the GPL *and* require
some special group to buy a licence. Of course, you can suggest it, you can throw in extras for doing so,
but your website reads as if it was required. But then, IANAL and will stay away from such trouble).

---

Have you heard of the Cygwin buyout license? or how about Qt's license? need I provide anymore examples?

quote:

---

- clearing up the licence issue. How can your code be distributed under the GPL, even if I was not to restrict it to 'non-commercial entities'? Even if that just means clearing up the phrasing on schifra.com. (Usually, even a commercial enterprise can use GPL code, they just need to pass on the GPL to their customers. No need to publish it though)(

---

Its pretty straight forward if you're developing a project that uses a license registered at http://www.opensource.org/ then you may use
the code as if it were GPL'ed

Other than that its a commercial product. there is no ambiguity just you babbling on about something that makes no sense.

quote:

---

- Improve your 'publicly available Schifra resources' - because I for sure couldn't find them.

---

mmmm... the schifra site, google code project, boost-vault, planet-source, programmers heaven, freshmeat enough resources for you?

quote:

---

- Generally be more helpful. Provide a usage example instead of just linking to your webpage. Explain. Explain. Explain.

---

In the downloads section there is something there - yeap you guessed it! its a file to download. you download that file unzip or ungzip it
and look inside, examples and all...



Thats been my 3cents.


Long so,



Arash Partow
________________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

I could not download your code, because back at the time, the decision wether this would be a) *published* open source code or b) commercially sold open source code. (Ie. the client would pay for my development time and receive the source under the GPL. What they do with it is none of my business as long as they respect the GPL) had not been made. Both would be valid under the GPL.

As far as I read the following words on your webpage:

quote:

---

Developers wanting to use the Schifra Reed-Solomon error correcting code library and its components within a commercial environment or application, which includes, but is not limited to engineering practices such as initial code evaluation through prototyping and experimenting to fullscale development and integration, are defined within Schifra User Group 2 (SUG2).

---

(emphasis mine)
I was not allowed to do that if I ever wanted to go with plan b.

The cgywin buyout licence is optional if you want to develop code linked to it, without releasing it under the GPL.
It's not mandatory if you are 'within a commercial enviroment' (a confusing term. For example being payed for open source work is in a commercial enviroment, isn't it?). I believe Qt nowadays has a similar licencing scheme, though their code was not under the GPL for a
long time.

Long story short, I believe your licence isn't suitably worded for what you want it to mean. Enviroment is, to me, a very uncertain term in this regard.



As for your resources - they are not linked from your page. Especially not from your faq. I'm unlikely to google for stuff when I'm already at the one place for quick (and hopefully final ) answers - the faq. And most of the places you mention also seem to be simply places to download the code, no wiki, no discussion, no bug reports, nothing that would provide me with a feel of what Schifra can (and can't) do and how that would be done, without downloading it.
(And such resources should probably be in one place, not spread out over half a dozen sites).
Even a simple list of 'you can use Schifra for Reed Solomon handling in the following applications: compact disc, DataMatrix, deep space probing, ....' would be a start to lower your barrier of entry.

Right now, Reed Solomon information on the net is in an awful state. After a while, you get the feeling everybody's just repeating
stuff they read somewhere without quite understanding. Or if they appear to understand it, the math is in a state only mathematicans
can handle.

You are in a good position. You seem to understand the math, you have a (apperantly - still haven't lookt at the code ) solid library.
Now stop hiding it behind the wish to make money, and get the word out better than 'here is Schifra. It does Reed Solomon
encoding/decoding'.

So long,
->Tyberius Prime


Edit: Grammar

(Edited by Tyberius Prime on 12-12-2006 00:42)

PS: http://www.schifra.com/downloads.html link the licence in the text