The breadth-first tree searching (BFTS) detection algorithm such as the QR decomposition with M algorithm (QRD-M) which is the generally K-best detection algorithm is suboptimal, but has high complexity. In this letter, the K-best BFTS detection algorithm having reduced complexity is proposed. The proposed detection algorithm calculates the channel condition to decide the thresholds for regulating complexity and performance and from the simulation results, it has good error performance with very low complexity.

In this paper, we present a low and variable computation complexity decoder based on K-Best for uncoded detection in spatially multiplexed MIMO systems. In the variable complexity K-Best (VKB), the detection of each symbol is carried out using only a symbol constellation of variable size. This symbol constellation is obtained by considering the channel properties and a given target SNR. Simulations show that the proposed technique almost matches the performance of the original K-Best decoder. Moreover, it is able to reduce the average computation complexity by at least 75% in terms of the number of visited nodes.

In this letter, an adaptive detection scheme for a multiple-input multiple-output (MIMO) system is proposed. In order to reduce the complexity of the decoding steps, the initial symbol is obtained by a MMSE equalizer and then the symbol ordering is performed by the channel state. After the received symbols are divided according to the channel state, some of the symbols are detected by using the MMSE detector with low complexity. With cancelation processing, the remainder symbols are detected for the K-best detector. The proposed adaptive detection scheme combines the MMSE and K-best detector based on the channel state. Therefore, the proposed adaptive detector achieves a good performance.

We propose new adaptive tree search algorithms for multiple-input multiple-output (MIMO) systems based on path metric comparison. With the fixed number of survivor paths, the correct path metric may be temporarily larger than the maximum path metric of the survivor paths under an ill-conditioned channel. There have been also adaptive path metric algorithms that control the number of survivor paths according to SNR. However, these algorithms cannot instantaneously adapt to the channel condition. The proposed algorithms accomplish dynamic adaptation based on the ratio of two minimum path metrics as the minimum is significantly smaller than the second minimum under good channel conditions and vice versa. The proposed algorithms are much less complex than the conventional noise variance-based adaptive tree search algorithms while keeping lower or similar error performance. We first employ the proposed adaptive tree search idea to K-best detection and then extend it QRD-M MIMO detection.

In this paper, we present a new dependency parsing method for languages which have very small annotated corpus and for which methods of segmentation and morphological analysis producing a unique (automatically disambiguated) result are very unreliable. Our method works on a morphosyntactic lattice factorizing all possible segmentation and part-of-speech tagging results. The quality of the input to syntactic analysis is hence much better than that of an unreliable unique sequence of lemmatized and tagged words. We propose an adaptation of Eisner's algorithm for finding the k-best dependency trees in a morphosyntactic lattice structure encoding multiple results of morphosyntactic analysis. Moreover, we present how to use Dependency Insertion Grammar in order to adjust the scores and filter out invalid trees, the use of language model to rescore the parse trees and the k-best extension of our parsing model. The highest parsing accuracy reported in this paper is 74.32% which represents a 6.31% improvement compared to the model taking the input from the unreliable morphosyntactic analysis tools.

It is known that MIMO channel matrix condition number influences detectors performance. Several authors have proposed combined decoders, mainly suboptimal, to cope with this fact. These combined algorithms require an estimation of the MIMO channel matrix condition number and a selection of a suitable threshold condition number. This letter presents practical algorithms to carry out the referred tasks and shows their performance in practice.

This paper proposes a reduced-complexity signal detection scheme for Orthogonal Frequency Division Multiplexing with Space Division Multiplexing (OFDM/SDM) systems that utilize Zero-Forcing (ZF) and K-best algorithms. It is known that Maximum Likelihood Detection (MLD) with exhaustive search achieves mathematically optimal performance for SDM signal detection. However, it also suffers from exponential computational complexity against the number of transmit antennas and modulation order. In order to reduce the computational complexity of MLD, we apply the K-best algorithm for signal detection. It is known that the K-best algorithm itself inherently reduces the computational complexity of MLD because it avoids exhaustive search. In this paper, we propose the modified K-best algorithm, which exploits the ZF algorithm for initial symbol estimation. This initial symbol estimation improves the decoding accuracy of the original K-best algorithm. We evaluate the performance of the proposed scheme through computer simulations. The computer simulation results show that the performance degradation from the MLD algorithm is suppressed to just 1 dB or so in terms of the required Eb/N0 for packet error rate (PER) = 10-2, When either 16 Quadrature Amplitude Modulation (16QAM) or 64QAM is applied with three transmit and three receive antennas. In these cases, 87% and 99% fewer metric computations are required than the MLD algorithm. It is confirmed that the proposed MLD algorithm offers a significant reduction in the computational complexity from the MLD algorithm while suppressing the performance degradation.

In highly reliable communication network design, disjoint paths between pairs of nodes are often needed in the design phase. The problem of finding k paths which are as diverse as possible and have the lowest total cost is called a k-best paths problem. We propose an algorithm for finding the k-best paths connecting a pair of nodes in a graph G. Graph extension is used to transfer the k-best paths problem to a problem which deploits well-known maximum flow (MaxFlow) and minimum cost network flow (MCNF) algorithms. We prove the k-best paths solution of our algorithm to be an optimal one and the time complexity is the same as MCNF algorithm. Our computational experiences show that the proposed algorithm can solve k-best paths problem for a large network within reasonable computation time.