On computing Verdu's upper bound for a class of maximum-likelihood multiuser detection and sequence detection problems

The upper bound derived by Verdu is often used to evaluate the bit error pe rformance of both the maximum-likelihood (ML) sequence detector for single- user systems and the ML multiuser detector for code-division multiple-acces s (CDMA) systems. This upper bound, which is based on the concept of indeco mposable error vectors (IEVs), can be expensive to compute because in gener al the IEVs may only be obtained using an exhaustive search. In this corres pondence, we consider the identification of IEVs for a particular class of ML detection problems commonly encountered in communications. By exploiting the properties of the IEVs for this case, we develop an IEV generation alg orithm which has a complexity substantially lower than that of the exhausti ve search. We also show that for specific communication systems, such as du obinary signaling, the expressions of Verdu's upper bound can be considerab ly simplified.