Improving the Efficiency of Minimum Determinant Computation in Space Time Trellis Code with Optimal Subtree Pruning

The calculation of minimum determinant plays a crucial role in fulfilling the determinant criterion of a certain code design in space time trellis code. In the heuristic optimization of code construction, the minimum determinant is derived via a variant of the branch and bound algorithm. Although the algorithm is relatively efficient, it is not optimized in terms of the pruning strategy. Search space is pruned when the upper bound is exceeded. No attempt is made on discerning the potential of different structures within the search space. This paper proposes a new pruning approach to improve the computational efficiency of finding the minimum determinant for a particular generator matrix G. It builds upon the idea of minimal complete cycles. They are the smallest paths that begin and end with zero. By capitalizing on the minimum complete cycle of the search tree, the structure with the highest potential in the search space can be identified. Consequently, it helps the search process to differentiate subtrees in their capacity of yielding a solution. Search can be focused on a certain subtree while others are pruned altogether. This enables approximately 45% reduction of the overall spatial and temporal cost. Despite its potential, the pruning method is inherently probabilistic. There is a 0.0357 risk that it could provide an erroneous minimum determinant.