An Efficient Tree Search Algorithm for the Free Distance of Variable-Length Error-Correcting Codes
| Autor: | Po-Ning Chen, Fady Alajaji, Chun Huang, Ting-Yi Wu, Yunghsiang S. Han |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Red–black tree
Tree rotation Computer science Optimal binary search tree Breadth-first search 020206 networking & telecommunications Best-first search 02 engineering and technology Interval tree Graph Search tree Computer Science Applications Tree traversal Search algorithm Modeling and Simulation Ternary search tree 0202 electrical engineering electronic engineering information engineering Algorithm design Depth-first search Electrical and Electronic Engineering Dichotomic search Algorithm Dijkstra's algorithm Order statistic tree |
| Zdroj: | IEEE Communications Letters. 22:474-477 |
| ISSN: | 1089-7798 |
| Popis: | We propose an efficient tree search algorithm for determining the free distance of variable-length error-correcting codes (VLECs). A main idea behind the algorithm is to structure all pairs of code word-concatenated sequences as a tree, in which we seek the pair of sequences that determine the free distance. In order to speed up the algorithm, we establish constraints that do not compromise optimality in determining the free distance. Experimental results on VLECs algorithmically constructed for the English alphabet show that our algorithm requires a considerably smaller number of bitwise distance computations and covers a much smaller number of tree nodes than Dijkstra’s algorithm operating over the pairwise distance graph while being a hundred times faster in terms of execution time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|