Space Efficient Matrix Methods for Lost Data Reconstruction in Erasure Codes

In previous work, we showed how simple matrix manipulation algorithms can completely solve the problem of data reconstruction in a uniform way across all XOR-based erasure codes. In those algorithms, a workspace matrix is constructed and manipulated. At the end of the algorithm, XOR formulas for reconstructing lost data can be read directly from the workspace. Empty formulas implied irretrivable data loss. The dimension of the (square) workspace matrix was equal to the total number of “bits in the codeword”, i.e., the number of data and parity elements. In this paper, we show how the workspace can be reduced significantly. Sample (self-explanatory) Mathematica code is provided as well.

By: Bruce Cassidy, James Lee Hafner

Published in: RJ10415 in 2007


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .