Sardinas–Patterson Decodability
Follow suffix states to distinguish prefix-free codes from uniquely decodable ones.
Free theory articleFollow suffix states to distinguish prefix-free codes from uniquely decodable ones.
Concept & interpretation
An algorithm to test whether a given set of codewords is uniquely decodable by computing sequence of suffix residuals.
Experiment
Use the interactive module to explore different codeword sets:
- Select a Code such as "Nonprefix UD" to see a code that is uniquely decodable despite not being prefix-free.
- Select "Ambiguous" to trace the generation of Sn sets until the empty word is found.
- Select "Residual cycle" to observe how the sequence of sets can loop indefinitely without containing the empty string, proving unique decodability.
For the full interactive tool, view the Sardinas-Patterson Decodability Module.