о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



ֵ·¸
ۡӦ衡ʩ豦
ժҪֵ·ϵͳԵҪ.нһֻ·Ľṹģͣʵֵ·ܵĻģʵֵ·⹦ܵļּɣ˱ڲУĲƵһ¸ǿϱաǿ롢ǿУ顢k-ݴǿϱաk-ݴǿk-ݴǿУ飬оֵ·Ҫ֮Ĺϵ֤ûģԹвͬԵĻ·.
ؼʡУ飬ǿϱգǿ룬k-ݴǿϱգk-ݴǿ룬·
ͼšTP302.8TP331.1
NEW CONCEPTS OF CONCURRENT ERROR DETECTION FOR DIGITAL CIRCUITS
JIANG Jian-Hui SHI Hong-Bao
Institute of Computing Technology, Shanghai Tiedao University, Shanghai 200331
MIN Ying-Hua JIANG Jian-Hui
CAD Laboratory, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080
AbstractConcurrent error detection is important for improving dependability of digital circuits and systems. In this paper, a structure module for basic concurrent error detection circuit is built. It is constructed by a basic functional module and a detector. Several new concepts, reduced strongly fault secure, reduced strongly variable disjoint, reduced strongly self-checking, k-fault-tolerant reduced strongly fault secure, k- fault-tolerant reduced strongly variable disjoint, and k- fault-tolerant reduced strongly self-checking are defined to characterize circuits with partially self-checking capability. The relations among all of these concepts about concurrent error detection are presented. Interconnection conditions, with which the basic functional modules and detectors must satisfy to construct basic circuits with different concurrent error detection properties, are proved.
Key wordspartially self-checking, reduced strongly fault secure, reduced strongly variable disjoint, k-fault-tolerant reduced strongly fault secure, k-fault-tolerant reduced strongly variable disjoint, circuit interconnection
1
⡢ϰȫͲУֵ·ϵͳݴҪ⼼ֱΪϵͳعṩ֧֣ϰȫڷֵ·ַǰȫУڱ֤ϵĵ·Ծܵظȷ12.ֵ·ɹģӦĲ󡢹ٶȵķߣǿ뱣֤ܼɵ·Ļ֮.
һ͵Ĺ()̰()⡢λУعͻָȲ.һĵ·ڲʱϣ书ְȫȷͬʱӦӦĲ϶λָʾϢ.·Զڲ(·)Ƿڹϣֻ(·в)κӼ()13.ˣΪһݴϵͳ߹()о⼼Ծ൱Ҫ.
80ǰйز⼼оҪɹж˽Ϊϵͳܽ13.ĵ2ֽһֻ·(¼ƻ·)Ľṹģͣʵֵ·ܵĻģʵֵ·⹦ܵļ(detector)ּɣ·ʸֳɹͲָʾ֣3ܽУ·ĻģУ(checker)Ļԣ4ʸֵĽṹģ¶˻·ԣһڲУ(partially self-checkingPSC)ĲƵ¸оЩ¸и֮ĹϵЩ¸ָ˹첢·;5֤ûģԹвͬԵĻ·.
2·ģṹϼ
һmn߼·ʵֵĺʾΪGпܵԭʼʸX(ʸΪm)ȫ뼯S(Xm)пܵԭʼʸY(ʸΪn)ȫS(Yn).·кϷʸĺϷʸSn(Xm)ӦкϷʸɺϷʸSn(Yn).ԱʸϷʸɣǷʸз.S(Xm)-Sn(Xm)ΪǷǷʸSa(Xm).S(Yn)-Sn(Yn).ΪǷʸSa(Yn).
·ԭʼYɱָΪ(ZE)УZ(ʸΪu)E(ʸΪv) ֱΪ·ĹͲָʾ4 u+v=n.еĹͲָʾֱɻ·ĹS(Zu)ͲָʾS(Ev).ƵأS(Zu)»֣S(Zu)=Sn(Zu)Sa(Zu)УSn(Zu)Sa(Zu)ֱʾϷʸͷǷʸ.S(Ev)Ҳ»֣S(Ev)=Sn(Ev)Sa(Ev)УSn(Ev)ǵ·Ĺ޲ָʾʸ·üеʸ书ȷģSa(Ev)ǵ·ֲָʾʸ·üеʸڲ˹ϣĲѱ⵽.ȻS(Yn)=S(Zu)S(Ev)˴߼ϿǣS(Yn)ɻΪ3֣
S(Yn)=Sn(Yn)Sd(Yn)Su(Yn),
ÿһֵɷֱΪ
Sn(Yn)={(Z,E)|ZSn(Zu)ESn(Ev)},
Sd(Yn)={(Z,E)|ZS(Zu)ESa(Ev)},
Su(Yn)={(Z,E)|ZSa(Zu)ESn(Ev)}.
УSd(Yn)ʾʸSu(Yn)ʾδ()ʸ˻·ķǷʸ.ڼΧĽǴӻģˣôʸʵ壬ZΪǷʱEܸϷˣɼSu(Yn)=ʾռ.
һ·ּ(ͼ1ʾ)һʵֺĻģ飬ʵֺdļ.ͼ1УWS(Ww)(ʸΪw)ǻģҲǼ룩ǰ.S(Ww)ǻģȫʸȫʸҲɻΪϷ뼯Sn(Ww)Ƿ뼯Sa(Ww)ཻӼ.ˣXS(Xm)Ц(X)=Wd(W)=YG(X)=Y.(ZE)ʾΪ(Zd(W),Ed(W))(GZXGEX)£ӦЦZd(W)=GZ(X)ͦZd(W)=GE(X).

ͼ1·Ľṹģ
һУ·(ͼ2)ģеļɿһ鴫(ʵ֦ZdֱӽWһĹ)У(ʵ֦Ed)ɵ.

ͼ2У·ĵͽṹ
·첢ϵͳĻԪ.
Լرָоֵ·1.·ǵеɵĹϼΪFڲϺ·ʵֵĺʾΪGf.
1. ·еÿһϾɰż򿪹ؼϼģͻ.
Բͬʵʵ·Ҫòͬϸ̶ȵĹϼ裬Աر䲢.ļ2һϸĹϼ裬Ϊ岢ȫУ(totally self-checkingTSC)Ļ.3ף5йعϼļ޸.
2. ·һʱֻһϣĹ֮ʱ㹻ʹʸڵ·.
3. һӰ(У)ĹϷ󣬵·㹻ʱڻģ(У)һǰʹü(У)ܹϷ뼯еʸӵ.һӰģĹϷ󣬵·㹻ʱڻģ(У)һǰʹûģܹϷ뼯еʸӵ.
3У·
3.1ģ(·)Ĺ;
У·ĲԿȫУʵֵνȫУĿ(TSC goal).ѵ·ʸĳֲ룬ȫУĿָڸĹϼ£·ڹ϶ĵһǷһ֣67.ʵȫУĿ;.
;1. ʹ·ͬʱйϱ(fault secureFSE)Բ(self-testingST)ԣ13.һ൱ϸʵ;Ϊ·ĿԺܴ󣬶fFĵ·޷FԲ.ˣ·;ʵֽΪ.
;2. ʹ·ǿϱ(strongly FSESFSE)ԣ67.
VLSIʵּ£һ;ʵҲһ.ʵʵ·ͨƵ·ǵĹеĳ޵ʵȫУĿ(;).
;3. ʹ·k-ݴǿϱ(k- fault tolerant partially SFSEk-FT PSFSE)ԣ8.
·еȫУԽFĳӼЧʱòУ19ݣͨС·ǵĹϼ޵ʵȫУĿķ.
;4. ʹ·вУԣ1.
⣬·ԺϷ뼯FSTFSTFԲԵģԺϷ뼯ĳӼFSTĳӼǹϱյģԲ110.Ƶأʸܼ·еĹϣǿԲ(strongly STSST)б110.
3.2У
һ·(code-disjointCD)ϱպԲԣõ·ΪȫУУ13.Ȼе£ϱԶУԲǱģ11ݣУɱΪУУ.УԲ㣬3ǰ£ɹһ־ǿ(strongly CDSCD)ԵУ5.Ե·ĲͬʵּУʵַ.
(1) k-ݴǿУk-ݴǿϱУ812
ǿУһǽʵֵ.ǵVLSI·ڿؼͲϵص㣬ʵʻõk-ݴǿ(k-fault-tolerant partially SCDk-FT PSCD) Уk-ݴǿϱУ.ǿУk-ݴǿУҪڣǰ߿ͨһսУеۻϼ⵽k-1ϣܷ񱻼ǲȷ.k-ݴǿУڲһΪkĹкʹڷǱ״̬.ʱһּӵ(ȼڻ·вk+1)ǲ֤.
(2) ǿУУ13
һϵͳкжвͬԵУΪʹﵽȫУĿ꣬һǿУ(strongly self-checkingSSC)Уͬʱǿϱպǿ.
(3) k-ݴǿУУ8
ǿУk-ݴǿУĹϵҲһk-ݴǿУ(k-FT partially SSCk-FT PSSC) Уף8ݳ֮Ϊk-ݴǿͲǿϱУ.
4ʸģ»·
4.1
ͼ1ʾĻ·ṹģ£ģ·ĲԵıֱУ·йԵĶ壬ڼʸ˻֣йؼɲ¶.
ҪǼģʸĺϷԣ·Ĺϼʱؼ.Ĳñ(variable disjointVD)һܣ1.ʸͳһؿñ뷽ʽɵ֣Ծ.
1. һǱģ WSn(Ww)ЦZd(W)=GZ(X)W=XXSn(Xm)ҦEdSn(Ev)ߢWSa(Ww)ЦZd(W)Sa(Zu)ͦEd(W)Sa(Ev).
ǵĵϼΪFd.
2. һFdǹϱյģfFdWSn(Ww)ЦZdf(W)=Zd(W)ͦEdf(W)=Ed(W)ߦZdf(W)Sa(Zu)ͦEdf(W)Sa(Ev).
3. һFdԲԵģԪfFdWSn(Ww)ЦZdf(W)Sa(Zu)ͦEdf(W)Sa(Ev).
4. һ·FdȫУļǱĺȫУ.
5. ޹ڼ䣬ǹϱյ.һСf1,f2fk-1fjFdj=1,2,,k-12kܡFdWSn(Ww)ЦZdf1,f2,,fk-1(W)=Zd(W)ͦEdf1,f2,,fk-1(W)=Ed(W)ߦZdf1,f2,,fk-1(W)Sa(Zu)ͦEdf1,f2,,fk-1(W)Sa(Ev).ҶԹСf1,f2,,fkWSn(Ww)ЦZdf1,f2,,fk(W)Sa(Zu)ͦEdf1,f2,,fk(W)Sa(Ev)ԹСf1,f2,,fkǿϱյ.
6. һFdǿϱյģFdейɵйжǿϱյ.
7. kһСһСf1,f2fk-1fiFdi=1,2,,kʵֺdf1,f2fkļɥʧϱԣҲһϷʸܼ⵽ù.ôük-ݴǿϱյģüǹϱյģҶкκq1qk-1߼ǹϱյģ߹Сf1,f2fqɱ⵽.
8. ޹ڼ䣬Ǳ.һСf1,f2fk-1fj.Fdj=12,,k-12kFdWSn(Ww)ЦZdf1,f2fk(W)=Zd(W)ͦEdf1,f2fk(W)Sn(Ev)WSa(Ww)ЦZdf1,f2fk(W)Sa(Zu)ͦEdf1,f2fk(W)Sa(Ev)ҶԹСf1f2fkWSn(Ww)ЦZdf1,f2fk(W)Sa(Zu)ͦEdf1,f2fk(W)Sa(Ev)ԹСf1f2fkǿ.
9. һFdǿģFdейɵйжǿ.
10. kһСһСf1,f2fkfiFd,i=1,2,,k,ʵֺdf1,f2fkļɥʧԣҲһϷʸܼ⵽ù.ôük-ݴǿģüǱģҶкκq1qk-1߼Ǳģ߹Сf1,f2fqɱ⵽.
11. һڹϼFdǿУģκιϲǰǱģԪfFdߢټԲԺ͹ϱյģߢڼǹϱյģǽǷʸӳǷʸһfFdڸùУٻߢڳ.
12. kһСһСf1,f2fkfiFd,i=1,2,,k,ʵֺdf1,f2fkļɥʧ͹ϱԣҲһϷʸܼ⵽ù.ôük-ݴǿУģüǱ͹ϱյģҶкκq1qk-1Ǳ͹ϱյģ߹Сf1,f2fqɱ⵽.
13. һ·FdǲУļǱĺͲУ.
УЩɴĩейزο׵ضֱ綨7ף14ݵظ.
4.2ڲУĲ¸
;1;4ʵֵĵ·Ĳμ.ڹϱ⵽ʱͺ(;2)Ĺеĳȼ(;3)·ǵĹϼС(;4).;2;4˼룬·ʵȫУĿĵ5;.
;5. ھĹF(FF)ʹ·оǿϱ(reduced SFSERSFSE).·Եظɶ.
14. һ·Ǿǿϱյģٵ·Sn(Xm)FSTFFFԲԵģҢڶSSn(Xm)Sn(Xm)FSEFSTǹϱյģ߽ڳFSTеһϲ·Ķϣٺ͢ڣ߽ڳ.
һ˼룬ɶ徫ǿ(reduced SVDRSVD);ǿУ(reduced SSCRSSC).
15. һǾǿģټǲУģڼǱģFdSTFdFdFdеһϲĶϣٻڳ.
16. һǾǿУģ޹ϵǱģҢټSn(Xm)FdSTFdFdFdԲԵģҶSSnXmSn(Xm)FdSEFdSTǹϱյģߢڶSSnXmFdSEǹϱյģҽǷʸӳΪǷʸ.FdSTеһϲĶϣٻߢڳ.
;3;5˼룬·ʵȫУĿĵ6;.
;6. ʹ·k-ݴǿϱ(k-fault-tolerant reduced SFSEk-FT RSFSE).·Եظɶ.
17. kһСһСf1,f2fkfiF, i=1,2,,kFFʵֺGf1,f2fkĵ·ɥʧϱԣҲһϷʸܼ⵽ù.ôõ·k-ݴǿϱյģõ·ǹϱյģҶкκq1qk-1ߵ·ǹϱյģ߹Сf1,f2fqɱ⵽.
18. kһСһСf1,f2fkfiFdi=1,2,,kFdFdʵֺdf1,f2fkļɥʧԣҲһϷʸܼ⵽ù.ôük-ݴǿ(k-fault-tolerant reduced SVDk-FT RSVD)ģüǱģҶкκq1qk-1߼Ǳģ߹Сf1,f2fqɱ⵽.
19. kһСһСf1,f2fkfiFdi=1,2,,kFdFdʵֺdf1,f2fkļɥʧ͹ϱԣҲһϷʸܼ⵽ù.ôük-ݴǿУ(k-fault-tolerant reduced SSCk-FT RSSC)üǱ͹ϱյģҶкκq1qk-1Ǳ͹ϱյģ߹Сf1,f2fqɱ⵽.
йز·Ҫ֮Ĺϵͼ3ʾУĸ*żע.

