图 1给出了空间复用MIMO迭代检测的系统模型，其中发射天线数为$M$，接收天线数为$N$，且有$N\ge M$。相应的频域MIMO系统模型为：

式中，$\mathbf{H}$是$N\times M$维的信道传输矩阵，且假定被接收端所知；$\mathbf{s}={{({{s}_{1}},{{s}_{2}},\cdots ,{{s}_{M}})}^{\text{T}}}$是$M\times 1$维的发送符号向量，它是由比特向量$\mathbf{b=}{{({{b}_{1}},{{b}_{2}},\cdots ,{{b}_{QM}})}^{\text{T}}}$经过星座映射得到的(如图 1中的16QAM)，$\mathbf{s}=\text{map}(\mathbf{b})\in {{\vartheta }^{M}}$，其中$\vartheta $代表星座点，$Q$为调制阶数，且有$\left| \vartheta \right|={{2}^{Q}}$。因此，每使用一次信道将传输$QM$ bit信息；接收向量$\mathbf{y}$和噪声向量$\mathbf{n}$都是$N\times 1$维的，且噪声向量的每个元素是服从零均值、方差${{\sigma }^{2}}={{N}_{0}}$的复高斯分布。本文将发送端的符号功率归一化为$E[\mathbf{s}{{\mathbf{s}}^{\text{H}}}]={{M}^{-1}}{{\mathbf{I}}_{M}}$，使得平均接收信噪比为$1/{{N}_{0}}$。

图  1  MIMO迭代检测系统模型

接收端采用了迭代检测译码算法，主要由SISO检测器和信道译码器模块构成。首先，SISO检测器利用接受向量$\mathbf{y}$和先验信息${{L}_{A1}}$得到似然信息${{L}_{D1}}$，在似然信息中减去先验信息${{L}_{A1}}$后作为外信息${{L}_{D1}}$，即有${{L}_{E1}}={{L}_{D1}}-{{L}_{A1}}$。检测器的外信息${{L}_{E1}}$经过解交织后作为信道译码器的先验信息${{L}_{A2}}$，译码输出的似然信息${{L}_{D2}}$减去先验信息得到译码器外信息${{L}_{E2}}$，即有${{L}_{E2}}={{L}_{D2}}-{{L}_{A2}}$。译码器的外信息经过交织后作为检测器的先验信息。

SISO检测器利用式(2)计算每比特的对数似然信息：

利用边缘概率函数定义可知：

式中，${{\mathbf{B }}_{i,\pm 1}}$是当前比特${{b}_{i}}=\pm 1$且维度为${{2}^{QM-1}}$的比特向量集合，即${{\mathbf{B }}_{i,\pm 1}}=\left\{ \left. \mathbf{b} \right|{{b}_{i}}=\pm 1 \right\}$。进一步利用Bayes理论，可将式(3)转化为：

因此，式(2)的每比特似然信息可以表示为：

式中，${{\mathbf{b}}_{\left[ i \right]}}$表示比特向量$\mathbf{b}$去掉第i个元素后的向量，即${{\mathbf{b}}_{\left[ i \right]}}=\left[ {{b}_{1}},{{b}_{2}},\cdots ,{{b}_{i-1}},{{b}_{i+1}},\cdots ,{{b}_{QM}} \right]$。式(5)中的第二个等式利用了经过交织后$\mathbf{b}$中元素的相互统计独立性。SISO检测器的外信息可由式(5)得到：

利用MAX-LOG-MAP算法^[1]，式(6)可简化为：

从式(7)(或者式(6))可以看出，计算每比特的外信息需要评估${{2}^{QM}}$个比特向量，其复杂度随着调制阶数和发射天线数呈指数增长。因此，需要解决如何在避免这种穷举搜索的同时得到较好性能的问题。

MCMC算法是在给定概率分布$P(\mathbf{x})$条件下(可能不存在显示表达式或者直接采样很复杂)，通过便捷的采样方式得到服从该分布的样本序列。采样原则是：构造一个转移矩阵为$\mathbf{P}$的马氏链，使得该马氏链的平稳分布等于$P(\mathbf{x})$，当从任意初始状态${{\mathbf{x}}^{\text{init}}}$出发沿着该马氏链转移，可得到其转移序列为${{\mathbf{x}}^{\text{init}}},{{\mathbf{x}}^{1}},{{\mathbf{x}}^{2}},\cdots ,{{\mathbf{x}}^{n}},{{\mathbf{x}}^{n+1}},\cdots $。如果马氏链在第$n$步已经收敛，则${{\mathbf{x}}^{n}},{{\mathbf{x}}^{n+1}},\cdots $便是服从$P(\mathbf{x})$分布的样本序列。

不同的MCMC算法集中在如何构造转移矩阵$\mathbf{P}$上。利用细致平稳条件得到的Metropolis-Hastings算法，由于存在接收率$\alpha (\alpha \le 1)$，当接受率低时，其采样过程将原地踏步，拒绝大量的跳转。而Gibbs采样是$\alpha =1$的一种特殊的MCMC实现方式，马氏链的转移沿着单根坐标轴进行，即由条件概率$P({{x}_{i}}|{{x}_{1}},{{x}_{2}},\cdots ,{{x}_{i-1}},{{x}_{i+1}},\cdots )$进行采样更新。

为了降低式(7)计算LLR的复杂度，本文利用基于Max-Log更新的采样得到服从式(3)右端$p(\left. \mathbf{b} \right|\mathbf{y},{{L}_{A1}})$分布的比特向量列表$\mathbf{L}$，该列表能以极大概率包含式(7)右端的两项，分别被定义为$\text{LLR }\!\!\_\!\!\text{ plus}(i)$和$\text{LLR }\!\!\_\!\!\text{ minus}(i)$。和LSD类似，LLR的计算可以表示为：

为了推导本文的基于Max-Log更新的采样算法，定义每比特的条件对数似然比为：

利用Bayes理论和$\mathbf{b}$中元素的独立性，将上式展开为：

式中，$\mathbf{s}({{b}_{i}}=\pm 1)=\text{map}({{\mathbf{b}}_{[i]}},{{b}_{i}}=\pm 1)$。传统Gibbs采样利用$P(\left. {{b}_{i}}=+1 \right|{{\mathbf{b}}_{[i]}},\mathbf{y},{{L}_{A1}})={1}/{[1+\exp (-{{\lambda }_{1}}({{b}_{i}}))]}\;$计算每比特的概率分布，然后根据概率分布进行采样更新^[5-11]，该过程涉及到非线性的指数${1}/{1+\exp (\centerdot )}\;$运算。为了降低计算复杂度，Max-Log更新直接在对数域进行max采样，并能使所产生的比特向量列表以极大概率包含式(8)中的$\text{LLR }\!\!\_\!\!\text{ plus}(i)$和$\text{LLR }\!\!\_\!\!\text{ minus}(i)$，有效地减少列表集合的大小。

在不同信噪比下，由式(10)计算得到的${{\lambda }_{1}}({{b}_{i}})$幅值范围会被扩展得很大。若用较少的比特位数表示${{\lambda }_{1}}({{b}_{i}})$会存在性能损失，反之则会增大复杂度。因此，为了增加算法的鲁棒性，在采样之前用${{L}_{A1}}={{L}_{A1}}/\text{SNR}$对先验信息进行归一化处理。此时，式(10)可改写为：

式中，${{\hat{s}}_{k}}$和${{s}_{k}}$分别为当前比特${{b}_{i}}=+1$和${{b}_{i}}=-1$所映射的当前符号；$y_{k}^{MF}=h_{k}^{\text{H}}\mathbf{y}$和${{\rho }_{k,l}}=h_{k}^{\text{H}}{{h}_{l}}$可在MCMC迭代采样之前完成。其比特更新过程为：

式(12)采样更新过程可概括为式(13)，即Max-Log更新的基本原理:

结合式(8)、式(11)和式(12)，得到了本文提出的MCMC整体算法，如算法1所示。

算法 1 MCMC MIMO Detection based on Max-Log Updating

Preprocessing ${{\mathbf{H}}^{\text{H}}}\mathbf{y}$and${{\mathbf{H}}^{\text{H}}}\mathbf{H}$;

Initialize ${{\mathbf{b}}^{0}}={{(b_{1}^{0},b_{2}^{0},\cdots ,b_{QM}^{0})}^{\text{T}}}$ randomly;

Initialize $\text{LLR }\_\text{ plus}=\text{LLR }\_\text{ minus}=(-\inf ,-\inf ,\cdots ,-\inf )$;

Normalize ${{L}_{A1}}={{L}_{A1}}/\text{SNR}$;

For n=1to |L|

// ------------Gibbs sampler-----------------

Compute ${{\lambda }_{1}}(b_{1}^{{}}|b_{2}^{n-1},\cdots ,b_{QM}^{n-1})$ using (11);

Draw sample $b_{1}^{n}$ using (12);

Compute ${{\lambda }_{1}}(b_{2}^{{}}|b_{1}^{n},b_{3}^{n-1},\cdots ,b_{QM}^{n-1})$ using (11);

Draw sample $b_{2}^{n}$ using (12);

$\vdots $

Compute ${{\lambda }_{1}}(b_{QM}^{{}}|b_{1}^{n},b_{2}^{n},\cdots ,b_{QM-1}^{n})$ using (11);

Draw sample $b_{QM}^{n}$ using (12);

// ------------LLR Calculator-----------------

For i=1 to $QM$

Compute

End for;

End for;

De-normalize ${{L}_{E1}}={{L}_{E1}}\times \text{SNR}$;

其中计算LLR时采取了和文献^[10]一样的处理，即在计算第i比特的外信息${{L}_{E1}}({{b}_{i}})$时，将当前时刻采样得到的比特向量和翻转第i比特的比特向量用作计算$\text{LLR }\!\!\_\!\!\text{ plus}(i)$和$\text{LLR }\!\!\_\!\!\text{ minus}(i)$。最后对外信息进行${{L}_{E1}}({{b}_{i}})={{L}_{E1}}({{b}_{i}})\text{SNR}$处理。

基于Max-Log更新的MCMC算法也存在高信噪比下陷入锁死的问题，当马氏链转移到状态$\mathbf{s}$时，若有：1)${{\left\| \mathbf{y}-\mathbf{H{s}'}({{b}_{i}}) \right\|}^{2}}-{{\left\| \mathbf{y}-\mathbf{Hs} \right\|}^{2}}>0$；2)${{L}_{A1}}({{b}_{i}})=0$或$\text{sign}({{L}_{A1}}({{b}_{i}}))=\text{sign}(\mathbf{s}({{b}_{i}}))$或$\text{sign}({{L}_{A1}}({{b}_{i}}))\ne \text{sign}(\mathbf{s}({{b}_{i}}))$，但$\left| {{L}_{A1}}({{b}_{i}}) \right|＜{{\left\| \mathbf{y}-\mathbf{H{s}'}({{b}_{i}}) \right\|}^{2}}-{{\left\| \mathbf{y}-\mathbf{Hs} \right\|}^{2}}$成立，$i=1,2,\cdots ,QM$，其中$\mathbf{{s}'}({{b}_{i}})$表示$\mathbf{s}$仅改变第i个比特元素后的向量，那么状态$\mathbf{s}$对应的条件对数比将大于$\mathbf{{s}'}({{b}_{i}})$，此时马氏链将长时间陷入锁死到状态$\mathbf{s}$，称这样的状态为局部最优态。例如，对于一个4-QAM调制的$2\times 2$的MIMO系统，当发送比特向量为$\mathbf{b}={{[1,1,1,1]}^{\text{T}}}$，那么$\mathbf{b}={{[1,1,1,1]}^{\text{T}}}$便是全局最优态。假设在状态转移过程中，系统到达了一个局部最优态${{[-1,1,-1,1]}^{\text{T}}}$，即该状态对应的条件对数似然比比它的所有临近态${{[1,1,-1,1]}^{\text{T}}}$，${{[-1,-1,-1,1]}^{\text{T}}}$，${{[-1,1,1,1]}^{\text{T}}}$，${{[-1,1,-1,-1]}^{\text{T}}}$都大。此时，系统将陷入锁死到该局部最优态，使得采样的状态数减少，从而导致计算LLR时出现较大的误差。为了解决陷入锁死问题，本文提出了如下3个增强技术。

基于Max-Log更新的MCMC算法类似于爬山算法(hill climbing)，其实质是一种简单的贪心搜索算法，但是会陷入锁死到局部最优态。在此基础上，本文提出了一种类似于模拟退火(simulated annealing)的抖动处理技术。将一个给定的抖动区间$[-\text{bias},\text{bias}]$作为置信区间，在区间外以概率1接收更新，在区间内认为其置信水平为50%，即对于处于区间$[-\text{bias,bias}]$内的比特进行随机采样更新。此时，式(12)的比特更新过程变为：

该技术可为马氏链提供一定的可能性跳出局部最优态，从而保证马氏链在较长的转移时间内不陷入锁死到局部最优态。

为了进一步降低陷入“锁死”状态的概率，本文定义${{\mathbf{b}}^{n}}={{\mathbf{b}}^{n-1}}$为潜在锁死态。当出现潜在锁死态时，立即重新初始化$\mathbf{b}$，以全新的初始态进行状态转移，即：

重新初始化可进一步提高系统性能，并且几乎不增加算法开销，仅仅需要一个1bit的状态标志来识别是否达到潜在锁死态。

在LSD算法中，LLR-clipping技术能在复杂度和性能之间进行折中。由于较大的LLR值会使得译码器无法正常工作于纠错状态，本文将修剪饱和处理(clipping)技术运用到MCMC算法中对输出外信息进行修剪饱和处理，即：

该技术一方面可以提升译码性能，另一方面也为后续的迭代检测提供更加正确的先验信息，从而帮助Gibbs采样器采得更有效的样本。

本文的仿真研究都是基于128个子载波，收发天线数均为4的OFDM-MIMO系统模型，其编码器采用码率为1/2的卷积码[133 171]，调制方式为16QAM。接收端采用迭代检测译码算法，其中译码器为BCJR译码，信道模型为准静态瑞利衰落信道。

图 2给出了传统MCMC算法的仿真性能，其中serial表示串行深度为50的Gibbs采样，parallel表示5路并行深度为10的Gibbs采样，I表示迭代次数。从图中可以看出，虽然并行MCMC能提高系统性能，但是即在高信噪比下存在误码平层。

图  2  传统MCMC串行采样和并行采样性能对比

不同抖动区间下对基于Max-Log更新的MCMC检测算法进行了仿真，如图 3所示。仿真结果显示，抖动处理能有效地解决陷入锁死问题，从而提高系统的检测性能。但是抖动区间的大小会影响MCMC算法的性能：区间太大，Gibbs采样过程跳转更剧烈，类似于随机游走，性能会降低；区间太小，采样过程会出现原地踏步，拒绝大量的跳转，同样会降低性能。从图 3可以得到最佳的抖动参数为0.15。另外，从图 2和图 3的仿真结果对比发现，相比传统MCMC算法，最佳抖动处理后的Max-Log更新的MCMC算法可获得超过5 dB的性能增益。

图  3  不同抖动参数的检测性能

经过3种增强技术处理的MCMC检测性能仿真如图 4所示。仿真结果显示重新初始化在抖动处理的基础上进一步带来了1～2dB的性能增益，修剪饱和处理在前两者的基础上继续提高了0.2 dB的性能。图 4的结果还表明了第2次迭代能提高6 dB左右的性能，而后续的迭代增益较小。基于此，图 5给出前两次迭代的MMSE-wPIC算法^[2]，STS算法^[3]和本文的MCMC增强算法的性能仿真结果。从图中可以看出，当$\left| L \right|=50$时，相比MMSE-PIC算法，MCMC增强算法有1～2dB的性能增益，当$\left| L \right|=100$时，相比准MAP算法STS，MCMC增强算法在第2次迭代只有不到1dB的性能损失。

图  5  MMSE、STS和MCMC检测算法性能对比

图  4  经过增强技术处理后的MCMC算法性能

本文利用基于FPGA面积开销的运算器数目来评估MMSE-PIC算法、传统MCMC算法和本文的MCMC增强算法的复杂度。由于STS算法的复杂度随着信道和噪声干扰的不同存在着不同的算法复杂度，且文献^[14]给出其复杂度远大于线性检测器，本文并未对其进行分析。和文献^[13]一样，假设比较器为单位复杂度，加法器为比较器的2倍开销，乘法器的复杂度为加法器的10倍，除法器和平方根分别为乘法器的4.5倍和3.8倍。复数乘法器的运算复杂度为4个实数乘法器和2个加法器的开销之和。此外，根据文献^[13]，由于$\mathbf{s}$是由星座点向量构成，式中乘法${{\rho }_{k,l}}{{s}_{l}}$、${{({{\hat{s}}_{k}}-{{s}_{k}})}^{\text{H}}}(\centerdot )$、$h_{k}^{2}(\hat{s}_{k}^{2}-s_{k}^{2})$可通过移位加(shift-add)实现。表 1给出了MMSE-PIC算法、传统MCMC算法和本文的MCMC增强算法的运算复杂度，参数与系统模型参数一致，M表示发射天线数，N表示接收天线数，Q为调制阶数，|L|为MCMC采样列表大小，最后的总体复杂度是当M=4，N=4，Q=4，|L|=50时的运算复杂度开销。从表中可以看出，MMSE-PIC算法和MCMC算法的复杂度都只是发射天线数和调制阶数呈多项式增长。

根据表 1的结论，得到$4\times 4$MIMO下，不同调制阶数(16QAM和64QAM)的MMSE-PIC算法和MCMC算法的复杂度，如图 6所示。

图  6  MMSE和MCMC复杂度对比

当采样序列$\left| L \right|=100$时，MMSE-PIC算法的复杂度在两种调制阶数下都为最小，如图 5所示，其性能要远远低于本文的MCMC增强算法。在$\left| L \right|=50$时，本文的MCMC算法的复杂度仅为MMSE-PIC算法的90%，且性能比MMSE-PIC算法提高1～2dB。从图中还可以得到，相比于传统MCMC算法，基于Max-Log更新的MCMC检测器能有效地降低计算复杂度。

本文提出了基于Max-Log更新的MCMC检测算法。该算法由Gibbs采样和LLR计算构成。首先，利用基于Max-Log更新的采样得到服从所需后验概率分布的比特向量列表，再利用MAX-LOG-MAP算法计算外信息。该MCMC检测算法具备复杂度低和可并行处理等优势，但是在高信噪比存在陷入锁死的问题，使得采样状态数减少，从而导致计算LLR时出现较大的误差。基于此，本文提出了3个增强技术：抖动处理、条件下重新初始化和修剪饱和处理。仿真结果表明：基于Max-Log更新的MCMC增强算法能有效提高系统的检测性能，并能降低计算复杂度。