Reed Solomon — OZONE Asylum, home of the Mad Scientists

OZONE

This page's ID: 28653

Edit Post

Who can edit a post?	The poster and administrators may edit a post. The poster can only edit it for a short while after the initial post.

Your User Name:
Your Password:
Login Options:	Remember Me On This Computer

Your Text: Insert Slimies » Insert UBB Code » Close Last Tag \| All Tags UBB Help	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] [b]Tyberius Prime said:[/b] "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." [/quote] 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-ax^0) + (y-bx^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] [b]Tyberius Prime said:[/b] "fcr gives, in index form, the first consecutive root of the Reed Solomon code generator polynomial." [/quote] 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] [b]Tyberius Prime said:[/b] "prim gives, in index form, the primitive element in the Galois field used to generate the Reed Solomon code generator polynomial." [/quote] 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] [b]Tyberius Prime said:[/b] "nroots gives the number of roots in the Reed Solomon code generator polynomial. This equals the number of parity symbols per code block." [/quote] Fortunately, you didn't put a question mark after this quote, because I find it rather confusing. The article at [url=http://www.4i2i.com/reed_solomon_codes.htm]Reed-Solomon Codes[/url] 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. [url=http://www.hyperbole-software.com/] [img]http://www.hyperbole-software.com/ozone/hyperbole-88x33.gif[/img] [/url] Loading...
Options:	Enable Slimies Enable Linkwords

« Backwards — Onwards »

Show Forum Drop Down Menu