A New Class of MDS Erasure Codes Based on Graphs

Author

Puttarak, Nattakan ; Kaewprapha, Phisan ; Boon Chong Ng ; Jing Li

Author_Institution

Dept. of Electr. & Comput. Eng., Lehigh Univ., Bethlehem, PA, USA

fYear

2009

Firstpage

1

Lastpage

6

Abstract

Maximum distance separable (MDS) array codes are XOR-based optimal erasure codes that are particularly suitable for use in disk arrays. This paper develops an innovative method to build MDS array codes from an elegant class of nested graphs, termed complete-graph-of-rings (CGR). We discuss a systematic and concrete way to transfer these graphs to array codes, unveil an interesting relation between the proposed map and the renowned perfect 1-factorization, and show that the proposed CGR codes subsume B-codes as their "contracted" codes. These new codes, termed CGR codes, and their dual codes are simple to describe, and require minimal encoding and decoding complexity.

Keywords

computational complexity; decoding; error correction codes; graph theory; matrix decomposition; MDS erasure codes; XOR-based optimal erasure codes; complete-graph-of-rings; disk arrays; maximum distance separable array codes; minimal encoding-decoding complexity; subsume B-codes; Availability; Concrete; Decoding; Educational institutions; Encoding; Fault tolerance; Industrial relations; Parity check codes; Scalability; Throughput;

fLanguage

English

Publisher

ieee

Conference_Titel

Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE

Conference_Location

Honolulu, HI

ISSN

1930-529X

Print_ISBN

978-1-4244-4148-8

Type

conf

DOI

10.1109/GLOCOM.2009.5426134

Filename

5426134