An upper bound on the distribution of computation of a sequential decoder for multiple-access channels

Author

Balakirsky, Vladimir B.

Author_Institution

Dept. of Inf. Theory, Lund Univ., Sweden

Volume

42

Issue

2

fYear

1996

fDate

3/1/1996 12:00:00 AM

Firstpage

399

Lastpage

408

Abstract

The computational distribution of sequential decoding for discrete memoryless multiple-access channels is examined. It is shown that all possible collections of incorrect paths in the code tree may be described by bipartite graphs. Using this fact and a new decoding metric it is proved that the number of computations in the first incorrect subtree is a Paretean random variable, and that the parameter of the Pareto distribution is estimated similarly to the parameter for systems of information transmission with one source

Keywords

discrete systems; memoryless systems; multi-access systems; probability; random processes; sequential decoding; telecommunication channels; trees (mathematics); Paretean random variable; Pareto distribution; bipartite graphs; code tree; computational distribution; decoding metric; discrete memoryless multiple-access channels; first incorrect subtree; incorrect paths; information transmission; sequential decoder; upper bound; Bipartite graph; Convolutional codes; Distributed computing; Error probability; Maximum likelihood decoding; Maximum likelihood estimation; Noise level; Random variables; Tree graphs; Upper bound;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/18.485712

Filename

485712