群結(jié)構(gòu)在設(shè)計(jì)沖突可避碼中的應(yīng)用

趙春娥，程志遠(yuǎn)，譚尊林

(中國(guó)石油大學(xué)(華東) 理學(xué)院,山東 青島 266580)

群的概念已經(jīng)普遍地被認(rèn)為是數(shù)學(xué)及其許多應(yīng)用中最基本的概念之一，它不但滲透到如幾何學(xué)、函數(shù)論、泛函分析等許多數(shù)學(xué)分支中，還在其他領(lǐng)域如結(jié)晶學(xué)、理論物理、量子化學(xué)、代數(shù)編碼學(xué)、自動(dòng)機(jī)理論等方面都有重要的應(yīng)用.

論文主要將群的理論應(yīng)用于多址聯(lián)接通信技術(shù)中.多址聯(lián)接通信技術(shù)在移動(dòng)通信網(wǎng)和衛(wèi)星通信網(wǎng)等工程領(lǐng)域都有廣泛的應(yīng)用，主要有頻分多址、時(shí)分多址和碼分多址3種基本多址技術(shù).時(shí)分多址是把時(shí)間分割成互不重疊的時(shí)段(幀)，再將幀分割成互不重疊的與用戶具有一一對(duì)應(yīng)關(guān)系的時(shí)隙(信道).當(dāng)多個(gè)用戶在同一時(shí)隙通信的時(shí)候，為了避免因沖突的產(chǎn)生使得發(fā)送消息不能被基站接收而導(dǎo)致通信失敗，每一個(gè)用戶都指定了一個(gè)通信協(xié)議，用戶按照協(xié)議來(lái)進(jìn)行通信.而每一個(gè)通信協(xié)議都是由一個(gè)沖突可避碼的碼字作為支撐集生成的0-1序列.因此，成功完成通信的基本保障是構(gòu)造合適的沖突可避碼.在這里，沖突可避碼的重量w是可以同時(shí)進(jìn)行通信的用戶數(shù)目，碼的容量為系統(tǒng)所支持的通信用戶的總數(shù).

對(duì)于重量w=3的沖突可避碼， 文獻(xiàn)[1-5]在長(zhǎng)度為n=16m，n=4(mod8)，n=4m，n=2(mod4)，n=1(mod2)時(shí)，給出了相應(yīng)的最優(yōu)沖突可避碼的構(gòu)造方法.文獻(xiàn)[6]給出了奇素?cái)?shù)長(zhǎng)緊的等差碼存在的充要條件并給出了最優(yōu)等差碼沖突可避碼的直接構(gòu)造和遞歸構(gòu)造.文獻(xiàn)[7]給出了奇數(shù)長(zhǎng)沖突可避碼容量的上界.對(duì)于重量w=4，文獻(xiàn)[8-9]分別利用了有向圖和無(wú)向圖，給出長(zhǎng)度為2a3b和2a3bm的最優(yōu)沖突可避碼的分析和構(gòu)造.對(duì)于一般重量w，文獻(xiàn)[10]給出了常重量沖突可避碼的上界，文獻(xiàn)[11]給出了漸進(jìn)上界和最優(yōu)構(gòu)造方法.論文將對(duì)文獻(xiàn)[12]中的方法進(jìn)行推廣，得到更多滿足條件的素?cái)?shù)p，從而構(gòu)造更多長(zhǎng)度的最優(yōu)碼，可以給更多的用戶提供協(xié)議序列進(jìn)行通信，提高通信系統(tǒng)的性能.

1 預(yù)備知識(shí)

d*(I)={j-i|i,j∈I,i≠j},

其中：減法是指模L的減法運(yùn)算.

一個(gè)長(zhǎng)為L(zhǎng)、重量為w的沖突可避碼(conflict-avoiding code，簡(jiǎn)稱CAC)C是P(L,w)的一個(gè)滿足下面條件的子集

d*(Ij)∩d*(Ik)=φ，?Ij,Ik∈C,j≠k,

其中：每一個(gè)I∈C都稱為一個(gè)長(zhǎng)為L(zhǎng)、重量為w的碼字.

一個(gè)碼字I∈P(L,w)稱為是等差的，如果I中每一個(gè)元素都形成ZL的一個(gè)等差排列，即

I=(0,i,2i,…,(w-1)i)，對(duì)于某個(gè)i∈ZL.

在上面的式子中，乘積是指模L的乘法運(yùn)算，i被稱為這個(gè)碼字的生成元，差的集合等于

d*(I)=(±i,±2i,…,±(w-1)i).

如果一個(gè)沖突可避碼C中所有的碼字都是等差的，則稱C是等差的，并且其生成元的集合記為Γ(C).

對(duì)于一個(gè)給定的L，令CAC(L,w)是所有的長(zhǎng)為L(zhǎng)、重量為w的CAC的集合.某個(gè)碼C∈CAC(L,w)具有極大容量，則記其容量為M(L,w)，即

