о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3610ڡVol.36No.101999



FCTĲṹ
º̡ë־աҶ
ժҪһֿɢұ任(FCT)·Ĳ(CED)ṹ.Ϊ˴ﵽ100%ĹϸʣFCTûڵ3ɢұ任B.G.Lee㷨ͽṹʵ.õķǻ㷨ĲݴΪ㷨ݴ(ABFT)Ӳ.Ľṹ֤100%Ĺϼ.ʵӦУֳЧӦзֳЧӦϵͳϸʵӰ죬˽.
ؼʡɢұ任⣬㷨ݴ, ϸ
ͼšTP306
A CONCURRENT ERROR DETECTION SCHEME
FOR FCT NETWORKS
CHEN He, MAO Zhi-Gang, and YE Yi-Zheng
(Microelectronics Center, Harbin Institute of Technology, Harbin 150001)
AbstractA concurrent error detection(CED) design is proposed for fast discrete cosine transform(FCT). To achieve the goal of 100 percent fault coverage, FCT is realized by using a butterfly architecture of the B.G.Lee fast algorithm based on DCT-III. Algorithm-based fault tolerance(ABFT) is used for error detection because ABFT is a low-cost system-level concurrent error detection and fault location scheme. The error detection capability of this scheme is analyzed. When the FCT is implemented with hardware, errors due to finite word length is unavoidable. So the influence of large truncation errors on the throughput and fault coverage is discussed and a conclusion is obtained.
Key wordsfast discrete cosine transform, concurrent error detection, algorithm-based fault tolerance, throughput, fault coverage
1
ɢұ任(DCT)չܿ죬ĿǰFCTѱ㷺ӦźŴУرͼѹ˲ͨϵͳ.VLSIķչΪFCTЧʵṩ.ǴԪͬһоƬɸټ㣬ԪеĹϽӰϵͳĹ.Ϊ˱֤ϵͳڼпݴǱҪ.һֻ㷨FCTϵͳFCTṹB.G.Lee㷨ͽṹ1.û㷨ݴABFTΪABFTһϵͳĽṹʵݴĵͺķѵϵͳݴ˼Ӳ.
ڹȥû㷨ݴ˼˼ֿٸҶ任(FFT)ⷽ24.FCTͽṹFFT۷չƣ˻ûFCTĻ㷨ݴṹ.ڷFFTCEDƺ󣬸FCTṹصFCTCED.
2B.G.Lee㷨FCTṹģ
2.1B.G.Lee㷨FCTṹ
x(n), n=0,1,N-1, x(n)DCTΪ

(1)
x(k)ǵkDCTϵ.
ɢұ任IDCTΪ

(2)
ΪЧؼDCT㷨B.G.Lee㷨ΪдԵĿ㷨֮һ.ǱӦ(k)B.G.Lee㷨8FCTṹͼͼ1ʾ.


(a)ϵͳͼ

(b)εԪ
ͼ1 B.G.Lee㷨8FCTϵͳͼ
ͼ1ʾNFCTɷΪv+log2N-1(N=2v)v㡢log2N-1ӷ.Ľ8FCTΪй֤NFCTͬ.ͼ1пɿ㵥ԪһǺӷ㵥Ԫ+ʾһǵ㵥ԪCiʾ.㵥Ԫṹͼ1(b)ΪabΪcd㵥ԪļΪ
c=a+b
d=(a-b)Ck


2.2ģ
ԻڵԪVLSI˵ͳżģڴѡȷԲѲ.ƪǲģ鼶ģͣ2ݣһ͵Ԫ9ֹϣģͼͼ1(b).ͼ9ֹΪΪ4Ӽ{1}{2}{368}{4579}.ںϼӵǲϣ磬Լͳ˷¹ϵʽp4=(p7-p9)p5,piΪ/ݶˣp7p9p5һĹϣͨտɵ¶p4й.ˣÿһģֻ迼4{1}{2}{3}{4}ñʾFCTеij˵Ĺ.ӷģ鼰2log2Nģһ𹹳FCT磬ֻ迼ÿģ鼰ӷģ롢ϣj=0,17.
3FCTĲϵͳconcurrent error detectionCED)
3.1FCTCEDݴϵͳ
ڽۻB.G.Lee㷨FCTṹ.ǵĿýþݴFCTṹ.1984Wangɢұ任Ϊ45ݣDCT-󣬺Աӣ

(3)

(4)


(5)
ʽ(5)ͨx(0)УͱȽϣɽһ򵥵Ĺϼṹͼ2.


ͼ2 Lee㷨8DCT-CEDϵͳͼ
ڴģ59%ĹϼⲻΪDCT-͹ϵʽΪ

b˷ĴУͼⲻ˹ǲɲ.ΪѡDCT-㷨ṹDCT-Աӣ

(6)

(7)
ɴ˹ʽɵ

(8)
ʽ(8)ǿɹDCT-CEDϵͳͼ3.ͼ3ɼCEDϵͳԭݴϵͳ˼˷УͼӷTSCȽ.x(0)˼һӳΪ˱ʱϵһ.


ͼ3 DCT-CEDϵͳͼ
3.2CEDϵͳϼ
ǶɷFCTеiĵj˵һġ˷֮ǰĵk˵õΪGK()2ݣiĵjΪ1Ϊ0ʱ˷ǰk˵õĽ:

