TO APPEAR IN IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-I: REGULAR PAPERS

1

VLSI Designs for Joint Channel Estimation and
Data Detection in Large SIMO Wireless Systems

arXiv:1709.07860v1 [cs.IT] 22 Sep 2017

Oscar Castañeda, Tom Goldstein, and Christoph Studer

Abstract—Channel estimation errors have a critical impact on
the reliability of wireless communication systems. While virtually
all existing wireless receivers separate channel estimation from
data detection, it is well known that joint channel estimation
and data detection (JED) significantly outperforms conventional
methods at the cost of high computational complexity. In this
paper, we propose a novel JED algorithm and corresponding
VLSI designs for large single-input multiple-output (SIMO)
wireless systems that use constant-modulus constellations. The
proposed algorithm is referred to as PRojection Onto conveX hull
(PrOX) and relies on biconvex relaxation (BCR), which enables us
to efficiently compute an approximate solution of the maximumlikelihood JED problem. Since BCR solves a biconvex problem
via alternating optimization, we provide a theoretical convergence
analysis for PrOX. We design a scalable, high-throughput VLSI
architecture that uses a linear array of processing elements
to minimize hardware complexity. We develop corresponding
field-programmable gate array (FPGA) and application-specific
integrated circuit (ASIC) designs, and we demonstrate that PrOX
significantly outperforms the only other existing JED design in
terms of throughput, hardware-efficiency, and energy-efficiency.
Index Terms—FPGA and ASIC designs, joint channel estimation and data detection (JED), large single-input multiple-output
(SIMO) wireless systems, biconvex relaxation (BCR).

I. I NTRODUCTION
IRELESS communication with a large number of
antennas at the base-station (BS) will play a major
role in fifth-generation (5G) systems. By equipping the BS
with hundreds or thousands of antenna elements, large wireless
systems enable fine-grained beamforming and, hence, improved
spectral-efficiency within each cell compared to traditional
communication systems that use a small number of BS
antennas [2]–[7]. All these advantages come at significantly
increased signal-processing complexity at the BS [8], which
necessitates the development of high-performance transceiver
algorithms that scale well to large BS array sizes and can be
implemented in very-large scale integration (VLSI) circuits at
low costs and in an energy-efficient manner.

W

A. The Importance of Accurate Channel State Information
Due to the fine-grained nature of beamforming in such
large wireless systems, the acquisition of accurate channel
O. Castañeda and C. Studer are with the School of Electrical and Computer
Engineering, Cornell University, Ithaca, NY; e-mail: oc66@cornell.edu,
studer@cornell.edu; web: http://vip.ece.cornell.edu
T. Goldstein is with the Department of Computer Science, University of
Maryland, College Park, MD; e-mail: tomg@cs.umd.edu
A short version of this paper summarizing the PrOX FPGA design has been
presented at the IEEE Int. Symp. on Circuits and Systems (ISCAS) 2017 [1].
The MATLAB simulator for PrOX used in this paper is available on GitHub:
https://github.com/VIP-Group/PrOX.

state information (CSI) at the BS is critical for reliable, highthroughput data transmission. In particular, accurate channel
state information is not only required in the uplink (to
coherently detect data transmitted from the users to the BS),
but also required for beamforming or precoding in the downlink
(to precisely focus the transmit energy towards the users
and to mitigate multi-user interference). However, the fading
nature of wireless channels as well as pilot contamination,
i.e., channel training that may be contaminated by pilots or
data transmission of users communicating in adjacent cells [2],
render the acquisition of accurate CSI without a significant
channel-training overhead a difficult task.
Most proposed large wireless systems rely on time-division
duplexing (TDD) and perform pilot-based channel training
during the uplink phase [3], [5]. It is, however, well known
that the quality of CSI can be improved significantly by
joint channel estimation and data detection (JED), which is
capable of approaching the performance of idealistic systems
with perfect CSI [9], [10]. While a few JED algorithms have
been proposed for traditional, small-scale wireless systems [9]–
[16], their computational complexity is typically high and not
much is known about their efficacy for systems with hundreds
or thousands of antennas. Moreover, with the exception of
the recently proposed VLSI designs in [17], no hardware
implementations for JED have been described in the literature.
B. Contributions
In this paper, we propose a novel, computationally efficient
and near-optimal JED algorithm for large SIMO wireless systems, and we develop corresponding very-large scale integrated
(VLSI) designs. Our contributions are summarized as follows:
• We use biconvex relaxation (BCR) [18] to develop PRojection Onto conveX hull (PrOX), a novel algorithm that
achieves near-optimal JED performance at low complexity.
• We theoretically analyze the convergence of PrOX, which
solves a biconvex problem via alternating optimization.
• We introduce an approximation that significantly reduces
the preprocessing complexity of PrOX at virtually no loss
in terms of error-rate performance.
• We provide simulation results that showcase the robustness
of PrOX to a broad range of system parameters.
• We develop a scalable VLSI architecture for PrOX that
uses a linear array of processing elements (PEs) to achieve
high-throughput at low hardware complexity.
• We show reference FPGA and ASIC implementation
results, and compare our designs to that of the recentlyreported JED implementations in [17].

2

TO APPEAR IN IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-I: REGULAR PAPERS

Our results demonstrate that PrOX provides near-optimal JED at
significantly lower complexity than existing reference designs.
C. Related Relevant Results

theoretical convergence analysis. Section IV details the VLSI
architecture for PrOX. Section V shows error-rate performance
and VLSI implementation results, and compares PrOX to
existing FPGA and ASIC designs. We conclude in Section VI.

