  This PhD dissertation investigates garbage-free reversible computing systems
from abstract design to physical gate-level implementation. Designed in
reversible logic, we propose a ripple-block carry adder and work towards a
reversible circuit for general multiplication. At a higher-level, abstract
designs are proposed for reversible systems, such as a small von Neumann
architecture that can execute programs written in a simple reversible
two-address instruction set, a novel reversible arithmetic logic unit, and a
linear cosine transform. To aid the design of reversible logic circuits we have
designed two reversible functional hardware description languages: a
linear-typed higher-level language and a gate-level point-free combinator
language. We suggest a garbage-free design flow, where circuits are described
in the higher-level language and then translated to the combinator language,
from which methods to place-and-route of CMOS gates can be applied. We have
also made standard cell layouts of the reversible gates in complementary
pass-gate CMOS logic and used these to fabricate the ALU design. In total, this
dissertation has shown that it is possible to design non-trivial reversible
computing systems without garbage and that support from languages (computer
aided design) can make this process easier.
