Lab for Programming and its Application in Mathematics

Lab manager: Prof. Dr. Michael Bodewig

Fix-free codes facilitate fast and robust transmission of digital messages. Here, the codewords are no prefixes of each other as in prefix-free codes and in addition, the codewords are also no suffixes of each other. Hence, coded messages can be decoded from both directions. This both saves time and prevents that errors at the beginning or ending of the message lead to a complete loss of information content.

To address the question which lengths are realized by codes, code words of length l over an alphabet with q letters are weighted with Kraft sum q^(-l). While Kraft’s inequality guarantees the existence of prefix-free codes with Kraft sum of at most 1, this question could not yet be finally answered for fix-free codes. The conjecture is that Kraft sums of at most ¾ are sufficient.