循環(huán)MDS矩陣的構(gòu)造

孫春雨， 陳博聰

(華南理工大學(xué) 數(shù)學(xué)學(xué)院， 廣東 廣州 510641)

循環(huán)MDS矩陣不僅在編碼理論中很重要， 而且在密碼學(xué)中也有許多應(yīng)用. 本文在文獻(xiàn)[1-3]的基礎(chǔ)上， 提出了有限域上循環(huán)MDS矩陣的新構(gòu)造， 并構(gòu)造了奇特性有限域上的一類循環(huán)對(duì)合MDS矩陣.

1 準(zhǔn)備知識(shí)

令Fq為具有q個(gè)元素的有限域，n表示一個(gè)正整數(shù). 令Fq[X]為變量X的多項(xiàng)式環(huán)， 其系數(shù)在Fq中， 并令

(1.1)

被稱為與多項(xiàng)式A(X)相關(guān)的循環(huán)矩陣. 然后， 可以通過(guò)將A到A(X)來(lái)驗(yàn)證Fq上的m×m循環(huán)矩陣的環(huán)與商環(huán)Fq[X]/〈Xm-1〉同構(gòu).

最后， 我們需要從文獻(xiàn)[5]和文獻(xiàn)[6]得到一些關(guān)于Fq上長(zhǎng)度為2m的2-準(zhǔn)循環(huán)碼的已知結(jié)果. 注意文獻(xiàn)[5]和文獻(xiàn)[6]已經(jīng)發(fā)展了關(guān)于在Fq上長(zhǎng)度為lm的2-準(zhǔn)循環(huán)碼的一般理論; 然而， 出于我們的使用目的， 我們只重申在特定情況下l=2時(shí)的結(jié)果.

Fq[X]/〈Xm-1〉×Fq[X]/〈Xm-1〉的Fq[X]/〈Xm-1〉子模稱為在Fq上長(zhǎng)度為2m的2-準(zhǔn)循環(huán)碼. Lally和Fitzpatrick[5]表明，F(xiàn)q上長(zhǎng)度為2m的任何準(zhǔn)循環(huán)碼都具有關(guān)于上的POT項(xiàng)序以減少的Gr?bner基形式存在的生成集. 這個(gè)基可以用上三角2×2矩陣的形式表示如下:

(1.2)

其中元素在Fq[X]中， 必須滿足以下條件:

(1) degg1， 1(X)>degg0， 1(X);

(2)g0， 0(X) 和g1， 1(X)是Xm-1的除數(shù);

(3) 若g0， 0(X)=Xm-1， 則g0， 1(X)=0.

Semenov和Trifonov[6]提供了一種有效的方法， 一旦獲得了C的具有簡(jiǎn)化的Gr?bner基形式(1.2)的生成矩陣， 就可以找到C的奇偶校驗(yàn)矩陣.

是通過(guò)堆疊向量vij獲得的ui×2矩陣. 構(gòu)造一個(gè)ui×2m矩陣

(1.3)

假設(shè)λ0，λ1， …，λt-1都是C的不同特征值， 并且λi在0≤i≤t-1時(shí)具有多重ui. 因此， 我們有t個(gè)矩陣H0，H1， …，Ht-1. 從文獻(xiàn)[6]引理2得出:

(1.4)

是一個(gè)(2m-k)×2m矩陣， 其秩等于2m-k， 其中k是C的維數(shù). Semenov和Trifonov[6]進(jìn)一步得出結(jié)論，H可以用作C的奇偶校驗(yàn)樣矩陣， 如下所示.

2 主要結(jié)論

令C為Fq上的[2m，m]-線性碼， 具有生成矩陣

G=(Im∣A)，

其中Im是m×m單位矩陣，A是m×m循環(huán)矩陣， 如(1.1)所示. 在本節(jié)中， 假設(shè)m與q互素. 我們的最終目的是明確找到0≤i≤m-1的Fq的m值ai， 使得C是MDS碼.為此， 我們要給出C的一個(gè)奇偶校驗(yàn)矩陣.為此， 我們首先證明C可以看作Fq上長(zhǎng)度為2m的2-準(zhǔn)循環(huán)碼. 由于G=(Im|A)是C的生成矩陣， 因此可以得出

然后， 我們有以下引理.

我們有

=(c0，c1， …，cm-1)(Im∣A).

對(duì)于所有0≤i≤m-1

其中a的下標(biāo)以模m計(jì)算.容易驗(yàn)證:

=(cm-1，c0， …，cm-2)(Im∣A).

我們注意到， 具有引理1.1的雙循環(huán)性的碼在文獻(xiàn)中稱為雙循環(huán)碼(例如參見(jiàn)[7]). 如[7]所述， 將

映射到

∈Fq[X]/〈Xm-1〉×Fq[X]/〈xm-1〉

的映射為

的雙射. 顯然，

Fq[X]/〈Xm-1〉×Fq[X]/〈Xm-1〉在通常意義上是Fq[X]/〈Xm-1〉模; 此外， 標(biāo)量乘法X對(duì)應(yīng)于向量(c，c′)的雙循環(huán)移位. 因此，C可以視為

Fq[X]/〈Xm-1〉×Fq[X]/〈Xm-1〉

的Fq[X]/〈Xm-1〉子模. 換句話說(shuō)，C是在Fq上長(zhǎng)度為2m的2-準(zhǔn)循環(huán)碼(例如參見(jiàn)[6]或[7]).

接下來(lái)， 我們的目標(biāo)是通過(guò)使用文獻(xiàn)[6]中介紹的方法為C導(dǎo)出一個(gè)奇偶校驗(yàn)矩陣. 現(xiàn)在很容易看出，C是由(1，A(X))生成的， 其中

degf(x)≤m-1}

=(αi， 1λiαiλi，λ2iαi，λ2i， …，λ(m-1)t)

此時(shí)我們得到形式為(1.4)的C的奇偶校驗(yàn)矩陣:

其中δ=λ-1也是Fqr中第m個(gè)單位根.

定理2.1假設(shè)m>1是q-1的除數(shù).令

λ∈Fq為本原的第m個(gè)單位根. 令α≠1是Fq的一個(gè)非零元素， 以使Fq的乘法群中α與m互素. 令

相反， 假設(shè)對(duì)于某個(gè)0≤i，j≤m-1有λi=αλj， 得出α=λi-j. 假設(shè)Fq的乘群中的α的階等于s. 因此， 1=αs=λs(i-j).然后， 我們看到m是s(i-j)的因子. 由假設(shè)s與m互素， 則m是i-j的因子.推出i=j， 因此α=1. 這與α≠1矛盾.

推論2.1令q為奇素?cái)?shù)， 令Fq中α=1. 假設(shè)m>1是q-1的奇因子. 令λ∈Fq是本原的第m個(gè)單位根. 設(shè)δ=λ-1且

相關(guān)的循環(huán)矩陣是循環(huán)對(duì)合MDS矩陣.