Dithered Signed-Error CMA: The Complex-Valued Case

Phil Schniter* and C. Richard Johnson, Jr.
School of Electrical Engineering, Cornell University

The 32nd Asilomar Conference on Signals, Systems, and Computers, November 2–5, 1998.

Adaptive blind equalization has gained widespread use in communication systems that operate without training signals. In particular, the Constant Modulus Algorithm (CMA) has become a favorite of practitioners due to its LMS-like complexity and desirable robustness properties. The desire for further reduction in computational complexity has motivated signed-error versions of CMA, which have been found to lack the robustness properties of CMA. Previously we have presented a simple modification of real-valued signed-error CMA, based on the judicious use of dither, that results in an algorithm with robustness properties nearly identical to those of real-valued (unsigned) CMA. This paper extends those results to the complex-valued case.

The Constant Modulus Algorithm (CMA) [1, 2, 3, 4] has gained widespread practical use as a blind adaptive equalization algorithm for digital communications systems operating over inter-symbol interference channels. Modern receiver implementations often realize the advantages offered by a fractionally-spaced equalizer (FSE), i.e., an equalizer operating at a rate higher than the baud rate and/or processing data from multiple sensors. Under a set of perfect blind equalizability (PBE) conditions (listed in "The Constant Modulus Algorithm"), CMA adaptation of a FSE is known to converge in mean to an equalizer setting capable of perfect symbol recovery (see, e.g., [4]).

Though assumptions of ideality are convenient for the theoretical analysis of blind equalization schemes, they are unconditionally violated in physical implementations of communication systems. This fact motivates the consideration of algorithm performance under realistic (non-ideal) conditions. We will use the term robust when referring to a blind algorithm’s ability to perform “well” under violations of the PBE conditions. It has been reasoned that the widespread practical use of fractionally-spaced CMA bears testament to its superior robustness properties. A sizeable body of theoretical analysis exists to support this claim [3].

Low-cost consumer applications (e.g., HDTV) motivate blind equalization techniques requiring minimum implementation cost. Though noted for its LMS-like complexity, CMA may be further simplified by transforming the bulk of its update multiplications into sign operations [2, 5]. A recent study suggests, however, that previously proposed versions of signed-error CMA (SE-CMA) do not inherit the desirable robustness properties of CMA. In particular, it was found that SE-CMA convergence may suffer when the channel is undermodelled [6].

The search for a computationally efficient algorithm with CMA-like robustness led us to propose Dithered Signed-Error CMA (DSE-CMA) [7]. As first introduced, DSE-CMA was a simple modification of real-valued SE-CMA based on the incorporation of controlled noise (sometimes referred to as “dither”). Real-valued DSE-CMA has been shown to possess robustness properties closely resembling real-valued (unsigned) CMA. In fact, the mean behavior of real-valued DSE-CMA has been shown to be identical to real-valued CMA under proper choice of design parameters [7]. The drawback to dithering is a degradation in steady-state mean-square error (MSE) performance. Hence, an expression for the excess MSE (EMSE) of DSE-CMA was derived in [7], yielding straightforward design guidelines. In this paper, we extend DSE-CMA to the complex-valued case, presenting analogous results on its transient and steady-state behaviors.

A word on notation: we use lower-case bold-face quantities (e.g., h) to denote vectors and upper-case bold-face quantities (e.g., H) to denote matrices. Conjugation is denoted by (·)*, transposition by

, and conjugate transposition by

The Fractionally-Spaced System Model

In this section, we construct a received signal model based on a single-sensor receiver operating at twice the baud rate (1). Note that an equivalent model results from the use of two sensors, and that generalization to multiple sensors/oversampling is straightforward [4]. Consider a baseband communication system operating at baud interval T. AT-spaced symbol sequence

is transmitted through a linear time-invariant and finite impulse response channel characterized by h, a

vector of T/2-spaced impulse response coefficients

. In addition to inter-symbol interference, the T/2-spaced received signal

is also corrupted by an additive noise process

. The baseband receiver consists of a T/2-spaced linear equalizer specified by the

coefficients in the vector f. At baud time index n, the receiver forms the symbol estimate

from the previous

received samples, as collected in the vector r(n). Figure 1 shows the linear system relating transmitted symbols

to the system outputs

