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.  Google Scholar

[2]

R. Ahlswede, Coloring hypergraphs: A new approach to multi-user source coding-II, J. Comb. Inform. Syst. Sci., 5 (1980), 220-268.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

V. Blinovsky, P. Narayan and M. Pinsker, Capacity of the arbitrarily varying channel under list decoding, Probl. Pered. Inform., 31 (1995), 99-113.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

V. Guruswami, Bridging Shannon and Hamming: List error-correction with optimal rate, in Proc. ICM, Hyderabad, 2010.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

J.-H. Jahn, Coding of arbitrarily varying multiuser channels, IEEE Trans. Inf. Theory, 27 (1981), 212-226. doi: 10.1109/TIT.1981.1056320.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[31]

J. Wolfowitz, Simultaneous channels, Arch. Rat. Mech. Anal., 4 (1960), 371-386.  Google Scholar

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.  Google Scholar

[2]

R. Ahlswede, Coloring hypergraphs: A new approach to multi-user source coding-II, J. Comb. Inform. Syst. Sci., 5 (1980), 220-268.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

V. Blinovsky, P. Narayan and M. Pinsker, Capacity of the arbitrarily varying channel under list decoding, Probl. Pered. Inform., 31 (1995), 99-113.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

V. Guruswami, Bridging Shannon and Hamming: List error-correction with optimal rate, in Proc. ICM, Hyderabad, 2010.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

J.-H. Jahn, Coding of arbitrarily varying multiuser channels, IEEE Trans. Inf. Theory, 27 (1981), 212-226. doi: 10.1109/TIT.1981.1056320.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[31]

J. Wolfowitz, Simultaneous channels, Arch. Rat. Mech. Anal., 4 (1960), 371-386.  Google Scholar

[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 & 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 & 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 & Management Optimization, 2021, 17 (3) : 1485-1504. doi: 10.3934/jimo.2020031
[11]

Shuhua Chang, Yameng Wang, Xinyu Wang, Kok Lay Teo. Pricing and energy efficiency decisions by manufacturer under channel coordination. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021033
[12]

Wei Chen, Fuying Jing, Li Zhong. Coordination strategy for a dual-channel electricity supply chain with sustainability. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021139
[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]

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

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

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

Jinghuan Li, Shuhua Zhang, Yu Li. Modelling and computation of optimal multiple investment timing in multi-stage capacity expansion infrastructure projects. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020154
[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 & Management Optimization, 2010, 6 (1) : 73-102. doi: 10.3934/jimo.2010.6.73
[19]

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

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences