通訊序列大亂鬥

發表於 2025-10-14 更新於 2026-01-18 分類於通訊技術 Disqus：

What?

作為「通訊序列設計」的修課(回顧)筆記，也希望能將通訊序列有趣之處呈現出來。

「序列設計」和「波型設計」的概念很像，就是根據時域、頻域與ISI或ICI的條件，找出/設計滿足這些條件的序列。雖然，老師也強調未來工作上可能不需要自己設計序列(規格已經寫好)，但是一些數學概念、方法還是很有用的。

Basics

序列最重要的特性即為correlation，可以分為週期性或是非週期性。

Periodic Cross-Correlation Function (PCCF)

$$
\rho({\bf c}, {\bf d};\ u) =
\begin{cases}
\begin{align}
&\sum_{i = 0}^{L - 1}{C_{(i + u){\rm mod}\ L} D_i^{*}},\ \ &0 \leq u \leq L - 1\\[10pt]
&\sum_{i = 0}^{L - 1}{C_i D_{(i - u){\rm mod}\ L}^{*}},\ \ &-L + 1 \leq u < 0
\end{align}
\end{cases}
$$

Aperiodic Cross-Correlation Function (ACCF)

$$
\hat{\rho}({\bf c}, {\bf d};\ u) =
\begin{cases}
\begin{align}
&\sum_{i = 0}^{L - u - 1}{C_{i + u} D_i^{*}},\ \ &0 \leq u \leq L - 1\\[10pt]
&\sum_{i = 0}^{L + u - 1}{C_i D_{i - u}^{*}},\ \ &-L + 1 \leq u < 0
\end{align}
\end{cases}
$$

Autocorrelation的形式是一樣的，只要把序列換掉即可。一般來說，${\bf C}$ 會是一個polyphase sequence，即 $C_i = \xi^{c_i}$，其中 $\xi = e^{j2\pi/L}$，$c_i \in {\Bbb Z}_L$。此外，correlation還有以下的性質：

$\hat{\rho}({\bf c};\ -u) = \hat{\rho}^{*}({\bf c};\ u)$
$\rho({\bf c};\ -u) = {\rho}^{*}({\bf c};\ u)$
PACF和AACF的關係，

$$
\rho({\bf c};\ u) =
\begin{cases}
\begin{align}
&\hat{\rho}({\bf c};\ u) + \hat{\rho}^{*}({\bf c};\ L - u),\ \ &u \geq 0\\[10pt]
&\hat{\rho}({\bf c};\ u) + \hat{\rho}({\bf c};\ L + u),\ \ &u < 0
\end{align}
\end{cases}
$$
PCCF和ACCF的關係，

$$
\rho({\bf c}, {\bf d};\ u) =
\begin{cases}
\begin{align}
&\hat{\rho}({\bf c}, {\bf d};\ u) + \hat{\rho}^{*}({\bf d}, {\bf c};\ L - u),\ \ &u \geq 0\\[10pt]
&\hat{\rho}({\bf c}, {\bf d};\ u) + \hat{\rho}({\bf c}, {\bf d};\ L + u),\ \ &u < 0
\end{align}
\end{cases}
$$

當序列為binary，complex conjugate的符號 $*$ 可以省略，式子會更簡化。

在檢驗不同序列(集合)的時候會經常用到這些關係式。序列的分類一般而言就是用correlation的性質來劃分，比如說若滿足 $\rho({\bf c};\ u) = 0\ \forall u \neq 0$，則這個序列為一個perfect sequence，目前唯一已知的binary perfect sequence為

$$
{\bf c} = (0, 0, 0, 1)
$$

可說是非常稀有。若滿足 $\lvert\hat{\rho}({\bf c};\ u)\rvert \leq 1\ \forall u \neq 0$，則這個序列為一個Barker sequence，數量也不是很多。一些用來衡量序列correlation的指標，包括peak sidelobe level (PSL)，

$$
{\rm PSL}({\bf c}) = \frac{\max_{1 \leq u \leq L - 1}{\lvert \rho({\bf c};\ u)\rvert}}{\lvert \rho({\bf c};\ 0)\rvert}
$$

