EE Seminar: Interaction in Gaussian and Binary Channels
Speaker: Assaf Ben-Yishai
Ph.D. student under the supervision of Prof. Ofer Shayevitz
Monday, November 4th, 2019 at 15:00
Room 206, Wolfson Mechanical Eng. Bldg., Faculty of Engineering
Interaction in Gaussian and Binary Channels
Abstract
The celebrated channel coding theorem proved by Claude Shannon in 1948, shows that information can be reliably conveyed over a noisy channel as long as its rate does not exceed a fundamental limit called the channel capacity. The scenario considered in Shannon’s original paper (and in the majority of the works following it), is where one user sends a long predetermined message to another user over a noisy channel using a codebook, i.e., by encoding the message into a codeword – a long predetermined sequence of channel inputs. In this research, we study two basic two-party communication scenarios that are richer than the prototypical problem considered by Shannon.
In the first part of the research, we study the additive white Gaussian noise (AWGN) channel with noisy feedback. The AWGN with clean feedback has been originally studied by Schalkwijk & Kailath in 1966. They presented a coding scheme (the SK-scheme) based on scalar arithmetic and achieving remarkable improvement in the delay vs. reliability tradeoff compared to communication without feedback. However, this scheme is known to fail in the presence of arbitrarily low noise in the feedback channel. We show that the susceptibility to feedback noise can be overcome by using modulo-arithmetic over the feedback, maintaining essentially the same low-complexity as the SK-scheme. Our new scheme provides a fast decay in the error probability at rates close to the Shannon capacity, provided that the signal-to-noise ratio of the feedback channel is sufficiently larger than that of the feedforward channel. The idea of applying modulo operations over the feedback is then leveraged to obtain two more contributions: improved error exponents for the AWGN with noisy feedback, and a new achievable rate region for the AWGN broadcast channel with an AWGN multiple-access feedback.
In the second part of the research, we study the problem of interactive communication over binary-input channels. In this setup, originally presented by Schulman in 1992 and motivated by distributed computing, two parties wish to simulate an interactive protocol over a pair of noisy channels. In contrast to Shannon’s setup, the information exchanged by the parties is not predetermined but rather generated on-the-fly during the course of communication. Our first contribution is a structured coding scheme based on extended-Hamming codes and randomized error detection, which is proved to reliably simulate any protocol at a coding rate of at least 0.302 the Shannon channel capacity, for any binary-input symmetric-output memoryless channel. We further show that the randomness required by the scheme can be harvested from the channel, giving rise to a fully deterministic coding scheme.
An exact characterization of the interactive capacity for general protocols remains notoriously elusive to date. It is commonly believed that the interactive capacity is strictly smaller than the Shannon capacity; this was recently shown to be the case in the infinitesimal noise regime by Kol & Raz. Nevertheless, rather surprisingly, we show that the full Shannon capacity can be achieved when simulating arbitrary two-state protocols, as well as broad classes of finite-state protocols with a bounded number of states.
