Campus Event Calendar
Event Entry
What and Who
Optimal Metastability-Containing Sorting Networks
Johannes Bund
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 14 May 2019
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Friedrichs et al. (TC 2018) showed that metastability can be contained when sorting inputs arising from time-to-digital
converters, i.e., measurement values can be correctly sorted without resolving metastability using synchronizers first. However, this
work left open whether this can be done by small circuits. We show that this is indeed possible, by providing a circuit that sorts Gray
code inputs (possibly containing a metastable bit) and has asymptotically optimal depth and size. Our solution utilizes the parallel prefix computation (PPC) framework (JACM 1980).
Contact
Johannes Bund
--email hidden
passcode not visible
logged in users only
Johannes Bund, 05/08/2019 15:43 -- Created document.