

\section{Introduction}

\IEEEPARstart{O}{ne} of the most-promising emerging technologies in 6G communication systems are \acp{ris}, which enable the 
control and optimization of the propagation channel, thereby enabling or boosting radio communication, localization, and sensing \cite{bjornson2021reconfigurable}.
An \ac{ris} comprises a large number of passive elements, with sub-wavelength inter-element spacing. Each element scatters the impinging signal after applying a phase shift to it. In order to improve the communication \ac{qos} in a wireless network comprising one or more \acp{ris}, the \acp{ris}' phase profiles should be jointly optimized \cite{abrardo2020intelligent}. Performing such optimization requires the \ac{csi} for the channel 
corresponding to each individual \ac{ris}. Furthermore, in localization, parameter estimation for each of the controlled channels as well as the uncontrolled one is often essential.  Obtaining the per-channel \ac{csi} entails resolving the interpath interference at the \ac{rx}, which is the topic of this paper. This task is  challenging  since \emph{i)}  unlike more conventional technologies such as relays, \acp{ris} are often passive and are not equipped with a \ac{rf} chain, thus they cannot transmit, receive, process, or amplify signals \cite{wu2021intelligent} \emph{ii)} \acp{ris} can only apply discrete phase shifts to the impinging signal \cite{pan2021reconfigurable}.


 Channel estimation for \ac{ris}-aided wireless systems has been studied in a number of papers (see \cite[Sec.\,VI-G]{di2020smart}). In order to estimate the channel from an individual \ac{ris}, it is generally assumed that the uncontrolled multipath is blocked (see e.g., \cite{alexandropoulos2020hardware})

 or that a \ac{ris} can be ``switched off''  (i.e., operate in absorption mode), thereby avoiding interpath interference (see e.g., \cite{mishra2019channel}).

 In \cite{jensen2020optimal,you2020channel}, the channel for each \ac{ris} element is estimated by designing the \ac{ris} phase profile according to orthogonal sequences. In all these studies the wireless system is aided by a single \ac{ris}. A limited number of papers consider channel estimation in multi-\ac{ris} systems:
 in \cite{ning2020channel}, channel estimation is performed for a multi-\ac{ris} \ac{mimo} system via successive hierarchical beam sweeping for each of the \acp{ris}. In \cite{alexandropoulos2020phase} explicit multi-\ac{ris} channel estimation is bypassed by maximizing the achievable rate directly using a supervised learning technique.
 

Similarly as in  channel estimation, in multi-RIS  localization it has been considered switching off  \acp{ris} to avoid interpath interference \cite{wang2021joint}.  In \cite{keykhosravi2021semi}, a semi-passive localization scenario has been studied, where each of the users are equipped with an \ac{ris} and orthogonal \ac{ris} phase profiles are used to resolve the interpath interference. \acp{crb}  on the localization accuracy have been derived in \cite{elzanaty2020reconfigurable} for multi-\ac{ris} \ac{mimo} systems, however no estimation method is provided. In \cite{keykhosravi2020siso}  localization is performed via successive interference cancellation, assuming that the direct channel is much stronger than the channel reflected from an \ac{ris}.  


In this paper, we tackle the problem of interpath interference during pilot transmission for a generic multi-\ac{ris} communication or localization scenario.
Our specific contributions are as follows: \textit{(i)} we design temporally coded \ac{ris} phase profiles with finite resolution, such that the signal received by different paths are mutually orthogonal, based on \ac{bh} matrices; \textit{(ii)} we show that these codes do not affect the chosen beamforming \ac{ris} phase profile, though they introduce a delay; \textit{(iii)} to address the delay, we study the problem of finding the shortest orthogonal code for finite resolution \ac{ris} using properties of \ac{bh} matrices; \textit{(iv)}
 to assess the effectiveness of our proposal, we consider the semi-passive localization scenario in \cite{keykhosravi2021semi} under limited \ac{ris} phase shifts resolution and show that  the \ac{crb}  bounds can be obtained with one bit phase resolution, while ignoring the  finite \ac{ris} phase resolution leads to  significant interpath interference.