. We assume that the source symbols

are drawn from a finite alphabet S and are zero-mean i.i.d. with variance

Defining the

fractionally-spaced convolution matrix

allows us to write the received vector as r(n) = Hs(n) + v(n), where v(n) is a vector containing the previous

samples of the channel noise process. The baud-rate linear system relating

is now compactly described by the T-spaced impulse response vector

, so that

with

with source vector

. The structure of H implies that

Figure 1. T/2-spaced baseband communication system model.

Perfect symbol recovery (PSR) occurs when the channel noise is absent, and when f and H are such that

for all n, some fixed system delay

, and some fixed angle

. The PSR system responses are characterized by

(where

denotes a vector with 1 in the

position and zeros elsewhere). We refer to PSR-inducing equalizers are “zero-forcing” and denote a zero-forcing equalizer associated with system delay

. The goal of blind equalization can be considered the achievement (or near-achievement) of PSR based only on knowledge of the system output

and the (marginal) statistics of the source process

The Constant Modulus Algorithm

The Constant Modulus Algorithm (CMA) is a stochastic gradient algorithm minimizing the Godard criterion:

. The positive constant

is referred to as the dispersion constant and is chosen in accordance with the source statistics. Conceived independently in [1] and [2], the Godard criterion penalizes the dispersion of the squared output modulus

away from

. As a FSE update algorithm, CMA takes the form

where µ is a (small) positive step-size. The function

(·) identified in (1) is referred to as the CMA error function and will appear many times throughout this paper.

The following perfect blind equalizability (PBE) conditions are known to be sufficient to guarantee that equalizers minimizing

achieve perfect symbol recovery [3].

(A1) Full column-rank H.

(A2) No additive channel noise.

(A3) Sub-Gaussian source: the normalized kurtosis

must be less than that of a Gaussian process.

(A4) I.i.d. zero-mean source. When complex-valued, the source must be circularly symmetric, i.e.,

Note that (A1)-(A2) pertain to the channel-equalizer pair's ability to achieve PSR, while (A3)-(A4) pertain specifically to blind adaptive equalization using the Godard criterion.

In an effort to eliminate the

regressor multiplies required by (1), we proposed a simple modification to real-valued SE-CMA, known as dithered signed-error CMA (DSE-CMA) [7], that resulted in an algorithm whose mean behavior closely matched that of real-valued (unsigned) CMA. The modification was motivated by a well-known technique known as dithering, whereby a carefully chosen random noise is added to a signal before quantization in an attempt to preserve information that would otherwise be lost in the quantization process. The focus of this paper is on the properties of complex-valued DSE-CMA, defined in (2) below:

Above, csgn(x) : = sgn(Rex) + j sgn(Im x), and

is a positive constant. In addition, (2) includes the complex-valued dither process

, where

and

are real-valued independent random processes uniformly distributed on (-1,1). The positive dither amplitude

appears twice in (2). Equation (2) also identifies the DSE-CMA error function

, which is readily decoupled into real and imaginary components:

, for

and

Quantization Noise Model

At first glance, the complex sign operator in (2) appears to complicate the behavioral analysis of DSE-CMA. Fortunately, the theory of dithered quantizers allows us to subsume the sign operator by adopting a quantization-noise model of the DSE-CMA error function (see Figure 2).

Since the complex sign operation can be decoupled into two real-valued operations, we consider, for the moment, the real-valued sgn (·) operator. DSE-CMA can be connected to the quantization literature with the observation that the operator

sgn (·) is identical to the two-level uniform quantizer Q(·), specified by

for quantizer spacing

Figure 2: Dithered Quantizer and Quantization noise model.

The quantization noises

and

arising from the nonsubtractively dithered quantization of information signals

and

are defined

For

uniformly distributed on (–1, 1] and

selected large enough to satisfy

for

of interest, [8] implies that

and

are mutually uncorrelated random processes whose first moments obey

and whose conditional second moments obey

Using (3) and (4), we can write the complex-valued DSE-CMA error function in terms of the complex-valued quantization noise

as follows

This leads to the compact DSE-CMA update expression:

Finally, (8) and (9) imply the following useful property:

The average transient behavior of DSE-CMA is completely determined by the expected DSE-CMA error function,

