/* ecc Version 1.2 by Paul Flaherty (paulf at stanford.edu) Copyright (C) 1993 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ /* rslib.c Library of Reed - Solomon Routines This file contains the actual routines to implement a Reed - Solomon (255,249,7) code. The encoder uses a feedback shift register generator, which systematically encodes 249 bytes into a 255 byte block. The decoder is a classic Peterson algorithm. */ #include "ecc.h" /* Also uses gflib.c */ /* Reed - Solomon Encoder. The Encoder uses a shift register algorithm, as detailed in _Applied Modern Algebra_ by Dornhoff and Hohn (p.446). Note that the message is reversed in the code array; this was done to allow for (emergency) recovery of the message directly from the data stream. */ rsencode (m, c) unsigned char m[249], c[255]; { unsigned char r[6], rtmp; int i, j; for (i = 0; i < 6; i++) r[i] = 0; for (i = 0; i < 249; i++) { c[254 - i] = m[i]; rtmp = gfadd (m[i], r[5]); for (j = 5; j > 0; j--) { r[j] = gfadd (gfmul (rtmp, g[j]), r[j - 1]); } r[0] = gfmul (rtmp, g[0]); } for (i = 0; i < 6; i++) { c[i] = r[i]; } } /* Polynomial Evaluator, used to determine the Syndrome Vector. This is relatively straightforward, and there are faster algorithms. */ unsigned char evalpoly (p, x) unsigned char p[255], x; { unsigned char y; int i; y = 0; for (i = 0; i < 255; i++) { y = gfadd (y, gfmul (p[i], gfexp (x, i))); } return (y); } /* Determine the Syndrome Vector. Note that in s[0] we return the OR of all of the syndromes; this allows for an easy check for the no - error condition. */ syndrome (c, s) unsigned char c[255], s[7]; { extern unsigned char e2v[256]; int i; s[0] = 0; for (i = 1; i < 7; i++) { s[i] = evalpoly (c, e2v[i]); s[0] = s[0] | s[i]; } } /* Determine the number of errors in a block. Since we have to find the determinant of the S[] matrix in order to determine singularity, we also return the determinant to be used by the Cramer's Rule correction algorithm. */ errnum (s, det, errs) unsigned char s[7], *det; int *errs; { *det = gfmul (s[2], gfmul (s[4], s[6])); *det = gfadd (*det, gfmul (s[2], gfmul (s[5], s[5]))); *det = gfadd (*det, gfmul (s[6], gfmul (s[3], s[3]))); *det = gfadd (*det, gfmul (s[4], gfmul (s[4], s[4]))); *errs = 3; if (*det != 0) return; *det = gfadd (gfmul (s[2], s[4]), gfexp (s[3], 2)); *errs = 2; if (*det != 0) return; *det = s[1]; *errs = 1; if (*det != 0) return; *errs = 4; } /* Full impementation of the three error correcting Peterson decoder. For t<6, it is faster than Massey - Berlekamp. It is also somewhat more intuitive. */ rsdecode (code, mesg, errcode) unsigned char code[255], mesg[249]; int *errcode; { extern unsigned char v2e[256]; unsigned char syn[7], deter, z[4], e0, e1, e2, n0, n1, n2, w0, w1, w2, x0, x[3]; int i, sols; *errcode = 0; /* First, get the message out of the code, so that even if we can't correct it, we return an estimate. */ for (i = 0; i < 249; i++) mesg[i] = code[254 - i]; syndrome (code, syn); if (syn[0] == 0) return; /* We now know we have at least one error. If there are no errors detected, we assume that something funny is going on, and so return with errcode 4, else pass the number of errors back via errcode. */ errnum (syn, &deter, errcode); if (*errcode == 4) return; /* Having obtained the syndrome, the number of errors, and the determinant, we now proceed to correct the block. If we do not find exactly the number of solutions equal to the number of errors, we have exceeded our error capacity, and return with the block uncorrected, and errcode 4. */ switch (*errcode) { case 1: x0 = gfmul (syn[2], gfinv (syn[1])); w0 = gfmul (gfexp (syn[1], 2), gfinv (syn[2])); if (v2e[x0] > 5) mesg[254 - v2e[x0]] = gfadd (mesg[254 - v2e[x0]], w0); return; case 2: z[0] = gfmul (gfadd (gfmul (syn[1], syn[3]), gfexp (syn[2], 2)), gfinv (deter)); z[1] = gfmul (gfadd (gfmul (syn[2], syn[3]), gfmul (syn[1], syn[4])), gfinv (deter)); z[2] = 1; z[3] = 0; polysolve (z, x, &sols); if (sols != 2) { *errcode = 4; return; } w0 = gfmul (z[0], syn[1]); w1 = gfadd (gfmul (z[0], syn[2]), gfmul (z[1], syn[1])); n0 = 254 - v2e[gfinv (x[0])]; n1 = 254 - v2e[gfinv (x[1])]; e0 = gfmul (gfadd (w0, gfmul (w1, x[0])), gfinv (z[1])); e1 = gfmul (gfadd (w0, gfmul (w1, x[1])), gfinv (z[1])); if (n0 < 249) mesg[n0] = gfadd (mesg[n0], e0); if (n1 < 249) mesg[n1] = gfadd (mesg[n1], e1); return; case 3: z[3] = 1; z[2] = gfmul (syn[1], gfmul (syn[4], syn[6])); z[2] = gfadd (z[2], gfmul (syn[1], gfmul (syn[5], syn[5]))); z[2] = gfadd (z[2], gfmul (syn[5], gfmul (syn[3], syn[3]))); z[2] = gfadd (z[2], gfmul (syn[3], gfmul (syn[4], syn[4]))); z[2] = gfadd (z[2], gfmul (syn[2], gfmul (syn[5], syn[4]))); z[2] = gfadd (z[2], gfmul (syn[2], gfmul (syn[3], syn[6]))); z[2] = gfmul (z[2], gfinv (deter)); z[1] = gfmul (syn[1], gfmul (syn[3], syn[6])); z[1] = gfadd (z[1], gfmul (syn[1], gfmul (syn[5], syn[4]))); z[1] = gfadd (z[1], gfmul (syn[4], gfmul (syn[3], syn[3]))); z[1] = gfadd (z[1], gfmul (syn[2], gfmul (syn[4], syn[4]))); z[1] = gfadd (z[1], gfmul (syn[2], gfmul (syn[3], syn[5]))); z[1] = gfadd (z[1], gfmul (syn[2], gfmul (syn[2], syn[6]))); z[1] = gfmul (z[1], gfinv (deter)); z[0] = gfmul (syn[2], gfmul (syn[3], syn[4])); z[0] = gfadd (z[0], gfmul (syn[3], gfmul (syn[2], syn[4]))); z[0] = gfadd (z[0], gfmul (syn[3], gfmul (syn[5], syn[1]))); z[0] = gfadd (z[0], gfmul (syn[4], gfmul (syn[4], syn[1]))); z[0] = gfadd (z[0], gfmul (syn[3], gfmul (syn[3], syn[3]))); z[0] = gfadd (z[0], gfmul (syn[2], gfmul (syn[2], syn[5]))); z[0] = gfmul (z[0], gfinv (deter)); polysolve (z, x, &sols); if (sols != 3) { *errcode = 4; return; } w0 = gfmul (z[0], syn[1]); w1 = gfadd (gfmul (z[0], syn[2]), gfmul (z[1], syn[1])); w2 = gfadd (gfmul (z[0], syn[3]), gfadd (gfmul (z[1], syn[2]), gfmul (z[2], syn[1]))); n0 = 254 - v2e[gfinv (x[0])]; n1 = 254 - v2e[gfinv (x[1])]; n2 = 254 - v2e[gfinv (x[2])]; e0 = gfadd (w0, gfadd (gfmul (w1, x[0]), gfmul (w2, gfexp (x[0], 2)))); e0 = gfmul (e0, gfinv (gfadd (z[1], gfexp (x[0], 2)))); e1 = gfadd (w0, gfadd (gfmul (w1, x[1]), gfmul (w2, gfexp (x[1], 2)))); e1 = gfmul (e1, gfinv (gfadd (z[1], gfexp (x[1], 2)))); e2 = gfadd (w0, gfadd (gfmul (w1, x[2]), gfmul (w2, gfexp (x[2], 2)))); e2 = gfmul (e2, gfinv (gfadd (z[1], gfexp (x[2], 2)))); if (n0 < 249) mesg[n0] = gfadd (mesg[n0], e0); if (n1 < 249) mesg[n1] = gfadd (mesg[n1], e1); if (n2 < 249) mesg[n2] = gfadd (mesg[n2], e2); return; default: *errcode = 4; return; } } /* Polynomial Solver. Simple exhaustive search, as solving polynomials is generally NP - Complete anyway. */ polysolve (polynom, roots, numsol) unsigned char polynom[4], roots[3]; int *numsol; { extern unsigned char e2v[256]; int i, j; unsigned char y; *numsol = 0; for (i = 0; i < 255; i++) { y = 0; for (j = 0; j < 4; j++) y = gfadd (y, gfmul (polynom[j], gfexp (e2v[i], j))); if (y == 0) { roots[*numsol] = e2v[i]; *numsol = *numsol + 1; } } }
file: /Techref/method/error/rs-255-248-7-pf-1993/rslib_c.htm, 70KB, , updated: 2000/5/10 13:16, local time: 2024/8/14 15:04,
18.220.140.208:LOG IN
|
©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions? <A HREF="http://techref.massmind.org/techref/method/error/rs-255-248-7-pf-1993/rslib_c.htm"> Colorized Source Code</A> |
Did you find what you needed? |
Welcome to massmind.org! |
Welcome to techref.massmind.org! |
.