betaFeedback

WorksComputer Science

Rates and Nearly-Lossless State over a Multi-Access Channel with Causal State Information

Abstract

The problem of transmitting both data and state over a memoryless state-dependent multi-access channel with causal state information is addressed. The state comprises three independent components: a common component, which is revealed to both en- coders, and two private components, each of which is revealed to a different encoder. The data are to be recovered with arbitrarily-small probability of error, and the state sequence with arbitrarily-small symbol-error rate. Under the assumption that the capacity region in the absence of a state recon- struction constraint is nonempty, the capacity region is derived and is shown to be achievable using a Block-Markov coding scheme employing binning and superposition coding.

Introduction

This paper studies the communication rates that can be supported by a state-dependent discrete memoryless multi-access channel (SD-MAC) when, in addition to recovering the transmitted data reliably, the receiver must also recover the state sequence. We assume that the state is revealed to the transmitters causally and that the receiver must reconstruct the state sequence “almost losslessly,” i.e., that the error rate in its reconstruction of the state sequence must vanish with the blocklength.

We do not address the case where some distortion is allowed in the state reconstruction. Our work can thus be viewed as an extension of [3] to multi-access networks, albeit for the special case of zero distortion. We also do not consider feedback, which is studied in the single-user case (with distortion constraints) in [2]. Finally, we only consider memoryless SD-MACs where the state is IID. The general case is beyond the scope of this paper, but see [11] for the Gilbert-Elliott single-user channel.

To address different architectures, we model the state SS as comprising three independent components: a component S0S_0 that is revealed to both encoders, a component S1S_1 that is revealed only to Encoder 1 and a component S2S_2 that is revealed only to Encoder 2; see Figure 1. Special cases are the “common state” architecture (where the multi-access is governed by a single state sequence that is revealed to both encoders) and the “independent states” architecture (where the channel is governed by two independent states each of which is revealed to a different encoder).

Figure 1. The network under consideration.

Our main result is a characterization of the capacity region, i.e., the set of rate pairs that can be reliably transmitted over the network under the constraint that the receiver recover the state sequence “almost losslessly,” i.e., with vanishing symbol error rate. The coding scheme we propose is a Block-Markov scheme with backward decoding. Key is that, using superposition coding (as in [19]), the transmitters cooperate to transmit some of the past state information that they share. To guarantee that, once transmission terminates, the backward decoding can commence, we assume that the capacity region of the SD-MAC (with causal side-information but without any state-reconstruction constraints) has a nonempty interior.

It is noteworthy that introducing the state-reconstruction constraints makes the problem more tractable: The capacity region of the SD-MAC with causal state information (and no state-reconstruction constraints) is still unknown. It was studied in [9, 10, 13], where it was shown that Shannon strategies are not optimal and that strictly-causal state information is beneficial.

The literature on state-dependent channels is vast. We mention here a small fraction that focuses on both the data to be transmitted and the channel state. Sutivong et al. [20] studied joint message transmission and state estimation over Gaussian channels with noncausal encoder state information. Kim et al. [6] considered state amplification for both discrete and continuous channels with noncausal state information. Zhang et al. [22] studied joint message transmission and state estimation when the encoders know only the state distribution but not its realization; they also extended their results to multiple-access channels.

More recently, Li et al. [14] derived an achievable rate-distortion region for joint state and message communication over multiple-access channels with causal state information and generalized feedback. Subsequent work [15] developed a simultaneous-decoding approach and obtained improved achievable regions for multiuser channels. While our setting can be viewed as a special case of theirs (when the generalized feedback is useless, and the allowed distortion is zero), we provide an exact characterization of the capacity region for multiple-access channels under the nearly-lossless state-reconstruction requirement.

A complementary line of research concerns state masking, which seeks to limit the information about the state revealed to the receiver [17]. Le Treust and Bloch [12] studied both state masking and amplification within a unified framework. Also related are studies of integrated sensing and communication in which, rather than by the receivers, the state estimation is performed by the transmitters (utilizing channel feedback) [1, 7, 16].

The rest of the paper is organized as follows. After some notation, we turn to § 2, which describes the communication scenario in greater detail and which defines the capacity region we seek. § 3 presents the main theorem characterizing said region. The proof is presented in § 4 (converse) and § 5 (achievability).

Notation

When kk is a positive integer, [1:k][1 : k] denotes the set {1,…,k}\{1, \ldots, k\}. More generally, for any positive real number a>0a > 0, we use [1:a][1 : a] to denote the (possibly empty) set {1,2,…,⌊a⌋}\{1, 2, \ldots, \lfloor a \rfloor\}. Upper-case calligraphic fonts denote finite sets, e.g., S\mathcal{S} denotes the set of possible channel states. The nn-fold Cartesian product of a set A\mathcal{A} with itself is denoted A×n\mathcal{A}^{\times n} and comprises all nn-tuples with entries from A\mathcal{A}. The cardinality of a set A\mathcal{A} is denoted ∣A∣|\mathcal{A}|, so ∣S∣|\mathcal{S}| denotes the number of channel states. A random variable taking values in the set A\mathcal{A} is usually denoted AA and its Probability Mass Function (PMF) PAP_A. Hence, the random channel state SS takes values in SS and its PMF is PSP_S. A generic realization of such a random variable is usually denoted aa, so PS(s)P_S(s) is the probability that SS equals ss. Given a PMF PXP_X and a conditional PMF PY∣XP_{Y|X}, we write PXPY∣XP_XP_{Y|X} for the joint PMF that assigns the pair (x,y)(x,y) the probability PX(x)PY∣X(y∣x)P_X(x)P_{Y|X}(y|x). The indicator function of an event E\mathcal{E} is denoted I{E}\mathbb{I}\{\mathcal{E}\} and equals 1 if E\mathcal{E} holds and equals 0 otherwise. For example, I{x=y}\mathbb{I}\{x=y\} is 1 if x=yx=y, and is 0 otherwise.

The empirical PMF PanP_{a^n} of a sequence an∈Ana^n \in\mathcal{A}^n is defined as

Pan(a)≜1n∑i=1nI{ai=a},a∈A.(1)P_{a^n}(a) \triangleq\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\{a_i=a\}, \qquad a \in\mathcal{A}. \tag*{(1)}

Given a PMF PAP_A on A\mathcal{A} and some δ>0\delta>0, the strongly δ\delta-typical set Tδ(n)(PA)T_{\delta}^{(n)}(P_A) is defined as in [18 Definition 4.1]:

Tδ(n)(PA)≜{an∈An:(∣Pan(a)−PA(a)∣<δ∣A∣, ∀a∈A) and ((PA(a)=0)⇒(Pan(a)=0))}.(2)T_{\delta}^{(n)}(P_A) \triangleq\left\{a^n \in\mathcal{A}^n : \left(\left|P_{a^n}(a)-P_A(a)\right| < \frac{\delta}{|\mathcal{A}|},\ \forall a \in\mathcal{A}\right) \text{ and } \left((P_A(a)=0) \Rightarrow(P_{a^n}(a)=0)\right)\right\}. \tag*{(2)}

We abbreviate Tδ(n)(PA)T_{\delta}^{(n)}(P_A) as Tδ(n)(A)T_{\delta}^{(n)}(A). More generally, Tδ(n)(A1,…,Am)T_{\delta}^{(n)}(A_1,\ldots,A_m) denotes the strongly typical set with respect to the joint PMF PA1⋯AmP_{A_1\cdots A_m} on A1×⋯×Am\mathcal{A}_1 \times\cdots\times\mathcal{A}_m. All logarithms are of base two. The binary entropy function is denoted by Hb(p)H_b(p).

The Setup

We consider a two-to-one SD-MAC with finite input alphabets X1\mathcal{X}_1, X2\mathcal{X}_2 and with a finite output alphabet Y\mathcal{Y}. The state alphabet S\mathcal{S} is finite and has the form

S=S0×S1×S2(3)\mathcal{S} = \mathcal{S}_0 \times\mathcal{S}_1 \times\mathcal{S}_2 \tag*{(3)}

so the time ii state SiS_i is a triple

Si=(S0,i,S1,i,S2,i).(4)S_i = (S_{0,i}, S_{1,i}, S_{2,i}). \tag*{(4)}

The states {Si}\{S_i\} are IID ∼PS\sim P_S, with PSP_S having the product form

PS=PS0PS1PS2.(5)P_S = P_{S_0}P_{S_1}P_{S_2}. \tag*{(5)}

The three components S0,iS_{0,i}, S1,iS_{1,i}, S2,iS_{2,i} of the Time-ii state SiS_i are thus independent and of PMFs PS0P_{S_0}, PS1P_{S_1}, and PS2P_{S_2}. By possibly redefining the state alphabet, we may assume—as we shall—that PSP_S is of full support (i.e., that PS(s)P_S(s) is positive for every state s∈Ss \in\mathcal{S}). Conditional on the states, the channel is memoryless, and we denote its law by PY∣X1X2S0S1S2P_{Y|X_1X_2S_0S_1S_2} or WY∣X1X2S0S1S2W_{Y|X_1X_2S_0S_1S_2}.

Each encoder wishes to convey a message to the decoder: Encoder 1 wishes to convey M1M_1 and Encoder 2 M2M_2. The two messages are independent, with M1M_1 uniformly distributed over the set M1=[1:2nR1]\mathcal{M}_1 = [1 : 2^{nR_1}], and with M2M_2 uniformly distributed over M2=[1:2nR2]\mathcal{M}_2 = [1 : 2^{nR_2}]. Here nn denotes the blocklength, and R1R_1, R2R_2 denote the rates of transmission in bits per channel-use.

The sequences {S0,i}\{S_{0,i}\} and {S1,i}\{S_{1,i}\} are revealed to Encoder 1 causally, so the symbol X1,i=X1,i(M1,S0i,S1i)X_{1,i} = X_{1,i}(M_1,S_0^i,S_1^i) it produces at Time-ii can depend not only on its message M1M_1 but also on the present-and-past values of the sequences {S0,i}\{S_{0,i}\} and {S1,i}\{S_{1,i}\}. Encoder 1 is thus specified by nn functions

f1,i:M1×S0×i×S1×i→X1,i∈[1:n](6)f_{1,i}:\mathcal{M}_1 \times\mathcal{S}_0^{\times i} \times\mathcal{S}_1^{\times i} \to\mathcal{X}_1,\qquad i \in[1:n] \tag*{(6)}