While a considerable number of algorithms and VLSI designs
II. S YSTEM M ODEL AND ML-O PTIMAL JED
have been proposed for small- and large-scale multi-antenna
We now introduce the considered SIMO system model and
wireless systems that separate channel estimation and data
develop
the associated ML-JED problem.
detection (see, e.g., [8], [17], [19] and the references therein),
only a few of results have been proposed for JED. Spheredecoding (SD) algorithms have been proposed to perform A. System Model
exact maximum-likelihood (ML) JED in SIMO and MIMO
We study a (potentially large) SIMO wireless uplink system
systems that use a small number of time slots [9]–[12], [20],
in which a single-antenna user transmits data over K + 1
[21]. Unfortunately, the complexity of SD methods quickly
time slots to a BS with B antennas. We consider the standard
becomes prohibitive for larger dimensional problems [22], [23]
block-fading, narrow-band1 channel model with the following
and approximate linear methods, which are widely used for
input-output relation [9]–[11], [20]:
coherent data detection in massive MIMO systems [8], cannot
be used for JED (see Section II-B for the reasons). Very recently,
Y = hsH + N.
(1)
a handful of approximate JED algorithms have been proposed
B×(K+1)
contains the B-dimensional
for large wireless systems [17], [24]–[26]. To the best of our Here, the matrix Y ∈ C
knowledge, reference [17] describes the only VLSI design of a receive vectors for the K + B1 time slots, i.e., Y =
, . . . , yK+1 ] with yk ∈ C and k = 1, 2, . . . , K + 1,
JED algorithm reported in the open literature. While this design [y1 , y2B
(assumed to
achieves near-ML-JED performance, the algorithm relies on h ∈ C is the unknown SIMO channel vector K+1
contains
semidefinite relaxation (SDR), which lifts the dimensionality of remain constant over the K +1 time slots), s ∈ O
the
transmitted
data
symbols
for
all
K
+
1
time
slots,
and
the problem to the square of the number of time slots causing
B×(K+1)
N
∈
C
models
i.i.d.
complex
circularly-symmetric
high hardware complexity. In contrast to all these results, PrOX
avoids lifting while achieving near-ML-JED performance and Gaussian noise with variance N0 per entry. In the remainder
can be implemented efficiently in VLSI, even for scenarios of the paper, we assume constant-modulus constellations, i.e.,
|s| = σ for all s ∈ O and a fixed σ > 0.
that operate with a large number of time slots.
Another line of related work investigates data detection Remark 1. The SIMO case is relevant in many rural dealgorithms that are robust to imperfect CSI [27], [28]. The ployment scenarios in which only a few users are active
idea is to statistically model channel estimation errors and at a time [30]. The assumption of having constant-modulus
to solve suitably adapted data detection problems. The re- constellations limits our results to low-rate modulation schemes,
sulting algorithms, however, (i) do not achieve the error-rate such as BPSK and PSK constellations. While the (multi-user)
performance of JED as they are not taking into account all MIMO case and higher-order QAM modulation schemes would
the received information (i.e., from training and data symbols be of interest in more general deployment scenarios, the
received over multiple time slots) and (ii) do not improve the associated ML-JED problem is significantly more challenging
channel estimate itself—the latter is critical in TDD systems to solve, and requires different, more complex, and complicated
that perform beamforming in the downlink using acquired CSI algorithms; see, e.g., [12], [21] for more details—we are
in the uplink [2]–[5]. In contrast, we propose JED algorithms planning to address this scenario in the future.
that (i) approach optimal error-rate performance as they jointly
process all received information and (ii) generate improved
B. Joint Channel Estimation and Data Detection (JED)
channel estimates that can be used for beamforming.
Let h be a deterministic—but unknown—channel vector
with unknown prior statistics. Then, one can formulate the
D. Notation
following ML-JED problem [11]:
Lowercase and uppercase boldface letters stand for column
 JED
ŝ , ĥ = arg min
Y − hsH F .
(2)
vectors and matrices, respectively. For the matrix A, the
K+1
B
s∈O
, h∈C
Hermitian is AH and the kth row and `th column entry is Ak,` .
For the vector a, the kth entry is ak . The Euclidean norm of a, This problem aims at simultaneously finding an estimate for
the Frobenius norm, and the spectral norm of A are denoted the transmitted data vector s and the channel vector h. We
by kak2 , kAkF , and kAk, respectively. The real and imaginary emphasize that there is a phase ambiguity between both output
vectors of ML-JED in (2). Specifically, if ŝJED ejφ ∈ OK+1 for
parts of the vector a are <(a) and =(a), respectively.
φ ∈ [0, 2π), then ĥejφ is also a valid solution to (2). In order to
E. Paper Outline
The rest of the paper is organized as follows. Section II
describes the system model as well as ML-optimal JED.
Section III introduces the PrOX algorithm and provides a

1 An extension to wideband systems that use OFDM [29] is straightforward
as the flat-fading model in (1) remains to be valid per active sub-carrier. An
extension of our methods to channels with multi-user interference or wideband
channels with inter-symbol interference is, however, not straightforward; see
also Remark 1 for more details.

O. CASTAÑEDA ET AL.

3

avoid this phase ambiguity, one can either transmit information
as phase differences among the entries in the vector s, which
is known as differential signaling [24], or fix the phase of at
least one entry in the transmit vector s. As in [17], we set the
first entry of the transmit vector to a fixed constellation point
š ∈ O and exploit this knowledge at the receiver.

where α > 0 is a suitably chosen regularization parameter. To
ensure that the problem in (4) is convex in the vector q, the
parameter α must be larger than the maximum eigenvalue of
the Gram matrix G = YH Y, i.e., α > kYH Yk.
We next relax the finite-alphabet constraint to the convex
hull CO of the set O given by [34]


|O|
|O|
Remark 2. While this approach resembles that of conventional,
X

X
pilot-based data transmission, we emphasize that ML-JED
CO =
αi si | (αi ∈ R+ , ∀i) ∧
αi = 1 ,


is fundamentally different. In traditional, pilot-based data
i=1
i=1
transmission, a small number of known training symbols are
used to generate channel estimates, which are then used during with si , i = 1, . . . , |O|. For example, the convex hull for BPSK
the detection of the data symbols. In contrast, ML-JED uses all constellations CBPSK is the line along the real axis in [−1, +1];
received symbols, i.e., pilots and data symbols, to improve the the convex hull CQPSK for QPSK is the square with the four
quality of CSI. We also note that ML-JED as in (2) jointly solves constellation points as corners. By relaxing O to the convex
for the transmitted data vector s and the channel vector h; this hull CO , we arrive at the following relaxed ML-JED problem:
is in contrast to JED methods that alternate between channel
minimize − kYqk22 + αkq − sk22 .
K+1
estimation and data detection (see, e.g., [13]–[16]) and for
s∈CO
,q∈CK+1
which ML-JED optimality can, in general, not be guaranteed.
For the above problem, it is likely to obtain a solution that is
Since we assumed the entries in s to be constant-modulus, inside the convex hull. We are, however, interested in finding
the ML-JED problem in (2) can be rewritten in the following, solutions that lie at the boundary of the convex hull CO as
more compact form [11]:
the original constellation points in O lie at the boundary. To
this end, we include a norm constraint that promotes large
ŝJED = arg max kYsk2 ,
(3)
values
in s, with the goal of pushing the entries of s towards
K+1
s∈O
the boundary of the convex hull. This leads to the final BCR
and the associated channel estimate is given by ĥ = formulation of the ML-JED problem:
YŝJED /kŝJED k22 . We note that the optimization problem in (3)
ŝBCR =
arg min
−kYqk22 + αkq − sk22 − βksk22 . (5)
resembles the famous MaxCut problem that is known to be NPK+1
K+1
s∈CO ,q∈C
hard [31]. Indeed, general problems of the form (3) are known
to be NP-hard with respect to randomized reductions, even Here, β is a suitably chosen algorithm parameter that satisfies
when only approximate solutions are sought [32]. Nevertheless, β < α, which ensures that the optimization problem is biconvex
for a small number of time slots K + 1, the problem in (3) in the vectors s and q. In words, for a fixed vector q, the
can be solved exactly and at low average complexity using problem in (5) is convex in s, and vice versa.
sphere decoding (SD) methods [11]. For a large number of
time slots, however, SD is known to entail prohibitively high
complexity [33]. Furthermore, linear approximations are useless B. Alternating Optimization
for JED, since the entries of s would grow without bound when
We solve the BCR problem in (5) using alternating minirelaxing the finite-alphabet constraint s ∈ OK+1 to the complex mization, i.e., we keep one of the vectors fixed while solving
numbers s ∈ CK+1 . As a consequence, the design of non-linear for the other. The resulting iterative procedure is given by
and low-complexity algorithms is necessary to enable JED for
q(t) = arg min −kYqk22 + αkq − s(t−1) k22
(6)
practical SIMO systems that use a large number of time slots.
q∈CK+1

(t)

s

III. P ROX: PROJECTION O NTO CONVE X HULL

= arg min αkq(t) − sk22 − βksk22 ,

(7)

K+1
s∈CO

We now develop a novel algorithm to approximately solve the where t = 1, 2, . . . , t
max is the iteration counter.
ML-JED problem in (3) using biconvex relaxation (BCR) [18],
We initialize the above algorithm with s(0) = š(G1,1 )−1 g1c ,
a recent framework to solve large semidefinite programs in
where g1c is the first column of G, and š ∈ O is the fixed
computer vision. The resulting algorithm is referred to as PRosymbol transmitted in the first time slot and known at the
jection Onto conveX hull (PrOX), requires low computational
receiver.
complexity, and achieves near-ML-JED performance.
Since the problem in (5) is biconvex in s and q, both
of the above steps are convex and can be solved optimally.
Furthermore, each of these optimization problems turns out
A. Biconvex Relaxation (BCR) of the ML-JED Problem
to have a closed form solution. Concretely, we obtain the
We start from (3) and include a regularization term that
following two-step PrOX algorithm:
K+1
forces the transmit vector s ∈ O
to be close to a copy
q ∈ CK+1 that is relaxed to the complex numbers as follows:
q(t) = (I − α−1 G)−1 s(t−1)
(8)
minimize

s∈O K+1 ,q∈CK+1

− kYqk22 + αkq − sk22 ,

(4)

s(t) = proxC K+1 (θq(t) ),
O

(9)

4

TO APPEAR IN IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-I: REGULAR PAPERS

α
> 0, I is the identity matrix, and the proximal
where θ = α−β
operator [35] is defined as

always lie on the boundary of the convex hull CO ; a proof is
given in Appendix B.

proxC K+1 (v) = arg min kv − sk22 .

Theorem 2. Let the conditions of Theorem 1 hold and further
assume α > β > 0. Then, any non-zero stationary point of (5)
lies along the boundary of the set CO .

O

(10)

K+1
s∈CO

This proximal operator is the element-wise orthogonal projection of the vector v = θq(t) onto the convex hull CO around the
constellation set O. For BPSK, the proximal operator in (10)
is given by proxCBPSK (vb ) = max {min {<(vb ), +1} , −1}, i.e.,
the projection onto the real line in [−1, +1]; for QPSK, (10)
corresponds to applying the same operation, independently, to
both <(vb ) and =(vb ). In the case of (9), we have v = θq(t)
with θ > 0 and hence, the proximal operator in (10) projects a
scaled version of q(t) onto the convex hull of the constellation
set CO —this is why we dub our algorithm PRojection Onto
conveX hull (PrOX).
C. Convergence Theory of PrOX

Remark 3. Theorem 1 and Theorem 2 do not guarantee PrOX
to find a global minimizer to the ML-JED problem (3), but
rather stationary (or saddle) points that lie on the boundary of
the convex hull—although we often observe global minimizers
in practice (cf. Section V-A). The development of stronger
results that provide conditions for which PrOX finds the optimal
solution is challenging and left for future work.
D. Simplifying the Preprocessing Stage
For a large number of time slots K + 1, computing the
b = (I − α−1 G)−1 in (8) results in high
matrix inverse G
preprocessing complexity. We now propose an approximate
method that substantially reduces the preprocessing complexity
for PrOX at a negligible loss in terms of error-rate performance.
Let kGk < α for any consistent matrix norm k · k. Then,
we have the following Neumann series expansion [36]:

We now show that the PrOX algorithm is well behaved,
even though it solves a biconvex problem using alternating
optimization. More specifically, we begin by establishing that
the iterates q(t) and s(t) generated by PrOX converge to
stationary points of the objective function in (5), provided that
∞
X
the algorithm parameters α and β are chosen appropriately.
(α−1 G)k .
(11)
(I − α−1 G)−1 =
We then show that these stationary points lie on the boundary
k=0
K+1
of the convex hull CO
, which implies that our biconvex As put forward in [8] for data detection in massive MIMO
relaxation is reasonably tight. In what follows, we denote the systems, one can approximate a matrix inverse by truncating
objective function of PrOX in (5) as
the series expansion to the first two terms, which is
( 1
β
K+1
α
2
2
2
− 2 kYqk2 + 2 kq − sk2 − 2 ksk2 , if s ∈ CO
(I − α−1 G)−1 ≈ I + α−1 G.
(12)
f (q, s) =
∞, otherwise.
Evidently, the expression on the right-hand side does not require
1
Note that the factors of 2 do not affect the solution of PrOX. the computation of a matrix inverse, which significantly reduces
At an optimal solution, the sub-gradients of f with respect the preprocessing complexity. More specifically, the matrix
to both s and q should be zero. Because s(t) is computed by to be inverted in the left-hand side of (12) is of dimension
minimizing f with respect to s(t) , we already know that the (K + 1) × (K + 1). The complexity (in terms of the number
sub-gradient of f with respect to s(t) contains zero. We can of real-valued multiplications) of an explicit matrix inversion
thus measure the optimality of the iterates by examining only using, e.g., the Cholesky factorization scales with (K + 1)3
∇q f, the gradient of f with respect to q. We now show that and exhibits stringent data dependencies when implemented
this gradient vanishes for a large number of iterations t; the in VLSI; see [8] for more details on the computational
complexity of Cholesky-based matrix inversion and a VLSI
proof is given in Appendix A.
design. Hence, for a large number of time slots K, the
Theorem 1. Suppose that the parameters α and β satisfy approximate preprocessing method in (12) yields significant
α > kGk and α > β. Then, the PrOX algorithm in (8) and (9) savings in terms of hardware complexity.
converges in the gradient sense, i.e.,
We have the following result that bounds the error of the
(t) (t)
approximation
in (12); the proof is given in Appendix C.
lim ∇q f (q , s ) = 0.
t→∞

Furthermore, any limit point of the sequence of iterates is a
stationary point.

Theorem 3. Let α > kGk. Then, the error of the approximation in (12) is bounded by

kα−1 Gk2
The PrOX algorithm is founded on the idea of replacing the
k(I − α−1 G)−1 − (I + α−1 G)k ≤
.
1 − kα−1 Gk
discrete constellation O with its convex hull CO . This results
in a biconvex problem that is easily solved without resorting
This result implies that if kGk is smaller than α, then
to expensive discrete programming or lifting-based methods. the approximation error will be small. In other words, the
However, in using a biconvex relaxation, there is a risk of approximation error will depend on the parameter α, which we
finding a minimizer that lies somewhere in the interior of the can tune in practice for optimal performance. In Section V-A,
convex hull CO , far away from any of the constellation points. we will show that PrOX with this approximation results in
We now provide conditions for which this situation does not excellent error-rate performance while significantly reducing
b
happen. The following theorem shows that minimizers of (5) the complexity compared to using the original matrix G.

O. CASTAÑEDA ET AL.

5

E. Hardware-Friendly Variant of PrOX
As a last step, we now modify the PrOX algorithm in (8)
and (9) to make it more hardware friendly. Since the BS is
assumed to know the first entry of s, there is no need to apply
the algorithm to this particular entry. Consequently, we force
(t)
the entry s1 to be š at the end of each iteration.
b exhibits, in general, a large dynamic range
The matrix G
for different system configurations and channel realizations.
To facilitate fixed-point design, we divide all of its elements
by a constant γ > 0, so that the entries of the resulting matrix
are close to one in absolute value. This scaling procedure
requires us to introduce a new vector q̃ = γ −1 q, resulting in
the following modified PrOX algorithm:
b (t−1)
q̃(t) = γ −1 q(t) = γ −1 Gs
(t)

s

(13)

(t)

(t)

= proxC K+1 (θγ q̃ ) = proxC K+1 (%q̃ ),
O

O

(14)

where % = θγ. With these two modifications, we arrive at the
hardware-friendly version of PrOX summarized as follows:
Algorithm 1 (Hardware-Friendly PrOX). Fix the algorithm parameters % > 0 and α > kGk. Precompute the
b using one of the following expressions:
matrix G
b = γ −1 (I − α−1 G)−1
G
b = γ −1 (I + α−1 G),
G

(15)
(16)

architecture consists of a linear array of N = K + 1 processing
elements (PEs), each one dedicated to computing an entry of
the vectors s and q̃. To execute Algorithm 1, each PE has three
b
key components: (i) a G-matrix
memory, (ii) a complex-valued
multiply-accumulate (MAC) unit, and (iii) a projection unit (see
b
the right side of Figure 1). The G-matrix
memory comprises
two memories to store the real and imaginary parts of ĝkr , i.e.,
b We assume that G,
b which is
the kth row of the matrix G.
the result of either (15) (for PrOX) or (16) (for APrOX), was
computed and loaded in the memories during a preprocessing
step. The MAC unit of the kth PE is used to sequentially
compute the kth row of the matrix-vector product (MVP) in
(t)
Step (17) of Algorithm 1, resulting in q̃k (see Section IV-B
for the details). Finally, the projection unit of the kth PE
computes the kth entry of Step (18) of Algorithm 1, i.e., it
(t)
(t)
(t)
uses q̃k to acquire sk . Since s1 = š, the first PE does
not need the previous three key components. Instead, PE 1
only contains two multiplexers and flip-flops that store the
predefined constellation point š in order to implement Step (19)
of Algorithm 1. The implementation of all other PEs is identical
and uses the aforementioned three key components. For these
PEs, the hard-output estimates in Step (20) are extracted directly
from the sign bits at the outputs of the projection units.
B. Matrix-Vector Product (MVP)

Before explaining the operation details of the proposed VLSI
architecture, we focus on the main computation of PrOX: the
MVP operation in Step (17) of Algorithm 1. A straightforward
b (t−1) using a linear array of
way
for computing q̃(t) = Gs
(t)
(t−1)
b
q̃ = Gs
(17)
PEs is depicted in Figure 2(a) for N = K + 1 = 3. This
s(t) = proxC K+1 (%q̃(t) )
(18)
architecture computes q̃(t) sequentially and on a column-byO
PN
c (t−1)
(t)
column basis, i.e., it evaluates q̃(t) =
in a
k=1 ĝk sk
s1 = š
(19)
sequential manner over k = 1, . . . , N clock cycles. Here, ĝkc
b While such an approach is
At the end of iteration tmax , compute hard-output estimates
represents the kth column of G.
of the transmitted signals as follows:
conceptually simple, it requires a centralized vector memory
which suffers from a high fan-out at its output (highlighted
(t )
ŝk = arg min |sk max − s|, k = 1, 2, . . . , K + 1. (20)
with red color in Figure 2(a)). More concretely, the vector
s∈O
memory output must be connected to N = K + 1 MAC units,
eventually becoming the critical path for systems with a large
In what follows, we will use PrOX to refer to Algonumber of time slots K +1. While wire pipelining at the output
rithm 1 with exact preprocessing as in (15) and approximate
of the vector memory could be used to mitigate the fan-out, we
PrOX (APrOX) to refer to Algorithm 1 with approximate
propose an alternative solution that avoids this issue altogether.
preprocessing as in (16). We also note that α > 0 and % > 0
Consider the MVP architecture depicted in Figure 2(b). In
are algorithm parameters that can be tuned via numerical
this architecture, we replace the centralized vector memory
simulations to improve the error-rate performance.
by a set of registers: each register is associated with a PE
and contains an entry of the vector s(t−1) . Furthermore, the
IV. VLSI A RCHITECTURE
registers are chained together in a cyclic manner, forming a
We now propose a VLSI architecture for PrOX, which shift register that enables all entries of s(t−1) to reach all the
exhibits high regularity and enables us to achieve high PEs in a round-robin fashion. Then, each PE only needs to
throughput at low hardware complexity.
access the correct entry of ĝkr to ensure that the accumulator of
their MAC unit contains the correct MVP result after N clock
cycles. By following this approach, each register only drives
A. Architecture Overview
the next register in the cycle and one of the MAC unit inputs,
Figure 1 shows the VLSI architecture for PrOX in a
regardless of N , hereby completely avoiding the fanout issue.
system that uses QPSK2 modulation. At a high level, our
We henceforth call this architecture input-cyclic MVP, which
builds the core component of the PrOX architecture shown in
2 For BPSK modulation, the VLSI architecture shown in Figure 1 can be
simplified as data-path elements used to compute = (s) can be removed.
Figure 1 and detailed in the next subsection.
and initialize s(0) = š(G1,1 )−1 g1c . Then, for every
iteration t = 1, 2, . . . , tmax , compute the following steps:

6

TO APPEAR IN IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-I: REGULAR PAPERS

Complex-valued MAC unit

Projection unit

PE
X
Memory

PE

+

+
-

+

+

+

+

+

X
Memory

X

PE
X

PE

Fig. 1. VLSI architecture of PrOX. Left: linear array of K + 1 processing elements (PEs), which enables us to achieve high throughput at low complexity.
Right: architecture details of the kth PE, which mainly consists of a complex-valued multiply-accumulate (MAC) unit and a projection unit.

b
We note that the reading pattern of the G-matrix
memory
for each PE corresponds to simply accessing the entries of ĝkr
in order. However, in contrast to the conventional architecture
in Figure 2(a), reading can start from any element and wraps
around after reaching the end of ĝkr . Instead of using address
generation logic required to implement this behavior, we store
b
a cyclically-permuted version of ĝkr in the G-matrix
memory
of each PE. By doing so, each PE simply needs to access
b
its G-matrix
memory in regular order starting from the first
address, as it would be done in the conventional architecture
depicted in Figure 2(a).
C. Operation Details of the PrOX Architecture
To implement the input-cyclic MVP architecture, the entries
b matrix for the kth PE are stored in the following
of the G
b k,k ; the
way: The first address of the PE memory contains G
b
second address contains Gk,k+1 , and so on. For example, in
the case shown in Figure 2(b), the second PE would have its
b
b 2,2 , G
b 2,3 , G
b 2,1 }.
G-matrix
entries organized as follows: {G
b k,k
In the first clock cycle, the kth PE has access to both G
(t−1)
(t−1)
b
and sk
, so it can compute the Gk,k sk
product, and store
the result in its accumulator. At the same time, this PE passes
its current s(t−1) entry to the subsequent PE in the chain, i.e.,
the (k − 1)th PE. Passing the current s(t−1) entry to the next
PE will be performed in all PEs during all the clock cycles of
the MVP computation. An example of this first clock cycle is
b 2,2 s2
shown in Figure 2(b), where the second PE computes G
and passes the s2 value to the first PE, so that the first PE has
access to s2 in the second clock cycle.
(t−1)
In the second clock cycle, the kth PE receives sk+1 from
the (k + 1)th PE, the previous PE in the array. As a result, the
b k,k+1 s(t−1) and accumulate it with the
kth PE can compute G
k+1
previous product. For example, in the second clock cycle of
Figure 2(b), the second PE receives s3 from the third PE and
b 2,3 s3 and add it with G
b 2,2 s2 .
is hence able to compute G
(t−1)
In the third clock cycle, the kth PE receives sk+2 from the
(t−1)
(k + 1)th PE. Note that, while the sk+2 value was initially in

the (k+2)th PE, the (k+2)th PE previously passed this value to
the (k + 1)th PE. Then, the kth PE has the necessary operands
to continue executing its complex-valued MAC operation. To
clarify this aspect, let us examine the third clock cycle in
b 2,1 and s1 to finish
Figure 2(b): the second PE has access to G
its computation. While the second PE received s1 from the
third PE, the third PE received s1 from the first PE in the
previous clock cycle.
This example illustrates how the exchange of values between
PEs enables each entry of s(t−1) to circulate through the linear
array of PEs. In the case of the example in Figure 2(b), a
complete circulation of all values in the shift registers takes
three clock cycles. In general, after K + 1 clock cycles, all PEs
have had access to all the entries of s(t−1) and used them to
compute their respective entry of q̃(t) . During this procedure,
the first PE (which is implemented differently than the other
PEs) executes the same procedure: it passes š to the (K + 1)th
PE during the first clock cycle, and in the subsequent clock
cycles sends the s(t−1) entry received from the second PE to
the (K + 1)th PE. As the MAC units contain three pipeline
stages, two clock cycles are required to flush the pipeline.
Hence, the MVP operation in Step (17) of Algorithm 1 is
computed in only K + 3 clock cycles.
We now describe the operation of the projection unit
shown on the right side of Figure 1, which implements
s(t) = proxC K+1 (%q̃(t) ). For QPSK, the projection unit of
O
the kth PE consists of two identical modules: one module
(t)
takes q̄ = <(q̃k ) as its input, while the other module takes
(t)
q̄ = =(q̃k ) as its input. For BPSK, only the module with an
(t)
input of q̄ = <(q̃k ) is required. The function of each module
is to compute %q̄ and to clip its value in case it exceeds an
absolute value of 1. In other words, each module determines
if %q̄ is smaller than −1, larger than +1, or in-between these
numbers, and outputs −1, +1, or %q̄, respectively. As % > 0,
to determine if %q̄ ≥ +1, one can also check q̄ ≥ +1/% or,
equivalently, if q̄ − 1/% ≥ 0, which can be extracted from the
sign bit of q̄ − 1/%. Analogously, to determine if %q̄ < −1, one

X

+

X

+
+

X

X

+
+

Vector Memory

Vector Memory

+

X

X

+

+
+

+

+
+

Vector Memory

X

Cycle 3

Cycle 2

7

Cycle 1

O. CASTAÑEDA ET AL.

X

X

+

+
+

+

+
+

X

+

Cycle 3

Cycle 2

Cycle 1

(a) Conventional column-by-column matrix-vector product

X

+

X

+

+

X

+

X

+

X

+

+

X

+

X

+

+
+

+
+

+
+

X

+
+

(b) Proposed input-cyclic matrix-vector product for PrOX
Fig. 2. Processing details of the matrix-vector product (MVP) operation: (a) conventional approach that proceeds on a column-by-column basis and leads to
high memory fan-out; (b) proposed input-cyclic method that reduces fan-out.

can also check q̄ + 1/% < 0, which can be extracted from the
sign bit of q̄ + 1/%. As a result, each module takes its input q̄
and computes q̄ − 1/% and q̄ + 1/%. Using the sign bits of these
two results, the module can select if the output will be −1,
+1, or %q̄. The quantity %q̄ is computed in parallel with the
calculation of q̄ + 1/% and q̄ − 1/%, which reduces the critical
path. By restricting the parameter % to be a power of two, the
multiplication can be carried out with inexpensive arithmetic
shifts. The projection unit uses one clock cycle to complete
its operation, but it can start only after the K + 3 clock cycles
used by the complex MAC unit. After the projection unit has
(t)
finished, the new sk will be available at the inputs of the
complex-valued MAC unit of the kth PE, ready to start a new
iteration. Consequently, each PrOX iteration requires a total
number of K + 4 clock cycles.

D. Implementation Details
We now provide the remaining implementation details,
including the fixed-point parameters as well as memory
considerations for our FPGA and ASIC designs.

1) Fixed-Point Parameters: To minimize area and power
consumption, and to maximize the throughput, we deploy fixedpoint arithmetic in our design. Specifically, our architecture
uses 6 bit signed fixed-point values for representing the s(t)
b 12 bit
entries, with 3 fraction bits. For the elements of G,
signed fixed-point values are used, with 11 fraction bits. While
18 bit values are generated at the outputs of the multipliers in
the complex-valued MAC unit, only 15 bits are used in the
subsequent adders and accumulators (of which 11 are fraction
bits). The adder and subtractor that receive the outputs from
the multipliers do not saturate, but rather wrap-around which
reduces area and delay. In contrast, the accumulator adders
saturate. The outputs of the complex-valued MAC unit are also
15 bit signed fixed-point values with 11 fraction bits. In the
projection unit, the −1/% and +1/% quantities are represented
using 12 bit signed fixed-point numbers with 11 fraction bits,
and are added to the outputs of the complex MAC unit using
15 bit saturating adders. The outputs of these adders are used
to determine the output of the projection unit. Furthermore,
for all the considered system configurations, % > 1. As % is
restricted to be a power of two, a multiplication with % is

8

TO APPEAR IN IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-I: REGULAR PAPERS

implemented by an arithmetic left shift. The number of shifts i.e., the downlink channel is the transpose of the uplink channel.
is encoded with a 4 bit number. Only the 6 most significant Hence, we can use the estimated channel acquired in the
bits of the shifted value are taken into the multiplexer of the uplink for MRC-based beamforming in the downlink. We
projection unit, as the output of this multiplexer will become the observe similar trends as for the uplink shown in Figure 3. In
next iterate s(t+1) . We note that these fixed-point parameters particular, PrOX, APrOX, and TASER all achieve near-MLare sufficient to achieve near-floating-point performance; see JED performance. MRC and MRC that uses the estimated
Figures 3 and 4 in Section V-A for corresponding symbol data vector sMRC to compute a re-trained channel estimate
error-rate performance results.
according to ĥ = YŝMRC /kŝMRC k22 (referred to as “RT”) is
b
2) Memory Considerations: For the FPGA designs, the G- able to approach our algorithms by 2 dB and 4 dB, respectively.
matrix memory is implemented using look-up tables (LUTs) Hence, we conclude that JED also significantly improves the
as distributed RAM, i.e., no block RAMs have been used. For reliability of data transmission in the downlink.
b
3) Performance vs. Complexity Trade-offs: Figure 5 shows
the ASIC designs, the G-matrix
memory is implemented using
latch arrays as described in [37]; these memories are built from the trade-offs between the ASIC throughput of PrOX and
standard cells and simplify automated design synthesis, without AProX, and the minimum signal-to-noise ratio (SNR) required
to achieve 1% SER in the uplink for SIMO systems with
a significant area penalty compared to SRAM macrocells.
K = 16 time slots and a varying number of BS antennas.
As
a reference, we include the performance of MRC with
V. R ESULTS
perfect
CSIR and that of the optimal ML-JED detector. We
We now show error-rate performance results as well as FPGA
observed
that by increasing the number of PrOX and APrOX
and ASIC implementation results. We also compare our design
iterations
tmax , the mean squared error (MSE) of the channel
to the only other existing JED design reported recently in [17].
estimate is reduced monotonically and the desired SER is
achieved at a lower SNR at the expense of reduced throughput.
A. Error-Rate Performance
Clearly, PrOX outperforms APrOX for a small number of
1) Uplink Data Detection: Figure 3 shows uplink symbol iterations; this implies that the preprocessing approximation
error-rate (SER) simulation results for PrOX and APrOX, both proposed in Section III-D entails a small performance loss
running tmax = 5 iterations. The simulation results are obtained when a small number of iterations is used. Note that for BPSK
from 50, 000 Monte-Carlo trials in a B = 16 BS antenna modulation, tmax = 2 PrOX iterations are typically sufficient
SIMO system with K = 16 time slots. We consider both to reach near-ML-JED performance at an ASIC throughput of
an i.i.d. flat Rayleigh block-fading channel model as well as 338 Mb/s per PrOX instance. For QPSK, 3 PrOX iterations are
a line-of-sight (LoS) channel with a spherical wave model sufficient at an ASIC throughput of 451 Mb/s.
and a linear BS antenna array with λ/2-wavelength spacing
Remark 4. For all provided simulation results, we have
as described in [38]. As reference points, we also include
assumed perfect synchronization and a transmission free of
the performance of maximum ratio combining (MRC)-based
impairments or pilot contamination3 . Hence, the provided
data detection with both perfect receive-side CSI (denoted by
simulation results may not be representative for other system
“CSIR”) and with conventional channel estimation, optimal MLconfigurations or more realistic communication scenarios. The
JED detection using the sphere-decoding algorithm put forward
MATLAB simulator for PrOX used in this paper is available on
in [12], and the recently proposed TASER (short for Triangular
GitHub: https:// github.com/ VIP-Group/ PrOX; this enables the
Approximate SEmidefinite Relaxation) algorithm [17] running
interested readers to investigate such aspects in more detail.
for 10 iterations. Note that MRC with perfect CSIR is optimal
for these scenarios. However, the assumption of perfect CSIR
cannot be realized in practice and one must resort to channel B. FPGA and ASIC Implementation Results
estimation (CHEST), which entails a performance loss of
To demonstrate the efficacy of PrOX, we now provide FPGA
more than 4 dB at 1% SER. PrOX and AProX achieve similar implementation results on a Xilinx Virtex-7 XC7VX690T and
error rate performance. Furthermore, both of our algorithms ASIC implementation results in a 40 nm CMOS technology.
significantly outperform MRC with CHEST and approach We implemented for different array sizes N ∈ {5, 9, 17, 33} in
near-ML-JED performance but, in stark contrast to ML-JED Verilog on register transfer level (RTL) and hence, our FPGA
data detection, at very low computational complexity. Our and ASIC designs support near-ML-JED for K ∈ {4, 8, 16, 32}
algorithms also outperform TASER, especially for QPSK time slots, respectively. We also provide a comparison to the
modulation; see Section V-B for a hardware comparison. We only other existing FPGA and ASIC designs for JED proposed
also show the fixed-point performance of the VLSI designs of in the literature [17].
PrOX. The markers of PrOX and APrOX correspond to the
1) FPGA Implementation Results: Our FPGA implemenfixed-point performance of golden models that exactly match tation results were obtained using the Xilinx Vivado Design
the outputs of our VLSI designs, whereas the curves correspond Suite, and are summarized in Table I. As expected, the resource
to MATLAB floating-point performance—evidently, our fixed- utilization scales nearly linearly with the array size N . For the
point VLSI designs exhibit virtually no implementation loss.
3 A straightforward model for pilot contamination would be to add inde2) Downlink Beamforming: Figure 4 shows downlink SER
pendent Gaussian noise to the received signals—such a model would simply
simulation results for PrOX and APrOX with the same system reduce the operating SNR. Without more accurate models, however, it is not
and algorithm parameters. We assume channel reciprocity [5], clear what the SNR reduction would be in a practical cellular system.

