臺灣博碩士論文加值系統

Chernoff上限計算廣泛運用於數位通訊系統及高速網路效能評估，通常原始資料源( Real Source )是複雜而難加以直接用於計算Chernoff上限，為方便簡化計算，常用之特性化方法為假設原始資料源為有限狀態之資料源，此種特性化後之資料源，本文稱之為擬資料源( Pseudo Source )。常見擬資料源產生方法為動差符合( Moment Matching )，但以動差符合特性化產生擬資料源於推測原始資料源Chernoff 上限，並不能無誤地保證其確實為原始資料源Chernoff上限之上界，因動差符合特性化產成擬資料源其隨機變數次序( Stochastic Order )無法確定大於原始資料源。
為解決擬資料源經以特性化原始資料源產生仍可用於推測原始資料源Chernoff上限之上界，本文依據隨機變數次序關系之觀念，提出一量化特性化原始資料源產生擬資料源之方法，以此擬資料源所求得Chernoff上限稱之為擬Chernoff上限( Pseudo Chernoff Bound )，此擬Chernoff上限之 可以多項式形式求得，無需求解非線性方程式，原於求解原始資料源Chernoff上限之 所遇，且此擬Chernoff上限確實保證為原始資料源Chernoff上限之上界，因量化特性化原始資料源產生之擬資料其隨機變數次序大於原始資料源。
最後引用量化特性化原始資料源產生擬資源於模擬無線通訊二位元通道符碼錯誤率問題與網路有效頻寬參數之計算。由數值模擬結果顯示，以量化特性化原始資料源產生擬資源，用此擬資源所求得之擬Chernoff 上限，確實可做為原始資料源Chernoff上限之上界。

Chernoff bound is a well-known upper bound that has been extensively used in the performance analysis of high-speed network and digital communication field. It is not easy to calculate the Chernoff bound of the real source. For simply working, to make the assumption that the real source with finite-state is a common method. We call the real source after being characterized as pseudo source. Usually, the researcher uses the moment match method to characterize the real source and get this pseudo source. But under some conditions, the Chernoff bound of this pseudo source with moment match to the real source may not be a upper bound of the Chernoff bound of the real source. Because the stochastic order of this pseudo source with moment match to the real source could not be guarantee more than the real source.
For solving this problem, based on stochastic order relation we investigate and propose a quantation algorithm to characterize the real source. The Chernoff bound of this pseudo source with quantation the real source could be got. It forms a polynomial format while calculate the theta of the Chernoff bound of this pseudo source with quantation the real source. Comparing with the real source, it forms a nonlinear format while calculate the theta of the Chernoff bound of the real source. Moreover, because the stochastic order of this pseudo source with quantation the real source is more than the real source, the Chernoff bound of this pseudo source with quantation the real source must be the upper bound of the Chernoff bound of the real source.
Finally, apply this quantation the real source algorithm on wireless binary channel symbol error and network effective bandwidth problems, it shows that the pseudo Chernoff bound exactly estimates the Chernoff bound of really source.

中文摘要 I
ABSTRACT III
目錄 V
圖目錄 VII
表目錄 VIII
第一章 簡介 1
1-1 CHERNOFF 界限用途與特性化資料源 1
1-2 CHERNOFF 上限簡介 3
1-3 內容大綱 6
第二章 擬資料生成原理與方法 8
2-1 隨機變數次序 8
2-2 量化特性化原始資料源 14
2-3 擬資料源求解擬CHERNOFF 上限 18
第三章 二位元對稱通道與數值擬模 21
3-1 二位元對稱通道 21
3-2 二位元對稱通道數值模擬 23
第四章 網路頻寬估計應用與數值擬模 27
4-1 網路頻寬需求估計之原因 27
4-2 有效頻寬參數 32
4-3 量化網路流量資料求解有效頻寬參數 36
第五章 結論 46
第六章 參考文獻 48

[1]F.P.Kelly, ” Notes on Effective Bandwith,” http://www.statslab.com.ac.uk/frank
[2]Y. M. Jang and B. G. Kim, “Chernoff Bound Approach for Connectoin Control in Broad band Satellite Systems,” IEEE Communication Letters,Vol. 3, No. 5, pp.154-156, May 1999
[3]K. Shiomoto, N. Yamanaka and T. Takahashi, ”Overview of Measurement-Based Control Admission Control Method in ATM Networks,” IEEE Communications Surveys,http:// www.comsoc.org/pubs/surveys,first quarter, 1999
[4]曹士林,”Matlab 輔助通信系統設計”,pp397-398,1th ed,滄海出版社
[5]H. Yong, W.Lee, and Jon W.Mark, “ATM network traffic characterization using two types of on-off sources,” IEEE IFCOM, pp152-159,1993
[6]H. Chernoff, ”A Measure of Asymptotic Efficiency for Tests of a Hopothesi based on the sum of Observation,” Annals Math. Stat.,23, pp 493-507,1962
[7]R. G. Gallager, “Lower Bounds on the Tails of Probability Distribution,” MIT, RLE, QRP 77,pp277-291,1965
[8]C. E. Shannon, R. G. Gallager, and E. R. Berlekamp, “Lower Bounds to Error Probability for Coding on Discrete Memoryless Channels: I,” Information and Control,Vol. 10, No. 1, pp 65-103, 1967
[9]I. M. Jacobs, ”Probability of Error Bounds for Binary Transmision on the Slow Fading Rician Channel,“ IEEE Trans. Information Theory, Vol. IT-12, No. 4, Oct, 1966
[10]Henry Stark and Jon W.Wood, ”Probability, Random Process, and Estimation Theory for engineers”, pp132-133, 1th ed,Prentice-Hall Press,1986
[11]T. H. Lee and K. C. Lai, “Characterization of Delay Sensitive Traffic”, IEEE/ACM Trans on Networking, pp.499-504,1998
[12]C. Courcoubetis, V.A. Siris, and G.D. Stamoulis, “Application of the Many Sources Asymptotic and Effective Bandwidths to Traffic Engineering”, Telecommuncation System., 12:pp167-191,1999
[13]Sheldon M. Ross, ”Stochastic Process,”2 nd ed,Wiley Pressed
[14]M. Shaked and J. G. Shanthikumar ,”Stochastic Orders and Their Applicatoins,” Academic Press, 1994.
[15]曹士林,”Matlab 輔助通信系統設計”,pp411-414,1th ed,滄海出版社
[16]C. Courcoubetis and Vasiliso A. Siris “Procedures and tools for analysis of network traffic measurements”, Elsevier Science
[17]F. P. Kelly, S. Zachary, and I. Zeidins, ”Stochastic Networks: Theory and Application”, pp 141-168, Oxford University Press, 1996
[18]C. Courcoubetis, F. P. Kelly, “Buffer overflow asymptotics for a switch handing many traffic source”, J. Apple. Prob., 33:886-903, 1996
[19]Jon G. Proakis,”Digital Communications, ”pp454-456,4th ed, McGraw-Hill Press,2001.
[20]Jon G. Proakis, ”Digital Communications, ”pp792-794,4th ed, McGraw-Hill Press,2001.
[21]Simon Haykin, ”Communication Systems”,4th ed, Wiley Pressed
[22]Feher, Kamilo. , “Wireless Digital Communications: Modulation and spread spectrum applications”, 1st ed, Prentice-Hall Pressed
[23]S. V. Nagaev and I.F. Pinelis, “ Some inequalities for the distribution of the sums of indepentent random variables,” Theorey of Probability and it Application,22:248-256, 1977