Multiplication free holographic coding
Shlomi Dolev, Sergey L. Frenkel · 2010
Holographic coding has the very appealing property of obtaining partial information on data, from any part of the coded information. We present holographic coding schemes based on the Walsh orthogonal codes. The schemes use only addition for coding and decoding. We propose randomizing the data so that the value of the coefficient of the Walsh code will be approximately distributed normally to ensure, with high probability, a fixed gain of information. The data is XORed with randomly chosen bits from random data that has been stored during a preprocessing stage or pseudo-random data produced by a pseudo-random generator. We suggest schemes to cope with erasures in the scope of Walsh codes. We suggest parity based schemes to support the erasure correcting of the Walsh coefficient which can tolerate a bounded number of erasures without using multiplication. We then suggest a scheme based on Preparata use of discrete Fourier coefficients, extending the data with zeros. Lastly, we present a rateless erasure coding scheme.