Design for Hierarchical Two-Pattern Testability of Data Paths
Md. Altaf-Ul-Amin, Satoshi Ohtake and Hideo Fujiwara Nara Institute of Science and Technology, Ikoma, Nara 630-0101, Japan
E-mail: {amin-m, ohtake, fujiwara}@is.aist-nara.ac.jp
Abstract
This paper introduces the concept of hierarchical testability of data paths for delay faults. A definition of hierarchically two-pattern testable (HTPT) data path is developed. Also, a design for testability (DFT) method is presented to augment a data path to an HTPT one. The DFT method incorporates a graph-based analysis of an HTPT data path and makes use of some graph algorithms. The proposed method can provide the similar advantages of the enhanced scan approach at the cost of much lower hardware overhead.
!"#$%&'()*+&,(%#
!"#$%&''()*+ ,!-.+ '(/'+ 0/+ *(1(//&)2+ '#+ 3('(1'+ 3(4&2+ 3(5(1'/+ 0*+ &+ 10)160'7+ !8(+ 09%#)'&*1(+ #5+ 3('(1'0*:+ 3(4&2+ 3(5(1'/+ 8&/+ /#&)(3+ 0*+ )(1(*'+ 2(&)/+'#+ ;((%+ %&1(+ "0'8+ '8(+ )&%03+ 0*1)(&/(+ 0*+ /%((3+ #5+ 0*'(:)&'(3+ 10)160'/7+ <+ /')&0:8'5#)"&)3+ /#46'0#*+ '#+ !-+ '(/'&=040'2+ 0/+ '8(+ (*8&*1(3+ /1&*+ >?@+ >A@7+ B6'+ '80/+ 0*1#)%#)&'(/+ C()2+ 80:8+ &)(&+ #C()8(&3+ &*3+ '(/'+ &%%401&'0#*+ '09(7+ D*+ '8(+
%)(/(*'+ "#);E+ "(+ 0*')#361(+ 80()&)1801&4+ !-+ '(/'&=040'2+ #5+ 3&'&+
%&'8/7+F0()&)1801&4+'(/'&=040'2+'&):('0*:+/'61;$&'+5&64'/+8&/+=((*+ (G%4#)(3+ 0*+ &+ *69=()+ #5+ )(/(&)18+ "#);/+ >H@+ >I@7+ !8(/(+ "#);/+
&33)(//+ '(/'&=040'2+ &'+ )(:0/'()+ ')&*/5()+ 4(C(4+ ,J!K.+ &*3+ '86/+ (G%4#0'+ '8(+ &3C&*'&:(/+ #5+ 80:8()$4(C(4+ 3(/0:*+ 80()&)182+ "8()(+ '8(+ *69=()+ #5+ %)090'0C(+ (4(9(*'/+ 0*+ '8(+ 3(/0:*+ 0/+ :)(&'42+ )(361(37+D*+'8(/(+"#);/+0'+0/+/8#"*+'8&'+80()&)1801&4+'(/'&=040'2+ 0/+=(''()+'8&*+:&'($4(C(4+=&/(3+5644$/1&*+9('8#3+ 0*+'8(+1#*'(G'+
#5+ '(/'+ :(*()&'0#*+ '09(E+ '(/'+ &%%401&'0#*+ '09(+ &*3+ /#9('09(/+ (C(*+&)(&+#C()8(&37+L6)+&%%)#&18+0/+80()&)1801&4+'(/'&=040'2+5#)+ 3(4&2+5&64'/7+!8(+3(/0:*+80()&)182+"(+1#*/03()+0/+J!K7+<'+J!K+
&+10)160'+1&*+=(+30C03(3+0*'#+'"#+%&)'/M+<+1#*')#44()+&*3+&+3&'&+
%&'87+D*0'0&442+"(+1#*/03()+'8(+3&'&+%&'8+#*427+N(+&//69(+'8&'+
&44+1#*')#4+0*%6'/+&*3+/'&'6/+#6'%6'/+#5+&+3&'&+%&'8+&)(+30)(1'42+ 1#*')#44&=4(+&*3+30)(1'42+#=/()C&=4(+)(/%(1'0C(427++
!8()(+ &)(+ &+ *69=()+ #5+ 3(4&2+ 5&64'+ 9#3(4/7+ <9#*:+ '8(/(E+ '8(+ %&'8+ 3(4&2+ 5&64'+ 9#3(4+ 0/+ 9#)(+ :(*()&4+ &*3+ 1&*+#C()1#9(+ '8(+4090'&'0#*/+ #5+#'8()+ 9#3(4/7+N(+ 3(C(4#%+F!-!+ 3&'&+%&'8+ '&):('0*:+ &44+ 3('(1'&=4(+ %&'8+ 3(4&2+ 5&64'/7+ F#"(C()E+ 0*+ '8(+
%)(/(*'+ "#);E+ "(+ 3#+ *#'+ 1#*/03()+ %&'8/+ 0*C#4C0*:+ 1#*')#4+ 0*%6'/+ #)+ /'&'6/+ #6'%6'/7+ !8(+ &3C&*'&:(/+ #5+ &*+ F!-!+ 3&'&+
%&'8+ &)(+ ,0.+ '8(+ 3&'&+ %&'8+ 1&*+ =(+ '(/'(3+ 6/0*:+ &*2+ 3(4&2+ 5&64'+ 9#3(4E+ ,00.+ 1#9=0*&'0#*&4+ <!-O+ 1&*+ =(+ 6/(3+ &*3+ ,000.+ /&9(+ 5&64'+ 1#C()&:(+ 1&*+ =(+ #='&0*(3+ &/+ 0*+ '8(+ (*8&*1(3+ /1&*+
&%%)#&187+
<*&42P0*:+ '8(+ 56*1'0#*&40'2+ #5+ &+ 10)160'E+ /#9(+ %&'8/+ 0*+ '8(+ 3&'&+%&'8+90:8'+=(+%)#C(*+'#+=(+964'0%4(+14#1;+'#4()&*'+%&'8/7+ Q(4&2+ 0*+ &+ 964'0%4(+ 14#1;+ '#4()&*'+ %&'8+ 0/+ 9#/'+ 40;(42+ '#+ =(+ 1&6:8'+=2+'(/'+5#)+')&*/0'0#*+5&64'/+&*3+*((3+*#'+'#+=(+'&):('(3+ 5#)+3(4&2+'(/'0*:+>R@7+D*+'80/+%&%()+"(+3(C(4#%(3+#6)+&%%)#&18+
&//690*:+ '8&'+ &44+ %&'8/+ #5+ 6*0'2+ /(S6(*'0&4+ 3(%'8+ &)(+ /0*:4(+
14#1;+'#4()&*'7+F#"(C()E+05+/#9(+964'0%4(+14#1;+'#4()&*'+%&'8/+ (G0/'+&*3+&)(+30/1&)3(3+5)#9+'8(+'&):('+5&64'+40/'E+#6)+&4:#)0'89+ 0/+/'044+&%%401&=4(+&*3+9&2+)(/64'+0*+4(//+8&)3"&)(+#C()8(&37++ -"# ./0#+(%+01&#(2#3.4#15&/6#
<+ 3&'&+ %&'8+ 1#*/0/'/+ #5+ 8&)3"&)(+ (4(9(*'/+ 1#**(1'(3+ =2+
"0)(/7+N(+&//69(+'8&'+'8(+"0)(/+0*+&+3&'&+%&'8+&)(+#5+/&9(+=0'+
"03'87+!8(+J!K+%&'8/+&)(+'8(+%&'8/+0*+&*+J!K+10)160'+#5+&+3&'&+
%&'8+'8&'E+,0.+/'&)'+&'+&+%)09&)2+0*%6'+&*3+(*3+&'+&+)(:0/'()+#)+,00.+ /'&)'+ &'+ &+ )(:0/'()+ &*3+ (*3+ &'+ &*#'8()T/&9(+ ,0*+ 1&/(+ #5+ 5((3=&1;.+)(:0/'()+#)+,000.+/'&)'+&'+&+)(:0/'()+&*3+(*3+&'+&+%)09&)2+
#6'%6'+ #)+ ,0C.+ /'&)'+ &'+ &+ %)09&)2+ 0*%6'+ &*3+ (*3+ &'+ &+ %)09&)2+
#6'%6'7+D'+0/+#=C0#6/+'8&'+'8(+/(S6(*'0&4+3(%'8+#5+&*+J!K+%&'8+ 0/+#*(7+U-D?$J?V+&*3+UJ?$<QQ$WXYZ$JIV+&)(+'"#+(G&9%4(/+
#5+J!K+%&'8/+0*+'8(+&)=0')&)2+&*3+/09%4(+3&'&+%&'8+#5+[0:6)(+?7+
!8(+)(&3()+9&2+C()052+'8&'+'8(+3&'&+%&'8+#5+ [0:6)(+?+ 8&/+'#'&4+ (0:8'((*+J!K+%&'8/7+
D*+ '8(+ 4#"()+ 80()&)182E+ (&18+ J!K+ %&'8+ 1#*/0/'/+ #5+ &+
*69=()+#5+?$=0'+"03(+%&'8/7+!8(/(+0*30C036&4+?$=0'+"03(+%&'8/+ 9&2+=(+14&//050(3+&/+)#=6/'E+*#*$)#=6/'E+56*1'0#*&4+/(*/0'0P&=4(+
&*3+ 56*1'0#*&4+ 6*/(*/0'0P&=4(+ %&'8/7+
!#+ :6&)&*'((+ '8(+ '090*:+%()5#)9&*1(E+0'+ 0/+*(1(//&)2+'#+'(/'+'8(+ )#=6/'E+ *#*$)#=6/'+
&*3+ 56*1'0#*&4+ /(*/0'0P&=4(+,[\.+%&'8/+
>Z@7+ !#+ '(/'+ &+ )#=6/'+
%&'8E+ 0'+ 0/+ %#//0=4(+ '#+ 50*3+ '"#+ C(1'#)/+ ,&+ C(1'#)+%&0).+'8&'+3055()+ 5)#9+ (&18+ #'8()+ #*42+
&'+/0*:4(+=0'+>]@7+<*+[\+
%&'8+ *((3/+ '#+ =(+ '(/'(3+ 0*+ &+ :)#6%+ /0964'&*(#6/42+ "0'8+
#*(+ #)+ 9#)(+ #'8()+ [\+ %&'8/7+ F(*1(+ '8(+ '(/'0*:+ #5+ &+ :)#6%+ #5+ [\+ %&'8/+ )(S60)(/+ '"#+ C(1'#)/E+ "8018+ 9&2+ 3055()+ 5)#9+ (&18+
#'8()+&'+964'0%4(+=0'/+>Z@7+[)#9+*#"+#*+'8(+'(/'0*:+#5+&*+J!K+
%&'8+"044+9(&*+'8(+'(/'0*:+#5+)#=6/'E+*#*$)#=6/'+&*3+56*1'0#*&4+ /(*/0'0P&=4(+%&'8/+0*+0'7+
-&'8+ 3(4&2+ 5&64'+ '(/'0*:+ )(S60)(/+ 4&6*180*:+ &+ ')&*/0'0#*+ &'+ '8(+/'&)'0*:+#5+&+%&'8+=2+&%%420*:+&+%&0)+#5+C(1'#)/E+%)#%&:&'0*:+ '8(+ ')&*/0'0#*+ &4#*:+ '8(+ %&'8+ &*3+ &44#"0*:+ 5&64'+ (55(1'+
#=/()C&'0#*+ 5)#9+ '8(+ (*3+ #5+ '8(+ %&'8+ >Z@7+ F#"(C()E+ 9&*2+ #5+ '8(+J!K+%&'8/+0*+'8(+3&'&+%&'8+*(0'8()+/'&)'+&'+&+-D+*#)+(*3+&'+&+ -L7+!8()(5#)(E+/#9(+%&'8/+&)(+*(1(//&)2+'#+(*/6)(+'8(+54#"+#5+ '(/'+ 3&'&+ ,'(/'+ C(1'#)/+ &*3+ '(/'+ )(/%#*/(/.+ 5)#9+ -D/+ '#+
ADD
MUX1
MUX2 R1
MUX3 R2
R3
MUX4
MULT MUX5
MUX6 R4
One One
R5
PO1 PO2
PI1 PI2
Figure 1: An arbitrary data path
IEEE the 10th Asian Test Symposium (ATS 2001), pp. 11-16, Nov. 2001.
&%%)#%)0&'(+ )(:0/'()/+ &*3+ 5)#9+ &%%)#%)0&'(+ )(:0/'()/+ '#+ -L/7+ -&'8/+ 6/(3+ 5#)+ '8(+ 54#"+ #5+ '(/'+ C(1'#)/+ "044+ =(+ )(5())(3+ '#+ &/+
!"#$%"&' ()$*++ &*3+ %&'8/+ 6/(3+ 5#)+ '8&'+ #5+ '(/'+ )(/%#*/(/+ "044+ =(+ )(5())(3+ '#+ &/+ ",+-%.)$/"#' ()$*+7+ <*2+ 4#:01+ C&46(+ 1&*+ =(+
%)#%&:&'(3+&4#*:+'8(+1#*')#4+%&'8/+&*3+'8(+#=/()C&'0#*+%&'8/7+
<*+J!K+%&'8+9&2+1)#//+#*(+#)+9#)(+964'0%4(G()/+,WXY/.+&*3+
#%()&'0#*&4+9#364(/7+D5+ &*+ 0*%6'+ #5+&+WXY+ #)+&*+ #%()&'0#*&4+ 9#364(+0/+#*+&*+J!K+%&'8+'8(*+'80/+0*%6'+0/+&*+"#0/#(1$+#5+'8(+
%&'87+L'8()+0*%6'T0*%6'/E+"8018+&)(+*#'+#*+'8(+%&'8E+&)(+1&44(3+
"220/#(1$+7+
-"!# 75&/6#&/'(*8/#5#9:;#
D*+&+3&'&+%&'8E+WXY/+&)(+C()2+1#99#*+(4(9(*'/+&*3+&)(+ 6/(3+&/+0*'()1#**(1'0*:+6*0'/7+K('+6/+1#*/03()+&+A+'#+?+WXY+&/+ /8#"*+ 0*+ [0:6)(+ A7+ B#'8+ <+ &*3+ B+ &)(+ *$=0'+ "03(7+ ^+ 0/+ '8(+ 1#*')#4+ 0*%6'7+ D5+ ^+ /(4(1'/+ <+ '8(*E+ ,0.+ %)#%&:&'0#*+ #5+ /0:*&4/+ 5)#9+ <,< E__< .+ '#+ L,L E__7L .+ 0/+ )#=6/'+ ,#55$0*%6'/+ )(9&0*+/'&=4(+&'+*#*$1#*')#440*:+C&46(.+&*3+0*3(%(*3(*'+#5+'8(+ /0:*&4/+&'+B+&*3+,00.+'8()(+0/+*#+9():0*:+:&'(+&9#*:+'8(+%&'8/+ ,< + '#+ L .E+ ,< + '#+ L .E__77,< + '#+ L .+ 07(7+ '8()(+ &)(+ #*42+ *+ 96'6&442+ 0*3(%(*3(*'+ ,?$=0'+"03(.+%&'8/+5)#9+
<+ '#+ L7+ \0904&)+ 0/+ '8(+ 1&/(+ 5#)+ '8(+ %&'8+ 5)#9+ B+ '#+ L7+ !8()(5#)(E+
"804(+ '(/'0*:+ &*2+ J!K+
%&'8+ 1)#//0*:+ #*(+ #)+ 9#)(+ WXY/+ '8(+ /(4(1'+ 0*%6'T0*%6'/+ /8#643+
/(4(1'+ '8(+ #*$
0*%6'T0*%6'/+ #5+ '8(+ WXYTWXY/+ &*3+ '8(+ #55$0*%6'T0*%6'/+ #5+ '8(+ WXYTWXY/+ 1&*+ =(+ 3#*`'+ 1&)(7+ [#)+ (G&9%4(E+ '#+ '(/'+ '8(+ %&'8+ a-DA$W6G?$ JAa+ ,[0:6)(+ ?.E+ !-+ C(1'#)/+ /8#643+ =(+ &%%40(3+ &'+ 345+ &*3+ '(/'+ )(/%#*/(/+ /8#643+ =(+ 1&%'6)(3+ &'+ 657+ !8(+ #55$0*%6'+ #5+ 7895+ 9&2+=(+3#*b'+1&)(7+
-"-# 75&/6#&/'(*8/#5%#(10'5&,(%5<#=()*<0#
W&*2+J!K+%&'8/+1)#//+*#'+#*42+WXY/+=6'+&4/#+#%()&'0#*&4+ 9#364(/7+ D*+ '8(+ 5#44#"0*:+ (G&9%4(E+ "(+ &)(+ 30/16//0*:+ /618+ &+
%&'87+
!"#$%&'( )*+ !8(+ %&'8+ aJ?$WXYH$WXYR$WXK!$JRa+ 0*+ [0:6)(+?+1)#//(/+'8(+#%()&'0#*&4+9#364(+78:;7+!8(+/(:9(*'+ aJ?$WXYH$WXYR$a+#5+'80/+%&'8+0/+40;(+&+"0)(+0*+&+/(*/(+'8&'+ '8(+/0:*&4+C&46(/+&'+6<+&%%(&)+6*18&*:(3+&'+'8(+#6'%6'+#5+'8(' 789=+05+'8(+1#*')#4+0*%6'/+#5+'8(+WXY/+/(4(1'+'8(+#*$0*%6'/7+
<:&0*+ '8(+ /(:9(*'+ a$JRa+ #*+ '8(+ #6'%6'+ /03(+ #5+ 78:;+ 0/+
#=C0#6/42+40;(+&+"0)(7+!8(+1#)(+/(:9(*'+#5+'80/+%&'8+0/+'8(+%&)'+
#5+ '8(+ %&'8+ 0*/03(+ '8(' 78:;7+ D*+ #'8()+ "#)3/+ '8(+ '(/'+ C(1'#)+ /('+)(S60)(3+'#+'(/'+'8(+%&)'+#5+'8(+%&'8+0*/03(+'8(+78:;+0/+'8(+ /&9(+ &/+ '#+ '(/'+ '8(+ "8#4(+ %&'8+ aJ?$WXYH$WXYR$WXK!$ JRa7+ !8(/(+ '(/'+ C(1'#)/+ 1&*+ =(+ :(*()&'(3+ =2+ /(%&)&'(42+ 1#*/03()0*:+ '8(+ :&'(+ 4(C(4+ 10)160'+ /')61'6)(+ #5+ '8(+ 78:;7+ L=C0#6/42+'8(+=0'+"03'8+#5+'8(/(+'(/'+C(1'#)/+/%&*/+=#'8+0*%6'/+
#5+'8('78:;7+\6%%#/(E+=0'/+#5+'8(+'(/'+C(1'#)/+'#+=(+&%%40(3+'#+ '8(+ #55$0*%6'+ #5+ '8(+ 78:;+ &)(+ *#'+ &44+ 3#*b'+ 1&)(/7+ F(*1(+ '#+ '(/'+ '8(+ %&'8+ aJ?$WXYH$WXYR$WXK!$JRaE+ '(/'+ C(1'#)/+ /8#643+ =(+ &%%40(3+ *#'+ #*42+ &'+ 6<+ =6'+ &4/#+ &'+ '8(+ #55$0*%6'+ #5+
'8(+78:;7+!(/'+C(1'#)/+1&*+=(+&%%40(3+&'+'8(+#55$0*%6'+#5+'8(+ 78:;'5)#9+)(:0/'()+657+!8()(5#)(E+"(+/&2+'8&'+'8(+J!K+%&'8+ a+ J?$WXYH$WXYR$WXK!$JRa+ 0/+ &*+ F!-!+ %&'8+ 05E+ ,0.+ '8()(+ (G0/'+ '"#+ 1#*')#4+ %&'8/+ 5)#9+ %)09&)2+ 0*%6'T0*%6'/+ '#+ J?+ &*3+ JA+ '8&'+ /6%%#)'+ '8(+ &%%401&'0#*+ #5+ !-+ C(1'#)/+ &*3+ ,00.+ '8()(+ (G0/'/+ &*+ #=/()C&'0#*+ %&'8+ '#+ %)#%&:&'(+ '8(+ '(/'+ )(/%#*/(/+ 5)#9+JR+'#+&+%)09&)2+#6'%6'7+
D*+[0:6)(+?E+"(+1&*+/((+'8&'+30/c#0*'+1#*')#4+%&'8/+a-D?$J?a+
&*3+ a-DA$WXY?$JAa+ &)(+ /655010(*'+ '#+ &%%42+ !-+ C(1'#)/+ &*3+ '8(+ '(/'+ )(/%#*/(+ 1&*+ =(+ #=/()C(3+ 6/0*:+ '8(+ #=/()C&'0#*+ %&'8+ UJR$-LAV7+D'+0/+*#'01(&=4(+ '8&'+'8(/(+1#*')#4+&*3+ #=/()C&'0#*+
%&'8/+1&*+&4/#+'(/'+'8(+J!K+%&'8+aJA$WXK!$JRa7+!"#+1#*')#4+
%&'8/+ *#'+ *(1(//&)042+ /8#643+ =(+ 30/c#0*'+ '#+ /6%%#)'+ '8(+
&%%401&'0#*+ #5+ !-+ '(/'7+ N(+ "044+ 9(*'0#*+ 0*+ \(1'0#*+ H7?+ '8(+
*(1(//&)2+ &*3+ /655010(*'+ 1#*30'0#*/+ 5#)+ '"#+ 1#*')#4+ %&'8/+ '#+ /6%%#)'+'8(+&%%401&'0#*+#5+!-+'(/'7++
>"# ./0#?.7.#@5&5#75&/#
D*+ '80/+ /(1'0#*+ "(+ 3(50*(+ '8(+ F!-!+ 3&'&+ %&'8+ &*3+ :0C(+ /#9(+ #'8()+ 3(50*0'0#*/7+ D*+ '8(+ 5#44#"0*:+ /6=+ /(1'0#*/+ "(+
%)(/(*'+&*+&*&42/0/+#*+F!-!+3&'&+%&'8/7+
+,-,.,/,0.()*(!8(+1'23''(0-(#.(456(%#/7+0/+*E+05+0'+1)#//(/+&*+
*$0*%6'+#%()&'0#*&4+9#364(7+
[#)+ (G&9%4(E+ '8(+ %&'8+ aJ?$WXYH$WXYR$WXK!$JRa+ #5+
>?)@(&-'<+0/+&*+J!K+%&'8+#5+3(:)((+A7+!8()(+90:8'+=(+%&'8/+0*+
&+ 3&'&+ %&'8+ '8&'+ 1)#//(/+ *#+ #%()&'0#*&4+ 9#364(7+ D*+ [0:6)(+ ?E+ '8(+ %&'8+ U-DA$WXY?$JAV+ 1)#//(/+ #*42+ &+ WXY+ &*3+ '8(+ %&'8+ U-D?$J?V+ 0/+ /09%42+ &+ "0)(7+ !8(/(+ %&'8/+ &)(+ /%(10&4+ '2%(/+ #5+ J!K+%&'8/+#5+3(:)((+?7+!8(+3(:)((+#5+&*+J!K+%&'8+09%40(/+'8(+
*69=()+ #5+ 1#*')#4+ %&'8/+ '8&'+ &)(+ /655010(*'+ '#+ (*/6)(+ 0'/+ 80()&)1801&4+!-+'(/'&=040'27+
+'-,.,/,0.( 8M+ <*+ J!K+ %&'8+ #5+ 3(:)((+ *E+ "8018+ 1)#//(/+ &*+ *$ 0*%6'+ #%()&'0#*&4+ 9#364(+ /&2+ W+ 0/+ &*+ 95:5( %#/7+ 05+ '8()(+ (G0/'+ *+ 1#*')#4+ %&'8/+ ^ E+ ^ _^ + &*3+ &*+ #=/()C&'0#*+ %&'8+ - + /618+'8&'E+,0.+^ +0/+5)#9+&+%)09&)2+0*%6'+'#+'8(+/'&)'0*:+)(:0/'()+
#5+'8(+ %&'8+,0*+1&/(+ 0'+/'&)'/+ &'+&+ -DE+^ +0/+&*+ (9%'2+ %&'8.+&*3+ ,00.+ ^ _7^ + 0/+ 5)#9+ %)09&)2+ 0*%6'T0*%6'/+ '#+ &+ )(:0/'()+ T+ )(:0/'()/+ "8018+ &)(+ (0'8()+ 30)(1'42+ #)+ '8)#6:8+ 964'0%4(G()T+ 964'0%4(G()/+ 1#**(1'(3+ '#+ '8(+ *$?+ #55$0*%6'T0*%6'/+ #5+ W+ ,D*+ 1&/(+&*+#55$0*%6'+#5+W+0/+1#**(1'(3+'#+&+-DE+'8(+1#))(/%#*30*:+ 1#*')#4+%&'8+0/+&*+(9%'2+%&'8.+&*3+,000.+^ E+^ _^ +/6%%#)'+'8(+
&%%401&'0#*+#5+!-+'(/'+&*3+,0C.+- +0/+5)#9+'8(+(*30*:+)(:0/'()+#5+ '8(+%&'8+'#+&+%)09&)2+#6'%6'+,0*+1&/(+'8(+%&'8+(*3/+&'+&+%)09&)2+
#6'%6'E+- +0/+&*+(9%'2+%&'8.7+
+'-,.,/,0.( ;*+ !8(+ /('+ #5+ 1#*')#4+ %&'8/+ &*3+ &*+ #=/()C&'0#*+
%&'8+'8&'+&)(+/655010(*'+'#+(*/6)(+'8(+80()&)1801&4+!-+'(/'&=040'2+
#5+&*+J!K+%&'8+0/+)(5())(3+'#+&/+'8(+/'</(%&#.+#5+'8(+%&'87+ +'-,.,/,0.(=M+<*+J!K+3&'&+%&'8+0/+&*+95:5(1#/#(%#/7+05+&44+ 0'/+J!K+%&'8/+&)(+F!-!+%&'8/7+
>"!# A(%),&,(%6#2('#+(%&'(<#15&/6#&(#6*11('&#.7#&06&# F()(E+ "(+ 50)/'+ =)0(542+ 30/16//+ '8(+ $*%1' 56*1'0#*+ >H@7+ !8(+ $*%1+ 56*1'0#*+&44#"/+'8(+%)#%&:&'0#*+#5+&+4#:01+C&46(+5)#9+&*+0*%6'+ '#+ '8(+ #6'%6'+ #5+ &*+ #%()&'0#*&4+ 9#364(+ "0'8#6'+ &*2+ 18&*:(7+ [#)+ 1#99#*+ '"#$0*%6'+ #%()&'0#*&4+ 9#364(/+ ,(7:7+ &33()E+ 964'0%40()+('17.E+&+$*%1+56*1'0#*+5)#9+&*+0*%6'+'#+'8(+#6'%6'+1&*+
=(+ )(&40P(3+ =2+ %)#C030*:+ &+ 1#*/'&*'+ &'+ '8(+ #'8()+ 0*%6'7+ !8(+
*(1(//&)2+ 1#*/'&*'+ 1&*+ =(+ %)#C03(3+ (0'8()+ =2+ 9(&*/+ #5+ &+ /6%%#)'+ %&'8+ #)+ =2+ &330*:+ &+ 9&/;7+ [#)+ #'8()+ 9#364(/+ $*%1+ 56*1'0#*/+ 1&*+ =(+ )(&40P(3+ =2+ 9(&*/+ #5+ &+ WXY7+ D*0'0&442E+ "(+
A1
B1
An
Bn
O1
O2
C
Figure 2: n-bit wide 2 to 1 MUX
&//69(+'8&'+&+$*%1+56*1'0#*+(G0/'/+5)#9+&*2+0*%6'+'#+'8(+#6'%6'+
#5+ &*2+ #%()&'0#*&4+ 9#364(7+ X*3()+ '80/+ &//69%'0#*+ &+ 1#*')#4+
%&'8+ 1&*+ =(+ )(%)(/(*'(3+ =2+ 40*(/+ &*3+ '8(+ )(:0/'()/+ 0'+ 1)#//(/7+ F#"(C()E+ /618+ &*+ &//69%'0#*+ 0/+ *#'+ *(1(//&)2+ 5#)+ &*+ F!-!+ 3&'&+%&'8+&*3+"044+=(+)(4&G(3+4&'()+#*7++
57'(2'.'3#&(>0.1,/,0.*(K('+^ E+^ _7+^ +&)(+*+1#*')#4+%&'8/+ /'&)'0*:+ &'+ %)09&)2+ 0*%6'T0*%6'/+ &*3+ (*30*:+ &'+ *+ 3055()(*'+
%#0*'/+ d- E+d- E__d- + ,!8(/(+(*30*:+ %#0*'/+9&2+=(+(0'8()+ )(:0/'()/+ #)+ %)09&)2+ 0*%6'/.7+ K('E+ &+ C(1'#)+ %&0)+ ,C E+ C .+ /%&*/+
#C()+ *+ 1#*')#4+ %&'8/7+ F(*1(E+ C #)+ C + 1&*+ =(+ 30C03(3+ 0*'#+ *+
%&)'0&4+ C(1'#)/E+ (&18+ #5+ "8018+ 0/+ &//#10&'(3+ '#+ &+ 1#*')#4+ %&'87+ B&/(3+ #*+'80/E+ "(+)(%)(/(*'+ C +&*3+C &/+ C eC fC f__C +
&*3+ C + e+ C fC f__77C + ,'8(+ /29=#4+ bfb+ 9()(42+ 40*;/+ '8(+
%&)'0&4+ C(1'#)/.7+ B0'$"03'8+ #5+ (&18+ #5+ + C E+ C E__C E+ C E+ C E__77C +0/+(S6&4+'#+'8(+=0'$"03'8+#5+'8(+3&'&+%&'87+K('E+C E+ C E__C E+ C E+ C E__77C + 1&*+ =(+ 5(3+ 5)#9+ %)09&)2+ 0*%6'T0*%6'/+&11#)30*:+'#+&+/18(364(+/618+'8&'+C E+C E__C + /0964'&*(#6/42+ &%%(&)/+ &'+ d- E+ d- E__d- + &*3+ 0*+ '8(+ *(G'+ 14#1;+ 1214(+ C E+ C E__77C + /0964'&*(#6/42+ &%%(&)+ &'+ d- E+ d- E__d- + '8(*+ "(+ /&2+ '8&'+ ^ E+ ^ _7+ ^ + /6%%#)'+ '8(+
&%%401&'0#*+#5+!-+'(/'7+
!8(+ /(S6(*'0&4+ 3(%'8+ #5+ &+ 1#*')#4+ %&'8+ 0/+ '8(+ *69=()+ #5+ )(:0/'()/+'8&'+&%%(&)+#*+'8(+%&'87+!#+9(&*+'8(+/(S6(*'0&4+3(%'8+
#5+&*2+1#*')#4+%&'8+/&2E+^ +"(+6/(+'8(+*#'&'0#*+\Q,^ .7+D*+'8(+ 5#44#"0*:+ '8(#)(9+ "(+ 9(*'0#*+ *(1(//&)2+ &*3+ /655010(*'+ 1#*30'0#*/+5#)+'"#+1#*')#4+%&'8/+'#+/6%%#)'+!-+'(/'7++
57'03'$( )M+ !"#+ 1#*')#4+ %&'8/+ ^ + &*3+ ^ + 5)#9+ %)09&)2+ 0*%6'T0*%6'/+'#+'"#+3055()(*'+%#0*'/+d- +&*3+d- +/6%%#)'+'8(+
&%%401&'0#*+ #5+ !-+ '(/'+ 05+ &*3+ #*42+ 05+ #*(+ #5+ '8(+ 5#44#"0*:+ 1#*30'0#*/+0/+/&'0/50(37+
A"#B/$/"#'<M+^ ∩^ +e+φ+07(7+^ +&*3+^ +&)(+30/c#0*'++
+A"#B/$/"#' 5M+ g\Q,^ ′.+ h+ \Q,^ ′.g≥+ + A+ E+ "8()(+ ^ ′+ &*3+ ^ ′+ &)(+ 30/c#0*'+ %&)'/+ #5+ ^ + &*3+ ^ + 5)#9+ d- + &*3+ d- + )(/%(1'0C(42+ '#+ '8(+*(&)(/'+9():0*:+%#0*'+#5+^ +&*3+^ 7++
A"#B/$/"#'CM+d0'8()+^ ′#)+^ ′+1)#//(/+&'+4(&/'+'"#+8#43+)(:0/'()/7++ A"#B/$/"#' DM+ N8(*+ g\Q,^ ′.+ h+ \Q,^ ′.g+ e?E+ '8(+ 30/c#0*'+ %&)'+ ,07(7+ #*(+ #5+ ^ ′#)+ ^ ′.+ "0'8+ 4#"()+ /(S6(*'0&4+ 3(%'8+ 1)#//(/+ &+ 8#43+)(:0/'()7+
!8(+ %)##5+ #5+ '80/+ '8(#)(9+ 0/+ (G%4&0*(3+ 0*+ >i@7+ [0:6)(+ H+ '2%01&442+ 3(%01'/+ '8(+
1#*30'0#*/+ #5+
;*-"%-@'<7+D*+[0:6)(+ H+ '8(+ )(:0/'()/+ "0'8+ 3#6=4(+ =#)3()40*(+
&)(+ 8#43+ )(:0/'()/7+ N(+ 9(*'0#*(3+ 0*+
>i@+ /#9(+ /655010(*'+ 1#*30'0#*/+ 5#)+ &*2+
*69=()+ #5+ 1#*')#4+
%&'8/+'#+/6%%#)'+!-+ '(/'7++
F()(E+ #*(+ '80*:+ 0/+ *#'("#)'827+ K('+
&*+J!K+%&'8+-+/'&)'+
&'+ &+ )(:0/'()+ J+ &*3+
1)#//(/+ &*+
#%()&'0#*&4+ 9#364(+ W7+ [#)+ -+ '#+ =(+ &*+ F!-!+ %&'8E+ &+ 1#*')#4+%&'8+5)#9+&+
-D+ '#+ J+ 0/+ *(1(//&)27+ j#"E+ 05+ J+ 0/+ &+ 5((3=&1;+ )(:0/'()+ ,[J.+ '#+ WE+ '8(+ 1#*')#4+ %&'8+ 96/'+ *#'+ 0*1#)%#)&'(+ &+ $*%1+ '#+ W7+ D*+ [0:6)(+?E+6C+0/+&*+[J+'#+EFF7+L*42+#*(+1#*')#4+%&'8+5)#9+&+ -D+ '#+ 6C+ 0/+ U-D?$J?$<QQ$WXYA$JHV7+ j#"+ '#+ '(/'+ '8(+ %&'8+ UJH$WXYI$<QQ$WXYZ$JIVE+ '80/+ 1#*')#4+ %&'8+ 1&**#'+ =(+ 6/(37+B(1&6/(E+'8(+50)/'+C(1'#)+#5+&+C(1'#)+%&0)+0/+4#&3(3+&'+6C' '#+/(''4(+'8(+/0:*&4+40*(/+'8)#6:8#6'+'8(+%&'8+0*14630*:+'8(+%&)'+
#5+ '8(+ %&'8+ 0*+ EFF7+ + D*+ '8(+ *(G'+ 14#1;E+ '8(+ /(1#*3+ C(1'#)+ 0/+ 4#&3(3+ &'+ 6C' '#+ 4&6*18+ '8(+ 3(/0)(3+ ')&*/0'0#*7+ F#"(C()E+ '8(+ 50)/'+ C(1'#)+ 1&**#'+ 3#+ 0'/+ c#=+ 05+ '8(+ /(1#*3+ C(1'#)+ %)#%&:&'(/+ 6/0*:+ &+ $*%1+ '#+ EFF7+ !8()(5#)(+ "(+ /8#643+ &4"&2/+ 1&)(56442+ (G1463(+/618+1#*')#4+%&'8/7++
>"-# B'51/#C560)#5%5<D6,6#(2#?.7.#)5&5#15&/6#
<44+J!K+%&'8/+'8&'+1)#//+&*+#%()&'0#*&4+9#364(+8&C0*:+'"#+
#)+ 9#)(+ 0*%6'/+ 1&*+ =(+ )(%)(/(*'(3+ &/+ &+ :)&%87+ N(+ 1&44+ 0'+ +$%1!$1%)&' !"##-!$/./$G' H%)(*+ ,\^O.+ #5+ '8(+ 9#364(7+ !8(+ *#3(/+ #5+ '8(+\^O+1#*/0/'+#5+'8(+9#364(+&*3+'8(+)(:0/'()/E+-D/+&*3+-L/+ '8&'+ &)(+ &'+ '8(+ /'&)'0*:+ &*3+ &'+ '8(+ (*30*:+ #5+ '8(+ J!K+ %&'8/+ '8)#6:8+ '8(+ 9#364(7+ !8(+ (3:(/+ #5+ '8(+ \^O+ )(%)(/(*'+ '8(+ 1#**(1'0#*/+#5+'8(+9#364(+"0'8+'8(+#'8()+*#3(/7+K('+'8(+/('+#5+
*#3(/+ 1#**(1'(3+ '#+ (&18+ #5+ '8(+ 0*%6'/+ #5+ &*+ *$0*%6'+ 9#364(+
&)(+ J E+ J J &*3+ '8(+ /('+ #5+ *#3(/+ 1#**(1'(3+ '#+ '8(+
#6'%6'+ #5+ '8(+ 9#364(+ 0/+ J 7+ K('+ J + e+ k) E) E) _77lE+ J + e+ k) E+ ) E) _7lE__7+ J + ek) E+ ) E) _77l+ + &*3+ J ek) E+ ) E+ ) _7l7+ [)#9+ '8(+ \^O+ #5+ &*+ *$0*%6'+ 9#364(+ &+ *m?$%&)'0'(+ :)&%8+ 1&*+ =(+ :(*()&'(37+ N(+ 1&44+ 0'+ %-H/+$-%' !"@()$/,/&/$G' H%)(*+ ,J^O.+#5+'8(+9#364(7+J E+J J +&*3+J +&)(+'8(+*m?+/('+
#5+*#3(/7+!8(+(3:(/+#5+'8(+J^O+&)(+3('()90*(3+=&/(3+#*+'8(+ 5#44#"0*:+)64(/7+
4?&')M+D5+'8()(+(G0/'+*+1#*')#4+%&'8/+^ E+^ _77^ +5)#9+%)09&)2+ 0*%6'T0*%6'/+'#+&*2+*#3(+) ∈+J E+) ∈J ___77) ∈J E+'8&'+ /6%%#)'+ '8(+ &%%401&'0#*+ #5+ !-+ '(/'E+ '8()(+ (G0/'+ (3:(/+ =('"((*+
&*2+'"#+*#3(/+#5+) E+) E+__&*3+) 7+
4?&'8M+ D5+ '8()(+ (G0/'+ &*+ #=/()C&'0#*+ %&'8+ 5)#9+ &*2+ *#3(+ ) ∈+ J + '#+ &+ %)09&)2+ #6'%6'E+ '8()(+ (G0/'+ (3:(/+ =('"((*+ ) + '#+ &*2+
*#3(+0*+J &*3+J &*3 J 7++
!"#$%&'( 8*+ !8(+ \^O+ #5+ 78:;+ #5+ [0:6)(+ ?+ 0/+ /8#"*+ 0*+ [0:6)(+I,&.7+J^O+#5+78:;+0/+/8#"*+0*+[0:6)(+I,=.+6*3()+'8(+
&//69%'0#*+ '8&'+ '8)#6:8+ 56*1'0#*+ (G0/'/+ 5)#9+ &*2+
0*%6'+ '#+ '8(+
#6'%6'+ #5+ &*2+
#%()&'0#*&4+ 9#364(7+ !&=4(+ ?+ /8#"/+ '8&'+ "8018+
(3:(T(3:(/+ 0*+
[0:6)(+ I,=.+ &)(+
=(1&6/(+ #5+ "8018+ 1#*')#4+#)+#=/()C&'0#*+%&'8T%&'8/7+
+ + +
Table 1: List of edges of the graph in Figure 4(b) and corresponding paths
C2′ C1′
EP1 EP2
PI
(b) Condition 2 C2
C1
EP1 EP2
PI1 PI2
(a) Condition 1
C2′ C1′
EP1 EP2
PI
(c) Condition 3
C2′ C1′
EP1 EP2
PI
(d) Condition 4
R4 R3
R1
R2
R2 R5
R4
Mult
R3
R1 R2
R2 R5
(a) (b)
Figure 4: (a) SCG and (b) RCG of MULT of Figure 1
Figure3: Control paths typically depicting the conditions of Theorem 1
(
+'-,.,/,0.(@*+<*+(3:(+0*+'8(+J^O+#5+&+9#364(+5)#9+&*2+*#3(+ 0*+J +'#+&*2+*#3(+0*+J #)+J ___7#) J E+&1'6&442+)(%)(/(*'+
&*+J!K+%&'8+'8)#6:8+'8(+ 9#364(+&*3+8(*1(+"(+)(5()+'#+/618+
&*+(3:(+&++%#/7('12'7+
+'-,.,/,0.( AM+ <*+ (3:(+ 0*+ '8(+ J^O+ =('"((*+ &*2+ '"#+ C()'01(/+
#5+J EJ ___77&*3 J +0/+&+>0./30&('12'7+
+'-,.,/,0.( B*+ D5+ &+ /6=+ :)&%8+ #5+ '8(+ J^O+ #5+ &+ 9#364(+ "0'8+
#*42+#*(+*#3(+5)#9+(&18+#5+J E+J J +&*3+J +0/+&+140S6(E+ '8(*+'80/+0/+)(5())(3+'#+&/+&+/'</(>&,C?'7++
<+ '(/'+ 140S6(+ 09%40(/+ '8(+ (G0/'(*1(+ #5+ *+ 1#*')#4+ %&'8+ &*3+ #*(+
#=/()C&'0#*+ %&'8E+ "8018+ &)(+ /655010(*'+ '#+ '(/'+ *+ J!K+ %&'8/+
%&//0*:+'8)#6:8+*+0*%6'/+#5+'8(+9#364(+07(7+&+'(/'+140S6(+0*+'8(+ J^O+#5+&*+*+0*%6'+9#364(+0*1#)%#)&'(/+'(/'+%4&*+5#)+*+%&'8/7+ 57'03'$(8*(<44+J!K+%&'8/+'8)#6:8+&+9#364(+&)(+!-+'(/'&=4(+ 05E+'8(+%&'8+(3:(/+1#))(/%#*30*:+'#+&44+J!K+%&'8/+'8)#6:8+'8(+ 9#364(+ (G0/'+ 0*+ 0'/+ J^O+ &*3+ (&18+ %&'8+ (3:(+ 0/+ %&)'+ #5+ /#9(+ '(/'+140S6(7++
!8(+%)##5+#5+'80/+'8(#)(9+0/+:0C(*+0*+>i@7+ E"#@0&5,<6#(2#&/0#@F.#=0&/()+
!80/+ /(1'0#*+ 30/16//(/+ '8(+Q[!+(4(9(*'/+"(+ 6'040P(+0*+ #6)+
&%%)#&18+ &*3+ &4/#+ '8(+ &4:#)0'89+ 5#)+ (55010(*'+ &330'0#*+ #5+ '8(+ Q[!+(4(9(*'/+'#+&6:9(*'+&+3&'&+%&'8+'#+&*+F!-!+#*(7+ E"!#./0#@F.#0<0=0%&6+
N(+1#*/03()+'8)((+'2%(/+#5+Q[!+(4(9(*'/+0*+#6)+&%%)#&187+
!8(2+ &)(+ WXY/E+ $*%1+ 56*1'0#*/+ &*3+ )#'&'0*:+ (*8&*1(3+ 540%$ 54#%/+,Jd[[/.7+!8(+#%()&'0#*+#5+&+WXY+0/+"(44+;*#"*7+<=#6'+ '8(+$*%1+56*1'0#*E+"(+=)0(542+(G%4&0*(3+0*+\(1'0#*+H7?+<*+Jd[[+ 1#*/0/'/+ #5+ '"#+ 540%$54#%/+ &*3+ &+ WXY+ &/+ /8#"*+ 0*+ 50:6)(+ R7+
!8(+1#*')#4+0*%6'+#5+'8(+WXY+0/+6/(3+&/+'8(+9#3(+/(4(1'#)7+D*+
*#)9&4+9#3(+'8(+Jd[[+=(8&C(/+40;(+&+*#)9&4+540%$54#%7+X/0*:+
*#)9&4+ 9#3(+ '"#+ =0'/+ 1&*+ =(+ 4#&3(3+ '#+ '8(+ Jd[[7+ n6/'+ &5'()+ 4#&30*:+ '"#+
=0'/E+'8(+9#3(+1&*+ =(+18&*:(3+'#+'(/'+ 9#3(7+D*+'(/'+9#3(+'8(+=0'/+(G18&*:(+ '8(0)+ %#/0'0#*+ &'+ (C()2+ 14#1;+ =6'+ )(9&0*+/'#)(3+0*+'8(+Jd[[7+F(*1(+&*+ Jd[[+1&*+=(+)(:&)3(3+&/+&+A$=0'+8#43+ )(:0/'()7+ L5+ &+ !-+ C(1'#)E+ '8(+ =0'+ #5+
"8018+C(1'#)+/8#643+=(+4#&3(3+50)/'+'#+ '8(+ Jd[[+ 3(%(*3/+ #*+ '8(+ '09(+ #5+ 4#&30*:+ &*3+ '8(+'09(+ #5+&%%420*:+'8(+ C(1'#)/7+
E"-# G<8(',&/=#2('#5)),%8#@F.#0<0=0%&6#
D*+ '80/+ /(1'0#*+ "(+ %)(/(*'+ #6)+ &4:#)0'89+ 5#)+ &330*:+ '(/'+ 8&)3"&)(+'#+&*+J!K+3&'&+%&'87+[#)+/09%4010'2+"(+&)(+3(/1)0=0*:+
#6)+ &4:#)0'89+ &//690*:+ '8&'+ #%()&'0#*&4+ 9#364(/+ 0*+ '8(+ 3&'&+
%&'8+ 8&/+ 9&G0969+ '"#+ 0*%6'/+ &*3+ '8()(+ 0/+ *#+ 18&0*0*:+ #5+ 9#364(/7+ !80/+ 9(&*/+ '8()(+ 0/+ *#+ J!K+ %&'8+ #5+ 3(:)((+ H+ #)+ 9#)(+ 0*+ '8(+ 3&'&+ %&'87+ W#/'+ #5+ '8(+ =(*189&);/+ /&'0/52+ '80/+ 1#*30'0#*7+<4/#E+#6)+&%%)#&18+ 1&*+=(+(G'(*3(3+ 5#)+3&'&+%&'8/+
"0'8+9#364(/+8&C0*:+9#)(+'8&*+'"#+0*%6'/7+!8(+0*%6'E+#6'%6'+
&*3+#%'090P&'0#*+5#)+#6)+&4:#)0'89+&)(+&/+5#44#"/7+ D.%?/*+<*+J!K+3&'&+%&'8+
E?/%?/M+<*+F!-!+3&'&+%&'8+
E%/,$#,F#/,0.( *+ W0*0*0P0*:+ 8&)3"&)(+ #C()8(&3+ &*3+ '(/'+
&%%401&'0#*+'09(+
E"-"!#H0<0+&,%8#1(&0%&,5<#+(%&'(<#5%)#(C60'I5&,(%#15&/6+ dC()2+ )(:0/'()+ ,#'8()+ '8&*+'8(+1#*/'&*'+)(:0/'()/.+#5+&+ 3&'&+
%&'8+0/+&'+'8(+/'&)'0*:+#5+/#9(+J!K+%&'8+&*3+&4/#+&'+'8(+(*30*:+
#5+/#9(+J!K+%&'87+!8()(5#)(+1#*')#4+%&'8/+&)(+*(1(//&)2+5)#9+ -D/+ '#+ &44+ )(:0/'()/+ &*3+ /#+ &)(+ '8(+ #=/()C&'0#*+ %&'8/+ 5)#9+ &44+ )(:0/'()/+ '#+ -L/7+ F#"(C()+ '8(+ *69=()+ #5+ %&'8/+ 0*+ '8(+ 3&'&+
%&'8+ 1&*+ =(+ C()2+ 4&):(+ &*3+ "(+ 6/(+ /#9(+ 8(6)0/'01/+ '#+ /(4(1'+ /#9(+ %#'(*'0&4+ 1#*')#4+ &*3+ #=/()C&'0#*+ %&'8/7+ N(+ 9&;(+ &+ /('+
^-+ #5+ %#'(*'0&4+ 1#*')#4+ %&'8/+ &*3+ &+ /('+ L-+ #5+ %#'(*'0&4+
#=/()C&'0#*+%&'8/+5#)+(&18+)(:0/'()+J7+!8(+50)/'+9(9=()/+#5+^-+
&)(+'8(+/8#)'(/'+3(%'8+%&'8/+5)#9+(&18+ -D+'#+J7+N(+5&C#)+'8(+ /8#)'(/'+ 3(%'8+ %&'8/+ =(1&6/(+ '8(2+ 8(4%+ '#+ )(361(+ '8(+ '(/'+
&%%401&'0#*+ '09(7+ !#+ 3('()90*(+ '8(+ /8#)'(/'+ 3(%'8+ 1#*')#4+
%&'8/E+ "(+ )(%)(/(*'+ '8(+ 3&'&+ %&'8+ &/+ &+ %#)'+ 30:)&%8+ >o@7+ !8(+ 30:)&%8+#5+'8(+3&'&+%&'8+#5+[0:6)(+?+0/+/8#"*+0*+[0:6)(+Z+,&.7+<+
*#3(+)(%)(/(*'/+&+%#)'+0*+'8(+3&'&+%&'8+&*3+&*2+(3:(+/&2E+,6EC.+ 09%40(/+'8&'+(0'8()+&+9('&4+40*(+1#**(1'/+6+'#+C+#)+6+&*3+C+&)(+ 0*%6'+ %#)'+ &*3+ #6'%6'+ %#)'+ )(/%(1'0C(42+ #5+ '8(+ /&9(+ (4(9(*'7+
!8(+ /8#)'(/'+ 3(%'8+ 1#*')#4+ %&'8/+ 1&*+ =(+ /(4(1'(3+ =2+
%()5#)90*:+ &+ 9#3050(3+ =)(&3'8+ 50)/'+ /(&)18+ ,B[\.+ #*+ '8(+ 30:)&%87+!8(+B[\+0/+%()5#)9(3+*+'09(/+"8()(+*+0/+'8(+*69=()+
#5+-D/+#5+'8(+3&'&+%&'87+d&18+#5+*+-D/+&)(+#*1(+1#*/03()(3+&/+ '8(+ /#6)1(+ *#3(7+ [0:6)(+ Z+ ,=.+ /8#"/+ '8(+ =)(&3'8+ 50)/'+ ')((+ ,'801;+ 40*(/.+ #5+ '8(+ 30:)&%8+ #5+ [0:6)(+ Z+ ,&.+ 1#*/03()0*:+ -D?+ &/+ '8(+ /#6)1(+ *#3(7+ !80/+ ')((+ 1#*'&0*/+ '8(+ /8#)'(/'+ 3(%'8+ %&'8/+ 5)#9+ -D?+ '#+ (&18+ )(:0/'()+ )(&18&=4(+ 5)#9+ -D?7+ \0904&)42+ '8(+ 9(9=()/+#5+L-+#5+&*2+)(:0/'()+J+&)(+'8(+/8#)'(/'+3(%'8+%&'8/+
5)#9+J+'#+(&18+-L7+!8(+/8#)'(/'+3(%'8+#=/()C&'0#*+%&'8/+1&*+
=(+ 3('()90*(3+ =2+ )(C()/0*:+ '8(+ (3:(/+ #5+ '8(+ 30:)&%8+ &*3+
%()5#)90*:+ /0904&)+ B[\+ 9+ '09(/+ "8()(+ 9+ 0/+ '8(+ *69=()+ #5+ -L/7+ [#)+ (&18+ 9(9=()+ #5+ ^-+ &*3+ L-+ #5+ &*2+ )(:0/'()+ "(+ 9&0*'&0*+&+C&)0&=4(E+"8018+"(+)(5()+'#+&/+'8(+a1#/'a+#5+'8(+%&'87+
!8(+ 1#/'+ #5+ '8(+ %&'8+ 0/+ *#'80*:+ =6'+ '8(+ *69=()+ #5+ $*%1+ 56*1'0#*/+&//#10&'(3+'#+'8(+%&'8+07(7+'8(+1#/'+#5+&+$*%1+56*1'0#*+ 0/+?7+
E"-"-#./0#7'01'(+066#
[0)/'E+ "(+ 1#*/03()+ '8(+ [J/+ #5+ &44+ 9#364(/7+ \6%%#/(E+ &+ )(:0/'()+J +&%%(&)/+#*+=#'8+0*%6'+&*3+#6'%6'+/03(/+#5+'8(+\^O+
#5+&+9#364(+W7+!80/+09%40(/+'8&'+J ++0/+&*+[J+'#+W7+j#"E+05+&+ 1#*')#4+%&'8+5)#9+&+-D+'#+J +0*1#)%#)&'(/+&+$*%1+'#+WE+'8(*+'80/+ 1#*')#4+%&'8+1&**#'+=(+6/(3+'#+'(/'+&*2+J!K+%&'8+'8&'+1)#//(/+ Figure 5: Rotating
enhanced flip-flop
D Q CK
Q D CK clk
One PI1
One
PI2
PO1 PO2
One PI1
One
PI2
PO1 PO2
(a) (b)
Figure 6: (a) Port digraph of the data path of Figure 1 and (b) Breadth first tree of the digraph of Figure 6(a)
W+,(G%4&0*(3+ 0*+\(1'0#*+H7?.7+ \#+"(+ 50)/'+50*3+ 0*+'8(+ ^-+#5+ J ++ 5#)+ &+ 1#*')#4+ %&'8+ "0'8#6'+ &+ $*%1+ '#+ W7+ D5+ "(+ /611((3E+ "(+ /"0'18+ '#+ #'8()+ [J+ #5+ W+ #)+ [J+ #5+ #'8()+ 9#364(7+ D5+ *#+ /618+ 1#*')#4+%&'8+0/+5#6*3+0*+'8(+^-+#5+J ++"(+/(&)18+'8(+(*'0)(+3&'&+
%&'87+ [#)+ '80/+ /(&)18E+ "(+ )(9#C(+ '8(+ (3:(/+ 5)#9+ 0*%6'/+ '#+
#6'%6'+ #5+ W+ 0*+ '8(+ 30:)&%8+ &*3+ '8(*+ 50*3+ /8#)'(/'+ %&'8+ 5)#9+ (&18+-D+'#+J +6*'04+&+%&'8+0/+5#6*37+D5+&+%&'8+0/+5#6*3E+'80/+%&'8+ 0/+&33(3+'#+'8(+^-+#5+J 7+F#"(C()+'8(+5&046)(+#5+/618+&+/(&)18+ 09%40(/+'8&'+'8()(+0/+*#+1#*')#4+%&'8+5)#9+&*2+-D+'#+J +"0'8#6'+
&+$*%1+'#+W7+X*3()+/618+&+/0'6&'0#*+&+30)(1'+%&'8+0/+&33(3+'#+J + 6/0*:+ &+ '(/'+ WXY+ 5)#9+ &+ -D7+ !80/+ -D+ 0/+ 18#/(*+ =&/(3+ #*+ '8(+ 1#*')#4+ %&'8/+ 0*+ ^-/+ #5+ '8(+ )(:0/'()/+ 1#**(1'(3+ '#+ '8(+ #'8()+ 0*%6'+#5+W+,0*%6'+'#+"8018+J +0/+*#'+1#**(1'(3.7+D5+'8(+9&c#)0'2+
#5+'8(+*#3(/+1#**(1'(3+'#+'8(+#'8()+ 0*%6'+ #5+ W+ 8&C(+ 1#*')#4+
%&'8+5)#9+&+-DE+"(+18##/(+#'8()+-D+5#)+J 7+!80/+30)(1'+%&'8+0/+ 0*1463(3+'#+'8(+^-+#5+J 7+D*+1&/(+'8(+3&'&+%&'8+8&/+/0*:4(+0*%6'E+ 0'+ 90:8'+ =(+ 30550164'+ '#+ 50*3+ &+ /60'&=4(+ -D7+ X*3()+ /618+ &+ /0'6&'0#*+ "(+ &6:9(*'+ (&18+ 540%$54#%+ #5+ J + '#+ Jd[[7+ !80/+ 0*5#)9&'0#*+ 0/+ &33(3+ '#+ '8(+ %&'8/+ 0*+ '8(+ ^-+ #5+ J 7+ N(+ '8(*+ /"0'18+'#+#'8()+[J+#5+W+#)+[J+#5+#'8()+9#364(+6*'04+&44+[J/+0*+ '8(+3&'&+%&'8+&)(+1#*/03()(37+ N(+/'&)'+'#+1#*/03()+'8(+[J/+ #5+ '8(+9#364(/+*(&)()+'#+-D/+50)/'7+\#9('09(/+&+/0*:4(+WXY+1&*+
=(+ 6/(3+ 5#)+ 9#)(+ '8&*+ #*(+ [J+ #5+ &+ 9#364(7+ D*+ [0:6)(+ ]E+ '8(+ '(/'+WXY+0/+%)#C030*:+1#*')#4+%&'8/+5)#9+34<+'#+=#'8+6C+&*3+ 6D7+D*+1&/(+#5+ /0*:4(+ 0*%6'+ Q&'&+ %&'8E+ 05+ 0'+=(1#9(/+ *(1(//&)2+ '#+ &6:9(*'+ 540%$54#%/+ #5+ 9#)(+ '8&*+ #*(+ )(:0/'()+'#+Jd[[E+ "(+ 6/(+ &+ :4#=&4+ Jd[[+ )(:0/'()+ 1#**(1'(3+ '#+ '8(+ #*42+ -D+ #5+ '8(+ 3&'&+ %&'87+\618+ &*+ Jd[[+ )(:0/'()+ 1&*+=(+6/(3+&/+&+ -D+5#)+!-+ '(/'0*:7+!80/+0/+=(1&6/(+&*+Jd[[+1&*+/'#)(+'"#+=0'/+5#)+&/+4#*:+
&/+ 0'+ 0/+ *(1(//&)27+ Q0)(1'+ %&'8/+ '8(*+ 1&*+ =(+ &33(3+ 5)#9+ '8(+ :4#=&4+ Jd[[+ )(:0/'()+ '#+ [J/+ 6/0*:+ '(/'+ WXY/7+ N(+ 6/(+ :4#=&4+ Jd[[+ =(1&6/(+ '8(+ 8&)3"&)(+ #C()8(&3+ 0*16))(3+ =2+ )(:0/'()/+ 0/+ C()2+80:87+N8(*(C()+"(+&33+&*2+Q[!+(4(9(*'E+"(+6%3&'(+'8(+
^-/+ #5+ )(:0/'()/+ &55(1'(3+ =2+ '8(+ &330'0#*7+ <330'0#*+ #5+ '(/'+ WXY/+&*3+Jd[[+)(:0/'()/+1)(&'(/+/#9(+9#)(+%&'8/+#5+3(:)((+
?+ 0*+ '8(+ 3&'&+%&'87+N(+/8#643+ &4/#+ 1#*/03()+'8(+!-+'(/'&=040'2+
#5+ '8(/(+ %&'8/7+ -)(%)#1(//+ #5+ &330*:+ Q[!+ (4(9(*'/+ 0/+ *#"+ 1#9%4('(7+ B(1&6/(+ #5+ &330*:+ Q[!+ (4(9(*'/+ 0*+ %)(%)#1(//E+
\^O/+#5+9#364(/+0*+'8(+3&'&+%&'8+)(9&0*+6*18&*:(3+ E"-">#@0&0'=,%,%8#.06<5%6#
N(+ 30/16//(3+ #6)+ &4:#)0'89+ 5#)+ &330*:+ /#9(+ Q[!+ (4(9(*'/+ 0*+ '8(+ %)(C0#6/+ /(1'0#*7+ D*+ '80/+ /(1'0#*E+"(+ 1#*'0*6(+
#6)+&4:#)0'89+#5+&330*:+9#)(+Q[!+(4(9(*'/+'#+(*/6)(+'8(+'(/'+
%4&*/+ 5#)+ &44+ J!K+ %&'8/7+ [0)/'+ "(+ &33)(//+ '8(+ J!K+ %&'8/+ #5+ 3(:)((+A+&*3+'8(*+#5+3(:)((+?7++
3.4# 15&/6# (2# )08'00# -J#N(+ 1#*/03()+ &44+ J!K+ %&'8/+ %&//0*:+ '8)#6:8+ &+ 9#364(+ &'+ &+ '09(7+ !8(+ 5#44#"0*:+ 5#6)+ /'(%/+ &)(+
%()5#)9(3+5#)+(&18+'"#$0*%6'+#%()&'0#*&4+9#364(7+
B0%0'5&,%8# 3AB# 2'(=# HAB# K6&01# !LJK('E+ W+ 0/+ &+ A$0*%6'+ 9#364(+ &*3+ J E+J +&*3+ J +&)(+'8(+/('+#5+ *#3(/+1#**(1'(3+'#+ '8(+ 4(5'+ 0*%6'E+ )0:8'+ 0*%6'+ &*3+ #6'%6'+ #5+ '8(+ 9#364(7+ d&18+ 9(9=()+#5+J +&*3+J +8&/+&+/('+#5+1#*')#4+%&'8/+^-+&*3+(&18+ 9(9=()+#5+J +8&/+&+/('+#5+#=/()C&'0#*+%&'8+L-7+K('+) +∈+J +
&*3+) +∈J 7+j#"+"(+4##;+5#)+'"#+1#*')#4+%&'8/E+#*(+5)#9+^-+
#5+) +&*3+#'8()+5)#9+^-+#5+) E+/618+'8&'+'8(2+/&'0/52+&*2+#*(+
#5+'8(+5#6)+1#*30'0#*/+#5+;*-"%-@'<7+D*+1&/(+"(+50*3+9#)(+'8&*+
#*(+%&0)+#5+1#*')#4+%&'8/+'#+/&'0/52+&*2+1#*30'0#*+#5+;*-"%-@'<E+
"(+18##/(+'8(+%&0)+8&C0*:+4#"(/'+1#/'7+N(+&33+&+1#*')#4+(3:(+
=('"((*+) +&*3+) +0*+'8(+J^O+&*3+;((%+)(1#)3+#5+'8(+4#"(/'+
1#/'+ 1#*')#4+ %&'8/+ '8&'+ /6%%#)'+ '80/+ (3:(7+ N(+ /8#643+ ;((%+ 0*+ 90*3+'8&'+0*+1&/(+) +&*3+) +0/+&+[J+'#+WE+"(+1&**#'+1#*/03()+&+ 1#*')#4+%&'8+5#)+) #)+) +0*1#)%#)&'0*:+&+$*%1+'#+W+6*4(//+) +#)+ ) + 0/+ &6:9(*'(3+ '#+ &*+ Jd[[+ )(:0/'()7+ D5+ "(+ 5&04+ '#+ 50*3+ &+ 1#*')#4+ (3:(+ =('"((*+ ) + &*3+ ) + "(+ /"0'18+ '#+ &*#'8()+ %&0)+ #5+
*#3(/7+ N(+ /(&)18+ 5#)+ 1#*')#4+ (3:(/+ =('"((*+ (C()2+ %#//0=4(+
%&0)+#5+*#3(/+"0'8+#*(+*#3(+5)#9+J +&*3+#*(+*#3(+5)#9+J 7+ [#)+ (&18+ 9(9=()+ #5+ J E+ "(+ 18##/(+ '8(+ 4#"(/'+ 1#/'+
#=/()C&'0#*+%&'8+5)#9+0'/+L-+&*3+&33+%&'8+(3:(/+'#+'8(+J^O+
&/+3(/1)0=(3+0*+%1&-'5+0*+\(1'0#*+H7A7++
G)),%8# @F.# 0<0=0%&6# &(# G*8=0%&# 3AB# K6&01# -LJ#D*+ '8(+ J^OE+/#9(+*#3(T*#3(/+#5+J +#)+J +9&2+*#'+=(+1#**(1'(3+'#+
&*2+1#*')#4+(3:(7+[#)+&*2+/618+*#3(+"(+&33+Q[!+(4(9(*'/+'#+ 1)(&'(+&+1#*')#4+(3:(+0*+'8(+J^O+0*1#)%#)&'0*:+'80/+*#3(7+[0)/'+
"(+')2+=2+&330*:+&+30)(1'+%&'8+'#+/618+&+*#3(+5)#9+/#9(+-D+=2+ 9(&*/+#5+&+'(/'+WXY7+D*+&+"#)/'+1&/(+"(+&6:9(*'+/618+&+*#3(+ '#+ &*+ Jd[[+ )(:0/'()7+ F#"(C()E+ 05+ 0'+ =(1#9(/+ *(1(//&)2+ '#+
&6:9(*'+ 9#)(+ '8&*+ #*(+ )(:0/'()E+ "(+ )&'8()+ 1)(&'(+ &+ :4#=&4+ Jd[[+ )(:0/'()+ &/+ 9(*'0#*(3+ 0*+ \(1'0#*+ I7A7A7+ !8(*E+ 30)(1'+
%&'8/+1&*+=(+1)(&'(3+5)#9+'8(+:4#=&4+Jd[[+)(:0/'()+'#+)(S60)(3+
*#3(/+ =2+ 9(&*/+ #5+ '(/'+ WXY/7+ !8(+ J^O+ #5+ W+ 0/+ *#"+ /655010(*'+ 5#)+ !-+ '(/'&=040'2+ #5+ &*2+ J!K+ %&'8+ '8)#6:8+ 0'7+ F#"(C()E+ "8(*+ &+ 30)(1'+ %&'8+ '#+ &+ *#3(+ 0/+ 1)(&'(3E+ "(+ 18(1;+
"8('8()+ '80/+ %&'8+ 1&*+ =(+ 6'040P(3+ '#+ )(9#C(+ /#9(+ Q[!+ (4(9(*'/+&33(3+5#)+'8(+%)(C0#6/42+%)#1(//(3+9#364(/7+<+30)(1'+
%&'8+'#+&+*#3(+90:8'+=(+6/(3+0*/'(&3+#5+/#9(+#'8()+*(1(//&)2+ 1#*')#4+%&'8T%&'8/+'#+'8(+/&9(+*#3(E+"8018+0*1#)%#)&'(/+&+$*%1+ 56*1'0#*7+
9,%,=,M,%8#+(%&'(<#0)806#,%#3AB#K6&01#>LJ+!8(+J^O+9&2+ 8&C(+ /#9(+ (G1(//+ 1#*')#4+ (3:(/7+ L5+ &44+ '8(+ 1#*')#4+ (3:(/+ "(+ /(4(1'+ '8(+ 90*0969+ *69=()+ #5+ '8(9+ 56450440*:+ '8&'+(&18+ *#3(+ 0*+ J + #)+ J + 0/+ 1#**(1'(3+ '#+ &'+ 4(&/'+ #*(+ 1#*')#4+ (3:(7+ W0*0969+ *69=()+ #5+ 1#*')#4+ (3:(/+ "044+ 1)(&'(+ 90*0969+
*69=()+ #5+ '(/'+ 140S6(/+ 0*+ '8(+ J^O+ '8&'+ &)(+ /655010(*'+ 5#)+ '(/'+
%4&*/+#5+J!K+%&'8/+'8)#6:8+W7+
G)),%8# @F.# 0<0=0%&6# 2('# /73?# F*%+&,(%6# K6&01# ELJ+ X*'04+
*#"+"(+&)(+ "0'8+'8(+ &//69%'0#*+'8&'+$*%1+56*1'0#*+(G0/'+ 5)#9+
&*2+ 0*%6'+ '#+ '8(+ #6'%6'+ #5+ &*2+ #%()&'0#*&4+ 9#364(7+ D'+ 0/+ *#"+ '09(+'#+18(1;+"8('8()+&+$*%1+'8&'+"(+*((3+)(&442+(G0/'/+,1&*+=(+ 09%4(9(*'(3+ =2+ &+ /6%%#)'+ %&'8.+ #)+ "(+ /8#643+ &33+ Q[!+ (4(9(*'+ ,9&/;+ #)+ #'8()/.+ 5#)+ 0'7+ [#)+ 3#0*:+ '80/+ "(+ 1#*/03()+ &+ '(/'+ 140S6(+ &'+ &+ '09(7+ <+ '(/'+ 140S6(+ 0*+ '8(+ J^O+ #5+&+ '"#$0*%6'+
#%()&'0#*&4+ 9#364(+ 0*1#)%#)&'(/+ '"#+ 1#*')#4+ %&'8/+ &*3+ #*(+
#=/()C&'0#*+ %&'87+ N(+ /(&)18+ 5#)+ /6%%#)'+ %&'8/+ 5#)+ '8(+ $*%1+ 56*1'0#*/+ &//#10&'(3+ '#+ '8(/(+ '8)((+ %&'8/+ 6/0*:+ /#9(+ 9&*6&4+ 1&4164&'0#*7+ <+ /6%%#)'+ %&'8+ 9&2+ 8&C(+ '090*:+ 1#*5401'+ "0'8+ 1#*')#4+%&'8/+#)+#'8()+/6%%#)'+%&'8/7+!090*:+1#*5401'+9(&*/+0'+
=(1#9(/+ *(1(//&)2+ '#+ %)#C03(+ 3055()(*'+ C&46(/+ &'+ '8(+ /&9(+ -D+
&'+ '8(+ /&9(+ '09(7+ N(+ &33+ 9&/;+ (4(9(*'+ '#+ )(&40P(+ '8(' $*%1+ 56*1'0#*/+5#)+"8018+&*2+/6%%#)'+%&'8+1&**#'+=(+5#6*3+"0'8#6'+ '090*:+ 1#*5401'7+ !8(+ 1#/'+ #5+ '8(+ $*%1+ 56*1'0#*+ )(&40P(3+ =2+ &+ 9&/;+ (4(9(*'+ =(1#9(/+ P()#+ &*3+ "(+ 6%3&'(+ '8(+ 1#/'+ #5+ &44+ 1#*')#4+ &*3+ #=/()C&'0#*+ %&'8/E+ "8018+ 0*1463(/+ '80/+ $*%1+ 56*1'0#*7+N(+1#*/03()+&44+'8(+'(/'+140S6(/+0*+'8(+J^O+#5+W+0*+&+ /0904&)+"&27++
!8(+ &=#C(+ 5#6)+ /'(%/+ &)(+ %()5#)9(3+ 5#)+ &44+ '"#$0*%6'+ 9#364(/+1#*/03()0*:+'8(+9#364(/+*(&)()+'#+'8(+-D/+50)/'7+N8(*+
"(+ 50*0/8+ &44+ '8(+ '"#$0*%6'+ 9#364(/+ '8(+ '(/'&=040'2+ #5+ &44+ '8(+ J!K+%&'8/+#5+3(:)((+A+0/+(*/6)(37+
3.4# 15&/6# (2# )08'00# !J#N(+ *#"+ 1#*/03()+ '8(+ '(/'&=040'2+ #5+ J!K+ %&'8/+ #5+ 3(:)((+ ?7+ K('+ J + &*3+ J + &)(+ '8(+ /'&)'0*:+ &*3+ (*30*:+ )(:0/'()+ #5+ &*+ J!K+ %&'8+ #5+ 3(:)((+ ?7+ N(+ 18##/(+ '8(+ 4#"(/'+1#/'+%&'8+5)#9+'8(+
^-+ #5+ J + &/+ '8(+ 1#*')#4+
%&'8+ &*3+ '8(+ 4#"(/'+ 1#/'+
%&'8+5)#9+'8(+L-+#5+J +&/+ '8(+ #=/()C&'0#*+ %&'87+ D5+
&*2+ $*%1+ #5+ 1#/'+ ?+ 0/+
&//#10&'(3+ "0'8+ '8(/(+
%&'8/E+ "(+ ')2+ '#+ )(&40P(+ '8(9+ 6/0*:+ /6%%#)'+ %&'87+ D*+ 1&/(+ "(+ 1&**#'+ 50*3+
&*2+ /6%%#)'+ %&'8+ "0'8#6'+ '090*:+ 1#*5401'E+ "(+ &33+
9&/;+ (4(9(*'+ #)+
964'0%4(G()+ '#+ )(&40P(+ '8(97+ N(+ 1#*/03()+ &44+ J!K+%&'8/+#5+3(:)((+?+0*+&+ /0904&)+ "&27+ [0:6)(+ ]+
/8#"/+ '8(+ F!-!+
(S60C&4(*'+ #5+ '8(+ 3&'&+ %&'8+ #5+ [0:6)(+ ?+ &6:9(*'(3+ =&/(3+ #*+ '8(+&4:#)0'89+3(/1)0=(3+&=#C(7+
N"+OP10',=0%&5<#306*<&6+
N(+ C()050(3+ '8(+ %()5#)9&*1(+ #5+ #6)+ Q[!+ 9('8#3+ =2+
&%%420*:+ 0'+ '#+ H+ =(*189&);+ 3&'&+ %&'8/+ &*3+ &+ JD\^+ %)#1(//#)+
%)#C03(3+=2+&+0*36/')27+!8(+18&)&1'()0/'01/+#5+'8(/(+3&'&++%&'8/+
&)(+ /8#"*+ 0*+ !&=4(+ ?7+ D*+ '80/+ '&=4(+ -D/+ &*3+ -L/+ 3(*#'(+ '8(+
*69=()+ #5+ %)09&)2+ 0*%6'/+ &*3+ %)09&)2+ #6'%6'/+ #5+ '8(+ 3&'&+
%&'8+)(/%(1'0C(427+ JdO/E+ WXY/+&*3+L-/+&)(+'8(+ *69=()/+ #5+ )(:0/'()/E+ 964'0%4(G()/+ &*3+ #%()&'0#*&4+ 9#364(/+ 0*+ '8(+ 3&'&+
%&'87+!8(+ 4&/'+1#469*+ #5+!&=4(+A+ /8#"/+ '8(+&)(&/+ #5+'8(+ 3&'&+
%&'8/+ :(*()&'(3+ =2+ '8(+ 4#:01+ /2*'8(/0/+ '##4+ Q(/0:*+ ^#9%04()+ ,\2*#%/2/.E+"8018+"(+6/(3+5#)+#6)+(G%()09(*'/7+
+ + +
+ +
!&=4(+ I+ /8#"/+ '8(+ )(/64'/+ )(:&)30*:+ 8&)3"&)(+ #C()8(&37+ N(+ 1#9%&)(+ '8(+ 8&)3"&)(+ #C()8(&3+ 0*16))(3+ =2+ #6)+ 9('8#3+ '#+ '8&'+ =2+ '8(+ (*8&*1(3+ /1&*+ &%%)#&187+ D*+ =#'8+ 1&/(/E+ '8(+
%()1(*'&:(+#5+&)(&+#C()8(&3+3(1)(&/(/+"0'8+'8(+ 0*1)(&/(+0*+=0'+
"03'8+#5+'8(+3&'&+%&'8/7+F#"(C()E+'8(+&)(&+#C()8(&3+0*16))(3+
=2+ #6)+ 9('8#3+ 0/+ &4"&2/+ 9618+ 4#"()7+ [#)+ #6)+ Q[!+ 9('8#3E+ '8(+ 1#469*/+ WXYE+ !FJX+ &*3+ Jd[[+ /8#"/+ '8(+ *69=()+ #5+
&33(3+WXY/E+$*%1+56*1'0#*/+&*3+Jd[[+)(:0/'()/7+ Q"#A(%+<*6,(%6#
!8(+ 1#*1(%'+ #5+ 80()&)1801&4+ '(/'&=040'2+ 5#)+ 3(4&2+ 5&64'/+ 0/+ 0*')#361(3+ 0*+ '80/+ %&%()7+ -)(1#9%6'(3+ C(1'#)+ %&0)/+ &)(+
%)#%&:&'(3+ C0&+ 1#*')#4+ %&'8/+ 5)#9+ %)09&)2+ 0*%6'/+ '#+
&%%)#%)0&'(+ 4#1&'0#*/+ &*3+ &)(+ &%%40(3+ 0*+ &+ !-+ 5&/80#*+ '#+ '(/'+
%&'8/+ #5+ 6*0'2+ /(S6(*'0&4+ 3(%'87+ !(/'+ )(/%#*/(/+ &)(+ &4/#+
%)#%&:&'(3+C0&+#=/()C&'0#*+%&'8/+5)#9+'8(+(*3+%#0*'/+#5+%&'8/+ 6*3()+ '(/'+ '#+ %)09&)2+ #6'%6'/7+ <+ Q[!+ 9('8#3+ 0/+ &4/#+
%)(/(*'(3+ '8&'+ 1&*+ =(+ &%%40(3+ '#+ &6:9(*'+ &+ 3&'&+ %&'8+ '#+ &*+ F!-!+#*(7+-)0#)0'2+8&/+=((*+:0C(*+'#+6/(+'8(+(G0/'0*:+%&'8/+0*+ '8(+3&'&+%&'8+&/+1#*')#4+%&'8/+&*3+#=/()C&'0#*+%&'8/7+!8(+&)(&+
#C()8(&3+ #5+ #6)+ Q[!+ 9('8#3+ 0/+ /9&44()+ 1#9%&)(3+ '#+ '8&'+ #5+ '8(+(*8&*1(3+/1&*+&%%)#&187+[#)+/#9(+(G&9%4(+3&'&+%&'8/E+'8(+
&)(&+#C()8(&3+0*16))(3+=2+#6)+Q[!+9('8#3+0/+A$?A+p+#*427+ G+R%(S<0)8=0%&6#
3020'0%+06J#
Table 2: Circuit characteristics
Table 3: Hardware overhead
Add
Mux1
Mux2 R1
Mux3 R2
R3
Mux4
Mult Mux5
Mux6 R4
One One
R5
PO2 PO1
PI1 PI2
thru Test
MUX
Figure 7: the HTPT equivalent of the data path of Figure 1
