Computational Complexity of Error Metrics in Approximate Computing

Article in Edited Volumes
(Book chapter)

Publication Details

Author(s): Keszöcze O, Soeken M, Drechsler R
Editor(s): Bernd Steinbach
Title edited volumes: Further Improvements in the Boolean Domain
Publication year: 2018
Pages range: Cambridge Scholars Publishing
ISBN: 978-1-5275-0371-7
Language: English


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 Authors / FAU Editors

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

External institutions with authors

École Polytechnique Fédérale de Lausanne (EPFL)
Universität Bremen

How to cite

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).

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.


Last updated on 2019-23-07 at 07:31