Fix-free code construction solved for three codeword lengths across alphabets
The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths
Information Theory
Summary
The paper solves a long-standing puzzle about building special sets of codewords called fix-free codes when the codewords have up to three different lengths. It proves that as long as the total size of these codewords follows a certain rule (called the Kraft sum is at most 3/4), you can always build such codes for any alphabet size. The authors provide a step-by-step way to create these codes using a new math approach involving matrices and counting methods. This extends earlier results from just binary codes to alphabets with many symbols.
What this means in practice
- •For data compression engineers: Design new error-resistant coding schemes with guaranteed fix-free properties for alphabets beyond binary with up to three codeword lengths.
- •For telecommunications protocol designers: Implement coding layers that avoid ambiguity using the paper’s deterministic method for constructing fix-free codes with restricted codeword lengths.
A theory result. No direct application yet.
Authors
Weiguo Gao, Zhi Shan
Abstract
We prove the \(3/4\) conjecture for \(q\)-ary fix-free codes with at most three distinct codeword lengths, for every integer \(q\geq2\). Every prescribed length distribution with Kraft sum at most \(3/4\) is realized by a deterministic construction. We introduce a matrix approach based on an exact identity for the overlap between forbidden prefix extensions and suffix residuals. Natural numerical order fixes the shortest layer, and the remaining selection problem is expressed through row and column counts. A fixed-cardinality interpolation theorem supplies feasible sets of every intermediate cardinality between nested endpoints, provided their differences satisfy one-sided uniqueness and either acyclicity or integral slack. Reverse-order selection handles the uniform cases directly; in the remaining cases, layer completion and aligned groups provide endpoints for interpolation. Together, these methods extend the binary three-length result to arbitrary finite alphabets and give a deterministic procedure for constructing the code.