Eimear Byrne: Belief propagation and non-linear codes.Belief updating by network propagation (a BP algorithm) has numerous applications. In more recent years, one of these has been toward the decoding of error-correcting codes that are efficiently represented by a graph. Linear codes defined by sparse parity check matrices form a particularly suitable family of codes for this scheme, and were introduced by Gallager in 1962. The remarkable performance of Gallager's codes went largely unnoticed until MacKay and Neal rediscovered his work in generalising MN codes, and increased computing power allowed for the appropriate simulations. Today they are recognised as among the most efficient codes, with performance close to the Shannon limit. One drawback of these low density parity check codes is that they are linear, whereas in general non-linear codes have superior parameters. We hence introduce a class of non-linear codes, suitable for decoding via belief propagation. We also describe how such codes admit an efficent encoding procedure, using simple techniques from algebraic geometry. |