Stochastic Iterative Algorithms for Signal Set Design for Gaussian Channels and the L2 Signal Set

Author: Yi Sun, University of Minnesota
Advisor: Prof. John Kieffer
Co-advisor: Prof. Laurie Nelson
Date: Jan. 1997


This thesis consists of two parts. In the first part, the stochastic iteration approach is proposed for signal set design. A fundamental stochastic iterative algorithm without energy constraint is proposed, which models a stochastic dynamic system using the detection probability of a signal set as energy function. Based on this fundamental algorithm, four practical stochastic iterative algorithms are proposed with respect to two energy constraints (the average energy constraint and the equal energy constraint) and two operation modes (sequential mode and batch mode). To study the performance of these proposed algorithms, many simulation experiments are carried out. Among these simulation experiments are the studies of almost all existing theoretical results, which include the optimality of the L1 signal set (consisting of a pair of antipodal signals and some zero signals), the optimality of the L2 signal set (consisting of three signals located at the vertices of an equilateral triangle and some zero signals), the truth of the weak simplex conjecture and two of Dunbridge’s theorems. The L2 signal set is newly discovered by the simulation and its optimality is shown in this thesis. Given the same conditions as those in the above theoretical results, the proposed algorithms always converge to the signal set proved optimal in theory. The influence of SNR and a priori probabilities on signal set is investigated via simulation. As an example of application of the proposed algorithms to practical communication system design, in the scenario of satellite communications in which SNR is very low, the signal sets of eight 2-D signals are studied by simulation. Two signal sets better than the practically used 8-PSK set are found in the SNR range of practical satellite communications. All simulation results show promise of the proposed algorithms.

In the second part of this thesis, optimal properties of the L2 signal set are analyzed in the SSC condition (equal a priori probability and average energy constraint) at low signal-to-noise ratios. We first discuss the properties of the mean width of the polytope generated by a signal set. Then two classes of signal sets are analyzed. The first to be analyzed is the class of 2-D signal sets E(M,K) (consisting of K signals equally spaced on a circle and M-K zero signals). The L2 signal set is proved to be unique optimal in the class of signal sets E(M,K) and further proved to be unique optimal in 2-D space. The class of signal sets S(M,K) (consisting of a regular simplex set of K signals and M-K zero signals) then is analyzed. It is shown that the strong simplex conjecture for M>=4 is disproved by any of the signal sets S(M,K) for 3 <= K <= M-1 <=K<=M-1 and is also disproved by S(M,2) (i.e., the L1 signal set) if M>=7. It is proved that the L2 signal set is the unique optimal signal set in this class of signal sets S(M,K) for all M>=4. This disproves the strong simplex conjecture for all M>=4 and also leads to the extension of the following results obtained by Steiner for all M>=7 to all M>=4: (1) there is no signal set which is optimal at all signal-to-noise ratios; (2) with average energy constraint, the optimal solution as SNR approaches zero is not an equal energy solution. Several other results are also obtained. Finally, we show that for M>=7, there exists an integer K'<=M-1 such that any of the signal sets E(M,K) for 4<=K<=K' disproves the strong simplex conjecture.
In this thesis, we found that many signal sets can disprove the strong simplex conjecture for M>=4, although the strong simplex conjecture is long-standing and was not disproved for many years.

Yi Sun
Department of Electrical Engineering
University of Minnesota
200 Union Street, SE
Minneapolis, MN 55455
Phone: (612)626-1769 (W) (612)645-3743 (H)
Fax: (612)625-4583