Verification of minimum-redundancy prefix codes

descriptionPublicationkeyboard_double_arrow_right Article 01 Apr 2006Publisher:Institute of Electrical and Electronics Engineers (IEEE)Journal:IEEE Transactions on Information Theory, volume 52, pages 1,399-1,404 (issn: 0018-9448,

Copyright policy )

Authors: Ahmed A. Belal; Amr Elmasry;

doi: 10.1109/tit.2006.871578

Verification of minimum-redundancy prefix codes

- Summary
- Metrics

Abstract

We show that verifying a given prefix code for optimality requires /spl Omega/(nlogn) time, indicating that the verification problem is not asymptotically easier than the construction problem. Alternatively, we give linear-time verification algorithms for several special cases that are either typical in practice or theoretically interesting.

Related Organizations

Alexandria University
Egypt

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	2
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average