. Equations (2)–(7) indicate that the real and imaginary components of

are “hard-limited” versions of the real and imaginary components of the CMA error function,

and

, i.e.,

and similarly for

In the theorems below, the implications of (12) are formalized in terms of DSE-CMA behavior over specific ranges of

Lemma 1. Define

The choice of dither amplitude ensures that for all equalizer outputs y satisfying the output amplitude constraints: , where denotes the unique real-valued root (2) of the cubic polynomial .

Proof. According to (12),

when

and

. Thus, it is sufficient to show that

if both

and

. Noting from the definition of

that

and that

, the remainder of the proof follows from Figure 3, where the roles of

and

should become clear.

Figure 3. Illustration of Lemma 1.

Writing the system output as

, for a (fixed) received vector r and arbitrary equalizer f, allows the following equalizer-space interpretation of Lemma 1:

Theorem 1. Denote the set of possible received vectors by R, and define to be the convex hull formed by the set of hyperplanes . Then choice of dither amplitude ensures that the expected DSE-CMA update is identical to the CMA update for equalizers within .

Proof. The details mimic those of the real-valued case in [7] after substituting

for

Next, we concern ourselves with neighborhoods of the zero-forcing (ZF) equalizers

Theorem 2. Define

Under satisfaction of the PBE conditions, choice of dither amplitude ensures the existence of a neighborhood around every ZF solution within which the expected DSE-CMA update is identical to the CMA update.

Proof. The details mimic the real-valued case given in [7].

Theorem 2 is of limited practical use since it requires satisfaction of PBE conditions. Fortunately, the concept is easily extended to the set of “open-eye” equalizers,

. Denoting the minimum distance between any pair of adjacent symbols in S by

The corresponding set of open-eye equalizer outputs is defined by

Theorem 3. Define

Choice of dither amplitude ensures the existence of a neighborhood around every open-eye equalizer, , within which the expected DSE-CMA update is identical to the CMA update.

Proof. The details mimic the real-valued case given in [7].

In summary,

is a lower bound on dither amplitude

for which the convex set

exists, while

and

are lower bounds on

for which “CMA-like” local neighborhoods around zero-forcing and open-eye equalizers exist, respectively. Table 1 quantifies the values of

for M-QAM alphabets. Note that the constant

may be less than

, in which case there would exist isolated “CMA-like” neighborhoods around the ZF solutions (i.e., ’hoods not contained in any “CMA-like” convex hull).

Table 1: Critical values of a for M-QAM.

M	4	16	64	256	1024
	0.38	0.58	0.62	0.63	0.64
	0	0.64	1.45	2.04	2.38
	3.27	2.37	2.43	2.57	2.66

The principal disadvantage of DSE-CMA concerns its steady-state behavior: the addition of dither leads to an increase in excess mean-squared error (EMSE), typically defined as the steady-state MSE above the level attained by a fixed locally minimum MSE solution. The subsections below quantify the EMSE of DSE-CMA under the satisfaction (or near-satisfaction) of the PBE conditions.

Small-Error Approximation of

Defining the output error

, the CMA error function can be written as

For small output error (i.e.,

1), we approximate the error function by expanding (13) and disregarding all but first order terms in

and

Without loss of generality, consider a zero-forcing phase offset

. Then, in the absence of channel noise, the parameter error definition

allows us to write

Since under the PBE assumptions and a reasonably small step-size we expect asymptotically small

, (14) can be used to characterize the steady-state behavior of DSE-CMA.

The Excess MSE of DSE-CMA

EMSE at time index n is defined to be the expected squared error above that achieved by the (local) zero-forcing solution

. Since, under satisfaction of the PBE conditions,

achieves zero error,

We are interested in quantifying the steady-state EMSE:

Our derivation assumes the following:

(B1) The equalizer parameter error vector

is statistically independent of the equalizer input r(n).

(B2) The dither amplitude

is chosen sufficiently greater than

so that

for all

under consideration.

(B3) The PBE conditions (A1)–(A4) are satisfied to the extent that the zero-forcing solution attains near-zero error, i.e.,

(B4) The step-size is chosen small enough for the small-error approximation (14) to hold asymptotically.

Assumption (B2) is needed for the results of the quantization noise model in "Quantization Noise Model" to hold.

