Nonbinary m-Sequences

m-sequences 在衛星導航系統中扮演重要的腳色，測距用的虛擬雜訊碼 (Pseudo-Random Code)基本上就是一種m-sequence。有關GPS訊號中PRN碼的設計可參考下面這個鏈結中的文件。

GPS訊號結構

一般的m-sequence大多為二進制(binary)，但也有非二進制的m-sequence。本篇主要介紹非二進制的m-sequence。欲生成一個非二進制的m-sequence，需要先建構一個extension field $GF(p^m)$，其中$p$是一個質數。在工程上最常用的extension field是$GF(2^m)$，可參考上述文章，有詳細介紹如何生成$GF(2^m)$。我們以一個實際的例子來說明，考慮一個二階的primitive polynomial $X^2+X+1$，則以此多項式生成之$GF(2^2)$ extension field包含四個元素，以冪次表示為$\{0, 1, \alpha, \alpha^2\}$，以多項式表示則為$\{0, 1, \alpha, \alpha^2 = 1 + \alpha\}$。也可以利用向量來表示，此時$GF(2^2) = \{(0,0), (0,1), (1,0), (1,1)\}$。接下來，我們考慮在$GF(2^2)$上的多項式，同樣地，為了方便說明，我們考慮一個二階的primitive polynomial $g(X)=g_0+g_1X+g_2X^2 = X^2+X+\alpha$。注意，因為我們現在考慮的是$GF(2^2)$上的多項式，因此$g(X)$的係數可以是$0, 1, \alpha,$ 或者$\alpha^2$。在本例中$g_0=\alpha, g_1 = 1, g_2=1$。接下來我們可以利用$g(X)$來產生一組非二進制m-sequence。若令$g(X)=0$，移項之後可得$X^2= X + \alpha$。若將$X$視為電路中的移位暫存器，$X^2$表示經過兩個移位暫存器(有關以移位暫存器來產生一個序列，同樣可參考上述連結中的文章)，則由上式可得到一個遞迴關係：$a_r = a_{r-1} + \alpha a_{r-2}$。若令$a_0=a_1=1$，由此遞迴關係可得到一個長度為$2^4-1 = 15$的非二進制m-sequence如下：
\[a_0a_1a_2a_3... = 11\alpha^210\alpha\alpha 1\alpha 0\alpha^2\alpha^2\alpha\alpha^2 0 \mbox{(repeat)} \]
但是，若想要利用數位電路來實現上述m-sequence，要如何產生$\alpha$這個符號，此時就需要借用$GF(2^2)$的向量表示，也就是說$\{0, 1, \alpha, \alpha^2\}$這四個符號都需要兩個位元來表示：$"0"\rightarrow 00$, $"1"\rightarrow 01$, $"\alpha"\rightarrow 10$, $"\alpha^2"\rightarrow 11$。如此一來，上述的非二進制m-sequence可以寫為：
\[01,01,11,01,00,10,10,01,10,00,11,11,10,11,00\]
解碼時必須兩個位元為一組進行解碼。

References
1. 王和盛, GPS接收機原理概論, unpublished manuscript.
2. S. Lin and D. J. Constello, Jr., Error Control Coding: Fundamentals and Applications, 2nd Edition, Prentice-Hall.