O. CASTAÑEDA ET AL.

9

100

10−1

10−2

10−3
−12

−10
−8
−6
−4
−2
Average SNR per receive antenna [dB]

10−1

10−2

10−3
−10

0

100

MRC (CSIR)
MRC
ML-JED
TASER
PrOX
APrOX

Uncoded symbol error rate (SER)

MRC (CSIR)
MRC
ML-JED
TASER
PrOX
APrOX

Uncoded symbol error rate (SER)

Uncoded symbol error rate (SER)

100

(a) BPSK, Rayleigh fading

−8 −6 −4 −2
0
2
4
Average SNR per receive antenna [dB]

10−1

10−2

10−3
−10

6

MRC (CSIR)
MRC
ML-JED
TASER
PrOX
APrOX

(b) QPSK, Rayleigh fading

−8 −6 −4 −2
0
2
4
Average SNR per receive antenna [dB]

6

(c) QPSK, LoS

Fig. 3. Uncoded uplink symbol-error rate (SER) for a SIMO uplink with B = 16 BS antennas and transmission over K = 16 time slots. PrOX and APrOX
achieve near-optimal SER performance (close to that of MRC detection with perfect CSIR) and exhibit a performance similar to ML-JED. At a SER of 0.1%,
TASER [17] entails a 1 dB SNR loss for QPSK, while MRC with conventional CHEST suffers more than 3 dB SNR loss for BPSK and QPSK. For PrOX and
APrOX, the curves show the floating-point performance whereas the markers show the fixed-point performance of our golden models.

