最優(yōu)化網絡路由及常重復合碼.pdf

1、本文分兩部分,在第一部分中我們研究的對象是最優(yōu)化網絡路由,在第二部分中我們研究的是常重復合碼。 在網絡研究中,最優(yōu)化網絡路由現在已經成為一個值得考慮而且已被很多人關注的問題了。在最優(yōu)化網絡中,一個最優(yōu)的纖維能夠被利用到的最大的帶寬被分成很多通道,每個路由通道使用一個特定的波長。任意兩個通道能使用同一個波長當且僅當他們沒有相同的連接。關于我們所研究的最優(yōu)網絡我們用到多重分配波長技術,即被稱為WDM optical networks

2、。這個概念第一次由Alok Aggarwal,AmotzBar-Noy,Don Coppersmith,Rajiv Ramaswami,Raruch Schieber,Madhu Sudan提出。我們主要的工作就是要使得網絡中需要用到的波長數最少。因為這個問題的難度很大,所以到目前為止只得到了很少的結果。 本文主要用組合設計中的方法來研究n≥9時的在最優(yōu)化網絡中的路由。我們所做的工作以及得到的成果主要是以下三點： 1.我

3、們利用一個回溯算法得到了當n=9和n=10的最優(yōu)解。 2.我們給出參考文獻[45]中構造Steiner三元系大集的方法。這個方法在構造Steiner三元系大集中起了非常大的作用。相信這個方法在這個問題上也能發(fā)揮作用,我們希望利用這個方法能完美的解決這個問題。 3.我們對這個問題做了初步的研究,確定了一些必要條件并找到了幾個有用的HLESTS。 上面三點就是本論文的主要結果。當然,有些結果還是可以進行改進的。比如,

4、我們采用現在的模型和算法無法找到當h為偶數時在循環(huán)群下的EGDD(2,3,h3),但這并不意味著這個設計不存在。我們可以采用更加微妙的模式和更加高效率的算法進行試驗。這需要我們進一步的研究和探討。在第二部分中,我們介紹了常重復合碼。常重復合碼是一種特殊的常重碼,是指在每個碼字中每個符號出現的次數是給定的。常重碼在編碼理論中有很重要的作用,二元常重碼已被很多人研究過了。常重復合碼包括重要的置換碼,而且由于它的廣泛應用性,常重復合碼已被更多

5、的人所重視。我們主要是要研究(n,5,[3,1])3-碼。 在本文中,我們主要是用組合設計中的方法去研究常重復合碼。我們所做的工作以及得到的成果主要是以下三點： 1.我們對所要研究的這類碼字進行分析得到一些必要條件并且利用一些算法直接構造了一些最優(yōu)(n,5,[3,1])3-碼。 2.我們利用GDD和GDc進行構造(n,5,[3,1])3-碼,并且找了一系列的GDC。 3.我們構造了一類最優(yōu)的(24t+1,

6、5,[3,1])3-碼,并且t≥1。我們還證明了個數為4的(6,5,[3,1])3-碼的最優(yōu)解是不存在的。 上面的三點就是本文第二部分所要介紹的主要內容,我想這里還有很多地方可以改進的。比如,由于我們的算法不夠優(yōu)秀,我們還不能證明一些碼的存在性。而且對于(9,5,[3,1])3-碼,我們通過計算機算法遍歷完也沒有解,但我們還不能從理論上證明是不存在的,我們可以采用更加微妙的模式和更加高效率的算法進行試驗。這需要我們進一步的研究和