null
(Ed.)
Abstract—We study a problem of constructing codes that
transform a channel with high bit error rate (BER) into one with
low BER (at the expense of rate). Our focus is on obtaining codes
with smooth (“graceful”) input-output BER curves (as opposed
to threshold-like curves typical for long error-correcting codes).
This paper restricts attention to binary erasure channels (BEC)
and contains two contributions. First, we introduce the notion
of Low Density Majority Codes (LDMCs). These codes are
non-linear sparse-graph codes, which output majority function
evaluated on randomly chosen small subsets of the data bits. This
is similar to Low Density Generator Matrix codes (LDGMs),
except that the XOR function is replaced with the majority.
We show that even with a few iterations of belief propagation
(BP) the attained input-output curves provably improve upon
performance of any linear systematic code. The effect of nonlinearity bootstraping the initial iterations of BP, suggests that
LDMCs should improve performance in various applications
where LDGMs have been used traditionally.
Second, we establish several two-point converse bounds that
lower bound the BER achievable at one erasure probability as
a function of BER achieved at another one. The novel nature of
our bounds is that they are specific to subclasses of codes (linear
systematic and non-linear systematic) and outperform similar
bounds implied by the area theorem for the EXIT function
more »
« less