Implementation of expander codes and their erasure decoding in Julia
- Start with an (
$n,d,\lambda$ )-Ramanujan Graph (Say$g$ ) - Find the double-cover of
$g$ (Say$g'$ ) - Find the edge-incidence graph of
$g'$ (Say$G$ ) - Choose a code
$C_0$ with block length$d$ - The set
$T = (G, C_0)$ forms our expander code with expander graph$G$ and inner code$C_0$ - Pick a codeword in
$T$ . For now pick$0$ - Pass the codeword through the erasure channel
- Decode this erasure using the
$UniqueDecode$ algorithm
[1] Guruswami, Venkatesan, Atri Rudra, and Madhu Sudan. "Essential coding theory." Draft available at http://www. cse. buffalo. edu/atri/courses/coding-theory/book 2, no. 1 (2012).
[2] Ron-Zewi, Noga, Mary Wootters, and Gilles Zémor. "Linear-time erasure list-decoding of expander codes." IEEE Transactions on Information Theory 67, no. 9 (2021): 5827-5839.