In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binary-input memoryless symmetric (BMS) channel and any epsilon > 2 epsilon*, where epsilon^* = \frac{ 1}{ 6}-\frac{ 5}{ 3}\log{ \frac{ 4}{ 3}} \approx 0.085, we show an explicit sequence of capacity-achieving codes with all the column wights of the generator matrix upper bounded by (\log N)^{ 1+epsilon}, where N is the code block length. The constructions are based on polar codes. Applications to crowdsourcing are also shown.
Categories: eess.SP cs.DC cs.IT math.IT