American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes
  • AMC Home
  • This Issue
  • Next Article
    On $\omega$-cyclic-conjugated-perfect quaternary GDJ sequences
May  2016, 10(2): 333-354. doi: 10.3934/amc.2016009

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, Germany
2. 

Information Theory and Applications Chair, Technische Universität Berlin, Einsteinufer 25, 10587 Berlin, Germany

Received  May 2014 Published  April 2016

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: list decoding, capacity region, coordination resources, conferencing encoders, Arbitrarily varying multiple access channel, derandomization..
Mathematics Subject Classification: Primary: 94A15, 62B10; Secondary: 68P3.
Citation: Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009
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.

show all references

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.

[1]

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002
[2]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485
[3]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311
[4]

Lizhong Peng, Shujun Dang, Bojin Zhuang. Localization operator and digital communication capacity of channel. Communications on Pure and Applied Analysis, 2007, 6 (3) : 819-827. doi: 10.3934/cpaa.2007.6.819
[5]

Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331
[6]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259
[7]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179
[8]

Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031
[9]

Cheng Ma, Y. C. E. Lee, Chi Kin Chan, Yan Wei. Auction and contracting mechanisms for channel coordination with consideration of participants' risk attitudes. Journal of Industrial and Management Optimization, 2017, 13 (2) : 775-801. doi: 10.3934/jimo.2016046
[10]

Chong Zhang, Yaxian Wang, Ying Liu, Haiyan Wang. Coordination contracts for a dual-channel supply chain under capital constraints. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1485-1504. doi: 10.3934/jimo.2020031
[11]

Wei Chen, Fuying Jing, Li Zhong. Coordination strategy for a dual-channel electricity supply chain with sustainability. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021139
[12]

Shuhua Chang, Yameng Wang, Xinyu Wang, Kok Lay Teo. Pricing and energy efficiency decisions by manufacturer under channel coordination. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1557-1582. doi: 10.3934/jimo.2021033
[13]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007
[14]

Yuan Zhao, Wuyi Yue. Performance evaluation and optimization of cognitive radio networks with adjustable access control for multiple secondary users. Journal of Industrial and Management Optimization, 2019, 15 (1) : 1-14. doi: 10.3934/jimo.2018029
[15]

Chuan Ding, Kaihong Wang, Shaoyong Lai. Channel coordination mechanism with retailers having fairness preference ---An improved quantity discount mechanism. Journal of Industrial and Management Optimization, 2013, 9 (4) : 967-982. doi: 10.3934/jimo.2013.9.967
[16]

Chao Zhao, Jixiang Song. Coordination of dual-channel supply chain considering differential pricing and loss-aversion based on quality control. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022053
[17]

Nina Yan, Tingting Tong, Hongyan Dai. Capital-constrained supply chain with multiple decision attributes: Decision optimization and coordination analysis. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1831-1856. doi: 10.3934/jimo.2018125
[18]

Wai-Ki Ching, Sin-Man Choi, Min Huang. Optimal service capacity in a multiple-server queueing system: A game theory approach. Journal of Industrial and Management Optimization, 2010, 6 (1) : 73-102. doi: 10.3934/jimo.2010.6.73
[19]

Jinghuan Li, Shuhua Zhang, Yu Li. Modelling and computation of optimal multiple investment timing in multi-stage capacity expansion infrastructure projects. Journal of Industrial and Management Optimization, 2022, 18 (1) : 297-314. doi: 10.3934/jimo.2020154
[20]

Hongbiao Fan, Jun-E Feng, Min Meng. Piecewise observers of rectangular discrete fuzzy descriptor systems with multiple time-varying delays. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1535-1556. doi: 10.3934/jimo.2016.12.1535

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (143)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy