Revisiting Sorting Network Based Completion Detection for 4 Phase Delay Insensitive Codes

Completion detectors (CD) are key components in delay insensitive asynchronous circuit design. Their task is to check whether received data is complete and valid and to inform subsequent logic of this condition. Hence, it is very important to implement CDs in a resource-efficient way. One way to achieve this goal is to make use of binary sorting networks (SN). This work analyses and extends this approach. We show which constraints in form of timing assumptions are necessary if existing SN based solutions are used. Furthermore, modifications to the existing solutions are proposed to obtain quasi delay insensitive (QDI) circuits with minimum overheads. In particular, this work elaborates generic design templates for CDs for 4-phase m-of-n, incomplete m-of-n, Berger and Zero-Sum codes.