Abstract
During the recent years, the residue number system (RNS) hsa beenreceiving considerable interest due to its parallel and fault-tolerantproperties. In this dissertation, a new algorithm for single residue digiterror correction is proposed. This algorithm is fully based on the mixedradix conversion (MRC) and redundant MR digits can be used to establish alook-up table to correct single residue digit errors. The necessary andsufficient conditions for the proposed algorithm are also derived. Theproposed algorithm can be extended to correct errors in the quadratic RNS(QRNS). It can be shown that single digital pair errors in a QRNS can becorrected.Since the scaling and the residue-to-binary conversion can be completedvia the MRC, the relationship between the single error correction (ordetection) and the scaling (or residue-to-binary conversion) isinvestigated. Then two operations can be unified in one hardware therebyreducing the complexity of these implementations, The original scalingalgorithm will reduce the dynamic range. In this dissertation, thisshortcoming can be eliminated by the use of the polarity shift. Thescaling error es is analyzed and found to be limited to the interval of -1< es < 1. Since the scaling is often required in the computations ofdigital signal processing (DSP) which is the primary application of theRNS, an error correction circuit with scaling (ECCS) or error detectioncircuit with scaling (EDCS) will be very efficient in the fault-tolerantsystems for the DSP applications, Two examples for the application of theproposed ECCS, EDCS or error correction circuit with residue-to-binaryconversion are given :One is the fast Fourier transform (FFT) network andthe other is the infinite impulse response (IIR) filter. Based on theproposed algorithms, the fault-tolerant FFT networks and IIR filters canbe completed.Finally, a VLSI layout (using double metal CMOS process and two-phasenonoverlapping clock strategy) for the proposed single error correctionalgorithm is implemented. The moduliset {16,17,19,23,29,31} is used andthe total and dynamic ranges are about 27 and 17 bits, respcctively.Function and timing verifications are simulated. The chip latency is 8clock cycles and the throughput is about 10MHz. In this layoutimplementation, it can be shown that the proposed algorithm is suitablefor VLSI design.餘數數字系統(RNS)具有優良的平行處理及容錯特性,近來由於硬體價格的降低，使其再度受到極大的重視，在本論文中，作者針對單一餘數數字錯誤之更正提出一新型的演算法，此演算法依據混合基數轉換法(MRC) 之原理，而使冗餘的混合基數數字足以建立更正表，其所需的充分必要條件皆將於本文中被推導出來。此外，此演算法亦能推廣到二次餘數數字系統(QRNS)，作者證出在QRNS中，任何單一數字組之錯誤，皆能被更正。此演算法最大大的好處，就是能與定比運算(Scalig)結合在同一硬體上，而其定比誤差經分析結果，是介於－１到１之間，數位訊號處理(DSP)為RNS應用最廣的領域，而定比運算在DSP 中又常被使用，因之，此演算法將能十分有效地使用於具容錯性質的DSP 應用中，諸如快速傅立葉轉換(FFT) 及無限脈衝響應濾波器(IIR filter)等。最後，作者亦完成了此新型演算法的超大型積體電路(VLSI)之佈局，功能及時序的模擬，並且提出了具有層次性及模組性的設計方法。依此方法，將可發現此演算法相當適合於VLSI的設計。