Improved techniques for estimating signal probabilities

The problem is presented in the context of some recent theoretical advances on a related problem, called random satisfiability. These recent results indicate the theoretical limitations inherent in the problem of computing signal probabilities. Such limitations exist even if one uses Monte Carlo tec...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1989-07, Vol.38 (7), p.1041-1045
Main Authors: Krishnamurthy, B., Tollis, I.G.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Built-in self-test
Computer networks
Fault detection
Laboratories
Monte Carlo methods
Pattern analysis
Signal analysis
Signal design
System testing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem is presented in the context of some recent theoretical advances on a related problem, called random satisfiability. These recent results indicate the theoretical limitations inherent in the problem of computing signal probabilities. Such limitations exist even if one uses Monte Carlo techniques for estimating signal probabilities. Theoretical results indicate that any practical method devised to compute signal probabilities would have to be evaluated purely on an empirical basis. An improved algorithm is offered for estimating the signal probabilities that takes into account the first-order effects of reconvergent input leads. It is demonstrated that this algorithm is linear in the product of the size of the network and the number of inputs. Empirical evidence is given indicating the improved performance obtained using this method over the straightforward probability computations. The results are very good, and the algorithm is very fast and easy to implement.< >
ISSN:0018-9340
1557-9956
DOI:10.1109/12.30854