On a conjecture on error recovery for variable length codes

Jiantao Zhou; Oscar C. Au; Xiaopeng Fan

doi:10.1109/ITW.2007.4313130

On a conjecture on error recovery for variable length codes

Jiantao Zhou^*
, Oscar C. Au
, Xiaopeng Fan

^*Corresponding author for this work

Hong Kong University of Science and Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Maxted et al. in 1985 gave a conjecture stating that, for a Geometric source, the stable code has the best error recovery performance for the case of bit inversion among all Huffman codes for this source, while the unstable code has the worst error recovery performance. This conjecture was extended by Swaszek et al. ten years later, but without proof, to sources with certain probability mass function. In this paper, we prove the correctness of the extended version of this conjecture. Our proof provides a novel mathematical technique for proving the optimality of variable length code in the sense of error recovery capability. Furthermore, our result offers some insight into the working mechanism of the suffix condition that has been widely used by many heuristic algorithms to find error-resilient codes.

Original language	English
Title of host publication	2007 IEEE Information Theory Workshop, ITW 2007, Proceedings
Pages	529-534
Number of pages	6
DOIs	https://doi.org/10.1109/ITW.2007.4313130
State	Published - 2007
Externally published	Yes
Event	2007 IEEE Information Theory Workshop, ITW 2007 - Lake Tahoe, CA, United States Duration: 2 Sep 2007 → 6 Sep 2007

Publication series

Name	2007 IEEE Information Theory Workshop, ITW 2007, Proceedings

Conference

Conference	2007 IEEE Information Theory Workshop, ITW 2007
Country/Territory	United States
City	Lake Tahoe, CA
Period	2/09/07 → 6/09/07

Access to Document

10.1109/ITW.2007.4313130

Cite this

@inproceedings{c1ba7bd2aa8641018d93d9a5dc524b69,

title = "On a conjecture on error recovery for variable length codes",

abstract = "Maxted et al. in 1985 gave a conjecture stating that, for a Geometric source, the stable code has the best error recovery performance for the case of bit inversion among all Huffman codes for this source, while the unstable code has the worst error recovery performance. This conjecture was extended by Swaszek et al. ten years later, but without proof, to sources with certain probability mass function. In this paper, we prove the correctness of the extended version of this conjecture. Our proof provides a novel mathematical technique for proving the optimality of variable length code in the sense of error recovery capability. Furthermore, our result offers some insight into the working mechanism of the suffix condition that has been widely used by many heuristic algorithms to find error-resilient codes.",

author = "Jiantao Zhou and Au, \{Oscar C.\} and Xiaopeng Fan",

year = "2007",

doi = "10.1109/ITW.2007.4313130",

language = "英语",

isbn = "1424415640",

series = "2007 IEEE Information Theory Workshop, ITW 2007, Proceedings",

pages = "529--534",

booktitle = "2007 IEEE Information Theory Workshop, ITW 2007, Proceedings",

note = "2007 IEEE Information Theory Workshop, ITW 2007 ; Conference date: 02-09-2007 Through 06-09-2007",

}

Zhou, J, Au, OC & Fan, X 2007, On a conjecture on error recovery for variable length codes. in 2007 IEEE Information Theory Workshop, ITW 2007, Proceedings., 4313130, 2007 IEEE Information Theory Workshop, ITW 2007, Proceedings, pp. 529-534, 2007 IEEE Information Theory Workshop, ITW 2007, Lake Tahoe, CA, United States, 2/09/07. https://doi.org/10.1109/ITW.2007.4313130

TY - GEN

T1 - On a conjecture on error recovery for variable length codes

AU - Zhou, Jiantao

AU - Au, Oscar C.

AU - Fan, Xiaopeng

PY - 2007

Y1 - 2007

N2 - Maxted et al. in 1985 gave a conjecture stating that, for a Geometric source, the stable code has the best error recovery performance for the case of bit inversion among all Huffman codes for this source, while the unstable code has the worst error recovery performance. This conjecture was extended by Swaszek et al. ten years later, but without proof, to sources with certain probability mass function. In this paper, we prove the correctness of the extended version of this conjecture. Our proof provides a novel mathematical technique for proving the optimality of variable length code in the sense of error recovery capability. Furthermore, our result offers some insight into the working mechanism of the suffix condition that has been widely used by many heuristic algorithms to find error-resilient codes.

AB - Maxted et al. in 1985 gave a conjecture stating that, for a Geometric source, the stable code has the best error recovery performance for the case of bit inversion among all Huffman codes for this source, while the unstable code has the worst error recovery performance. This conjecture was extended by Swaszek et al. ten years later, but without proof, to sources with certain probability mass function. In this paper, we prove the correctness of the extended version of this conjecture. Our proof provides a novel mathematical technique for proving the optimality of variable length code in the sense of error recovery capability. Furthermore, our result offers some insight into the working mechanism of the suffix condition that has been widely used by many heuristic algorithms to find error-resilient codes.

UR - https://www.scopus.com/pages/publications/46749129794

U2 - 10.1109/ITW.2007.4313130

DO - 10.1109/ITW.2007.4313130

M3 - 会议稿件

AN - SCOPUS:46749129794

SN - 1424415640

SN - 9781424415649

T3 - 2007 IEEE Information Theory Workshop, ITW 2007, Proceedings

SP - 529

EP - 534

BT - 2007 IEEE Information Theory Workshop, ITW 2007, Proceedings

T2 - 2007 IEEE Information Theory Workshop, ITW 2007

Y2 - 2 September 2007 through 6 September 2007

ER -

On a conjecture on error recovery for variable length codes

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this