Three fast search routines to be used in the encoding phase of vector quantization (VQ) image compression systems are presented. These routines, which are based on geometric considerations, provide the same results as an exhaustive (or full) search. Examples show that the proposed algorithms need only 3-20% of the number of mathematical operations required by a full search and fewer than 50% of the operations required by recently proposed alternatives.

Monte Carlo methods have been used to study the recall accuracy of three discrete distributed associative memory models: a discrete correlation matrix model (DCM), the Bayes discriminant rule model developed by Murakami and Aibara (MA), and a discrete version of the generalized inverse model of Kohonen (DGI). The key (input) and data (output) vectors have nc components restricted to the values − 1 and + 1. The elements of the nc × nc recall matrix may take on any floating point value. Auto-associative (key and data vectors identical) and hetero- associative operation have been examined with both noiseless (perfect) and noisy key vectors. Simulations have been performed over a range of nc from 20 to 100 and of nv, the number of vector pairs stored, from 1 to 50. The recall accuracy, defined as the probability that a component of the output vector is correct, depends strongly on the ratio nv/nc. The DGI model is the only one able to provide perfect hetero-associative recall with perfect input for nv ≤ nc, but is extremely sensitive to input noise. If the probability that a component of the input vector is correct is 0.9 the three models will provide perfect output only if nv is less than about 0.15 nc. For more noisy inputs the MA model provides the highest probability that a component of the output will be correct.

Monte Carlo simulations of the continuous Moore-Penrose generalized inverse associative memory (Kohonen [l]) have shown that the noise-to-signal ratio is improved on recall in the autoassociative case as long as the number of vector pairs stored is less than the number of components per vector. In the heteroassociative case, however, the noise-to-signal ratio may actually be greatly increased upon recall, particularly as the number of vector pairs stored approaches the number of components per vector. The increase in output noise-to-signal ratio in the heteroassociative case is found to be due to the fact that the inverse of the product of the key vector matrix with its transpose may increase without bound in spite of the fact that the key vectors are linearly independent.