List detection for multi-access channels

We propose a low complexity iterative multiuser decoder. We perform the multiuser a-posteriori probability calculation based on the marginalization of probabilities over a subset of the P highest probable sequences. Given a K user symmetric channel this list may be approximated closely with per-bit computational complexity O(K + P + 2K log K). We further show that for any multiuser system possessing a polynomial complexity optimal detection algorithm it is possible to obtain the P highest probable sequences with polynomial complexity. We further show that for any multiuser channel it is possible to obtain P highly probable sequences in polynomial time and hence utilize the list detection procedure for iterative decoding.