skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Friday, September 13 until 2:00 AM ET on Saturday, September 14 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the NSF-PAR

This content will become publicly available on October 6, 2024

Title: Achievable Rates for Low-Complexity Posterior Matching over the Binary Symmetric Channel
Horstein, Burnashev, Shayevitz and Feder, Naghshvar et al . and others have studied sequential transmission of a k-bit message over the binary symmetric channel (BSC) with full, noiseless feedback using posterior matching. Yang et al . provide an improved lower bound on the achievable rate using martingale analysis that relies on the small-enough difference (SED) partitioning introduced by Naghshvar et al . SED requires a relatively complex encoder and decoder. To reduce complexity, this paper replaces SED with relaxed constraints that admit the small enough absolute difference (SEAD) partitioning rule. The main analytical results show that achievable-rate bounds higher than those found by Yang et al . [2] are possible even under the new constraints, which are less restrictive than SED. The new analysis does not use martingale theory for the confirmation phase and applies a surrogate channel technique to tighten the results. An initial systematic transmission further increases the achievable rate bound. The simplified encoder associated with SEAD has a complexity below order O ( K 2 ) and allows simulations for message sizes of at least 1000 bits. For example, simulations achieve 99% of of the channel’s 0.50-bit capacity with an average block size of 200 bits for a target codeword error rate of 10 -3.  more » « less
Award ID(s):
1955660
NSF-PAR ID:
10510038
Author(s) / Creator(s):
; ;
Publisher / Repository:
IEEE
Date Published:
Journal Name:
IEEE Transactions on Information Theory
ISSN:
0018-9448
Page Range / eLocation ID:
1-27
Subject(s) / Keyword(s):
Posterior matching, binary symmetric channel, noiseless feedback, random coding
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ( , 2020 IEEE International Symposium on Information Theory (ISIT))
    null (Ed.)
    In this paper, we consider the problem of sequential transmission over the binary symmetric channel (BSC) with full, noiseless feedback. Naghshvar et al. proposed a one-phase encoding scheme, for which we refer to as the small-enough difference (SED) encoder, which can achieve capacity and Burnashev's optimal error exponent for symmetric binary-input channels. They also provided a non-asymptotic upper bound on the average blocklength, which implies an achievability bound on rates. However, their achievability bound is loose compared to the simulated performance of SED encoder, and even lies beneath Polyanskiy's achievability bound of a system limited to stop feedback. This paper significantly tightens the achievability bound by using a Markovian analysis that leverages both the submartingale and Markov properties of the transmitted message. Our new non-asymptotic lower bound on achievable rate lies above Polyanskiy's bound and is close to the actual performance of the SED encoder over the BSC. 
    more » « less
  2. ; ; ( , 2021 IEEE International Symposium on Information Theory (ISIT))
    Traditional communication systems transmit a codeword only after all message bits are available at the transmitter. This paper joins Guo & Kostina and Lalitha et al. in developing approaches for causal encoding, where the transmitter may begin transmitting codeword symbols as soon as the first message bit arrives. Building on the posterior matching encoders of Horstein, Shayevitz & Feder, and Naghshvar et al., this paper extends our computationally efficient systematic encoder to progressively encode using only the message bits that are causally available. Systematic codes work well with posterior matching on a channel with feedback, and they provide an immediate benefit when causal encoding is employed instead of traditional encoding. Our algorithm captures additional gains in the interesting region where the transmission rate μ is higher than the source rate λ at which message bits become available. In this region, we improve performance further through the transmission of additional, non- systematic symbols before a traditional encoder would have even begun transmission. 
    more » « less
  3. ; ; ( , 2020 IEEE International Symposium on Information Theory (ISIT))
    null (Ed.)
    Building on the work of Horstein, Shayevitz and Feder, and Naghshvar et al., this paper presents algorithms for low-complexity sequential transmission of a k-bit message over the binary symmetric channel (BSC) with full, noiseless feedback. To lower complexity, this paper shows that the initial k binary transmissions can be sent before any feedback is required and groups messages with equal posteriors to reduce the number of posterior updates from exponential in k to linear in k. Simulation results demonstrate that achievable rates for this full, noiseless feedback system approach capacity rapidly as a function of average blocklength, faster than known finite-blocklength lower bounds on achievable rate with noiseless active feedback and significantly faster than finite-blocklength lower bounds for a stop feedback system. 
    more » « less
  4. ; ( , IEEE)
    This paper presents new achievability bounds on the maximal achievable rate of variable-length stop-feedback (VLSF) codes operating over a binary erasure channel (BEC) at a fixed message size M=2^k . We provide bounds for two cases: The first case considers VLSF codes with possibly infinite decoding times and zero error probability. The second case limits the maximum (finite) number of decoding times and specifies a maximum tolerable probability of error. Both new achievability bounds are proved by constructing a new VLSF code that employs systematic transmission of the first k message bits followed by random linear fountain parity bits decoded with a rank decoder. For VLSF codes with infinite decoding times, our new bound outperforms the state-of-the-art result for BEC by Devassy et al. in 2016. We show that the backoff from capacity reduces to zero as the erasure probability decreases, thus giving a negative answer to the open question Devassy et al. posed on whether the 23.4% backoff to capacity at k=3 is fundamental to all BECs. For VLSF codes with finite decoding times, numerical evaluations show that the systematic transmission followed by random linear fountain coding performs better than random linear coding in terms of achievable rates. 
    more » « less
  5. ; ; ( , IEEE control systems letters)
    In this letter, we consider a Linear Quadratic Gaussian (LQG) control system where feedback occurs over a noiseless binary channel and derive lower bounds on the minimum communication cost (quantified via the channel bitrate) required to attain a given control performance. We assume that at every time step an encoder can convey a packet containing a variable number of bits over the channel to a decoder at the controller. Our system model provides for the possibility that the encoder and decoder have shared randomness, as is the case in systems using dithered quantizers. We define two extremal prefix-free requirements that may be imposed on the message packets; such constraints are useful in that they allow the decoder, and potentially other agents to uniquely identify the end of a transmission in an online fashion. We then derive a lower bound on the rate of prefix-free coding in terms of directed information; in particular we show that a previously known bound still holds in the case with shared randomness. We generalize the bound for when prefix constraints are relaxed, and conclude with a rate-distortion formulation. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email