Codes and Expansions (CodEx) Seminar

Jonathan D.H. Smith (Iowa State University):
Codes, Errors, and Loops

Classical algebraic error-correcting code theory has traditionally focused on construction of a code within a certain channel; typically by using fields directly, or through algebraic geometry over certain fields. The set of errors corrected by the code then emerges as a secondary feature, for example as the set of coset leaders.

The topic of the current talk is an alternative approach, which avoids field theory altogether and requires no more than an abelian group structure on the channel. The primary focus is placed on the set of errors to be corrected (the "error ball" of the channel). A suitable binary multiplication is constructed on the error ball, for example by a greedy algorithm. The code is then obtained through a Principle of Local Duality, which replaces the global duality of classical coding theory.

Codes constructed in this way are known as "loop transversal codes", reflecting the origin of the technique in Reinhold Baer's study of quotients of groups by subgroups which are not necessarily normal. Optimal or near-optimal linear codes, including the binary and ternary Golay codes, appear as greedy loop transversal codes. The technique has produced record-breaking codes for burst error correction, and is well suited to the construction of codes for handling atypical noise structure.

We present these codes within a general framework, which also provides a local approach to modular arithmetic through the Division Algorithm. We will exhibit the fractal structure of a "universal syndrome" for all double-error correcting binary codes, and a non-associative ball multiplication that arises from perfect domination in circulant graphs.

This is joint work with Dughwan Choi, Mehmet Dağlı, Frank Hummer and Bokhee Im.

This is a joint work with Ji Shi.