Common-Message Broadcast Channels with Feedback in the Nonasymptotic Regime: Stop Feedback

Kasper Fløe Trillingsgaard, Wei Yang, Giuseppe Durisi, Petar Popovski

Research output: Contribution to journalJournal articleResearchpeer-review

1 Citation (Scopus)
57 Downloads (Pure)

Abstract

We investigate the maximum coding rate for a given average blocklength and error probability over a $K$-user discrete memoryless broadcast channel for the scenario where a common message is transmitted using variable-length stop-feedback codes. For the point-to-point case, Polyanskiy et al. (2011) demonstrated that variable-length coding combined with stop-feedback significantly increases the speed of convergence of the maximum coding rate to capacity. This speed-up manifests itself in the absence of a square-root penalty in the asymptotic expansion of the maximum coding rate for large blocklengths, i.e., zero dispersion. In this paper, we present nonasymptotic achievability and converse bounds on the maximum coding rate of the common-message $K$-user discrete memoryless broadcast channel, which strengthen and generalize the ones reported in Trillingsgaard et al. (2015) for the two-user case. An asymptotic analysis of these bounds reveals that zero dispersion cannot be achieved for certain common-message broadcast channels (e.g., the binary symmetric broadcast channel). Furthermore, we identify conditions under which our converse and achievability bounds are tight up to the second order. Through numerical evaluations, we illustrate that our second-order expansions approximate accurately the maximum coding rate and that the speed of convergence to capacity is indeed slower than for the point-to-point case.

Original languageEnglish
Article number8456639
JournalI E E E Transactions on Information Theory
Volume64
Issue number12
Pages (from-to)7686-7718
Number of pages33
ISSN0018-9448
DOIs
Publication statusPublished - 1 Dec 2018

Fingerprint

broadcast
coding
regime
Feedback
Asymptotic analysis
penalty
scenario
evaluation
Error probability

Keywords

  • Broadcast channel with common-message
  • channel dispersion
  • decision feedback
  • finite blocklength regime
  • stop feedback
  • variable-length coding

Cite this

@article{e1c9981160b44fdd87729e5c7c7e2440,
title = "Common-Message Broadcast Channels with Feedback in the Nonasymptotic Regime: Stop Feedback",
abstract = "We investigate the maximum coding rate for a given average blocklength and error probability over a $K$-user discrete memoryless broadcast channel for the scenario where a common message is transmitted using variable-length stop-feedback codes. For the point-to-point case, Polyanskiy et al. (2011) demonstrated that variable-length coding combined with stop-feedback significantly increases the speed of convergence of the maximum coding rate to capacity. This speed-up manifests itself in the absence of a square-root penalty in the asymptotic expansion of the maximum coding rate for large blocklengths, i.e., zero dispersion. In this paper, we present nonasymptotic achievability and converse bounds on the maximum coding rate of the common-message $K$-user discrete memoryless broadcast channel, which strengthen and generalize the ones reported in Trillingsgaard et al. (2015) for the two-user case. An asymptotic analysis of these bounds reveals that zero dispersion cannot be achieved for certain common-message broadcast channels (e.g., the binary symmetric broadcast channel). Furthermore, we identify conditions under which our converse and achievability bounds are tight up to the second order. Through numerical evaluations, we illustrate that our second-order expansions approximate accurately the maximum coding rate and that the speed of convergence to capacity is indeed slower than for the point-to-point case.",
keywords = "Broadcast channel with common-message, channel dispersion, decision feedback, finite blocklength regime, stop feedback, variable-length coding",
author = "Trillingsgaard, {Kasper Fl{\o}e} and Wei Yang and Giuseppe Durisi and Petar Popovski",
year = "2018",
month = "12",
day = "1",
doi = "10.1109/TIT.2018.2868953",
language = "English",
volume = "64",
pages = "7686--7718",
journal = "I E E E Transactions on Information Theory",
issn = "0018-9448",
publisher = "IEEE",
number = "12",

}

Common-Message Broadcast Channels with Feedback in the Nonasymptotic Regime : Stop Feedback. / Trillingsgaard, Kasper Fløe; Yang, Wei; Durisi, Giuseppe; Popovski, Petar.

In: I E E E Transactions on Information Theory, Vol. 64, No. 12, 8456639, 01.12.2018, p. 7686-7718.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Common-Message Broadcast Channels with Feedback in the Nonasymptotic Regime

T2 - Stop Feedback

AU - Trillingsgaard, Kasper Fløe

AU - Yang, Wei

AU - Durisi, Giuseppe

AU - Popovski, Petar

PY - 2018/12/1

Y1 - 2018/12/1

N2 - We investigate the maximum coding rate for a given average blocklength and error probability over a $K$-user discrete memoryless broadcast channel for the scenario where a common message is transmitted using variable-length stop-feedback codes. For the point-to-point case, Polyanskiy et al. (2011) demonstrated that variable-length coding combined with stop-feedback significantly increases the speed of convergence of the maximum coding rate to capacity. This speed-up manifests itself in the absence of a square-root penalty in the asymptotic expansion of the maximum coding rate for large blocklengths, i.e., zero dispersion. In this paper, we present nonasymptotic achievability and converse bounds on the maximum coding rate of the common-message $K$-user discrete memoryless broadcast channel, which strengthen and generalize the ones reported in Trillingsgaard et al. (2015) for the two-user case. An asymptotic analysis of these bounds reveals that zero dispersion cannot be achieved for certain common-message broadcast channels (e.g., the binary symmetric broadcast channel). Furthermore, we identify conditions under which our converse and achievability bounds are tight up to the second order. Through numerical evaluations, we illustrate that our second-order expansions approximate accurately the maximum coding rate and that the speed of convergence to capacity is indeed slower than for the point-to-point case.

AB - We investigate the maximum coding rate for a given average blocklength and error probability over a $K$-user discrete memoryless broadcast channel for the scenario where a common message is transmitted using variable-length stop-feedback codes. For the point-to-point case, Polyanskiy et al. (2011) demonstrated that variable-length coding combined with stop-feedback significantly increases the speed of convergence of the maximum coding rate to capacity. This speed-up manifests itself in the absence of a square-root penalty in the asymptotic expansion of the maximum coding rate for large blocklengths, i.e., zero dispersion. In this paper, we present nonasymptotic achievability and converse bounds on the maximum coding rate of the common-message $K$-user discrete memoryless broadcast channel, which strengthen and generalize the ones reported in Trillingsgaard et al. (2015) for the two-user case. An asymptotic analysis of these bounds reveals that zero dispersion cannot be achieved for certain common-message broadcast channels (e.g., the binary symmetric broadcast channel). Furthermore, we identify conditions under which our converse and achievability bounds are tight up to the second order. Through numerical evaluations, we illustrate that our second-order expansions approximate accurately the maximum coding rate and that the speed of convergence to capacity is indeed slower than for the point-to-point case.

KW - Broadcast channel with common-message

KW - channel dispersion

KW - decision feedback

KW - finite blocklength regime

KW - stop feedback

KW - variable-length coding

UR - http://www.scopus.com/inward/record.url?scp=85052891430&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2868953

DO - 10.1109/TIT.2018.2868953

M3 - Journal article

VL - 64

SP - 7686

EP - 7718

JO - I E E E Transactions on Information Theory

JF - I E E E Transactions on Information Theory

SN - 0018-9448

IS - 12

M1 - 8456639

ER -