Computationally Optimal Metric-First Code Tree Search Algorithms
- 1 June 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 32 (6) , 710-717
- https://doi.org/10.1109/tcom.1984.1096122
Abstract
Code tree search algorithms find wide applicability in source encoding, channel decoding, pattern recognition, and maximum likelihood sequence estimation. These algorithms search code trees and may be classified as depth-first, breadth-first, and metric-first depending on the search criterion employed. We define here a criterion for metric-first algorithms to be optimal. We show that implementations of metric-first searches proposed heretofore are not optimal, and we propose and analyze two algorithms which are. Experimental data obtained by encoding a voiced speech sound point to superiority of the proposed implementation over earlier versions.Keywords
This publication has 14 references indexed in Scilit:
- Sequential Coding Algorithms: A Survey and Cost AnalysisIEEE Transactions on Communications, 1984
- Speech Encoding by a Stack AlgorithmIEEE Transactions on Communications, 1980
- Dynamic hashingBIT Numerical Mathematics, 1978
- A multiple stack algorithm for erasurefree decoding of convolutional codesIEEE Transactions on Communications, 1977
- Real-number convolutional codes for speech-like quasi-stationary sources (Corresp.)IEEE Transactions on Information Theory, 1977
- Generalized stack algorithms for decoding convolutional codesIEEE Transactions on Information Theory, 1975
- Tree encoding of speechIEEE Transactions on Information Theory, 1975
- Binary Search Trees and File OrganizationACM Computing Surveys, 1974
- Fast Sequential Decoding Algorithm Using a StackIBM Journal of Research and Development, 1969
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithmIEEE Transactions on Information Theory, 1967