Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources

Holger  Boche; Rafael F.  Schaefer

doi:10.3934/amc.2016009

Article Contents

2016, Volume 10, Issue 2: 333-354. Doi: 10.3934/amc.2016009

This issue Previous Article On $\omega$-cyclic-conjugated-perfect quaternary GDJ sequences Next Article Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes

Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources

Holger Boche^1, and
Rafael F. Schaefer^2,

1.
Lehrstuhl für Theoretische Informationstechnik, Technische Universität München, 80290 München
2.
Information Theory and Applications Chair, Technische Universität Berlin, Einsteinufer 25, 10587 Berlin

Received: May 2014

Published online: April 2016

Abstract / Introduction Related Papers Cited by

Abstract

Communication over channels that may vary in an arbitrary and unknown manner from channel use to channel use is studied. Such channels fall in the framework of arbitrarily varying channels (AVCs), for which it has been shown that the classical deterministic approaches with pre-specified encoder and decoder fail if the AVC is symmetrizable. However, more sophisticated strategies such as common randomness (CR) assisted codes or list decoding are capable to resolve the ambiguity induced by symmetrizable AVCs. AVCs further serve as the indispensable basis for modeling adversarial attacks such as jamming in information theoretic security related communication problems. In this paper, we study the arbitrarily varying multiple access channel (AVMAC) with conferencing encoders, which models the communication scenario with two cooperating transmitters and one receiver. This can be motivated for example by cooperating base stations or access points in future systems. The capacity region of the AVMAC with conferencing encoders is established and it is shown that list decoding allows for reliable communication also for symmetrizable AVMACs. The list capacity region equals the CR-assisted capacity region for large enough list size. Finally, for fixed probability of decoding error the amount of resources, i.e., CR or list size, is quantified and shown to be finite.

Keywords:

Arbitrarily varying multiple access channel,
conferencing encoders,
list decoding,
coordination resources,
capacity region,
derandomization.

Mathematics Subject Classification: Primary: 94A15, 62B10; Secondary: 68P30.

Citation:

Related Papers

Cited by

References

