Fault Tolerant Non-regular Digital Signal Processing Based on Computation Tree Block Decomposition

Mineo KANEKO  Hiroyuki MIYAUCHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.9   pp.1535-1545
Publication Date: 1994/09/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Digital Signal Processing
fault tolerance,  on-line error correction,  signal flow graph,  DSP algorithm,  

Full Text: PDF(955.2KB)>>
Buy this Article

In this paper, we present Branching Oriented System Equation based on-line error correction scheme for recursive digital signal processing. The target digital signal processing is linear and time-invariant, and the algorithm includes multiplications with constant coefficient, additions and delays. The difficulties of the algorithm-level fault tolerance for such algorithm without structural regularity include error distribution problem and right timing of error correction. To escape the error distribution problem, multiple fan-out nodes in an algorithm are specified as the nodes at which error corrections are performed. The Branching Oriented Graph and Branching Oriented System Equation are so introduced to formulate on-line correction schemes based on this strategy. The Branching Oriented Graph is treated as the collection of computation sub-blocks. Applying checksum code independently to each sub-block is our most trivial on-line error correction scheme, and it results in, with appropriate selection of error identification process, TMR in sub-block level. One of the advantages of our method is in the reduction of redundant operations performed by merging some computation sub-blocks. On the other hand, the schedulability of the system is an important issue for our method since our on-line error correction mechanism induces additional data dependencies. In this paper, the schedulability condition and some modifications on the scheme are also discussed.