Using a simple yet rigorous approach, Algebraic and Stochastic coding theory makes the subject of coding theory easy to understand for readers with a thorough knowledge of digital arithmetic, Boolean and modern algebr...
详细信息
ISBN:
(纸本)9781439881811;1439881812
Using a simple yet rigorous approach, Algebraic and Stochastic coding theory makes the subject of coding theory easy to understand for readers with a thorough knowledge of digital arithmetic, Boolean and modern algebra, and probability theory. It explains the underlying principles of coding theory and offers a clear, detailed description of each code. More advanced readers will appreciate its coverage of recent developments in coding theory and stochastic processes. After a brief review of coding history and Boolean algebra, the book introduces linear codes, including Hamming and Golay codes. It then examines codes based on the Galois field theory as well as their application in BCH and especially the ReedSolomon codes that have been used for error correction of data transmissions in space missions. The major outlook in coding theory seems to be geared toward stochastic processes, and this book takes a bold step in this direction. As research focuses on error correction and recovery of erasures, the book discusses belief propagation and distributions. It examines the low-density parity-check and erasure codes that have opened up new approaches to improve wide-area network data transmission. It also describes modern codes, such as the Luby transform and Raptor codes, that are enabling new directions in high-speed transmission of very large data to multiple users. This robust, self-contained text fully explains coding problems, illustrating them with more than 200 examples. Combining theory and computational techniques, it will appeal not only to students but also to industry professionals, researchers, and academics in areas such as coding theory and signal and image processing.
The P300-based brain-computer interface (BCI) speller relies on eliciting and detecting specific brain responses to target stimulus events, termed event-related potentials (ERPs). In a visual speller, ERPs are elicite...
详细信息
ISBN:
(纸本)9781509041183
The P300-based brain-computer interface (BCI) speller relies on eliciting and detecting specific brain responses to target stimulus events, termed event-related potentials (ERPs). In a visual speller, ERPs are elicited when the user's desired character, i.e. the "target," is flashed on a computer screen. The P300 speller is currently limited by its relatively slow typing speed due to the need for repetitive data measurements that are necessary to achieve reasonable signal-to-noise ratios. In addition, refractory effects limit the ability to elicit ERPs with every target stimulus event presentation. In this paper, we present a new method to design the stimulus presentation paradigm for the P300 speller by exploiting an information-theoretic approach to maximize the information content that is presented to the user while also mitigating refractory effects. We present results with real-time BCI use which demonstrate significant performance improvements with our performance-based paradigm compared to the conventional stimulus presentation paradigm.
Collected here are papers that were presented at or inspired by the DIMACS workshop, Algebraic coding theory and Information theory (Rutgers University, Piscataway, NJ). Among the topics discussed are universal data c...
详细信息
ISBN:
(纸本)0821836269
Collected here are papers that were presented at or inspired by the DIMACS workshop, Algebraic coding theory and Information theory (Rutgers University, Piscataway, NJ). Among the topics discussed are universal data compression, graph theoretical ideas in the construction of codes and lattices, decoding algorithms, and computation of capacity in various communications schemes. The book is suitable for graduate students and researchers interested in coding and information theory.
We introduce a quantity which is called Rényi's-Tsalli's entropy of order and discussed some of its major properties with Shannon and other entropies in the literature. Further, we give its application in...
详细信息
Data availability is critical in distributed storage systems, especially when node failures are prevalent in real life. A key requirement is to minimize the amount of data transferred among nodes when recovering the l...
详细信息
Data availability is critical in distributed storage systems, especially when node failures are prevalent in real life. A key requirement is to minimize the amount of data transferred among nodes when recovering the lost or unavailable data of failed nodes. This paper explores recovery solutions based on regenerating codes, which have been designed to provide fault-tolerant storage and minimum bandwidth. Existing optimal regenerating codes are designed for single node failures. We build a system called CORE, which augments existing optimal regenerating codes for the recovery of a general number of failures including single and concurrent failures. We show theoretically that CORE achieves the minimum possible bandwidth for most cases. We implement a CORE prototype and evaluate it atop an HDFS cluster testbed with up to 20 storage nodes. We demonstrate that our CORE prototype conforms to our theoretical findings and achieves bandwidth savings when compared to the conventional recovery approach based on erasure codes.
Although the expenses associated with DNA sequencing have been rapidly decreasing, the current cost of sequencing information stands at roughly ${\$}120$ /GB, which is dramatically more expensive than reading from exi...
详细信息
Although the expenses associated with DNA sequencing have been rapidly decreasing, the current cost of sequencing information stands at roughly ${\$}120$ /GB, which is dramatically more expensive than reading from existing archival storage solutions today. In this work, we aim to reduce not only the cost but also the latency of DNA storage by initiating the study of the DNA coverage depth problem, which aims to reduce the required number of reads to retrieve information from the storage system. Under this framework, our main goal is to understand the effect of error-correcting codes and retrieval algorithms on the required sequencing coverage depth. We establish that the expected number of reads that are required for information retrieval is minimized when the channel follows a uniform distribution. We also derive upper and lower bounds on the probability distribution of this number of required reads and provide a comprehensive upper and lower bound on its expected value. We further prove that for a noiseless channel and uniform distribution, MDS codes are optimal in terms of minimizing the expected number of reads. Additionally, we study the DNA coverage depth problem under the random-access setup, in which the user aims to retrieve just a specific information unit from the entire DNA storage system. We prove that the expected retrieval time is at least k for [n,k] MDS codes as well as for other families of codes. Furthermore, we present explicit code constructions that achieve expected retrieval times below k and evaluate their performance through analytical methods and simulations. Lastly, we provide lower bounds on the maximum expected retrieval time. Our findings offer valuable insights for reducing the cost and latency of DNA storage.
暂无评论