O(n log q) encoding

[maksverver]

This thread is just to dump an idea I had when implementing the O(q log q) PAR2 encoder, that is potentially relevant for PAR3.

In par2afft, I implemented an O(q log q) encoder, which is essentially a (65536,32768) linear code over GF(2^16): i.e. it encodes a message of length 32768 into a codeword of length 65536.

Any (n, m) linear code can be shortened to an (n', m') code (n' ≤ n, m' ≤ m) simply by setting the extra (m - m') input values to 0 and discarding the extra (n' - n) output values. This is what my par2afft tool currently does to implement input block counts under 32768.

This is easy and works correctly but the downside is that it doesn't change the time required to encode a single message, so the throughput (as measured in input bytes processed per second) falls to n'/n. For the typical case of 2000 input blocks that's a slowdown of a factor 16.

However, it doesn't have to be this way! Instead of setting the unused symbols to 0, we can just take multiple elements from each block to fill up the message.

For example, if we want to encode with a typical input block count of 2000, we can populate 32000 of 32768 slots by using 16 elements from each input slice:

m[0] = slice[0][0]
m[1] = slice[0][1]
..
m[15] = slice[0][15]
m[16] = slice[1][0]
m[17] = slice[1][1]
..
m[31] = slice[1][15]
m[32] = slice[21][0]
..
m[31999] = slice[1999][15]
m[32000] = 0
..
m[32767] = 0

Esentially: m[i] = slice[i/16][i%16]

This doesn't lose anything in robustness (compared to the original 2000 input block encoding scheme), and turns an O(q log q) code into an O(n log q) code for arbitrary n, though most efficiently when n divides q, or nearly so (i.e., q % n is small).

Note that O(n log q) is still slower than O(n log n) encoding, but only by a factor log n/log q, e.g. for n=2000, q=65536, log n/log q = ~0.69 so you keep 69% of your througput compared to a hypothetical O(n log n) scheme, which might actually be slower due to constant factors or not even exist.

I think it's quite an elegant solution: with only a single code, you can support various input block counts, allowing the tradeoff between I/O and robustness to be chosen freely without significantly affecting throughput.

The problem is that neither PAR2 nor PAR3 currently supports this mode. For PAR2 this is unavoidable because the format is fixed, which is exactly its strength. For PAR3 I think it would be useful to consider adding this feature, especially if it turns out O(q log q) codes are easier to implement or faster than O(n log n).