关键词: 多符号差分检测, K-best算法, 排序

Abstract: The K-best algorithm（also known as the M algorithm） is well appreciated not only for its lower complexity，but also for its fixed complexity and latency，so it is used to solve the problem of high complexity for Multiple Symbol Differential Detection（MSDD）.However，at present，the K-best algorithm used in the MSDD reduces the complexity by reducing the branches of extensible nodes mostly，and the method of sorting on each layer is almost empty.To solve this problem，this article researches two sorting methods based on dynamic K-best algorithm，Batcher’s sort merge sort and K cycles sort.The simulation analysis shows that Batcher merge sort method can reduce 70% of the compare & swap（c&s） operations compared to the traditional bubble sort method，but also has the similar performance，and only the 0.25 dB difference at high SNR.K cycles sort scheme not only reduces about 90% of complexity compared to the bubble sort method，but also nearly saves 85% c&s compared to the Batcher’s sorting method，while its performance is the best at high SNR.

Key words: Multiple Symbol Differential Detection（MSDD）, K-best algorithm, sort