ReedSolomon decoding issue

[JessicaMulein]

I was trying to do some very basic reed solomon encoding and decoding and I was able to generate FEC for an input array filled with the numbers 0 to 127, and then decode the input + fec data (given as FEC first, then data, figured out by trial and error). But while it works when there are no errors, introducing even one bit error seems to cause the decode never to complete (or at least not in any reasonable timeframe).

Have you done much testing on your reed solomon module of your red-agate-math library?

I had set up a GF2e8 with a gx from getgx using nth 127. I was doing an encode on 128 bytes (filled with numbers 0 to 127) and then trying to decode([...fec, ...input]).

[shellyln]

Hi, @JessicaMulein .

Reed-Solomon encoding has been well tested by reading QRs generated using the library with a physical QR code reader.
Decoding, however, has not been well tested.
Also, the decoding does not use a very good algorithm for error location searching and error correction.

getGx(field: FiniteField<F>, nth: number, aDegree: number = 0)

The second parameter nth in ReedSolomon.getGx() gives the degree of the generating polynomial, not the degree of the data.

An example of its usage is shown below:

red-agate/packages/red-agate-barcode/src/barcode/Qr.ts

Lines 493 to 511 in b62921d

	const repeats = segments[i][0];
	const dataCwSize = segments[i][2];
	const ecCwSize = segments[i][1] - dataCwSize;
	let gx: number[];
	if (gxList.length <= (ecCwSize - 1)) {
	gxList = ReedSolomon.listGx(field, gxList, ecCwSize, 0);
	}
	gx = gxList[ecCwSize - 1];
	const rs = new ReedSolomon(field, gx, 0);
	for (let j = 0; j < repeats; j++) {
	const dataCodewords = bytes.slice(p, p + dataCwSize).reverse();
	const ecCodewords = Uint8Array.from(rs.encode(dataCodewords));
	dataCwStack.push(dataCodewords.reverse());
	ecCwStack .push(ecCodewords.reverse());
	totalLength += dataCwSize + ecCwSize;
	p += dataCwSize;
	}

red-agate/packages/red-agate-math/src/_spec/ReedSolomon.spec.ts

Lines 33 to 55 in b62921d

	rsol = new ff.ReedSolomon(gf2, rsgxs[rsgxs.length - 1]);
	rsol.gx = ff.ReedSolomon.getGx(gf2, 10, 0);
	const ax = [
	16, 32, 12, 86, 97, 128, 236, 17,
	236, 17, 236, 17, 236, 17, 236, 17].reverse();
	const poly = new ff.ArrayPolynomialRing(rsol.field);
	const rsec = rsol.encode(ax);
	// console.log(poly.add(poly.mul(poly.divmod(ax, rsol.gx, rsol.gx.length - 1).q, rsol.gx), rsec));
	const rsrecv = rsec.concat(ax);
	const wwww1 = poly.field.div(0, 242);
	const q1111 = poly.divmod(rsrecv, rsol.gx);
	// console.log(q1111.q);
	// console.log(q1111.r);
	// console.log(q1111.divisible);
	// console.log("rs send=" + rsrecv);
	rsrecv[3] ^= 51;
	rsrecv[11] ^= 211;
	rsrecv[12] ^= 73;
	rsrecv[20] ^= 99;
	// console.log("rs corr=" + rsol.decode(rsrecv));

[JessicaMulein]

My encode/decode looked like this

import { ReedSolomon, Gf2e8Field } from 'red-agate-math';
export abstract class StaticHelpersFec {
    public static field: Gf2e8Field = new Gf2e8Field();
    public static gx: number[] = ReedSolomon.getGx<number>(StaticHelpersFec.field, 127);
    public static codec: ReedSolomon<number> = new ReedSolomon<number>(StaticHelpersFec.field, StaticHelpersFec.gx); 
    public static fecEncode(data: Array<number>): Array<number> {
        const fec = StaticHelpersFec.codec.encode(data);
        return fec;
    }
    public static fecDecode(data: Array<number>): Array<number> {
        const decoded = StaticHelpersFec.codec.decode(data);
        return decoded;
    }
}

and my test looked like this

import { StaticHelpersFec } from "./lib/staticHelpers.fec";

function buildData(n: number): Array<number> {
    const result: Array<number> = [];
    for (let i = 0; i < n; i++) {
        result.push(i);
    }
    return result;
}

