Indicating combinational logic decomposition

Access Full Text

Indicating combinational logic decomposition

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

Self-timed circuits present an attractive solution to the problem of process variation. However, implementing self-timed combinational logic is complex and expensive. As there are no external timing references, data must be encoded within an unordered (DI) encoding and the outputs of functions must indicate to the environment that transitions on inputs and internal signals have taken place. Mapping large function blocks into cell-libraries is extremely difficult as decomposing gates introduces new signals which may violate indication. This study presents a novel method for implementing any m-of-n-encoded function block using ‘bounded gates’, where any gate may be decomposed without violating indication. This is achieved by successively decomposing the input encoding into smaller unordered codes. The study presents algorithms to determine and quantify potential re-encodings. An exact branch and bound approach to the solution is shown, but the complexity of determining unordered encodings restricts the size of function blocks that may be decomposed. To overcome this problem, an approach has been proposed that uses algebraic extraction techniques to efficiently determine and quantify potential encodings. The results of the synthesis procedures are demonstrated on a range of combinational function blocks.

Inspec keywords: algebra; combinational circuits; tree searching

Other keywords: combinational function blocks; combinational logic decomposition; bounded gates; branch and bound approach; m-of-n-encoded function block; self-timed circuits; algebraic extraction; self-timed combinational logic; unordered encoding

Subjects: Algebra; Logic circuits; Algebra; Combinatorial mathematics; Combinatorial mathematics; Logic and switching circuits

References

    1. 1)
      • Chelcea, T., Venkataramani, G., Goldstein, S.C.: `Area optimizations for dual-rail circuits using relative-timing analysis', Proc. Int. Symp. on Asynchronous Circuits and Systems, March 2007, Berkeley, USA, p. 117–128.
    2. 2)
      • V.I. Varshavsky . (1990) Self-timed control of concurrent processes: the design of aperiodic logical circuits in computers and discrete systems.
    3. 3)
      • K. Fant . (2005) Logically determined design.
    4. 4)
      • Zhou, Y., Sokolov, D., Yakovlev, A.: `Cost-aware synthesis of asynchronous circuits based on partial acknowledgement', Proc. Int. Conf. Computer-Aided Design, November 2006, San Jose, USA, p. 158–163.
    5. 5)
      • Jeong, C., Nowick, S.M.: `Optimization of robust asynchronous circuits by local input completeness relaxation', Proc. Asia South-Pacific Design Automation Conf., January 2007, Yokohama, Japan, p. 622–627.
    6. 6)
    7. 7)
      • Jeong, C., Nowick, S.M.: `Block-level relaxation for timing-robust asynchronous circuits based on eager evaluation', Proc. Int. Symp. on Asynchronous Circuits and Systems, April 2008, Newcastle, UK, p. 95–104.
    8. 8)
    9. 9)
      • Cortadella, J., Kondratyev, A., Lavagno, L., Sotiriou, C.: `Coping with the variability of combinational logic delays', Proc. Int. Conf. Computer Design, October 2004, San Jose, USA, p. 505–508.
    10. 10)
      • Burns, S.M.: `General conditions for the decomposition of state-holding elements', Proc. Int. Symp. on Asynchronous Circuits and Systems, March 1996, Fukushima, Japan, p. 48–57.
    11. 11)
      • Brayton, R.K., McMullen, C.T.: `The decomposition and factorization of boolean expressions', Proc. Int. Symp. on Circuits and Systems, May 1982, Rome, Italy, p. 49–54.
    12. 12)
      • Toms, W.B., Edwards, D.A.: `Prime indicants: a synthesis method for combinational logic blocks', Proc. Int. Symp. on Asynchronous Circuits and Systems, May 2009, Chapel Hill, USA, p. 139–150.
    13. 13)
      • Toms, W.B., Edwards, D.A.: `A complete synthesis method for block-level relaxation in self-timed datapaths', Proc. Int. Conf. on Application of Concurrency to System Design, June 2010, Braga, Portugal, p. 24–34.
    14. 14)
      • Toms, W.B., Edwards, D.A.: `M-of-N code decomposition for indicating combinational logic', Proc. Int. Symp. on Asynchronous Circuits and Systems, May 2010, Grenoble, France, p. 15–25.
    15. 15)
    16. 16)
      • Kondratyev, A., Lwin, K.: `Design of asynchronous circuits by synchronous CAD tools', Proc. Design Automation Conf., June 2002, San Diego, USA, p. 411–414.
    17. 17)
      • C. Seitz , C.A. Mead , L.A. Conway . (1980) System timing, Introduction to VLSI systems.
    18. 18)
      • Martin, A.J.: `The limitations to delay-insensitivity in asynchronous circuits', Proc. Advanced Research in VLSI, 1990, p. 263–278.
    19. 19)
      • Rudell, R.L.: `Logic synthesis for VLSI design', 1989, PhD, University of California at Berkeley.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2010.0107
Loading

Related content

content/journals/10.1049/iet-cdt.2010.0107
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading