Role of Feedback in Modulo-Sum Computation over K-User Erasure Multiple-Access Channels

I-Hsiang Wang*, Yu-Chih Huang, Shih-Chun Lin

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


The modulo-sum computation of messages over a K-user finite-field erasure multiple access channel (MAC) is studied, with emphasis on the role of feedback in the large system regime. For the non-feedback case, we propose a grouping scheme which has higher computation rate than that of the conventional "compute-and-forward" (CF) scheme where each transmitter uses the same linear code and the receiver leverages the additive structure of the multiple access channel to compute the modulo sum. Furthermore, with a growing number of users, the proposed grouping scheme strictly outperforms the conventional "decode-and-forward (DF)" scheme when the erasure probability is smaller than 1 - e(1/e) approximate to 0.3078, where the receiver first decodes messages of all users and then computes the modulo sum. This is in contrast to the two-user case where the currently best known achievability, reported by Khisti, Hern, and Narayanan in 2013, coincides with the better one between DF and CF. For the case with delayed state feedback, a new hybrid-ARQ-type scheme is proposed, and in the large system regime, it achieves a computation rate scaling like Omega(1/log (K)), much higher than the scaling Theta(1/K) achieved by the grouping scheme without feedback. Our result hints at significant gain in function computation due to feedback in the large system regime when the transmitters are connected intermittently to the receiver, in sharp contrast to the static case where feedback provides no gain at all.

Original languageEnglish
Title of host publication2017 IEEE INFORMATION THEORY WORKSHOP (ITW)
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781509030972
StatePublished - 2017
Event2017 IEEE Information Theory Workshop, ITW 2017 - Kaohsiung, Taiwan
Duration: 6 Nov 201710 Nov 2017

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Conference2017 IEEE Information Theory Workshop, ITW 2017

Cite this