101. A Library for Formalization of Linear Error-Correcting Codes
- Author
-
Reynald Affeldt, Takafumi Saikawa, and Jacques Garrigue
- Subjects
Class (computer programming) ,Correctness ,Theoretical computer science ,Computer science ,020207 software engineering ,0102 computer and information sciences ,02 engineering and technology ,Coding theory ,01 natural sciences ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Artificial Intelligence ,0202 electrical engineering, electronic engineering, information engineering ,Redundancy (engineering) ,Error correcting ,Special care ,Hamming code ,Software - Abstract
Error-correcting codes add redundancy to transmitted data to ensure reliable communication over noisy channels. Since they form the foundations of digital communication, their correctness is a matter of concern. To enable trustful verification of linear error-correcting codes, we have been carrying out a systematic formalization in the Coq proof-assistant. This formalization includes the material that one can expect of a university class on the topic: the formalization of well-known codes (Hamming, Reed–Solomon, Bose–Chaudhuri–Hocquenghem) and also a glimpse at modern coding theory. We demonstrate the usefulness of our formalization by extracting a verified decoder for low-density parity-check codes based on the sum-product algorithm. To achieve this formalization, we needed to develop a number of libraries on top of Coq’s Mathematical Components. Special care was taken to make them as reusable as possible so as to help implementers and researchers dealing with error-correcting codes in the future.
- Published
- 2020