Search

The K-level Sigma-Delta (ΣΔ) scheme with step size δ is introduced as a technique for quantizing finite frame expansions for Rd. Error estimates for various quantized frame expansions are derived, and, in particular, it is shown that ΣΔ quantization of a unit-norm finite frame expansion in Rd achieves approximation error ∥x - ...∥ ≤ δd/2N (σ(F, p) + 1) where N is the frame size, and the frame variation σ(F, p) is a quantity which reflects the dependence of the ΣΔ scheme on the frame. Here ∥ · ∥ is the d-dimensional Euclidean 2-norm. Lower bounds and refined upper bounds are derived for certain specific cases. As a direct consequence of these error bounds one is able to bound the mean squared error (MSE) by an order of 1/N². When dealing with sufficiently redundant frame expansions, this represents a significant improvement over classical pulse-code modulation (PCM) quantization, which only has MSE of order 1/N under certain nonrigorous statistical assumptions. ΣΔ also achieves the optimal MSE order for PCM with consistent reconstruction. [ABSTRACT FROM AUTHOR]

We investigate the maximum increase in number of phrases that results from changing k consecutive symbols in a string x having length n parsed using an LZ'77-like algorithm. We consider a class of compression algorithms that partition a sequence into a collection y of nonoverlapping, variable-length phrases and encode them. Each phrase either is a singleton or matches a substring that starts to its left. We show that changing a single symbol of x in position i can yield an expansion that is of order O(n - i)2/3 as (n - i) → ∞. Our lower bound requires an alphabet size of O(n - i)1/3. We also show that changing k consecutive symbols starting from position i can yield an expansion having a similar but somewhat more involved form. The paper contains both analytically derived upper and lower bounds, and algorithms for numerically computing tighter bounds. While deriving the bounds, we provide a detailed analysis of how expansion can arise when changing consecutive symbols. This problem is motivated by management policies for computer systems, such as the IBM Memory eXpansion Technology (MXT) or the IBM iSeries compressed disks, that use LZ'77-like coding on small compression units, such as 1-4 kbyte, and store the compressed data in memory or on disk tracks. Here, when a change of a portion of the compression unit occurs, for example, an L2 cache line, or a 512-byte disk sector, the data is recompressed and potentially stored in a different location. Knowing the maximum expansion, rather than the average expansion, is an important factor for designing policies for allocation and management of memory or disk space. [ABSTRACT FROM AUTHOR]