Cyclic Codes and Cellular Automata


Cyclic codes represent one of the most studied classes of error-correcting codes, due to their rich algebraic structure. In fact, several types of linear codes such as BCH and Reed-Solomon codes fall into the broad category of cyclic codes.In this talk, we show the equivalence between additive cellular automata (CA) and linear cyclic codes. In particular, we observe that preimage computation in additive CA corresponds to the systematic encoding procedure of cyclic codes through Linear Feedback Shift Registers (LFSR). On the other hand, syndrome computation in a cyclic code can be carried out in parallel by applying the corresponding CA global rule to a codeword. Further, we leverage on the theory of cryptographic boolean functions to characterize the minimum distance (and thus the error-correction capability) of cyclic codes induced by CA. As an example, we finally present how to implement the (7,4,3) Hamming code using a radius 2 CA.

Salle des Actes, Château de Valrose, University of Nice Sophia Antipolis, France