In this post, I am going to review two erasure codes: the Blaum-Bruck-Vardy code and the BASIC code (also here). These are erasure codes, which means, their purpose is to encode a number of data disks into a number of coding disks so that when one or more data/coding disks fail, the failed disk can be reconstructed using the existing data and coding disks.
A strength of these codes is that although the algebra is described on extension fields/rings over , the encoding/decoding process uses only Boolean addition/rotation operation and no finite field operation. These codes are also MDS (Maximum Distance Separable), which means they have the largest possible (minimum) distance for a fixed message-length and codeword-length.
(Recall that if a code has data components and
parity components in its generator matrix in standard form, its distance is at most
by the Singleton bound. Hence the code is MDS if and only if it can tolerate
arbitrary disk failures.)
The BASIC code does the following things in relations to the BBV code:
- Adds a virtual parity bit after each disk, giving each disk an even parity
- Does polynomial arithmetic modulo
instead of
as in the case of BBV code
- Shows equivalence to the BBV code by making a nice observation via Chinese Remainder Theorem
- Proves MDS property for any number of coding disks when
is “large enough” and has a certain structure
Open Question: What is the least disk size for which these codes are MDS with arbitrary distance?