The capacity of the Kanerva associative memory

Abstract

Asymptotic expressions for the capacity of an associative memory proposed by P. Kanerva (1984) are derived. Capacity is defined as the maximum number of random binary words that can be stored at random addresses so that the probability that a word is in error is arbitrarily small when it is retrieved by an n-bit address containing fewer than delta n errors, delta <or=1/2. Sphere-packing arguments show that the capacity of any associative memory can grow exponentially in n at a rate of at most 1-h/sub 2/( delta ), where h/sub 2/( delta ) is the binary entropy function in bits. It turns out that the Kanerva associative memory achieves this upper bound when its parameters are optimally set. Thus, the capacity of the Kanerva associative memory has an exponential growth rate equal to the rate of the best information-theoretic codes, that is 1-h/sub 2/( delta ). However, the Kanerva memory achieves its exponential growth in capacity at the expense of an exponential growth in hardware.<<ETX>>