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?
Continue reading “Two MDS Array Codes for Disk Erasures: the Blaum-Bruck-Vardy Code and the BASIC Code”
[This post, which is based on an ongoing discussion with Alex Russell and Ravi Sundaram, contains some unpublished results.]
Currently, we are asking whether all submatrices of the order- Vandermonde matrix over a finite extension of are invertible where is prime. The answer is “no” in general: there are examples of fields where the Vandermonde matrix has a singular submatrix.
We can ask an easier(?) question, though. What happens if we randomly sample a set of columns and look into submatrices formed by a subset of the sampled columns. With a touch of beautiful insight, Professor Russell has connected Szemeredi’s theorem on arithmetic progressions with this question.
Let denote an arithmetic progression of length $latek k$. Let for .
The Szemerédi theorem says, any “sufficiently dense” subset contains infinitely many for all . A finitary version says: Fix your favourite . Then, there exists a natural such that if you look any subset of size at least , you will find an . Yet another version says:
Szemerédi’s Theorem. The size of the largest subset without an cannot be too large; in particular, it is .
Recall that a function is if it grows too slow compared to , so that .
Continue reading “Vandermonde Submatrices and Arithmetic Progressions”
To this day, no method of finding a generator of is known to be more efficient than essentially trying 2, then 3, and so on. Who cares? Well, the difficulty of breaking a certain public key cryptosystem (due to El Gamal) depends on the difficulty of working with generators of . — Keith Conrad
An th root of unity in a finite field is an element satisfying , where is an integer. If is the smallest positive integer with this property, is called a primitive th root of unity. If is a primitive th root of unity, then all elements in the set are also roots of unity. Actually, the set form a cyclic group of order under multiplication, with generator .
Problem: Suppose you are given a finite field of degree , and you are promised that there indeed exists a primitive th root of unity for prime. Find , and in particular, produce a C++code that finds it.
In what follows, we talk about how to find such a root and provide my C++ code; the code uses the awesome NTL library.
Continue reading “Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code”