Comment on [Efst04]-8-31-double-se-web

Ghassem Jaberipur

Description

?44?I?;?:?4?;?-:?N;???4N????4;???4;??4:I4??N?4?4N??G???????:N)??4?I???)??????I???TN:?L?N??)? 1 nComment on “Fast Parallel Prefix Modulo 2 +1 Adder” Ghassem Jaberipur and Hanieh Alavi, ECE dept., Shahid Beheshti University Abstract— Costas Efstathiou et al present (IEEE Trans. Computers, Vol. 53, No. 9 pp. 1211-1216) an n-bit totally parallel prefix n(TPP) implementation of modulo 2 +1 adders with 62logJ latency in terms of unit gate delay. We locate a flaw in the logic equation for the most significant bit and present a simple counter example to prove this claim. We provide the relevant correct equation and its derivation details. We also show that it can be implemented within the TPP tree, without additional latency. Furthermore, despite the correctness of the equations for individual carry signals, we point out a missing parallel prefix operand in the corresponding general equation. In lack of any derivation or proof for the latter, we provide the relevant correct equation with derivation details. nIndex Terms— Binary adders, Modulo 2 +1 arithmetic, Parallel prefix adders, RNS. 1 INTRODUCTIONn n nHE moduli set {2 –1, 2 , 2 +1} is popular in the r : LI RI LO R? ?) , where is the 0 ?>5 ,5 ,5Tapplications of residue number system (RNS). carry-out of ...

Informations

• Publié par: Sonab
• Nombre de lectures: 63
• Langue: English

Extrait

