M序列基本概念

m序列是最長(zhǎng)線(xiàn)性移位寄存器序列的簡(jiǎn)稱(chēng)，是一種偽隨機(jī)序列、偽噪聲(PN)碼或偽隨機(jī)碼?？梢灶A(yù)先確定并且可以重復(fù)實(shí)現(xiàn)的序列稱(chēng)為確定序列;既不能預(yù)先確定又不能重復(fù)實(shí)現(xiàn)的序列稱(chēng)隨機(jī)序列;不能預(yù)先確定但可以重復(fù)產(chǎn)生的序列稱(chēng)偽隨機(jī)序列。

m序列是目前廣泛應(yīng)用的一種偽隨機(jī)序列，其在通信領(lǐng)域有著廣泛的應(yīng)用，如擴(kuò)頻通信，衛(wèi)星通信的碼分多址，數(shù)字?jǐn)?shù)據(jù)中的加密、加擾、同步、誤碼率測(cè)量等領(lǐng)域。

在所有的偽隨機(jī)序列中，m序列是最重要、最基本的一種偽隨機(jī)序列。它容易產(chǎn)生，規(guī)律性強(qiáng)，有很好的自相關(guān)性和較好的互相關(guān)特性。在IS-95的反向信道中，選擇了m序列的PN碼作為地址碼，利用不同相位m序列幾乎正交的特性來(lái)為每個(gè)用戶(hù)的業(yè)務(wù)信道分配了一個(gè)相位。

對(duì)于一個(gè)n級(jí)反饋移位寄存器來(lái)說(shuō)，最多可以有2^n 個(gè)狀態(tài)，對(duì)于一個(gè)線(xiàn)性反 饋移位寄存器來(lái)說(shuō)，全"0"狀態(tài)不會(huì)轉(zhuǎn)入其他狀態(tài)，所以線(xiàn)性移位寄存器的序列的最長(zhǎng)周期為 2^n-1。當(dāng)n級(jí)線(xiàn)性移位寄存器產(chǎn)生的序列{ai}的周期為T(mén)= 2^n-1時(shí)，稱(chēng){ai}為n級(jí)m序列。

當(dāng)反饋函數(shù)f(a1,a2,a3,…an)為非線(xiàn)性函數(shù)時(shí)，便構(gòu)成非線(xiàn)性移位寄存器，其輸出序列為非線(xiàn)性序列。輸出序列的周期最大可達(dá) 2^n ，并稱(chēng)周期達(dá)到最大值的非線(xiàn)性移位寄存器序列為M序列。

1. 信息安全

主要用在加密解密上面

2. 通信行業(yè)

CDMA通信的行業(yè)的信息

最長(zhǎng)上升子序列

Longest Increasing Subsequence

最長(zhǎng)上升子序列:

有兩種基本方法:兩個(gè)時(shí)間復(fù)雜度分別為O(n^2)和O(nlogn)

對(duì)于給定數(shù)列a，元素個(gè)數(shù)為n，f[i]為以元素i結(jié)尾的最長(zhǎng)子上升序列的最大長(zhǎng)度。

最長(zhǎng)上升子序列f滿(mǎn)足對(duì)任意1<=j<i<=n(a[j]<a[i])，有f[j]<f[i]。

容易得出O(n^2)的DP狀態(tài)轉(zhuǎn)移方程:

f[i]=max{f[j]}+1;(1<=j<i且a[j]<a[i])

我們不妨把f的初值設(shè)為0，并在末尾添加一個(gè)元素inf，并將n++

這樣經(jīng)過(guò)兩重循環(huán)，f[n]即為L(zhǎng)IS長(zhǎng)度

代碼如下:

又稱(chēng)作CMI算法

時(shí)間復(fù)雜度為O(nlogn)

其操作如下:

開(kāi)辟一個(gè)棧b，每次取棧頂元素s和讀到的元素a做比較，如果a>s，則置為棧頂;如果a<s，則二分查找棧中的比a大的第1個(gè)數(shù)，并替換。最終棧的大小即為最長(zhǎng)遞增子序列為長(zhǎng)度

考察b棧內(nèi)每個(gè)元素的含義,b[i] 表示所有長(zhǎng)度為i的上升子序列中最小的最后一個(gè)數(shù).

·舉例:原序列為3，4，5，2，4，2

棧為3，4，5，此時(shí)讀到2，則用2替換3，得到棧中元素為2，4，5，再讀4，用4替換5，得到2，4，4，再讀2，得到最終棧為2，2，4,最終得到的解是:

長(zhǎng)度為1的上升子序列中最小的最后一個(gè)數(shù)是2 (2)

長(zhǎng)度為2的上升子序列中最小的最后一個(gè)數(shù)是2 (2,2)長(zhǎng)度為3的上升子序列中最小的最后一個(gè)數(shù)是4 (3,4,4)

可知沒(méi)有長(zhǎng)度為4的上升子序列,最長(zhǎng)遞增子序列長(zhǎng)度為3. (3,4,4)

CMI本質(zhì)是LIS問(wèn)題的另一種動(dòng)態(tài)規(guī)劃思路

注意:CMI只能求LIS的長(zhǎng)度和最后一個(gè)數(shù),不能求LIS的序列!

代碼如下:

#include<iostream>

using namespace std;

int n;

int a[1001],b[1001];

int rear;

int solve(int t)

{ int l=1,r=rear;

while(l<=r)

{ int mid=(l+r)>>1;

if(b[mid]>=t)//若為非遞減序列，則為b[mid]>t

r=mid-1;

else

l=mid+1;

}

if(l>rear)

rear=l;

return l;

}

int main()

{ int i,j;

scanf("%d",&n);

rear=0;

for(i=1;i<=n;i++)

{

scanf("%d",&a[i]);

b[solve(a[i])]=a[i];

}

printf("%d\n",rear);

system("pause");

return 0;

}