ePrints

Correctness of dataflow and systolic algorithms using algebras of streams

Lookup NU author(s): Dr Jason Steggles

Downloads

Full text for this publication is not currently held within this repository. Alternative links are provided below where available.

Abstract

We present two case studies which illustrate the use of second-order algebra as a formalism for specification and verification of hardware algorithms. In the first case study we specify a systolic algorithm for convolution and formally verify its correctness using second-order equational logic. The second case study demonstrates the expressive power of second-order algebraic specifications by presenting a non-constructive specification of the Hamming stream problem. A dataflow algorithm for computing the Hamming stream is then specified and the correctness of this algorithm is verified by semantical methods. Both case studies illustrate aspects of the metatheory of second-order equational logic.

Publication metadata

Author(s): Meinke K, Steggles LJ

Publication type: Article

Publication status: Published

Journal: Acta Informatica

Year: 2001

Volume: 38

Issue: 1

Pages: 45-88

ISSN (print): 0001-5903

ISSN (electronic): 1432-0525

Publisher: Springer

URL: http://dx.doi.org/10.1007/PL00013322

DOI: 10.1007/PL00013322

Altmetrics

Share