置換碼的界及構(gòu)造的研究.pdf

1、長(zhǎng)為n，最小距離為d的置換碼(陣列)記為(n，d)置換碼，是關(guān)于某n個(gè)元素的置換的集合C，并且對(duì)任意不同的x，y ∈C，它們之間的漢明距離至少為d。令P(n，d)記為(n，d)置換碼的碼元數(shù)量的最大可能值。若(n，d)置換碼C的大小|C|=P(n，d)則稱之為最優(yōu)化置換碼。P(n，d)的值的研究被認(rèn)為是置換碼研究的基本問(wèn)題。 置換碼曾在上世紀(jì)70年代有過(guò)零星的研究，由于Vinck(Coded modulation forpowe

2、rline communications，Proc．Int．J．Elec．Commun．，vol．54，no．1，2000)提出置換碼可應(yīng)用于電力線通信上的糾錯(cuò)編碼，而重新引起了學(xué)術(shù)界的研究興趣。本文主要對(duì)置換碼理論的最基本問(wèn)題-置換碼的上、下界和構(gòu)造-進(jìn)行了深入研究。本文取得的主要結(jié)果如下所列： 1．證明了一個(gè)關(guān)于P(n，d)和P<,Ω>(n，d)的不等式。 2．給出了P(n，d，w)的若干基本性質(zhì)，然后基于它們分別給

3、出P(n，2k)和P(n，2k+1)的新上界。當(dāng)常數(shù)α,β滿足某些條件時(shí)，若d=βn<'α>，則新上界漸近優(yōu)于以往的上界。 3．基于Jiang和Vardy提出的圖論框架，給出了P(n，d)的Gilbert-Varshamov下界的三個(gè)改進(jìn)。 4．通過(guò)考慮覆蓋球的交集，給出了P(n，d)的Gilbert-Varshamov下界的二個(gè)改進(jìn)。 5．提出了從(n，d)置換碼分別構(gòu)造(n-1，d-3)和(n-1，d-2)置

4、換碼的方法，由此給出當(dāng)n和d取某些情況時(shí)置換碼的新下界。 6．提出兩個(gè)由有限域上的分式多項(xiàng)式構(gòu)造置換碼的方法，并由此得到置換碼的一些新下界。 7．證明了階為n，最小度為d的置換群和(n，d)置換碼的關(guān)系，由此得到置換碼的一些新下界。 8．給出了由二元碼構(gòu)造置換碼的三個(gè)新構(gòu)造，前兩個(gè)構(gòu)造建立了P(n，d)，DP(n，d)和CP(n，d)之間的一些令人感興趣的不等式，后一個(gè)構(gòu)造比直接構(gòu)造更加有效地利用距離保持映射從二

5、元碼構(gòu)造置換碼。 9．廣義碼是各種具體碼的抽象形式，包括置換碼和二元碼等。給出廣義碼的Gilbert-Varshamov界的一個(gè)簡(jiǎn)單新證明，接著證明了一個(gè)簡(jiǎn)單隨機(jī)構(gòu)造算法只需要較低的復(fù)雜度就能以較大的概率得到較大的碼，而以前的Altruisitic算法由于復(fù)雜度太高實(shí)際上難以實(shí)現(xiàn)。當(dāng)簡(jiǎn)單隨機(jī)構(gòu)造算法應(yīng)用于構(gòu)造置換碼時(shí)，與Keevash和Ku提出的半隨機(jī)構(gòu)造算法比較，不僅沒(méi)有苛刻的實(shí)現(xiàn)條件，而且需要更少的時(shí)間。 10．二元