TY - JOUR
T1 - Strong Coordination over Noisy Channels
AU - Obead, Sarah A.
AU - Vellambi, Badri N.
AU - Kliewer, Jorg
N1 - Funding Information:
Manuscript received August 14, 2018; revised October 7, 2020; accepted February 12, 2021. Date of publication March 2, 2021; date of current version April 21, 2021. This work was supported by NSF under Grant CCF-1440014, Grant CCF-1439465, and Grant CNS-1526547. This article was presented in part at the 2017 IEEE International Symposium on Information Theory (ISIT) [1] and in part at the 55th Annual Allerton Conference [2]. (Corresponding author: Sarah A. Obead.) Sarah A. Obead and Jörg Kliewer are with the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07102 USA (e-mail: sao23@njit.edu; jkliewer@njit.edu).
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2021/5
Y1 - 2021/5
N2 - We study the problem of strong coordination of the actions of two nodes $\mathsf X$ and $\mathsf Y$ that communicate over a discrete memoryless channel (DMC) such that the actions follow a prescribed joint probability distribution. We propose two novel random coding schemes and a polar coding scheme for this noisy strong coordination problem, and derive inner and outer bounds for the respective strong coordination capacity region. The first scheme is a joint coordination-channel encoding scheme that utilizes the randomness provided by the communication channel to reduce the amount of local randomness required to generate the sequence of actions at Node $\mathsf Y$. Based on this random coding scheme, we provide a characterization of the capacity region for a special case of the noisy strong coordination setup, namely, when the DMC is a deterministic channel. The second scheme exploits separate coordination and channel encoding where local randomness is extracted from the channel after decoding. Moreover, by leveraging the random coding results for this problem, we present an example in which the proposed joint encoding scheme is able to strictly outperform the separate encoding scheme in terms of achievable communication rate for the same amount of injected randomness into both systems. Thus, we establish the sub-optimality of the separation of strong coordination and channel encoding with respect to the communication rate over the DMC in this problem. Finally, the third scheme is a joint coordination-channel polar coding scheme for strong coordination. We show that polar codes are able to achieve the established inner bound to the strong noisy coordination capacity region and thus provide a constructive alternative to a random coding proof. Our polar coding scheme also offers a constructive solution to a channel simulation problem where a DMC and shared randomness are employed together to simulate another DMC.
AB - We study the problem of strong coordination of the actions of two nodes $\mathsf X$ and $\mathsf Y$ that communicate over a discrete memoryless channel (DMC) such that the actions follow a prescribed joint probability distribution. We propose two novel random coding schemes and a polar coding scheme for this noisy strong coordination problem, and derive inner and outer bounds for the respective strong coordination capacity region. The first scheme is a joint coordination-channel encoding scheme that utilizes the randomness provided by the communication channel to reduce the amount of local randomness required to generate the sequence of actions at Node $\mathsf Y$. Based on this random coding scheme, we provide a characterization of the capacity region for a special case of the noisy strong coordination setup, namely, when the DMC is a deterministic channel. The second scheme exploits separate coordination and channel encoding where local randomness is extracted from the channel after decoding. Moreover, by leveraging the random coding results for this problem, we present an example in which the proposed joint encoding scheme is able to strictly outperform the separate encoding scheme in terms of achievable communication rate for the same amount of injected randomness into both systems. Thus, we establish the sub-optimality of the separation of strong coordination and channel encoding with respect to the communication rate over the DMC in this problem. Finally, the third scheme is a joint coordination-channel polar coding scheme for strong coordination. We show that polar codes are able to achieve the established inner bound to the strong noisy coordination capacity region and thus provide a constructive alternative to a random coding proof. Our polar coding scheme also offers a constructive solution to a channel simulation problem where a DMC and shared randomness are employed together to simulate another DMC.
KW - Strong coordination
KW - channel resolvability
KW - joint source-channel coding
KW - polar codes
KW - superposition coding
UR - http://www.scopus.com/inward/record.url?scp=85102292179&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102292179&partnerID=8YFLogxK
U2 - 10.1109/TIT.2021.3063140
DO - 10.1109/TIT.2021.3063140
M3 - Article
AN - SCOPUS:85102292179
SN - 0018-9448
VL - 67
SP - 2716
EP - 2738
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 5
M1 - 9366940
ER -