100

10−1

10−2

10−3
−12

−10
−8
−6
−4
−2
Average SNR per receive antenna [dB]

10−1

10−2

10−3
−10

0

100

MRC (CSIR)
MRC
MRC (RT)
ML-JED
TASER
PrOX
APrOX

Uncoded symbol error rate (SER)

MRC (CSIR)
MRC
MRC (RT)
ML-JED
TASER
PrOX
APrOX

Uncoded symbol error rate (SER)

Uncoded symbol error rate (SER)

100

(a) BPSK, Rayleigh fading

−8 −6 −4 −2
0
2
4
Average SNR per receive antenna [dB]

10−1

10−2

10−3
−10

6

MRC (CSIR)
MRC
MRC (RT)
ML-JED
TASER
PrOX
APrOX

(b) QPSK, Rayleigh fading

−8 −6 −4 −2
0
2
4
Average SNR per receive antenna [dB]

6

(c) QPSK, LoS

Fig. 4. Uncoded downlink symbol-error rate (SER) for a SIMO uplink with B = 16 and K = 16. Beamforming with the channel estimate from PrOX, APrOX
and TASER [17] achieve near-optimal SER performance (close to that of perfect CSIR) and a performance similar to that of ML-JED. At a SER of 0.1%, MRC
with conventional CHEST suffers a 4 dB SNR loss for QPSK; retraining the channel with the estimated uplink data vector can reduce this loss, as in MRC
(RT). For PrOX and APrOX, the curves show the floating-point performance whereas the markers show the fixed-point performance of our golden models.

500
400
300

PrOX
B = 16
B = 32
B = 64
B = 128
APrOX
B = 16
B = 32
B = 64
B = 128

1

1 11

1

1

1,400

1 1

1,200

200
100

1,000
800
600

PrOX
B = 16
B = 32
B = 64
B = 128
APrOX
B = 16
B = 32
B = 64
B = 128

1

1

1 1

1

1

1,400

1

1,200
ASIC throughput [Mb/s]

600

ASIC throughput [Mb/s]

ASIC throughput [Mb/s]

700

400
200

0
−18 −16 −14 −12 −10 −8 −6 −4
Min. SNR [dB] required to achieve 1% SER

(a) BPSK, Rayleigh fading

−2

0
−14

1,000
800
600

PrOX
B = 16
B = 32
B = 64
B = 128
APrOX
B = 16
B = 32
B = 64
B = 128

1

1 1

1 1

1

1 1

400
200

−12 −10 −8
−6
−4
−2
Min. SNR [dB] required to achieve 1% SER

(b) QPSK, Rayleigh fading

0

0
−14

−12 −10 −8
−6
−4
−2
Min. SNR [dB] required to achieve 1% SER

0

(c) QPSK, LoS

Fig. 5. ASIC throughput vs. performance trade-off of PrOX and APrOX for K = 16 time slots. Vertical solid lines represent MRC with CSIR; vertical dashed
lines represent ML-JED performance. The numbers next to the markers correspond to the number of iterations tmax . The throughput was obtained from post
place-and-route ASIC implementation results. We can see that PrOX requires a smaller number of iterations than APrOX to achieve ML-JED performance.

10

TO APPEAR IN IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-I: REGULAR PAPERS

TABLE I
FPGA IMPLEMENTATION RESULTS OF P ROX ON A X ILINX V IRTEX -7
XC7VX690T FOR DIFFERENT P ROX ARRAY SIZES
Array size (N = K +1)
Time slots (K = N −1)
Slices
LUTs
FFs
DSP48s
Max. clock freq. [MHz]
Min. latency [cycles]
Max. throughputa [Mb/s]
Power estimateb [W]
a Assuming
b Statistical

N =5
K =4

N =9
K =8

N = 17
K = 16

N = 33
K = 32

327
990
515
16
358
8
358
0.45

658
1 991
989
32
341
12
454
0.47

1 491
4 818
1 953
64
297
20
475
0.79

3 018
9 861
3 857
128
240
36
426
1.14

(a) N = 5
(b) N = 9

QPSK modulation; for BPSK, the throughput is halved.
power estimation at max. clock freq. and 1.0 V supply voltage.
(d) N = 33

(c) N = 17
TABLE II
C OMPARISON OF JED FPGA DESIGNS FOR A QPSK, B = 128, K = 8
LARGE -SIMO SYSTEM ON A X ILINX V IRTEX -7 XC7VX690T
Detection algorithm
Error-rate performance
Iterations tmax

PrOX
Near ML-JED
3

TASER [17]
Near ML-JED
3

Slices
LUTs
FFs
DSP48s
Clock frequency [MHz]
Latency [clock cycles]
Throughput [Mb/s]
Power estimatea [W]

658 (0.61 %)
1 991 (0.46 %)
989 (0.11 %)
32 (0.89 %)
341
12
151
0.47

4 350 (4.02 %)
13 779 (3.18 %)
6 857 (0.79 %)
168 (4.67 %)
225
72
50
1.30

75 841
3.09

3 629
26.0

Throughput/LUTs
Energy/bit [nJ/b]
a Statistical

power estimation at max. clock freq. and 1.0 V supply voltage.

N ∈ {5, 9, 17} arrays, the critical path of PrOX is in the PEs’
projection unit; for the largest N = 33 array, the critical path
is in the distribution of the control signals.
Table II compares PrOX with TASER [17], which have been
implemented on the same FPGA for a SIMO system with
B = 128 BS antennas and communication through K = 8
time slots. PrOX requires significantly fewer resources and
lower power than TASER, while achieving a substantially
higher throughput. This makes our design superior to TASER
in terms of both hardware-efficiency (measured in throughput
per FPGA LUTs) and energy per bit. Concretely, PrOX is 20×
more hardware-efficient and 8× more energy-efficient than
TASER for the considered scenario.
2) ASIC Implementation Results: Our ASIC post placeand-route implementation results summarized in Table III
were obtained using Synopsys DC and IC compilers with
a 40 nm CMOS standard-cell technology. Figure 6 shows the
corresponding ASIC layouts. For the N ∈ {5, 9} arrays, the
critical path of PrOX is in the PEs’ projection unit; for N = 17,
the critical path is in the multipliers of the MAC unit and, for
the largest N = 33 array, the critical path is in the address
generation logic and readout circuitry of the ĝkr memories.
Table IV compares PrOX with TASER [17], which have

Fig. 6. Layouts of the PrOX ASIC designs for array sizes N ∈ {5, 9, 17, 33}.
The PEs of each design were colored differently. One can observe a nearly
linear increase in silicon area depending on the array size N = K + 1.

TABLE III
ASIC IMPLEMENTATION RESULTS OF P ROX IN 40 NM CMOS FOR
DIFFERENT ARRAY SIZES

Array size (N = K +1)
Time slots (K = N −1)

N =5
K =4

N =9
K =8

N = 17
K = 16

N = 33
K = 32

Core area [µm2 ]
Core density [%]
Cell area [GE]
Max. clock freq. [MHz]
Min. latency [cycles]
Max. throughput [Mb/s]
Power estimatea [mW]

26 419
77.24
28 922
976
8
976
10

53 361
77.39
58 522
942
12
1 256
18

132 903
72.96
137 428
846
20
1 354
38

303 722
76.38
328 753
695
36
1 235
58

a Post

place-and-route power estimation at max. clock freq. and 1.1 V.

TABLE IV
C OMPARISON OF JED ASIC S FOR A QPSK, B = 128, K = 8
LARGE -SIMO SYSTEM IN 40 NM CMOS
Detection algorithm
Error-rate performance
Iterations tmax

PrOX
Near ML-JED
3

TASER [17]
Near ML-JED
3

Core area [µm2 ]
Core density [%]
Cell area [GE]
Max. clock freq. [MHz]
Latency [clock cycles]
Throughput [Mb/s]
Power estimatea [mW]

53 361
77.39
58 522
942
12
418
18

482 677
68.89
471 238
560
24
125
87

7 153

279

43

697

Throughput/cell
area [b/(s×GE)]
Energy/bit [pJ/b]
a Post

place-and-route power estimation at max. clock freq. and 1.1 V.

O. CASTAÑEDA ET AL.

11

been implemented on the same 40 nm CMOS technology for a constellation sets [12], [21], they are either computationally
SIMO system with B = 128 and K = 8. Similar to the complex or exhibit a considerable loss with respect to the
FPGA case, the PrOX ASIC designs require significantly optimal ML-JED performance. The development of efficient
fewer resources and lower power than the TASER ASIC JED algorithms that can be implemented as high-throughput
designs, while achieving a substantially higher throughput. VLSI designs for large (multi-user) MIMO systems with
Concretely, PrOX is 25× more hardware-efficient (in terms of arbitrary constellations is part of ongoing work.
the throughput per cell area) and 16× more energy-efficient
than TASER for the considered scenario.
A PPENDIX A
We also note that PrOX exhibits a similar (for BPSK) or
P ROOF OF T HEOREM 1
better (for QPSK) SER performance than TASER, while using
We need a closed form expression for the gradient so that
fewer algorithm iterations; see Figures 3 and 4 for the associated we can say something about its convergence. We have
SER results. However, while PrOX is only suitable for JED in
∂q f (q(t) , s(t) ) = −YT Yq(t) + α(q(t) − s(t) ).
large SIMO systems, TASER is also able to perform near-ML
data detection in coherent massive multi-user MIMO systems From the optimality condition for the minimization step (6),
that use conventional pilot-based channel training [17]. Hence, we have
the error-rate performance and hardware complexity advantages
0 = −YT Yq(t) + α(q(t) − s(t−1) )
of PrOX over TASER come at the cost of reduced flexibility.
= −YT Yq(t) + α(q(t) − s(t) ) + α(s(t) − s(t−1) )

= ∂q f (q(t) , s(t) ) + α(s(t) − s(t−1) ),
Remark 5. While a plethora of VLSI designs exist for data detection in coherent small-scale and massive (multi-user) MIMO
and thus
systems that separate channel estimation from data detection
(see [8], [19], [22], [23], [39]–[46] and the references therein),
∂q f (q(t) , s(t) ) = α(s(t−1) − s(t) ).
(21)
TASER is the only other SIMO-JED VLSI design that has been
Now that we have a simple representation for the gradient,
described in the literature [17]. Furthermore, low-complexity
we can bound its norm. Note that f is strongly convex in q
linear methods that are commonly used for conventional (multiwith parameter α − kYT Yk, and so
user) MIMO data detection cannot be used in the JED scenario
(as briefly discussed in Section II-B). Hence, we limited our
α − kYT Yk
kq − qs k22
(22)
f
(q,
s)
−
f
(q
,
s)
≥
s
comparisons in Table II and Table IV to PrOX and TASER.
2
VI. C ONCLUSIONS