Using the properties of the trace operator, the independence assumption (B1), and the definitions

and

, it is straightforward to show that

The quantization noise model of Section 4.1 and the error function approximation (14) can be used to derive the following recursion for F(n), valid for equalizer lengths

Then, using (15) and (16), one can derive the following approximation to the steady-state EMSE of DSE-CMA:

where

and

. The details of the derivation of (15)–(17) follow the real-valued case [7] closely.

Equation (17) can be compared to an analogous expression for the EMSE of complex-valued CMA [4]:

It is apparent from (17) and (18) that the EMSE of CMA and DSE-CMA differ by the multiplicative factor

via

. Note the dependence on both the dither amplitude

and the distribution of

. Table 2 presents values of

for various M-QAM sources and particular choices of

Table 2: EMSE Relative Performance Factor:

M-QAM	4	16	64	256	1024
	—	3.8	13.3	24.0	32.3
	—	51.6	37.2	24.0	38.2

Excess MSE Under PBE Conditions

Table 3 presents simulation results verifying the approximation of the excess MSE of DSE-CMA given in (17). The simulations were conducted using length-64 MMSE approximations of three (noiseless) SPIB (3) microwave channels, T/2-spaced length-62 FSEs, and various i.i.d. M-QAM sources. This ensured that conditions (A1)–(A4) were satisfied. The step-sizes were chosen so that (B4) was satisfied, and the dither amplitude of

= 2.5 satisfied (B2). Table 3 gives percentage deviations from the EMSE levels predicted by (17) which were obtained by averaging the results of

iterations. Overall, the simulation results closely match (17).

Table 3.

Deviation from Predicted Level (17).

Average Transient Behavior

Since we have emphasized the importance of performance evaluation in realistic (non-ideal) environments, we now present a comparison of DSE-CMA to CMA in this content. Figure 4 shows ensemble-averaged MSE trajectories of the two algorithms operated under identical conditions and initialized at the same locations using various SPIB microwave channels. Noise level (SNR = 40 dB) and equalizer length

were selected to represent typical applications while providing open-eye performance (for a 16-QAM source) at convergence. The following “double-spike” [4] equalizer initialization was used in all simulations: taps 10 and 11 were set to 0.5 and all others were set to zero. As evident in Figure 4, the DSE-CMA trajectories track the CMA trajectories closely until the effects of EMSE take over. Figure 4 also suggests that the EMSE approximation in (17) remains a useful guideline even under typical violations of the PBE conditions.

Figure 4. Averaged MSE trajectories for various SPIB channels.

This paper has derived the fundamental properties of the complex-valued dithered signed-error constant modulus algorithm. In summary, we have found that, under proper selection of algorithmic design quantities, the expected transient behavior of DSE-CMA is identical to that of CMA. Though the steady-state MSE of DSE-CMA is larger than that of CMA, its value is well characterized and can be accounted for in the design procedure. Lacking space, we refer the reader to [7] for advice on the selection of

, and f(0); the guidelines mimic those of the real-valued case.

With the exception of computational complexity, the new algorithm has been designed to mimic CMA, rather than “improve” on its performance. Our primary motivation for this is twofold. First, CMA is well-regarded by practitioners. It has established itself over the last 20 years as the most popular practical blind equalization algorithm, due in large part to its robustness properties [3]. It is precisely these robustness properties which we have attempted to preserve. Secondly, CMA has been extensively analyzed by theoreticians [3]. The bulk of these analyses apply directly to DSE-CMA. As it is often the case that modifications of classic algorithms have disadvantages that outweigh the proposed advantages, the spirit of DSE-CMA is a computationally efficient algorithm that “leaves well enough alone.”

Finally, we mention a potentially useful modification to DSE-CMA. In the case of SE-LMS, the extension of the sign operator to a multi-level quantizer has been shown to yield significant performance improvements at the expense of a modest increase in computational complexity [9]. Perhaps multi-level quantization would yield similar advantages for DSE-CMA, most importantly a reduction in EMSE.

A more tutorial (and more complete) development of the fractionally-spaced system model can be found in [3].

When

, it can be shown that the cubic polynomial

has a unique real-valued root which is given by the expression

The Signal Processing Information Base microwave channel database resides at http://spib.rice.edu/spib/microwave.html.