討論區: English (Thread #14255)

ReedSolomon question (2007-03-22 11:29 by 匿名 #28522)

I compared ReedSolomon.java with the code from http://sourceforge.net/projects/rscode/, and found a difference.
--> in decode_data() & Modified_Berlekamp_Massey(), the original NPAR is replaced by 8(==MAXDEG).

--> and during my decoding of camera scanned picture, I found the error correction in ReedSolomon.java cannot correct all errors and sometime give wrong result. Anybody can solve the problem?

回覆 #28522×

You can not use Wiki syntax
You are not logged in. To discriminate your posts from the rest, you need to pick a nickname. (The uniqueness of nickname is not reserved. It is possible that someone else could use the exactly same nickname. If you want assurance of your identity, you are recommended to login before posting.) 登入

RE: ReedSolomon question (2007-06-11 00:28 by drhu00 #30116)

See my previous comments about possible bug in ReedSolomon. Let me know if following ReedSolomon fixed your problem or not.
**************************************
public class ReedSolomon {
public static int glog[] = new int[] {
-255, 255, 1, 240, 2, 225, 241, 53, 3, 38, 226, 133, 242, 43, 54, 210,
4, 195, 39, 114, 227, 106, 134, 28, 243, 140, 44, 23, 55, 118, 211, 234,
5, 219, 196, 96, 40, 222, 115, 103, 228, 78, 107, 125, 135, 8, 29, 162,
244, 186, 141, 180, 45, 99, 24, 49, 56, 13, 119, 153, 212, 199, 235, 91,
6, 76, 220, 217, 197, 11, 97, 184, 41, 36, 223, 253, 116, 138, 104, 193,
229, 86, 79, 171, 108, 165, 126, 145, 136, 34, 9, 74, 30, 32, 163, 84,
245, 173, 187, 204, 142, 81, 181, 190, 46, 88, 100, 159, 25, 231, 50, 207,
57, 147, 14, 67, 120, 128, 154, 248, 213, 167, 200, 63, 236, 110, 92, 176,
7, 161, 77, 124, 221, 102, 218, 95, 198, 90, 12, 152, 98, 48, 185, 179,
42, 209, 37, 132, 224, 52, 254, 239, 117, 233, 139, 22, 105, 27, 194, 113,
230, 206, 87, 158, 80, 189, 172, 203, 109, 175, 166, 62, 127, 247, 146, 66,
137, 192, 35, 252, 10, 183, 75, 216, 31, 83, 33, 73, 164, 144, 85, 170,
246, 65, 174, 61, 188, 202, 205, 157, 143, 169, 82, 72, 182, 215, 191, 251,
47, 178, 89, 151, 101, 94, 160, 123, 26, 112, 232, 21, 51, 238, 208, 131,
58, 69, 148, 18, 15, 16, 68, 17, 121, 149, 129, 19, 155, 59, 249, 70,
214, 250, 168, 71, 201, 156, 64, 60, 237, 130, 111, 20, 93, 122, 177, 150 };

public static int gexp[] = new int[] {
1, 2, 4, 8, 16, 32, 64, 128, 45, 90, 180, 69, 138, 57, 114, 228,
229, 231, 227, 235, 251, 219, 155, 27, 54, 108, 216, 157, 23, 46, 92, 184,
93, 186, 89, 178, 73, 146, 9, 18, 36, 72, 144, 13, 26, 52, 104, 208,
141, 55, 110, 220, 149, 7, 14, 28, 56, 112, 224, 237, 247, 195, 171, 123,
246, 193, 175, 115, 230, 225, 239, 243, 203, 187, 91, 182, 65, 130, 41, 82,
164, 101, 202, 185, 95, 190, 81, 162, 105, 210, 137, 63, 126, 252, 213, 135,
35, 70, 140, 53, 106, 212, 133, 39, 78, 156, 21, 42, 84, 168, 125, 250,
217, 159, 19, 38, 76, 152, 29, 58, 116, 232, 253, 215, 131, 43, 86, 172,
117, 234, 249, 223, 147, 11, 22, 44, 88, 176, 77, 154, 25, 50, 100, 200,
189, 87, 174, 113, 226, 233, 255, 211, 139, 59, 118, 236, 245, 199, 163, 107,
214, 129, 47, 94, 188, 85, 170, 121, 242, 201, 191, 83, 166, 97, 194, 169,
127, 254, 209, 143, 51, 102, 204, 181, 71, 142, 49, 98, 196, 165, 103, 206,
177, 79, 158, 17, 34, 68, 136, 61, 122, 244, 197, 167, 99, 198, 161, 111,
222, 145, 15, 30, 60, 120, 240, 205, 183, 67, 134, 33, 66, 132, 37, 74,
148, 5, 10, 20, 40, 80, 160, 109, 218, 153, 31, 62, 124, 248, 221, 151,
3, 6, 12, 24, 48, 96, 192, 173, 119, 238, 241, 207, 179, 75, 150, 1 };

//G(x)=P^8+P^4+P^3+P^2+1
int[] y;
int NPAR;
int MAXDEG;
int[] synBytes;
// The Error Locator Polynomial, also known as Lambda or Sigma. Lambda[0] == 1
int[] Lambda;
// The Error Evaluator Polynomial
int[] Omega;

// local ANSI declarations
// error locations found using Chien's search
int[] ErrorLocs = new int[256];
int NErrors;

// erasure flags
int[] ErasureLocs = new int[256];
int NErasures = 0;

/* multiplication using logarithms */
int gmult(int a, int b) {
if (a==0 || b == 0) return (0);
int i = glog[a];
int j = glog[b];
int k = (i + j) % (255);
//System.out.println("i=" + i + " j=" + j + " gexp[k]=" + gexp[k]);
return (gexp[k]);
}

int ginv (int elt) {
return (gexp[255-glog[elt]]);
}

public ReedSolomon(int[] source, int aNPAR) {
y = source;
NPAR = aNPAR;
MAXDEG = NPAR * 2;
synBytes = new int[MAXDEG];
Lambda = new int[MAXDEG];
Omega = new int[MAXDEG];
}

void decode_data(int[] data) {
int sum;
for (int j = 0; j < NPAR; j++) {
sum = 0;
//System.out.println("gexp[j+1]=" + gexp[j+1]);
for (int i = 0; i < data.length; i++) {
sum = data[i] ^ gmult(gexp[j+1], sum);
//System.out.println("sum=" + sum);
}
synBytes[j] = sum;
//System.out.println("synBytes["+j+"]="+synBytes[j]);
}
}

public void correct() {
decode_data(y);
boolean hasError = false;

for (int i = 0; i < NPAR; i++) {
//System.out.println("synBytes[" + i + "] = " + synBytes[i]);
if (synBytes[i] != 0) hasError = true;
}

if (hasError) {
correct_errors_erasures (y, y.length, 0, new int[1]);
}
}

public int getNumCorrectedErrors() {
return NErrors;
}

/* From Cain, Clark, "Error-Correction Coding For Digital Communications", pp. 216. */
void Modified_Berlekamp_Massey () {
int n, L, L2, k, d, i;
int[] psi = new int[MAXDEG];
int[] psi2 = new int[MAXDEG];
int[] D = new int[MAXDEG];
int[] gamma = new int[MAXDEG];

/* initialize Gamma, the erasure locator polynomial */
init_gamma(gamma);

/* initialize to z */
copy_poly(D, gamma);
mul_z_poly(D);

copy_poly(psi, gamma);
k = -1; L = NErasures;

for (n = NErasures; n < NPAR; n++) {
d = compute_discrepancy(psi, synBytes, L, n);
//System.out.println("n=" + n + " d=" + d);
if (d != 0) {
/* psi2 = psi - d*D */
for (i = 0; i < MAXDEG; i++) psi2[i] = psi[i] ^ gmult(d, D[i]);

if (L < (n-k)) {
L2 = n-k;
k = n-L;
/* D = scale_poly(ginv(d), psi); */
for (i = 0; i < MAXDEG; i++) D[i] = gmult(psi[i], ginv(d));
L = L2;
}

/* psi = psi2 */
for (i = 0; i < MAXDEG; i++) psi[i] = psi2[i];
}

mul_z_poly(D);
}

for(i = 0; i < MAXDEG; i++) Lambda[i] = psi[i];

compute_modified_omega();
}

/* given Psi (called Lambda in Modified_Berlekamp_Massey) and synBytes,
compute the combined erasure/error evaluator polynomial as
Psi*S mod z^4
*/
void compute_modified_omega () {
int[] product = new int[MAXDEG*2];

mult_polys(product, Lambda, synBytes);
zero_poly(Omega);
for(int i = 0; i < NPAR; i++) Omega[i] = product[i];
}

/* polynomial multiplication */
void mult_polys (int[] dst, int[] p1, int[] p2) {
int i, j;
int[] tmp1 = new int[MAXDEG*2];

for (i = 0; i < (MAXDEG*2); i++) dst[i] = 0;

for (i = 0; i < MAXDEG; i++) {
for(j=MAXDEG; j<(MAXDEG*2); j++) tmp1[j]=0;

/* scale tmp1 by p1[i] */
for(j = 0; j < MAXDEG; j++) tmp1[j]=gmult(p2[j], p1[i]);

/* and mult (shift) tmp1 right by i */
for (j = (MAXDEG*2)-1; j >= i; j--) tmp1[j] = tmp1[j-i];

for (j = 0; j < i; j++) tmp1[j] = 0;

/* add into partial product */
for(j = 0; j < (MAXDEG*2); j++) dst[j] ^= tmp1[j];
}
}

/* gamma = product (1-z*a^Ij) for erasure locs Ij */
void init_gamma (int[] gamma) {
int[] tmp = new int[MAXDEG];

zero_poly(gamma);
zero_poly(tmp);
gamma[0] = 1;

for (int e = 0; e < NErasures; e++) {
copy_poly(tmp, gamma);
scale_poly(gexp[ErasureLocs[e]], tmp);
mul_z_poly(tmp);
add_polys(gamma, tmp);
}
}

void compute_next_omega (int d, int[] A, int[] dst, int[] src) {
for (int i = 0; i < MAXDEG; i++) {
dst[i] = src[i] ^ gmult(d, A[i]);
}
}

int compute_discrepancy (int[] lambda, int[] S, int L, int n) {
int sum=0;

for (int i = 0; i <= L; i++)
sum ^= gmult(lambda[i], S[n-i]);
return (sum);
}

/********** polynomial arithmetic *******************/
void add_polys (int[] dst, int[] src) {
for (int i = 0; i < MAXDEG; i++) dst[i] ^= src[i];
}

void copy_poly (int[] dst, int[] src) {
for (int i = 0; i < MAXDEG; i++) dst[i] = src[i];
}

void scale_poly (int k, int[] poly) {
for (int i = 0; i < MAXDEG; i++) poly[i] = gmult(k, poly[i]);
}


void zero_poly (int[] poly) {
for (int i = 0; i < MAXDEG; i++) poly[i] = 0;
}

/* multiply by z, i.e., shift right by 1 */
void mul_z_poly (int[] src) {
for (int i = MAXDEG-1; i > 0; i--) src[i] = src[i-1];
src[0] = 0;
}

/* Finds all the roots of an error-locator polynomial with coefficients
* Lambda[j] by evaluating Lambda at successive values of alpha.
*
* This can be tested with the decoder's equations case.
*/
void Find_Roots () {
int sum;
NErrors = 0;

for (int r = 1; r < 256; r++) {
sum = 0;
/* evaluate lambda at r */
for (int k = 0; k < NPAR+1; k++) {
sum ^= gmult(gexp[(k*r)%255], Lambda[k]);
//System.out.println("r: " + r + " k: " + k + " sum: " + sum);
}
if (sum == 0) {
ErrorLocs[NErrors] = (255-r);
NErrors++;
//System.out.println("Root found at r = " + r + "(255-r) = " + (255-r));
}
}
}

/* Combined Erasure And Error Magnitude Computation
*
* Pass in the codeword, its size in bytes, as well as
* an array of any known erasure locations, along the number
* of these erasures.
*
* Evaluate Omega(actually Psi)/Lambda' at the roots
* alpha^(-i) for error locs i.
*
* Returns 1 if everything ok, or 0 if an out-of-bounds error is found
*
*/
int correct_errors_erasures (int[] codeword, int csize, int nerasures, int[] erasures) {
int r, i, j, err;

/* If you want to take advantage of erasure correction, be sure to
set NErasures and ErasureLocs[] with the locations of erasures.
*/
NErasures = nerasures;
for (i = 0; i < NErasures; i++) ErasureLocs[i] = erasures[i];

Modified_Berlekamp_Massey();
Find_Roots();

//System.out.println("NErrors: " + NErrors);
if ((NErrors <= NPAR) && NErrors > 0) {
/* first check for illegal error locs */
for (r = 0; r < NErrors; r++) {
if (ErrorLocs[r] >= csize) {
//System.out.println("ErrorLocs[" + r + "]: " + ErrorLocs[r]);
//return(0);
}
}

for (r = 0; r < NErrors; r++) {
int num, denom;
i = ErrorLocs[r];
/* evaluate Omega at alpha^(-i) */

num = 0;
for (j = 0; j < MAXDEG; j++)
num ^= gmult(Omega[j], gexp[((255-i)*j)%255]);

/* evaluate Lambda' (derivative) at alpha^(-i) ; all odd powers disappear */
denom = 0;
for (j = 1; j < MAXDEG; j += 2) {
denom ^= gmult(Lambda[j], gexp[((255-i)*(j-1)) % 255]);
}

err = gmult(num, ginv(denom));
int tmp = csize - i - 1;
//System.out.println("csize-i-1=" + tmp + " err =" + err);
//System.out.println(codeword[csize-i-1]);
if (tmp >= 0) codeword[tmp] ^= err;
//System.out.println(codeword[tmp]);
}

//for (int p = 0; p < codeword.length; p++) {
// System.out.print(codeword[p] + " ");
//}
//System.out.println("");

return(1);
} else {
return(0);
}
}
}
回覆: #28522

回覆 #30116×

You can not use Wiki syntax
You are not logged in. To discriminate your posts from the rest, you need to pick a nickname. (The uniqueness of nickname is not reserved. It is possible that someone else could use the exactly same nickname. If you want assurance of your identity, you are recommended to login before posting.) 登入

RE: ReedSolomon question (2007-07-02 16:47 by jascco #30412)

Hi all,

Tried to apply this correction to code. But in my case it doesen't help. I

I have encoded string TestString! to my qrcode when it has no errors decode results is same. But when apply two errors to image it gives me result TestSuring!

If I do some debugging I see that erros have not been found.

For request I can send my test images.

Any help on this?

Jascco

回覆: #30116

回覆 #30412×

You can not use Wiki syntax
You are not logged in. To discriminate your posts from the rest, you need to pick a nickname. (The uniqueness of nickname is not reserved. It is possible that someone else could use the exactly same nickname. If you want assurance of your identity, you are recommended to login before posting.) 登入

RE: ReedSolomon question (2007-09-03 23:54 by drhu00 #31992)

Hi, jascco
I think I find the bug of reedsolomon. Please send me your test images and let me verify it.
you can send to drhu00@yahoo.com
If it is ok, I'll send the code to Yanbe.
回覆: #30412

回覆 #31992×

You can not use Wiki syntax
You are not logged in. To discriminate your posts from the rest, you need to pick a nickname. (The uniqueness of nickname is not reserved. It is possible that someone else could use the exactly same nickname. If you want assurance of your identity, you are recommended to login before posting.) 登入