where qs = arg minq f (q, s). Likewise, f is strongly convex
in s with parameter α − β, and so

α−β
f (q, s) − f (q, sq ) ≥
ks − sq k22
(23)
We have proposed a novel joint channel estimation and data
2
detection (JED) algorithm, referred to as PRojection Onto
where sq = arg mins f (q, s).
conveX hull (PrOX). Our algorithm builds upon biconvex
If we choose q = q(t−1) and s = s(t−1) in (22), then
relaxation (BCR) [18], which enables near-maximum-likelihood
qs = q(t) and we have
(ML) JED performance at low computational complexity for
large SIMO systems with constant-modulus constellations. We
f (q(t−1) , s(t−1) ) − f (q(t) , s(t−1) )
have provided theoretical convergence guarantees for PrOX
α − kYT Yk (t−1)
and introduced an approximation that significantly reduces the
≥
kq
− q(t) k22 . (24)
2
preprocessing complexity. To demonstrate the effectiveness
of our algorithm, we have proposed a VLSI architecture Similarly, from (23) we get
that consists of a linear array of processing elements (PEs).
α − β (t−1)
f (q(t) , s(t−1) ) − f (q(t) , s(t) ) ≥
ks
− s(t) k22 .
Our architecture enables high-throughput near-ML-JED at low
2
silicon area and power consumption. We have provided FPGA Adding these two inequalities yields
and ASIC implementation results, which demonstrate that
(t−1) (t−1)
,s
) − f (q(t) , s(t) )
PrOX significantly outperforms the only other existing JED f (q
design [17] in terms of hardware- and energy-efficiency as well
α − β (t−1)
α − kYT Yk (t−1)
kq
− q(t) k22 +
ks
− s(t) k22 .
≥
as error-rate performance. More generally, PrOX constitutes a
2
2
first step towards hardware accelerators that are able to find Summing from t = 1 to t = T, and observing that the
approximate solutions to problems that resemble the famous summation on the left telescopes, we get
MaxCut problem in a hardware-efficient manner.
f (q(0) , s(0) ) − f (q(T ) , s(T ) )
(25)
There are many avenues for future work. An extension of
T
PrOX to compute soft-outputs in the form of log-likelihood raT
X α − kY Yk
≥
kq(t−1) − q(t) k22
(26)
tios (LLRs) is part of ongoing work. Furthermore, a theoretical
2
t=1
error-rate performance analysis of PrOX is a challenging open
α − β (t−1)
research problem. Finally, while some algorithms exist for JED
+
ks
− s(t) k22 .
in the MIMO case and for general (non-constant modulus)
2

12

TO APPEAR IN IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-I: REGULAR PAPERS

Because the iterates remain bounded and f is continuous, the
left-hand side of (25) is bounded from above. We can conclude
that ks(t−1) − s(t) k → 0, and from (21), we see that the
residuals converge as well.
Finally, because the sub-gradients of f depend continuously
on s and q, any limit point of the sequence of iterates must
have zero sub-gradients, and is thus a stationary point.
A PPENDIX B
P ROOF OF T HEOREM 2
Let (q∗ , s∗ ) denote a non-zero stationary point of f that
lies in the interior of CO . Such a point satisfies the first-order
conditions
∗

T

∗

∗

−Y Yq + α(q − s ) = 0
∗

∗

(28)

α−β ∗
α s .

Plugging this result

α(s − q ) − βs = 0.

From (28), we see that q∗ =
into (27) yields
−YT Y

(27)

∗

α−β ∗
s + (α − β)s∗ − αs∗ = 0,
α

which re-arranges to
YT Ys∗ =

−αβ ∗
s .
α−β

Since s∗ is non-zero, this shows that s∗ is an eigenvector of
YT Y with negative eigenvalue. This is impossible because the
Gram matrix YT Y is positive semi-definite. It follows that
(q∗ , s∗ ) cannot satisfy the first-order conditions (27) and (28),
and thus, cannot lie in the interior of CO .
A PPENDIX C
P ROOF OF T HEOREM 3
Since kGk < α, we have the Neumann series expansion [36]
in (11). Hence, we can bound the approximation error from
above as follows:
k(I − α−1 G)−1 − (I + α−1 G)k =
(a)

∞
X

(c)

k=2
∞
X

≤
=

k=0
(d)

=

(b)

(α−1 G)k ≤
α−1 G

k

∞
X

∞
X

(α−1 G)k

k=2

α−1 G

k

k=2

− 1 − kα−1 Gk

−1
1
Gk2
(e) kα
− 1 − kα−1 Gk =
.
−1
1 − kα Gk
1 − kα−1 Gk

Here, step (a) follows from the triangle inequality, step (b)
from the fact that the spectral norm is a consistent matrix norm,
step (c) is a result of basic arithmetic manipulations, step (d)
follows from geometric series expansions, and step (e) is the
same expression in simplified form. We note that the proof
continues to hold for any consistent matrix norm.

ACKNOWLEDGMENTS
The authors would like to thank S. Jacobsson and G. Durisi
for discussions on line-of-sight channels. We also thank C. Jeon
and G. Mirza for discussions on the input-cyclic MVP engine.
The work of O. Castañeda and C. Studer was supported by
Xilinx, Inc. and by the US National Science Foundation (NSF)
under grants ECCS-1408006, CCF-1535897, CAREER CCF1652065, and CNS-1717559. The work of T. Goldstein was
supported by the US NSF under grant CCF-1535902 and by the
US Office of Naval Research under grant N00014-17-1-2078.
R EFERENCES
[1] O. Castañeda, T. Goldstein, and C. Studer, “FPGA design of lowcomplexity joint channel estimation and data detection for large SIMO
wireless systems,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS), May
2017, pp. 128–131.
[2] T. L. Marzetta, “Noncooperative cellular wireless with unlimited numbers
of base station antennas,” IEEE Trans. Wireless Commun., vol. 9, no. 11,
pp. 3590–3600, Nov. 2010.
[3] F. Rusek, D. Persson, B. K. Lau, E. G. Larsson, T. L. Marzetta, O. Edfors,
and F. Tufvesson, “Scaling up MIMO: Opportunities and challenges with
very large arrays,” IEEE Signal Process. Mag., vol. 30, no. 1, pp. 40–60,
Jan. 2013.
[4] J. Hoydis, S. Ten Brink, and M. Debbah, “Massive MIMO in the UL/DL
of cellular networks: How many antennas do we need?” IEEE J. Sel.
Areas Commun., vol. 31, no. 2, pp. 160–171, Feb. 2013.
[5] E. Larsson, O. Edfors, F. Tufvesson, and T. Marzetta, “Massive MIMO
for next generation wireless systems,” IEEE Commun. Mag., vol. 52,
no. 2, pp. 186–195, Feb. 2014.
[6] J. G. Andrews, S. Buzzi, W. Choi, S. V. Hanly, A. Lozano, A. C. Soong,
and J. C. Zhang, “What will 5G be?” IEEE J. Sel. Areas Commun.,
vol. 32, no. 6, pp. 1065–1082, Jun. 2014.
[7] L. Lu, G. Li, A. Swindlehurst, A. Ashikhmin, and R. Zhang, “An overview
of massive MIMO: Benefits and challenges,” IEEE J. Sel. Topics Signal
Process., vol. 8, no. 5, pp. 742–758, Oct. 2014.
[8] M. Wu, B. Yin, G. Wang, C. Dick, J. R. Cavallaro, and C. Studer,
“Large-scale MIMO detection for 3GPP LTE: algorithms and FPGA
implementations,” IEEE J. Sel. Topics Signal Process., vol. 8, no. 5, pp.
916–929, Oct. 2014.
[9] P. Stoica and G. Ganesan, “Space–time block codes: Trained, blind, and
semi-blind detection,” Elsevier Dig. Signal Process., vol. 13, no. 1, pp.
93–105, Jan. 2003.
[10] H. Vikalo, B. Hassibi, and P. Stoica, “Efficient joint maximum-likelihood
channel estimation and signal detection,” IEEE Trans. Wireless Commun.,
vol. 5, no. 7, pp. 1838–1845, Jul. 2006.
[11] H. A. J. Alshamary, M. F. Anjum, T. Al-Naffouri, A. Zaib, and W. Xu,
“Optimal non-coherent data detection for massive SIMO wireless systems
with general constellations: A polynomial complexity solution,” arXiv
preprint: 1507.02319, Jul. 2015.
[12] W. Xu, M. Stojnic, and B. Hassibi, “On exact maximum-likelihood
detection for non-coherent MIMO wireless systems: A branch-estimatebound optimization framework,” in Proc. IEEE Int. Symp. Inf. Theory
(ISIT), Jul. 2008, pp. 2017–2021.
[13] T.-H. Pham, Y.-C. Liang, and A. Nallanathan, “A joint channel estimation
and data detection receiver for multiuser MIMO IFDMA systems,” IEEE
Trans. Commun., vol. 57, no. 6, pp. 1857–1865, Jun. 2010.
[14] R. Prasad, C. R. Murthy, and B. D. Rao, “Joint channel estimation and
data detection in MIMO-OFDM systems: A sparse Bayesian learning
approach,” IEEE Trans. Sig. Proc., vol. 63, no. 20, pp. 5369–5382, Oct.
2015.
[15] E. Kofidis, C. Chatzichristos, and A. L. F. de Almeida, “Joint channel
estimation / data detection in MIMO-FBMC/OQAM systems - a tensorbased approach,” arXiv preprint: 1609.09661, Sep. 2016.
[16] C.-K. Wen, C.-J. Wang, S. Jin, K.-K. Wong, and P. Ting, “Bayes-optimal
joint channel-and-data estimation for massive MIMO with low-precision
ADCs,” IEEE Trans. Sig. Proc., vol. 64, no. 10, pp. 2541–2556, Dec.
2016.
[17] O. Castañeda, T. Goldstein, and C. Studer, “Data detection in large
multi-antenna wireless systems via approximate semidefinite relaxation,”
IEEE Trans. Circuits Syst. I, no. 99, pp. 2334–2346, Nov. 2016.

