置換碼的界及構造的研究.pdf

1、長為n，最小距離為d的置換碼(陣列)記為(n，d)置換碼，是關于某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)提出置換碼可應用于電力線通信上的糾錯編碼，而重新引起了學術界的研究興趣。本文主要對置換碼理論的最基本問題-置換碼的上、下界和構造-進行了深入研究。本文取得的主要結果如下所列： 1．證明了一個關于P(n，d)和P<,Ω>(n，d)的不等式。 2．給出了P(n，d，w)的若干基本性質，然后基于它們分別給

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

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

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