References

  1. [1]Mehrasa Ahmadipour, Mari Kobayashi, Michèle Wigger, and Giuseppe Caire. An information-theoretic approach to joint sensing and communication. IEEE Transactions on Information Theory, 70(2):1124–1146, 2024.
  2. [2]Shraga I. Bross and Amos Lapidoth. The rate-and-state capacity with feedback. IEEE Transactions on Information Theory, 64(3):1893–1918, 2018.DOI
  3. [3]Chiranjib Choudhuri, Young-Han Kim, and Urbashi Mitra. Causal state communication. IEEE Transactions on Information Theory, 59(6):3709–3719, 2013.
  4. [4]Abbas El Gamal and Young-Han Kim. Network Information Theory. Cambridge University Press, 2011.
  5. [5]Alexander J. Grant, Bixio Rimoldi, Rüdiger L. Urbanke, and Philip A. Whiting. Rate-splitting multiple access for discrete memoryless channels. IEEE Transactions on Information Theory, 47(3):873–890, 2001.DOI
  6. [6]Young-Han Kim, Arak Sutivong, and Thomas M. Cover. State amplification. IEEE Transactions on Information Theory, 54(5):1850–1859, 2008.
  7. [7]Mari Kobayashi, Hassan Hamad, Gerhard Kramer, and Giuseppe Caire. Joint state sensing and communication over memoryless multiple access channels. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 270–274. IEEE, 2019.arxiv.org/abs/1902.03775
  8. [8]Amos Lapidoth, Baohua Ni, and Ligong Wang. The equivalence of causal and noncausal state information on bipartite networks with state-cognizant receivers. arXiv preprint arXiv:2604.25504, 2026.arxiv.org/abs/2604.25504
  9. [9]Amos Lapidoth and Yossef Steinberg. The multiple-access channel with causal side information: Common state. IEEE Transactions on Information Theory, 59(1):32–50, 2013.DOI
  10. [10]Amos Lapidoth and Yossef Steinberg. The multiple-access channel with causal side information: Double state. IEEE Transactions on Information Theory, 59(3):1379–1393, 2013.DOI
  11. [11]Amos Lapidoth and Ligong Wang. Rate and nearly-lossless state over the Gilbert–Elliott channel. Entropy, 27(5):494, 2025.DOI
  12. [12]Maël Le Treust and Matthieu R. Bloch. State leakage and coordination with causal state knowledge at the encoder. IEEE Transactions on Information Theory, 67(2):805–823, 2021.arxiv.org/abs/1812.07026
  13. [13]Min Li, Osvaldo Simeone, and Aylin Yener. Multiple access channels with states causally known at transmitters. IEEE Transactions on Information Theory, 59(3):1394–1404, 2013.DOI
  14. [14]Xinyang Li, Vlad C. Andrei, Ullrich J. Mönich, and Holger Boche. An achievable rate-distortion region for joint state and message communication over multiple access channels. In 2024 IEEE Information Theory Workshop (ITW), pages 109–114. IEEE, 2024.arxiv.org/abs/2409.17950
  15. [15]Xinyang Li, Yiqi Chen, Vlad C. Andrei, Aladin Djuhera, Ullrich J. Mönich, and Holger Boche. A simultaneous decoding approach to joint state and message communications. IEEE Journal on Selected Areas in Communications, 44:107–120, 2026.arxiv.org/abs/2501.11133
  16. [16]Yao Liu, Min Li, An Liu, Lawrence Ong, and Aylin Yener. Fundamental limits of multiple-access integrated sensing and communication systems. IEEE Transactions on Information Theory, 71(6):4317–4341, 2025.DOI
  17. [17]Neri Merhav and Shlomo Shamai. Information rates subject to state masking. IEEE Transactions on Information Theory, 53(6):2254–2261, 2007.DOI
  18. [18]Stefan M. Moser. Advanced topics in information theory. Lecture notes, 6th edition, 2025. Version 6.5, ETH Zurich and National Yang Ming Chiao Tung University.
  19. [19]David Slepian and Jack K. Wolf. Noiseless coding of correlated information sources. IEEE Transactions on Information Theory, 19(4):471–480, 1973.DOI
  20. [20]Arak Sutivong, Mung Chiang, Thomas M. Cover, and Young-Han Kim. Channel capacity and state estimation for state-dependent Gaussian channels. IEEE Transactions on Information Theory, 51(4):1486–1495, 2005.DOI
  21. [21]John M. Wozencraft and Irwin Mark Jacobs. Principles of Communications Engineering. John Wiley & Sons, 1966.
  22. [22]Wenyi Zhang, Satish Vedantam, and Urbaśhi Mitra. Joint transmission and state estimation: A constrained channel coding approach. IEEE Transactions on Information Theory, 57(10):7084–7095, 2011.arxiv.org/abs/1104.0547

Paper details

vlnc:W_6gv8xj78
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents