伽罗华域下的伪随机序列图像编码

大创

---

一篇TPAMI文章Determining Both Surface Position and Orientation in Structured-Light-Based Sensing，用伪随机序列来编码图像，简单从下面三部分介绍：

---

1、伪随机序列（PN序列）

先科普一下伪随机噪声，伪随机噪声具有类似于随机噪声的某些统计特性，同时又能重复产生，主要未来实现高可靠的保密通信，特别是在CDMA系统中作为扩频码已成为CDMA技术中的关键问题。目前广泛应用的伪随机噪声都是由周期性数字序列经过滤波等处理后得到的。这种周期性数字序列成为伪随机序列，同时又称为伪随机信号或者伪随机码。

伪随机序列的分类：m序列、M序列、二次剩余序列、双素数序列

伪随机序列的性质（以m序列为例）：

1. 均衡性 在m序列的一个周期中，1和0的数目基本相等，准确的说是，“1”的个数比“0”的个数多一个。
2. 游程分布 什么是游程呢？可不是梦游的路程哦！我们把一个序列中取值相同的那些相继的（连在一起的）元素合称为一个“游程（run）”。一个游程中元素的个数称为游程长度。一般来说，在m序列中。长度为1 的游程占游程总数的1/2，长度为2的游程占游程总数的1/4，长度为3的游程占1/8。即长度为k的游程数目占游程总数的$2^{-k}$次幂。
3. 移位相加特性 一个m序列M与其经过任意次延迟移位产生的另一个不同序列Mr模2相加，得到的仍是M的某次延迟移位序列Ms。
4. 自相关特性 自相关特性具有周期性，周期为m。
5. 功率谱密度 对m序列的自相关函数作傅里叶变换，求出其功率谱密度。
6. 伪噪声特性 由于m序列的这些特性与伪随机序列的性质是相似的，所以m序列被称为伪随机序列，同时具有上述性质的也都被称为伪随机序列。

---

2、 伽罗华域

伽罗华（也译作伽瓦罗），法国数学家，群论的创立者。用群论彻底解决了根式求解代数方程的问题，而且由此发展了一整套关于群和域的理论，先介绍几个概念。

2.1 域

一组元素的集合，以及在集合上的四则运算，构成一个域。其中加法和乘法必须满足交换、结合和分配的规律。加法和乘法具有封闭性，即加法和乘法结果仍然是域中的元素。
域中必须有加法单位元和乘法单位元，且每一个元素都有对应的加法逆元和乘法逆元。但不要求域中的 0有乘法逆元。

2.2 有限域

仅含有限多个元素的域。因为它由伽罗华所发现，因而又称为伽罗华域。
所以当我们说伽罗华域的时候，就是指有限域。
$GF(2^w)$表示含有$2^w$个元素的有限域。

2.3 本原多项式

域中不可约多项式是不能够进行因子分解的多项式， 本原多项式 （primitive polynomial）是一种特殊的不可约多项式。当一个域上的本原多项式确定了，这个域上的运算也就确定了。本原多项式一般通过查表可得，同一个域往往有多个本原多项式。
通过将域中的元素化为多项式形式，可以将域上的乘法运算转化为普通的多项式乘法再模本原多项式。

提到多项式以及本原多项式，就难免会涉及多项式的运算，这样才能确定是否为本原多项式。

2.4 多项式运算

由于$GF(2^w)$上的四则运算是基于多项式运算的，这里先介绍多项式运算。
多项式一般长这个样子：

$$f(x)=x^6+x^4+x^2+x+1$$

2.4.1 多项式加减法

将两个多项式中相同阶数的项系数相加或相减。例如

$$(x^2+x)+(x+1)=x^2+2x+1$$

2.4.2 多项式乘法

将其中一个多项式的各项分别与另一个多项式的各项相乘，然后把相同指数的项的系数相加。例如

$$(x^2+x)\times (x+1)=x^2(x+1)+x(x+1)=x^3+x^2+x^2+x$$

2.4.3 多项式除法

使用长除法。例如计算$x^3-12x^2-42$除以$x-3$。使用长除法计算，商$x^2-9x-27$，余数$-123$。

2.4.4 $GF(2^w)$上的多项式运算

对于$GF(2^w)$上的多项式计算，多项式系数只能取0或1。（如果是$GF(3^w)$，那么系数可以取 0、 1、 2）

$GF(2^w)$的多项式加法中，合并阶数相同的同类项时，由于0+0=0,1+1=0,0+1=1+0=1，因此系数不是进行加法操作，而是进行异或操作。

$GF(2^w)$的多项式减法等于加法，例如$x^4 – x^4$就等于$x^4 + x^4$。

1、有限域$GF(p)$：有限域$GF(p)$，其中$p$为素数。
2、有限域$GF(2^w)$：实际应用中，很多场合需要 0到255这256个数字能组成一个域。但256不是素数，小于256的最大素数为251，如果直接把大于等于251的数截断为250，则会丢失一部分数据。因此引入了$GF(p^w)$，其中$p$为素数，通常取$p=2$。计算机领域中经常使用的是$GF(2^8)$，8刚好是一个字节的比特数。

