本文提出關於快速傅立葉轉換(FET) 容錯設計的一種新方向。基本上，偵測對象是
建立在蝶式模組(butterfly module)。因此可達到即時偵錯的功能，而不像先前其
他方法必須等整個FET 計算完畢後再來執行偵錯動作。文中提出三種FET 的容錯設
計方法：一種並行偵錯蝶式模組(CED-butterfly) 與二種並行改錯蝶式模組 (CEC-
butterfly)。在CED-butterfly 設計中，錯誤可在每個蝶式運算中被偵測出來，而
更可藉由簡單的繞組方式來達成錯誤改正。在CEC-butterfly 中，錯誤可直接在蝶
式運算中被改正過來。由於考慮到晶片面積和速率效應，所提三種設計便有不同的
應用時機。
首先，第一種是time redundancy CED-butterfly 設計，適用於強調高速度的應用
中。在此種設計，butterfly 運算中之複數計算的實部與虛部均由硬體電路直接實
現。藉由對稱與交換的設計策略，第２次的計算可由交換實、虛兩部電路以執行之
。此法的hardware overhead 約為7/(4n＋8) ，ｎ是字元長度，偵錯能力是與雙模
組技術相同。
第二種是RECO的CEC-butterfly ，是由一個CEC 串並式(serial-parallel) 乘法器
與兩個CEC 加法器所組成。基於time redundancy 的觀念，使用迴旋移位位元的重
覆計算(RECO)將乘法器與加法器設計成具有並行偵錯(CED) 功能，原理是利用第一
次的結果與第二次使用旋轉移位位元所提出的結果相比較以達到偵錯的目的。此種
特別適用於所需晶片面積較少及速度效能較低的應用。
第三種是針對不同晶片面積與速度效能之需求而設計出的CEC-butterfly ，基本觀
念是將一個算術陣列分裂成ｍ個部分，此算術運算可由一個部分經ｍ次反覆計算而
達成。由此可將３個部分設計成TMR 的形式經ｍ次反覆計算以達到容錯的目的。所
需額外電路僅是多工器、栓鎖器、選擇器，而且更可由選擇一適當的ｍ值來降低這
些額外電路的比例。

摘要
List of Figures
List of Tables
圖
表
誌謝
Contents
Chapter 1 Introduction
1.1 FFT Processor
1.2 Fault Tolerance
1.3 Dissertation Organization
Chapter 2 Motivation
2.1 Problem Statement and Related Work
2.2 The Proposed Mechanism
Chapter 3 CED-Butterfly by Exchanging Strategy
3.1 The Fault Model
3.2 Methodology of Exchanging Strategy
3.3 The Implementation of CED-Butterfly
3.4 The Design of Real-Time Fault-Tolerant FFT Processor
3.5 Comparison with Others
3.6 Summary
Chatper 4 CEC-Butterfly by RECO
4.1 Methodology of RECO
4.2 Concurrent Error-Detectable Serial-Parallel Multiplier by RECO Scheme
4.3 Error Detection Capability
4.4 Fault-Tolerant Serial-Parallel Multiplier
4.5 Summary
Chapter 5 CEC-Butterfly by Partitioning Technique
5.1 Design of Error Correction in Adders
5.2 Design of Error Correction in Array Multiplier
5.3 Design of Error Correction in Array Divider
5.4 Summary
Chapter 6 conclusions
References