Erasure Coding with the Finite Radon Transform

Abstract

The Mojette transform and the finite Radon transform (FRT) are discrete data projection methods that are exactly invertible and are computed using simple addition operations. Incorporation of a known level of redundancy into data and projection spaces enables the use of the FRT to recover the exact, original data when network packets are lost during data transmission. The FRT can also be shown to be Maximum Distance Separable (MDS). By writing the FRT transform in Vandermonde form, explicit expressions for discrete projection and inversion as matrix operations have been obtained. A cyclic, prime-sized Vandermonde form for the FRT approach is shown here to yield explicit polynomial expressions for the recovery of image rows from projected data and vice-versa. These polynomial solutions are consistent with the heuristic algorithms for "row-solving" that have been published previously. This formalism also opens the way to link "ghost" projections in FRT space and "anti-images" in data space that may provide a key to an efficient method of encoding and decoding general data sets in a systematic form.