Sardinas–Patterson Decodability

An algorithm to test whether a given set of codewords is uniquely decodable by computing sequence of suffix residuals.

Concept Overview

A code (a set of words) is uniquely decodable if every concatenation of its words can be decoded in only one way. Prefix-free codes are uniquely decodable, but they are not the only ones. The Sardinas-Patterson algorithm is a finite-state method to determine whether a given variable-length code has the unique decodability property. It does so by looking for a sequence of overlapping codewords that could result in an ambiguous decoding.

Algorithm Definition

Let C be a set of codewords. The algorithm constructs a sequence of sets of words S₀, S₁, S₂, ...

S₀ = C
S_n+1 = (C^-1 · S_n) ∪ (S_n^-1 · C)

Where A^-1 · B is the left quotient of B by A. It contains the suffix x such that a ∈ A and ax ∈ B.

The code is not uniquely decodable if the empty word (ε) appears in any S_n for n ≥ 1. The code is uniquely decodable if a set S_n is empty, or if the sequence of sets becomes periodic (a set repeats) without ever containing the empty word.

Worked Example

Consider the ambiguous code C = {"0", "01", "10"}. We trace the Sardinas-Patterson algorithm:

S₀ = C = {"0", "01", "10"}
S₁: We look for a codeword that is a prefix of another. "0" is a prefix of "01". The suffix is "1". So S₁ = {"1"}.
S₂: We check S₁ against C, and C against S₁. "1" (from S₁) is a prefix of "10" (from C). The suffix is "0". So S₂ = {"0"}.
S₃: "0" (from S₂) is equal to "0" (from C), so the suffix is the empty word ε. So S₃ = {ε, "1"}.

Since the empty word appears in S₃, the code is not uniquely decodable. We can construct the ambiguity witness: 010 = 0 | 10 = 01 | 0.

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 S_n 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.

Limitations

The Sardinas-Patterson algorithm applies to finite codes or regular languages. The time complexity can be high in the worst case (exponential in relation to codeword lengths), and the number of states generated can be large. However, since the length of any suffix generated is strictly less than the longest codeword in C, the set of possible suffixes is finite, guaranteeing termination.

The algorithm and prefix code foundations are based on the original 1953 Sardinas-Patterson paper and standard academic notes on information theory.

References

https://courses.grainger.illinois.edu/ece563/fa2024/hw3sol-F24.pdf
Sardinas, A. A., & Patterson, G. W. (1953). A necessary and sufficient condition for the unique decodability of coded messages.

Sardinas–Patterson Decodability