Computational Complexity of Error Metrics in Approximate Computing

Beitrag in einem Sammelwerk
(Buchkapitel)


Details zur Publikation

Autor(en): Keszöcze O, Soeken M, Drechsler R
Herausgeber: Bernd Steinbach
Titel Sammelwerk: Further Improvements in the Boolean Domain
Jahr der Veröffentlichung: 2018
Seitenbereich: Cambridge Scholars Publishing
ISBN: 978-1-5275-0371-7
Sprache: Englisch


Abstract

The amount of digital systems supporting our daily life is increasing
continuously. Improved technical facilities for their production have
led to growing challenges for engineers and scientists working in the
Boolean domain. A Boolean variable can only carry two different Boolean
values: FALSE or TRUE (0 or 1), and has the best interference resistance
in technical systems. However, a Boolean function exponentially depends
on the number of its variables. This exponential complexity is the
reason for major problems in the process of design and realization of
circuits. According to Moore’s Law, the complexity of digital systems
approximately doubles every 18 months. This requires comprehensive
knowledge and techniques to solve very complex Boolean problems. This
volume represents the third book in a series that provides further
insights into the Boolean domain.

Part 1 explores powerful
models, methods and techniques which improve the efficiency in solving
Boolean problems of extreme complexity. The universality of Boolean
equations as a model to solve Non-deterministic Polynomial-time (NP)
hard problems, as well as special properties of index generation
functions, spectral techniques, or relational approaches, is discussed
here. Both hardware devices, such as Field Programmable Gate Arrays
(FPGAs) or Graphics Processing Units (GPUs), and optimized algorithms
realized in software contribute to the acceleration of Boolean
calculations. Part 2 contributes to the synthesis and visualization of
digital circuits, and provides interesting new solutions for several
types of circuits. A comprehensive collection of benchmarks supports the
evolution of both existing and new synthesis approaches. The continuous
reduction of the size of the transistors increases the challenges with
regard to the reliability of the circuits. Part 3 describes several new
approaches for the synthesis of reversible circuits. These approaches,
as well as a classification of reversible functions, extend the basis of
future quantum computers.


FAU-Autoren / FAU-Herausgeber

Keszöcze, Oliver Prof. Dr.
Juniorprofessur für Informatik


Autor(en) der externen Einrichtung(en)
École Polytechnique Fédérale de Lausanne (EPFL)
Universität Bremen


Zitierweisen

APA:
Keszöcze, O., Soeken, M., & Drechsler, R. (2018). Computational Complexity of Error Metrics in Approximate Computing. In Bernd Steinbach (Eds.), Further Improvements in the Boolean Domain (pp. Cambridge Scholars Publishing).

MLA:
Keszöcze, Oliver, Mathias Soeken, and Rolf Drechsler. "Computational Complexity of Error Metrics in Approximate Computing." Further Improvements in the Boolean Domain Ed. Bernd Steinbach, 2018. Cambridge Scholars Publishing.

BibTeX: 

Zuletzt aktualisiert 2018-28-09 um 13:53