Abstract:

We show that linear complexity, capacity approaching information embedding codes exist for information embedding problems. Specifically, we introduce the double erasure information embedding channel model, and show that in at least some parameter regimes one can achieve rates arbitrarily close to capacity using suitably defined codes on graphs. Furthermore, we show that both encoding and decoding can be implemented with linear complexity by exploiting belief propagation techniques.