Citation Information

• Plain Text:

     .techreport     p:08:e48
     author          J. S. Plank
     title           The 48 Sets of Minimal Density {MDS} {RAID-6} Matrices for a Word Size of Eight
     institution     University of Tennessee
     month           March
     year            2008
     number          UT-CS-08-611
     where           http://web.eecs.utk.edu/~jplank/plank/papers/CS-08-611.html
  

• Bibtex:

  @TECHREPORT{p:08:e48,
          author = "J. S. Plank",
          title = "The 48 Sets of Minimal Density {MDS} {RAID-6} Matrices for a Word Size of Eight",
          institution = "University of Tennessee",
          month = "March",
          year = "2008",
          number = "UT-CS-08-611",
          where = "http://web.eecs.utk.edu/~jplank/plank/papers/CS-08-611.html"
  }
  

There are 48 distinct sets of minimal density MDS RAID-6 codes with a word size w=8. Each may be defined by eight matrices, X₀, ..., X₇, where X₀ is always equal to an identity matrix. For example, Figure 1 shows the X_i matrices for the best matrix.

Figure 1: The eight X_i matrices for the best minimal density MDS matrix for w=8.

We represent each X_i (i > 0) with a permutation matrix and an extra one. The permutation matrix may be represented by a vector Π_i which has w integer elements π_i,0, ..., π_i,w-1. π_i,j is the column which contains the location of the one in row j. In order to be a valid permutation matrix, Π_i must be such that 0 ≤ π_ij < w and if j ≠ j' then π_i,j ≠ π_i,j'.

We can represent a matrix X_i with its permutation matrix Π_i plus a row and column identifying the extra one. We will use the following notation to represent X_i:

For example, X₁ in Figure 1 may be represented as {(7,3,0,2,6,1,5,4),4,7}.

The following table enumerates the 48 sets of minimal density MDS matrices. In each matrix, X₁ is an identity matrix, and thus is not specified. The value f at the end of each row denotes the overhead factor of decoding with that matrix. This is the average overhead over optimal when decoding from two disk failures.

Note, the first row of the table is the matrix in Figure 1.

Reference