一種求解線性碼最小距離的方法

（天津職業(yè)技術(shù)師范大學(xué) 理學(xué)院，天津 300222）

1 引言及預(yù)備知識(shí)

線性碼的最小距離與編碼的檢錯(cuò)和糾錯(cuò)能力息息相關(guān)，最小距離越大，檢錯(cuò)和糾錯(cuò)能力越強(qiáng).線性碼的最小距離有多種求法，如利用權(quán)重分布多項(xiàng)式、窮舉、生成矩陣、校驗(yàn)矩陣相關(guān)列、幾何學(xué)等方法求線性碼最小距離[1]237.多項(xiàng)式理論可以用來(lái)描述一部分具有良好性質(zhì)的線性碼（如循環(huán)碼），且也可以通過(guò)編碼的方式將線性碼轉(zhuǎn)化為多項(xiàng)式，即用原數(shù)字信息與線性碼的生成矩陣做乘法，得到由多項(xiàng)式表示的線性碼一般表達(dá)式.在此基礎(chǔ)上，可以考慮由線性碼生成的理想It，其由線性碼的一般表達(dá)式中t個(gè)不同的多項(xiàng)式乘積生成，對(duì)于理想It，Gr?bner 基理論是用來(lái)解決理想生成元的一種手段.近年來(lái)，Gr?bner基在線性碼理論的研究中是一個(gè)活躍的研究領(lǐng)域，1992 年，Cooper 在文獻(xiàn)[2]中用多項(xiàng)式表示循環(huán)碼，進(jìn)而用Gr?bner 基理論進(jìn)行解碼，其是首位把Gr?bner 基應(yīng)用到線性碼理論中的學(xué)者；文獻(xiàn)[3-6]應(yīng)用Gr?bner基理論研究了線性碼的各種性質(zhì)；文獻(xiàn)[7-9]對(duì)Gr?bner 基理論的應(yīng)用做了詳細(xì)的介紹.

本文由文獻(xiàn)[1]中的一種求線性碼最小距離的方法展開(kāi)，該方法主要運(yùn)用代數(shù)方法求由線性碼生成的理想It何時(shí)有非零解，來(lái)確定線性碼的最小距離.但該方法的適用范圍有限，碼字較長(zhǎng)時(shí)計(jì)算過(guò)程比較復(fù)雜，基于這種情形，提出一種新的方法——利用線性碼所生成理想的Gr?bner 基確定線性碼的最小距離.改進(jìn)后的方法能夠處理原方法不能處理的一些問(wèn)題，且會(huì)給出較好的結(jié)果.基于Maple 平臺(tái)對(duì)2種方法進(jìn)行了對(duì)比，證明改進(jìn)后的方法比原方法速度更快.

線性碼的本質(zhì)是有限域上有限維向量空間的線性子空間，因此可以用線性代數(shù)中的一些工具對(duì)線性碼進(jìn)行研究.記為有限域Fq上的n維線性空間.

自1965 年Buchberger 提出Gr?bner 基方法后，Gr?bner 基已經(jīng)在各個(gè)研究領(lǐng)域得到了很好的應(yīng)用，包括代數(shù)方程組的求解、多項(xiàng)式的因子分解、糾錯(cuò)編碼中循環(huán)碼和代數(shù)幾何碼的譯碼、密碼學(xué)等研究領(lǐng)域.Gr?bner 基與單項(xiàng)式的序關(guān)系密切相關(guān)，常見(jiàn)的序關(guān)系有字典序、分次字典序、分次逆字典序等.

2 基于Gr?bner 基的最小距離算法

由命題1 可知，可以通過(guò)計(jì)算It的零點(diǎn)集來(lái)判定碼C的最小距離，但是當(dāng)n和t較大時(shí)，利用此方法無(wú)法在有限時(shí)間內(nèi)得到結(jié)果，實(shí)例驗(yàn)證可以說(shuō)明利用命題1 計(jì)算最小距離耗時(shí)更長(zhǎng).

直接計(jì)算理想It的零點(diǎn)集較為困難，但可以利用理想的Gr?bner 基求出其零點(diǎn)集，這是計(jì)算理想零點(diǎn)集的一個(gè)有效方法.

命題2 是對(duì)命題1 的改進(jìn)，它給出一種求碼C最小距離的新方法，即利用多項(xiàng)式理想的Gr?bner 基算法求碼C的最小距離.

根據(jù)命題2 求碼C最小距離時(shí)的基本思路為：首先確定碼C的一般表達(dá)式和多項(xiàng)式運(yùn)算規(guī)則，通過(guò)一個(gè)循環(huán)構(gòu)造理想It，接下來(lái)調(diào)用Maple 中用于計(jì)算Gr?bner 基的函數(shù)包，計(jì)算理想It在字典序下的Gr?bner基，輸出It的Gr?bner 基G，由此可確定所給線性碼的最小距離.

求碼C最小距離的Maple 程序：

3 實(shí)例驗(yàn)證

給出3個(gè)實(shí)例，用命題2 求解其最小距離，并在每個(gè)例題后給出用Gr?bner 基算法計(jì)算由碼C生成的理想所需要的時(shí)間.

解由生成矩陣G可以得到碼字的一般表達(dá)式c=(x1,x2,x3,x1+x2+x3,x1+αx2+α2x3,x1+α2x2+αx3),由α2+α+1=0可知，α3=1，α2=α+1.經(jīng)過(guò)計(jì)算可得到I1，I2，I3，I4的Gr?bner基分別為

用Gr?bner 基算法計(jì)算由二元線性碼生成的理想I1，I2，I3，I4所需要的時(shí)間分別為0.031 200 2，0.093 600 6，0.249 601 6，0.249 601 6，0.109 200 7 s.

例2 設(shè)五元線性碼C的生成矩陣為，求該線性碼的最小距離.

用Gr?bner 基算法計(jì)算由五元線性碼生成的理想I1，I2，I3所需要的時(shí)間分別為0.015 600 1，0.046 800 3，0.031 200 2 s.

用Gr?bner 基算法計(jì)算由碼C生成的理想I1，I2，I3，I4，I5，I6所需要的時(shí)間分別為0.062 400 4，0.483 603 1，5.990 438 4，42.276 271，137.421 280 9，195.999 656 4 s.

注在例3 中，若用命題1 來(lái)求解碼字的最小距離，首先要根據(jù)定義5 給出It（t=1,2,3,4,5,6），再計(jì)算It在F2中何時(shí)有非零解，從而得出二元碼C的最小距離.利用命題1 計(jì)算I1，I2，I3，I4，I5，I6零點(diǎn)集所需要的時(shí)間分別為0.24，0.82，9.85，70.42，200.82，285.67 s，所需時(shí)間明顯多于本文所給方法.因此，當(dāng)碼長(zhǎng)較長(zhǎng)的情況下，用Gr?bner 基算法計(jì)算碼C的最小距離速度更快.

4 結(jié)語(yǔ)

最小距離反映了線性碼的檢錯(cuò)和糾錯(cuò)能力，因此研究線性碼最小距離的求解方法對(duì)線性碼的測(cè)評(píng)具有重要意義[11].本文介紹了基本的代數(shù)編碼知識(shí)，利用線性碼所生成理想的Gr?bner 基對(duì)原有線性碼最小距離求法進(jìn)行改進(jìn)，提出了一種求解線性碼最小距離的新方法，并用實(shí)例驗(yàn)證在碼字較長(zhǎng)的情況下，新方法比原有方法的計(jì)算速度更快.