以及著名的PAPR，

$$
{\rm PAPR}({\bf c}) = \max_{0 \leq t \leq 1}{\frac{P_{\bf c}(t)}{P_{ave}}}
$$

其中 $P_{\bf c}(t) = {\lvert S_{\bf c}(t)\rvert}^2 = {\lvert \sum_{i = 0}^{L - 1}{C_i e^{j2\pi it}}\rvert}^2$。可以看得出來，絕對值裡的函數其實就是序列 $\bf C$ 經過IDFT、DAC後的波型(也就是OFDM波型啦)。因此，透過IFFT + oversampling (zero-padding)便可以算出序列的瞬時功率，再計算得到PAPR。

Sequence Sets

來看一些經典的序列集合，這些集合裡的序列共享著特殊的correlation性質，因此被湊在一塊。首先是最基礎的Golay complementary sets (GCS)，

$$
\sum_{i = 0}^{N - 1}{\hat{\rho}({\bf c_i};\ u)} =
\begin{cases}
\begin{align}
0,\ &u \neq 0\\[10pt]
NL,\ &u = 0
\end{align}
\end{cases}
$$

這樣的特性可以怎麼善用？根據這個特性，可以得到 $\sum_{i = 0}^{N - 1}{P_{\bf c_i}(t)} = NL$，表示 $P_{\bf c_i}(t) \leq NL$，即 ${\rm PAPR}(C) = \max_{ {\bf c} \in C}{ {\rm PAPR}{(\bf c)} } \leq N$，也就是控制了PAPR的上限。能夠得知PAPR上限是很重要的一件事，因為RF前端的功率放大器(PA)通常是運作在線性區(linear region)，如果PAPR過大，PA的平均輸出功率就必須降低，稱為output back-off (OBO)；並且運作在降低的工作點上，PA的功率使用效率也下降。(參考自Chieuh [2])

實驗A：用GCS建立一個可控PAPR的OFDM系統

未完成…。

1	printf("hello world");

圖A-1是不使用GCS codeword的OFDM波型，圖A-2是使用GCS codeword的OFDM波型。未完成…。

接著是GCS的延伸，complete complementary code (CCC)。兩個GCS $C^0$、$C^1$ 為正交，若且惟若

$$
\sum_{i = 0}^{N - 1}{\hat{\rho}({\bf c_i^0}, {\bf c_i^1};\ u)} = 0,\ {\rm for\ any}\ u
$$

此「正交性」也是定義在correlation sum之上的，和GCS的定義相仿。CCC即為 $M$ 組互相正交的GCS的集合，關係式如下：

$$
\sum_{i = 0}^{N - 1}{\hat{\rho}({\bf c_i^{k_1}}, {\bf c_i^{k_2}};\ u)} =
\begin{cases}
\begin{align}
&NL,\ &u = 0,\ k_1 = k_2\\[10pt]
&0,\ &u \neq 0,\ k_1 = k_2\\[10pt]
&0,\ &\forall u,\ k_1 \neq k_2
\end{align}
\end{cases}
$$

CCC裡相異GCS正交的特性，非常適合用在多載波的分碼多工系統(MC-CDMA)，每個使用者使用一組GCS，接收端做correlation時其他使用者的投影量為零，意即不受多重存取干擾(multiple-access interference，MAI)。

實驗B：用CCC模擬一個MC-CDMA系統

未完成…。

1	printf("hello world");

Z-complementary sequence sets (ZCS)則是更大的一個序列集合，而且和GCS、CCC不同，correlation為零的位移 $u$ 僅限於特定區域，稱為 zero-correlation zone。ZCS的特性如下：

$$
\sum_{i = 0}^{N - 1}{\hat{\rho}({\bf c_i^{k_1}}, {\bf c_i^{k_2}};\ u)} =
\begin{cases}
\begin{align}
&NL,\ &u = 0,\ k_1 = k_2\\[10pt]
&0,\ &0 < \lvert u\rvert < Z,\ k_1 = k_2\\[10pt]
&0,\ &\lvert u\rvert < Z,\ k_1 \neq k_2
\end{align}
\end{cases}
$$

和CCC的特性相似，只不過有ZCZ的限制。這邊提一下「optimal」的意思，當一個序列集合裡的序列數/集合數達到理論上限時，就稱它為optimal的序列集合。不同序列集合的序列數/集合數上限都不一樣。

實驗C：用ZCS模擬一個MC-CDMA系統，並和CCC比較

未完成…。

1	printf("hello world");

最後介紹zero-correlation zone sets (ZCZ set)。ZCZ sets的特性如下：

$$
\begin{cases}
\begin{align}
&\rho({\bf c_k};\ u) = 0,\ {\rm for}\ \leq \lvert u\rvert \leq Z\\[10pt]
&\rho({\bf c_k, c_l};\ u) = 0,\ {\rm for}\ \lvert u\rvert \leq Z
\end{align}
\end{cases}
$$

當中 $k \neq l$ 表示集合中的兩相異序列，注意ZCZ sets是定義在週期性自相關函數，而前面介紹的GCS、CCC、ZCS都是定義在非週期性自相關函數。ZCZ sets可以用在cell之間的載波頻率偵測。

這一節介紹了很多序列集合，其實它們彼此之間有所關連，一些集合是另一個集合的子集合。圖2呈現這些序列集合的關係。

圖2，各種序列集合的關係，改自上課講義。

Periodic Pairs

許多序列對有週期自相關函數的良好特性，通常是兩個序列的週期自相關函數的「和」滿足某些條件，如前述的ZCZ sets。Periodic complementary sets (PCS)就是一例，其特性如下：

$$
\sum_{i = 0}^{N - 1}{\rho({\bf c_i};\ u)} =
\begin{cases}
\begin{align}
0,\ &u \neq 0\\[10pt]
NL,\ &u = 0
\end{align}
\end{cases}
$$

其實也就是periodic GCS。如果集合裡只有一對序列，則稱為periodic complementary pair (PCP)。根據correlation的性質，一對GCP一定是PCP，但是一對PCP卻未必是GCP。因此，PCP的數量是多於GCP的。

期中project便是要尋找長度為74，82，90，106以及130的PCP。同學們的做法大概分為兩類：

參考論文A [3]，建立index set、尋找SDS，再將SDS轉換為序列。
參考論文B [4]，尋找符合條件的壓縮序列，再解壓縮、尋找PCP。

多數同學參考論文A，而我們這組參考論文B (因為它有附程式碼)。結果就我們這組沒找到半個序列對，因為

論文A使用orbit來建造index set，將搜尋空間大幅縮減，搜尋時間也相應減少；而論文B則是近乎exhaustive的搜尋，只有透過字典排序取最小、刪去等價序列的方式，來縮減搜尋空間，縮減程度小於論文A。
論文B壓縮-解壓縮的方法適用於長度 $L$ 有許多因數的情況，所以長度為74、82的序列並不適合這樣尋找。
論文A提供了長度74、82的生成orbit，只要確實實現論文的做法，是保證可以找到的。

好吧，講了這麼多都是失敗的藉口。那麼就來介紹一下index set和SDS的關係。所謂index set指的是，集合元素為序列中「-1」的位置，所以任一個序列都可以唯一對應到一個index set。如果序列對應到index set $X$，那麼correlation可以對應到什麼呢？答案是插值表(difference table)，數學表示為

$$
\delta_X(u) = \lvert (u + X) \cap X\rvert
$$

其中「$+$」為模 $L$ 加法。$\delta_X(u)$ 表示序列向右循環位移 $u$ 後，「-1」對應到「-1」的個數。假設 $\lvert X\rvert = r$，即序列共有 $r$ 個「-1」，我們可以整理出以下表格：

case	value
1 對應到 1	$L - 2(r - \delta_X(u)) - \delta_X(u)$
1 對應到 -1	$2(r - \delta_X(u))$
-1 對應到 -1	$\delta_X(u)$

因此週期自相關函數可以寫為

$$
\rho({\bf a};\ u) = L - 4(r - \delta_X(u))
$$

而序列對的週期自相關函數「和」可以寫為

$$
\rho({\bf a};\ u) + \rho({\bf b};\ u) = 2L - 4[r + s - (\delta_X(u) + \delta_Y(u))]
$$

因此，只要找到符合條件的index set pair，就等於找到對應的序列對。要符合什麼條件呢？就PCP而言，我們想要找到一組參數為 $(L;\ r,\ s;\ \lambda = \delta_X + \delta_Y)$ 的supplementary difference set (SDS)，滿足

$$
L = 2(r + s - (\delta_X(u) + \delta_Y(u)))\ \forall\ u \neq 0
$$

論文A就是透過尋找SDS來尋找PCP。期末project也有一些同學是用類似的方法尋找序列對，包括我(但我沒找到)。

接著來看optimal periodic almost-complementary pair (PACP)，$L$ 為偶數時特性如下：

$$
\lvert \rho({\bf c};\ u) + \rho({\bf d};\ u)\rvert =
\begin{cases}
\begin{align}
0,\ &1 \leq \lvert u\rvert < L/2\\[10pt]
4,\ &\lvert u\rvert = L/2\\[10pt]
2L,\ &u = 0
\end{align}
\end{cases}
$$

而 $L$ 為奇數時的optimal PACP特性如下：

$$
\lvert \rho({\bf c};\ u) + \rho({\bf d};\ u)\rvert =
\begin{cases}
\begin{align}
2,\ &1 \leq \lvert u\rvert \leq L/2\\[10pt]
2L,\ &u = 0
\end{align}
\end{cases}
$$

PACP是PZCP的optimal型態，當長度 $L$ 為偶數時，PACP correlation sum只在 $u = L/2$ 處為非零，其大小為4；當長度 $L$ 為奇數時，PACP correlation sum在非零的 $u$ 大小皆為2。期末project要找的就是PACP和PQCP，這部分就略過不提了。

最後是periodic quasi-complementary pair (PQCP)，特性如下：

$$
\lvert \rho({\bf c};\ u) + \rho({\bf d};\ u)\rvert \leq \epsilon,\ 1 \leq u \leq L - 1
$$

條件相當的寬鬆，PACP也是PQCP的子集。期末project要找的PQCP則是只有兩個非零位移的correlation sum為非零，條件比較嚴格。

Aperiodic Pairs

這一節介紹一些擁有非週期性特性的序列對。首先是ZCP，也就是ZCS裡只有一個集合，這個集合裡只有兩個序列的例子。不同於GCP的長度受限，任何長度的binary ZCP都存在。Z的區間大小則有上限：

$$
\begin{cases}
\begin{align}
&Z \leq \frac{L + 1}{2},\ &\text{L is even}\\[10pt]
&Z \leq L - 2,\ &\text{L is odd}
\end{align}
\end{cases}
$$

那麼要怎麼建構ZCP呢？如果我們有ZCP的kernel，就可以根據這些kernel來建構相同長度or更長的ZCP。Kernel不能從較短長度的序列得到，也不能對相同長度的序列做基本操作(如negation、negating alternatively)得到，要找到就比較困難，不過找到之後可以衍生出相同長度或較長長度的ZCP，一些基本的做法如

以特定方式串接 (concatenation) 兩序列。
交錯 (interleaving) 兩序列。假設 $({\bf A}^0,\ {\bf B}^0)$ 為一 $(L,\ Z)\text{-ZCP}$，則

$$
({\bf A}^n,\ {\bf B}^n) = ({\bf A}^{n - 1}\star {\bf B}^{n - 1},\ {\bf A}^{n - 1}\star ({\bf -B}^{n - 1}))
$$

為一 $(2^nL,\ 2^nZ)\text{-ZCP}$。
使用Kronecker product，詳參講義。

接著是擁有兩端ZCZ的SZCP，S是symmetric的意思，特性如下：

$$
\hat{\rho}({\bf c};\ u) + \hat{\rho}({\bf d};\ u) =
\begin{cases}
\begin{align}
2L,\ &u = 0\\[10pt]
0,\ &0 < \lvert u\rvert < Z\\[10pt]
0,\ &L - Z < \lvert u\rvert \leq L - 1
\end{align}
\end{cases}
$$

