OFDM筆記-5: Cyclic Prefix

Content

介紹 OFDM 系統不可或缺的 CP。其實我也不知道為什麼要特地把 CP 的介紹獨立為一篇文章，也許是因為 OFDM 系統非常依賴 CP 的緣故吧！並且 CP 的概念也用在其他調變方式，如 OTFS，所以深入理解 CP 絕對是有利無害的。

以下是OFDM筆記全系列的文章：

• OFDM筆記-1: OFDM簡介
• OFDM筆記-2: 通道模型
• OFDM筆記-3: OFDM模擬-Python
• OFDM筆記-4: OFDM模擬-C++
• OFDM筆記-5: Cyclic Prefix
• OFDM筆記-6: 待解決的問題

  CP 作為 guard interval，將 linear convolution 轉變為 circular convolution、進而簡化 OFDM 接收端等化器設計的故事，大家已經耳熟能詳了。所以這篇文章會介紹 CP 的其他應用。

同步

  OFDM 在頻率上 (carrier frequency offset，CFO) 以及時間上 (symbol timing offset，STO) 都需要同步，否則無法還原傳送的符號。這一節分享的是[1]這篇 1997 年的經典論文，同時處理 CFO 和 STO 的問題。在過去的文獻(相較於此論文)裡，Moose (1994) 假設 STO 為已知，在頻域計算 CFO 的 ML 估計，不過有一些 training symbol 長度的限制；Nogami (1995) 等人採用加入 null symbol 來估計 STO 的方法，但是這個方法在傳送 burst 的時候不管用。這篇論文改良 Classen (1994) 的做法，一種方法解決兩個問題。

  讀完才發現這篇論文其實不是 CP 的應用，不過姑且還是和 CP 有關。論文首先說明如何解決 STO，接著描述如何解決 CFO，兩者都是基於一組 training sequence 的設計。

STO

  在一個 frame 的開頭設計一個 training symbol，稱作 TS1。TS1 的 useful part 長度為 2L，前 L 個 sample 和後 L 個 sample 一模一樣。這要如何得到？回想一下，如果在時域作 upsampling 兩倍，對應到頻域就是頻譜相對原點收縮兩倍。根據對偶性，在頻域作 upsampling 兩倍，就會對應到時域重複的兩半。

圖A，在頻域 upsampling。

  接收端收到基頻的 sample $r_i$ 後，計算長度為 2L 的 sliding window 裡，前半和後半的 correlation ($d$ 為 sliding window 裡第一個 sample 時間)，

$$
\begin{align}
&P(d) = \sum_{m = 0}^{L - 1}{r_{d + m}^{*} r_{d + m + L}}\\[10pt]
&P(d + 1) = P(d) + r_{d + L}^{*} r_{d + 2L} - r_{d}^{*} r_{d + L}
\end{align}
$$

  如果 start time 完全沒有誤差，或是在 CP 長度減去通道長度的範圍內(見圖B)，$\lvert P(d)\rvert$ 都會是最大值。定義 $R(d) = \sum_{m = 0}^{L - 1}{\lvert r_{d + m + L}\rvert^2}$ 作為正規化的常數，我們可以定義 timing metric $M(d)$ 來表示 STO 造成的影響，

$$
M(d) = \frac{\lvert P(d)\rvert}{R(d)}
$$

  圖C呈現 start time 與 timing metric 的關係，$N_{\text{fft}} = 1024$，$N_{\text{CP}} = 128$。注意到有一段平坦的區間，就是前述 CP 形成的範圍，start time 在這段區間內誤差為零(但會引入固定的相位差)。

圖B，start time 的選取範圍。
圖C，timing metric vs start time，取十次模擬的平均值。

  假設接收到的 sample 可以分為訊號和雜訊的成分，$r_i = s_i + n_i$，$E\left[\lvert s_i\rvert^2\right] = 2\sigma_s^2$，$E\left[\lvert n_i\rvert^2\right] = 2\sigma_n^2$。經過一番推敲，論文提出在 correct timing 的情況下，timing metric 為常態分布，期望值為

$$
E\left[M(d_{\text{opt}})\right] = \frac{\sigma_s^2}{\sigma_s^2 + \sigma_n^2}
$$

  意味著 SNR 愈大，$E\left[M(d_{\text{opt}})\right]$ 愈趨近於 1，很合理。論文也提出對 SNR 的一個估計器，

$$
\hat{\text{SNR}} = \frac{M(d_{\text{opt}})}{1 - M(d_{\text{opt}})}
$$

  這個估計器在低 SNR 時比較準確。因此，接收端可以從 timing metric 來估計 SNR，判斷是否解讀訊號，或是將 SNR 的資訊回傳給發射端(雖然這好像和 start time 的選取比較沒關係)。

  論文提供兩個尋找最佳 start time 的方法：找 timing metric 最大值的時間點，或是找最大值左右兩個 90% 最大值的點，再取兩點中心。後者的效果比較好，不過兩種方法都要求先找到峰值。

CFO

  假設 CFO 為 $\Delta f$，則 TS1 的前後半剛好相差一個固定的相位 $\phi = \pi T\Delta f$，$T$ 是子載波間距的倒數。$\phi$ 可以由前面提到的 $P(d)$ 來估計(假設 STO 的問題已經解決)，

$$
\hat{\phi} = \angle P(d)
$$

  然而這裡有個問題：如果實際的頻率位移 $\lvert\Delta f\rvert > \frac{1}{T}$，單從 $\hat{\phi}$ (定義在 $-\pi$ 到 $\pi$ 之間)是無法得知的。更一般的情形可以寫作

$$
\Delta f = \frac{\hat{\phi}}{\pi T} + \frac{2k}{T}
$$

  可以看成是整數部分和小數部分的表示。要估計 $\Delta f$，我們需要第二個 training symbol TS2。TS2 的每一個子載波皆載有 PN 序列 (TS1 則只有偶數編號的子載波載有 PN 序列)。首先先補償 $\hat{\phi} / \pi T$ 的相位差，接下來的目標就是估計 $2k / T$。

  令 $X_{1, i}$ 和 $X_{2, i}$ 分別表示 TS1 和 TS2 各個子載波承載的符號，當然 $X_{1, i}$ 只有在 $i$ 為偶數的時候有值；$X_{2, i}$ 則是每個 $i$ 都有值。定義 $v_i$ 為 $X_{2, i} / X_{1, i}$，$i$ 為偶數，也就是說它是 differential 的。現在來看看 $v_i$ 在頻率位移下的變化：頻率位移後，$v_i’ = v_{(i + 2k)_N}$，經歷了 cyclic shift，所以 correlation 的概念一樣可以用於頻率位移的估計。定義頻率位移 metric 為

$$
B(k) = \frac{\lvert\sum{ {X’_{1, (i + 2k)_N}}^{*}\ {v’_i}^{*}\ X’_{2, (i + 2k)_N}}\rvert^2}{2\left(\sum{\lvert X_{2, i}\rvert^2}\right)}
$$

  而 $\hat{k} = \arg{\max_{k}{B(k)}}$。看起來有點複雜，不過和 timing metric 的概念是一樣的，就有點像齒輪的嵌合，選擇合適的 $\hat{k}$ 就可以讓 $B(k)$ 分子的每一項相位為零。這部分好像比較像是 detection 而不是 estimation。

通道估測

  CP 也可以用於通道估測。這一節分享[2]這篇 1999 年的論文，使用 CP 來作 blind channel estimation，也就是不使用 training symbol 的作法。論文首先強調 CP-OFDM 時域波型的 cyclostationarity 性質。令 $P = N + N_{\text{cp}}$，並以 polyphase representation 來表示哪一個 block 的哪一個 sample，$x_p[n] = x[n P + p]$。據此，OFDM 時域波型可以寫為

$$
x_p[n] = \frac{1}{N} \sum_{m = 0}^{N - 1}{s_m[n] e^{j\frac{2\pi}{N} m(p - N_{\text{cp}})}},\ \ 0 \leq p \leq P - 1
$$

  而其自相關函數可以寫為(假設 $E\left[s_m[n] s^{*}_r[n]\right] = \sigma_s^2 \delta[m - r]$)

$$
\begin{align}
c_{xx}[nP + p;\ \tau] &= E\left[x_{p + \tau}[n] x^{*}_p[n]\right] \sum_{\zeta = 0}^{P - 1}{\delta[\zeta - (p + \tau)]}\\[10pt]
&= \frac{1}{N^2} \sum_{m = 0}^{N - 1}{\sum_{r = 0}^{N - 1}{E\left[s_m[n] s^{*}_r[n]\right] e^{j\frac{2\pi}{N} m(p + \tau - N_{\text{cp}})} e^{-j\frac{2\pi}{N} r(p - N_{\text{cp}})}}} \sum_{\zeta = 0}^{P - 1}{\delta[\zeta - (p + \tau)]}\\[10pt]
&= \frac{\sigma_s^2}{N^2} \sum_{m = 0}^{N - 1}{e^{j\frac{2\pi}{N} m\tau}} \sum_{\zeta = 0}^{P - 1}{\delta[\zeta - (p + \tau)]}\\[10pt]
&= \frac{\sigma_s^2}{N} \left(\delta[\tau] + \delta[\tau - N]\sum_{\zeta = 0}^{P - N - 1}{\delta[\zeta - p]} + \delta[\tau + N]\sum_{\zeta = N}^{P - 1}{\delta[\zeta - p]}\right)
\end{align}
$$

  $\sum{\delta[\zeta - (p + \tau)]}$ 是用來限制 $0 \leq p + \tau \leq P - 1$ (我還是第一次看到這種操作)。上面這個式子說明 $c_{xx}$ 是 $p$ 和 $\tau$ 的函數，但是注意它不是 $n$ 的函數，表示每經過週期 $P$，$c_{xx}$ 就會開始重複，因此為 cyclostationary。

  經過 LTI 系統，cyclostationarity 的性質不變，就不附上推導過程了 ($L$ 是通道長度)：

$$
c_{rr}[nP + p;\ \tau] = \sum_{\zeta = 0}^{L - 1}{\sum_{\substack{q =\\ \tau - \zeta - (L - 1)}}^{\tau - \zeta}{h[\zeta] h^{*}[\zeta - \tau + q] c_{xx}[nP + p - \zeta;\ q]}} + \sigma_n^2 \delta[\tau]
$$

  計算它的 DTFS expansion $C_{rr}[k;\ \tau]$，論文作者稱其為 cyclic correlation。基本上，時域的自相關函數對應到頻域的功率頻譜，不過 cyclic correlation 描述時間變數 $p$ 的週期性質，而不是時間差變數 $\tau$，所以不能解讀為功率頻譜；$C_{rr}[k;\ \tau]$ 可以理解為「變化週期為 $P / k$ 的自相關模式」。說真的搞不太懂它的物理意義。

$$
C_{rr}[k;\ \tau] = \frac{1}{P} \sum_{p = 0}^{P - 1}{c_{rr}[nP + p;\ \tau] e^{-j\frac{2\pi}{P} kp}}
$$

越讀腦袋越亂，而且論文裡有些式子沒寫好，要自己推敲一番。
圖片來源：tenor.com，連結

  最後，再對時間差變數 $\tau$ 作 z-transform，得到 $S_{rr}(k;\ z)$ (cyclic spectrum)。由於 $C_{rr}$ 可以寫成

$$
C_{rr}[k;\ \tau] = \left(h[\tau] e^{-j\frac{2\pi}{P} k\tau}\right) \star h^{*}[-\tau] \star C_{xx}[k;\ \tau]
$$

  故

$$
S_{rr}(k;\ z) = H(e^{j\frac{2\pi}{P} k} z) H^{*}((z^{-1})^{*}) S_{xx}(k;\ z)
$$

  $S_{xx}$ 為已知，$S_{rr}$ 則可以在接收端得到(估計)，$H(z)$ 則可以透過選取兩個合適的 $k_i$，再經過一番運算得到。圖D呈現 $L = 7$，$N = 64$，$N_{\text{cp}} = 8$ 的情況下，$\lvert S_{rr}\rvert$ 的形狀。($z$ 由 $e^{j\omega}$ 代換。)

圖D，$\lvert S_{rr}(k;\ e^{j\omega})\rvert$ 頻譜。

  這篇論文我覺得讀來相當吃力，也許是耐不住性子慢慢推導吧，和 Google Gemini 討論才對它有些想法。簡單來說，因為加入了 CP，傳送訊號與接收訊號為 cyclostationary，等於是增加了不同 $k_i$ 所提供的條件(資訊)，方能解出 $H(z)$。Blind estimation 不使用 pilot symbol，因此最大化既有的頻譜使用效率；但是估計 $S_{rr}$ 需要時間，無法應用於高速變化的通道，演算法複雜度高，不如 pilot-aided 的方法簡單有效。不過，在不可能知道 pilot 資訊的情況下，如監偵軍事情報，可能還是需要 blind estimation (thoughts from Google Gemini)。

