Computational complexity of sequential sequence estimation for intersymbol interference channels

Author

Xiong, Fuqin ; Dai, Quingyuan ; Shwedyk, Edward

Author_Institution

Manitoba Univ., Winnipeg, Man., Canada

Volume

41

Issue

2

fYear

1993

fDate

2/1/1993 12:00:00 AM

Firstpage

332

Lastpage

337

Abstract

The computational complexity of a sequential algorithm (SA) developed for intersymbol interference (ISI) channels is analyzed. To determine the computational complexity, the finite-state machine that models the channel and white matched filter system, of which the SA is a part, is interpreted as a special convolutional encoder followed by a binary symbol to Q-ary symbol mapping. It follows that the computational distribution is Pareto, and that there exists a computational cutoff rate R_comp. For the uncoded data considered, the rate is fixed and the R_comp criterion translates into a signal-to-noise ratio (SNR) criterion. An upper bound on SNR_comp is found analytically by assuming a uniform input distribution. Iteration equations developed by S. Arimoto (1976) are adapted to find the true SNR_comp numerically

Keywords

computational complexity; convolutional codes; encoding; finite state machines; intersymbol interference; matched filters; telecommunication channels; ISI; Pareto distribution; binary symbol to Q-ary symbol mapping; computational complexity; computational cutoff rate; convolutional encoder; finite-state machine; intersymbol interference channels; iteration equations; sequential algorithm; sequential sequence estimation; signal-to-noise ratio; upper bound; white matched filter; Computational complexity; Convolution; Distributed computing; Equations; Gaussian noise; Intersymbol interference; Matched filters; Pareto analysis; Signal to noise ratio; Upper bound;

fLanguage

English

Journal_Title

Communications, IEEE Transactions on

Publisher

ieee

ISSN

0090-6778

Type

jour

DOI

10.1109/26.216508

Filename

216508