Title :
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
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).
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;
Conference_Titel :
Data Compression Conference (DCC), 2010
Conference_Location :
Snowbird, UT
Print_ISBN :
978-1-4244-6425-8
Electronic_ISBN :
1068-0314
DOI :
10.1109/DCC.2010.35
