奇偶排序網路的障礙診斷

Abstract

本篇論文中﹐吾人為第一次對於奇偶排序網路中的單一障礙之檢測以及定 位進行研究。在這個研究中﹐吾人發現三個測試樣本已經足夠去定位排序 網路中的單一連結障礙﹐而且四個測試樣本也足夠去檢測一個排序網路中 的單一排序元件障礙。定位排序元件障礙所需要之測試樣本是因障礙之形 式而決定：對大部分的障礙形式而言﹐這數目小於四個特定的測試樣本﹔ 對其它的障礙形式而言﹐吾人將在論文中提出一些測試樣本產生及二元搜 索程序來產生測試樣本﹐在此定位測試中所需要之樣本數目小於 (n+ log2n)﹐其中 n=log2N且 N為此排序網路輸入的數目。□ In this thesis, we study, for the first time, detection and location for single faults in odd-even sorting networks. In the study, we have found that three tests are enough to locate single link fault and four tests are sufficient to detect single sorting element fault in an odd-even sorting network. For location tests for sorting element faults, the numbers of tests depend on the type of faults occurring at the sorting element: For most types of sorting element faults, the numbers are less than four specific tests; For the other types of faults, we have presentd the test generation procedure and binary search procedures in the thesis to generate the tests. The numbers of location tests are less than (n+log2n), where n= log2N and N is the number of inputs of the sorting network.