n Comment on “Fast Parallel Prefix Modulo 2+1 Adder” Ghassem Jaberipur and Hanieh Alavi, ECE dept., Shahid Beheshti University Abstract—Costas Efstathiou et al present (IEEE Trans. Computers, Vol. 53, No. 9 pp. 1211-1216) ann-bit totally parallel prefix n (TPP) implementation of modulo 2 +1 adders with6 ൅ 2 log ݊latency in terms of unit gate delay. We locate a flaw in the logic equation for the most significant bit and present a simple counter example to prove this claim. We provide the relevant correct equation and its derivation details. We also show that it can be implemented within the TPP tree, without additional latency. Furthermore, despite the correctness of the equations for individual carry signals, we point out a missing parallel prefix operand in the corresponding general equation. In lack of any derivation or proof for the latter, we provide the relevant correct equation with derivation details. n Index Terms—Binary adders, Modulo 2 +1 arithmetic, Parallel prefix adders, RNS. 1 I NTRODUCTION n nn HE moduli set {2–1, 2, 2+1} is popular in ther 0 :ש ܩْ ܿ݉ ൌݏݎ ൌ݉ ْ, whereܩ isthe ଴ ଴௡ାଵ ଴௡ ௡,ଵ௡,ଵ T applications of residue number system (RNS).carry-out of positionnthe original computation of inM. n nn+1n Modular adders for the 2and 2–1 channels haveNote that sinceM≤no carry is generated in 2+2 –1 been reported vian-bit parallel prefix andn-bittotally thecomputation ofܿ ൅ܩ. Therefore,ש ܩ݉ ൌܿ. ௡ ௡,ଵ௡ାଵ ௡௡,ଵ parallel prefix (TPP) trees, with (3 ൅ 2 log ݊) latency in כ כ i≤n–1):ݎ ൌ݉ ْْ ܿܩ ൌݏ r i : (1≤ ௜ ௜௜ିଵ,ଵ ௜௜ିଵ ْ ܩ, ௜ିଵ,ଵ כ terms of unit gate delay [2]. Timing coordination within whereܩis the carry into positioniwithin the addition ௜ିଵ,ଵ n the three RNS channels calls for modulo 2 +1 adders with ݉ …݉ ൅ܿ שܩ. ௡ିଵ ଴௡ ௡,ଵ O (logn) latency. This has motivated the authors of [1] to כ ൌݏ ൅ܿ ൅݉ ൅ܩThis is simply sum of r n :ݎ ௡ ௡ ௡ିଵ௡ାଵ ௡ିଵ,ଵ . design such adders via a (logn)level TPP, where the the bits in positionnof Fig. 1. overall latency is6 ൅ 2 log ݊. Unfortunately however, TheS+C stageof Fig. 1 is trusted to a TPP tree, with there is a flaw in the logical equation for the most ܿ ൌܿש ܩ. However, there is flaw in the actual ௜௡ ௡௡,ଵ significant bit (MSB) of the sum that leads to wrong equation implemented in Fig. 3 of [1] forr n . results in several instances of the input operands. In this comment we underline the aforementioned flaw 2.1 The flaw in the computation ofr n via a counter example, provide the derivation details of n It is rightly stated in [1] thatr n  =1 ifA+B =2 . Then the the pertinent correct equation and its implementation authors, without providing any proof, conclude that within the same (logn)level TPP tree of [1] such that the ݎ ൌܿ רܲ רݏ, ௡ ௡௡ ଴ whereP n  isthe group propagate signal ሺ6൅2log݊ሻis preserved. Moreover, we offer the latency from position 1 ton. It is not difficult to prove that derivation details for Equation (4) of [1], where our ௡ ሺܣ ൅ ܤ ൌ2ሻ  impliesሺܿ רܲ רݏ ൌ1ሻ. However, the ௡ ௡ ଴ motive is twofold: First, this equation has a key role since ௡ converse (i.e.,ሻܲ רሺܿ רฺ ሺܣ ൅ ܤ ൌ2ݏ ൌ1ሻ) is not ௡ ௡ ଴ it computes all the TPP carries, while no derivation or always true. In fact it fails in 25% of the cases of input proof is given for it in [1]. Secondly, there is a missing data forn= 8. This claim is supported by exhaustive test parallel prefix operand, although all applications of this via VHDL simulation. However, Example 1 below clearly equation, forn= 8, are correct. demonstrates the flaw. Example 1 (Counter example for࢘ ൌࢉ ר࢙ࡼ ר): ܖ ࢔࢔ ૙ 2 T HE FLAW Consider an instance of Fig. 1, forn=4, as depicted in Fig. lead toൌ1ר ܲר ݏ. n 2, wherec 4  =0,s 0  =1, andP 4 1 =ܿ ௡ ௡ ଴ The modulo 2+1 addition scheme in [1] primarily ௡ However,R=|12+12| 17 =7, which leads tor 4 = 0.◄ computesܯ ൌܣ ൅ ܤ ൅ 2െ 1, whereA andB arethe n n+1-bit operands in [0, 2 ]. Equation (1), adapted from [1], A0 1 1 0 0= 12 defines ൅ ܤ| … ݎ ݎ ൌ|ܣ ܴ ൌݎ ݎ interms ofM, ೙ ௡ ௡ିଵଵ ଴ଶ ାଵ B0 1 1 0 0= 12 where |ܺ|  standsforX modulom andݔfor the stands 4 ௠ 2 –1 = 150 1 1 1 1 complement ofx. S1 1 1 1 0 ௡ ܴ ൌ|݉ ݉ …݉ ݉൅ ሺ2൅ 1ሻ݉ | ೙శభ  (1) ௡ ௡ିଵଵ ଴௡ାଵ ଶ C0 1 1 0 0 Fig. 1 depicts a typical computation of M (= S+C), where M1 0 0 1 1 1 s ൌa ْb,bc ൌa ש,۩bs ൌaandc ൌa רb. ୧ ୧୧ ୧୧ ୧୬ ୬୬ ୬୬ ୬ Fig. 2: An instance of Fig. 1 forn= 4 The correct equation, as will be derived in Section 3, is: A a n  a n1 …a 1  a 0 כ ݎ ൌሺܿ שݏ רܿ שሺݏ שܿ ሻר ܩሻ ْܩ (3) ௡ ௡௡ ௡ିଵ௡ ௡ିଵ௡ିଵ,ଵ ௡ିଵ,ଵ B b n  b n1 …b 1  b 0 The correctness of the latter is exhaustively tested via n 2 –10 1… 11 VHDL simulation forn8. =Besides the latter flaw, a S s n  s n1 …s 1  s 0 parallel prefix term ሺܿ ש ݃ , ݌ ሻ missing in the third is ௡ ௡௡ C c n  c n–1 …c 1  c 0 part of Equation (4) in [1]. The corrected Equation (4), as M m n+1  m n  m n1 …m 1  m 0 will be derived in the next section, is as follows, where Fig. 1: Computation ofM ԭሺܩ, ܲሻ ൌܩ : The computation ofRcan be analyzed as follows: כ ܩ ൌԭቆ൫ܩ ௜,ଵ , ܲ ௜,ଵ ൯ ל ݏ ଴ ൯ቇש ݃, ݌ ሻ ל ൫ܩ , ܲ ר ሺܿ (4) ௜,ଵ ௡௡ ௡௡ିଵ,௜ାଵ ௡ିଵ,௜ାଵ

1

3 T HE CORRECTED DESIGN Theγandπequations are justified as follows: ܿ שݏ רܿ ש ሺݏ שܿ ሻ ר ܩ ௡ ௡ ௡ିଵ௡ ௡ିଵ௡ିଵ,ଵ The corrected Equations (3) and (4) are derived below. ൌܽ רܾ ש ሺܽ שܾ ሻ ר ܽר ܾר ܿ ש ሺܽ ש ܾ ሻ ר ܽ ר ܾ ௡ ௡௡ ௡௡ ௡ ௡ିଵ௡ ௡௡ ௡ 3.1 Derivation of the most significant bitr ר ܩר ܩש ܿ n ௡ିଵ,ଵ ௡ିଵ௡ିଵ,ଵ ൌܽ רܾ ש ሺܽ שܾ ሻ ר ܿ ש ሺܽ ש ܾש ܿ ሻ ר ܩ Recalling the arithmetic equation forr n from Section 2 (i.e, ௡ ௡௡ ௡௡ିଵ ௡௡ ௡ିଵ௡ିଵ,ଵ כ ݎ ൌݏ ൅ܿ ൅݉ ൅ܩ), and݉ ൌܩש ܿ, the ௡ ௡ ௡ିଵ௡ାଵ ௡ିଵ,ଵ௡ାଵ ௡,ଵ௡ ൌܽ שܾ שܿ שܽ רܾ ש ሺܽ שܾ ሻ ר ܿר ܩ ௡ ௡ ௡ିଵ ௡ ௡௡ ௡௡ିଵ ௡ିଵ,ଵ MSBr n can be computed by the logical Equation (5). כ ݎ ൌݏ ْܿ ْ݉ ْܩ ൌ ൌԭ ቀሺγ, πሻ ל ሺܩ , ܲሻቁ ௡ ௡௡ିଵ ௡ାଵ ௡ିଵ,ଵ ௡ିଵ,ଵ ௡ିଵ,ଵ כ ሺሺݏ ْሺܩ שܿ ሻሻْ ܿሻ ۩ܩ(5) ௡ ௡,ଵ௡ ௡ିଵ ௡ିଵ,ଵ כ ݎ ൌԭ ቀሺγ, πሻ ל ሺܩ , ܲሻቁ ْܩ (6) ௡ ௡ିଵ,ଵ௡ିଵ,ଵ ௡ିଵ,ଵ Given thatܿ ൌ0ݏ ר,ܿൌݏרܿ,ܩ ൌ݃ש ݌ר ܩ, ௡ ௡௡ ௡௡ ௡,ଵ௡ ௡ ௡ିଵ,ଵ כ The prefix node that could computeܩthe last in ௡ିଵ,ଵ ݃ ൌܿݏ ר, andܿ݌ ൌݏ ש, the inner ௡ ௡௡ିଵ ௡௡ ௡ିଵ row and columnn–1 of the TPP tree is missing in Fig. 3 of parenthesized XOR equation can be simplified as follows: [1]. This and the path leading tor 8 , defined by Equation ݏ ْ൫ܩ שܿ ൯ൌሺݏ שܿ שܩ ሻר ݏר ܩש ݏר ܿ ௡ ௡,ଵ௡ ௡௡ ௡,ଵ௡ ௡,ଵ௡ ௡ (7),are now added in the new Fig. 3 below. כ ൌݏ רܩ שݏ רܩ שܿ רݏ שܿ רܩ ௡ ௡,ଵ௡ ௡,ଵ௡ ௡ ௡௡,ଵ , ݌ ቀሺγ, πሻ ל ሺ݃ , ݌ ሻ ל … ሺ݃ ݎ ൌԭሻቁ ْܩ (7) ଼ ଻଻ ଵଵ ଻,ଵ ൌܿ שݏ רܩ שݏ רܩ ൌר ݃ש ݌ר ܩש ݏ ௡ ௡௡,ଵ ௡௡,ଵ ܿ ௡ ש ݏ ௡௡ ௡ ௡ ௡ିଵ,ଵ The latency ofγ andπ is2 and 3 unit gate delay. Therefore, the prefix operand (γ,π) is ready as soon as all ר ൫݃ש ݌ר ܩ൯ ൌܿש ݏר ݃ר ൫݌ש ܩ൯ ש ݏר ௡ ௡ ௡ିଵ,ଵ௡ ௡௡ ௡௡ିଵ,ଵ ௡ other prefix operands are. This leads to availability ofr n at ݏ רܿ שݏ ר ሺݏ שܿ ሻ ר ܩ ௡ ௡ିଵ ௡௡ ௡ିଵ௡ିଵ,ଵ time5 ൅ 2 log ݊in terms of unit gate delay. ൌܿ שݏ ר ሺݏ שܿ ሻ ר ൫ݏר ܿש ܩ൯ ש ݏר ܿ ௡ ௡௡ ௡ିଵ௡ ௡ିଵ௡ିଵ,ଵ ௡௡ିଵ b 8 a 8 b 7 a 7 b 6 a 6 b 5 a 5 4 4 3 3 2 2 b 1 a 1 b a b a b a b a ר ܩൌܿ שݏ רܿ רܩ שݏ רܿ רܩ 0 0 ௡ିଵ,ଵ ௡௡ ௡ିଵ௡ିଵ,ଵ ௡ ௡ିଵ௡ିଵ,ଵ Given thatൌcc֜1ൌ0֜רcൌcc, the outer ୬ ୬ିଵ୬ ୬ିଵ୬ c s 8 c c s 4 c 3 2 s c c c c 8 7 7 6 6 5 5 3 1 1 c 0 0 parenthesized XOR equation within Equation (5) can now be simplified as follows: ൫ܿ שݏ רܿ רܩ שݏ רܿ רܩ ൯ْ ܿ ( γ,π ) ( g∨c,p ) 5 5 4 4 ( T 1 ,g 1 ) g,p ( g,p ) ( ) ௡ ௡ ௡ିଵ௡ିଵ,ଵ ௡ ௡ିଵ௡ିଵ,ଵ ௡ିଵ 8 88 , ( ,p ) 3 3 ( ) ( t,g ) g pg 7 7 6 6 t,g ) 2 2 ൌ൫ܿ שݏ רܿ רܩ שݏ רܿ רܩ שܿ ൯ ௡ ௡ ௡ିଵ௡ିଵ,ଵ ௡ ௡ିଵ௡ିଵ,ଵ ௡ିଵ ר ൫ܿש ݏר ܿר ܩש ݏר ܿר ܩ൯ ר ܿ ௡ ௡ ௡ିଵ௡ିଵ,ଵ ௡ ௡ିଵ௡ିଵ,ଵ ௡ିଵ ൌ൫ܿ שݏ רܩ שܿ ൯ר ቀܿר ܿש ݏר ܿר ܩ ቁ ௡ ௡௡ିଵ,ଵ ௡ିଵ௡ ௡ିଵ ௡ ௡ିଵ௡ିଵ,ଵ ൌܩ שݏ רܿܿ שܿ רܩ שݏ רܿ רݏ שܿ ר ௡ ௡ ௡ ௡ିଵ ௡௡ିଵ,ଵ ௡௡ିଵ,ଵ ௡ ௡ିଵ ∗ ∗ ∗ ∗ ∗ ∗ ש ܿר ܩൌܿ שݏ רܿ שሺݏ שܿ ሻר ܩ c * c c c 4 c 3 c 1 6 ௡ିଵ ௡ିଵ,ଵ ௡௡ ௡ିଵ௡ ௡ିଵ௡ିଵ,ଵ c −1 ∗ c 7 ∗ It only remains to apply the latter into Equation (5) that c 0 h h s 5 4 h 0 h 7 h 3 h 2 h 1 6 leads to the desired Equation (3). Direct implementation r r r 7 r 5 r 4 r r r r of this equation leads to the overall latency of7 ൅ 2 log ݊. 8 6 3 2 1 0 n Fig. 3: The corrected modulo 2 +1 TPP adder כ 3.2 Derivation ofࡳ(1≤i≤n–2) ࢏,૚ כ כ ܩ ൌܩ שܲ רܩ ൌܩש ܲר ሺݏר ܿש ݃ש ݌ܩ ሻ ௜,ଵ ௜,ଵ௜,ଵ ଴௜,ଵ ௜,ଵ଴ ௡௡ ௡௡ିଵ,ଵ R EFERENCES ൌܩ שܲ רݏ רܿ ש݃ ר൫݌ שܩ שܲ רܩ ൯ ௜,ଵ ௜,ଵ ଴ ௡ ௡௡ ௡ିଵ,௜ାଵ௡ିଵ,௜ାଵ ௜,ଵ n [1]Efstathiou C., H. T. Vergos, and D. Nikolos, “Fast Parallel-Prefix 2 +1 ൌܩ שሺܲ רݏ רܿ ר݃ ר݌ ሻש ሺܲר ݏר ܿש ݃ ௜,ଵ ௜,ଵ଴ ௡௡ ௡௜,ଵ ଴ ௡௡ Adder”, IEEE Trans. on Computers, Vol. 53, No. 9, pp. 1211–1216, Sep- ר ܩר ܲሻ ש ൫ܲר ݏר ܿש ݃ר ܩר ܩ ൯ tember 2004. ௡ିଵ,௜ାଵ ௡ିଵ,௜ାଵ௜,ଵ ଴ ௡௡ ௡ିଵ,௜ାଵ ௜,ଵ n [2]Kalamatianos, “High-Speed Parallel-Prefix Modulo 2 –1 Adders,” IEEE ൌܩ שሺܲ רݏ רܿ ר݌ ሻש ܲר ݏר ܿש ݃ר ܩ ௜,ଵ ௜,ଵ଴ ௡ ௡௜,ଵ ଴ ௡௡ ௡ିଵ,௜ାଵ Trans. Computers, Vol. 49, No. 7, special issue on computer arithmetic, ൌܩ שܲ רݏ ר൫ܿ ש݌ שܿ ש݃ רܩ ሻ൯ ௜,ଵ ௜,ଵ ଴௡ ௡ ௡ ௡ ௡ିଵ,௜ାଵ pp. 673-680, July 2000. n ൌܩ שܲ רݏ ר ሺܿ ש݌ ሻሺܿ ש ݃ש ܩሻ [3]Vergos H.T. and C. Efstathiou, "Novel Modulo 2 +1 Multipliers", Proc. ௜,ଵ ௜,ଵ ଴௡ ௡௡ ௡ ௡ିଵ,௜ାଵ of the 9th EUROMICRO Conference on Digital system Design, Du- ൌܩ שܲ רݏ רܿ ש݃ ש݌ רܩ ௜,ଵ ௜,ଵ ଴ ௡ ௡ ௡ ௡ିଵ,௜ାଵ brovnik, pp.168-175, 2006. ൌԭሺሺܩ ,ܲ ሻל ݏ ר ሺܿ ש ݃, ݌ ሻ ל ሺܩ , ܲሻሻ ௜,ଵ ௜,ଵ଴ ௡௡ ௡௡ିଵ,௜ାଵ ௡ିଵ,௜ାଵ Given the above carry signals, which are computable via a TPP tree exactly as in [1], the final sum bitsr i  canbe computed as follows: כ כ ݎ ൌ݄ ْܩ ൌݏْ ْܿ ܩ (1≤i≤n– 1) ௜ ௜ ௜ିଵ,ଵ௜ ௜ିଵ ௜ିଵ,ଵ

3.3 Implementation of࢘within the TPP tree ࢔ The left operand of the XOR in Equation (3) can be represented as a prefix equation and implemented within the TPP tree as in Equation (6) and Fig. 3, where γ ൌܽש ܾש ܿ andπ ൌܽר ܾש ሺܽሻ ר ܿש ܾ. ௡ ௡ ௡ିଵ௡ ௡௡ ௡௡ିଵ