Asymptotically optimal low-complexity sequential lossless coding for piecewise-stationary memoryless sources--Part I: The regular case

The lower bound on the redundancy for lossless universal coding of regular memoryless sources with a bounded number of abrupt changes in the statistics is shown to be asymptotically achievalbe using a fixed per-letter computational complexity sequential compression scheme with fixed storage complexi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2000-11, Vol.46 (7), p.2444-2467
Main Authors: Shamir, Gil I, Costello, Daniel J
Format: Article
Language:English
Subjects:
Codes
Computer memory
Computer programming
Redundancy
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The lower bound on the redundancy for lossless universal coding of regular memoryless sources with a bounded number of abrupt changes in the statistics is shown to be asymptotically achievalbe using a fixed per-letter computational complexity sequential compression scheme with fixed storage complexity.
ISSN:0018-9448
1557-9654
DOI:10.1109/18.887857