M(L,w)=max{|C||C∈CAC(L,w)}.

類似地，令CACe(L,w)是長(zhǎng)度為L(zhǎng)、重量為w的等差CAC的集合，等差碼C∈CACe(L,w)的極大容量記為Me(L,w)，即

Me(L,w)=max{|C||C∈CACe(L,w)}.

對(duì)于一個(gè)等差碼C∈CACe(L,w)，如果

|C|=Me(L,w)，

則稱C是最優(yōu)的.一個(gè)最優(yōu)的碼C∈CAC(L,w)，如果

則稱C為緊的.

2 常重量素?cái)?shù)長(zhǎng)沖突可避碼的最優(yōu)構(gòu)造

定義1[12]給定素?cái)?shù)p，令

Zp={0,1,…,p-1}，

則Zp中的非零元集合Zp*對(duì)于模p的乘法運(yùn)算是一個(gè)階為p-1的循環(huán)群.

對(duì)于p-1的因子f，記Zp*的f階乘法子群為

定理2令p=2(w-1)ms+1是一個(gè)素?cái)?shù)，如果存在Zp*的2m(w-1)階子群H，使得{1,2,…,w-1}是{Nj:j=1,2,…,w-1}的一個(gè)代表系，其中:N1是H的一個(gè)2m階子群，Nj為N1在H中的陪集，則存在最優(yōu)等差(2(w-1)ms+1,w)-沖突可避碼.

證明由于H是Zp*的2m(w-1)階子群，則存在有限域Zp的本原元α，使得

H=(αs)，

令

g=αs(w-1)，

則

N1=(g)，

有

(1)

令Γ(C)={αigj:0≤i≤s-1,0≤j≤m-1}為等差碼字的生成集，由于對(duì)于每一個(gè)等差碼字

I=(0,αigj,2αigj,…,(w-1)αigj)，

其差的集合為

d*(I(i,j))={±αigj,±2αigj,…,±(w-1)αigj}.

由于{1,2,…,w-1}構(gòu)成N1的一個(gè)代表系，由(1)式得，對(duì)于任意兩個(gè)碼字I(i1,j2)，I(i2,j2)，有

d*(I(i1,j1))∩d*(I(i2,j2))=φ,(i1,j1)≠(i2,j2)，

因此，由這些等差碼字構(gòu)成的沖突可避碼是最優(yōu)的而且是緊的,由αigj:0≤i≤s-1,0≤j≤m-1生成的ms個(gè)碼字構(gòu)成一個(gè)等差(2(w-1)ms+1,w)-沖突可避碼.

特別地，當(dāng)定理2中參數(shù)s=1時(shí)，即為定理1中的構(gòu)造方法.因此，定理2是定理1的一種推廣.

定理3[10]設(shè)G是一個(gè)群，H是G的一個(gè)子群，A是G的一個(gè)非空子集，如果A是一個(gè)H-周期，則A能寫(xiě)成H的某些陪集的并.

則存在最優(yōu)等差(2(w-1)ms+1,w)-沖突可避碼.

H=(αs(w-1))，

則

(2)

記g=αs(w-1)，令

Γ(C)={αigj:0≤i≤s-1,0≤j≤m-1}

為等差碼字的生成集， 由于對(duì)于每一個(gè)等差碼字

I(i,j)=(0,αigj,2αigj,…,(w-1)αigj)，

其差的集合為

d*(I(i,j))={±αigj,±2αigj,…,±(w-1)αigj}.

由于{1,2,…,w-1}構(gòu)成N0的一個(gè)代表系，由(2) 式得，對(duì)于任意兩個(gè)碼字I(i1,j1)，I(i2,j2),有

d*(I(i1,j1))∩d*(I(i2,j2))=φ,(i1,j1)≠(i2,j2)，

因此，由這些等差碼字構(gòu)成的沖突可避碼是最優(yōu)的而且是緊的，由αigj:0≤i≤s-1,0≤j≤m-1生成的ms個(gè)等差碼字構(gòu)成一個(gè)(2(w-1)ms+1,w)-沖突可避碼.

特別地，當(dāng)定理4中參數(shù)s=1時(shí)，即定理1中的構(gòu)造方法.因此，定理4也是定理1的一種推廣.

3 結(jié)束語(yǔ)

論文主要研究了重量為w且長(zhǎng)度為素?cái)?shù)p的沖突可避碼的最優(yōu)構(gòu)造.區(qū)別于以往圖論圈結(jié)構(gòu)的討論方法，論文利用子群陪集劃分的方法首先確定出碼字差的集合，然后再還原成碼字，從而構(gòu)造沖突可避碼.論文將已有方法中群的代表系推廣至子群的代表系，又將群的代表系推廣至H-周期的代表系, 擴(kuò)大了參數(shù)p的取值范圍，用此方法可以構(gòu)造更多最優(yōu)的沖突可避碼.