Code Poetry
and Text Adventures

by catid posted (>30 days ago) 9:29pm Sun. Nov 23rd 2014 PST
The MDS-AES paper, while somewhat broken as it turns out, is interesting for erasure codes.  First a glossary of terms:

MDS code: Maximum distance separable code.  This means it can provide the same optimal recovery performance as Reed-Solomon codes.

Cauchy/Vandermonde matrix: Good references on wikipedia.  Just ways to construct MDS codes.

Punctured code: This means that rows or columns of the matrix are removed.  In erasure codes this is common because a lot of good data makes it through to the receiver.  Removed columns are the ones that we actually received correctly.  Removed rows are recovery symbols that got lost or are not received yet.

Involutory matrix: The matrix is its own inverse.  This means to invert it just multiply by the same matrix.  I'm not sure if this actually works for punctured codes as I've only seen it discussed in the literature for decryption.  I think it's not a huge win if the matrix is involutory for erasure codes, unless matrix multiplication has some kind of shortcut.  And it's unlikely that the nice property of matrix multiplication will also survive puncturing too...

MDS-AES type matrices are symmetric across both diagonals, meaning that a NxN MDS-AES matrix has only N unique symbols.

Leaning somewhat on the low Hamming weight of the MDS-AES matrix elements and the high amount of structure, a lot of the intermediate results can be reused.  Meaning that often times some temporary computations can be made, and then bits strategically flipped to get from those temporary values to the ones needed for each row.  This means that matrix multiplication can be done much faster.

Most normal erasure codes require the encoder to do this matrix multiplication, so this seems like a big win.  And the encoder is the bottleneck in the erasure code software.  So in certain special circumstances this would be a great improvement.

However in the general case not so much.  Usually the check symbols produced by the erasure code are far outnumbered by the original data symbols.  This is because the user doesn't want the data to be greatly increased in size.  So for 30-300 input data symbols the output may only be 5 check symbols.  My code already runs at 400 MB/s for 10 check symbols for 29 packets of data, for example.

MDS-AES prevents the first row from being all ones, so for m = 1 it's much slower than the usual erasure code approaches.  I think that Cauchy matrices with lots of precomputation can yield similarly fast multiplication shortcuts without giving up the first row of ones to speed up the encoder.

This all was a diversion from the Rainbow Road code project I've been putting off for a while now.  I was hoping that something in these "FFHadamard" toys the encryption guys were playing with would be useful but it looks like there's nothing directly transferable.  Oh well.