A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train

The problem of a posteriori joint detecting and discriminating pulses in a quasiperiodic pulse train is studied. By the quasiperiodic pulse train, we mean any pulse train in which the time lapse between the beginning instants of two consecutive pulses varies over time within a certain fixed interval. We consider the kind of quasiperiodic pulse train in which the beginning instants of pulses are deterministic (nonrandom). We analyze the case when all pulses in a pulse train belong to an alphabet of reference pulses having identical duration. It is assumed that the observed interval of the pulse train contains the complete pulses (no parts of pulses are missing at the observation) and that the unobservable pulse train is distorted by an additive white Gaussian noise. Up until this time, there has been no exact algorithm to solve this a posteriori problem under these very simple assumptions because of enormous combinatorial complexity. We derive and prove an efficient (polynomial) computing algorithm for the exact solution to this problem. The recursive equations for step-by step discrete optimization are obtained under the maximum-likelihood criterion. The same formulas hold under the least-squares criterion. The computational load of the algorithm is evaluated, and its dependency on the parameters of the problem is proven.

I. Introduction

Many physical processes found in real applications can be interpreted as a pulse process. Pulse signals, pulse sequences, or pulse trains are used as a model of the process in such applications as electronic warfare [1], radar [2], communications [3], geophysics [4], speech processing [5], medical and engineering diagnostics [6], [7], and others. Appropriate processing and analysis of pulse trains is the relevant problem for these applications. By analyzing pulse repetition interval, arrival time, or shape of pulses, one can get useful information about properties of a target, jamming signal, seismic source, minerals, voice, fault type of some equipment, a state of patient, etc. For example, changes in patient state are often indicated by well-known correlated changes of pulse shape in electro-cardiograms (ECGs) and electro-encephalograms (EEGs).