Typical sumsets of linear codes
Jingge Zhu, Michael Gastpar · 2016
Given two identical linear codes C with rate R over Fqof length n, we independently pick one codeword from each codebook uniformly at random. A sumset is formed by adding these two codewords entry-wise as integer vectors and a sumset is called typical, if the sum falls inside this set with high probability. In this paper we show that the asymptotic size of such typical sumsets for most codes is min{22nR, 2n(R+D)} where D depends solely on the alphabet size q. More generally, we completely characterize the asymptotic size of typical sumsets of two nested linear codes C1, C2with different rates. We also provide two applications of the results, one on a computation problem over the general two-user multiple-access channel, and one on a communication problem over an additive two-user multiple-access channel.