Computing linear transforms with unreliable components
Yaoqing Lamar Yang, Pulkit Grover, Soummya Kar · 2016
We consider the problem of computing a binary linear transform when all circuit components are unreliable. We propose a novel “ENCODED” technique that uses LDPC (low-density parity-check) codes and embedded noisy decoders to keep the error probability of the computation below a small constant independent of the size of the linear transform, even when all logic gates in the computation are prone to probabilistic errors. Unlike existing works on applying coding to computing with unreliable components, the “ENCODED” technique explicitly considers the errors that happen during both the encoding and the decoding phases. Further, we show that ENCODED requires fewer operations (in order sense) than repetition techniques.