BOUNDS ON THE PERFORMANCE OF PARTIAL SELECTION NETWORKS

The evaluation of the performance of partial selection networks which select a set of M elements from a set of N inputs is addressed in this paper, The partial selection problem occurs when dealing with non exh austive multi-path breadth-first searches, like in the M algorithm or the bidirectional algorithm, These algorithms are used in the decoding of convolutional codes, This paper presents a set of bounds to evalua te the quality of regular, Delta class, networks of depth IgN and widt h N/2, with respect to their selection capabilities. The results from the bounds are compared to Monte Carlo simulations of the selection ca pabilities of the Banyan and Alekseyev networks, Finally, the performa nce degradation associated with the use of these networks on the perfo rmance of a bidirectional decoder is presented, In particular, we show that even with imperfect selection, the bidirectional decoder can out perform a Viterbi decoder of comparable complexity.