Counting solutions for the CDMA multiuser MAP demodulator

We evaluate the average number of locally minimal solutions for maximum-a-{\it posteriori} (MAP) demodulation in code-division multiple-access (CDMA) systems [1]. For this purpose, we use a sophisticated method to investigate the ground state properties for the Sherrington-Kirkpatrick-type (i.e. fully connected) spin glasses established by Tanaka and Edwards [2] in 1980. We derive the number of locally minimal solutions as a function of several parameters which specify the CDMA multiuser MAP demodulator. We also calculate the distribution function of the energies for the locally minimum states. We find that for a small number of chip intervals (or equivalently a large number of users) and large noise level at the base station, the number of local minimum solutions becomes larger than that of the SK model [3]. This provides us with useful information about the computational complexity of the MAP demodulator [4]. \\ \\ $[1]$ T. Tanaka, Europhys. Lett. {\bf 54} (4), 540 (2001). \\ $[2]$ F. Tanaka and S.F. Edwards, J. Phys. F: Metal Phys. {\bf 10} 2769 (1980). \\ $[3]$ D. Sherrington and S. Kirkpatrick, Phys. Rev. Lett. {\bf 35}, 1792 (1975). \\ $[4]$ J.P.L. Hatchett and J. Inoue, in preparation.