Information reconciliation for erasure channels

Abstract

Say Alice and Bob have n-bit strings which are identical except that Bob's contains t "erasures": the corresponding bit may be either zero or one. Alice will send Bob a message he can use to fill in his erased bits. The Slepian-Wolf bound suggests Alice may send as few as t bits, even when Alice does not know which t bits of are erased. We present several protocols acheiving this bound with varying degrees of success. A binary, linear, and deterministic protocol exists only for t ϵ {0, 1, n-1, n}. A nonbinary protocol exists for any t ≤ n ≤ 2m-1, but requires that erasures occur in m-bit blocks. A nonlinear protocol seems promising, but the theory to prove it in general is difficult to explore. Finally, a probabilistic protocol has no parameter constraints, but has suboptimal communication complexity based on an additional parameter c, and will fail with an error-rate Є dependent on c and t.