EUVIMEDEUVIMED entdecken
Crossref

Formal verification of multiplier circuits using computer algebra

Daniela Kaufmann

it - Information Technology · 16.12.2022 · 64 (6) · 285-291

DOI: 10.1515/itit-2022-0039 ↗

Kurz gefasst

Fachartikel in der Zeitschrift it - Information Technology, online erschienen am 24.06.2022. Verfasst von Daniela Kaufmann. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 30 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Digital circuits are widely utilized in computers, because they provide models for various digital components and arithmetic operations. Arithmetic circuits are a subclass of digital circuits that are used to execute Boolean algebra. To avoid problems like the infamous Pentium FDIV bug, it is critical to ensure that arithmetic circuits are correct. Formal verification can be used to determine the correctness of a circuit with respect to a certain specification. However, arithmetic circuits, particularly integer multipliers, represent a challenge to current verification methodologies and, in reality, still necessitate a significant amount of manual labor. In my dissertation we examine and develop automated reasoning approaches based on computer algebra, where the word-level specification, modeled as a polynomial, is reduced by a Gröbner basis inferred by the gate-level representation of the circuit. We provide a precise formalization of this reasoning process, which includes soundness and completeness arguments and adds to the mathematical background in this field. On the practical side we present an unique incremental column-wise verification algorithm and preprocessing approaches based on variable elimination that simplify the inferred Gröbner basis. Furthermore, we provide an algebraic proof calculus in this thesis that allows obtaining certificates as a by-product of circuit verification in order to boost confidence in the outcomes of automated reasoning tools. These certificates can be efficiently verified with independent proof checking tools.

Zitieren

APA

Kaufmann, D. (2022). Formal verification of multiplier circuits using computer algebra. it - Information Technology, 64(6), 285-291. https://doi.org/10.1515/itit-2022-0039

Vancouver

Kaufmann D. Formal verification of multiplier circuits using computer algebra. it - Information Technology. 2022;64(6):285-291. doi:10.1515/itit-2022-0039

BibTeX
@article{Kaufmann2022,
  author = {Kaufmann, Daniela},
  title = {Formal verification of multiplier circuits using computer algebra},
  journal = {it - Information Technology},
  year = {2022},
  volume = {64},
  number = {6},
  pages = {285--291},
  doi = {10.1515/itit-2022-0039}
}
Kostenlos starten →