Sigma-delta quantization errors and the traveling salesman problem

Abstract

In transmission, storaging and coding of digital signals we frequently perform A/D conversion using quantization. In this paper we study the maximal and mean square errors as a result of quantization. We focus on the sigma-delta modulation quantization scheme in the finite frame expansion setting. We show that this problem is related to the classical Traveling Salesman Problem (TSP) in the Euclidean space. It is known [Benedetto et al., Sigma-delta ( ΣΔ ) quantization and finite frames, IEEE Trans. Inform. Theory 52, 1990-2005 (2006)] that the error bounds from the sigma-delta scheme depends on the ordering of the frame elements. By examining a priori bounds for the Euclidean TSP we show that error bounds in the sigma-delta scheme is superior to those from the pulse code modulation (PCM) scheme in general. We also give a recursive algorithm for finding an ordering of the frame elements that will lead to good maximal error and mean square error. © 2007 Springer Science+Business Media B.V.