Regular Expressions for Irregular Rhythms

Houssam Abbas, Alëna Rodionova, Ezio Bartocci, Scott A. Smolka, Radu Grosu

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—where a peak in a cardiac signal indicates a heartbeat—and various discriminators used to distinguish fatal from non-fatal arrhythmias. Expressing these algorithms in current temporal logics is often cumbersome and computationally expensive. In contrast, we show that a range of peak detectors and discriminators 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.

Introduction

Implantable Cardioverter Defibrillators (ICDs) are life-critical devices that monitor heart rhythms to deliver life-saving shocks. Their operation relies on two distinct stages: Peak Detection (PD), which identifies heartbeats in electrical signals, and Discrimination, which analyzes the timing of those peaks to diagnose arrhythmias.

Currently, a significant gap exists between these two stages. Signal processing is typically implemented in low-level code, while decision logic is analyzed using temporal logics. This "fractured" approach makes formal verification difficult. Temporal logics often struggle with the numerical complexity of signal processing, leading to formulas that are unwieldy and error-prone. If an ICD misses a peak (under-sensing) or identifies a false one (over-sensing), the consequences can be fatal.

The QRE Framework

We propose using Quantitative Regular Expressions (QREs) as a unified language for both signal processing and decision logic. Unlike standard regular expressions that match simple patterns, QREs can perform numerical calculations—such as averaging or wavelet transforms—as they scan a data stream.

One of the primary advantages of QREs is their declarative nature. Instead of writing complex "if-then-else" code to manage state and memory, a developer describes the characteristics of a peak or a rhythm. The QRE compiler then automatically generates an efficient monitor with provable memory and runtime guarantees, which is essential for devices that must operate for years on a single battery.

Formalizing Detection and Discrimination

We translated several peak detection and discrimination strategies into QREs to demonstrate their succinctness and clarity. These include:

  • Wavelet Peaks with Maxima (WPM): A robust method that analyzes "maxima lines" across different scales of a wavelet transform to identify true signal singularities.
  • Time-Domain Detector (MDT): A formalization of a commercial peak detector currently used in real-world ICDs.
  • Discrimination Logic: QREs can easily express complex timing features like "sudden onset" or "average interval length" using simple, readable syntax.
QRE definitions for arrhythmia discrimination logic showing the succinctness of the language.

Experimental Evaluation

To evaluate the performance of QRE-based detectors, we utilized real patient electrograms (EGMs) containing various rhythms, including Normal Sinus Rhythm (NSR), Ventricular Tachycardia (VT), and Ventricular Fibrillation (VF). All signals were manually annotated by a professional cardiologist to establish a ground truth.

A cardiac signal (left) and its corresponding wavelet scalogram (right) used in the WPM detection method.

Our results indicate that the peakWPM QRE achieved perfect detection for VT rhythms, matching the cardiologist's annotations exactly. Furthermore, while the commercial-style MDT detector struggled with the high amplitude variability of disorganized VF signals, the wavelet-based QREs remained robust, successfully identifying peaks even in chaotic data.

Conclusion and Future Work

By providing a single formalism for the entire detection pipeline, QREs enable end-to-end formal analysis of medical device algorithms. This could significantly streamline the regulatory approval process for algorithm updates.

Future work will focus on developing a compiler to translate QREs directly into hardware-level code (C or assembly) to measure exact power consumption. Additionally, we aim to explore probabilistic analysis to estimate the likelihood of sensing errors and incorporate energy modeling to formally calculate the battery drain associated with different detection algorithms.

Summary updated

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 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 (where a peak in a cardiac signal indicates a heartbeat) and various discriminators, each of which uses a feature of the cardiac signal to distinguish fatal from non-fatal arrhythmias. Expressing these algorithms' desired output in current temporal logics, and implementing them via monitor synthesis, is cumbersome, error-prone, computationally expensive, and sometimes infeasible. In contrast, we show that a range of peak detectors (in both the time and wavelet domains) and various discriminators at the heart of today's arrhythmia-detection devices are easily expressible in QREs. The fact that one formalism (QREs) is used to describe the desired end-to-end operation of an arrhythmia detector opens the way to formal analysis and rigorous testing of these detectors' correctness and performance. Such analysis could alleviate the regulatory burden on device developers when modifying their algorithms. The performance of the peak-detection QREs is demonstrated by running them on real patient data, on which they yield results on par with those provided by a cardiologist.
BibTeX
@inproceedings{abbas2017regular,
  author = {Houssam Abbas and Alëna Rodionova and Ezio Bartocci and Scott A. Smolka and Radu Grosu},
  title = {{Regular Expressions for Irregular Rhythms}},
  booktitle = {CMSB},
  year = {2017},
  doi = {10.1007/978-3-319-67471-1\_2},
}
Figure