\emph{Notation:} The vectors, which are columns by default, are represented by the lower-case bold letters and the matrices by the upper case bold ones. The $i$th element of vector $\bm{x}$ is shown by $[\bm{x}]_i$ and the element on the $i$th row and $j$th column of matrix $\mathbf{X}$ is shown by $[\mathbf{X}]_{i,j}$. Furthermore, $[\mathbf{X}]_{i}$ indicates the $i$th row of matrix $\mathbf{X}$. We show the the ceiling function by $\lceil\cdot\rceil$. We define the set $\mathbb{T}$ to represent the circle group and $\mathbb{T}_R$ to represent $\{e^{\jmath2\pi r/R}\}_{r=0}^{R-1}$. The  zero-mean  circularly  symmetric Gaussian  distribution with covariance  matrix $\bm{C}$ is represented by $\mathcal{CN}(\bm{0}, \bm{C})$. The Kronecker and Hadamard products are indicated by $\otimes$ and $\odot$ respectively. We define $\mathbf{X}^{\otimes n} = \underbrace{\mathbf{X} \otimes \dots \otimes \mathbf{X}}_{n \text{ times}}$ and $\mathbf{X}^{\otimes 0} =1$.


\section{System model}
We consider a general  \ac{mimo} scenario, where the \ac{tx} sends pilots with constant energy, for the purpose of channel estimation or user localization. The signal from the \ac{tx} is received  via the uncontrolled multipath and  controlled multipath from the $K\ge 1$ \acp{ris}. We ignore multi-bounce effects from two or more \acp{ris}. The received signal at $t$th transmission can be represented as
\begin{align}\label{eq:chMod1}
   \mathbf{y}_t= \Big(\mathbf{H}_0 + \sum\limits_{k=1}^K \mathbf{H}_k(\bm{\gamma}_{k,t})\Big)\sqrt{E_{\mathrm{s}}} +\bm{\nu}_{t}.
\end{align}
Here, $\mathbf{H}_0\in\mathbb{C}^{N_{\mathrm{rx}}\times N_{\mathrm{tx}}}$ represents the uncontrolled channel (which may or may not be blocked), where $N_{\mathrm{rx}}$ and $ N_{\mathrm{tx}}$ are the \ac{rx} and \ac{tx} antenna count. The channel from \ac{tx} to the $k$th \ac{ris} to the \ac{rx} is shown by $\mathbf{H}_k(\bm{\gamma}_{k,t})$, where $\bm{\gamma}_{k,t}\in \mathbb{T}^{N_\mathrm{ris}}_R$ represents the phase profile at time $t$ of  \ac{ris} $k$ with $N_\mathrm{ris}$ being the number of unit cells per \ac{ris} and $R \in \mathbb{N}_{>1}$ being the \acp{ris} phase resolution. The transmitted pilots are assumed to identical to $\sqrt{E_{\mathrm{s}}}$. Finally, $\bm{\nu}_{t}\sim \mathcal{CN}(\bm{0},N_0\bm{I}_{N_{\mathrm{rx}}})$ represents the complex  additive zero-mean white noise.
The channel related to the $k$th \ac{ris} can be decomposed as
\begin{align}
    \mathbf{H}_k(\bm{\gamma}_{k,t})&= \mathbf{H}_{\mathrm{sr},k} \mathrm{diag}(\bm{\gamma}_{k,t})\mathbf{H}_{\mathrm{ts},k},
\end{align}
where $\mathbf{H}_{\mathrm{sr},k} \in \mathbb{C}^{N_{\mathrm{rx}}\times N_{\mathrm{ris}}}$ and $\mathbf{H}_{\mathrm{ts},k} \in \mathbb{C}^{N_{\mathrm{ris}}\times N_{\mathrm{tx}}}$ represent the channels from \ac{ris} to \ac{rx} and from \ac{tx} to \ac{ris}, respectively. One can observe that for any $h\in\mathbb{T}_R$, we have
\begin{align}\label{nlos:h}
    \mathbf{H}_k(h\bm{\gamma}_{k,t}) = h\mathbf{H}_k(\bm{\gamma}_{k,t}).
\end{align}
Finally, we assume that the system designer has chosen desired phase profile $\bm{\zeta}_{k,q} \in \mathbb{T}^{N_{\mathrm{ris}}}_R$ for each \ac{ris} $k$, for transmissions times $q\in \{0,\ldots,Q-1\}$, $Q\ge 1$. The choice of $\bm{\zeta}_{k,q}$ and $Q$ is arbitrary, and could correspond, e.g., to $Q$ different beams that are directed to the \ac{rx} (e.g., if some prior knowledge of the \ac{rx} position is available); or to cover a plurality of users; or random beams to provide omnidirectional illumination.



Our proposed design (see Section \ref{sec:RIS_phase_profile_design}) is applicable to all the channel models that can be described by \eqref{eq:chMod1}--\eqref{nlos:h}, which includes most of the \ac{ris} channel models in the literature, whether narrow-band or wide-band, near-field or far-field, parametric or unstructured, single-RIS or multi-RIS, and with or without uncontrolled multipath.




