The 48 Sets of Minimal Density MDS RAID-6 Matrices for a Word Size of Eight

James S. Plank

March 24, 2008

Technical Report UT-CS-08-611
Department of Computer Science
University of Tennessee
Knoxville, TN 37996

http://web.eecs.utk.edu/~plank/plank/papers/CS-08-611.html
PDF: http://web.eecs.utk.edu/~plank/plank/papers/CS-08-611.pdf


Citation Information


Please see the paper [Plank08] for all terminology related to RAID-6 coding using bit matrices.

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:

Xi = {Πi,ri,ci}

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.


# X1X2 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

Reference

[Plank 08] James S. Plank, ``The RAID-6 Liberation Codes,'' FAST-2008: 6th Usenix Conference on File and Storage Technologies, San Jose, CA, February, 2008.