當 $L$ 為偶數且 $Z = L/2$，則這個SZCP為optimal，此時 $\lvert \text{AACS}({\bf c}, {\bf d};\ u)\rvert = 2$。看起來和偶數長度的optimal PACP相似，不過PACP是定義在週期性特性，而SZCP定義在非週期性特性。

最後來看cross Z-complementary pair (CZCP)，顧名思義它是定義在cross-correlation的，和ZCS有些相似。CZCP使用兩個ZCZ區間，${\it T_1}$ 和 ${\it T_2}$，

$$
\begin{align}
{\it T_1}&\equiv \{1, 2, \cdots, Z\}\\[10pt]
{\it T_2}&\equiv \{L - Z, L - Z + 1, \cdots, L - 1\}
\end{align}
$$

CZCP必須滿足兩個條件，

$$
\begin{align}
&(C_1)\ \ \hat{\rho}({\bf c};\ u) + \hat{\rho}({\bf d};\ u) = 0,\ \ &\lvert u\rvert \in {\it T_1}\cup{\it T_2}\\[10pt]
&(C_2)\ \ \hat{\rho}({\bf c}, {\bf d};\ u) + \hat{\rho}({\bf d}, {\bf c};\ u) = 0,\ \ &\lvert u\rvert \in {\it T_2}
\end{align}
$$

等於說AACS有前後兩塊ZCZ，而ACCS只有後面那塊ZCZ。這種特別的性質，正好可以用在single-carrier spatial modulation (SC-SM)系統，可以消除ISI和ICI。

實驗D：CZCP及其他序列對在SC-SM系統的應用

未完成…。

1	printf("hello world");

Boolean Functions

布林函數可以用來建構序列集合，如 $f(x_1, x_2, x_3) = x_1 x_2 + x_3$，「$+$」為模2加法。每一個布林函數都可以對應到一個長度為 $2^m$ 的序列，

$$
{\bf F} = (f_1, f_2, f_3, \cdots, f_{2^m - 1})
$$

當中 $f_i = f(i_1, i_2, \cdots, i_m)$ 為這個布林函數對數字 $i$ 的mapping，${(i)}_{10} = {(i_1, i_2, \cdots, i_m)}_2$。序列 ${\bf F}$ 也可以寫為

$$
{\bf F} = f({\bf x_1}, {\bf x_2}, \cdots, {\bf x_m})
$$

其中 ${\bf x_k}$ 為 $0 \sim 2^m - 1$ 每個二進位數字的第 $k$ 個bit所組成的向量。這樣的表示方法在MATLAB用點乘是比較方便的。Generalized Boolean function則把對應域擴展到 ${\Bbb Z}_q$，所以形如

$$
f(x_1, x_2, x_3) = 3x_1 x_2 + 4x_3\ \ ({\rm mod}\ 5)
$$

的布林函數存在(變成模 $q$ 加法)。

實驗E：用布林函數建立一組GCS

未完成…。

1	printf("hello world");

Generalized Reed-Muller Codes

Golay-Davis-Jedwab Complementary Pair (GDJ pair)

Concluding words

這門課的兩次project，我(個人)都沒有找到任何序列。第一次project要尋找PCP，第二次project要尋找PACP和PQCP，幸好第二次project我的組員有一些成果，原來是我在雷啊！

由於時間不夠，課程沒有講完GDJ pair和後面的部分。不過有了這些基礎，之後再閱讀通訊序列相關的論文，應該是遊刃有餘。

Reference

[1] 上課講義。

[2] T.D. Chiueh, et al, Baseband Receiver Design for Wireless MIMO-OFDM Communications. John Wiley & Sons Singapore Pte. Ltd, 2012.

[3] D. Ž. Doković and I. S. Kotsireas, “Some new periodic Golay pairs,” Numer. Algorithms, vol. 69, no. 3, pp. 523–530, Sep. 2015.

[4] T. Lumsden, I. Kotsireas, and C. Bright, “New results on periodic Golay pairs,” Math. Comput., Apr. 2025.