Randomness and Noise in Information Systems.

摘要

This dissertation is devoted to the study of randomness and noise in a number of information systems including computation systems, storage systems, and natural paradigms like molecular systems, where randomness plays important and distinct roles. Motivated by applications in engineering and science we address a number of theoretical research questions. • In a computation system, randomness enables to perform tasks faster, simpler, or more space efficient. Hence, randomness is a useful computational resource, and the research question we address is: How to efficiently extract randomness from natural sources? • In a molecular system such as a chemical reaction network or a gene regulatory network, randomness is inherent and serves as the key mechanism for producing the desired quantities of molecular species. A chemical reaction can be abstractly described as a probabilistic switch. Hence, given a set of probabilistic switches (with some fixed switching probabilities), the research question we address is: How to synthesize a stochastic network consisting of those switches that computes a pre-specified probability distribution? • In an information storage system, like flash memories where information is represented by a relatively small number of electrons, randomness is a threat to data reliability. Hence, the research question we address is: How to represent, write and read information in the presence of randomness (noise)?;This dissertation is focusing on the foregoing key questions and describes novel contributions related to randomness generation and extraction, stochastic system synthesis and coding for information storage.