Decoding of a Cartesian product set with a constraint on an additive cost; fixed-rate entropy-coded vector quantization

The authors consider a discrete set of points A composed of K=|A| elements. A non-negative cost c(a) is associated with each element a∈A. The n-fold Cartesian product of A is dented as {A}ⁿ. The cost of an n-fold element a=(a₀, ..., a _n-1)∈{A}ⁿ is equal to: c(a)=Σ_i c(a_i). The authors select a subset of the n-fold elements, S_n∈{A}ⁿ, with a cost less than or equal to a given value c_max. They refer to A as the constituent subset. They consider another set of n-tuples X_n denoted as the input set. A non-negative distance is defined between each x=(x₀, ..., x_n-1)∈X_n, and each s=(s₀, ..., s_n-1)∈S_n. The distance between x_i and s_i is denoted as d(x_i ,s_i). The distance between x and s is equal to: d(x,s)=Σ_id(x_i, s_i). Decoding of an element x∈X_n is to find the element s∈S_n which has the minimum distance to x. A major application of this decoding problem is in fixed-rate entropy-coded vector quantization where A is the set of reconstruction vectors of a vector quantizer and cost is equivalent to self-information