Optimal, Small, Systematic Parity-Check Erasure Codes -- A Brief Presentation
James S. Plank

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

Available as: .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.

Citation Info:

Authors: James S. Plank
Title: Optimal, Small, Systematic Parity-Check Erasure Codes -- A Brief Presentation
Institution: University of Tennessee Computer Science Department
Year: 2004
Month: July
Number: UT-CS-04-528
Where: http://loci.eecs.utk.edu/publications/2004_Systematic_Parity_Check_Codes.php