Index assignment for two-channel quantization

József Balogh, János A. Csirik

Research output: Contribution to journalArticlepeer-review


This paper concerns the design of a multiple description scalar quantization (MDSQ) system for two identical channels for an unbounded discrete information source. This translates to the combinatorial problem of finding an arrangement of the integers into the infinite plane square grid so that each row and each column contains exactly N numbers, such that the difference between any two numbers in the same row (or column) is at most d, with d to be minimized for a given N. The best previous lower and upper bounds on the lowest d were N2 /3 + O(N) and N2/2 + O(N). We give new lower and upper bounds, both of the form 3N2/8 + O(N). We also consider minimizing the maximal variance in any row or column and show that it must be at least N4/60 + O(N3), and that it does not have to be more than 3N4/160 + O(N3).

Original languageEnglish (US)
Pages (from-to)2737-2751
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number11
StatePublished - Nov 2004
Externally publishedYes

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this