Indicating combinational logic decomposition

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. © 2011 The Institution of Engineering and Technology.