Academic
Publications
Low-density MDS codes and factors of complete graphs

Low-density MDS codes and factors of complete graphs,10.1109/18.782102,IEEE Transactions on Information Theory,Lihao Xu,Vasken Bohossian,Jehoshua Bruc

Low-density MDS codes and factors of complete graphs   (Citations: 65)
BibTex | RIS | RefWorks Download
We present a class of array code of size , where or , called B-Code. The distances of the B-Code and its dual are and , respectively. The B-Code and its dual are optimal in the sense that i) they are maximum-distance separable (MDS), ii) they have an optimal encoding property, i.e., the number of the parity bits that are affected by change of a single information bit is minimal, and iii) they have optimal length. Using a new graph description of the codes, we prove an equivalence relation between the construction of the B-Code (or its dual) and a combinatorial problem known as perfect one- factorization of complete graphs, thus obtaining constructions of two families of the B-Code and its dual, one of which is new. Efficient decoding algorithms are also given, both for erasure correcting and for error correcting. The existence of perfect one- factorizations for every complete graph with an even number of nodes is a 35 years long conjecture in graph theory. The construction of B-Codes of arbitrary odd length will provide an affirmative answer to the conjecture.
Journal: IEEE Transactions on Information Theory - TIT , vol. 45, no. 6, pp. 1817-1836, 1999
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Examples of MDS array codes are EVENODD [1], [2], B-code [3], X-code [4], RDP [5], and STAR-code [6]...
    • ...and the corresponding permutation of v is [2, 3, 0, 1]. In addition, we define Xv as the set of integers x in [0, 2 m − 1] such that the inner product between their binary representation and v satisfies x · v = 0, e.g., X (1,0) = {0, 1}. The construction of the two parity columns is as follows: The first parity column is simply the row sums...
    • ...and the permutation f l v is [2, 0, 1, 5, 3, 4, 8, 6, 7]. For x ∈ [0, r m − 1], we define the zigzag set Zx in parity node l as the elements ai,j such that their coordinates satisfy f l vj (i) = x...

    Itzhak Tamoet al. MDS Array Codes with Optimal Rebuilding

    • ...Xu, et al. [12] found the equivalence between the con-...

    Chao Jinet al. Extending and analysis of X-Code

    • ...RAID-6 Code ED-2 Code MDS B-code [20] YES YES X-code [8] YES YES BCP code [21] YES YES ZZS code [22] YES YES WEAVER codes [11] YES NO LSI code [23] YES NO EVENODD [9] NO YES RDP [10] NO YES...

    Jianqiang Luoet al. SCAN: An Efficient Decoding Algorithm for RAID6 Codes

    • ...Given a data item to be encoded with an erasure code (n,k), the algorithm produces n � k fragments; m fragments are necessary and sufficient to recover the original data item, where k � m � n. When m ¼ k, the erasure code algorithm is said to be optimal [19]...

    Andrea Bondavalliet al. The HIDENETS Holistic Approach for the Analysis of Large Critical Mobi...

    • ...According to the structure and distribution of different parities, MDS codes can be categorized into horizontal codes [30], [5], [3], [8], [4], [28], [27] and vertical codes [6], [41], [42], [23]...
    • ...3) Vertical Parity (VP): Vertical parity normally appears in vertical codes, such as in B-Code [41] and P-Code [23]...
    • ...Researchers have presented many RAID-6 implementations based on various erasure coding technologies, including Reed-Solomon code [30], Cauchy Reed-Solomon code [5], EVENODD code [3], RDP code [8], Blaum-Roth code [4], Liberation code [28], Liber8tion code [27], Cyclic code [6], B-Code [41], X-Code [42], and P-Code [23]...

    Chentao Wuet al. HDP code: A Horizontal-Diagonal Parity Code to Optimize I/O load balan...

Sort by: