Kybernetika 50 no. 6, 1003-1031, 2014

On capacity regions of discrete asynchronous multiple access channels

Lóránt Farkas and Tamás KóiDOI: 10.14736/kyb-2014-6-1003


A general formalization is given for asynchronous multiple access channels which admits different assumptions on delays. This general framework allows the analysis of so far unexplored models leading to new interesting capacity regions. The main result is the single letter characterization of the capacity region in case of 3 senders, 2 synchronous with each other and the third not synchronous with them.


delay, partly asynchronous, multiple-access, rate splitting, successive decoding




  1. R. Ahlswede: Multi-way communication channels. In: Proc. 2nd International Symposium on Information Theory, Tsahkadsor, Armenian SSR (1971), Akadémiai Kiadó, Budapest, pp. 23-52.   CrossRef
  2. M. Bierbaum and H. M. Wallmeier: A note on the capacity region of the multi-access channel. IEEE Trans. Inform. Theory 25 (1979), 484.   CrossRef
  3. T. M. Cover, R. J. McEliece and E. C. Posner: Asynchronous multiple-acces channel capacity. IEEE Trans. Inform. Theory 27 (1981), 409-413.   CrossRef
  4. I. Csisz{á}r and J. K{ö}rner: Information theory, Coding theorems for Discrete Memoryless Systems Second edition. Cambridge University Press, Cambridge 2011.   CrossRef
  5. L. Farkas and T. Kói: Capacity region of discrete asynchronous multiple access channels. Int. Symp. Inform. Theory Proc. (ISIT) 19 (2011), 2273-2277.   CrossRef
  6. L. Farkas and T. Kói: Capacity regions of partly asynchronous multiple access channels. Int. Symp. Inform. Theory Proc. (ISIT) 20 (2012), 3018-3022.   CrossRef
  7. A. El Gamal and Y.-H. Kim: Network Information Theory. Cambridge University Press, Cambridge 2012   CrossRef
  8. A. J. Grant, B. Rimoldi, R. L. Urbanke and P. A. Whiting: Rate-splitting multiple acces for discrete memoryless channels. IEEE Trans. Inform. Theory 47 (2001), 873-890.   CrossRef
  9. R. M. Gray: Sliding-block joint source/noisy-channel coding theorems. IEEE Trans. Inform. Theory 22 (1976), 682-690.   CrossRef
  10. S. Hanly and P. Whiting: Constraints on capacity in a multi-user channel. Int. Symp. Inform. Theory Proc. (ISIT) 4 (1994), 54.   CrossRef
  11. J. Y. N. Hui and P. A. Humblet: The capacity region of the totally asynchronous multiple-access channel. IEEE Trans. Inform. Theory 31 (1985), 207-216.   CrossRef
  12. H. Liao: Multiple Access Channels. Ph.D. Dissertation, Dept. Elec. Eng., Univ. Hawai, Honolulu 1972.   CrossRef
  13. B. Rimoldi: Generalized time sharing: A low-complexity capacity-achieving multiple-access technique. IEEE Trans. Inform. Theory 47 (2001), 2432-2442.   CrossRef
  14. D. Tse and S. Hanly: Multi-access fading channels - Part I: Polymatroid structure, optimal resource allocation and throughput capacities. IEEE Trans. Inform. Theory 44 (1998), 2796-2815.   CrossRef
  15. G. Sh. Poltyrev: Coding in an asynchronous multiple-access channel. Problemy Peredachi Informatsii 19 (1983), 12-21.   CrossRef
  16. Y. Polyanskiy: On asynchronous capacity and dispersion. In: 46th Annual Conference on Information Sciences and Systems (CISS) (2012), pp. 1-6.   CrossRef
  17. A. Tchamkerten, V. Chandar and G. W. Wornell: Communication under strong asynchronism. IEEE Trans. Inform. Theory 55 (2009), 4508-4528.   CrossRef
  18. S. Verdu: Multiple-access channels with memory with and without frame synchronism. IEEE Trans. Inform. Theory 35 (1989), 605-619.   CrossRef