伽罗华域的元素可以通过该域上的本原多项式生成。通过本原多项式得到的域，其加法单位元都是 0，乘法单位元是1。

以$GF(2^3)$为例，指数小于3的多项式共8个： $0， 1， x， x+1， x^2， x^2+1， x^2 + x， x^2+x+1$。其系数刚好就是000,001, 010, 011, 100, 101, 110, 111，是0 到7这8个数的二进制形式。

$GF(2^3)$上有不只一个本原多项式，选一个本原多项式$x^3+x+1$，这8个多项式进行四则运算后 mod $(x^3+x+1)$的结果都是8个之中的某一个。因此这8个多项式构成一个有限域。

通过本原多项式生成元素
设$P(x)$是$GF(2^w)$上的某一个本原多项式，$GF(2^w)$的元素产生步骤是：

1、给定一个初始集合，包含0,1和元素x，即 $\{0,1,x\}$；

2、将这个集合中的最后一个元素，即x，乘以x，如果结果的度大于等于$w$，则将结果mod $P(x)$后加入集合；

3、直到集合有$2^w$个元素，此时最后一个元素乘以x再mod P(x)的值等于1。

---

3、编码过程（伪随机序列在伽罗华域内的窗口特性）

3.1 伪随机序列产生原理

一般反馈移位寄存器的框图如图1，它由串联的几个二元移存器(图1中空白方框)及一个开关网络构成。每个二元存储器即为一个双稳态触发器，状态分别记为“0”和“1”。每个触发器看作一级。图中长方框内所示的开关网络可视为具有$m$个输入端及一个输出端的组合门电路，它可由含有$m$个逻辑变元$x_1, x_2,\cdots,x_m$的布尔(Boole)函数$x_{r+1}=f(x_1,x_1,\cdots,x_m)$来标志，称为该组合门电路的反馈逻辑函数。在反馈移动寄存器中，每个存储器的状态记为“0”或“1”，寄存器存在$2^m$个不同的状态。输出的序列是周期性的，但全为0的状态是不能发生的，除非整个序列全是0，所以最大可能周期是$2m-1$。当序列的周期为最大值时，即为我们所称的伪随机序列。它的$h(x)$称为本原多项式。注意对于每个$m$都存在$m$次数的本原多项式$h(x)$，且本原多项式可以推导出反馈逻辑函数；从本质上说，我们的讨论可以在$q$元域$GF(q)$上进行，即存储器有$q$种状态。我们在介绍原理时，仅在二元域$GF(2)$中进行讨论。一个最简单的生成伪随机序列的反馈移动寄存器如图2，它的本原多项式为

$$h(x)=x^4 + x +1 \tag 1$$

图中$\bigoplus$为模2 加法。从表1可看到寄存器的连续状态和输出的序列$(000100110101111)$，序列的周期是15。

3.2 伪随机阵列生成方法

将伪随机序列构造成伪随机阵列很简单，令伪随机序列$a_0,a_1,\cdots,a_n-1$ 的周期为

$$n = 2^m −1 \tag 2$$
式中$m=k_1k_2$，$k_1, k_2$ 为伪随机阵列的窗口参数，伪随机阵列的大小为$n_1 \times n_2$。其中 $$n_1=2^{k_1}-1,n_2=\frac{n}{n_1} \tag 3$$ 将该伪随机序列转化成伪随机阵列好比做填空题，将序列填到一个$n_1\times n_2$阵列里。填的原则是从左上角开始，沿主对角线方向往下依次填，当填到边沿时就跳到对边继续按主对角线方向填，往复直到填完为止，如图3。

下面是我们在$q$元域$GF(q)$上编制的一个伪随机阵列，阵列大小为$63\times 65$，$n_1=63，n2=65，q=4，m=6$。
其中$q, m, n1, n_2$ 以及窗口参数$k_1, k_2$ 的相互关系如下$m=k_1k_2 ， k_1=3, k_2=2, n_1=q^{k_1}-1=63,n=q^m-1=4095,n_2=\frac{n}{n_1}=65$。由于它是在4元域上的阵列，故寄存器状态除了“0”,“1”还有“$ω$”, “$ω_2$”。已知$q=4,m=6$，这样在$GF(q)$域上的本原多项式中可选择本原多项式为

$$H(x)=x6 + x2 + x +ω \tag 4$$
式中$ω$为$GF(4)$的本原元，且$ω^2+ω+1=0, ω^3=1, GF(4)=\{0, 1, ω, ω^2\}$，其反馈移动寄存器如图4。

按照其工作原理，用 C++编程构建一个伪随机阵列(部分如图5)，$3$代表$ω$，$7$ 代表$ω^2$。

由窗口特性可知，在这$n_1 \times n_2$ 阵列中的任意$k_1 \times k_2$ 的窗口阵列都是唯一的。如图3 中，加深了颜色的$2\times 2$ 的阵列就是窗口，颜色加深部分(即窗口)在$3\times 5$的编码阵列中任意移动得到得$2\times 2$的阵列都是唯一的