On the Capacity of Noisy Computations

Details On the Capacity of Noisy Computations On the Capacity of Noisy Computations

2011-05-16

arxiv.org/abs/1105.3068v1

Computer Science

Information Theory

This paper has been submitted to the Information Theory Workshop 2011

Scientific paper

This paper presents an analysis of the concept of capacity for noisy computations, i.e. algorithms implemented by unreliable computing devices (e.g. noisy Turing Machines). The capacity of a noisy computation is defined and justified by companion coding theorems. Under some constraints on the encoding process, capacity is the upper bound of input rates allowing reliable computation, i.e. decodability of noisy outputs into expected outputs. A model of noisy computation of a perfect function f thanks to an unreliable device F is given together with a model of reliable computation based on input encoding and output decoding. A coding lemma (extending the Feinstein's theorem to noisy computations), a joint source-computation coding theorem and its converse are proved. They apply if the input source, the function f, the noisy device F and the cascade f^{-1}F induce AMS and ergodic one-sided random processes.

Affiliated with

Also associated with

No associations

Rating

On the Capacity of Noisy Computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Capacity of Noisy Computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Capacity of Noisy Computations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-77307