Random clique codes

International audienceA new family of associative memories based on sparse neural networks has been recently introduced. These memories achieve excellent performance thanks to the use of error-correcting coding principles. Based on these devices, we introduce a new family of codes termed clique codes. These codes are based on the cliques in balanced c-partite graphs describing associative memories. In particular, we study an ensemble of random clique codes, and prove that such ensemble contains asymptotically good codes. Furthermore, these codes can be efficiently decoded using the neural network-based associative memories with limited complexity and memory consumption. They offer a new interesting alternative to existing codes, in particular when the underlying channel is assumed to be a memoryless erasure channel