ͼ3Ҫ֮Ĺϵ
5ģ
ģһȡǼɵĻ·ӦеĲԣȡѡõĻģͼеĲ.
1. һǿϱյĻģǿļɵĻ·ǿϱյ.
1. һǿϱյĻģͷǿļɵĻ·Ƿǿϱյ.
11֤ף5ݵؽֱӵõ.ɶ1ɵ.
2. һǿϱյĻģǿУļɵĻ·ǿϱյ.
2. һk-ݴǿϱյĻģk-ݴǿļɵĻ·k-ݴǿϱյ.
֤. ޹£ģǹϱյģǱ.ϷʱӰģ.3ۣ
(1) ĳʼk-1ȫڻģ.k-ݴǿϱյģˣģ鱣ǿϱԣڼ3£ϲʱڣԭʼϷʸڻģ.ģ齫߸Ϸ߸Ƿ.ڼǿģˣӦڻģ·߸Ϸ߸ָʾ.·ǿϱյ.kڻģвʱ޷ȷϱԣΪܲһĺϷʱضϷ.ģеһϾǲɼ.ˣ·k-ݴǿϱյ.
(2) ĳʼk-1ȫڼ.k-ݴǿģˣǿԣڼ3£ϲʱڣɻʸ.߸Ƿ(⵽).ˣ·߸Ϸ߸ָʾ.·ǿϱյ.kڼвʱڷǱ״̬ȷṩ빦.ˣ·k-ݴǿϱյ.
(3) ģͼڲϣǷֱ𶼲k-1(Ƿֱk-1).(1)(2)ķͽۿ֪ʱ·ǿϱյ.·ٲһʱ·ȷǿϱ.·(k+p)-ݴǿϱ(0<p<k).
ۺ֪·(k+p)-ݴǿϱ(0pk).
֤.
3. һk-ݴǿϱյĻģͷk-ݴǿļɵĻ·k-ݴǿϱյ.
֤. ݶ壬k-ݴǿģһСf1f2fj(1jk)ʹü ڲf1f2fjǲɼģ f1f2fjɼʱһǷ룬ʹظϷ.ζŻģһǷ޷⵽.ˣ·k-ݴǿϱյ.
֤.
4. һk-ݴǿϱյĻģk-ݴǿУļɵĻ·k-ݴǿϱյ.
ۿֱɶ2.
·ǵĹϼFFSTFSEF.ѿֻҪF滻ΪFɶ112ɷֱ𵼳ж356ɶ234ɷֱ𵼳ж478.
3. һɾǿϱյĻģ;ǿļɵĻ·Ǿǿϱյ.
5. һɾǿϱյĻģͷǾǿļɵĻ·ǷǾǿϱյ.
6. һɾǿϱյĻģ;ǿУļɵĻ·Ǿǿϱյ.
4. һk-ݴǿϱյĻģk-ݴǿļɵĻ·k-ݴǿϱյ.
7. һk-ݴǿϱյĻģͷk-ݴǿļɵĻ·k-ݴǿϱյ.
8. һk-ݴǿϱյĻģk-ݴǿУļɵĻ·k-ݴǿϱյ.
1лģ(У)ԹɾвͬԵĻ·.
1ģ(У)
·ģ(У)߻
TSCTSCTSCSellersˡCarterˣ3ݡ
TSCTSCCD+STTamirˣ311ݡ
SFSESFSESCD(SVD)Smithˣ7ݡNicolaidis˫ϵͳSCDУ5Nicolaidisȸ֤5
SFSE
SFSE
SSC
JhaCMOS CVSżCMOS DCVS˫SSCУ13,14ݱĸ֤
k-FT PSFSEk-FT PSFSEk-FT PSCD(k-FT PSVD)LoNMOS 3ȡ12-FT PSCDУ12( ؼģͣҿ˲ϵɿ·Ͷ·)ĸ֤
k-FT PSFSEk-FT PSFSEk-FT PSSCWangLalaż3ȡ13-FT PSSCУ9( żģ)ĸ֤
PSCPSCPSCWakerlyˣ9ݡ
RSFSERSFSERSSCĸ֤
RSFSERSFSERSVDĸ֤
k-FT RSFSEk-FT RSFSEk-FT RSVDĸ֤
k-FT RSFSEk-FT RSFSEk-FT RSSCĸ֤
6
ԽԽעڸĹģоУʵּøʵĲõĲ·.овĻϣڲУĲƵһ¸ǿϱաǿ롢ǿУ顢k-ݴǿϱաk-ݴǿk-ݴǿУ飬о˲(¸)֮Ĺϵ֤ûģԹ켸־вͬԵĻ·.ΪⲢ·Ĺԭһоµĵ·ṹʵַṩ˼. 
עõȻѧ(Ŀ69733010)ϺߵѧУʦѧйѧԺ㼼оCADʵҿſ.
߼飺ۣУ196411ڣʿооΪݴ㡢ϵͳCADCATʵʱֲʽϵͳͨϢ.
Ӧ裬У193512оԱʿʦIEEE FellowоΪݴԡɿԵ.
ʩ豦У19373ڣʿʦҪоΪ硢רϵͳ֪ʶȡܵϵͳ.
ߵλۡʩ豦Ϻѧ㼼оϺ200331
Ӧ衡ۡйѧԺ㼼оCADʵҡ100080
ο
1ı. ݴ. : й. 1995
(Hu Mou, Computer Fault Tolerant Techniques (in Chinese). Beijing: China Railway Publishing House, 1995)
2Lala P K. Fault Tolerant and Fault Testable Hardware Design. Englewood Cliffs, N J: Prentice-Hall, 1985
3Rao T R N, Fujiwara E. Error-Control Coding for Computer Systems. Englewood Cliffs, N J: Prentice-Hall, 1989
4Jiang Jianhui, Hu Mou. The extended self-checking properties of alternating-complementary logic systems. In: Proc of International Workshop on Computer-Aided Design, Test, and Evaluation for Dependability. Beijing: International Academic Publishers, 1996. 258263
5Nicolaidis M, Courtois B. Strongly code disjoint checkers. IEEE Trans on Computers, 1988, 37(6): 751756
6Min Y, Li J. Strongly fault secure PLAs and totally self-checking checkers. IEEE Trans on Computers, 1988, 37(7): 863867
7Smith J E, Metze G. Strongly fault secure logic networks. IEEE Trans on Computers, 1978, 27(6): 491499
8Wang J Q, Lala P K. Partially strongly fault secure and partially strongly code disjoint 1-out-of-3 code checker. IEEE Trans on Computers, 1994, 43(10): 12381240
9Wakerly J. Partially self-checking circuits and their use in performing logical operations. IEEE Trans on Computers, 1974, 23(7): 658666
10, ı. ȫ߼CMOS B/T߼·. о뷢չ, 1993, 30(5): 5561
(Jiang Jianhui, Hu Mou. Safe logic elements CMOS B/T logical circuits and their noise margins. Journal of Computer Research and Development (in Chinese), 1993, 30(5): 5561)
11Tamir Y, Sequin C H. Design and application of self-testing comparators implemented with MOS PLA's. IEEE Trans on Computers, 1984, 33(6): 493506
12Lo J C, Thanawastien S. On the design of combinational totally self-checking 1-out-of-3 coed checker. IEEE Trans on Computers, 1990, 39(3): 387393
13Jha N K. Strongly fault-secure and strongly self-checking domino-CMOS implementations of totally self-checking circuits. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, 1990, 9(3): 332336
14Jha N K. Fault detection in CVS parity trees with application to strongly self-checking parity and two-rail checker. IEEE Trans on Computers, 1993, 42(2): 179189
ԭյڣ1998-12-29޸ĸյڣ1999-04-07.
