Abstract
Motivated by the problem of verifying the correctness of arrhythmia-detection algorithms, we present a formalization of these algorithms in the language of Quantitative Regular Expressions (QREs). QREs are a flexible formal language for specifying complex numerical queries over data streams, with provable runtime and memory consumption guarantees. The medical-device algorithms of interest include peak detection and various discriminators used to distinguish fatal from non-fatal arrhythmias. We show that a range of peak detectors and discriminators at the heart of today's arrhythmia-detection devices are easily expressible in QREs. This unified formalism opens the way to formal analysis and rigorous testing, potentially alleviating the regulatory burden on device developers. The performance of the QRE-based detectors is demonstrated on real patient data, yielding results on par with those provided by a cardiologist.
Introduction
Implantable Cardioverter Defibrillators (ICDs) are life-saving medical devices that monitor heart rhythms to detect and treat fatal arrhythmias. The reliability of these devices depends on the seamless integration of high-speed signal processing and complex decision logic. However, verifying the correctness of these algorithms is a significant challenge due to the limitations of existing formal methods when applied to numerical data streams.
The Challenge of Medical Device Verification
Modern ICD algorithms perform two critical tasks: peak detection (identifying individual heartbeats) and discrimination (distinguishing fatal arrhythmias like Ventricular Fibrillation from harmless fast heart rates). Historically, engineers have attempted to use temporal logics such as Signal Temporal Logic (STL) or Linear Temporal Logic (LTL) to specify these requirements. However, these logics struggle with the heavy numerical lifting required for signal processing, such as calculating moving averages or performing wavelet transforms. This "fracturing of formalisms"—using different tools for different parts of the pipeline—makes end-to-end safety verification nearly impossible.
Quantitative Regular Expressions (QREs)
We propose Quantitative Regular Expressions (QREs) as a "one-stop shop" for both signal processing and decision logic. QREs extend standard regular expressions by allowing them to match patterns in data streams while simultaneously performing numerical computations, or "costs."
A key advantage of QREs is the "split-op" combinator, which enables developers to break a signal into discrete windows, perform mathematical operations, and pass the results to subsequent stages without manual state management. This declarative approach reduces the surface area for bugs compared to traditional imperative programming.
Implementation and Results
The researchers implemented three distinct peak detectors using QREs: the Wavelet Peaks with Maxima (WPM), the Wavelet Peaks with Blanking (WPB), and a formalization of a commercial time-domain detector (MDT). These were evaluated using real patient intra-cardiac electrograms (EGMs) annotated by expert cardiologists.
The QRE-based WPM detector achieved perfect detection on patient data, matching cardiologist-level accuracy. Furthermore, it demonstrated superior precision compared to the commercial MDT detector, particularly in disorganized signals like Ventricular Fibrillation, where the MDT often produced false positives (over-sensing). Complex discriminators that required unwieldy formulas in temporal logic were expressed clearly and concisely in just a few lines of QRE code.
Conclusion and Future Work
QREs provide a unified, expressive, and efficient framework for formalizing arrhythmia detection. By bridging the gap between signal processing and high-level logic, they enable more rigorous testing and formal analysis of medical device software. Future work will focus on compiling QREs into highly optimized code for low-power microcontrollers and conducting detailed energy consumption analyses to ensure suitability for battery-powered implants.
Summary updated