When Huffman meets Hamming: A class of optimal variable-length error correcting codes

Serap A. Savari, Jörg Kliewer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We introduce a family of binary prefix condition codes in which each codeword is required to have a Hamming weight which is a multiple of w for some integer w ≥ 2. Such codes have intrinsic error resilience and are a special case of codes with codewords constrained to belong to a language accepted by a deterministic finite automaton. For a given source over n symbols and parameter w we offer an algorithm to construct a minimum-redundancy code among this class of prefix condition codes which has a running time of O(nw+2).

Original languageEnglish (US)
Title of host publicationProceedings - Data Compression Conference, DCC 2010
Pages327-336
Number of pages10
DOIs
StatePublished - 2010
Externally publishedYes
EventData Compression Conference, DCC 2010 - Snowbird, UT, United States
Duration: Mar 24 2010Mar 26 2010

Publication series

NameData Compression Conference Proceedings
ISSN (Print)1068-0314

Other

OtherData Compression Conference, DCC 2010
Country/TerritoryUnited States
CitySnowbird, UT
Period3/24/103/26/10

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'When Huffman meets Hamming: A class of optimal variable-length error correcting codes'. Together they form a unique fingerprint.

Cite this