6533b837fe1ef96bd12a26f8

RESEARCH PRODUCT

Varieties of Codes and Kraft Inequality

Antonio RestivoFabio Burderi

subject

Discrete mathematicsClass (set theory)Unique factorization domainCode wordAstrophysics::Cosmology and Extragalactic AstrophysicsKraft's inequalityCombinatoricsFormal languageHigh Energy Physics::ExperimentSpecial caseVariety (universal algebra)Connection (algebraic framework)Mathematics::Representation TheoryMathematics

description

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 $\mathcal{V}$ of codes, if all the elements of $\mathcal{V}$ satisfy the Kraft inequality, then $\mathcal{V}$ is the variety of UD codes. Thus, in terms of varieties, Kraft inequality characterizes UD codes.

yearjournalcountryeditionlanguage
2005-01-01
https://doi.org/10.1007/978-3-540-31856-9_45