Kuwait Journal of Science

Previous Issues

Advance Search
Year : From To Vol
Issue Discipline:

Volume :36 Issue : 2 2009      Add To Cart                                                                    Download

Parity-based concurrent error detection with bounded latency in finite state machines


*Computer Engineering Department, Kuwait University, Kuwait

E-mail: sobeeh.almukhaizim@ku.edu.kw

**Department of Computer Science, Rensselaer Polytechnic Institute, USA,

E-mail: drinep@cs.rpi.edu

***Departments of Electrical Engineering and Computer Science, Yale University, USA,

E-mail: yiorgos.makris@yale.edu




We extend a previously-developed non-intrusive concurrent error detection (CED) method for finite state machines (FSMs) to perform CED with bounded latency. The proposed method is based on compaction of the state/output bits of the FSM via parity trees and comparison to the error-free compacted responses, which are predicted through additional hardware. The corresponding optimization problem is formulated as an integer linear program and an algorithm to approximate its optimal solution through the use of linear program relaxation and randomized rounding is outlined. In order to reduce the incurred area overhead, we approximate the entropy of parity trees required for performing lossless compaction, and we select low-entropy ones. We then extend this method to support CED with bounded latency, wherein the overhead is further reduced at the cost of introducing a small latency in the detection of errors. Experimental results demonstrate that allowing a small bounded latency in the detection of errors yields further reduction in the parity predictor hardware overhead.


Keywords: Concurrent Error Detection, Finite State Machines, Integer Programming, On-Line Test, Parity


Kuwait Journal of Science
Journal of Law

You are Visitor No.


Journal of Law
Journal of Law
Tell your friendsJournal of Law
Journal of Law

Last Updated

Jun 19, 2012

Journal of Law
Journal of Law
Journal of Law

Please enter your email Here to receive our news

Journal of Law