Index assignment for two-channel quantization

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 N²/3+O(N) and N²/2+O(N). We give new lower and upper bounds, both of the form 3N²/8+O(N). We also consider minimizing the maximal variance in any row or column and show that it must be at least N⁴/60+O(N³), and that it does not have to be more than 3N⁴/160+O(N³).