Dear All,

Can you help me to find something wrong on the following theorem :

THEOREM 2 : if A and B are WSO(n1, a,b) and WSO(n2,c,d). respectively, where b>=c, then A(n1) * B(n2) is WSO(n1+n2-1, a,b-c+d) with depth max {d(A),d(B)+b-c} and fan-out max{fo(A),fo(B)}

THEOREM 3 : H(n) is WSO(n,r,r+1) with depth 2r+1 and fan-out 2, where r=[;g(n-1)]
LEMMA 5, HD(i) is WSO(2powi+1, i, 2i+1) with depth 2i+1 and fan-out 2, where i>=0,
PROOF. We shall prove by induction on i
Base Step. From Theorem 3, the H(2pow0 +1) circuit is WSO(2pow0 +1,0,1) with dept 1 and fan out 2
Induction Step: Assume that HD(j) is WSO(2powj+1, j, 2j+1) with depth 2j+1 and fan out 2. From theorem 3, H(2powj+1 +1) is WSO(2powj+1 +1,j+1,j+2) with depyh 2j+3 and fan-out 2. Since HD(j+1)=H(2powj+1 +1) * HD(j), from Theorem 2, HD(j+1) is WSO(2powj+2, j+1,2j+3) with depth 2j+3 and fan out 2.

Rhank you very much.

regards,
ming

Is this your reaserch topic or homework ?

My Homework

Not unless you explain what "H" or "HD" or "WSO" or "[;g(n-1)]" are supposed to me.

H and HD=dept size optimal; WSO= Waist-Size Optimal, [;g(n-1)]= [lg(n-1)]