When Huffman Meets Hamming: A Class of Optimal Variable-Length Error Correcting Codes

Author

Savari, Serap A. ; Kliewer, Jörg

Author_Institution

Texas A&M Univ., College Station, TX, USA

fYear

2010

fDate

24-26 March 2010

Firstpage

327

Lastpage

336

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(n^w+2).

Keywords

Hamming codes; Huffman codes; binary codes; computational complexity; error correction codes; variable length codes; Hamming weight; binary prefix condition codes; deterministic finite automaton; intrinsic error resilience; minimum-redundancy code; optimal variable-length error correcting codes; prefix condition codes; Automata; Binary trees; Channel coding; Data compression; Dynamic programming; Error correction codes; Hamming distance; Hamming weight; Resilience; Sufficient conditions;

fLanguage

English

Publisher

ieee

Conference_Titel

Data Compression Conference (DCC), 2010

Conference_Location

Snowbird, UT

ISSN

1068-0314

Print_ISBN

978-1-4244-6425-8

Electronic_ISBN

1068-0314

Type

conf

DOI

10.1109/DCC.2010.35

Filename

5453476