describe('staticHelpers.fec', () => {
    it('should encode and decode with no errors present', () => {
        const input = buildData(128);
        const fec = StaticHelpersFec.fecEncode(input);
        const decoded = StaticHelpersFec.fecDecode([...fec, ...input]);
        expect(decoded).toStrictEqual(input);
    });
    it('should encode and decode with up to 63 errors present', () => {
        const input = buildData(128);
        const fec = StaticHelpersFec.fecEncode(input);
        const degraded = [...input];
        for (let i = 0; i < 63; i++) {
            const randomIndex = Math.floor(Math.random() * degraded.length);
            degraded[randomIndex] = Math.floor(Math.random() * 256);
        }
        const decoded = StaticHelpersFec.fecDecode([...fec, ...degraded]);
        expect(decoded).toStrictEqual(input);
    });
});

The second test fails to return within any reasonable timeframe.

[JessicaMulein]

sorry for the flip flop. when I reconstructed my proof of concept, I thought it was working but realized I was passing in an undegraded input. It definitely still fails to return in the same way.

Can you see anything wrong in what I'm doing?

[shellyln]

Can you see anything wrong in what I'm doing?

• In general, the error correction capability is 1/2 the degree of the generating polynomial. (Your code seems to be fine)
• The parameter of ReedSolomon.decode() is [...errorCorrectingCode, ...Data], in that order. (Your code seems to be fine)
• Math.floor(Math.random() * degraded.length) Very low probability, but if random returns 1, it exceeds the range of the index.

Why don’t you try it once with a small number of errors?

The following test is working:

import * as ff from "../index";

describe("ReedSolomon", function() {
    it("ReedSolomon", function() {
        const gf2 = new ff.Gf2e8Field();
        let rsol = new ff.ReedSolomon(gf2, []);
        const specRegxs = [193, 157, 113, 95, 94, 199, 111, 159, 194, 216, 1];

        const rsgxs = ff.ReedSolomon.listGx(gf2, void 0, 10, 0);
        expect(rsgxs[rsgxs.length - 1].length).toEqual(specRegxs.length);
        for (let i = 0; i < specRegxs.length; i++) {
            expect(rsgxs[rsgxs.length - 1][i]).toEqual(specRegxs[i]);
        }

        let rsgxs2 = ff.ReedSolomon.listGx(gf2, void 0, 5, 0);
        expect(rsgxs2.length).toEqual(5);
        rsgxs2 = ff.ReedSolomon.listGx(gf2, rsgxs2, 10, 0);
        expect(rsgxs2.length).toEqual(10);
        expect(rsgxs2[rsgxs2.length - 1].length).toEqual(specRegxs.length);
        for (let i = 0; i < specRegxs.length; i++) {
            expect(rsgxs2[rsgxs2.length - 1][i]).toEqual(specRegxs[i]);
        }

        const rsgx3 = ff.ReedSolomon.getGx(gf2, 10, 0);
        expect(rsgx3.length).toEqual(specRegxs.length);
        for (let i = 0; i < specRegxs.length; i++) {
            expect(rsgx3[i]).toEqual(specRegxs[i]);
        }

        rsol = new ff.ReedSolomon(gf2, rsgxs[rsgxs.length - 1]);
        rsol.gx = ff.ReedSolomon.getGx(gf2, 10, 0);
        const ax = [
            16, 32, 12, 86, 97, 128, 236, 17,
            237, 18, 239, 19, 240, 20, 241, 21].reverse();

        const poly = new ff.ArrayPolynomialRing(rsol.field);
        const rsec = rsol.encode(ax);
        // console.log(poly.add(poly.mul(poly.divmod(ax, rsol.gx, rsol.gx.length - 1).q, rsol.gx), rsec));
        const rsrecv = rsec.concat(ax);

        const wwww1 = poly.field.div(0, 242);
        const q1111 = poly.divmod(rsrecv, rsol.gx);
        // console.log(q1111.q);
        // console.log(q1111.r);
        // console.log(q1111.divisible);
        console.log("rs send=" + rsrecv);

        //rsrecv[3] ^= 51;
        rsrecv[11] ^= 211;
        rsrecv[12] ^= 73;
        rsrecv[17] ^= 103;
        rsrecv[21] ^= 99;
        rsrecv[23] ^= 97;
        //rsrecv[25] ^= 53;

        const rscorr = rsol.decode(rsrecv);
        console.log("rs corr=" + rscorr);
        expect(rscorr.length).toEqual(ax.length);
        for (let i = 0; i < ax.length; i++) {
            expect(rscorr[i]).toEqual(ax[i]);
        }
    });
});

rs send=78,0,106,221,233,41,112,249,21,208,21,241,20,240,19,239,18,237,17,236,128,97,86,12,32,16
rs corr=21,241,20,240,19,239,18,237,17,236,128,97,86,12,32,16