On the Optimal Achievable Rates for Linear Computation With Random Homologous Codes

DOI10.1109/TIT.2020.3010253MaRDI QIDQ5138805zbMATH OpenOpenAlexFDO

Authors Pinar Sen, Sung Hoon Lim, Younghan Kim

Publication date 4 December 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.03338

zbMATH Keywords

bounds on optimal tradeoffcommunication rateslinear combination of sourcesmultiple access channelstructured nested coset codes

Mathematics Subject Classification ID

Source coding (94A29) Channel models (including quantum) in information and communication theory (94A40)

Abstract: The problem of computing a linear combination of sources over a multiple access channel is studied. Inner and outer bounds on the optimal tradeoff between the communication rates are established when encoding is restricted to random ensembles of homologous codes, namely, structured nested coset codes from the same generator matrix and individual shaping functions, but when decoding is optimized with respect to the realization of the encoders. For the special case in which the desired linear combination is "matched" to the structure of the multiple access channel in a natural sense, these inner and outer bounds coincide. This result indicates that most, if not all, coding schemes for computation in the literature that rely on random construction of nested coset codes cannot be improved by using more powerful decoders, such as the maximum likelihood decoder. The proof techniques are adapted to characterize the rate region for broadcast channels achieved by Marton's (random) coding scheme under maximum likelihood decoding.

Recommendations

• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• Decoding random linear codes in \(\tilde{\mathcal{O}}(2^{0.054n})\)
• scientific article; zbMATH DE number 4123671
• Bounds on Maximum Likelihood Decoding Performance for Linear Codes at Low Rates
• On the minimum bit-error rate of linear codes
• Exact decoding probability of random linear network coding for combinatorial networks
• Linear Codes, Target Function Classes, and Network Computing Capacity
• Publication:4502653
• Decoding complexity bound for linear block codes
• scientific article; zbMATH DE number 4062996

This page was built for publication: On the Optimal Achievable Rates for Linear Computation With Random Homologous Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138805)