可分組設計及其在信息科學中的應用.pdf

1、可分組設計(GDD)在組合設計理論中有著極其重要的作用，它們被廣泛地用來構造各類設計。例如，在組合設計理論奠基人Wilson和Hanani證明成對平衡設計存在的充分必要條件時，可分組設計是他們遞歸構造過程中不可缺少的一部分。類似地，可分解可分組設計和frame在構造具有可分解性質的設計的時候同樣起著基礎性的作用。我們稱一個GDD是型一致的如果它所有組的大小均相同。本文研究了多類可分組設計的存在性問題，包括型不一致的4-GDD，型一致的5

2、-GDD，4-RGDD，4-frame以及G-GDD等。同時，我們也討論了可分組設計在信息科學當中的應用，這些應用包括光纖網絡中的業(yè)務疏導問題以及非線性糾錯碼。
　　在第2章中，我們研究了型為gum1的可分組設計存在性問題。當區(qū)組大小為3時，這個問題已被Colbourn，Hoffman和Rees于1992年解決。而區(qū)組大小是4的情形還沒有被解決。目前關于此類4-GDD的存在性結果多集中于gu是偶數的情況。本文將考察此類4-GDD整

3、個存在性問題。我們證明了對任意給定的g，除了很小一部分的u外，型為gum1的4-GDD存在的必要條件（關于參數u和m）也是充分的。作為這類型不一致的GDD的應用，我們構造了一些其他類型的設計，包括成對平衡設計，有向成對平衡設計，Kirkman frame，以及可分組覆蓋設計。
　　在第3章中，我們繼續(xù)研究了5-GDD，4-RGDD以及4-frame的存在性問題。雖然整個問題還沒有徹底解決，但我們已取得了很大的進展。我們的結果主要集

4、中在組相對比較大的情形。我們取得這些結果要歸功于兩類強有力的遞歸構造，它們是“雙可分組設計構造”和“Rees型乘積構造”。在應用的時候我們對這兩類構造都做了一些改進。此外我們還構造了一些較小的設計，包括型為2184，944，1818和3611的4-RGDD。
　　在第4章，可分組設計的概念擴展到了G-可分組設計。我們利用G-GDD構造了五個頂點的G-設計。此類設計的存在性問題最早由Bermond，Huang，Rosa和Sottea

5、u于1980年提出，并與光纖網絡中的業(yè)務疏導問題密切相關，但至今仍未徹底解決。我們完全解決了這個問題，同時對幾乎所有的n，確定了n階C-疏導的最小成本，這里C≤9。
　　在第5章，我們考察了長度為n的完備的q元t-刪位糾錯碼碼字個數所有可能的取值。由于在Levenshteǐn距離下半徑為t的球可以有不同的大小，所以完備的t-刪位糾錯碼的碼字個數可以是不一樣的，因而確定所有可能的取值是有意義的。當t=n-2時，t-刪位糾錯碼和有向填

6、充問題密切相關，后者的構造主要基于組合設計理論中的工具。在本章中，我們通過構造大量的不完全有向填充，基本上確定了完備的(4，2)q-DCC所有可能的大小，這里還剩下大小為62的(4，2)19-DCC和大小為196的(4，2)34-DCC沒有解決。
　　第6第7兩章主要研究常重碼(CWC)和常重復合碼(CCC)。已有許多種工具被用來確定常重碼和常重復合碼碼字個數的最大值，其中包括了一些組合的手段。我們對其中的可分組碼(GDC)和完全

7、可約超單(CRSS)設計比較感興趣。Chee，Ge和Ling提出了可分組碼的概念，并用來確定重量為三的最優(yōu)常重復合碼的大小。在第6章中，我們研究了重量為四、極小距離為六的最優(yōu)三元常重復合碼的構造問題。除了一小部分的長度外，我們基本上將這個問題解決了。完全可約超單設計與多元常重碼相關，一個(v，k，λ)-CRSS設計就是一個最優(yōu)（v，2（k-1），k）λ+1-碼。在第7章中，我們基本上解決了(v，5，2)-CRSS設計的存在性問題，除了可