[1]	R. Ahlswede, Elimination of correlation in random codes for arbitrarily carying channels, Z. Wahrscheinlichkeitstheorie verw. Gebiete, 44 (1978), 159-175.
[2]	R. Ahlswede, Coloring hypergraphs: A new approach to multi-user source coding-II, J. Comb. Inform. Syst. Sci., 5 (1980), 220-268.
[3]	R. Ahlswede, Arbitrarily varying channels with states sequence known to the sender, IEEE Trans. Inf. Theory, 32 (1986), 621-629.doi: 10.1109/TIT.1986.1057222.
[4]	R. Ahlswede and N. Cai, Two proofs of Pinsker's conjecture concerning arbitrarily varying channels, IEEE Trans. Inf. Theory, 37 (1991), 1647-1649.doi: 10.1109/18.104326.
[5]	R. Ahlswede and N. Cai, Arbitrarily varying multiple-access channels I - Ericson's symmetrizability is adequate, Gubner's conjecture is true, IEEE Trans. Inf. Theory, 45 (1999), 742-749.doi: 10.1109/18.749024.
[6]	P. Beelen and K. Brander, Efficient list decoding of a class of algebraic-geometry codes, Adv. Math. Commun., 4 (2010), 485-518.doi: 10.3934/amc.2010.4.485.
[7]	I. Bjelaković, H. Boche and J. Sommerfeld, Capacity results for arbitrarily varying wiretap channels, in Information Theory, Combinatorics, and Search Theory, Springer, 2013, 123-144.doi: 10.1007/978-3-642-36899-8_5.
[8]	D. Blackwell, L. Breiman and A. J. Thomasian, The capacity of a class of channels, Ann. Math. Stat., 30 (1959), 1229-1241.doi: 10.1214/aoms/1177706106.
[9]	D. Blackwell, L. Breiman and A. J. Thomasian, The capacities of certain channel classes under random coding, Ann. Math. Stat., 31 (1960), 558-567.doi: 10.1214/aoms/1177705783.
[10]	V. Blinovsky, P. Narayan and M. Pinsker, Capacity of the arbitrarily varying channel under list decoding, Probl. Pered. Inform., 31 (1995), 99-113.
[11]	H. Boche and J. Nötzel, The classical-quantum multiple access channel with conferencing encoders and with common messages, Quantum Inf. Proc., 13 (2014), 2595-2617.doi: 10.1007/s11128-014-0814-y.
[12]	H. Boche and R. F. Schaefer, Capacity results and super-activation for wiretap channels with active wiretappers, IEEE Trans. Inf. Forensics Sec., 8 (2013), 1482-1496.doi: 10.1109/TIFS.2013.2276049.
[13]	H. Boche and R. F. Schaefer, List decoding for arbitrarily varying multiple access channels with conferencing encoders, in Proc. IEEE Int. Conf. Commun., Sydney, 2014, 1934-1940.doi: 10.1109/ICC.2014.6883606.
[14]	H. Boche, R. F. Schaefer and H. V. Poor, On the continuity of the secrecy capacity of wiretap channels under channel uncertainty, in Proc. IEEE Int. Conf. Commun., London, 2015, 5779-5784.doi: 10.1109/ICC.2015.7248976.
[15]	I. Csiszár and P. Narayan, The capacity of the arbitrarily varying channel revisited: positivity, constraints, IEEE Trans. Inf. Theory, 34 (1988), 181-193.doi: 10.1109/18.2627.
[16]	J. A. Gubner, On the deterministic-code capacity of the multiple-access arbitrarily varying channel, IEEE Trans. Inf. Theory, 36 (1990), 262-275.doi: 10.1109/18.52472.
[17]	V. Guruswami, Bridging Shannon and Hamming: List error-correction with optimal rate, in Proc. ICM, Hyderabad, 2010.
[18]	F. Hernando, T. Høholdt and D. Ruano, List decoding of matrix-product codes from nested codes: an application to quasi-cyclic codes, Adv. Math. Commun., 6 (2012), 259-272.doi: 10.3934/amc.2012.6.259.
[19]	B. L. Hughes, The sSmalles list for the arbitrarily varying channel, IEEE Trans. Inf. Theory, 43 (1997), 803-815.doi: 10.1109/18.568692.
[20]	J.-H. Jahn, Coding of arbitrarily varying multiuser channels, IEEE Trans. Inf. Theory, 27 (1981), 212-226.doi: 10.1109/TIT.1981.1056320.
[21]	E. MolavianJazi, M. Bloch and J. N. Laneman, Arbitrary jamming can preclude secure communication, in Proc. 47th Ann. Allerton Conf. Commun. Control Comp., Urbana-Champaign, 2009, 1069-1075.doi: 10.1109/ALLERTON.2009.5394876.
[22]	S. Nitinawarat, On the deterministic code capacity region of an arbitrarily varying multiple-access channel under list decoding, IEEE Trans. Inf. Theory, 59 (2013), 2683-2693.doi: 10.1109/TIT.2013.2242514.
[23]	J. Nötzel, M. Wiese and H. Boche, The arbitrarily varying wiretap channel - secret randomness, stability and super-activation, in Proc. IEEE Int. Symp. Inf. Theory, Hong Kong, 2015, 2151-2155.doi: 10.1109/ISIT.2015.7282836.
[24]	A. D. Sarwate and M. Gastpar, List-decoding for the arbitrarily varying channel under state constraints, IEEE Trans. Inf. Theory, 58 (2012), 1372-1384.doi: 10.1109/TIT.2011.2178153.
[25]	R. F. Schaefer and H. Boche, List decoding for arbitrarily varying broadcast channels with receiver side information, IEEE Trans. Inf. Theory, 60 (2014), 4472-4487.doi: 10.1109/TIT.2014.2326412.
[26]	M. Wiese and H. Boche, The arbitrarily varying multiple-access channel with conferencing encoders, IEEE Trans. Inf. Theory, 59 (2013), 1405-1416.doi: 10.1109/TIT.2012.2229779.
[27]	M. Wiese and H. Boche, On the weakest resource for coordination in arbitrarily varying multiple access channels with conferencing encoders, Probl. Inf. Transm., 50 (2014), 15-26.doi: 10.1134/S0032946014010025.
[28]	M. Wiese, H. Boche, I. Bjelaković and V. Jungnickel, The compound multiple access channel with partially cooperating encoders, IEEE Trans. Inf. Theory, 57 (2011), 3045-3066.doi: 10.1109/TIT.2011.2119830.
[29]	M. Wiese, J. Nötzel and H. Boche, The arbitrarily varying wiretap channel - communication under uncoordinated attacks, in Proc. IEEE Int. Symp. Inf. Theory, Hong Kong, 2015, 2146-2150.doi: 10.1109/ISIT.2015.7282835.
[30]	F. M. J. Willems, The discrete memoryless multiple access channel with partially cooperating encoders, IEEE Trans. Inf. Theory, 29 (1983), 441-445.doi: 10.1109/TIT.1983.1056660.
[31]	J. Wolfowitz, Simultaneous channels, Arch. Rat. Mech. Anal., 4 (1960), 371-386.