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.