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

摘要： K-best算法（即M算法）不但具有较低复杂度，而且还具有固定的复杂度和时延，因而被应用于解决多符号差分检测（MSDD）高计算复杂度的问题。然而，当前K-best算法在MSDD中的应用大多仅通过减少节点的分支数来降低复杂度，而对每层排序方法的研究几乎是空白。鉴于此研究了基于动态K-best算法下的Batcher合并排序和K cycles排序。仿真得出Batcher合并排序方法比传统的冒泡排序在比较交换次数上可以减少70%，而性能在高信噪比时仅相差0.25 dB;K cycles排序在复杂度上比Batcher减少将近85%，比冒泡减少90%左右，而其性能在高信噪比时是最优的。

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