Codes approaching the Shannon limit with polynomial complexity per information bit

We consider codes for channels with extreme noise that emerge in various low-power applications. Simple LDPC codes with parity checks of weight 3 are first studied for any code dimension m → ∞. These codes form modulation schemes: they improve the original channel outputs for any SNR > -6 dB (per information bit) and gain 3 dB over uncoded modulation as SNR grows. However, they also have a floor on the output bit error rate (BER) irrespective of their length. Tight lower and upper bounds, which are virtually identical to simulation results, are then obtained for BER at any SNR. We also study a combined scheme that splits
$m$
information bits into
$b$
blocks and protects each with some polar code. Decoding moves back and forth between polar and LDPC codes, every time using a polar code of a higher rate. For m → ∞and a sufficiently large parameter b, this design yields a vanishing BER at any SNR above the Shannon limit of -1.59 dB and has complexity order of m log m per information bit.