Varieties of codes and Kraft inequality

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

Decipherability conditions for codes are investigated by using the approach of Guzman, who introduced in [7] the notion of variety of codes and established a connection between classes of codes and varieties of monoids. The class of Uniquely Decipherable (UD) codes is a special case of variety of codes, corresponding to the variety of all monoids. It is well known that the Kraft inequality is a necessary condition for UD codes, but it is not sufficient, in the sense that there exist codes that are not UD and that satisfy the Kraft inequality. The main result of the present paper states that, given a variety V of codes, if all the elements of V satisfy the Kraft inequality, then V is the variety of UD codes. Thus, in terms of varieties, Kraft inequality characterizes UD codes.
Original languageEnglish
Pages (from-to)507-520
JournalTheory of Computing Systems
Volume40
Publication statusPublished - 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Varieties of codes and Kraft inequality'. Together they form a unique fingerprint.

  • Cite this