\documentclass[journal,11pt,a4paper,onecolumn,draftcls]{IEEEtran}
%\documentclass[journal,11pt,a4paper,twoside,twocolumn]{IEEEtran}
\usepackage{endfloat}
\usepackage{algpseudocode}
\usepackage[ruled,nothing]{algorithm}
\usepackage{amsmath,amssymb,amsfonts,mathrsfs,amscd,amsthm}
\usepackage[section]{placeins}
\usepackage[normal]{subfigure}
\usepackage{flushend}

\usepackage[dvips]{epsfig}
\DeclareGraphicsRule{.eps.gz}{eps}{.eps.bb}{`gunzip -c #1}
\DeclareGraphicsExtensions{.eps}
\graphicspath{{figures/}{eps/}{pdf/}{png/}{images/eps/}{images/pdf/}{images/png/}}


\title{Non-Linear Precoding with Periodically Flipped Constellation for
MIMO Downlink Channels}
\author{%
  \IEEEauthorblockN{Laurent Mazet, Sheng Yang, Lina Mroueh and Marc de Courville} \\
  \IEEEauthorblockA{Motorola-Labs Paris -- Parc Les  Algorithmes, Saint Aubin -- 91193 Gif sur Yvette Cedex -- France \\
    mazet@softndesign.org, sheng.yang@supelec.fr, lina.mroueh@enst.fr, marc.de.courville@motorola.com}}

\newcommand{\vect}[1]{{\lowercase{\pmb{#1}}}}
\newcommand{\mat}[1]{{\uppercase{\pmb{#1}}}}
\renewcommand{\matrix}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\pinv}[1]{{#1}^+}
\newcommand{\inv}[1]{{#1}^{{\scriptstyle -\!1 \!}}}
\newcommand{\herm}[1]{{#1}^{{\scriptstyle \dag\!}}}
\newcommand{\tran}[1]{{#1}^{{\scriptstyle \mathsf{T} \!}}}

\newcommand{\muc}{\hat{\vect{u}}}
\newcommand{\mvn}{\vect{v_n}}
\newcommand{\mvp}{\vect{v}_\parallel}
\newcommand{\mvo}{\vect{v}_\perp}
\newcommand{\nmvo}{\| {\mvo} \|^2}
\newcommand{\unc}{\hat{u}_n}
\newcommand{\uc}{\hat{u}}
\newcommand{\runc}{[\hat{u}_n]}

\newcommand{\muuc}{\hat{\vect{u}}}
\newcommand{\mek}{\vect{e_k}}
\newcommand{\sign}{\textrm{sign}}
\newcommand{\tr}[1]{\textrm{#1}}
\newcommand{\up}[1]{\textsuperscript{#1}}


\DeclareMathOperator{\flor}{floor}
\DeclareMathOperator{\chec}{check}

\begin{document}
\maketitle

\begin{abstract}
% Modifications 
In this paper, we propose a new constellation scheme for non-linear precoding in MIMO
downlink channels. Instead of using a periodically replicated
constellation, the proposed periodically flipped constellation (PFC)
successively mirrors the existing constellation to form an infinite
constellation. It is shown that the mirroring operation increases the
effective minimum distance of the original constellation and provides a
superior error resistance over the conventional constellation scheme for low order modulations, and low error rate scenarios. By
allowing for a contraction on the PFC, further performance improvement
due to a better tradeoff between the average transmit power and
minimum distance is achieved. Then, practical implementation of the PFC
specified sphere encoder is proposed. With a Schnorr-Euchner based
algorithm, the sphere encoder with PFC does not suffer from any
 penalty in terms of complexity. Finally, we apply the PFC in an OFDMA
 system and evaluate the performance with numerical simulations. 
\end{abstract}



\section{Introduction}
\label{sec:introduction}

The next generation cellular system (such as IEEE 802.16m~\cite{16m}, LTE
advanced~\cite{book.holma07}, etc) features Multiple-Input
Multiple-Output (MIMO) transmission (see \cite{ett.telatar99, wpc.foschini98}) and
multi-user communications. 

In the uplink channel, as known as the Multiple Access Channel (MAC), of such
systems, multiple mobile terminals transmit simultaneously to the base
station. The latter treats the received signal in such a way that
messages from different mobile terminals are distinguishable. The
capacity region of a multiple access\cite{isit.ahlswede71} has been known decades
ago. A capacity achieving scheme is the
Successive Interference Cancellation (SIC). This scheme has been well
studied and extends naturally in the MIMO case. 

Unlike the uplink channel, little is known for the downlink channel, as
known as the Broadcast Channel (BC), until recent years. Solid progress on
the capacity region of MIMO broadcast channel has been made in
\cite{ieeeIT.caire03, ieeeIT.viswanath03, ieeeIT.vishwanath03,
ieeeIT.yu04}, and the exact characterization of the capacity region was
found in \cite{ieeeIT.weingarten06}. It has been shown that the Dirty Paper
Coding (DPC) achieves the capacity region. As a dual counterpart of the
SIC for the MAC, the DPC for the BC successively removes the inter-user
interference at transmitter provided that exact Channel State
Information (CSI) is available at the transmitter side.  

The main hindrance to the practical implementation of the DPC is its high
complexity (see, for example, \cite{ieeeIT.erez05}) and its sensibility to the
CSI, as shown by \cite{allerton.yang05}. Low complexity solutions come naturally to
the channel inversion based schemes, such as the Zero-Forcing (ZF) and
the Minimum Mean Square Error (MMSE) precoders. The main idea is to
inverse the channel matrix at transmitter in such a way that the
inter-user interference is gone at the receiver side. However, direct
application of such precoders either requires high transmit power or
results in lower Signal to Noise Ratio (SNR) for a fixed transmit power,
especially when the channel matrix is ill-conditioned. One of the
workaround is to apply the lattice basis reduction at the transmitter
side. The lattice reduction yields a better conditioned basis and a
cubic constellation carved from the reduced basis has a much smaller
average energy (see \cite{ieeeIT.taherzadeh07}). Another workaround is the
vector perturbation scheme proposed by Hochwald \emph{et al}~\cite{ieeecom.hochwald05}.  
Instead of sending symbol from the cubic constellation carved from the
lattice of the inverse of the channel matrix, one can send any symbol from
the coset of this symbol. The optimal choice can be decided by so-called
sphere encoder. In both schemes, a modulo operation is involved at both the transmitter and receiver sides. 


The performance of the vector perturbation scheme depends highly on the modulo function sensitivity to
noise perturbation at low SNR. In our contribution, we propose to
implement a new non-linear precoder based on
the use of a more sophisticated constellation scheme called Periodically Flipped Constellation (PFC) at the
encoder associated to a modified modulo function at the receiver
to perform decoding. We show that this technique improves the
performance at low SNR by reducing detection errors due to
noise perturbation. Unlike in the
original scheme in \cite{ieeecom.hochwald05}, the sphere encoder cannot be applied directly for the PFC case.
We proposed therefore a general sphere encoder structure based on Schnorr-Euchner algorithm (see \cite{ieeeIT.agrell02}) that works for a broad class of constellation including the
PFC. Moreover, it turns out that the complexity of the general sphere
encoder is practically the same as the original sphere encoder.


%In this paper, we consider the vector perturbation scheme. Unlike in the
%original scheme in \cite{ieeecom.hochwald05} where a coset based
%infinite constellation is used, we propose a more
%sophisticated constellation scheme called Periodically Flipped
%Constellation (PFC). This constellation scheme successively mirrors the
%existing constellation to form an infinite constellation. The main
%advantage of this scheme is the robustness to noise at the receiver
%side, since it provides an improved minimum distance property as
%compared to the coset based constellation. As we will show in the rest
%of the paper, the resistance of the PFC to noise can be traded for a
%better energy efficiency. It is also shown that a contraction on the PFC
%provides a better trade-off between these two and therefore a better
%overall performance. Due to this particular PFC, sphere encoder cannot
%be applied directly. Two implementation schemes are proposed. This first
%one is a composition of multiple sphere encoders. The main idea is to
%consider the PFC as a union of $2^K$ conventional sub-constellations.
%Performing a conventional sphere encoding in each sub-constellation then
%choosing the best one form the resulting symbols is optimal. While this
%solution can be simple from the perspective of reusing the existing
%hardware, it is highly inefficient in terms of complexity as compared to
%the sphere encoder. The second solution is to perform the infinite
%lattice search operation (see \cite{ieeeIT.agrell02}) in considering the
%particular PFC during the search. We proposed a general sphere encoder
%structure that works for a broad class of constellation including the
%PFC. Moreover, it turns out that the complexity of the general sphere
%encoder is practically the same as the original sphere encoder. The
%proposed PFC and sphere encoder is then applied in an OFDMA system with
%numerical simulation. 

The rest of the paper is organized as follows. The system model and some
basic assumptions are presented in section~\ref{sec:preliminaries}.
Section~\ref{sec:pfc} introduces the proposed periodically flipped
constellation scheme. The improvement that can be achieved with
constellation contraction is detailed in section~\ref{sec:alpha}. More over some numerical simulation results are shown in this section to asset the performance gain compared to conventional scheme.
Section~\ref{sec:implementation} deals with the implementation of the
proposed scheme. Finally, section~\ref{sec:conclusions}
concludes the paper.  

\section{Preliminaries}
\label{sec:preliminaries}

\subsection{Notations}
The notations used in this paper are as follows. Boldface lower case letters $\vect{v}$ denote vectors, boldface capital letters $\mat{M}$ denote matrices. $\mathcal{CN}$ represents the complex Gaussian random variable. $\mathbb{E}\left(X\right)$ is the mathematical expectation of random variable $X$. $\left\|\vect{v}\right\|$ stands for the Euclidean norm of vector $\vect{v}$. $\|\mat{H}\|_{\text{F}}$ is the Frobenius norm of matrix $\mat{H}$ and $\inv{\mat{H}}$ is the inverse of a square matrix $\mat{H}$. $\mathbb{Z}^K[i]$ is the set of $K$ length complex integer vectors. Finally, $\lfloor x \rfloor$ and  $[x]$ denote respectively the floor and round operators.

\subsection{System Model}
\label{sec:system-model}
We consider a broadcast channel with one source equipped with $N_{t}$
antennas and $K$ destinations each one having single antenna. For the
ease of presentation, we assume that $K=N_{t}$, although the results can
be extended straightforwardly to the case with $K<N_{t}$. The signal
model is
\begin{equation}
  \label{eq:BC}
  \vect{y} = \mat{H}\frac{\vect{x}}{\sqrt{\gamma}} + \vect{z}
\end{equation}%
where $\vect{z} \in \mathcal{CN}(0,\mathbf{I})$ is the Additive White
Gaussian Noise (AWGN), $\mat{H}$ is the channel matrix, and $\gamma$
is the power normalization factor that does not depend on the
transmitted message, but can depend on the channel $\mat{H}$. Here, we
set
\begin{equation}
  \label{eq:gamma}
  \gamma \triangleq \frac{\mathbb{E}(\| \vect{x} \|^2)}{P}
\end{equation}
with $P$ being the total transmission power of the source. Since the
power of $\vect{y}$ can depend on both the source message and the
channel $\mat{H}$, we impose that the expectation in (\ref{eq:gamma})
is only over the source message for a given channel realization
$\mat{H}$. 

\subsection{Channel Inversion}
A simple linear precoding scheme is the zero-forcing
precoding (also denoted channel inversion) where
\begin{equation}
  \vect{x} \triangleq \inv{\mat{H}} \vect{s}
\end{equation}%
with $\vect{s}$ being the vector of signals intended for different
users. It is assumed that $\vect{s}$ belongs to a constellation carved
from the translated lattice $\Lambda$ defined by
\begin{equation}
  \label{eq:Lambda}
  \Lambda \triangleq \tau_c\mathbb{Z}^K[i]+\tau_c\frac{1+i}{2}
\end{equation}
and is normalized in power, i.e. $\mathbb{E}(|s_i|^2) = 1$ for all
$i$.  $\tau_c$ is the minimum distance between two different points in
the constellation. With the ZF precoding, the equivalent channel is
\begin{equation}
  \label{eq:ZF2}
  y_k = \frac{\sqrt{P}}{\| {\inv{\mat{H}}} \|_{\text{F}} } s_k + z_k,\quad \forall\,k 
\end{equation}%
Since we can approximate $\frac{1}{\| {\inv{\mat{H}}} \|_{\text{F}} }$ by $\sigma_{\min}(\mat{H})$, the minimum singular
value of $\mat{H}$, it can be deduced that this scheme suffers from
significant loss in terms of power and diversity (of order 1 in
Rayleigh fading channels). 

\subsection{Vector Perturbation}
\label{sec:vertor-perturb}

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\linewidth]{se_scheme2}
  \caption{Non-linear precoding with vector perturbation.}
  \label{fig:system-model}
\end{figure}


A fix to this problem is to use non-linear precoding scheme. A vector version of the Tomlinson-Harashima
precoding \cite{eletters.tomlinson71,ieeecom.harashima72} scheme, also
known as the vector perturbation scheme, is
proposed in \cite{ieeecom.hochwald05} and is described briefly as
follows (cf Fig.~\ref{fig:system-model}). This transmitted signal $\vect{x}$ is
\begin{equation}
  \label{eq:perturbation}
  \vect{x} = \inv{\mat{H}} (\vect{s}+\vect{p}(\vect{s}))
\end{equation}%
with $\vect{p}(\vect{s})\in\mathcal{P}(\vect{s})$ being the
perturbation vector. Thus, an obvious optimal choice of $\vect{p}$ is
\begin{align}
  \vect{p}^*(\vect{s}) &= \arg\min_{\vect{p}\in\mathcal{P}(\vect{s})} \| {\vect{x}} \|^2 \nonumber\\
  &= \arg\min_{\vect{p}\in\mathcal{P}(\vect{s})} \|
  {-\inv{\mat{H}}\vect{s}-\inv{\mat{H}}\vect{p}} \|^2.
\end{align}%
Note that the naive ZF scheme is a particular case of the above
scheme, which can be seen by setting trivially $\mathcal{P}(\vect{s})
= \{0\}$.  Therefore, the non-linear scheme is at least as good as the
linear scheme. In \cite{ieeecom.hochwald05}, $\mathcal{P}(\vect{s})$ is
set as a sub-lattice $\tau \mathbb{Z}^{K}[i]$ of the lattice $\tau_c
\mathbb{Z}^K[i]$ independent of $\vect{s}$. $\tau$ is chosen in order to get a periodic extension of the original signal constellation. 
Thus, $\tau/\tau_c\in\mathbb{Z}$ and $\vect{s}+\vect{p}(\vect{s})$ belongs to a coset of $\tau
\mathbb{Z}^{K}[i]$ determined by $\vect{s}$\footnote{For a QAM
signaling, it is readily shown that the cardinality of the constellation
is $(\tau/\tau_c)^2$.}. The received signal for
each user being
$$y_k = \frac{s'_k}{\sqrt{\gamma}} + z_k,\quad s'_k\in\tau_c\mathbb{Z}[i]+\tau_c\frac{1+i}{2},$$
the receiver tries to decide the most probable coset. For a hard
detector, the closest lattice point is first found and then is used to
determine the representation $\hat{\vect{s}}$ of the coset by a
{mod}-$\tau\mathbb{Z}^K[i]$ operation using the modulo function $f_\tau(\cdot)$ where $f_\tau(y) = y - \left\lfloor \frac{y+\tau/2}{\tau}\right\rfloor\tau$.

\section{Periodically Flipped Constellations}
\label{sec:pfc}

As shown above, the conventional vector perturbation scheme restricts the
possible perturbation vectors within the sub-lattice
$\tau\mathbb{Z}^K[i]$. In this section, we show that the performance can
be improved with another set of perturbation vectors. The
motivation is shown by the following example.  

\subsection{Motivating example} 

\begin{figure}[htbp]
  \centering
  \subfigure[Replicated constellation\label{fig:classical}]{\includegraphics[width=0.8\linewidth]{se_std2}}
  \\
  \subfigure[Periodically flipped constellation\label{fig:PFC}]{\includegraphics[width=0.8\linewidth]{se_pfc2}}
  \caption{Extra protection provided by periodically flipped constellation.}
  \label{fig:extra-protection}
\end{figure}

For simplicity of demonstration, we consider, in this example, the
special case of QPSK modulation. Suppose that the base station needs to
transmit to some user $k$ a symbol $d_{k} = -1+i$. With the conventional
vector perturbation scheme, a replicated constellation is
used as an infinite extension of the original constellation (cf. Fig.~\ref{fig:classical}). Let us assume that another point (say, $-5+i$) that is in the same coset turns out to minimize the transmit power and is chosen. If the noise happens to draw the received symbol outside the constellation
as shown in Fig.~\ref{fig:classical}, the receiver will 
make a wrong decision by searching the closest point in the
constellation to the received symbol.  

The situation can be improved with a better choice of perturbation set,
i.e. a better infinite extension. The idea is shown in
Fig.~\ref{fig:PFC}. Assume that $d_k=1+i$ is the information symbol.
Instead of associating the information symbol with its periodically
replicated counterparts, as in the previous case, the original
constellation is successively flipped away. We call this constellation
scheme the periodically flipped constellation. In this example,
the transmitter finds that $-5+i$ minimizes the transmit power over all
the associated points of $d_k=1+i$ in the PFC. Now, with the same noise
as in the previous case, the receiver can make a right decision by
searching the closest point at the extended constellation, i.e. the
PFC. Thus, the overall error rate performance is improved.


\subsection{Scheme definition}

Mathematically, a PFC of a $K$-dimensional QAM constellation
$\mathcal{C}$ can be represented by
$$\bigl\{ \vect{s}+\vect{p}(\vect{s})\ \left|\ \vect{s}\in\mathcal{C},\
\vect{p}(\vect{s})\in\mathcal{P}_{\text{PFC}}(\vect{s})\right.\bigr\}$$
with the set of perturbation vectors defined by 
\begin{equation}
  \label{eq:PFCset}
  \mathcal{P}_{\text{PFC}}(\vect{s}) \triangleq
  \left\{\vect{p}\,\left|\,
      \begin{aligned}
        \Re\{p_i\}\!\in\!(2\tau\mathbb{Z})\!\cup\!(f(\Re\{s_i\})\!+\!2\tau\mathbb{Z})\quad \\
        \forall i=1,\ldots,K, \\
        \Im\{p_i\}\!\in\!(2\tau\mathbb{Z})\!\cup\!(f(\Im\{s_i\})\!+\!2\tau\mathbb{Z})\quad\\
        \forall i=1,\ldots,K
      \end{aligned}\right.
  \right\}
\end{equation}%
where $f(s)=\tau-s$, $s\in\mathbb{R}$ is the flip function; $\Re\{x\}$ and $\Im\{x\}$ represent the real and imaginary parts of $x$, respectively. Since the above set is defined in a dimensional-wise manner, we can rewrite it
as
\begin{equation}
  \label{eq:PFCset2}
  \mathcal{P}_{\text{PFC}}(\vect{s}) \triangleq
  \left\{\vect{p}\,\left|\,
      \begin{aligned}
        \Re\{p_i\}\in\mathcal{P}_{\text{PFC}}(\Re\{s_i\})\quad \\
        \forall i=1,\ldots,K,\\
        \Im\{p_i\}\in\mathcal{P}_{\text{PFC}}(\Im\{s_i\})\quad \\
        \forall i=1,\ldots,K
      \end{aligned}\right.
  \right\}
\end{equation}%

With the flipped replication, it is obvious that points at the
border of the constellation enjoy a better protection. This is due to the
fact that the number of neighbors that are at the minimum distance to
any of these points is reduced by at least one\footnote{In the QPSK
example, the number of neighbors is reduced by two for all constellation points.}.
For BPSK, the number of neighbors of minimum distance to any symbol is 1 for PFC compared to 2 in the conventional case.
Similarly, this number is equal to 2 compared to 4 for QPSK and, to 2 or 3 compared to 4 for 16QAM.

%The table \ref{tab:SymbolErrorProbability} summarizes the number of neighbours of minimum distance to any symbol in QAM constellations of different size.
%\begin{table}[htbp]
%  \centering
%  \caption{Number of neighbours of minimum distance in QAM
%  constellations.}
%  \begin{tabular}{|c|c|c|} 
%    \hline
%    M-QAM & RC & PFC  \\
%    \hline
%    BPSK & 2 & 1\\
%    QPSK & 4 & 2 \\
%    16QAM & 4 & 2 or 3\\
%    \hline
%  \end{tabular}
%  \label{tab:SymbolErrorProbability}
%\end{table}

At the receiver side, similar operation is performed as with the
conventional vector perturbation schemes. More specifically, the closest
lattice point is first found, and then is used to determine the
representation in the original coset using a modified modulo function
which corresponds to $-f_\tau(\cdot)$ when the closest point happens to be
within one of the flipped constellations and $f_\tau(\cdot)$ if not. Hence, detection complexity remains the same as the
conventional constellation with the PFC. 

\subsection{Numerical Results}
\label{sec:results}

For illustration, we consider the case of a broadcast channel with $4$ transmit antennas and $4$ selected single antennas users among a large number of users.

In Fig.~\ref{fig:perf_per}, we compare for this antenna configuration the packet error rate for the conventional vector perturbation technique versus the PFC perturbation schemewhen a convolutional code $[$o133~o171$]$ is used for a packet size of 1kB.  A MIMO OFDMA system, having $N$ subcarriers, where $N = 512$, $1024$, $2048$ in practical standards is used. On each subcarrier, the channel is considered flat. 

Knowing that channel coefficients on two subcarriers $f_i$ and $f_j$ such that $|f_i - f_j| \geq B_c$ ($B_c$ being the coherence band) are uncorrelated, a frequency interleaver can be used to have independent channel on interleaved subcarriers. For each user, a cluster of $10$ independent subcarriers is assigned. This kind of feature is usually promotted as ``distributed subcarriers'' in modern OFDMA systems such as IEEE~802.16e and 3GPP-LTE.

We can see that the PFC provides a gain of 1.5dB for QPSK at $\text{BER}=10^{-2}$. Although this technique protects the border points in the constellation, there is no gain for higher order of modulations (16QAM and 64QAM). This loss in gain can be explained from the fact that the power normalization factors with replicated constellation is, in average, smaller than the one with periodically flipped constellation.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\linewidth]{per_cc_10c}
  \caption{Coded performance of PFC sphere encoder versus standard sphere encoder}
  \label{fig:perf_per}
\end{figure}

We also observed (on uncoded performance curves not presented in this paper) that gains of PFC over the classical SE are observed only in the low SNR regime. This can be explained by the fact that the PFC enhances performance of sphere encoding against noise perturbation. At low SNR, the probability that the error is due to noise perturbation is significant. However, at high SNR, the variance of the noise is very small, this error probability is reduced.

Let's remark, that there is no restriction on using the PFC with channel inversion. PFC can be also applied to the case of regularized sphere encoding~\cite{ieeecom.hochwald05}. 
 
\section{Improvement with Constellation Contraction}
\label{sec:alpha}

As stated in previous sections, the gain of the PFC over the standard
periodically replicated constellation comes from the fact that
constellation points at the border of the original constellation enjoy
extra protection. As it will be shown in the following, such protection
is excessive, since it can be reduced without impacting the performance.
Meanwhile, reducing the protection may save transmit power. 

\subsection{Constellation Contraction}

In this section, we propose to improve the performance of the vector
perturbation scheme by introducing a contraction on the PFC. The PFC with
contraction can be regarded as a generalized PFC, defined by an
additional contraction factor
$\alpha$ (Fig.~\ref{fig:sphere-encoder-with}). This idea is motivated by the following two observations. For simplicity of demonstration, we consider a BPSK modulation as an example.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.6\linewidth]{se_pfca}
  \caption{Sphere Encoder with $\alpha$-contraction.}
  \label{fig:sphere-encoder-with}
\end{figure}

First, we analyze the impact of $\alpha$ at the receiver side. The PFC
of a BPSK modulation is shown in Fig.~\ref{fig:alpha_Rx}. Assuming that
``$\square$'' is transmitted, we have the following approximation of
the union bound
\begin{multline}
  \text{Prob}\{\text{error}\,|\,\square\,\text{is transmitted}\} \\
  \shoveright{\lesssim \text{PEP}\{\square\to\bigcirc_1\} + \text{PEP}\{\square\to\bigcirc_2\}}  \\
  = Q\left(\frac{d_{\min}}{\sqrt{2\sigma^2}}\right) +
  Q\left(\frac{(1+\alpha)d_{\min}}{\sqrt{2\sigma^2}}\right)
\end{multline}
where $\text{PEP}\{A\to B\}$ is the pair-wise error probability that $A$
is confused with $B$ at the receiver; $Q(x)$ is the Gaussian tail
function; $\sigma^2$ is the variance of the AWGN. Since $Q(t)$ can be well
approximated by $1/2\exp(-t^2/2)$, we know that 
$$Q\left(\frac{d_{\min}}{\sqrt{2\sigma^2}}\right) \gg
Q\left(\frac{(1+\alpha)d_{\min}}{\sqrt{2\sigma^2}}\right),$$ except for
$\alpha$ small compared to 1. This remark implies that the error probability is not
sensitive to $\alpha$ when $\alpha$ is large.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\linewidth]{alpha_Rx} 
  \caption{PFC of BPSK: illustration of closest neighbors and the
  corresponding distances.}
  \label{fig:alpha_Rx}
\end{figure}

The second observation is impact of $\alpha$ on the transmitter side.
Without loss of generality, let us assume that the transmitter intends
to send ``$\square$''. With the PFC, the transmitter can choose in the
PFC the ``$\square$'' that minimizes the transmit power.
\begin{equation}
  \vect{p}^*(\vect{s}) = \arg\min_{\vect{p}\in\mathcal{P}(\vect{s})} \|
  {-\inv{\mat{H}}\vect{s}-\inv{\mat{H}}\vect{p}} \|^2.
\end{equation}%
This is essentially a quantization problem where the minimum power can
be seen as the quantization error of $-\inv{\mat{H}}\vect{s}$ in the
irregular\footnote{It is a lattice only when $\vect{p}$ is in
  $c\mathbb{Z}^n$ with $c$ being some scalar. Here, $\mathcal{P}$
  defined by the PFC is not a subset of a lattice in the general
  case.} lattice defined by $\inv{\mat{H}}$. As shown in
Fig.~\ref{fig:alpha_Tx}, decreasing the value of $\alpha$ can reduce
the size of quantization cell, which means a smaller quantization
error (smaller required transmit power). On the other hand, increasing
$\alpha$ provokes a larger transmit power in average.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\linewidth]{alpha_Tx} 
  \caption{PFC of BPSK: quantization cell.}
  \label{fig:alpha_Tx}
\end{figure}


As a conclusion of the above observations, there is a trade-off between
error probability at the receiver and the average transmit power for
the generalized PFC scheme. This trade-off is realized by $\alpha$.
While the original PFC scheme fixes $\alpha=1$, a relatively large value,
intuition suggests that one should decrease $\alpha$ from 1. In the
large $\alpha$ regime, the error probability is not sensitive to
$\alpha$, whereas the transmit power is sensitive to it. In this
regime, the decrease of $\alpha$ saves the transmit power by paying a
marginal penalty on the error probability. In the regime of small
$\alpha$, the error probability is very sensitive to $\alpha$, whereas
the transmit power is not sensitive to it. the decrease of $\alpha$
merely increases the error probability. The above arguments will be
confirmed by the numerical results presented later on.

\subsection{Performance assessments}
\label{sec:perf-assess}

By tuning the distance between replicated constellation, PFC performance
are improved by 1.3dB for QPSK, 0.4dB for 16QAM and 0.3dB for 64QAM (see
Fig.~\ref{fig:snr-gain-pfc}).

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\linewidth]{pera_cc_10c}
  \caption{SNR gain of PFC-$\alpha$ versus PFC at a PER target of 1\%.}
  \label{fig:snr-gain-pfc}
\end{figure}


\section{Implementation of General Sphere Encoder}
\label{sec:implementation}

\subsection{General closest point problem}
For $\mat{G} \in \mathbb{R}^{m\times n}$ and $\vect{y} \in \mathbb{R}^m$, let
us consider the minimization
\begin{equation}\label{clp}
  \hat{\vect{x}} = \arg \min_{\vect{x} \in \mathbb{Z}^n} \| {\vect{y} - \mat{G}\vect{x}} \|^2.%
\end{equation}%
The set $\Lambda(\mat{G}) \triangleq \{\mat{G}\vect{x}: \vect{x} \in \mathbb{Z}^n\}$
is a $n$-dimensional lattice in $\mathbb{R}^m$. The search in
(\ref{clp}) for the \emph{closest lattice point} to a given point
$\vect{y}$ has been widely investigated in lattice theory.

% In general, the optimal search algorithm should exploit the structure of the
%lattice. For general lattices, that do not exhibit any particular
%structure, the problem was shown to be NP-hard. In
%\cite{acmsigsam.pohst81}, however, Pohst proposed an efficient
%strategy for enumerating all the lattice points within a sphere with
%a certain radius. Although its worst case complexity is exponential in
%$m$, this strategy has been widely used ever since in \emph{closest
%  lattice point} search problems due to its efficiency in many useful
%scenarios.
%
%The Pohst enumeration strategy was first introduced in digital
%communications by Viterbo and Biglieri. In \cite{ieeeIT.viterbo99},
%Viterbo and Boutros applied it to the ML detection of multidimensional
%constellations transmitted over single antenna fading channels. 

More recently, Agrell \emph{et al}~\cite{ieeeIT.agrell02} proposed the use
of the Schnorr-Euchner refinement of the Pohst enumeration \cite{acmsigsam.pohst81} in the
\emph{closest lattice point} search. They further concluded, based on
numerical results, that the Schnorr-Euchner enumeration is more
efficient than the Viterbo-Boutros implementation \cite{ieeeIT.viterbo99}.

In the rest of this section, we will first present briefly the
principle of the Schnorr-Euchner strategy. A detailed version can be
found in \cite{ieeeIT.agrell02}. Then, it will be adapted to the
construct a sphere encoder with PFC.

\subsection{Closest lattice point search with Schnorr-Euchner algorithm}
\label{sec:clos-latt-point}

The Schnorr-Euchner strategy is in fact a combination of the Pohst
strategy and the Babai nearest-plane algorithm \cite{cmbntrca.babai86}.
Let us denote $\mat{G}\in\mathbb{R}^{m\times n}, m\geq n$ the generator matrix
of lattice $\Lambda(\mat{G})$, $\vect{y} \in \mathbb{R}^m$ a vector to be decoded in
the lattice
$\Lambda(\mat{G})$.% , and $\hat{\vect{u}} \triangleq \mat{G}^{+}\vect{y}$
% with $\hat{\vect{u}} = \tran{\matrix{\uc_1 & \uc_2 & \ldots & \uc_n}}$,
% then
\subsubsection{Recursive formulation}
\label{sec:recurs-form}

Let us define $\mat{G}_n \triangleq \mat{G}$ and rewrite it as
\begin{equation*}
  \mat{G}_n = \matrix{\mat{G}_{n-1} & \mvn}
\end{equation*}%
where $\mat{G}_{n-1}$ is an $m \times (n-1)$ matrix consisting of the $n-1$
first columns of $\mat{G}$ and $\mvn = \mvp + \mvo$, with $\mvp$ and
$\mvo$ in the column space and the null space of $\mat{G}_{n-1}$,
respectively. The lattice points are defined by the following set
\begin{align*}
  \Lambda(\mat{G}_n) &= \left\{ \mat{G}_n\vect{u}_n:\ \vect{u}_n \in \mathbb{Z}^n \right\} \\
  &= \bigcup_{u_n=-\infty}^{+\infty} \left\{ \vect{c} + u_n\mvp+u_n\mvo:
    \vect{c} \in \Lambda(\mat{G}_{n-1}) \right\}
\end{align*}%
which is basically a stack of $(n-1)$-dimensional translated
sub-lattices from $\Lambda(\mat{G}_{n-1})$. The $(n-1)$-dimensional
hyperplanes that contain these sub-lattices will be called
$(n-1)$-dimensional \emph{layers}. $u_n \in \mathbb{Z}$ can be seen as
the index of the $(n-1)$-dimensional layer. We can write any point
$\vect{y}\in\mathbb{R}^m$ in the following form
$$\vect{y} = \mvo \xi_n + \mat{G}_{n-1}\vect{\xi}_{n-1}$$
with $\xi_n\in\mathbb{R}$ and $\vect{\xi}_{n-1}\in\mathbb{R}^{n-1}$. Hence,
searching the closest lattice point in $\Lambda(\mat{G}_n)$ to a given
point $\vect{y}$ can be formulated as follows:
\begin{align}
  \hat{\vect{u}} &= \arg\min_{\vect{u}_n \in \mathbb{Z}^n} \| {\vect{y} - \mat{G}_n\vect{u}_n} \|^2 \nonumber\\
  &= \arg\min_{\vect{u}_n \in \mathbb{Z}^n} \left\{
  d_n(u_n) %\underbrace{|{\xi_n-u_n}|^2\| {\mvo}\|^2}_{d_n(u_n)}
  +
  \left\|
  y_{n-1}(u_n) %\underbrace{\left(\mat{G}_{n-1}\vect{\xi}_{n-1} - \mvp u_n\right)}_{y_{n-1}(u_n)}
    -
    \mat{G}_{n-1}\vect{u}_{n-1}
  \right\|^2 \right\}
  \label{eq:recursive}
\end{align}
where $d_n(u_n) = |{\xi_n-u_n}|^2\| {\mvo}\|^2$ and $y_{n-1}(u_n) = \left(\mat{G}_{n-1}\vect{\xi}_{n-1} - \mvp u_n\right)$
In the last equation, the first term stands for the distance between
the given point $\vect{y}$ and the layer defined by $u_n$, while the
second term is the distance between the projection of $\vect{y}$ on
the translated $(n-1)$-sub-lattice and a point in this sub-lattice
defined by $\vect{u}_{n-1}$.


\subsubsection{Tree structure}
\label{sec:tree-structure}
Therefore, finding the closest lattice point in a $n$-dimensional
lattice consists of finding the closest points in all translated
$(n-1)$-dimensional sub-lattices. The recursive formulation implies a
tree structure that depends only on the generator matrix $\mat{G}$ of
the lattice. 
% Specifically, the first level sub-tree depends on the
%generator matrix $\mat{G}_{n-1}$ of the $(n-1)$-dimensional
%sub-lattice, the second level sub-tree depends on the generator matrix
%$\mat{G}_{n-2}$ of the $(n-2)$-dimensional sub-lattice, and so on. 

A tree node at the $i$\up{th} level is labeled by $(u_{n-i+1},\ldots,u_n)$ and
represents a specific translation of a $(n-i)$-dimensional sub-lattice.
In particular, a leaf node is a lattice point. The weight of each tree
node is defined by the distance between the given point $\vect{y}$ and
the translated sub-lattice related to the node. Hence, the goal of the
tree search is to find the leaf node with the smallest weight.


\subsubsection{Enumeration with non-decreasing distance}
\label{sec:enumeration-with-non}
The Schnorr-Euchner enumeration is a depth first tree search
algorithm. A distinguished property of the enumeration is that the
tree nodes in the same level are ordered with increasing weight. That
is, a node with a smaller weight is always visited before the others.
%\begin{figure}[htbp]
%  \centering
%  \includegraphics[width=0.7\linewidth]{tree}
%  \caption{Schnorr-Euchner searching procedure.}
%  \label{fig:tree}
%\end{figure}
Since the weights of the tree nodes on the level $i$ can be written as
$w_i=w_{i-1} + d_i(u_i)$ differ only on $d_i(u_i)$, as implied by
\eqref{eq:recursive}, ordering the nodes in terms of $w_i$ is easy.
Assuming $\xi_n \leq [\xi_n]$, it is obvious that
\begin{equation}
  u_n = [\xi_n], [\xi_n]-1, [\xi_n]+1, \ldots \label{eq:ordering}
\end{equation}%
is a non-decreasing order in terms of $w_i$. The ordering for the case
$\xi_n > [\xi_n]$ can be deduced similarly.

%With the ordering constraint, the first leaf node visited by
%Schnorr-Euchner enumeration is the Babai point,
%obtained by $n$ successive closest plane searches. The weight of the
%Babai point then becomes the threshold on the weight. Tree nodes with
%a larger weight than the threshold will not be visited, neither will
%the sub-tree of it. This threshold is updated each time we find a leaf
%node with a smaller weight than the threshold. Once a node has a
%larger weight than the threshold, all the sub-trees on the same level
%and on the right of the current node will not be visited. This is
%because they have even larger weights than the current node does due
%to the ordered property imposed by the enumeration. 

With this ordering constraint, the complexity is
 significantly reduced (see \cite{ieeeIT.agrell02} for more details). The pseudo code of
the algorithm is provided below. 

% %Note that further
%refinement such as the QR decomposition can be used in the algorithm
%to reduce the complexity. However, we do not introduce here for
%brevity.

\begin{algorithm}[htbp]
  \caption{Schnorr-Euchner search for the closest lattice point}
  \label{SE}
  \begin{algorithmic}[1]
    \Require a $m \times n$ real matrix $\mat{G}$ with $m\geq n$, a $m$-dimensional
    vector $\vect{y}\in\mathbb{R}^n$ to decode in the lattice $\Lambda(\mat{G})$;
    \Ensure a $n$-dimensional vector $\muuc$ ($\in \mathbb{Z}^n$) such that
    $\mat{G}\muuc$ is the closest lattice point to $\vect{y}$.
      \State $k \gets n$
      \State $\mat{G}_k \gets \mat{G}$
      \State $\mat{G}_{k-1} \gets \mat{G}_k(:,1:k-1)$ and $\vect{v}_k \gets \mat{G}_k(:,k)$
      \State $\mvp \gets (\mat{G}_{k-1}\pinv{\mat{G}}_{k-1})\vect{v}_k$, $\mvo \gets \vect{v}_k-\mvp$, and $x_k \gets \frac{\herm{\mvo}\vect{y}}{\|{\mvo}\|^2}$
      \State $u_k \gets \textrm{round}(x_k)$
      \State $\textrm{step}_k \gets \sign(x_k-u_k)$
      \State $\Delta_k \gets \| {\mvo} \| (x_k-u_k)$
      \State $\textrm{dist}_k \gets 0$
      \While{true}
        \State $\textrm{newdist} \gets \textrm{dist}_k + \Delta_k^2$
        \If{$\textrm{newdist} < \textrm{bestdist}$}
          \If{$k \neq 1$}  \Comment{visiting intermediate node}
          %% \State \Foroneline{$i=1:k-1$}{$e_{k-1,i} \gets e_{ki} - yh_{ki}$}
            \State $k \gets k - 1$ \Comment{keep going down the tree}
            \State $\textrm{dist}_k \gets \textrm{newdist}$ \Comment{update current dist.}
            \State $\vect{y} \gets \left(\mathbf{I}-{\mvo\pinv{\mvo}}\right)\vect{y}$ \Comment{proj. to subspace}
            \State $\vect{y} \gets \vect{y}-\mvp u_k$ \Comment{horizontal shift}
            \State $\mat{G}_{k-1} \gets \mat{G}_k(:,1:k-1)$
            \State $\vect{v}_k \gets \mat{G}_k(:,k)$
            \State $\mvp \gets (\mat{G}_{k-1}\pinv{\mat{G}}_{k-1})\vect{v}_k$
            \State $\mvo \gets \vect{v}_k-\mvp$ and $x_k \gets \frac{\herm{\mvo}\vect{y}}{\| {\mvo} \|^2 }$
            \State $u_k \gets \textrm{round}(x_k)$
            \State $\textrm{step}_k \gets \sign(x_k-u_k)$
            \State $\Delta_k \gets \| {\mvo} \| (x_k-u_k)$
%%
    \algstore{bkbreak}
  \end{algorithmic}
\end{algorithm}

\begin{algorithm}[htbp]
  \caption{Schnorr-Euchner search for the closest lattice point (Algorithm I cont'd)}
  \begin{algorithmic}[1]
    \algrestore{bkbreak}
%%
          \Else \Comment{a leaf node has been visited}
            \State $\muuc \gets \vect{u}$ \Comment{it is the best point for now}
            \State $\textrm{bestdist} \gets \textrm{newdist}$;
            \State $k \gets k + 1$ \Comment{go back up, keep searching}
            \State $u_k \gets u_k + \textrm{step}_k$
            \State $\textrm{step}_k \gets - \textrm{step}_k - \sign(\text{step}_k)$
            \State $\Delta_k \gets \| {\mvo} \| (x_k-u_k)$
          \EndIf
        \Else  \Comment{current point has a larger distance}
          \If{$k = n$}
            \State break \Comment{return $\muuc$}
          \Else
            \State $k \gets k + 1$ \Comment{go back up, keep searching}
            \State $u_k \gets u_k + \textrm{step}_k$
            \State $\textrm{step}_k \gets - \textrm{step}_k - \sign(\text{step}_k)$
            \State $\Delta_k \gets \| {\mvo} \| (x_k-u_k)$
          \EndIf
        \EndIf
      \EndWhile
  \end{algorithmic}
\end{algorithm}

\subsection{Sphere encoder implementations for PFC}
\label{sec:sphere-encod-impl}

In this section, two implementations of the sphere encoder with PFC
are issued. The first solution is the composition of $2$ sphere encoders, and the others is unique sphere encoders based on a modified Schnorr Euchner.  It is clear that using a unique Schnorr Euchner on the resulting lattice instead of the decompositions of $2$ sphere encoders reduces significantly the complexity as shown in \cite{viterbo}. 

\subsubsection{Solution 1: composition of sphere encoders}
\label{sec:solut-1:-comp}

Since $\mathcal{P}_{\text{PFC}}(\vect{s})$ can be seen as a union of
$2^{2K}$ shifted sub-lattices $2\tau \mathbb{Z}^K[i]$, finding the
closest point in $\mathcal{P}_{\text{PFC}}(\vect{s})$ can be
implemented by finding the closest points in each of the shifted
sub-lattices and then taking the one with minimum distance. In each
shifted sub-lattice, a standard sphere decoder can be used for the
research. Therefore, the complexity of the composition is that of the
sphere decoder multiplied by a factor $2^{2K}$. This exponential time
complexity becomes unacceptable for a large number of users $K$.

\subsubsection{Solution 2: modified Schnorr-Euchner algorithm}
\label{sec:solution-2:-modified}

A more efficient way is to modify the sphere decoder in such a way
that it can work directly on the set
$\mathcal{P}_{\text{PFC}}(\vect{s})$ that does not have the lattice
property in general. As it will be shown in the following, this can be
worked around since each dimension of any point in
$\mathcal{P}_{\text{PFC}}(\vect{s})$ belongs to a manageable set (we
will get back to this in the end of the section).

As is shown in section~\ref{sec:enumeration-with-non}, the advantage
of the Schnorr-Euchner enumeration is its property of the
non-decreasing ordering in each dimension. In the lattice case, each
real dimension is a scaled version of the lattice $\mathbb{Z}$ and the
ordering is easily done by \eqref{eq:ordering}. The implementation
of the iterator is shown in algorithm~\ref{SE} at line 5, 6, 21, 22,
28, 29, 37, and 38. These lines realize the updating of the next point
to visit and the updating of the step. The rest of the algorithm is
independent of the structure of the set. As an abstraction, lines 5
and 6 can be replaced by the following lines
\begin{gather*}
  \text{Iter}(k).\text{update}(x_k),\\
u_k \gets \text{Iter}(k).\text{next}().
\end{gather*}
Similarly, lines 21 and 22 are replaced by exactly the same lines
above. On the other hand, lines 28 and 29 are replaced by
$$u_k \gets \text{Iter}(k).\text{next}().$$
Again, the same line is used to replace lines 37 and 38.  Note that
there is one ``Iterator'' per dimension and it is updated only when we
go down from a higher dimension, which is the case for lines 5 and 28.
The update positions the point $x_k$ and then determines the ordering
for non-decreasing distance in the dimension $k$. Thus, the current
point and the step between the current point and the next point are
initialized each time an update is performed. The function next() sets
the next point as current point, updates the step, and then returns
the current point.

As a result, what we need is to re-implement the functions update() and next()
for when the PFC is used in place of the conventional constellation. For convenience of exposition, we consider real lattices
in the following. It can be shown that this assumption is without loss
of generality because the complex signal model can be easily converted
to a real signal model with the complex to real field embedding.
Furthermore, the considered model is a scaled version of the original
model in such a way that the distance between the adjacent
constellation points is 1. The PFC without contraction is assumed in
the first place. The necessary modifications with respect to the
generalized PFC will be provided at the end of the section. 

It should be noted that an initialization
stage is needed for the iterators at the beginning of the proposed
sphere encoding, as shown in algorithm~\ref{init}.
\begin{algorithm}[htbp]
  \caption{Initialization of iterators: init($q$, $\vect{s}$)}\label{init}
  \begin{algorithmic}[1]
  \Require an integer $q$ and a $2K \times 1$ vector $\vect{s}$ with $s_i\in[0,q-1]$ 
  \For{$k=1:2K$}
    \State $\text{Iter}(k).q\gets q$
    \State $\text{Iter}(k).s\gets s_k$
  \EndFor
  \end{algorithmic}
\end{algorithm}

An implementation of the updating of an iterator is shown in
algorithm~\ref{update}. An example of a PFC of a BPSK constellation is
illustrated in Fig.~\ref{fig:iterator}.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\linewidth]{iterator}
  \caption{An example of PFC with BPSK: updating the iterator.}
  \label{fig:iterator}
\end{figure}

In algorithm~\ref{update}, two
iterator modes have been defined according to the position of $\xi$.
The iterator decides the next point to visit in each mode.

\begin{algorithm}[htbp]
  \caption{ Update an iterator: $\text{Iter}.\text{update}(\xi)$}
  \label{update}
  \begin{algorithmic}[1]
    \Require a real number $\xi$
      \State $\text{Iter}.\text{counter}\gets0$
      \State $\text{Iter}.\text{current}\gets\xi$
      \State
      $a\gets\left\lfloor\frac{\xi}{2*\text{Iter}.q}\right\rfloor*2*\text{Iter}.q$ %\Comment{largest point in $2q\mathbb{Z}$ that is smaller than $\xi$}
      \State
      $b\gets\left\lfloor\frac{\xi+2*\text{Iter}.s+1}{2*\text{Iter}.q}\right\rfloor*2*\text{Iter}.q - (2*\text{Iter}.s+1)$ % \Comment{largest point in $2q\mathbb{Z}+f(s)$ that is smaller than $\xi$}
      \State $\tilde{a}\gets\max\{a,b\}$,  $\tilde{b}\gets\min\{a,b\}$
      \State $\text{Iter}.d_1 \gets  2*\text{Iter}.q - (\tilde{a} - \tilde{b})$
      \State $\text{Iter}.d_2 \gets \tilde{a} - \tilde{b}$

      \If{$\xi\leq\tilde{b}+\text{Iter}.q$ or $\xi\geq\tilde{a}+\text{Iter}.q$}
        \State $\text{Iter}.\text{mode} \gets 1$
      \Else
        \State $\text{Iter}.\text{mode} \gets 0$
      \EndIf

      \If{$\xi>\frac{\tilde{a}+\tilde{b}}{2}+\text{Iter}.q$}
        \State $\text{Iter}.\text{step} \gets \tilde{b}+2*\text{Iter}.q-\xi$
      \Else
        \State $\text{Iter}.\text{step} \gets \tilde{a}-\xi$
      \EndIf

  \end{algorithmic}
\end{algorithm}

This is implemented in the function next(), as shown in algorithm~\ref{next}.

\begin{algorithm}[htbp]
  \caption{Find the next point to visit:
    $\text{Iter}.\text{next}()$}
  \label{next}\small
  \begin{algorithmic}[1]
    \Ensure a real number
      \State $\text{Iter}.\text{current} \gets \text{Iter}.\text{current}+\text{Iter}.\text{step}$;

      \If{$\text{Iter}.\text{mode}=0$}
        \If{$\text{Iter}.\text{counter}\ \text{mod}\ 4=0$} 
          \If{$\text{Iter}.\text{counter}=0$}
            \State $\text{Iter}.\text{step} \gets -(\text{sign}(\text{Iter}.\text{step}))*\text{Iter}.d_1$
          \Else
            \State $\text{Iter}.\text{step} \!\gets\! -\text{Iter}.\text{step}-(\text{sign}(\text{Iter}.\text{step}))*\text{Iter}.d_1$
          \EndIf
        \ElsIf{$\text{Iter}.\text{counter}\ \text{mod}\ 4=1$} 
          \State $\text{Iter}.\text{step} \gets -\text{Iter}.\text{step}-(\text{sign}(\text{Iter}.\text{step}))*\text{Iter}.d_2$
        \ElsIf{$\text{Iter}.\text{counter}\ \text{mod}\ 4=2$} 
          \State $\text{Iter}.\text{step} \gets -\text{Iter}.\text{step}-(\text{sign}(\text{Iter}.\text{step}))*\text{Iter}.d_2$
        \Else
          \State $\text{Iter}.\text{step} \gets -\text{Iter}.\text{step}-(\text{sign}(\text{Iter}.\text{step}))*\text{Iter}.d_1$
        \EndIf
      \Else
        \If{$\text{Iter}.\text{counter}\ \text{mod}\ 2=0$} 
          \State $\text{Iter}.\text{step} \gets (\text{sign}(\text{Iter}.\text{step}))*\text{Iter}.d_2$
        \Else
          \State $f \gets ((\text{Iter}.\text{counter}+1)/2)*(\text{Iter}.d_1+\text{Iter}.d_2)-\text{Iter}.d_2$
          \State $\text{Iter}.\text{step} \gets -\text{Iter}.\text{step}-(\text{sign}(\text{Iter}.\text{step}))*f$
        \EndIf
      \EndIf

  
      \State $\text{Iter}.\text{counter}\gets\text{Iter}.\text{counter}+1$
      \State \Return $\text{Iter}.\text{current}$

  \end{algorithmic}
\end{algorithm}

In Fig.~\ref{fig:iterator2}, the order in which the iterator visits the
points is shown for the two modes.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\linewidth]{iterator2}
  \caption{An example of PFC with BPSK: visiting order.}
  \label{fig:iterator2}
\end{figure}

It is clear that the re-implementation of the iterator does not
increase the order of the complexity of the Schnorr-Euchner algorithm.
This is due to the manageable structure of the set in each real
dimension, thanks to which the iterator can be implemented in low
complexity.

\begin{algorithm}[htbp]
  \caption{Initialization of iterators: init($q$, $\vect{s}$)}
  \label{init2}
  \begin{algorithmic}[1]
    \Require an integer $q$ and a $2K \times 1$ vector $\vect{s}$ with $s_i\in[0,q-1]$ 
      \For{$k=1:2K$}
        \State $\text{Iter}(k).q\gets q$
        \State $\text{Iter}(k).s\gets s_k$
        \State $\text{Iter}(k).\alpha\gets \alpha$
        \State $\text{Iter}(k).Q\gets q-1+\alpha$
      \EndFor
  \end{algorithmic}
\end{algorithm}

The implementation of the sphere encoder with the generalized PFC is
in exactly the same way as that with the original PFC. The only
modification is on the iterator, since the PFC depends on $\alpha$
now. The new implementation of the functions init() and
Iterator.update() is shown in algorithm~\ref{init2} and
algorithm~\ref{update2}.

\section{Conclusions}
\label{sec:conclusions}

In this paper, we present a new non-linear precoding technique for the multi-user MIMO downlink channel in the broadband wireless context. This new precoding scheme consists in choosing the set of perturbation vectors in a periodically flipped constellation rather than the replicated constellation as in the case of conventional sphere encoding scheme. 

\begin{algorithm}[htbp]
  \caption{ Update an iterator:
    $\text{Iter}.\text{update}(\xi)$}
  \label{update2}
  \begin{algorithmic}[1]
    \Require a real number $\xi$
      \State $\text{Iter}.\text{counter}\gets0$
      \State $\text{Iter}.\text{current}\gets\xi$
      \State $a\gets\left\lfloor\frac{\xi}{2*\text{Iter}.Q}\right\rfloor
      2*\text{Iter}.Q$ %\Comment{largest point in $2q\mathbb{Z}$ that is smaller than $\xi$}
      \State
      $b\gets\left\lfloor\frac{\xi+2*\text{Iter}.s+\text{Iter}.\alpha}{2*\text{Iter}.Q}\right\rfloor
      2*\text{Iter}.Q - (2*\text{Iter}.s+\text{Iter}.\alpha)$ % \Comment{largest point in $2q\mathbb{Z}+f(s)$ that is smaller than $\xi$}
      \State $\tilde{a}\gets\max\{a,b\}$,  $\tilde{b}\gets\min\{a,b\}$
      \State $\text{Iter}.d_1 \gets  2*\text{Iter}.Q - (\tilde{a} - \tilde{b})$
      \State $\text{Iter}.d_2 \gets \tilde{a} - \tilde{b}$

      \If{$\xi\leq\tilde{b}+\text{Iter}.Q$ or $\xi\geq\tilde{a}+\text{Iter}.Q$}
        \State $\text{Iter}.\text{mode} \gets 1$
      \Else
        \State $\text{Iter}.\text{mode} \gets 0$
      \EndIf

      \If{$\xi>\frac{\tilde{a}+\tilde{b}}{2}+\text{Iter}.Q$}
        \State $\text{Iter}.\text{step} \gets \tilde{b}+2*\text{Iter}.Q-\xi$
      \Else
        \State $\text{Iter}.\text{step} \gets \tilde{a}-\xi$
      \EndIf
  \end{algorithmic}
\end{algorithm}

We show that this scheme, by enhancing the protection of outer constellation points, improves the performance when low order QAM constellations are used. For higher order QAM (e.g. 64QAM) constellations, the energy loss of the PFC compared to the standard periodically replicated constellation can be recovered using the generalized PFC with a finely tuned compression. By introducing the contraction on the constellation distance, we show that this can provide a better trade-off between the PFC resistance and the energy efficiency.

Finally, we propose a practical implementation for the sphere encoding with PFC based on the Schnorr-Euchner algorithm. The modified Schnorr-Euchner benefits from the manageable structure of the PFC to find the closest point in this type of lattice. Moreover, this modified algorithm takes into account the tuning parameter in order to adjust the distance between neighboring replicated and flipped constellations.  

\bibliographystyle{IEEEtran} 
\bibliography{paper_pfc}


\end{document}
