[数据结构与算法]MATLAB生成M序列和Gold序列

M序列

??最长线性移位寄存器序列又称为m序列，他是一种伪随机序列，在硬件电路中，m序列可以通过反馈移位寄存器产生，寄存器的反馈连接有生成m序列的本源多项式确定。
??m序列的$0$映射成$?1$后，m序列的循环自相关函数（不归一化）在时间间隔为$0$处取最大值，其他时间间隔的循环自相关函数都是$?1$。本源多项式$x^6+x^4+x^3+x+1$产生的m序列的循环自相关函数如下图所示。

MATLAB生成M序列和计算循环自相关函数

function p=PnCode(polynomial,reg)
%  PN码产生器函数
%  polynomial为本原多项式，从左到右依次为高位到低位，且最高位与最低位必须为1;低位表示延时一个周期，高位依次顺延，例如[1 0 0 1 0 1]
%  reg为置寄存器初始值,也相当于PN码的初始相位，左边为高位，如[1 0 0 1 0]表示延时５个周期的寄器和２个周期的寄存器初值为1
grade=length(polynomial)-1;%根据多项式计算延时级数
PN_Length=(2^grade-1);     %计算PN码一个周期的长度 
n=0;                         
c=zeros(1,grade);
for i=grade:-1:1
    if polynomial(i)==1
        n=n+1;
        c(n)=grade+1-i;
    end
end  
%产生一个周期的PN码  
p = zeros(1,PN_Length);
for i=1:PN_Length
    %从最高延时的寄存器中输出PN码
    p(i)=reg(1);
    %完成各抽头寄存器取值的模2加
    m = mod(reg*polynomial(1:grade)',2);
    %寄存器的值依次移位
    reg(1:(grade-1)) = reg(2:grade);
    reg(grade)=m;
end

function [r,lags] = periodic_corr(x,y)
% returns the periodic cross-correlation or autocorrelation of two discrete-time sequences.
% Rxy(m) = sum(i) x(i)Y((i+m) mod L)
% x input array
% y input array
% r periodic cross-correlation or autocorrelation
% lags Lag indices
if size(x,2) == 1 && ~isscalar(x)
    x = x';
end
if size(y,2) == 1 && ~isscalar(y)
    y = y';
end
if size(x,2)~=size(y,2)
    error(message('x y dimension mismatch'));
end
L = size(x,2);
r = zeros(1,2*L-1);
for m = 1:L
    if m == 1
        r(L) = x*y'/L;
    else
        r(L+m-1) = x*y'/L;
        r(m-1) = x*y'/L;
    end
    y = circshift(y,-1);
end
lags = -(L-1):L-1;
end

M序列优选对

??对于由两个$n$阶本源多项式生成的m序列$a$和$b$，如果它们的互相关函数的绝对值的最大值满足公式$(1)$所示的关系，则m序列$a$和$b$构成优选对。$$|R_{a,b}(\tau ){|}_{max}=\{\begin{array}{l}{2}^{\frac{n+1}{2}}+1,n为奇数\\ 2^{\frac{n+2}{2}}+1,n为偶数且不是4的倍数\end{array}\text{\hspace{1em}(1)}$$
??m序列优选对具有三值互相关特性，即它们的循环互相关函数只能取三个值。$n$为奇数时，互相关函数取$?1$、$?(2^{\frac{n+1}{2}}+1)$和$2^{\frac{n+1}{2}}?1$；$n$为偶数且不是4的倍数时，互相关函数取$?1$、$?(2^{\frac{n+2}{2}}+1)$和$2^{\frac{n+2}{2}}?1$。
??下面给出几组m序列优选对的本源多项式。

??本原多项式$x^6+x+1$和$x^6+x^5+x^2+x+1$产生的m序列的互相关函数（不归一化）如下图所示，它们的三个互相关值分别为$?1$、$?17$和$15$。

GOLD序列

??Gold序列是由2个码长相等、码时钟速率相同的m序列优选对模二加和构成的，每改变2个m序列相对位移就可以得到一个新的Gold序列。
??对于$n$阶本源多项式生成的m序列优选对，m序列的周期为$2^n?1$，m序列优选对可以有$2^n?1$种模2加组合，再加上原来的2个m序列，可以得到一族$2^n+1$个Gold序列。Gold序列的自相关特性不如m序列，但是同一族的Gold序列的互相关特性继承了m序列优选对的互相关特性，即三值互相关特性。由本原多项式$x^6+x+1$和$x^6+x^5+x^2+x+1$获得的m序列优选对生成65个Gold序列，随便抽两个Gold序列计算循环互相关函数，如下图所示。

平衡GOLD序列

??如果Gold序列中$1$的数量比$?1$的数量多一个，那么该Gold序列称为平衡Gold序列。扩频时采用平衡Gold序列有许多优点，比如平衡码能更好地抑制载波。当$n$为奇数时，一族Gold序列中平衡序列和非平衡序列出现的概率各占50％；当$n$为偶数且不为4的倍数时，一族Gold序列中平衡序列出现的概率为75％，非平衡序列为25％。

MATLAB生成Gold序列和寻找平衡序列

MATLAB中可以用comm.GoldSequence函数生成Gold序列，具体用法可以参考help文档。找平衡序列的方法是暴力枚举。

function [g,balanced] = GoldCode(polynomial1,polynomial2)
% Generate Gold sequence
% polynomial1、polynomial2 primitive polynomial, lists the coefficients of
%                          the polynomial in descending order of powers.  
%                          The first and last elements must equal 1, and
%                          the length of this vector requires a value of
%                          n+1, where n is the degree of the primitive polynomial.
%                          polynomial1 and polynomial2 generate a pair of m
%                          sequences which is a preferred pair 
% g Gold sequences
% balanced index of balanged Gold sequence in g

if length(polynomial1) ~= length(polynomial2)
     error(message('polynomial1 polynomial2 dimension mismatch'));
end
grade=length(polynomial1)-1;%根据多项式计算延时级数
gold_length=(2^grade-1);    %计算PN码一个周期的长度
g = zeros(gold_length+2,gold_length);
balanced = zeros(gold_length+2,1);
for n = -2:gold_length-1
    goldseq = comm.GoldSequence('FirstPolynomial',polynomial1,...
                                'SecondPolynomial',polynomial2,...
                                'FirstInitialConditions',[zeros(1,grade-1) 1],...
                                'SecondInitialConditions',[zeros(1,grade-1) 1],...
                                'Index',n,'SamplesPerFrame',gold_length);
    x = goldseq()';
% 	g(n+3,:) = 2*x-1;
    g(n+3,:) = x;
    if length(find(x == 1)) == (gold_length+1)/2
        balanced(n+3) = 1;
    end
end
balanced = find(balanced == 1);
end

参考：Gold序列与m序列仿真应用
辛肖明, 陈琼. m序列优选对及平衡Gold码序列[J]. 北京理工大学学报, 1990, 10(4):106-113.