\section{RIS phase profile design}\label{sec:RIS_phase_profile_design}

\subsection{Slow and fast \ac{ris} phase profiles}
We design the RIS phase profile by dividing the total transmission time $T$, into $P$ intervals with $Q$ symbols, i.e., we set $T = P\times Q$. Here, $P$ is a design parameters, which will be discussed later. We represent the \ac{ris} phase profile as
\begin{align}\label{eq:gama_kt}
    \bm{\gamma}_{k,t} = \beta_{k,p} \bm{\zeta}_{k,q},
\end{align}
where $p=t \, \mathrm{mod}\, P$ and $q = (t-p)/P$, so we have that $t=qP+p$. We call $\beta_{k,p}\in \mathbb{T}_R$ the \emph{fast-varying} part of the \ac{ris} phase profile and $\bm{\zeta}_{k,q} \in \mathbb{T}^{N_{\mathrm{ris}}}_R$ the \emph{slow-varying} part. Notice that since $\mathbb{T}_R$ is closed under multiplication, the $\bm{\gamma}_{k,t}$ in \eqref{eq:gama_kt} is in $\mathbb{T}^{N_{\mathrm{ris}}}_R$.


While the slow-varying parts are predetermined, we will design the fast varying part such that, for all $k=1\dots, K$, $k'\neq k$, we have 

 
  
