March 24, 2008
Technical Report UT-CS-08-611
Department of Computer Science
University of Tennessee
Knoxville, TN 37996
http://web.eecs.utk.edu/~jplank/plank/papers/CS-08-611.html
PDF:
http://web.eecs.utk.edu/~jplank/plank/papers/CS-08-611.pdf
.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
@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, X0, ..., X7, where X0 is always equal to an identity matrix. For example, Figure 1 shows the Xi matrices for the best matrix.
Figure 1: The eight Xi matrices for the best minimal density MDS matrix for w=8.
We represent each Xi (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 Xi with its permutation matrix Πi plus a row and column identifying the extra one. We will use the following notation to represent Xi:
For example, X1 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, X1 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.
# | X1 | X2 | X3 | X4 | X5 | X6 | X7 | f |
1 | {(7,3,0,2,6,1,5,4),4,7} | {(6,2,4,0,7,3,1,5),1,3} | {(2,5,7,6,0,3,4,1),5,4} | {(5,6,1,7,2,4,3,0),2,0} | {(1,2,3,4,5,6,7,0),7,2} | {(3,0,6,5,1,7,4,2),6,5} | {(4,7,1,5,3,2,0,6),3,1} | 1.18452 |
2 | {(5,7,0,2,6,4,1,3),1,1} | {(6,3,1,4,7,2,5,0),3,2} | {(2,5,7,6,3,0,1,4),6,3} | {(4,7,6,0,1,2,3,5),5,7} | {(1,2,3,4,5,7,0,6),7,4} | {(3,4,5,7,0,1,2,6),2,6} | {(7,0,5,1,3,6,4,2),4,5} | 1.18532 |
3 | {(7,4,6,1,5,2,0,3),4,4} | {(1,2,3,4,7,0,5,6),7,3} | {(6,7,1,2,5,3,4,0),3,5} | {(3,4,0,5,2,7,1,6),1,6} | {(5,6,3,7,0,1,2,4),2,1} | {(2,3,4,0,6,1,7,5),5,7} | {(4,0,5,2,3,6,7,1),6,2} | 1.18552 |
4 | {(1,2,3,4,5,6,7,0),7,4} | {(3,6,0,1,7,2,4,5),5,6} | {(7,0,1,2,3,4,5,6),4,7} | {(6,7,5,0,2,3,1,4),2,1} | {(2,6,4,5,1,7,3,0),1,0} | {(5,3,7,4,6,2,0,1),3,2} | {(4,5,6,7,3,0,1,2),6,3} | 1.18571 |
5 | {(1,2,3,4,5,6,7,0),7,6} | {(2,5,4,1,7,0,3,6),3,4} | {(6,0,4,7,3,2,5,1),2,5} | {(4,6,7,2,1,3,5,0),6,0} | {(5,4,6,1,2,7,0,3),4,1} | {(3,7,0,5,2,6,1,4),5,2} | {(7,3,1,0,6,4,2,5),1,7} | 1.18571 |
6 | {(1,2,3,4,5,6,7,0),7,4} | {(2,5,6,0,3,7,1,4),6,3} | {(6,7,5,2,1,4,3,0),2,0} | {(3,6,0,4,7,1,2,5),3,6} | {(4,6,5,7,2,3,0,1),1,5} | {(7,4,1,6,0,2,5,3),5,7} | {(5,0,7,1,3,2,4,6),4,2} | 1.18591 |
7 | {(4,3,6,0,7,2,1,5),6,2} | {(7,0,5,2,1,4,3,6),2,6} | {(3,7,5,6,0,1,2,4),1,5} | {(6,5,7,1,3,2,4,0),5,3} | {(5,4,0,7,3,6,1,2),4,1} | {(1,2,3,4,5,7,0,6),7,4} | {(2,7,1,4,6,0,5,3),3,7} | 1.18591 |
8 | {(6,4,1,5,7,2,3,0),5,4} | {(7,6,5,1,2,3,0,4),2,1} | {(1,2,7,0,3,4,5,6),7,3} | {(4,0,5,7,3,6,1,2),4,5} | {(2,7,3,1,5,0,4,6),3,6} | {(5,4,0,2,6,1,7,3),1,7} | {(3,5,4,6,0,2,7,1),6,2} | 1.18591 |
9 | {(1,2,3,4,5,7,0,6),7,3} | {(7,0,6,1,2,4,3,5),3,4} | {(2,3,7,5,0,4,1,6),5,6} | {(5,7,0,1,6,3,2,4),6,1} | {(6,5,1,2,7,0,4,3),1,7} | {(3,4,5,6,7,1,2,0),4,2} | {(4,5,3,0,1,6,7,2),2,5} | 1.18611 |
10 | {(1,2,3,4,7,0,5,6),7,2} | {(2,6,5,0,3,7,4,1),6,5} | {(7,3,5,2,0,4,1,6),2,6} | {(6,0,7,1,2,3,4,5),5,4} | {(4,5,0,7,1,6,3,2),3,1} | {(5,7,4,6,1,3,2,0),4,3} | {(3,2,6,7,5,1,0,4),1,7} | 1.18611 |
11 | {(3,4,5,7,0,6,1,2),6,5} | {(4,7,1,0,6,2,5,3),1,2} | {(1,2,3,4,5,7,0,6),7,4} | {(7,0,5,2,1,4,3,6),2,6} | {(2,3,6,4,7,0,1,5),3,1} | {(6,5,7,1,3,2,4,0),5,3} | {(5,7,0,6,3,1,2,4),4,7} | 1.18611 |
12 | {(5,7,0,2,6,4,1,3),1,1} | {(7,0,6,4,1,2,3,5),3,2} | {(2,5,7,6,3,0,1,4),6,3} | {(3,7,5,1,0,6,4,2),2,7} | {(4,3,1,0,7,2,5,6),5,6} | {(1,2,3,4,5,7,0,6),7,4} | {(6,4,5,7,3,1,2,0),4,5} | 1.18611 |
13 | {(6,7,3,1,5,2,4,0),5,1} | {(7,4,5,2,6,1,0,3),2,4} | {(4,0,5,7,3,6,1,2),4,5} | {(3,5,4,6,0,2,7,1),6,2} | {(5,6,0,1,2,3,7,4),3,7} | {(1,2,7,0,3,4,5,6),7,3} | {(2,4,1,5,7,0,3,6),1,6} | 1.18611 |
14 | {(3,6,0,7,1,2,5,4),5,6} | {(1,2,3,4,5,6,7,0),7,4} | {(2,3,6,4,7,0,1,5),3,1} | {(6,7,4,5,0,2,1,3),6,2} | {(4,5,1,6,3,7,2,0),4,0} | {(5,6,7,2,3,4,0,1),1,3} | {(7,4,5,0,6,1,3,2),2,7} | 1.18631 |
15 | {(4,6,1,0,7,2,3,5),5,6} | {(1,2,3,4,5,6,7,0),7,4} | {(2,4,6,7,3,1,5,0),4,0} | {(6,7,4,5,0,2,1,3),6,2} | {(3,5,0,4,6,7,1,2),3,1} | {(5,6,7,2,3,4,0,1),1,3} | {(7,3,5,6,1,0,2,4),2,7} | 1.18631 |
16 | {(6,7,5,4,2,1,3,0),4,5} | {(4,3,6,2,1,0,7,5),1,7} | {(7,4,5,1,6,3,0,2),2,1} | {(3,0,1,5,2,6,7,4),6,2} | {(5,3,0,6,7,4,2,1),5,3} | {(1,2,7,0,3,4,5,6),7,4} | {(2,5,3,1,0,7,4,6),3,6} | 1.18651 |
17 | {(5,4,0,1,7,6,3,2),3,4} | {(2,5,4,1,6,0,7,3),6,1} | {(6,4,3,7,5,2,1,0),1,2} | {(3,7,1,5,0,2,4,6),5,6} | {(1,2,7,0,3,4,5,6),7,3} | {(7,6,5,2,3,1,0,4),4,5} | {(4,0,5,6,2,3,7,1),2,7} | 1.18671 |
18 | {(6,4,1,7,5,3,2,0),4,4} | {(4,0,5,2,3,6,7,1),6,2} | {(7,6,3,1,5,2,0,4),2,5} | {(3,4,0,5,2,7,1,6),1,6} | {(2,3,4,0,6,1,7,5),5,7} | {(5,7,6,2,0,1,4,3),3,1} | {(1,2,3,4,7,0,5,6),7,3} | 1.18671 |
19 | {(7,4,5,6,2,3,0,1),4,5} | {(3,0,1,5,2,6,7,4),6,2} | {(6,3,5,4,7,1,2,0),2,3} | {(4,3,6,2,1,0,7,5),1,7} | {(5,7,0,1,6,4,3,2),5,1} | {(2,5,3,1,0,7,4,6),3,6} | {(1,2,7,0,3,4,5,6),7,4} | 1.18730 |
20 | {(1,2,3,4,5,6,7,0),7,1} | {(5,3,0,6,7,4,2,1),5,6} | {(6,7,5,1,2,0,3,4),6,2} | {(4,6,7,5,2,1,0,3),4,7} | {(2,5,4,0,1,7,3,6),1,3} | {(7,5,1,6,0,3,4,2),3,5} | {(3,0,7,2,6,4,1,5),2,4} | 1.18750 |
21 | {(1,2,3,4,5,6,7,0),7,1} | {(6,4,5,0,3,7,2,1),2,3} | {(3,7,0,6,1,2,4,5),6,2} | {(2,6,7,5,0,1,4,3),1,4} | {(7,6,4,1,3,0,5,2),4,6} | {(5,3,1,7,6,2,0,4),5,7} | {(4,0,5,7,2,3,1,6),3,5} | 1.18750 |
22 | {(1,2,3,4,5,7,0,6),7,3} | {(7,6,1,5,0,2,4,3),6,5} | {(2,4,7,5,3,0,1,6),3,6} | {(3,0,5,6,7,1,4,2),5,4} | {(5,7,6,1,2,4,3,0),1,2} | {(6,3,0,7,2,1,5,4),4,1} | {(4,7,3,0,1,6,2,5),2,7} | 1.18750 |
23 | {(1,2,3,4,7,0,5,6),7,2} | {(5,6,0,2,3,7,4,1),4,7} | {(4,2,6,7,3,1,0,5),1,3} | {(6,4,5,0,2,7,1,3),5,1} | {(3,0,4,5,1,6,7,2),2,5} | {(2,7,4,6,5,3,1,0),6,4} | {(7,3,1,5,0,4,2,6),3,6} | 1.18750 |
24 | {(5,4,0,1,7,6,3,2),3,4} | {(2,5,4,1,6,0,7,3),6,1} | {(4,0,3,7,5,2,1,6),5,6} | {(7,4,5,6,2,3,0,1),1,5} | {(6,7,1,5,3,2,4,0),4,2} | {(1,2,7,0,3,4,5,6),7,3} | {(3,6,5,2,0,1,7,4),2,7} | 1.18790 |
25 | {(1,2,3,4,5,6,7,0),7,4} | {(2,3,5,0,6,7,1,4),6,5} | {(3,6,0,1,7,2,4,5),5,6} | {(5,0,7,4,2,3,1,6),3,1} | {(6,7,5,2,1,4,3,0),2,0} | {(7,6,4,5,0,1,2,3),1,7} | {(4,5,6,7,3,2,0,1),4,2} | 1.18869 |
26 | {(1,2,3,4,5,6,7,0),7,4} | {(2,3,5,0,6,7,1,4),6,5} | {(7,0,1,2,3,4,5,6),4,7} | {(3,6,4,5,7,2,0,1),1,2} | {(6,7,5,1,3,0,4,2),2,3} | {(4,5,6,7,1,2,3,0),5,0} | {(5,6,7,4,0,1,2,3),3,6} | 1.18869 |
27 | {(1,2,3,4,5,6,7,0),7,4} | {(2,5,6,0,3,7,1,4),6,3} | {(4,6,0,7,1,2,3,5),1,2} | {(6,7,1,2,3,4,5,0),4,0} | {(5,6,7,4,0,1,2,3),3,6} | {(3,4,5,6,7,0,1,2),2,1} | {(7,3,4,5,6,2,0,1),5,7} | 1.18869 |
28 | {(1,2,3,4,5,6,7,0),7,4} | {(5,3,7,0,6,2,1,4),5,1} | {(4,0,5,7,3,1,2,6),2,3} | {(3,4,5,6,7,0,1,2),6,5} | {(6,7,1,4,0,2,5,3),3,2} | {(7,5,6,2,3,4,0,1),4,7} | {(2,6,4,5,1,7,3,0),1,0} | 1.18869 |
29 | {(1,2,3,4,5,6,7,0),7,4} | {(3,0,5,2,7,4,1,6),2,1} | {(2,3,5,4,6,7,0,1),3,5} | {(5,4,7,6,2,3,1,0),6,0} | {(4,6,1,7,3,0,5,2),4,6} | {(7,6,4,5,0,1,2,3),1,7} | {(6,7,0,1,3,2,4,5),5,3} | 1.18909 |
48 | {(1,2,3,4,5,6,7,0),7,4} | {(3,0,5,2,7,4,1,6),2,1} | {(2,3,4,5,6,7,1,0),6,0} | {(6,7,5,4,1,0,3,2),3,5} | {(5,6,7,0,3,1,2,4),1,3} | {(4,5,6,7,3,2,0,1),4,2} | {(7,4,1,6,0,2,5,3),5,7} | 1.18930 |
31 | {(1,2,3,4,5,6,7,0),7,7} | {(7,4,1,2,6,0,5,3),3,4} | {(3,4,6,1,7,2,0,5),1,6} | {(2,7,6,5,3,1,4,0),2,0} | {(4,5,0,2,1,7,3,6),4,2} | {(6,3,5,0,1,4,7,2),6,1} | {(5,6,4,7,0,3,2,1),5,5} | 1.19028 |
32 | {(3,4,0,6,2,7,5,1),3,3} | {(6,7,5,2,0,4,1,3),1,4} | {(4,6,1,7,5,3,0,2),4,1} | {(7,3,1,5,6,0,2,4),2,2} | {(1,2,3,4,5,6,7,0),7,5} | {(2,5,6,1,7,4,3,0),5,0} | {(5,7,4,0,3,1,2,6),6,7} | 1.19028 |
33 | {(1,2,3,4,5,6,7,0),7,4} | {(6,7,5,0,2,3,1,4),6,5} | {(3,6,4,5,7,2,0,1),5,6} | {(2,5,6,4,0,7,1,3),3,1} | {(5,0,7,1,3,2,4,6),4,2} | {(7,6,0,2,1,4,3,5),1,7} | {(4,3,5,7,6,1,2,0),2,0} | 1.19087 |
34 | {(1,2,3,4,5,6,7,0),7,4} | {(6,7,5,0,2,3,1,4),6,5} | {(3,6,4,5,7,2,0,1),1,2} | {(5,4,7,6,0,2,1,3),5,1} | {(4,6,5,7,1,0,3,2),2,6} | {(2,5,6,1,3,7,4,0),4,0} | {(7,3,0,4,6,1,2,5),3,7} | 1.19127 |
35 | {(1,2,3,4,5,6,7,0),7,4} | {(3,6,4,5,7,2,0,1),5,6} | {(6,7,5,0,2,3,1,4),2,1} | {(2,6,5,1,0,7,4,3),1,5} | {(4,3,0,7,6,2,1,5),6,2} | {(5,4,7,6,3,1,2,0),4,0} | {(7,5,6,4,1,0,3,2),3,7} | 1.19186 |
36 | {(1,2,3,4,5,6,7,0),7,4} | {(6,7,5,1,3,0,4,2),2,3} | {(2,3,5,4,6,7,0,1),3,5} | {(3,5,6,2,7,4,1,0),6,0} | {(7,0,4,5,3,1,2,6),4,7} | {(5,4,7,6,0,2,1,3),5,1} | {(4,6,0,7,1,2,3,5),1,2} | 1.19306 |
37 | {(1,2,3,4,5,6,7,0),7,4} | {(2,6,5,0,1,7,3,4),2,6} | {(3,5,6,1,7,2,4,0),5,0} | {(6,7,4,5,3,0,1,2),4,1} | {(5,6,7,2,3,4,0,1),1,3} | {(4,3,0,7,6,2,1,5),6,2} | {(7,0,1,4,2,3,5,6),3,7} | 1.19325 |
38 | {(1,2,3,4,5,6,7,0),7,4} | {(5,3,7,0,6,2,1,4),5,1} | {(3,6,0,4,7,1,2,5),3,6} | {(7,4,5,6,2,3,0,1),2,7} | {(2,6,5,1,0,7,4,3),1,5} | {(4,5,6,7,3,0,1,2),6,3} | {(6,7,1,2,3,4,5,0),4,0} | 1.19325 |
39 | {(1,2,3,4,5,6,7,0),7,4} | {(5,6,7,1,0,2,4,3),1,2} | {(6,7,1,0,3,2,5,4),5,3} | {(2,3,4,5,6,7,1,0),6,0} | {(7,5,6,2,3,4,0,1),4,7} | {(3,0,5,4,7,1,2,6),3,5} | {(4,6,5,7,1,0,3,2),2,6} | 1.19425 |
40 | {(1,2,3,4,5,6,7,0),7,4} | {(2,6,5,0,1,7,3,4),2,6} | {(4,6,1,7,2,3,5,0),1,0} | {(3,4,5,6,7,0,1,2),6,5} | {(7,0,4,5,3,1,2,6),4,7} | {(6,7,0,1,3,2,4,5),5,3} | {(5,3,7,4,6,2,0,1),3,2} | 1.19464 |
41 | {(1,2,3,4,5,6,7,0),7,7} | {(4,5,7,2,6,0,3,1),6,4} | {(5,0,1,7,2,3,4,6),3,2} | {(2,3,4,6,7,1,0,5),2,1} | {(7,4,6,0,3,1,5,2),5,0} | {(6,7,0,5,2,4,1,3),4,3} | {(3,6,5,1,0,7,2,4),1,5} | 1.19504 |
42 | {(4,5,6,0,1,7,3,2),2,3} | {(1,2,3,4,5,6,7,0),7,5} | {(3,6,5,7,0,4,2,1),5,6} | {(6,7,0,2,3,4,1,5),6,4} | {(5,3,7,6,2,1,4,0),1,0} | {(2,0,4,1,7,3,5,6),4,2} | {(7,4,1,5,6,2,0,3),3,1} | 1.19504 |
43 | {(1,2,3,4,5,6,7,0),7,4} | {(5,6,7,1,0,2,4,3),1,2} | {(4,5,6,7,1,2,3,0),5,0} | {(7,0,1,4,2,3,5,6),3,7} | {(3,4,5,6,7,0,1,2),2,1} | {(6,7,0,2,3,4,1,5),6,3} | {(2,6,4,5,3,7,0,1),4,6} | 1.19544 |
44 | {(6,5,0,7,1,3,4,2),6,0} | {(5,4,7,6,3,2,0,1),5,3} | {(4,7,6,1,2,0,3,5),3,5} | {(7,6,4,5,0,1,2,3),1,7} | {(2,6,1,0,3,7,5,4),4,6} | {(3,0,5,2,7,4,1,6),2,1} | {(1,2,3,4,5,6,7,0),7,4} | 1.19544 |
45 | {(1,2,3,4,5,6,7,0),7,4} | {(3,5,6,1,7,2,4,0),5,0} | {(5,0,7,4,2,3,1,6),3,1} | {(6,7,4,5,0,2,1,3),6,2} | {(4,6,1,7,3,0,5,2),4,6} | {(2,4,5,6,3,7,0,1),2,3} | {(7,6,0,2,1,4,3,5),1,7} | 1.19583 |
46 | {(1,2,3,4,5,6,7,0),7,6} | {(3,0,5,7,1,4,2,6),2,3} | {(5,4,6,1,2,7,0,3),3,2} | {(6,7,1,2,3,0,4,5),1,4} | {(7,3,5,6,0,1,4,2),6,5} | {(2,5,7,0,6,3,1,4),4,0} | {(4,6,0,5,7,2,3,1),5,1} | 1.19603 |
47 | {(1,2,3,4,5,6,7,0),7,7} | {(3,7,4,5,6,1,0,2),5,4} | {(7,6,0,1,2,4,5,3),4,3} | {(6,3,1,7,2,0,4,5),3,2} | {(2,5,6,0,3,7,1,4),2,0} | {(4,0,5,2,7,1,3,6),6,1} | {(5,4,7,6,0,3,2,1),1,5} | 1.19603 |
48 | {(6,0,7,1,3,2,5,4),4,1} | {(3,5,4,6,1,7,2,0),6,0} | {(4,3,6,5,7,0,1,2),3,6} | {(5,4,6,7,2,3,0,1),2,3} | {(1,2,3,4,5,6,7,0),7,5} | {(7,6,5,2,0,1,4,3),5,4} | {(2,7,1,0,6,4,3,5),1,2} | 1.19623 |