A Uniquely Decodable (UD) Code is a code such that any vector of the ambiant space has a unique closest codeword. This definition seems to have appeared for the first time in the book of Van Lint (Introduction to Coding theory), but although UD codes are appealing combinatorial objects, no systematic search for them has been attempted since. Perfect codes are obvious instances of UD codes~: so are direct sums of perfect codes. Are there any other UD codes? In the nonlinear case, the answer is yes. In the linear case, the question is still open. We have focused on the linear case, and begun a study of their structure. In particular we can show that a linear UD code must have `nested' perfect subcodes. By using these perfect subcodes, identifying related designs, and applying Llyod theorems together with some nonexistence results for codes we can solve the existence problem of linear UD codes in some cases. In particular, all UD codes of covering radius 2 can be found.

This is joint work with G. Cohen, J. Rifa and J. Tena.

Back to Workshop Schedule