O. CASTAÑEDA ET AL.

[18] S. Shah, A. Kumar, C. Castillo, D. Jacobs, C. Studer, and T. Goldstein,
“Biconvex relaxation for semidefinite programming in computer vision,”
European Conf. Comput. Vision (ECCV), pp. 717–735, Sep. 2016.
[19] S. Yang and L. Hanzo, “Fifty years of MIMO detection: The road to
large-scale MIMOs,” IEEE Commun. Surveys Tuts., vol. 17, no. 4, pp.
1941–1988, Sep. 2015.
[20] P. Stoica, H. Vikalo, and B. Hassibi, “Joint maximum-likelihood channel
estimation and signal detection for SIMO channels,” in Proc. IEEE Int.
Conf. Acoust., Speech, Signal Process. (ICASSP), vol. 4, May 2003, pp.
13–16.
[21] H. A. J. Alshamary and W. Xu, “Efficient optimal joint channel estimation
and data detection for massive MIMO systems,” in Proc. IEEE Int. Symp.
Inf. Theory (ISIT), Jul. 2016, pp. 875–879.
[22] A. Burg, M. Borgmann, M. Wenk, M. Zellweger, W. Fichtner, and
H. Bölcskei, “VLSI implementation of MIMO detection using the sphere
decoding algorithm,” IEEE J. Solid-State Circuits, vol. 40, no. 7, pp.
1566–1577, Jul. 2005.
[23] C. Studer, M. Wenk, and A. Burg, “VLSI implementation of hard-and
soft-output sphere decoding for wide-band MIMO systems,” in VLSI-SoC:
Forward-Looking Trends in IC and Systems Design. Springer, 2010, pp.
128–154.
[24] A. Schenk and R. F. H. Fischer, “Noncoherent detection in massive
MIMO systems,” in Int. ITG Workshop on Smart Antennas (WSA), Apr.
2013, pp. 1–8.
[25] G. Yammine and R. F. Fischer, “Soft-decision decoding in noncoherent
massive MIMO systems,” in Int. ITG Workshop on Smart Antennas
(WSA), Mar. 2016, pp. 1–7.
[26] J. Feng, H. Gao, T. Wang, T. Lv, and W. Guo, “A noncoherent differential
transmission scheme for multiuser massive MIMO systems,” in Proc.
IEEE Wireless Commun. Networking Conf. (WCNC), Mar. 2017, pp. 1–6.
[27] B. S. Thian and A. Goldsmith, “Decoding for MIMO systems with
imperfect channel state information,” in Proc. IEEE Global Telecommun.
Conf. (GLOBECOM), Dec. 2010, pp. 1–6.
[28] R. Ghods, C. Jeon, G. Mirza, A. Maleki, and C. Studer, “Optimally-tuned
nonparametric linear equalization for massive MU-MIMO systems,” in
Proc. IEEE Int. Symp. Inf. Theory (ISIT); arXiv preprint: 1705.02985,
Jun. 2017.
[29] R. Prasad, OFDM for Wireless Communications Systems. Norwood,
MA, USA: Artech House, Inc., 2004.
[30] “3GPP TS 36.211 Evolved Universal Terrestrial Radio Access (E-UTRA)
physical channels and modulation (release 8),” 3rd Generation Partnership
Project.
[31] D. Steinberg, “Computation of matrix norms with applications to robust
optimization,” Master’s thesis, Technion, Israel, 2005.

13

[32] M. Ajtai, “The shortest vector problem in L2 is NP-hard for randomized
reductions,” in Proc. ACM Symp. Theory Comput. ACM, 1998, pp.
10–19.
[33] D. Seethaler, J. Jaldén, C. Studer, and H. Bölcskei, “On the complexity
distribution of sphere decoding,” IEEE Trans. Inf. Theory, vol. 57, no. 9,
pp. 5754–5768, Sep. 2011.
[34] M. Wu, C. Dick, J. R. Cavallaro, and C. Studer, “High-throughput
data detection for massive MU-MIMO-OFDM using coordinate descent,”
IEEE Trans. Circuits Syst. I, no. 99, pp. 2357–2367, Nov. 2016.
[35] N. Parikh and S. Boyd, “Proximal algorithms,” Foundations and Trends
Optimization, vol. 1, no. 3, pp. 123–231, Jan. 2013.
[36] G. Stewart, Matrix Algorithms: Basic decompositions, 1998.
[37] P. Meinerzhagen, C. Roth, and A. Burg, “Towards generic low-power
area-efficient standard cell based memory architectures,” in Proc. IEEE
Int. Midwest Symp. Circuits Syst. (MWSCAS), Aug. 2010, pp. 129–132.
[38] D. Tse and P. Viswanath, Fundamentals of wireless communication.
Cambridge University Press, 2005.
[39] K. Wong, C. Tsui, R. Cheng, and W. Mow, “A VLSI architecture of a
K-best lattice decoding algorithm for MIMO channels,” in Proc. IEEE
Int. Symp. Circuits Syst. (ISCAS), vol. 3, May 2002, pp. 273–276.
[40] C. Studer, A. Burg, and H. Bölcskei, “Soft-output sphere decoding:
Algorithms and VLSI implementation,” IEEE J. Sel. Areas Commun.,
vol. 26, no. 2, pp. 290–300, Feb. 2008.
[41] C. H. Liao, T. P. Wang, and T. D. Chiueh, “A 74.8 mW soft-output
detector IC for 8×8 spatial-multiplexing MIMO communications,” IEEE
J. Solid-State Circuits, vol. 45, no. 2, pp. 411–421, Feb. 2010.
[42] C. H. Yang, T. H. Yu, and D. Marković, “A 5.8 mW 3GPP-LTE compliant
8×8 MIMO sphere decoder chip with soft-outputs,” in Symp. VLSI
Circuits, Jun. 2010, pp. 209–210.
[43] E. M. Witte, F. Borlenghi, G. Ascheid, R. Leupers, and H. Meyr, “A
scalable VLSI architecture for soft-input soft-output single tree-search
sphere decoding,” IEEE Trans. Circuits and Syst. II, vol. 57, no. 9, pp.
706–710, Sep. 2010.
[44] C.-F. Liao, J.-Y. Wang, and Y.-H. Huang, “A 3.1 Gb/s 8×8 sorting
reduced K-Best detector with lattice reduction and QR decomposition,”
IEEE Trans. VLSI Syst., vol. 22, no. 12, pp. 2675–2688, Feb. 2014.
[45] C. Senning, L. Bruderer, J. Hunziker, and A. Burg, “A lattice reductionaided MIMO channel equalizer in 90 nm CMOS achieving 720 Mb/s,”
IEEE Trans. Circuits Syst. I, vol. 61, no. 6, pp. 1860–1871, Jun. 2014.
[46] B. Yin, M. Wu, J. Cavallaro, and C. Studer, “VLSI Design of Large-Scale
Soft-Output MIMO Detection Using Conjugate Gradients,” in Proc. IEEE
Int. Conf. Circuits Syst. (ISCAS), May 2015, pp. 1498–1501.