ǶeΪĴ.УͼӷΪe0,,˵ǲɲ.Ǳ뱣֤һϽ.e0,裬֤йϿɲ⣬.
ڱУΪ֤㣬ǶλƱʾݣis1s2s3ʾjd1d2d3ʾɱʾΪ.
1. 
֤. 
2. 3<i<6ʱ
֤. ͼ3оƵɵó
1֪ԣ
3. i3ʱ
֤. ͼ3пɵó
ڶi3Ϊͽṹƹ㵽һi3


d3=0ʱ12֪
d3=1ʱǽչ12֤.
˶i3.
1. FCTһϡһ˷йϻУͼӷһйʱʽ(8)CEDƿɼЩ߼.
    ֤. 123ǿ֪FCTڲһϣϵͳɼ.ڷУͼӷ˵һϣTSCȽ.ϣCEDϵͳɴﵽ100%Ĺϸ.
3.3CEDϵͳӲ
NFCTʵΪ
˷M=N/2log2N ӷA=3N/2log2N-N+1.
ݴϵͳȣڳ˷ΪڼӷΪΪӷӲӶȽϳ˷ӲӶСö࣬ϵͳӲֻǳ˷Ӳȼɣ
ϵͳ˷УFCT㲻ͬһͨ·ϣ˶FCT˵ʱϵ.ϵͳһ˷ӷĹʱ˴ϼźŵʱΪ TM+3TATMTAֱΪ˷ӷʱ.
4ض
FCTʵӦУֳЧӦڴ룬FCT޴ʱTSCȽҲܲ.Ϊ˽⣬TSCȽһƫ.TSCȽ˵Ĳڦʱ(retry)ԽãһݣԾ˲еĹܹģЧֳЧӦ.һСĦǿܻӰΪܶԻִУһĦֿʹһЩܹϲɲ⣬ǽ۴CEDϵͳϸ.ڷǰǼϵͳԶʵ֣õΪƲ룬ֳΪضϴ.ƣ縡ƣƣԭ롢룩ֳ봦ɰͬķз.
4.1
F(k)ΪkFCTϵĽضף6нķΪƽֵΪЦ(k)ΪλУΪķq=2-bbΪֳ.TSCȽܵΪ=F(0)bƽֵΪ.F(0)F(1)F(N-1)һƽֵΪ0Ϊ.ļ޶ΪFһֲ̬ƽֵΪ0Ϊ˵ķֲһ׼ֲ̬.ϵͳ£2ݣ

1г˲ͬʱϵͳ.
1ϵͳ

0.00.51.01.52.02.53.03.5
0.50.6180.7590.8820.9560.9880.99731.000

ɱ1ɿϵͳǵѡйأĦζŸߵ󣬲ɲ࣬۹ϸ.
4.2ϸ
ϸʶΪɲϵͳзĹ֮.ɹܹĹܴe(i)һڣ-11ھȷֲİҼe(i)FCTÿһܷ.G(k)Ϊe(i)ĵkFCTϵƽֵΪ0䷽ΪڵiĹܹϿӰMiFCTУ2ǲͬNʱֵ.
2ֵ

N4816
0.1720.13450.1299

S=F+GSʾTSCȽֵܵSƽֵ0Ϊ˹ϸΪ3г˲ͬNֳֵǡϵͳĹϸ.
3ϵͳĹϸ

= 
=0.759=2.
=0.956=3.
=0.9973
bN481648164816
40.9440.9961.000.8930.9921.000.8410.991.00
80.92040.9941.000.83360.991.000.7570.9841.00
160.8860.9921.000.77180.9861.000.66720.9781.00

ӱ3пɿNbͬʱԽϵͳϸԽ.ͬʱͬNֳbԽ󣬹ϸԽ󣬶bͬʱNԽ󣬹ϸԽ.ϵͳĹϸʣɴNb֣ϸʵ߻Ľͣ NbǵѡҪע.
ʵʱϵͳ˵ΪNΪ̶ֵ˱ȽϺõĽ취b.⣬ǻɿʵʱϵͳ˵ɲϵļʺܵͣΪıֵܸߣԹܹϸͨҪȽضϴö.һ£ֻҪйܹϣCEDϵͳͿɼ. 
5 
ڱУԻB.G.Lee㷨ͽṹFCT磬һֻ㷨Ĳݴϵͳ.ϵͳнϸߵĹϸʣȽϵͣʵӦüֵ.
߼飺º̣Ů19703ʿҪоΪASICơݴ·ơDSP.
ë־գУ19619ڣҪоΪASICơݴ·ơɵ·ԡӲȫ.
ҶŮ19372ʿʦҪоΪԶɵ·Ƶ.
ߵλҵѧ΢ġ150001
ο
1Lee B G. A new algorithm to compute the discrete cosine transform. IEEE Trans Acoust Speech Signal Process, 1984, 32(12): 12431245
2Jou J Y, Abraham J A. Fault-tolerant FFT networks. IEEE Trans Comput, 1988, 37(5): 548561
3Wang S J, Jha N K. Algorithm-based fault tolerance for FFT networks. IEEE Trans Comput, 1994, 43(7): 849854
4Oh C G, Youn H Y. On concurrent error detection, location, and correction of FFT networks. In: Proc IEEE FTCS'93 Toulouse, France, 1993. 596605
5Wang Z. Fast algorithms for the discrete W transform and for the discrete Fourier transform. IEEE Trans Acoust Speech Signal Process, 1984, 32(4): 803816
6Yun I D, Lee S U. On the fixed-point-error analysis of several fast DCT algorithms. IEEE Trans Circuits Syst Video Technol, 1993, 3(1): 2741 
ԭյڣ1997-12-29;
޸ĸյڣ1998-03-23.
