Optimal, Small, Systematic Parity-Check Erasure Codes -- A Brief Presentation

Technical Report CS-04-528, University of Tennessee Department of Computer Science, July, 2004.

This paper has not yet been submitted for publication. At the moment it exists as a reference for systems programmers.

Available via anonymous ftp to cs.utk.edu in pub/plank/papers/CS-04-528.pdf

Abstract

Parity-check erasure codes are important alternatives to Reed-Solomon codes for wide-area storage and checkpointing applications. While the bulk of the research on these codes has been on large, and infinite-sized codes, there is an important need for systems programmers to utilize small codes. To this author's knowledge, there has been no presentation of optimal, small codes in the literature.

Let the number of data bits be n, and the number of coding bits be m. Let the average number of bits required to decode all bits in the code be o, otherwise termed the "overhead". Finally, let the computational overhead of a code be l.

In this paper, we present the optimal systematic codes for each value of n, m and l, such that (n+m)*m is less than or equal to 30. These codes have been derived by an exhaustive search of all codes. It is the intent of this paper to provide systems researchers and programmers with a reference that they may use when they need to evaluate and employ small codes in their applications.

PDF of the paper.
HTML of the paper.

Citation Information

Plain Text:

author          J. S. Plank 
title           Optimal, Small, Systematic Parity-Check Erasure Codes -- A Brief Presentation
number          UT-CS-04-528
institution     Department of Computer Science, University of Tennessee
month           July
year            2004
where           http://web.eecs.utk.edu/~jplank/plank/papers/CS-04-528.html

Bibtex:

@TECHREPORT{p:04:oss,
        author = "J. S. Plank ",
        title = "Optimal, Small, Systematic Parity-Check Erasure Codes -- A Brief Presentation",
        number = "UT-CS-04-528",
        institution = "Department of Computer Science, University of Tennessee",
        month = "July",
        year = "2004",
        where = "http://web.eecs.utk.edu/~jplank/plank/papers/CS-04-528.html"
}