How to Compute Modulo Prime-Power Sums ?

Mohsen Heidari, Farhad Shirani, Sandeep Pradhan

A new class of structured codes called Quasi Group Codes (QGC) is introduced. A QGC is a subset of a group code. In contrast with group codes, QGCs are not closed under group addition. The parameters of the QGC can be chosen such that the size of $\mathcal{C}+\mathcal{C}$ is equal to any number between $|\mathcal{C}|$ and $|\mathcal{C}|^2$ . We analyze the performance of a specific class of QGCs. This class of QGCs is constructed by assigning single-letter distributions to the indices of the codewords in a group code. Then, the QGC is defined as the set of codewords whose index is in the typical set corresponding to these single-letter distributions. The asymptotic performance limits of this class of QGCs is characterized using single-letter information quantities. Corresponding covering and packing bounds are derived. It is shown that the point-to-point channel capacity and optimal rate-distortion function are achievable using QGCs. Coding strategies based on QGCs are introduced for three fundamental multi-terminal problems: the K\"orner-Marton problem for modulo prime-power sums, computation over the multiple access channel (MAC), and MAC with distributed states. For each problem a single-letter achievable rate-region is derived. It is shown, through examples, that the coding strategies improve upon the previous strategies based on unstructured codes, linear codes and group codes.

Knowledge Graph



Sign up or login to leave a comment