# Polynomial Cancellation Coded DFT-s-OFDM for Low-PAPR Uplink Signaling
## 3 Analysis of PCC-DFT-s-OFDM
### Computational Complexity  
In this subsection, we analyze the computational complexity increase of PCC-based DFT precoding compared with conventional DFT precoding. According to (1) and (2), the PCC-based DFT precoded data vector \(\mathbf{X}=\left[X_{0},\ \ldots,\ X_{M-1}\right]^{T}\) can be rewritten as:  
\[\mathbf{X}=\mathbf{\mathcal{F}}_{M}\mathbf{\mathcal{P}}\mathbf{s}, \tag{16}\]  
where \(\mathbf{\mathcal{F}}_{M}\) is the \(M\)-by-\(M\) DFT matrix, \(\mathbf{s}=\left[s_{0},\ \ldots,\ s_{M-1}\right]^{T}\) is the input PSK/QAM symbol vector, and \(\mathbf{\mathcal{P}}\) is an \(M\)-by-\(P\) PCC mapping matrix whose entries are zeros except \(\mathcal{P}\left(2^{d}m,m\right)=\left(-1\right)^{u},\ \ldots,\ \mathcal{P}\left(2^{d}m+u,m \right)=\left(-1\right)^{u}\) for \(0\leq m\leq M-1\) and \(0\leq u\leq 2^{d}-1\). The PCC demapping matrix is given by \(\mathbf{\mathcal{P}}^{\ddagger}\), where \(\left[\cdot\right]^{\dagger}\) is the Moore-Penrose inverse. By mathematically evaluating the matrices \(\mathbf{\mathcal{P}}\) and \(\mathbf{\mathcal{P}}^{\ddagger}\), the PCC mapping and demapping increase \(M\) complex multiplications for the transmitter and \(P\left(2^{d}-1\right)=M\left(1-2^{-d}\right)\) complex additions for the receiver. However, since each PSK/QAM symbol only needs one complex multiplication to generate the results of \(d\)-order PCC-mapped symbols, the increased number of complex multiplications for the transmitter can be further reduced to \(P=M/2^{d}\). Therefore, the comparison of computational complexity between conventional DFT precoder/deprecoder and PCC-based one can be summarized as Table 1. As seen, PCC-based DFT precoding requires \(\mathcal{O}\left(M^{2}\right)\) operations whose complexity is consistent with conventional DFT precoding, where \(\mathcal{O}\left(\cdot\right)\) is the Big-O notation. That is, the computational complexity increase of DFT precoding is almost negligible when PCC is applied. This makes PCC-DFT-s-OFDM more compatible with existing  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Computational Complexity**} & \multicolumn{3}{c}{**Conventional DFT Precoding (\(d\)=0)**} & \multicolumn{2}{c}{**PCC-Based DFT Precoding (\(d\)>0)**} \\ \cline{2-6}  & & **Function** & **Big-O 1** & **Function** & **Big-O 1** \\ \hline Number of complex & Tx & \(M^{2}\) & \(\mathcal{O}\left(M^{2}\right)\) & \(M2^{-d}+M^{2}\) & \(\mathcal{O}\left(M^{2}\right)\) \\ multiplications & Rx & \(M^{2}\) & \(\mathcal{O}\left(M^{2}\right)\) & \(M^{2}\) & \(\mathcal{O}\left(M^{2}\right)\) \\ \hline Number of complex & Tx & \(M(M-1)\) & \(\mathcal{O}\left(M^{2}\right)\) & \(M(M-1)\) & \(\mathcal{O}\left(M^{2}\right)\) \\ additions & Rx & \(M(M-1)\) & \(\mathcal{O}\left(M^{2}\right)\) & \(M\left(1-2^{-d}\right)+M(M-1)\) & \(\mathcal{O}\left(M^{2}\right)\) \\ \hline \hline \end{tabular}  
* Both operations can be reduced to \(\mathcal{O}\left(M\log_{2}M\right)\) if split-radix fast Fourier transform (FFT) is applied.  
\end{table}
Table 1: Comparison of computational complexity between the conventional discrete Fourier transform (DFT) precoding and polynomial cancellation coding (PCC)-based DFT precoding.  
Figure 3: Example impulse responses \(G_{k}^{d}\) with \(N=512\) and \(M=48\) for (**a,b**) \(d=1\) (**c,d**) \(d=2\), and (**e,f**) \(d=3\). Since \(G_{k}^{d}\) is complex-valued, its real/imaginary parts and amplitude (in linear/log scale) are shown separately.