GLRT-Optimal Noncoherent Lattice Decoding
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 1
GLRT-Optimal Noncoherent Lattice Decoding
Daniel J. Ryan†‡∗, Iain B. Collings‡ and I. Vaughan L. Clarkson⋆
†School of Electrical and Information Engineering, University of Sydney, AUSTRALIA,
Phone: +612 9372 4465, Fax: +612 9372 4490, Email: dan@ee.usyd.edu.au
‡Wireless Technologies Laboratory, CSIRO ICT Centre, AUSTRALIA,
Phone: +612 9372 4120, Fax: +612 9372 4490, Email: iain.collings@csiro.au
⋆School of Information Technology and Electrical Engineering, University of Queensland, AUSTRALIA,
Phone: +617 3365 8834, Fax: +617 3365 4999, Email: v.clarkson@itee.uq.edu.au
Abstract
This paper presents new low-complexity lattice-decoding algorithms for noncoherent block detection of QAM
and PAM signals over complex-valued fading channels. The algorithms are optimal in terms of the generalized
likelihood ratio test (GLRT). The computational complexity is polynomial in the block length; making GLRT-optimal
noncoherent detection feasible for implementation. We also provide even lower complexity suboptimal algorithms.
Simulations show that the suboptimal algorithms have performance indistinguishable from the optimal algorithms.
Finally, we consider block based transmission, and propose to use noncoherent detection as an alternative to pilot
assisted transmission (PAT). The new technique is shown to outperform PAT.
Index Terms
Noncoherent detection, lattice decoding, wireless communications.
I. INTRODUCTION
Noncoherent transmission of digital signals over unknown fading channels has recently received significant
attention especially for the case of the block-fading channel model. Applications include recovery from deep
fades in pilot-symbol assisted modulation based schemes, eavesdropping, and non-data-aided channel estimation.
Noncoherent transmission is particularly applicable to systems exhibiting small coherence intervals where the use of
training signals would result in a significant loss in throughput. Recently, some elegant information-theoretic results
have been derived for noncoherent single and multiple-antenna systems under the assumption of Rayleigh fading, for
I. V. L. Clarkson was on study leave throughout 2005 at the Dept. of Electrical & Computer Engineering, University of British Columbia,
Canada. This paper has appeared in part at VTC-Spring 2006 and ICASSP 2006.
http://arxiv.org/abs/0704.1524v1
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 2
example [1, 2]. Information theoretic aspects of noncoherent transmission were considered in [3] which concluded
that at low SNR and for small coherence intervals there is a significant capacity penalty by using training. Under
this noncoherent detection regime, it has been shown by numerical simulation that standard modulation techniques
such as quadrature amplitude modulation (QAM) can achieve near-capacity in the single-antenna noncoherent block
Rayleigh-fading channel [4].
This paper focuses on noncoherent receiver design for the block fading channel. A great deal of work has been
performed on partially coherent receivers such as pilot-symbol assisted modulation (PSAM) [5, 6], per-survivor
techniques [7], and coupled estimators [8]. However the challenge remains to develop high-performance, low-
complexity, fully noncoherent receivers.
Various suboptimal algorithms have been proposed for block-based noncoherent detection. For slowly fading
channels, a blind phase recovery approach was proposed in [9] for noncoherent detection of differentially encoded
QAM [10] where the attenuation was assumed to be known exactly at the receiver. In [11], a suboptimal technique
for PSK was proposed which involved forming a number of equally spaced channel phase estimates. An extension
to multi-amplitude constellations was also presented, where every sequence of symbol amplitudes is considered,
and then the PSK technique is applied to determine the phase of the symbols. Unfortunately, the complexity of this
suboptimal approach is still exponential in the sequence length, albeit with a smaller base.
Recently, lattice decoding algorithms have been applied to noncoherent and differential detection. For PSK
over temporally-correlated Rayleigh fading channels, a form of lattice decoding (namely sphere-decoding) can be
applied since it turns out that the detection metric is Euclidean [12]. Lattice decoding techniques have also been
used for differential detection of diagonal space-time block codes over Rayleigh fading channels, by approximating
the decision metric with a Euclidean metric [13, 14]. In [15], we presented simulation results for another lattice
projection approach for suboptimal PAM and QAM detection. Unfortunately, each of these algorithms require
complexity exponential with the block length to guarantee that the optimal estimate is found [16, 17]. Practical
implementation considerations demand that low complexity algorithms be developed.
For the case of the constant envelope PSK constellation, a detection algorithm with complexity O(T logT ) was
developed in [18, 19] (where T is the block length), which can provide the optimal data estimate over an unknown
noncoherent fading channel, in terms of the Generalized Likelihood Ratio Test (GLRT). The GLRT is equivalent to
joint ML estimation of a continuous valued channel parameter and discrete-valued data parameters. This approach
was generalized in [20], where they outlined a general graph-based approach which involved forming a spanning
tree. Specific details were presented for the cases of QAM over a phase noncoherent channel (i.e. known channel
amplitude) [20, 21], and for PSK over a fading channel with coding [22]. The challenge remains to develop efficient
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 3
algorithms for optimal noncoherent sequence detection of multi-amplitude constellations over fading channels.
In this paper we propose a new GLRT-optimal noncoherent lattice decoding approach for QAM and PAM symbols
which has complexity polynomial in the block length. We start by considering detection of M -ary PAM over real-
valued fading channels (which we shall term real-PAM). We show that the GLRT-optimal codeword estimate is the
closest codeword (or lattice point) in angle to the line described by the received vector. We propose an algorithm
that searches along the line, and chooses the best codeword estimate from this search. We provide a theorem that
bounds the search to a segment of the line, limiting the number of codewords that need to be considered. We show
how the search can be done in an iterative manner, and that the resulting complexity of the algorithm is O(T logT ).
We then consider the more practical case of M -ary QAM detection over complex-valued fading channels, and
show that in this case the GLRT-optimal codeword estimate is the closest codeword in angle to a plane described
by the received vector. We propose an algorithm that searches across the plane, and chooses the best codeword
estimate from this search. We provide a theorem that bounds the search to a segment of the plane. We show how
the extent of the search can be further reduced by exploiting the rotational symmetry of the constellation. The
resulting plane search algorithm can be performed with complexity of order O(T 3).
We also present new suboptimal noncoherent QAM detection algorithms with even lower complexity; by com-
bining a channel phase estimator with our fast real-PAM algorithm. We propose using O(T ) instances of the
real-PAM algorithm. This approach therefore has complexity of order O(T 2 logT ). Simulations indicate that there
is a negligible performance loss compared to GLRT, when using this suboptimal technique.
Finally, we also propose a pilot-assisted version of our new reduced-search noncoherent lattice-decoding algo-
rithms. The pilot symbol is used to remove the ambiguities inherent with noncoherent detection. Our approach
obtains improved performance compared with standard pilot assisted transmission [6], while maintaining the same
data rate.
II. SYSTEM MODEL
A. Signal Model
We define a codebook C(X , T ) as the set of all possible sequences of T transmitted symbols, x = [x1, . . . , xT ]
such that each xt is in some constellation X . For an M -ary PAM constellation, X = {±1,±3, . . . ,±(M − 1)}. For
QAM, X is a subset of the Gaussian (complex) integers with odd real and imaginary components. For example, for an
M2-ary square QAM constellation, X = { x |Re {x} ∈ X ′, Im {x} ∈ X ′} where X ′ , {±1,±3, . . . ,±(M − 1)}.
Thus each codebook C(X , T ) is a set of lattice points drawn from a subset of the unit lattice of RT or CT .
We consider block fading channels and assume that the channel h is constant for at least T symbols as in [1–4,
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 4
11]. We will consider narrowband fading channels where h is either real-valued and complex-valued channels. Thus
we can write the received codeword y = [ y1, . . . , yT ]
′ as follows,
y = hx+ n (1)
where n = [ n1, . . . , nT ]
′ is a vector of additive white Gaussian noise.
B. Detection
The noncoherent detection problem is to estimate x based on y without knowledge of the channel and in the
absence of training data. The log-likelihood function of the maximum likelihood (ML) detector (of both channel
and data) is given by
L(y;x, h) = −‖y − hx‖
where constant factors have been discarded and ‖·‖ represents the Euclidean norm. For a given codeword hypothesis
x̂, the likelihood function is maximized by choosing
where (·)† denotes Hermitian transpose.
Hence, the ML estimate of x conditioned on the corresponding channel estimate, is given by
opt = arg max
x̂∈C(X ,T )
y; x̂,
= arg max
x̂∈C(X ,T )
∣x̂†y
This is the Generalized Likelihood Ratio Test (GLRT) [23] considered in [11, 20].
Note that (4) is equivalently given by
opt = arg max
x̂∈C(X ,T )
∣x̂†y
= arg max
x̂∈C(X ,T )
cos2 θ(x̂,y) (6)
where θ(x,y) is the principal angle between x and y [24]. Thus x̂opt can be found by searching the points of
C(X , T ) to find the one closest in angle to y.
For QAM, we can also obtain a geometric interpretation of (4) by expressing the complex vectors in R2T . We
will use the underscore notation x to denote the mapped version of x as follows,
x = [ Re {x1} Im {x1} . . . Re {xT } Im {xT }]
′ (7)
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 5
and denote the real-valued codebook as CR(X , T ) = {x | x ∈ C}. For M
2-ary square QAM, we therefore have
CR(X , T ) = C(X
′, 2T ) where X ′ is an M -ary PAM constellation. We also define Y ∈ R2T×2 as a basis for the
subspace yC mapped into the real space R2T ; that is
Re {y1} Im {y1} . . . Re {yT } Im {yT }
− Im {y1} Re {y1} . . . − Im {yT } Re {yT }
. (8)
Note that the columns of Y are orthogonal. The projection matrix P(y) ∈ R2T×2T is defined as
P(y) ,
such that
P(y)x = arg min
v∈YR2
‖x− v‖ .
That is, the vector P(y)x is the projection of x onto the subspace YR2. Now, it can be easily shown that
= arg max
x̂:x̂∈C(X ,T )
cos2 θ(x̂,P(y)x̂)
Thus the GLRT-optimal data estimate x̂opt, corresponds to the x̂ ∈ CR(X , T ) closest in angle to the plane YR
It is important to note that two forms of ambiguity exist for this noncoherent detection problem. The first is
the well-known phase ambiguity which occurs for any constellation that is invariant to a particular phase rotation.
For example, for square QAM constellations the following four optimal channel estimate and codeword pairs have
the same likelihood: (ĥopt, x̂opt), (−ĥopt,−x̂opt), (−iĥopt, ix̂opt) and (iĥopt,−ix̂opt); corresponding to the four π/2
rotations of the constellation. We will assume that this type of ambiguity can be resolved, for example, by using
the phase of the last symbol from the previous codeword [4], or by using differential encoding [10]. The second
type of ambiguity we call a divisor ambiguity and arises when there are multiple points in C(X , T ) that lie on
the same 1-dimensional (real or complex) subspace e.g. [1, 1, 1] and [3, 3, 3] for 4-ary real-PAM with T = 3. This
produces a lower bound on the noncoherent block detection error rate as discussed and analyzed in [25].
III. REDUCED SEARCH SPACE
In this section we show that the GLRT-optimal data estimate x̂opt, can be found without testing all the elements of
C(X , T ). In the previous section we established that x̂opt is the codeword closest in angle to a particular subspace,
so it naturally makes sense to define a ‘nearest neighbor set’ of the subspace and search within that set. The
subspace of interest has basis vector y and passes through the origin. We show that the nearest neighbor set for this
subspace contains x̂opt. This implies that low complexity decoding algorithms can be developed, based on finding
this particular nearest neighbor set, and searching it.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 6
Definition 1: We define NN(v) to be the point, or set of points, in C(X , T ) closest to the arbitrary point v (i.e.,
the nearest neighbor to v). That is, d is an element of NN(v) if ‖v − d‖ 6 ‖v − z‖ for all z ∈ C(X , T ).
Of course, usually NN(v) will have a single element, and in this case we can write NN(v) = d.
Definition 2: We define N (C(X , T ),y) to be the nearest neighbor subset of the codebook C(X , T ), corresponding
to the subspace with basis vector y, passing through the origin. That is, u ∈ N (C(X , T ),y) if and only if there
exists some λ such that NN(λy) = u.
Note that from a geometrical perspective, it is useful to think of λ as being equivalent to the inverse of a channel
estimate; implying that a point u is in the nearest neighbor set if there is a channel estimate ĥ such that the distance
|y− ĥu| is smaller than for any other point. Consequently we define λ̂opt , (ĥopt)−1 as the reciprocal of the optimal
channel estimate.
The following property of the GLRT-optimal codeword estimate x̂opt, allows us to reduce the set of codewords
which need to be tested, to a small subset of the |X |
possible codewords (where |·| denotes set cardinality). Note
that an equivalent result was presented in [20], however the geometrical interpretation of our formulation is more
apparent; and is important when developing our new search algorithms later.
Property 1:
opt ∈ N (C(X , T ),y).
Proof: Consider the case where x̂opt /∈ N (C(X , T ),y). From Definition 2 this implies that there exists some
x̂ ∈ N (C(X , T ),y) such that ||λ̂opty−x̂|| < ||λ̂opty−x̂opt|| however this would imply L(y; x̂, ĥopt) > L(y; x̂opt, ĥopt)
from (2) and hence we have a proof by contradiction.
IV. PAM DETECTION FOR REAL-VALUED FADING CHANNELS
This section presents a low complexity algorithm for GLRT-optimal noncoherent PAM detection over real-valued
channels. Practically, such channels arise in baseband transmission (eg. multi-level PCM), or in certain bandpass
systems where phase and frequency are separately estimated by a phase-locked loop.
We first present a theorem that we will use to reduce the number of codewords that need to be examined, even
beyond the limitations imposed by Property 1. Note that in this real-valued channel case, the subspace of interest
(defined by y) actually reduces to a line, yR. The theorem implies that only a limited extent of the line needs to
be searched; and that the extent depends on the largest value of y. We then propose a fast low-complexity iterative
algorithm to perform the search. In the sequel, we will extend the algorithm to complex-valued channels. Later, we
will directly incorporate the algorithm from this section into an extremely low complexity suboptimal algorithm for
noncoherent detection over the more commonly encountered complex-valued channels.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 7
A. Limiting the Search Space
Theorem 1: For noncoherent detection of M -ary PAM codewords of length T over a real-valued fading channel
∣λ̂optyt
∣ 6 M + T − 2
for all t = 1, 2, . . . , T .
Proof: Define n , argmaxt {|λ̂
optyt|}. Note that if |λ̂
optyn| 6 M then the theorem is satisfied.
Now, consider the alternative case when |λ̂optyn| > M . Rearranging the GLRT-optimal channel estimate in (3)
gives (x̂opt)′(y − ĥoptx̂opt) = 0 and hence
(x̂opt)′(λ̂opty − x̂opt) = 0. (10)
We will use this property to bound λ̂opt. Using (2) and the fact that C(X , T ) contains all possible sequences
{ x | xt ∈ X ∀t }, the elements of x̂
opt can be determined on an element-wise basis as
t = argmin
∣λ̂optyt − x
∣. (11)
For the case we are considering where |λ̂optyn| > M , it follows that since the largest PAM constellation values are
±(M − 1), that x̂optn = sgn {yn}(M − 1) where sgn is the signum function.
We now substitute (11) into (10) to bound λ̂opt, which gives
x̂optn
λ̂optyn − x̂
λ̂optyt − x̂
. (12)
Now (11) and the symmetry of the PAM constellation implies that sgn
= sgn {λ̂optyt}. Moreover, since
t ∈ {±1,±3, . . . ,±(M − 1)} it follows form the definition of λ̂
opt that −1 < λ̂optyt− x̂
t < 1 for all x̂
t except
±(M − 1). More generally, for all x̂optt , sgn
(λ̂optyt − x̂
t ) > −1 and hence x̂
λ̂optyt − x̂
> −|x̂
Substituting this into (12) gives
x̂optn
λ̂optyn − x̂
and hence
∣λ̂optyn
x̂optn +
6 M − 1 +
(T − 1)(M − 1)
M − 1
= M + T − 2.
Therefore, since |λ̂optyt| 6 |λ̂
optyn| for all t the theorem is proved.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 8
B. PAM Algorithm
In this Section we use Property 1 and Theorem 1 to develop a low-complexity algorithm for real-PAM detection.
This algorithm reduces the number of codewords for which the decision metric is evaluated to order MT , which
is much smaller than the set of all possible MT codewords that would be considered by an exhaustive search.
Furthermore, we demonstrate how the algorithm can be implemented in an iterative manner so that the complexity
is O(T logT ).
Property 1 implies that x̂opt can be found by calculating the metric in (4) for only those x̂ ∈ N (C(X , T ),y),
i.e. for only those x̂ ∈ C for which the line yR passes through its Euclidean nearest neighbor region. Furthermore,
Theorem 1 implies that only a finite segment of the line need be considered. We have demonstrated such a search in
Figure 1, which shows the positive axes for 8-ary PAM with T = 2, where the shaded regions indicate the nearest
neighbor regions of the points which need to be searched. The specifics of the algorithm are as follows.
First, for ease of notation we modify the received codeword y by changing the signs of all negative elements in
y. This will mean that the corresponding (modified) x̂opt will now have all positive elements. The true (original)
GLRT estimate of x can be obtained by applying the reverse sign changes to x̂opt. Observe that we can do this
without loss of generality since the PAM constellation is symmetric around zero.
Definition 3: We define P (x̂) to be the range of λ such that x̂ is the nearest neighbor to λy, within the limits
0 < λ < λmax , (M + T − 2)/maxt {yt} (where the limits are due to Theorem 1 and the fact that all xt are
greater than zero for the modified received codeword). Formally,
P (x̂) , {λ | x̂ ∈ NN(λy), λ ∈ (0, λmax)}.
Note that each non-empty P (x̂) corresponds to a distinct interval of the line yR. The proposed algorithm proceeds
by enumerating these non-empty P (x̂)’s, by first enumerating their boundary points along the line yR. We then sort
the boundary points so that the decision metrics for the corresponding x̂ can be calculated in an iterative manner.
For real-PAM, the boundary values of λ can be shown to be given by νt,b =
for all t = 1, . . . , T and
b = 2, 4, . . . ,M − 2 such that 0 < νt,b < λ
max (where the values of b come from the regular boundaries in the
positive half of the PAM constellation X ). We use V0 to denote the set of all (νt,b, t) pairs.
We then sort the elements of V0 in ascending order of their νt,b value, and append the value (λ
max, 0) to the
end of the ordered set (since this is the outer boundary of the segment of the line yR which needs to be searched,
according to Theorem 1; where the second element of the pair is arbitrarily set to 0 since it is not needed in the
algorithm). We denote the newly ordered set by V , and index it by k, (i.e. we denote its kth element by (νk , tk)).
These ordered values are shown on the example case of Figure 1, where the values of νk denote the distance along
the line yR where the line crosses from one nearest neighbor region into the next.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 9
We now show how V can be used to enumerate the codewords which need to be searched, and show how to
calculate the corresponding decision metrics in an iterative manner. The algorithm can be visualized geometrically
as searching along a segment of the line yR, by iterating in k. Whenever the line crosses from the nearest neighbor
region of one lattice point (codeword) to the nearest neighbor region of another, we calculate the metric for the
new lattice point. Note that in this context, the value of tk indicates the dimension of the boundary that is going
to be crossed (in the T -dimensional space) when leaving the kth segment of the line.
The iterative search starts with the codeword x̂(1) = 1 , [ 1, 1, . . . , 1]′; which has a corresponding decision
metric L(1) = (1′y)2/ ‖1‖2, where L(x̂) , (x̂′y)2/ ‖x̂‖2 is the likelihood function in (4). We will use the symbol
λ̂ as a marker for the most likely codeword, and we initially set it to λ̂ = ν1/2 (i.e. during the iteration process, λ̂
will be updated whenever a codeword is found to have a higher likelihood than any previously searched codeword,
and the value of λ̂ will be chosen such that NN(λ̂) gives the new codeword).
The iteration proceeds by noting that each time a nearest neighbor boundary is crossed, only one element of the
T -dimensional nearest neighbor codeword vector changes (since for real-PAM, the boundaries are straight lines,
orthogonal to one of the dimensions, and parallel to all the others). Therefore the kth codeword which needs to be
considered, is calculated from the (k − 1)th codeword, on an element-wise basis as follows:
x̂(k)p =
(k−1)
p , for p 6= tk−1
p + 1, for p = tk−1.
We define αk , (x̂
(k))′y and βk ,
∥x̂(k)
, and hence L(x̂(k)) = α2k/βk is the decision metric for the kth
codeword considered. The values αk and βk are calculated iteratively as follows,
αk = αk−1 + 2ytk−1 (14)
βk = βk−1 + 4x̂tk−1 + 4. (15)
If L(x̂(k)) improves on the previous best codeword estimate then we update λ̂ in the interior of P (x̂(k)), by
setting λ̂ = (νk + νk−1)/2.
Once all segments of the line have been searched, we have x̂opt = NN(λ̂y). Pseudo-code for the algorithm is
given in Table III.
The complexity of the algorithm is a function of the number of intersection points νt,b, i.e., NI , |V0|, where
|·| denotes set cardinality. NI is upper bounded by (M/2− 1)T , however in general it will be much less than this
due to the restricted line search implied by Theorem 1, as shown by simulation in Section VII. The sorting of V0
can be performed using standard sorting techniques in O(NI logNI) [26]. The updates (13), (14) and (15) have
complexity O(1), and the final calculation of x̂opt is of order T . Thus the overall complexity is dominated by the
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 10
sorting operation, and hence the complexity of the algorithm is of order O(T logT ); a significant improvement
compared with an exhaustive search over all MT possible codewords in the codebook C(X , T ).
V. GLRT-OPTIMAL QAM DETECTION FOR COMPLEX-VALUED FADING CHANNELS
This section presents a low complexity algorithm for GLRT-optimal noncoherent QAM detection over complex-
valued fading channels. Similarly to the the real-PAM case, we first present a theorem that we will use to reduce
the number of codewords that need to be examined, beyond the limitations imposed by Property 1. In the complex-
valued channel case, the subspace of interest is the plane YR2, where Y was defined in (8). The theorem implies
that only a limited extent of the plane needs to be searched; and that the extent depends on the largest element
in y. We then propose a fast low-complexity algorithm to perform the search for QAM. We also show how PAM
detection over complex-valued channels can be viewed as a special case of the QAM algorithm.
A. Limiting the Search Space
Theorem 2: For noncoherent detection of M2-ary QAM codewords of length T over a complex-valued fading
channel
λ̂optyt
∣ 6 M + 2T − 2, and
λ̂optyt
∣ 6 M + 2T − 2,
for all t = 1, 2, . . . , T .
Proof: Define the point v , λ̂opty, along with its corresponding real-valued representation v, as in (7). Also
define n , argmaxt {|vt|}. Note that if |vn| 6 M then |Re {λ̂
optyt}| 6 M and |Im {λ̂
optyt}| 6 M for all t and
the theorem is satisfied.
Now, consider the alternative case when |vn| > M . Similarly to the real-PAM case, rearranging the GLRT-optimal
channel estimate in (3) gives (x̂opt)†(y − ĥoptx̂opt) = 0 and hence
(x̂opt)†(λ̂opty − x̂opt) = 0. (16)
It follows that
λ̂opt =
‖x̂opt‖
|y†x̂opt|
Combining this with the the fact that for any vector u ∈ CT , the real-valued representation of the complex scalar
y†u is Y′u, we obtain the real-valued representation of λ̂opt as
opt =
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 11
and therefore
v = Yλ̂opt =
It follows that v′x = ‖x‖
, i.e.
)′(v − x̂opt) = 0. (17)
Using (2) and the fact that C(X , T ) contains all possible sequences { x | xt ∈ X ∀t }, the elements of x̂
opt can be
determined on an element-wise basis as
t = arg min
x∈X ′
|vt − x| (18)
for all t = 1, . . . , 2T where we recall from Section II-A that X ′ = {±1,±3, . . . ,±(M − 1)}. We now substitute
(18) into (17) which gives
x̂optn
vn − x̂
vt − x̂
. (19)
This is similar to (12) in the proof of Theorem 1. By following through the subsequent steps in the proof of Theorem
1, and keeping in mind that the dimensions of the vectors are now of dimension 2T , we obtain |vn| 6 M +2T − 2
which implies that |Re {λ̂optyt}| < M + 2T − 2 and |Im {λ̂
optyt}| < M + 2T − 2 for all t = 1, . . . , T .
B. QAM Algorithm
In this Section we use Property 1 and Theorem 2 to develop a low-complexity algorithm for QAM detection.
Property 1 implies that x̂opt can be found by calculating the metric in (4) for only those x̂ ∈ N (C(X , T ),Y), i.e. for
only those x̂ ∈ C for which the plane YR2 passes through its Euclidean nearest neighbor region. Furthermore,
Theorem 2 implies that only a finite region of the plane need be considered. Conceptually, this is a direct extension
of the real-PAM case shown in Figure 1 (considered previously). The difference being that Figure 1 shows the
line yR, but we now have a plane YR2. Also the number of orthogonal dimensions doubles when considering
complex-valued channels. We demonstrated this complex-valued channel QAM case in Figure 2 which is a two
dimensional plot in the plane YR2. The parallel lines (at various angles) are the boundaries arising from the QAM
constellation, and the shaded region indicates the nearest neighbor regions of codewords which need to be searched.
The QAM search algorithm we present here, follows the same principles as the real-PAM algorithm of Section
IV-B, where instead of working with boundary points of line segments, we need to work with boundary edges of
planar regions. The specifics of the algorithm are as follows.
First, for ease of notation we modify the received codeword y by multiplying it by the complex scalar y∗m/|ym|,
where m = argmaxt |yt|. This will mean that the mth element of y will be real-valued and positive. The true
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 12
(original) GLRT-optimal estimate of the channel can be be obtained by applying the reverse phase rotation to ĥopt,
while the optimality of the new GLRT-optimal codeword estimate is unaffected.
Hence Theorem 2 implies that the search over the plane Yλ is reduced to the segment of the plane for which
|λ1|, |λ2| < λ
max where λmax , (M +2T − 2)/|ym|. Furthermore, as discussed in Section II-B because of the π/2
phase ambiguity in square QAM constellations, there are four GLRT-optimal inverse channel estimates ±λ̂opt,±iλ̂opt
(with corresponding phase ambiguous GLRT-optimal codeword estimates). Hence, we only need to consider the
square region of the plane
S = { λ | λ1 ∈ (0, λ
max), λ2 ∈ [0, λ
max) } (20)
since exactly one of ±λ̂opt,±iλ̂opt will exist in this region of the plane. Note that S is the shaded region in Figure
2 (mentioned previously).
Similarly to the real-PAM case we make the following definition.
Definition 4: We define P (x̂) to be the range of λ ∈ S such that x̂ is the nearest neighbor to Yλ. Formally,
P (x̂) , {λ | x̂ ∈ NN(Yλ), λ ∈ S }.
Note that each non-empty P (x̂) corresponds to a distinct region of the plane YR2. The proposed algorithm
proceeds by enumerating these non-empty P (x̂)’s, by first enumerating their boundary vertices in the plane. These
vertices are found by calculating the intersection of all the constellation-point boundary lines in the plane (e.g. as
shown in Figure 2). The vertices are then used to calculate an interior-point inside each of the nearest neighbor
regions in the shaded square S. The respective nearest neighbor codeword is calculated for each interior-point, and
then it is only these points for which the likelihood metrics are calculated. Clearly, this is a significantly reduced
search space compared with the space of all possible codewords.
For QAM the vertices of the nearest-neighbor regions in the plane YR2 can be found by first noting that, since
t can be given in on an element-wise basis as in (18), P (x̂) can be written as
P (x̂) ,
{ λ | xt = arg min
x∈X ′
|(Yλ)t − x|, λ ∈ S}
where (Yλ)t is the tth element of Yλ and we recall that X
′ = {±1,±3, . . . ,±(M − 1)}. This can be written as
the feasible region for the set of linear inequalities corresponding to the nearest neighbor region boundaries in X ′
for each element of x̂t, as
P (x̂) =
{ λ | l(x̂t) 6 (Yλ)t 6 u(x̂t), λ ∈ S}
where l(x̂t) and u(x̂t) are the upper and lower nearest neighbor boundaries in the constellation X
′. For t /∈
{2m, 2m− 1} they take on values in the set {0,±2, . . . ,±(M − 2),±∞}. For t ∈ {2m, 2m− 1} we must
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 13
consider intersections with the boundary of S, and therefore in this case l(x̂t) and u(x̂t) take on values in the set
{0,±2, . . . ,±(M − 2),±(M + 2T − 2)}.
By including the square boundary of the region S, all non-empty P (x̂) are closed simply connected sets on the
plane R2. Therefore, since P (x̂) is formed from linear inequalities it is a convex polygon in R2. For each P (x̂),
denote B(x̂) as its polygonal boundary and V (x̂) as the vertices of the polygon.
We now propose a method that enumerates all the vertices V (x̂) for all non-empty P (x̂), and then uses these
vertices to generate a point in the interior of all P (x̂), which is then used to obtain a unique codeword via finding
the nearest neighbor codeword to that point. Consider the set of points { ν ± ǫµ |ν ∈ V (x̂)}. If µ is some vector
that is not parallel to any side of the polygon P (x̂), and if ǫ is chosen sufficiently small, then at least one point in
this set will be in the interior of P (x). Since the received symbol is subject to AWGN, and is therefore irrational
with probability one, it follows that the arbitrary choice of µ , [ 1 1 ]′ will almost surely guarantee this, given that
ǫ > 0 is chosen sufficiently small. In practice, simply setting ǫ to some small positive constant will be sufficient
to ensure that a point in the interior of P (x̂) is enumerated. However, in Appendix A we present a technique to
perform this in a strictly optimal fashion with complexity per vertex of O(T ).
Since the vertices are shared by adjacent P (x̂), each vertex is only required to be enumerated once. We define
the set of all vertices within or on the boundary of S as V = { ν | ν ∈ V (x̂), P (x̂) 6= ∅ }. The set V can be
enumerated as the the intersections of the lines Y t,1ν1 + Y t,2ν2 = b and Y t′,1ν1 + Y t′,2ν2 = b
′, for all pairs of
t, t′ and for all nearest neighbor boundaries b, b′ in X ′. That is
Y t,1 Y t,1
Y t,2 Y t,2
for all t = 1, 2, . . . , 2T − 1, t′ = t + 1, t + 2, . . . , 2T , and b, b′ ∈ B(t), where B(t) , {0,±2, . . . ,±(M − 2)}
if t /∈ {2m, 2m− 1} and for symbol indices t ∈ {2m, 2m− 1} where we consider the square boundary B(t) ,
{0,±2, . . . ,±(M − 2),±(M + 2T − 2)}.
To enumerate a point in each P (x̂), for each vertex ν enumerated we calculate the points on the plane λ+ ,
ν+ǫµ, and λ− , ν+ǫµ. Then for each of these two points, if it is in the square S, we calculate the corresponding
codewords NN(λ+Y) and/or NN(λ−Y) and the decision metrics in (4).
Pseudo-code is provided in Table IV.
The complexity of the algorithm is a function of the number of codewords examined, NC , which is in turn
a function of the number of vertices calculated. The number of vertices calculated in (21) corresponding to the
intersections between lines in where b, b′ is a boundary of X ′ and both b and b′ are non-zero is T (2T − 1)[(M −
1)2 − 1]; for which at most two codewords are generated for a quarter of these intersections. For the intersections
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 14
of the boundaries of X ′ and the square S there are 2(2T − 2)(M − 1)2 intersections, which for one quarter of
these intersections one codeword is generated. For the vertices at (0, 0) and (λmax, λmax) one codeword is generated.
Hence the total number of codewords examined is at most
T (2T − 1)
[(M − 1)2 − 1] + (2T − 2)(M − 1)2 + 2. (22)
Since the complexity of each codeword and decision metric calculation is of order T then the overall complexity is
of order M2T 3 (which is linear in the constellation size M2) a significant improvement over an exhaustive search
over all M2T possible codewords in the codebook C(X , T ).
A further reduction in computational expense, without any loss in optimality, can be achieved by enumerating
only one out of each set of four phase ambiguous vertices. The technique is not presented here due to space
constraints, however the number of non-zero vertices examined is reduced by a factor of 4 and 1/3 of the matrix
inverse calculations in (21) are avoided.
C. PAM Over Complex Channels
PAM detection over complex fading channels can be viewed as a special case of complex-channel QAM,
where there is zero imaginary component in the constellation. In this case, the search over the plane YR2 can
be restricted by extending the proof of Theorem 2. To do this, we note that the condition in (16) holds, which
implies that (x̂opt)′(Re {λ̂opty} − x̂opt) = 0 since x̂opt is always real-valued. The rest of the proof follows to give
the result that |Re {λ̂optyt}| 6 M + T − 2. This fact combined with Property 1 and the π phase ambiguity
of PAM constellations, implies that we only consider codewords x̂ = NN(Yλ) for λ in the region S =
{ λ | 0 < λ1 < λ
max = (M + T − 2)/|ym| }.
The specifics of the M -ary PAM algorithm are the same as for the M2-ary QAM case, with the exception that
the calculation of (21) to obtain the vertices in the interior of the (21) is only performed for all t = 1, 3, . . . , 2T −1,
t′ = t + 2, t+ 4, . . . , 2T , and b, b′ ∈ B(t), where B(t) , {0,±2, . . . ,±(M − 2)} if t 6= 2m− 1 and for B(t) ,
{0,±2, . . . ,±(M − 2),M + T − 2} if t = 2m− 1.
The total number of codewords searched can be shown to be at most
T (T − 1)
[(M − 1)2 − 1] + (T − 1)(M − 1) + 1. (23)
Since the complexity of each codeword and decision metric calculation is of order T then the overall complexity is
O(T 3). In the following section, we will see that a simple suboptimal approach can achieve even lower complexity
with near-optimal performance.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 15
VI. SUBOPTIMAL ALGORITHMS FOR COMPLEX-VALUED FADING CHANNELS
In this section, we propose even lower complexity suboptimal algorithms for detection of QAM and PAM over
complex-valued fading channels. We directly use the GLRT-optimal algorithm for real-PAM from Section IV as
the basis for the algorithms.
A. Suboptimal PAM algorithm
Since for PAM constellations, all constellation points lie along the real line in the complex plane, a suboptimal
phase estimation technique combined with our GLRT-optimal algorithm for real-valued fading channels should be
sufficient to provide near-optimal performance. This effectively reduces the search over the whole plane YR2 for
the GLRT-optimal case, to a search over a single line at the given estimated phase angle.
We use the power-law estimator [27] which, for constellations exhibiting a rotational symmetry of π radians, is
simply
φ̂PL ,
y2t (24)
where ∠ refers to the complex argument. Detection is performed by first rotating the received codeword y according
to this estimate, and then detecting Re{e−jφ̂PLy} using the GLRT-optimal algorithm of PAM over a real-valued
fading channel.
B. Suboptimal QAM algorithm
Here we propose a suboptimal algorithm, which reduces the overall algorithmic complexity to O(T 2 logT )
by using O(T ) instances of the PAM detection algorithm presented in Section IV. Instead of enumerating the
intersections of lines on the (λ1, λ2)-plane, as we did in Section V-B, here we propose to use a modified version of
the nearest-neighbor real-PAM line-search algorithm for L lines of the type presented in Section IV. We generate
these lines emanating from the origin into S (the shaded region in Figure 2), evenly spaced in angle. Of course, this
does not guarantee that we fully enumerate N (C(X ), T ) since a finite number of radiating lines can not completely
cover a plane, however, we will see by simulation in Section V-B that the performance is close to the optimal.
As in the optimal case, we multiply y by y∗m/|ym| so that ym will be real-valued and positive. In this suboptimal
QAM case, this implies that we only examine points on the plane Yλ for λ = [ λ1 λ2 ]
′ satisfying 0 < |λ1|, |λ2| <
λmax0 , where λ
0 , (M + 2T − 2)/|ym|.
The L directions of the lines with respect to the direction of positive λ1 have angles Φ , {φ1, . . . , φL} where
φℓ = (ℓ − 1)π/(2L). For each angle φℓ, we perform a nearest neighbor line search for the line with basis vector
[ cosφℓ sinφℓ ], as proposed in the suboptimal PAM algorithm in Section VI-A. The search is performed for
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 16
the segment of the line λy
where λ ∈ R and 0 < λ < λmaxℓ where λ
l , λ
0 /max{cosφℓ, sinφℓ}. In this case
the lines searches are performed for blocks of length 2T .
There is of course a modification required to update the codeword metrics in terms of complex numbers. The
first line search performed is for φ1 = 0, and hence the line search is over λy1 = λy. In this case the intervals of
the line P (x̂) are defined as,
P (x̂) ,
λ | x̂ ∈ NN(λy
), λ ∈ (0, λmaxl )
Hence the algorithm works by enumerating and calculating the metric for all x̂ ∈ C(X ′, 2T ) for which P (x̂) is
non-empty.
In this case the set V0 of boundary points of the regions P (x̂) is enumerated by calculating νt,b = b/|yt| for
all t = 1, . . . , 2T and b = 2, 4, . . . ,M − 2, (which are the nearest neighbor boundaries in the positive half of the
constellation X ′), and storing only those values of (νt,b, t) such that νt,b < λ
ℓ . The set of ordered boundary
points V is again obtained by sorting, and (λmaxℓ , 0) is appended to V as the extent of the search. Recall that (νk, tk)
are the kth elements of V .
The search through the codewords is initialized to the first codeword for the which the line segment passes through,
which is given by x̂(1) = s where s , sgn
. The likelihood update variables are initialized to α = (x̂(1))†y
and β = ‖x̂(1)‖2. To regenerate the optimal codeword, the values of λ and φ are initialized to λ = ν1/2 and
φ = φ1 = 0.
The (k + 1)th codeword considered, x̂(k+1), is calculated from the kth codeword as
(k+1)
+ 2stk . (25)
To update the decision metric we define αk , (x̂
(k))†y and βk , ‖x̂
‖2, and hence L(x̂(k)) = |αk|
2/βk is the
decision metric for the kth codeword considered. The values αk are updated as follows, If tk is odd, then αk is
updated as
αk−1 + 2stk−1y(tk−1+1)/2, tk−1 odd
αk−1 − 2istk−1ytk−1/2, tk−1even.
The values of βk are updated according to
βk = βk−1 + 4stk−1 x̂tk−1 + 4. (27)
If L(x̂(k)) = |αk|
2/βk improves on the best codeword estimate then we store λ = (νk + νk−1)/2 and φ = φℓ.
To start the next line search, y is multiplied by e
2L and the line search is then performed again for the new
value of y. When all line searches have been performed, we calculate x̂opt = NN(λejφy) for the original y.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 17
Pseudo-code is provided in Table V.
The significantly reduced algorithmic complexity compared to the GLRT-optimal algorithm is governed by the
number of line searches and the complexity of each line search. Since there are L phases, each performing a
version of the real-PAM line-search algorithm of Section IV for the case M -ary PAM detection of 2T symbols.
Thus NC 6 L(2T (M/2−1)+1). From Section V-B we have noted that the number of codewords in N (C(X , T ),y)
is of order M2T 2 and thus L must be O(T ) for it to be possible that the majority of N (C(X , T ),y) is enumerated.
Hence, if L is increased proportionally to T , the overall complexity of the algorithm is O(T 2 log T ). Note that
however, the improved computational performance of the algorithm is largely due to being able to choose L small,
which corresponds to avoiding examining a significant number of the x̂ with associated P (x̂) being so small as to
imply that x̂ is not relatively close in angle to the plane YR2. We will see via simulation in Section VII that small
L (e.g. L = 4 for T = 7 16-QAM detection) can achieve near-optimal performance.
VII. SIMULATION RESULTS
We now present simulation results to demonstrate the performance of the new PAM and QAM noncoherent
reduced search lattice-decoding algorithms. Simulations are performed to obtain the codeword error rate (CER) as
a function of SNR for noncoherent detection of 8-ary PAM and 16-ary square QAM. For both case, the simulations
are performed for codeword lengths of T = 3 and 7 over a block Rayleigh fading channel where h is i.i.d. circularly
symmetric complex Gaussian with unit variance. We have assumed that the phase ambiguities have been removed
within each codeword, (for example, by the use of differential encoding [10]).
Figure 3 presents results for 8-ary PAM for the GLRT-optimal plane search algorithm from Section V-C and the
suboptimal phase-estimator plus line-search algorithm from Section VI-A. We also compare with the suboptimal
grid-search algorithm proposed in [20] and the quantization based receiver proposed in [11]. For the grid-search
algorithm we use uniformly spaced channel phase estimates and the channel attenuation estimates are chosen
uniformly from the CDF of the Rayleigh fading channel distribution. For fairness the number of channel attenuation
estimates is adjusted so that the total number of channel estimates was kept equal to the maximum number of
codeword estimates that potentially could be produced by our GLRT-optimal algorithm. Best results are obtained
for choosing the channel phase estimates as 0 and π/2, and hence the kth channel amplitude estimate is given
by |ĥ(k)|2 = − log(1 − k/(1 + ⌈NC/L⌉)). For the quantization-based receiver (QBR) considered in [11], all
possible sequences of (positive) amplitude levels are produced, and the sign of each symbol is then determined by
symbol-wise coherent detection using uniformly spaced channel phase estimates (a channel amplitude estimate is
not required since the signal amplitude is assumed known). For QBR, we again use the channel phase estimates 0
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 18
and π/2.
Figure 4 presents the CER as a function of SNR, for 16-QAM transmission. Results are shown for the GLRT-
optimal QAM algorithm given in Section V-B and the suboptimal algorithm given in Section VI-B. We also compare
with the grid-based algorithm, where best performance for a fixed number of codeword estimates was obtained using
L = 4 channel phase estimates, which we also use for QBR.
For both the PAM and QAM cases we see that the suboptimal line-search algorithms provide negligible per-
formance loss compared to the GLRT-optimal algorithm. For the case of T = 3, where QBR is computationally
possible, there is a noticeable performance loss. As discussed in Section II-B, divisor ambiguities result in a lower
bound on the CER. Expressions for these lower bounds were provided in [25] and are also shown in the figure.
Clearly, for high SNR, both of our GLRT-optimal algorithms and both suboptimal algorithms detection achieve these
bounds for both PAM and QAM. As noted in [11], there is an inherent suboptimality introduced by quantizing
the unbounded channel attenuation by employing a grid-search approach, and hence the performance is clearly
inferior. Also, although QBR achieves near-optimal performance for T = 3, since the complexity of QBR increases
exponentially with T is not possible to produce curves for T = 7.
In Table I we present the relative computational complexities of the algorithms for the simulations in terms of the
average number of codewords examined. The numbers in brackets indicate the number of codewords examined by
the search if the restrictions on the search region provided by Theorems 1 and 2 are not applied (and are therefore
slightly greater than the worst case values given in (22) and (23)). We see that the suboptimal phase-estimator plus
line-search approaches examine far fewer codewords yet obtains near-optimal performance, and that the complexity
of QBR quickly becomes infeasible with increasing T .
GLRT-Optimal Phase Estimator QBR Grid
Reduced Search + Line Search Search
8-PAM T = 3 132.3 (173) 7.3 (10) 128 174
8-PAM T = 7 772.6 (1093) 16.4 (22) 32768 1094
16-QAM T = 3 52.6 (87) 22.9 (28) 108 88
16-QAM T = 7 311.8 (439) 52.9 (60) 8748 440
TABLE I
NUMBER OF CODEWORDS EXAMINED FOR NONCOHERENT PAM AND QAM DETECTION
VIII. REDUCED AMBIGUITY TRANSMISSION
In this section we extend our new noncoherent detection algorithm to pilot assisted transmission (PAT) systems
[6]. Unlike, standard PAT we propose to use the pilot symbol for noncoherent ambiguity resolution, rather than
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 19
simply for channel estimation. We propose to replace the pilot symbol of PAT with a symbol generated in the
following way. Two bits are allocated for resolving the π/2 phase ambiguity of square QAM, and the remaining
bits in the symbol are allocated to parity, remove divisor ambiguities and improve error performance. Therefore,
this scheme has the same data rate as PAT and can be compared directly.
With parity check bits in the codeword, we can now even further reduce the search space of our reduced search
GLRT lattice-decoding algorithm by only considering codewords which satisfy a parity check. This significantly
reduces the ambiguity problem. We will denote this parity-aided transmission scheme as reduced ambiguity (RA)
transmission.
An arbitrarily chosen parity check scheme might reduce the number of divisor ambiguities, however since the
metric (4) has a geometric interpretation it may be possible to design other parity-check schemes which both
resolve ambiguities and optimize performance by providing a minimum angular separation between codewords.
The resolution of ambiguities can be achieved, at least for 16-QAM, by using the following parity-check scheme.
Two parity bits p1, p2 are calculated from the data bits {d1, d2, . . . , d2(T−1)} as follows,
p1 ≡ 1 +
4(T−1)
dt (28)
p2 ≡ 1 +
2(T−1)
d2t (29)
where ≡ denotes equality in GF (2). They are then mapped to the upper right-hand quadrant of the QAM
constellation of the first (pilot) symbol in the codeword as follows: (00) ֌ 1 + j, (01) ֌ 1 + 3j, (11) ֌ 3 + 3j
and (10) ֌ 3 + j. Effectively this means the first two bits of the first symbol of each codeword is chosen such
that x1, x2 > 0, which removes the π/2 phase ambiguity, and the other two bits are parity bits, which in this case
can be shown to completely remove the divisor ambiguities (see Appendix B).
Figure 5 presents the bit error rate (BER) as a function of SNR for detection of 16-QAM transmitted over a
block independent phase-noncoherent AWGN channel. Again we have assumed that the phase ambiguities have
been removed within each codeword. Results are shown for three codeword lengths T = 3, 5, 7. The figure shows
curves for our new RA reduced-search GLRT-optimal algorithm, and compares them to standard PAT. Both schemes
use a single pilot symbol per codeword; which for the RA scheme is generated as described above, and for PAT it
is a symbol which has energy equal to the average energy per symbol. For PAT, the GLRT estimate of the channel
(based on the pilot symbol) is used to perform GLRT-optimal data detection, while for RA lattice decoding we use
our reduced search GLRT-optimal algorithm. Note that for PAT, the BER is independent of the codeword length
T since it is a symbol-by-symbol detection scheme, whereas for RA lattice decoding the BER decreases as T
increases since it is a sequence detection scheme. Clearly our scheme outperforms PAT increasingly with T .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 20
Figure 6 shows the CER for the scenario of Figure 5. This serves to highlight even further the benefit from
our lattice (sequence) decoding approach compared with PAT. For PAT, since bit errors occur independently on a
symbol-by-symbol basis, the CER increases with T . However, for RA lattice decoding the CER decreases. Also the
figure highlights the advantage of using pilot symbols, compared with fully noncoherent transmission, by observing
that the SNR range is significantly lower than for Figures 3 and 4.
IX. CONCLUSION
In this paper we developed polynomial-time lattice-decoding algorithms for noncoherent block detection of PAM
and QAM. Faster suboptimal algorithms for QAM were also presented which have excellent agreement with the
optimal algorithms. A reduced ambiguity transmission scheme was introduced which was shown to outperform pilot
assisted transmission over the phase noncoherent channel.
APPENDIX
A. Strictly Optimal Calculation of Interior Points
For each non-empty region P (x̂), there exists a vertex ν ∈ V (x̂) and small scalars ν+, ν− > 0, such that either
ν+ , ν + [ ν+ 0 ]′ or ν− , ν + [ ν− 0 ]′ is in the interior of P (x̂).
Suppose the first case is true. Now, the line ν+ γ[ 1 0 ]′intersects an edge of the boundary of P (x), and we will
call this intersection point µ. We propose to choose ν+ = γ > 0 so that ν+ is the midpoint of ν and µ. Defining
ut as the tth element of u = Y ν, where Y is defined by the original received vector y, we can calculate ν
follows,
Note that almost surely y
6= 0. Similarly, using the line ν − γ[ 1 0 ]′ we calculate ν− = γ > 0 as
This process will in general always calculate a point in each non-empty P (x̂). However, to avoid calculation
problems we first rotate ν by ym/|ym|, so that the vectors [ ν
+ 0 ]′ and [ ν− 0 ]′ are not parallel to any of the
edges of P (x̂) (e.g. those that are part of S). This rotation is later reversed, so that the points calculated are in the
original coordinates.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 21
B. Removal of Ambiguities in 16-ary QAM
In this section we show that the proposed RA pilot symbol approach (using parity checks, as discussed in Section
VIII) totally removes both the phase and divisor ambiguities otherwise inherent in a noncoherent detection system
(as discussed in Section II-A).
We start by recalling that the proposed parity scheme involves calculating the parity bits from the data bits dt for
t = 1, . . . , 4T as follows.
p1 ≡ 1 +
4(T−1)
dt p2 ≡ 1 +
2(T−1)
d2t (30)
where ≡ denotes equality in GF (2).
The data and parity bits are then mapped to the symbols as shown in Table II, where we recall from the definition
in (7) that x2t−1 = Re {xt} and x2t = Im {xt}.
d2t−1d2t xt
00 −3
01 −1
p1p2 x1 (pilot symbol)
00 1 + i
01 1 + 3i
11 3 + 3i
10 3 + i
TABLE II
MAPPING OF DATA AND PARITY BITS.
Since x1 is constrained to have positive real and imaginary components, the phase ambiguity has been removed.
It remains to show that all divisor ambiguities have also been removed.
To do this, we first define the associates of a Gaussian integer g to be the elements of the set A(g) =
{g, gi,−g,−gi}. We also denote A(g)T to be a codeword of length T composed of only elements of A(g).
For 16-QAM, it can be easily shown that a necessary condition for a divisor ambiguity to exist is that there exists
codewords x(1) ∈ A(g1)
T , x(2) ∈ A(g2)
T for some g1, g2 ∈ X , {1 + i, 3 + 3i, 3 + i, 1 + 3i} such that g1 6= g2.
For a codeword x and some g ∈ X , we define N1, N2, N3 and N4 as the number of occurrences in a codeword
of each of the four possible rotations of g in the codeword, that is g, gi,−g and −gi respectively. Noting that the
phase ambiguity has been removed (since x1 is constrained to have positive real and imaginary components), a
sufficient condition for two codewords to be unambiguous is that there exists some t, such that the tth symbols
from the two codewords are in different quadrants of the complex plane. It follows then, that a sufficient condition
for two codewords to be unambiguous is that they do not have the same values of N1 to N4.
We now use this property on N1 to N4 to show that for arbitrary T , it is not possible for two ambiguous
codewords x(1) ∈ A(g1)
T , x(2) ∈ A(g2)
T , to satisfy the parity check (30) for any g1, g2 ∈ X such that g1 6= g2.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 22
We consider each g ∈ X (where we have previously defined X = {1+ i, 3+ 3i, 3+ i, 1+ 3i}) in turn, showing
that all codewords x ∈ A(g)T that satisfy the parity check, are distinguishable in phase from all parity-satisfying
codewords considered up to that point. For 16-QAM this process involves considering the four Gaussian integers
1 + i, 3 + 3i, 3 + i and 1 + 3i in turn, as detailed in the following four cases.
Define xD to be the data codeword component of x, i.e. x = [x2 . . . xT ]
• Case xD ∈ A(1 + i)T−1:
In this case, we show that there does not exist any x ∈ A(1 + i)T that satisfies the parity check. Using
Table II, the bits (d4ℓ−3 . . . d4ℓ) are mapped to the symbol xℓ = x2ℓ−1 + ix2ℓ ∈ x
D in the following way:
(1111) ֌ 1 + i, (0111) ֌ −1 + i, (0101) ֌ −1 − i and (1101) ֌ 1 − i. Clearly from (29), p2 ≡ 1, and
therefore the pilot symbol x1 will be either 1 + 3i or 3 + 3i. It follows that x /∈ A(1 + i)
• Case xD ∈ A(3 + 3i)T−1:
In this case, we show the conditions under which a codeword x ∈ A(3 + 3i)T satisfies the parity check. The
associated bit mappings are (1010) ֌ 3 + 3i, (0010) ֌ −3 + 3i, (0000) ֌ −3− 3i and (1000) ֌ 3 − 3i.
Clearly, p1 ≡ 1 +N2 +N4 and p2 ≡ 1. Therefore,
1 + 3i, if (p1p2) = (01) i.e. if N2 6≡ N4,
3 + 3i, if (p1p2) = (11) i.e. if N2 ≡ N4.
Furthermore it follows that x ∈ A(3 + 3i)T only if N2 ≡ N4.
• Case xD ∈ A(3 + i)T−1:
In this case, we show the conditions under which a codeword x ∈ A(3 + i)T satisfies the parity check, and
show that under these conditions there does not exist any ambiguous codeword from A(3+3i)T , i.e. from the
previous case. The bit mappings are (1011) ֌ 3+i, (0110) ֌ −1+3i, (0001)֌ −3−i and (1100) ֌ 1−3i.
In this case, p1 ≡ 1 + N1 + N3 and p2 ≡ 1 + N1 + N2 + N3 + N4 ≡ 1 + T − 1 ≡ T . If T is odd, then
p2 ≡ 1 and therefore x1 ∈ {1 + 3i, 3 + 3i} and therefore x /∈ A(3 + i)
T . If T is even then p2 ≡ 0 and
p1 ≡ 1 +N1 +N3 ≡ N2 +N4. Therefore
3 + i if (p1p2) = (10) i.e. if N2 6≡ N4,
1 + i, if (p1p2) = (00) i.e. if N2 ≡ N4.
It follows that x ∈ A(3 + i)T only if N2 6≡ N4 and T is even. Recall that in the previous case, valid
parity satisifying codewords only occurred if N2 ≡ N4. Therefore an ambiguity will not occur between two
codewords x ∈ A(3 + i)T and x(1) ∈ A(3 + 3i)T since they will be distinguishable in phase.
• Case xD ∈ A(1 + 3i)T−1:
In this case, we show the conditions under which a codeword x ∈ A(1+3i)T satisfies the parity check, and show
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 23
that under these conditions there does not exist any ambiguous codeword from either A(3+3i)T or A(3+ i)T ,
i.e. from the previous two cases. The bit mappings are (1110) ֌ 1+3i, (0011)֌ −3+ i, (0100)֌ −1− 3i
and (1001) ֌ 3 − i. Here, p1 ≡ 1 + N1 + N3 and p2 ≡ T . If T is even, then p2 ≡ 0 and therefore
x1 ∈ {1 + i, 3 + i} and no ambiguity occurs. If T is odd then p1 ≡ 1 +N2 +N4 and p2 ≡ 1. Therefore,
1 + 3i if (p1p2) = (01) i.e. if N2 6≡ N4,
3 + 3i, if (p1p2) = (11) i.e. if N2 ≡ N4.
It follows that x ∈ A(1 + 3i)T only if N2 6≡ N4 and T is odd. Clearly, these conditions are different to those
to the previous two cases and therefore no ambiguities exist.
REFERENCES
[1] T. L. Marzetta and B. M. Hochwald, “Capacity of a mobile multiple-antenna communication link in Rayleigh flat fading,” IEEE Trans.
Inform. Theory, vol. 45, no. 1, pp. 139–157, Jan. 1999.
[2] L. Zheng and D. N. C. Tse, “Communication on the Grassmann manifold: A geometric approach to the noncoherent multiple-antenna
channel,” IEEE Trans. Inform. Theory, vol. 48, pp. 359–383, Feb. 2002.
[3] B. Hassibi and B. M. Hochwald, “How much training is needed in multiple-antenna wireless links?” IEEE Trans. Inform. Theory, vol. 49,
no. 4, pp. 951–963, Apr. 2003.
[4] R.-R. Chen, R. Koetter, D. Agrawal, and U. Madhow, “Joint demodulation and decoding for the noncoherent block fading channel: A
practical framework for approaching Shannon capacity,” IEEE Trans. Commun., vol. 51, pp. 1676–1689, Oct. 2003.
[5] J. K. Cavers, “An analysis of pilot symbol assisted modulation for Rayleigh fading channels,” IEEE Trans. Veh. Technol., vol. 40, no. 4,
pp. 686–693, 1991.
[6] L. Tong, B. M. Sadler, and M. Dong, “Pilot-assisted wireless transmissions,” IEEE Signal Processing Mag., vol. 21, pp. 12–25, Nov. 2004.
[7] R. Raheli, A. Polydoros, and C.-K. Tzou, “Per-survivor processing: A general approach to MLSE in uncertain environments,” IEEE Trans.
Commun., vol. 43, no. 2/3/4, pp. 354–364, Feb 1995.
[8] L. M. Davis, I. B. Collings, and P. Hoeher, “Joint MAP equalization and channel estimation for frequency-selective and frequency-flat
fast-fading channels,” IEEE Trans. Commun., vol. 49, no. 12, pp. 2106–2114, December 2001.
[9] C. N. Georghiades, “Blind carrier phase acquisition for QAM constellations,” IEEE Trans. Commun., vol. 45, no. 11, pp. 1477–1486, Nov.
1997.
[10] W. E. Weber, “Differential encoding for multiple amplitude and phase shift keying systems,” IEEE Trans. Commun., vol. 26, pp. 385–391,
Mar. 1978.
[11] D. Warrier and U. Madhow, “Spectrally efficient noncoherent communication,” IEEE Trans. Inform. Theory, vol. 48, pp. 652–668, Mar.
2002.
[12] L. Lampe, R. Schober, V. Pauli, and C. Windpassinger, “Multiple-symbol differential sphere decoding,” IEEE Trans. Commun., vol. 53,
pp. 1981–1985, Dec. 2005.
[13] K. L. Clarkson, W. Sweldens, and A. Zheng, “Fast multiple-antenna differential decoding,” IEEE Trans. Commun., vol. 49, no. 2, pp.
253–261, Feb. 2001.
[14] C. Ling, W. H. Mow, K. H. Li, and A. C. Kot, “Multiple-antenna differential lattice decoding,” IEEE J. Sel. Areas Commun., vol. 23,
no. 9, pp. 1821–1829, Sept. 2005.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 24
[15] D. J. Ryan, I. V. L. Clarkson, and I. B. Collings, “Detection error probabilities in noncoherent channels,” in Proc. IEEE Int. Symp. on
Inform. Theory (ISIT), Adelaide, Australia, Sept. 2005, pp. 617–621.
[16] V. Pauli and L. Lampe, “On the complexity of sphere decoding for MSDD,” in Proc. IEEE Int. Symp. on Inform. Theory (ISIT), Seattle,
WA, July 2006, pp. 932–936.
[17] E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, “Closest point search in lattices,” IEEE Trans. Inform. Theory, vol. 48, no. 8, pp. 2201–2214,
Aug. 2002.
[18] K. M. Mackenthun Jr., “A fast algorithm for multiple-symbol differential detection of MPSK,” IEEE Trans. Commun., vol. 42, pp. 1471–
1474, Feb./Mar./Apr. 1994.
[19] W. Sweldens, “Fast block noncoherent decoding,” IEEE Comms. Letters, vol. 5, no. 4, pp. 132–134, Apr. 2001.
[20] I. Motedayen-Aval and A. Anastasopoulos, “Polynomial-complexity noncoherent symbol-by-symbol detection with application to adaptive
iterative decoding of turbo-like codes,” IEEE Trans. Commun., pp. 197–207, Feb. 2003.
[21] ——, “Polynomial-complexity, adaptive symbol-by-symbol soft-decision algorithms with application to non-coherent detection of LDPCC,”
in Proc. IEEE Int. Conf. on Communications (ICC), New York, USA, Apr. 2002, pp. 1677–1681.
[22] ——, “Polynomial complexity ML sequence and symbol-by-symbol detection in fading channels,” in Proc. IEEE Int. Conf. on
Communications (ICC), Anchorage, Alaska, May 2003, pp. 2718–2722.
[23] H. L. Van Trees, Detection, Estimation, and Modulation Theory: Part I. John Wiley & Sons, 1968.
[24] Y.-C. Wong, “Differential geometry of Grassmann manifolds,” Proc. Nat. Acad. Sci. USA, vol. 47, pp. 589–594, 1967.
[25] D. J. Ryan, I. V. L. Clarkson, and I. B. Collings, “Blind detection of PAM and QAM in fading channels,” IEEE Trans. Inform. Theory,
vol. 52, pp. 1197–1206, Mar. 2006.
[26] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. Cambridge, MA, USA: McGraw-Hill
Higher Education, 2001.
[27] M. Moeneclaey and G. de Jonghe, “ML-oriented NDA carrier synchronization for general rotationally symmetric signal constellations,”
IEEE Trans. Commun., pp. 2531–2533, Aug. 1994.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 25
1 begin
2 s := sgn y; // Store sign of each yt
3 y := s ◦ y; // Make each yt positive
4 Bmax := M + T − 2;
5 m := argmaxt {yt};
6 λmax := (M + 2T − 2)/|ym|; // Search region: 0 < λ < λ
7 V0 := ∅; // Calculate and store P (x) boundary points
8 for t := 1 to T do
9 for all b ∈ {2, 4, . . . ,M − 2} do
10 ν := b/yt;
11 if ν < λmax ;
12 V0 := {V, (ν, t)};
13 else break;
14 end for all;
15 end for;
16 V := sort(V0); // Sort V0 in ascending order of ν
17 V := {V, (λmax, 0)};
18 x̂ := [ 1 1 . . . 1 ]′; // Initialize data estimate
19 α := x̂′y; // Initialize likelihood terms
20 β := ‖x̂‖2;
21 L := α2/β;
22 λ := V(1, 1)/2;
23 for k := 1 to |V| − 1 do // Iteratively examine likelihoods
24 t := V(k, 2);
25 α := α + 2yt; // Update likelihood terms
26 β := β + 4x̂t + 4;
27 x̂t := x̂t + 2; // Update x
28 if α2/β > L // If better x found
29 L := α2/β; // Update likelihood
30 λ := (V(k, 1) + V(k + 1, 1))/2; // Store point in P (x̂)
31 end if;
32 end for;
33 return x̂opt := s ◦ NN(λy);
TABLE III
M -ARY REAL-PAM NONCOHERENT LATTICE DECODING ALGORITHM
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 26
1 begin
2 m := arg maxt {|yt|};
3 y := (y∗m/|ym|)y; // Rotate y so that ym is purely real
4 Bmax := M + 2T − 2;
5 λmax := Bmax/|ym|; // Search boundary (Thm. 2).
6 x̂best := NN((ǫ+ iǫ)y); // Codeword near origin
7 Lmax := L(x̂best); // L’hood L(x) ,
/ ‖x‖2
8 B := {2, 4, . . . ,M − 2}; // Positive NN boundaries
// Calculate only intersection points (i.e. vertices) in
// first quadrant using (21) by reducing number of
// NN boundaries B1,B2 and then rotating.
9 for t := 1 to 2T − 1 do
10 B1 := B;
11 if t ∈ {2m − 1, 2m} then B1 := {B1, B
max};
12 for t′ := t + 1 to 2T do
13 B2 := B;
14 if t′ ∈ {2m − 1, 2m} then B2 := {B2, B
max};
15 S :=
Y t′,1 Y t′,2
; // Matrix in (21)
16 for all b1 ∈ B1
17 for all b2 ∈ B2
// Calculate intersection point;
18 ν := Real-To-Complex(S[ b1 b2 ]
19 ν := Rotate-To-First-Quadrant(ν);
20 for all s ∈ {−1, 1}
21 λ := ν + s(ǫ + iǫ); // Point in some partition
// Check that λ is in reduced search region
22 if 0 < Re {λ} < λmax and
0 6 Im {λ} < λmax then
23 x̂ := NN(λy); // Calculate NN
24 if L(x̂) > Lmax // If better x found
25 x̂best := x̂; // Update codeword estimate
26 Lmax := L(x̂); // Update likelihood
27 end if;
28 end if;
29 end for all;
30 end for all;
31 end for all;
32 end for;
33 end for;
34 return x̂opt := x̂best;
TABLE IV
M2-ARY SQUARE QAM NONCOHERENT LATTICE DECODING ALGORITHM
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 27
1 begin
2 L := 0; // Initialize likelihood
3 λmax0 := (M + 2T − 2)/maxt |yt|;
4 for ℓ = 1 to L then
5 // Search region: 0 < λ < λmax (Theorem 2)
6 λmax := λmax0 /min
˛cos ℓπ
˛sin ℓπ
7 V0 = ∅; // Calculate and store P (x) boundary points
8 for t = 1 to 2T then
9 for all b ∈ {2, 4, . . . ,M − 2} then
10 ν := b/|y
11 if ν < λmax ;
12 V0 := {V0, (ν, t)};
13 else break;
14 end for all;
15 end for;
16 V := sort(V0); // Sort V0 in ascending order of ν
17 V := {V, (λmax, 0)};
18 s := sgn{y};
19 x̂ := s; // Initialize data estimate
20 α := x̂†y; // Initialize likelihood terms
21 β := ‖x̂‖2;
22 if α2/β > L // If better x found
23 L := α2/β; // Update likelihood
24 λ := V(1)/2;
25 φ := ℓπ/(2L);
26 end if;
27 for k := 1 to |V| − 1 do // Iteratively examine likelihoods
28 t := V(k, 2);
29 if t′ is odd then
30 α := α + 2sty(t+1)/2;
31 else
32 α := α − 2istyt/2;
33 end if
34 β := β + 4s
35 x̂t := x̂t + 2st;
36 if |α|2/β > L // If better x found
37 L := |α|2/β; // Update likelihood
38 λ := (V(k, 1) + V(k + 1, 1))/2; // Store point in P (x̂)
39 φ := ℓπ/(2L);
40 end if;
41 end for;
42 y := ye
2L ; // Rotate y for next line search
43 end for;
44 return x̂opt := NN(λejφy);
TABLE V
SUBOPTIMAL M2-ARY SQUARE QAM MULTIPLE LINE-SEARCH NONCOHERENT DETECTION ALGORITHM
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 28
0 2 4 6 8 10 12
Fig. 1. Illustration of noncoherent detection of 8-ary PAM for T = 2. The dots are all the (two dimensional) PAM codewords in the positive
quarter-plane, and the angled line is yR, for an example received codeword y. The shaded regions indicate the nearest neighbor regions
of points which need to be searched. That is, they are in N (C(X , T ),y) (from Property 1), and they correspond to values of λ less than
λmax = (M + T − 2)/maxt |yt| = M/maxt |yt| (from Theorem 1).
−6 −4 −2 0 2 4 6
 = Real{λ}
Fig. 2. Plot of partitions P (x̂) on the R2 plane for 16-ary QAM detection of a sequence of length T = 3 for the received vector y =
[ −0.1076 − 0.4728i, −0.7002 − 0.0968i, −1.1228 + 0.4955i ]. The bold square corresponds to the search boundary S .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 29
20 30 40 50 60 70
SNR (dB)
New GLRT−Optimal Reduced−Search
Phase−Estimator + Line Search
Grid Search [20]
QBR (exponential complexity)
Ambiguity lower bound
Fig. 3. Plot of Codeword Error Rate (CER) as a function of SNR for an 8-ary PAM system.
20 30 40 50 60 70
SNR (dB)
New GLRT−Optimal Reduced−Search
Phase−Estimator + Line Search (Section VI.B)
Grid Search [20]
QBR (exponential complexity)
Ambiguity Lower Bound
Fig. 4. Plot of Codeword Error Rate (CER) as a function of SNR for a 16-ary square QAM system.
IEEE TRANSACTIONS ON SIGNAL PROCESSING, ACCEPTED TO APPEAR (ACCEPTED NOV. 2006) 30
10 12 14 16 18 20 22
SNR (dB)
RA T=3
RA T=5
RA T=7
Fig. 5. Comparison of Bit Error Rate (BER) as a function of SNR for 16-QAM for PAT versus RA transmission.
10 12 14 16 18 20 22
SNR (dB)
PAT T=7
PAT T=5
PAT T=3
RA T=3
RA T=5
RA T=7
Fig. 6. Comparison of Codeword Error Rate (CER) as a function of SNR for 16-QAM for PAT versus RA transmission.
	Introduction
	System Model
	Signal Model
	Detection
	Reduced Search Space
	PAM Detection For Real-Valued Fading Channels
	Limiting the Search Space
	PAM Algorithm
	GLRT-Optimal QAM Detection For Complex-Valued Fading Channels
	Limiting the Search Space
	QAM Algorithm
	PAM Over Complex Channels
	Suboptimal Algorithms for Complex-Valued Fading Channels
	Suboptimal PAM algorithm
	Suboptimal QAM algorithm
	Simulation Results
	Reduced Ambiguity Transmission
	Conclusion
	Appendix
	Strictly Optimal Calculation of Interior Points
	Removal of Ambiguities in 16-ary QAM
	References
