# Two MDS Array Codes for Disk Erasures: the Blaum-Bruck-Vardy Code and the BASIC Code

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 $GF(2)$, 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 $d$ data components and $c$ parity components in its generator matrix in standard form, its distance is at most $c + 1$ by the Singleton bound. Hence the code is MDS if and only if it can tolerate $c$ arbitrary disk failures.)

The BASIC code does the following things in relations to the BBV code:

1. Adds a virtual parity bit after each disk, giving each disk an even parity
2. Does polynomial arithmetic modulo $1+x^p$ instead of $h(x) = 1+x+\cdots + x^{p-1}$ as in the case of BBV code
3. Shows equivalence to the BBV code by making a nice observation via Chinese Remainder Theorem
4. Proves MDS property for any number of coding disks when $p$ 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?

# Generalized Vandermonde Matrices with Missing Row-Powers

Let $[n] := \{0, 1, 2, \cdots, n -1 \}$. Let $x = (x_0, \cdots, x_{n-1})$ with distinc $x_j$s. Let $R = \{0 = r_1, r_2, \cdots, r_{n-1} = r$ be a set of distinct nonnegative row-powers. Consider the $n \times n$ Generalized Vandermonde matrix $V(x ; R) := \left( x_j^{r_i} \right)_{i,j \in [n]}$. When $R = [n]$, this matrix becomes the ordinary Vandermonde matrix, $V(x)$.

An equivalent description of $R$ is the largest row-power $r \in R$ and the set of missing rows from $[r]$: that is, the items that are in $[r]$ but not in $R$. Let $L_r = \{\ell_0, \ell_1, \cdots \}$ be this set. Define the punctured Generalized Vandermonde matrix $V_{\perp}(x; L_r) := V(x; R)$. Let $s_k(x)$ be the $k$th elementary symmetric polynomial.

Now we are ready to present some interesting results without proof, from the paper “Lower bound on Sequence Complexity” by Kolokotronis, Limniotis, and Kalouptsidis.

$det V_{\perp}(x ; \{\ell \}) = det V(x) \ s_{n-\ell}(x).$

$det V_{\perp}(x ; \{\ell_0, \ell_1\}) = det V(x) \ det \left( s_{n-\ell_i+j}(x) \right)_{i,j \in [2]}.$

$det V_{\perp}(x ; L) = det V(x) \ det \left( s_{n-\ell_i+j}(x) \right)_{i,j \in [s]} \text{ where } L = \{ \ell_0, \ell_1, \cdots, \ell_{s-1}\}.$

I will add some applications later on.