With the emergence of wearable and non-intrusive med- ical devices, one major challenge is the real-time analysis of the acquired signals in real-life and ambulatory con- ditions. This paper presents a lightweight algorithm for on-line heart beat classification and correction that relies on a probabilistic model to determine whether a heart beat is likely to happen under certain timing conditions or not. It can quickly decide if a beat is occurring at an expected time or if there is a problem in the series (e.g., a skipped, an extra or a misplaced beat). If an error is detected, the series is repaired accordingly. The algorithm has been carefully optimized to minimize the required processing power and memory usage in order to enable its real-time embedded implementation on a wearable sensing device. Our experimental results, based on the PhysioNet Fanta- sia database, show that the proposed algorithm achieves 99.5% sensitivity in the detection and correction of erro- neous beats. In addition, it features a fast response time when the activity level of the user changes, thus enabling its use in situations where the heart rate quickly changes.