The Capacity of the Kanerva Associative Memory is Exponential
Philip A. Chou · Neural Information Processing Systems · 1987
The capacity of an associative memory is defined as the maximum number of vords that can be stored and retrieved reliably by an address within a given sphere of attraction. It is shown by sphere packing arguments that as the address length increases, the capacity of any associative memory is limited to an exponential growth rate of 1 - h2(δ), where h2(δ) is the binary entropy function in bits, and δ is the radius of the sphere of attraction. This exponential growth in capacity can actually be achieved by the Kanerva associative memory, if its parameters are optimally set. Formulas for these optimal values are provided. The exponential growth in capacity for the Kanerva associative memory contrasts sharply with the sub-linear growth in capacity for the Hopfield associative memory.