\begin{align}
    &\sum\limits_{p=0}^{P-1} \beta_{k,p}\beta^*_{k',p} =0\,\, \text{and}\,\, \sum\limits_{p=0}^{P-1} \beta_{k,p}=0 \label{eq:beta1}\\
   
    &{\beta}_{k,p}  \in \mathbb{T}_R, \forall k,p \label{eq:beta3}.
\end{align}
With this design, in the \ac{rx} we first multiply the received signal with the conjugate of the transmitted pilot to obtain $\mathbf{w}_t = \mathbf{y}_t $. Then we calculate
\begin{align}
    \mathbf{z}_{k,q} &= \sum\limits_{p=0}^{P-1}\beta^*_{k,p} \mathbf{w}_{qP+p} =P \sqrt{E_{\mathrm{s}}} \mathbf{H}_k(\bm{\zeta}_{k,q})\mathbf{1}_{N_{\mathrm{tx}}} + \bm{\nu}_{k,q}\label{eq:zkq}\\
    \mathbf{z}_{0,q} &= \sum\limits_{p=0}^{P-1} \mathbf{w}_{qP+p} =P \sqrt{E_{\mathrm{s}}} \mathbf{H}_0\mathbf{1}_{N_{\mathrm{tx}}} + \bm{\nu}_{0,q},\label{eq:zkq}
\end{align}
where, $\mathbf{1}_{N_{\mathrm{tx}}}$ denotes the all-one vector of length $N_{\mathrm{tx}}$. Vectors $\bm{\nu}_{k,q}$ and $\bm{\nu}_{0,q}$ \Corr{represent the additive noise with distribution $\mathcal{CN}(\bm{0},PN_0\bm{I}_{N_{\mathrm{rx}}})$}. It can be seen that  in the observations $\mathbf{z}_{k,q}$ all interpath interference is eliminated and that each path can be estimated separately. The question remains how to design the fast-varying part to satisfy \eqref{eq:beta1}--\eqref{eq:beta3}, while simultaneously keeping $P$ as small as possible. This will be discussed next.




\subsection{Designing the fast-varying part}\label{sec:fast_varying}


In this section, we show how to find a feasible  solution of $\beta_{k,p}\in \mathbb{T}_{R}$ that satisfy \eqref{eq:beta1}--\eqref{eq:beta3} for a given $K$ and $R$. Also, we consider the problem of finding $P^*$, the minimum value of $P$ that allows a feasible solution. We refer to such solution as the \emph{optimal solution}.
We will now define several concepts, based on which we show for which cases an optimal solution can be found, while providing a simple method for finding a feasible solution for the general case.

We first introduce $\mathrm{BH}(P,R)$ as the set of \ac{bh} matrices of order $P$ and complexity $R$, that is all matrices  $\bm{\Upsilon}\in \mathbb{T}^{P\times P}_R$ that satisfy $\bm{\Upsilon} \bm{\Upsilon}^{\mathrm{H}} = P\mathbf{I}_P$, where $\mathbf{I}_P$ is a $P\times P$ identity matrix. In general, these sets may be empty and finding elements in $\mathrm{BH}(P,R)$ or characterizing the entire set is an open problem. However, in \cite{lampio2020orderly}, a numerical method is introduced to search for BH matrices; the authors publish a list of discovered BH matrices on their Wiki page\footnote{\url{https://wiki.aalto.fi/display/Butson}}. 

Secondly, we represent the prime factorization of $R$ b
\begin{align}\label{eq:primeFac}
    R = p_1^{e_1}\times p_2^{e_2}\times \dots \times p_L^{e_L},
\end{align} 
where we assume that $p_1< p_2 < \dots < p_L$. 

Thirdly, we define the vectors $\bm{\beta}_k = [\beta_{k,0}, \beta_{k,1}, \dots, \beta_{k,P-1}]^\top$ and $\bm{\beta}_0 = \mathbf{1}_P$. Then the conditions \eqref{eq:beta1}
can be rewritten as 
\begin{align}
\bm{\beta}_0 &= \mathbf{1}_P\label{eq:bVecCondition1}\\
    \bm{\beta}_k^{\mathrm{H}} \bm{\beta}_{k'} &= P \mathbbm{1}(k=k'),\label{eq:bVecCondition}
\end{align}
where $\mathbbm{1}(\cdot)$ is the indicator function. Furthermore, we let $\mathbf{B}\in \mathbb{T}_{R}^{(K+1)\times P} $ be $[\bm{\beta}_0^\top, \dots, \bm{\beta}_{K}^{\top}]^{\top}$ and rewrite the conditions \eqref{eq:beta1}
as
\begin{align}
    [\mathbf{B}]_1 &= \mathbf{1}_P^\top\label{eq:bMatCondition1}\\
    \mathbf{B}\mathbf{B}^{\mathrm{H}} &= P \mathbf{I}_{K+1}.\label{eq:bMatCondition2}
\end{align}



\subsection{Special cases}
Before dealing with the general case, we consider five  specific cases of practical importance for which an optimal solution to \eqref{eq:beta1}--\eqref{eq:beta3} can be found.
\subsubsection{Case \emph{I}: Infinite resolution: $\beta_{k,p}\in \mathbb{T}$}\label{sec:infb}
With infinite phase resolution, we can find a feasible solution by setting $\bm{\beta}_k^\top$ to be the $k$th row of the $P\times P$ \ac{dft} matrix $\mathbf{F}_P$, i.e.,
\begin{align}\label{eq:binf}
    \beta_{k,p} = [\mathbf{F}_P]_{k,p} = e^{-\jmath 2\pi kd /P}.
\end{align}
The condition \eqref{eq:bVecCondition} holds since the \ac{dft} matrix is unitary.   This also shows, by construction, that $P^*\le K+1$. Via the following lemma, we prove that the minimum duration solution is $P^*=K+1$. 

\begin{lemma}\label{lemma:kPlus1}
If $P<K+1$, then there is no solution  for $\bm{\beta}_k \in \mathbb{T}_R^{P}$ that satisfies \eqref{eq:bVecCondition} for $k=0, \dots, K$.
\end{lemma}
\begin{proof}
 Since $\bm{\beta}_k\in \mathbb{C}^{P}$ then, if $K+1>P$, vectors $\bm{\beta}_k$ must be linearly dependent. This is in contradiction to \eqref{eq:bVecCondition}.
\end{proof}

\subsubsection{Case \emph{II}: $p_1\geq K+1$}\label{sec:caseII}
We now show that in this case, $P^* = p_1$. To do so, we first present a solution for $\bm{\beta}_k$ with $P=p_1$ and then prove that no solutions exist for $P<p_1$. The first part is done by setting  $\bm{\beta}_k^\top$ to the $k$th row of $\mathbf{F}_{p_1}$. Since $\mathbb{T}_{p_i} \subseteq \mathbb{T}_{R}$, this yields a valid solution.
To prove the second part, we use the following proposition.

\begin{proposition}\label{prob:1}
For any $R>1$ with the prime factorization \eqref{eq:primeFac}, let $\mathcal{W}(R)$ be the set of all positive integers $M$ for which there exists $\bm{\alpha} \in \mathbb{T}_R^M$ such that $\bm{\alpha}^\top \mathbf{1}_M=0$. Then 
\begin{align}\label{eq:Wdef}
    \mathcal{W}(R) = \Big\{\sum_{i=1}^Lm_ip_i\, \vert\, m_i\in\mathbb{N} \Big\} \setminus \{0\}.
\end{align}
\end{proposition}
\begin{proof}
See  \cite{lam2000vanishing}.
\end{proof}
Now, assume that $P < p_1$ and that $\bm{\beta}_k \in \mathbb{T}^P_R$ satisfies \eqref{eq:bVecCondition1}--\eqref{eq:bVecCondition}. Then, $\bm{\beta}_1^\top \mathbf{1}_P =0$, which,  according to Proposition~\ref{prob:1}, implies that $P\in \mathcal{W}(R)$. However, from \eqref{eq:Wdef}, the minimum member of $\mathcal{W}(R)$ is $p_1$ and this is in contradiction with the assumption that $P < p_1$.



\subsubsection{Case \emph{III}: $R=2$}\label{sec:case:R2}
In this case, $\bm{\beta}_k$ are real vectors, and therefore we should consider (real) Hadamard matrices in order to find a solution. If $K=1$, one can check that $\mathbf{F}_2$ is an optimal solution. For higher values of $K$, we use the following proposition. 
\begin{proposition}\label{prop:2}
If $\mathrm{BH} (P,2)$ is non-empty, and $P>2$ then a positive integer $\kappa$ exists such that $P=4\kappa$.
\end{proposition}
\begin{proof}
See \cite[Sec.\,1.3.2]{laclair2016survey}.
\end{proof}
The inverse of Proposition~\ref{prop:2} reads as follows. 
\begin{conjecture}[Hadamard Conjecture]\label{conj:1}
For any positive integer $\kappa$, the set $\mathrm{BH} (4\kappa,2)$ is non-empty.
\end{conjecture}
This conjecture has been an open problem for over $100$ years. However, it has been proven for values $\kappa<167$ \cite{laclair2016survey}, which is enough for most practical purposes. Next, we present the following theorem on optimal solutions for $R=2$.
\begin{theorem}
Let $2<K<664$. Then the smallest value of $P$ that yields a solution for $\{\bm{\beta}_k\in\mathbb{T}_{2}^P\}_{k=0}^{K}$ that satisfies \eqref{eq:bVecCondition1} and \eqref{eq:bVecCondition} is  $ P^* = 4\lceil(K+1)/4\rceil$. 
\end{theorem}
\begin{proof}
See Appendix \ref{app:Thm1}.
\end{proof}
To generate the optimal solution one should assign $\bm{\beta}_k$ (for $k=0, \dots, K$) to the $k$th row of a matrix  $\mathrm{BH}(P^*, 2)$ that satisfies \eqref{eq:bMatCondition1}.

\subsubsection{Case \emph{IV}: $R=2^r$ with $r>1$}
We begin by stating a conjecture about the existence of $\mathrm{BH}(P,4)$ matrices \cite{seberry1973complex}.
\begin{conjecture}\label{conj:turyn}
For all positive integers $\kappa$, the set $\mathrm{BH}(2\kappa,4)$ is non-empty.
\end{conjecture}
It was shown that this conjecture is true for all $\kappa\leq32$ \cite{seberry1973complex}, which is large enough for all the practical cases that we consider in this paper. The following corollary follows from the fact that for all $r\geq 2$ we have that $\mathrm{BH}(P,4)\subseteq\mathrm{BH}(P,2^r)$.
\begin{corollary}\label{cor:two-to-r}
For all positive integers $\kappa\leq 32$ and  $r\geq 2$, the set $\mathrm{BH}(2\kappa,2^r)$ is non-empty. 
\end{corollary}
Next, in the following theorem we discuss the optimal solution.
\begin{theorem}
Let $1\leq K<64$ and $r\geq 2$, then the smallest value of $P$, for which there exists a solution for $\{\bm{\beta}_k\in\mathbb{T}_{2^r}^P\}_{k=0}^{K}$ that satisfies \eqref{eq:bVecCondition1} and \eqref{eq:bVecCondition} is  $ P^*=2\lceil(K+1)/2\rceil$. 
\end{theorem}
\begin{proof}
See Appendix \ref{app:Thm2} 
\end{proof}
The optimal solution can be generated based on the rows of a $\mathrm{BH}(P^*, 2^r)$ matrix satisfying \eqref{eq:bMatCondition1}.

\subsubsection{Case \emph{V}: $\mathrm{BH}(K+1,R)$ is non-empty}
We first introduce the following lemma from \cite{butson1962generalized} for later use.
\begin{lemma}\label{lemma:1}
If there exists $\mathbf{G}\in \mathbb{T}^{(K+1)\times P}_R$ that satisfies  \eqref{eq:bMatCondition2}, then there exists a matrix $\mathbf{B}\in \mathbb{T}^{(K+1)\times P}_R$ that satisfies both \eqref{eq:bMatCondition1} and \eqref{eq:bMatCondition2} and it can be generated as $ \mathbf{G} \bm{\Lambda}^{\mathrm{H}}$,
where $\bm{\Lambda} = \text{diag}([\mathbf{G}]_1)$.
\end{lemma}
\begin{proof}
The proof follows by simply substituting $\mathbf{B}$ into \eqref{eq:bMatCondition1} and \eqref{eq:bMatCondition2}.
\end{proof}
 Let now $\mathbf{A}\in\mathrm{BH}(K+1,R)$. Then by using Lemma~\ref{lemma:1} we can generate matrix $\mathbf{B}$ whose rows represent a solution for $\bm{\beta}_k$ in $\mathbb{T}_B^{K+1}$. Therefore, we have that $P^* \leq K+1$. However, based on Lemma~\ref{lemma:kPlus1}, we have  $P^* \geq K+1$, and thus $P^* = K+1$.


\subsection{General case}
We  note that based on Lemma~\ref{lemma:1}, we can relax the condition \eqref{eq:bMatCondition1} and only search for matrices $\mathbf{B} \in \mathbb{T}^{(K+1)\times P}_R$ that satisfies \eqref{eq:bMatCondition2}. We call the set of such matrices partial BH  (PBH) matrices of order $(K+1,P)$ and complexity $R$ and denote it by $\mathrm{PBH}(K+1,P,R)$. It is evident that $\mathrm{PBH}(P,P,R) =\mathrm{BH}(P,R)$. Thus, since finding BH matrices, in general, is an open problem, so is finding PBH ones. 
One way to generate a $\mathrm{PBH}(K+1,P,R)$ is by selecting the first $K+1$ rows of a $\mathrm{BH}(P,R)$ matrix with $P\geq K+1$. In what follows we present a simple method to generate this BH matrix using the \ac{dft} matrices.

We define the set 
\begin{align}
    \mathcal{V}(R) = \Big\{\prod_{i=1}^Lp_i^{m_i}\geq K+1 \big\vert\,  m_i\in\mathbb{N} \Big\}
\end{align}
and determine $\tilde{v} = \min\{\mathcal{V}(R)\}  = \prod_{i=1}^Lp_i^{\tilde{m}_i}$.
Then 
$
    \mathbf{S} = \mathbf{F}_{p_1}^{\otimes \tilde{m}_1} \otimes \dots \otimes \mathbf{F}_{p_L}^{\otimes \tilde{m}_L}
$
is a $\mathrm{BH}(\tilde{v},R)$ matrix that satisfies \eqref{eq:bMatCondition1}. Therefore, one can set $\bm{\beta}_k^{\top}$ to the first $K+1$ rows of $\mathbf{S}$. In general, this solution may not be optimal. However, if $p_1\geq K+1$ then $\mathbf{S} = \mathbf{F}_{p_1}$, which, as proved in Sec.\,\ref{sec:caseII}, is the optimal solution.

\subsection{Summary}
We have shown for 5 special cases that optimal solutions can be found and provided a method to find such solution. For the general case, we can only provide a constructive method for finding feasible solutions, though without guarantee of optimality. 
\section{Simulation results}

\begin{figure}
    \centering
    \begin{tikzpicture}
    \node  [anchor=mid] (pic) {\includegraphics[width=5cm]{system.png}};
    \node (dist) at (.4, 1.4) {\footnotesize $10$m};
    \node (UE) at (2, 4) {\footnotesize RIS};
    \node (Rx) at (-1.5, 4.8) {\footnotesize Rx};
    \node (Bs) at (.4, 3) {\footnotesize BS};
    \end{tikzpicture}
    \caption{System setup with $8$ \acp{ris} and three Rxs located on a circle of radius $10$ m around the BS. The \acp{ris}  and Rxs are on $z=-3$~m and  $z=1$~m planes, respectively and BS is at origin.}
    \label{fig:system}
\end{figure}

\begin{figure}
    \centering
    \input{cdfs}
    \caption{ Cumulative distribution of root mean squared error ($e$ in meter) of the estimator over $100$ random realizations of RIS phase profiles. The results are presented for our method with  one-bit RIS phase resolution ($R=2$) and for the  method in \cite{keykhosravi2021semi}, followed by quantization with $R\in\{1,4,\dots,64\}$.  The theoretical lower bound is shown by the dashed line. }
    \label{fig:PebResults}
\end{figure}

In this section, we illustrate the effectiveness of the proposed method in mitigating the interpath interference in a semi-passive localization scenario from \cite{keykhosravi2021semi}. 
\subsection{Scenario}
In this setup we consider $K=8$  \acp{ris}, one \ac{bs} transmitting pilot signals, and $3$ receivers that receive the signal directly from the \ac{bs} and also the reflected signal from the \acp{ris}. The placement of each of the elements is depicted in Fig.\,\ref{fig:system}. We consider the transmission of \ac{ofdm} signals from the \ac{bs}. The parameters of the signal and noise can be found in \cite[Table\,I]{keykhosravi2021semi}. 
We set $Q=1$ and select $\bm{\zeta}_{k,0}$ randomly. 
We then estimate the location of each of the  $K$ \acp{ris} as follows. We first resolve the interpath interference at each \ac{rx} via  orthogonal coding of the \ac{ris} phase profiles as described in Section\,\ref{sec:RIS_phase_profile_design}. Then, we calculate the \ac{toa} of all the $K+1$ paths ariving at each of the \acp{rx} (see \cite[Sec.\,III-B]{keykhosravi2021semi}). Finally, we estimate the RIS location based on the calculated \acp{toa} (see \cite[III-C]{keykhosravi2021semi}).
\subsection{Fast-varying phase profiles}
With regard to the fast-varying part of the \ac{ris} phase profile (i.e, $\bm{\beta_k}$), we consider two different methods:
\begin{itemize}
    \item \emph{Proposed method:} The first method is based on our proposal in Section\,\ref{sec:fast_varying}, where we assume that \acp{ris} have one bit of phase resolution (i.e., $R=2$). Based on our results in Section\,\ref{sec:case:R2} we set $P=12$ and we let $\bm{\beta_k}$ be the rows of a $\mathrm{BH}(2,12)$ matrix (or equivalently, a $12\times 12$ Hadamard matrix).
    \item \emph{Benchmark:} With the second method, we ignore the limited phase resolution and  design  $\bm{\beta_k}$ as in Sec.\,\ref{sec:infb} and  \cite{keykhosravi2021semi}. For a fair comparison, we consider the same number of transmission as in the proposed method, i.e., $P=12$. Therefore, we set $\bm{\beta_k}$ to be the rows of the matrix $\mathbf{F}_{12}$. We consider six different phase resolutions $R\in\{2,4,8,16,32,64\}$. For each $R$, we map the values of $\beta_{k,p}$ (obtained from $\mathbf{F}_{12}$) to the closest point in $\mathbb{T}_R$ to account for limited phase resolution of the \acp{ris}. Such quantization impairs the orthogonality of $\bm{\beta_k}$. Therefore, we expect that the estimator cannot avoid interpath interference and its accuracy deteriorates. 
\end{itemize}
 

\subsection{Results and discussion}

In Fig.\,\ref{fig:PebResults}, we demonstrate the \ac{cdf} of the \ac{ris} position estimation error for $100$ random realizations of $\bm{\zeta}_{k,0}  \in \mathbb{T}^{N_{\mathrm{ris}}}_R$. We present the results for the \ac{ris} located at $(10, 0, -3)$.
As it can be seen, the performance degradation due to quantization is more severe with low values of $R$. On the other hand, our method takes into account the limited resolution of the \ac{ris} phase shifts and therefore, avoids any quantization effects.  It can be seen that via our proposed method, with only one-bit resolution, the estimator can attain the theoretical lower bound, which is calculated through \ac{fim} analysis \cite[Chapter~3]{kay1993fundamentals}. 


\section{Conclusion}
We proposed a method to resolve interpath interference in wireless systems equipped with multiple \acp{ris} with limited phase resolution. We did so by dividing the \ac{ris} phase profiles into a fast-varying and a slow-varying part and designing the former part to be orthogonal across \acp{ris}. We proposed a method to find such orthogonal sequences in general and discussed the special cases where such sequences are optimal (have the shortest length). Our solution can be applied to 
most system models considered in the literature. 
Future work can explore a trade-off between the interpath interference and number of transmissions ($P$) and look for sequences ($\bm{\beta_k} \in \mathbb{T}_R^P$) with minimum correlation for a given $P$.


\appendices
\section{Proof of Theorem 1} \label{app:Thm1}
Let $U = 4\lceil(K+1)/4\rceil$ and $P^*$ be the smallest value of $P$ that yields a solution.
From Conjecture\,\ref{conj:1} and Lemma~\ref{lemma:1}, we know that matrix $\mathbf{B}$ exists such that $\mathbf{B}\in \mathrm{BH}(U, 2)$ and $[\mathbf{B}]_1$ satisfies \eqref{eq:bVecCondition1}. Therefore, the first $K+1$ rows of $\mathbf{B}$ provide a solution for $\bm{\beta}_k$ (note that the dimension of $\mathbf{B}$ is at least $K+1$). Furthermore, from Lemma\,\ref{lemma:kPlus1} we know that $P^*\geq K+1$. 
To complete the proof, we need to  show that any $P$ that yields a solution for $\bm{\beta}_k$ must be a factor of $4$. The proof is in the same lines as the proof of Proposition~\ref{prop:2} in \cite[Sec.\,1.3.2]{laclair2016survey} and we present it here for completeness. 

 Based on \eqref{eq:bVecCondition1} and \eqref{eq:bVecCondition}, we have that $\bm{\beta}_2^\top\mathbf{1}_P=0$, therefore, $P$ should be even and  $\bm{\beta}_2$ contain equal number of $1$ and $-1$. Without loss of generality we can assume that  $\bm{\beta}_2=[\mathbf{1}_{P/2}^\top,-\mathbf{1}_{P/2}^\top]$. Then since $\bm{\beta}_3^\top\bm{\beta}_2=0$ we have that $\Sigma_1-\Sigma_2=0$, where $\Sigma_1$ ($\Sigma_2$) is the summation of all the elements in the first (second) half of vector $\bm{\beta}_3$. Furthermore, since $\bm{\beta}_3^\top\bm{\beta}_1=0$, we get $\Sigma_1+\Sigma_2=0$. Therefore, we have $\Sigma_1=\Sigma_2=0$ which proves that each half of the vector $\bm{\beta}_3$ must contain equal number of $1$ and $-1$. Therefore, the length of $\bm{\beta}_3$, which is $P$, must be divisible by $4$.

\section{Proof of Theorem 2} \label{app:Thm2}
Let $U=2\lceil(K+1)/2\rceil$ and $P^*$ be the smallest value of $P$ that yields a solution. Based on Corollary\,\ref{cor:two-to-r} and Lemma\,\ref{lemma:1}, there exists $\mathbf{B}\in \mathrm{BH}(U,2^r)$ whose first $K+1$ rows determine a solution for $\{\bm{\beta}_k\in\mathbb{T}_{2^r}^P\}_{k=0}^{K}$ (note that $U\geq K+1$). Therefore, $P^*\leq U$. 
Furthermore, from \eqref{eq:bVecCondition1} and  \eqref{eq:bVecCondition}, we have that  $\bm{\beta}_1^\top\mathbf{1}_{P^*} = 0$. Therefore, from Proposition\,\ref{prob:1} we have that $P^*\in \mathcal{W}(2^r)$, which is the set of positive even numbers (see \eqref{eq:Wdef}). Also, from Lemma\,\ref{lemma:kPlus1} we know that $P^*\geq K+1$. Therefore, $P^*$ must be larger than or equal to the smallest even number lager than $K+1$, that is $U$.
\begin{comment}
\begin{align}
    \begin{bmatrix}
     1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1\\
     1&-1& 1&-1& 1& 1& 1&-1&-1&-1& 1&-1\\
     1&-1&-1& 1&-1& 1& 1& 1&-1&-1&-1& 1\\
     1& 1&-1&-1& 1&-1& 1& 1& 1&-1&-1&-1\\
     1&-1& 1&-1&-1& 1&-1& 1& 1& 1&-1&-1\\
     1&-1&-1& 1&-1&-1& 1&-1& 1& 1& 1&-1\\
     1&-1&-1&-1& 1&-1&-1& 1&-1& 1& 1& 1\\
     1& 1&-1&-1&-1& 1&-1&-1& 1&-1& 1& 1\\
     1& 1& 1&-1&-1&-1& 1&-1&-1& 1&-1& 1\\
     1& 1& 1& 1&-1&-1&-1& 1&-1&-1& 1&-1\\
     1&-1& 1& 1& 1&-1&-1&-1& 1&-1&-1& 1\\
     1& 1&-1& 1& 1& 1&-1&-1&-1& 1&-1&-1
\end{bmatrix} 
\end{align}
\end{comment}




\vspace{-.5cm}


\bibliographystyle{IEEEtran}
