Using odd numbers for erasure codes

uint64_t f64(uint64_t x, uint64_t y) {
    return y * (2 - y * x);
}

static uint64_t inverse64(uint64_t x) {
    uint64_t y = x;
    y = f64(x, y);
    y = f64(x, y);
    y = f64(x, y);
    y = f64(x, y);
    y = f64(x, y);
    return y;
}

static void Test()
{
    siamese::PCGRandom prng;
    prng.Seed(0);

    uint64_t x, y;
    uint64_t a, b, c, d;
    uint64_t s, t;

    for (;;)
    {
        x = ((uint64_t)prng.Next() << 32) | prng.Next();
        y = ((uint64_t)prng.Next() << 32) | prng.Next();

        a = ((uint64_t)prng.Next() << 32) | prng.Next() | 1; // odd
        b = ((uint64_t)prng.Next() << 32) | prng.Next() | 1; // odd
        c = ((uint64_t)prng.Next() << 32) | prng.Next() | 1; // odd
        d = (((uint64_t)prng.Next() << 32) | prng.Next() | 1) - 1; // even

        // Convolutional encoder:
        s = a * x + b * y;
        t = c * x + d * y;

        // Simulate Gaussian elimination decoder:

        uint64_t ai = inverse64(a);

        t -= c * ai * s;

        uint64_t temp = d - c * ai * b;
        uint64_t tempi = inverse64(temp);

        uint64_t yr = tempi * t;

        s -= b * yr;

        uint64_t xr = ai * s;

        if (x != xr || y != yr)
        {
            Logger.Error("x - xr = ", x - xr, " y - yr = ", y - yr);
            TONK_DEBUG_BREAK();
        }
    }
}

Normal computer arithmetic units have operations that satisfy most of the things needed for an erasure codec.

The only thing that's tricky is that all the values we need to invert must be odd: The inverse64() calls above, for example.

This means the upper left value of the generator matrix (a) needs to be odd. And it causes some limitations on the even/oddness of the other matrix values (b, c, d).

Since we have control over the generator matrix this seems doable. The actual problem comes in because in a real system the generator matrix is large (100x100 or more). And the rows/columns of this smaller 2x2 matrix are selected at random from that larger matrix. They're the row values or recovery symbols we received, and the set of columns or original data that was lost.

Since we do not have control over which rows/columns of the generator matrix are chosen in the problem, and we have strong limitations on which rows/columns must be even or odd this is actually intractable.

Furthermore I'm not sure if there is any solution that works for 3x3 or larger matrices (haven't worked it out on paper yet). It may be impossible to solve the large matrices.

I'm not sure how to fix these problems, but it would yield probably the simplest erasure codec.