A set X ⊆ Σ** of pictures is a code if every picture over Σ is tilable in at most one way with pictures in X. The definition of strong prefix code is introduced. The family of finite strong prefix codes is decidable and it has a polynomial time decoding algorithm. Maximality for finite strong prefix codes is also studied and related to the notion of completeness. We prove that any finite strong prefix code can be embedded in a unique maximal strong prefix code that has minimal size and cardinality. A complete characterization of the structure of maximal finite strong prefix codes completes the paper.
Structure and properties of strong prefix codes of pictures
ANSELMO, Marcella;
2017
Abstract
A set X ⊆ Σ** of pictures is a code if every picture over Σ is tilable in at most one way with pictures in X. The definition of strong prefix code is introduced. The family of finite strong prefix codes is decidable and it has a polynomial time decoding algorithm. Maximality for finite strong prefix codes is also studied and related to the notion of completeness. We prove that any finite strong prefix code can be embedded in a unique maximal strong prefix code that has minimal size and cardinality. A complete characterization of the structure of maximal finite strong prefix codes completes the paper.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
MSCS2017.pdf
accesso aperto
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Creative commons
Dimensione
418.86 kB
Formato
Adobe PDF
|
418.86 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.