其他

  這一節我們提出一個問題：OFDM 難道就非 CP 不可嗎？ 在[3]這篇論文中提出用於 ZP-OFDM 系統的等化器設計，也比較了 CP 和 ZP 的優缺點。這篇論文以相當簡潔的方式表示 CP-OFDM：假設傳送的第 $i$ 個 block 符號為 ${\bf s}(i)$，則接收到的 sample 可以寫作

$$
{\bf r}(i) = {\rm H} {\rm F}_{\text{cp}} {\bf s}(i) + {\rm H}_{\text{IBI}} {\rm F}_{\text{cp}} {\bf s}(i - 1) + {\bf n}(i)
$$

  當中 ${\rm F}_{\text{cp}}$ 是加上 CP 部分的 IDFT 矩陣，$\rm H$ 是代表通道的下三角矩陣，${\rm H}_{\text{IBI}}$ 是代表 inter-block interference 的上三角矩陣。ZP-OFDM 也是一樣的形式：

$$
\begin{align}
{\bf r}(i) &= {\rm H} {\rm F}_{\text{zp}} {\bf s}(i) + {\rm H}_{\text{IBI}} {\rm F}_{\text{zp}} {\bf s}(i - 1) + {\bf n}(i)\\[10pt]
\text{(ZP 作為 postfix)}\ &= {\rm H} {\rm F}_{\text{zp}} {\bf s}(i) + {\bf n}(i)\\[10pt]
&= {\rm H_0} {\rm F}_N^H {\bf s}(i) + {\bf n}(i)
\end{align}
$$

  其中 $\rm H_0$ 由 $\rm H$ 的前 $N$ 個行向量組成，也是因為將 ZP 作為 postfix 而得以簡化。注意 $P\times N$ 矩陣 $\rm H_0$ 的行向量為線性獨立，因此可以計算它的 left inverse $\rm H_0^{\dagger}$ 還原時域訊號 (ZF equalizer)。相較於 CP-OFDM 在頻域執行 one-tap equalization，ZP-OFDM 在時域的 equalizer 不會有 deep-fading 的問題，因此可以還原每一個子載波的符號 (full diversity gain)；當然 CP-OFDM 的接收機複雜度就比 ZP-OFDM 簡單許多，正所謂 trade-off 不可避，好的 performance 一定伴隨著相當的代價。

  論文提出兩種 ZP-OFDM 的等化器設計，ZP-OFDM-OLA 和 ZP-OFDM-FAST，後面的十頁大家就自己去讀。從圖表得到的結論是，ZP-OFDM-OLA 的效果和 CP-OFDM 差不多，ZP-OFDM-FAST 的錯誤率在未編碼的情況下比 CP-OFDM 多出 2 ~ 3 dB 的增益，有編碼的話差異就減少到 1 dB 以內；不過模擬預設的通道也可能是 performance 差異的重要原因。

結語

  我一直覺得 CP 是很優美的設計，它的形式很簡單，功能卻非常強大。雖然本文舉出 CP-OFDM 的一些缺點，但是別忘了LTE-advanced、5G 和 Wifi 都是基於 CP-OFDM，顯然經過工程考量，CP 還是比較有優勢的。也許在 OTFS 系統，CP 也能大展身手。

參考資料

[1] T. M. Schmidl and D. C. Cox, “Robust frequency and timing synchronization for OFDM,” in IEEE Transactions on Communications, vol. 45, no. 12, pp. 1613-1621, Dec. 1997.

[2] R. W. Heath and G. B. Giannakis, “Exploiting input cyclostationarity for blind channel identification in OFDM systems,” in IEEE Transactions on Signal Processing, vol. 47, no. 3, pp. 848-856, March 1999.

[3] B. Muquet, Zhengdao Wang, G. B. Giannakis, M. de Courville and P. Duhamel, “Cyclic prefixing or zero padding for wireless multicarrier transmissions?,” in IEEE Transactions on Communications, vol. 50, no. 12, pp. 2136-2148, Dec. 2002.