Results 1 to 1 of 1

Thread: Find Something wrong on a Theorem

  1. #1 Find Something wrong on a Theorem 
    New Member
    Join Date
    Nov 2008
    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.

    Thank you very much.


    Reply With Quote  


Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts