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

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

2、rline communications，Proc．Int．J．Elec．Commun．，vol．54，no．1，2000)提出置換碼可應(yīng)用于電力線通信上的糾錯編碼，而重新引起了學(xué)術(shù)界的研究興趣。本文主要對置換碼理論的最基本問題-置換碼的上、下界和構(gòu)造-進行了深入研究。本文取得的主要結(jié)果如下所列： 1．證明了一個關(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ù)α,β滿足某些條件時，若d=βn<'α>，則新上界漸近優(yōu)于以往的上界。 3．基于Jiang和Vardy提出的圖論框架，給出了P(n，d)的Gilbert-Varshamov下界的三個改進。 4．通過考慮覆蓋球的交集，給出了P(n，d)的Gilbert-Varshamov下界的二個改進。 5．提出了從(n，d)置換碼分別構(gòu)造(n-1，d-3)和(n-1，d-2)置

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

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