本发明涉及多层丛集式多输入多输出检测方法及多输入多输出检测器。用于一多输入多输出系统的一接收机的多输入多输出检测方法，该多输入多输出系统使用一多维度的正交振幅调制(N-QAM)，该多输入多输出检测方法包含有产生多个平均码元向量集合及多个搜寻半径；选择对应于N-QAM星座图的多层级架构的最上层的一候选码元向量集合；根据该最上层的候选码元向量集合，产生对应于N-QAM星座图的多层级架构的下一层的一搜寻空间；确认该搜寻空间所对应的N-QAM星座图的多层级架构的层级；以及于该搜寻空间所对应的N-QAM星座图的多层级架构的层级已至最底层时，根据该搜寻空间产生一输出讯号。
1.一种用于一多输入多输出系统的一接收机的多输入多输出检测方法，该多输入多输出系统使用一多维度的正交振幅调制，该多输入多输出检测方法包含有：产生多个平均码元向量集合及多个搜寻半径，每一平均码元向量集合及每一搜寻半径皆对应于N-QAM星座图的多层级架构除最底层之外的其中一层；
在对应于多层级架构的最上层的一平均码元向量集合所形成的一初始搜寻空间中，选择一候选码元向量集合；
根据该候选码元向量集合，产生对应于多层级架构的下一层搜寻空间；
若该下一层搜寻空间非为最底层时，则从该搜索空间中选择下一层的候选码元向量集合；以及若于该下一层搜寻空间所对应的多层级架构的层级已至最底层时，根据该下一层搜寻空间产生一输出讯号。
2.如权利要求1所述的多输入多输出检测方法，其中该多个搜寻半径的每一搜寻半径是一欧几里得距离与一噪声抑制参数的乘积。
3.如权利要求1所述的多输入多输出检测方法，其中，于确认该搜寻空间所对应的多层级架构的层级不等于最底层时，于该搜寻空间中，选择符合一限制条件的一候选码元向量集合，其中该限制条件对应于该搜寻空间所对应的多层级架构的层级。
4.如权利要求3所述的多输入多输出检测方法，其中该限制条件是该候选码元向量集合中每一平均码元向量经过信道后，与一接收讯号之间的一误差向量的欧几里得距离必须小于一搜寻半径。
5.如权利要求3所述的多输入多输出检测方法，其中于该搜寻空间中选择符合该限制条件的该候选码元向量集合的步骤，包含有：进行一部分欧几里得距离运算程序，计算该搜寻空间中一平均码元向量经过信道后，与一接收讯号之间的一误差向量的一部分欧几里得距离；
比较该部分欧几里得距离及一搜寻半径，以产生一比较结果，该搜寻半径对应于该搜寻空间所对应的多层级架构的层级；
判断该部分欧几里得距离运算程序是否已计算至完整的欧几里得距离，以产生一判断结果；以及根据该比较结果及该判断结果，选择该候选码元向量集合。
6.如权利要求5所述的多输入多输出检测方法，其中根据该比较结果及该判断结果选择该候选码元向量集合的步骤，包含有：于该比较结果显示该部分欧几里得距离大于该搜寻半径时，停止该部分欧几里得距离运算程序，并排除该平均码元向量于该候选码元向量集合之外。
7.如权利要求5所述的多输入多输出检测方法，其中根据该比较结果及该判断结果选择该候选码元向量集合的步骤，包含有：于该比较结果显示该部分欧几里得距离小于该搜寻半径，且该判断结果显示该部分欧几里得距离运算程序尚未计算至完整的欧几里得距离时，进行该部分欧几里得距离运算程序，并增加该误差向量的一元素至该部分欧几里得距离运算程序中。
8.如权利要求5所述的多输入多输出检测方法，还包含有：
于该部分欧几里得距离小于该搜寻半径，且该部分欧几里得距离运算程序已计算至完整的欧几里得距离时，选择该平均码元向量作为该候选码元向量集合其中一候选码元向量。
9.如权利要求5所述的多输入多输出检测方法，还包含有：
对该候选码元向量集合中的多个平均码元向量所对应的多个误差向量，进行欧几里得距离大小的排序；以及选择一第一数量的平均码元向量形成一最佳候选码元向量集合，该第一数量的平均码元向量对应至该多个误差向量中，欧几里得距离最小的该第一数量的误差向量。
10.如权利要求1所述的多输入多输出检测方法，其中选择最上层的该候选码元向量集合的步骤是：在对应于多层级架构的最上层的一平均码元向量集合所形成的一初始搜寻空间中，选择符合一初始限制条件的该候选码元向量集合，该初始限制条件对应于多层级架构的最上层。
11.如权利要求10所述的多输入多输出检测方法，其中该初始限制条件是该候选码元向量集合中每一平均码元向量经过信道后，与一接收讯号之间的一误差向量的欧几里得距离必须小于一搜寻半径，该搜寻半径对应于多层级架构的最上层。
12.如权利要求1所述的多输入多输出检测方法，其中选择最上层的该候选码元向量集合的步骤，包含有：根据一最小均方误差算法处理一接收讯号，以取得一估测的传送讯号及该估测的传送讯号的相位；以及根据该估测的传送讯号的相位，选择该候选码元向量集合。
13.如权利要求12所述的多输入多输出检测方法，其中根据该估测的传送讯号的相位选择该候选码元向量集合的步骤，包含有：根据该估测的传送讯号其中一元素的相位所在的范围，选择对应于多层级架构的最上层的平均码元向量集合其中二个或三个平均码元向量，作为该元素所有可能的值，进而产生该候选码元向量集合。
14.如权利要求1所述的多输入多输出检测方法，其中根据该搜寻空间产生该输出讯号的步骤，包含有：于该搜寻空间所对应的多层级架构的层级已至最底层时，于该搜寻空间中选择一码元向量作为该输出讯号，该码元向量经过信道后与该接收讯号之间的一误差向量具有最小欧几里得距离。
15.如权利要求1所述的多输入多输出检测方法，其中根据该搜寻空间产生该输出讯号的步骤，包含有：于该搜寻空间所对应的多层级架构的层级已至最底层时，计算该搜寻空间的多个码元向量经过通道后，与该接收讯号之间的多个误差向量的欧几里得距离；
根据该多个误差向量的欧几里得距离的大小值，对该搜寻空间的该多个码元向量进行排序；以及于该多个码元向量中，选择一第一数量的码元向量以产生该输出讯号，该第一数量的码元向量对应于最小的该第一数量的误差向量的欧几里得距离。
16.一种用于一多输入多输出系统的一接收机的多输入多输出检测器，该多输入多输出系统使用一多维度的正交振幅调制，该多输入多输出检测器包含有：一接收端，用来接收一接收讯号；
一平均码元向量集合产生单元，用来产生多个平均码元向量集合，每一平均码元向量集合对应于N-QAM星座图的多层级架构中除最底层之外其中一层；
一搜寻半径产生单元，耦接于该平均码元产生单元及该接收机的一信道估测单元，用来根据该多个平均码元向量集合及该信道估测单元所产生的一信道矩阵，产生多个搜寻半径，每一搜寻半径对应于多层级架构中除最底层之外其中一层；
一候选码元向量集合产生单元，用来在对应于多层级架构除最底层之外其中一层的一搜寻空间中，选择符合一限制条件的一候选码元向量集合，该限制条件对应于该搜寻空间所对应的多层级架构的层级；
一搜寻空间产生单元，耦接于该候选码元向量集合产生单元，用来根据对应于多层级架构除最底层之外其中一层的一候选码元向量集合，产生对应于多层级架构的下一层的搜寻空间；以及一确认单元，耦接于该搜寻空间产生单元，用来确认该搜寻空间所对应的多层级架构的层级；以及一精确搜寻单元，耦接于该接收端、该信道估测单元及该确认单元，用来于该确认单元确认该搜寻空间所对应的多层级架构的层级已至最底层时，根据该搜寻空间，产生一输出讯号。
17.如权利要求16所述的多输入多输出检测器，其中该多个搜寻半径的每一搜寻半径是一欧几里得距离与一噪声抑制参数的乘积。
18.如权利要求16所述的多输入多输出检测器，其中符合该限制条件的该候选码元向量集合中每一平均码元向量经过信道后，与该接收讯号之间的一误差向量的欧几里得距离必须小于一搜寻半径，该搜寻半径是该多个搜寻半径其中一搜寻半径。
19.如权利要求16所述的多输入多输出检测器，其中该候选码元向量集合产生单元包含有：一部分欧几里得距离运算单元，耦接于该接收端、该平均码元向量集合产生单元、该信道估测单元及该确认单元，用来计算多层级架构除最底层之外每一层所对应的一搜寻空间中一平均码元向量经过信道后，与该接收讯号之间的一误差向量的一部分欧几里得距离；
一比较单元，耦接于该部分欧几里得距离运算单元及该搜寻半径产生单元，用来比较该部分欧几里得距离及一搜寻半径，以产生一比较结果，该搜寻半径对应于该搜寻空间所对应的多层级架构的层级；
一判断单元，耦接于该部分欧几里得距离运算单元，用来判断该部分欧几里得距离运算程序是否已计算至完整的欧几里得距离，以产生一判断结果；以及一第一选择单元，耦接于该比较单元及该判断单元，用来据该比较结果及该判断结果，选择该候选码元向量集合。
20.如权利要求19所述的多输入多输出检测器，其中该候选码元向量集合产生单元还包含有一第二选择单元，用来进行下列步骤：对该第一选择单元所选择的该候选码元向量集合中的多个平均码元向量所对应的多个误差向量，进行欧几里得距离大小的排序；以及选择一第一数量的平均码元向量形成一最佳候选码元向量集合，该第一数量的平均码元向量对应至该多个误差向量中，欧几里得距离最小的该第一数量的误差向量。
21.如权利要求16所述的多输入多输出检测器，其中该精确搜寻单元是于该搜寻空间所对应的多层级架构的层级已至最底层时，于该搜寻空间中选择一码元向量作为该输出讯号，该码元向量经过信道后与该接收讯号之间的一误差向量具有最小欧几里得距离。
22.如权利要求16所述的多输入多输出检测器，其中该精确搜寻单元是于该搜寻空间所对应的多层级架构的层级已至最底层时，进行下列步骤：计算该搜寻空间的多个码元向量经过通道后，与该接收讯号之间的多个误差向量的欧几里得距离；
根据该多个误差向量的欧几里得距离的大小值，对该搜寻空间的该多个码元向量进行排序；以及于该多个码元向量中，选择一第一数量的码元向量以产生该输出讯号，该第一数量的码元向量对应于最小的该第一数量的误差向量的欧几里得距离。
23.如权利要求16所述的多输入多输出检测器，还包含有：
一相位决定单元，用来选择对应于N-QAM星座图的多层级架构的最上层的一候选码元向量集合，该相位决定单元包含有：一运算单元，耦接于该接收端及该信道估测单元，用来根据一最小均方误差算法处理该接收讯号，以取得一估测的传送讯号及该估测的传送讯号的相位；以及一选择单元，耦接于该运算单元，用来根据该估测的传送讯号的相位，选择对应于最上层的该候选码元向量集合。
24.如权利要求23所述的多输入多输出检测器，其中该选择单元是用来根据该估测的传送讯号其中一元素的相位所在的范围，选择对应于多层级架构的最上层的平均码元向量集合其中二个或三个平均码元向量，作为该元素所有可能的值，进而产生该候选码元向量集合。
多层丛集式多输入多输出检测方法及多输入多输出检测器
技术领域
[0001] 本发明涉及一种无线通讯系统，特别是涉及一种多输入多输出(MIMO)无线通讯系统。
背景技术
[0002] 多输入多输出(Multiple-Input Multiple-Output，MIMO)技术使用天线阵列收发讯号，可于既有的频谱资源之下增加信道的容量，抵抗多重路径所造成的讯号衰减，同时增加通讯涵盖范围。当前的无线通讯标准，如无线局域网络所使用的IEEE 802.11n、WiMax所使用的IEEE 802.16及第三代行动通讯联盟所提出的长期演进系统(Long Term Evolution，LTE)皆应用多输入多输出技术以提高传输吞吐量。另一方面，高维度的正交振幅调制(Quadrature Amplitude Modulation，QAM)技术亦广泛地应用于上述无线通讯标准中。
[0003] 一NT×NR多输入多输出系统具有NT支传送天线及NR支接收天线，传送讯号表示为 xj表示第j个传送天线所传送的讯号，对应至一正交振幅调制星座图(Constellation)其中一码元(Symbol)，又称星座点。T表示转置矩阵。NT×NR多输入多输出系统的接收讯号表示为 yj表示第j个接收天线
所接收的讯号。接收讯号亦可表示为y＝Hx+n，H为NR×NT的通道矩阵，n为可加性白色高斯噪声(Additive White Gaussian Noise，AWGN)。请参考图1，图1为现有的一4×4多输入多输出系统10的示意图。在多输入多输出系统10的一传送端中，欲传送的一数据流(Data Stream)通过一正交振幅调制单元102进行调制成为传送讯号x＝[x1，x2，x3，x4]T，经过射频讯号处理后由天线T1～T4传送至通道中。多输入多输出系统10的一接收端的天线R1～R4接收射频讯号后，经过射频讯号处理，产生接收讯号y＝[y1，y2，y3，y4]T至一多输入多输出检测器104。由图1可知，每支接收天线皆接收到传送天线T1～T4所传送的讯号，这些来自不同传送天线的讯号之间相互干扰，因此，多输入多输出检测器104即用来T
根据接收讯号y＝[y1，y2，y3，y4] 产生估测的传送讯号 以供一正交振
幅解调单元106解调出正确的传送讯号。
[0004] 现有技术已提出了各种多输入多输出检测方法，简介如下。线性的多输入多输出检测方法如迫零(Zero-Forcing，ZF)算法及最小均方误差(Minimum Mean Square Error，MMSE)算法，是对估测的通道矩阵进行反矩阵运算，以取得传送讯号。迫零算法的运作可视为一滤波器，能够完全消除符间干扰(Inter-symbolInterference，ISI)，缺点是容易放大噪声；最小均方误差算法虽不能完全消除符间干扰，但不会放大噪声。上述两种方法的优点在于实作的复杂度低，但是效能有限。另外，非线性的多输入多输出检测方法包含有垂直式贝尔实验室分层空时(Vertical Bell LaboratoriesLayered Space Time，V-BLAST)算法、最大相似度(Maximum Likelihood，ML)算法及球状译码(Sphere Decoding，SD)算法等。垂直式贝尔实验室分层空时算法利用矩阵运算的QR分解法(QR Decomposition)，进行连续干扰消除(Successive Interference Cancellation)。相较于迫零算法及最小均方误差算法，垂直式贝尔实验室分层空时算法的效能较佳。最大相似度算法是将接收到的码元向量与传送讯号空间中所有的码元向量逐一比对，以检测最有可能被传送的码元向量。最大相似度算法具有最佳的效能，其复杂度亦是所有算法中最高的。球状译码算法是通过搜寻范围的设定，减少候选码元向量的数量以降低复杂度，其效能接近最大相似度算法的最佳效能。然而，于低信噪比(Signal-to-Noise Ratio，SNR)时，通道效应将影响球状译码算法的搜寻半径的决定过程，增加实作的复杂度。
[0005] 除了上述算法之外，还有一些方法利用N个维度的正交振幅调制星座图所具有的多层级架构，减少搜寻范围，以降低复杂度，如论文”Depth-Firstand Breadth-First Search Based Multilevel SGA Algorithms for Near OptimalSymbol Detection in MIMO Systems，”Wireless Communications，IEEETransactions on，vol.7，no.3，pp.1052-1061，March 2008，”Approximate MLdetection for MIMO systems with very low complexity，″ICASSP′04，vol.4，no.，pp.iv-809-12vol.4，17-21May 2004，以及美国专利第7,108,047号所提出的”Symbol De-mapping Methods in Multiple-Input Multiple-Output Systems”等方法。星座图的多层级架构简述如下。一个N-QAM星座图可l分为L层，L＝log4N，第l层(1≤l≤L)对应的平均码元集合S 表示为： i＝
1-l
1，2，...，Nl，Nl＝4 ×N
[0006] 请参考图2，图2为现有的一64-QAM星座图。64-QAM星座图可根据I-Q平面的四个象限，视为四个16-QAM星座图，每一16-QAM星座图可视为四个4-QAM星座图。1
64-QAM星座图的第一层的平均码元集合S 包含了全部共64个码元。每一4-QAM星座图中所有码元的平均值以一平均码元表示，如图中的星号点，因此第二层的平均码元集合
2
共16个平均码元。在第二层的平均码元集合S 中，同一象限的四
个平均码元的平均值进一步以另一平均码元表示，如图中的方点，因此第三层的平均码元l l
集合 共4个平均码元。属于第一层的平均码元si 以及与si 最靠近
的第(l-1)层中的4个平均码元之间的关系表示为：
[0007]
[0008] Ss，il-1为平均码元集合Sl-1的一子集合，包含与sil最接近的4个平均码元。若根据第l层的平均码元集合形成传送讯号空间，NT×NR多输入多输出系统的传送讯号可表示为 其中 分别为第1，2，...NT个传送天线所传送的码元l
向量，每一传送天线所传送的码元向量皆对应至平均码元集合S 其中一平均码元。由上可l
知，NT×NR多输入多输出系统总共可传送的平均码元向量集合X 表示为：
[0009]
[0010] 以图1的4×4多输入多输出系统10为例，若使用64-QAM进行讯号调制且根据第2 4
二层的平均码元集合形成传送讯号空间，则平均码元向量集合X 包含有16 个不同的平均l，i l，i l，i
码元向量。对应于一平均码元向量x 的一丛集(Cluster)C ，是平均码元向量x 在第l-1 l，
(l-1)层所延伸出的 个平均码元向量，视为平均码元向量集合X 的一子集合。丛集Ci
表示为：
[0011]
[0012] 假设接收讯号y为传送讯号x经过信道矩阵H的结果，且第l层的平均码元向量集合中，距离传送讯号x最近的平均码元向量为一平均码元向量xl。传送讯号x及平均码元向量xl经过通道之后的误差向量的欧几里得距离(Euclidean Distance)表示如下：
[0013] ||Hx-Hxl||2＝||H(x-xl)||2＝(x-xl)HHHH(x-xl)
[0014] 由于多输入多输出系统的各信道之间的相互影响，上述式中仅能确定HHH对角线元素为正实数，因此||Hx-Hxl||2不一定正比于||(x-xl)||2。换言之，在传送讯号空间中与传送讯号x相距最近的平均码元向量xl在经过信道之后，未必能在接收讯号空间中仍然与接收讯号y保持最小欧几里得距离，造成了系统误差。
[0015] 论 文”Depth-First and Breadth-First Search Based MultilevelSGAAlgorithms for Near Optimal Symbol Detection in MIMO Systems”所提出的方法是基于深度优先搜寻(Depth-First Search)或广度优先搜寻(Breadth-FirstSearch)，以序列高斯逼近(Sequential Gaussian Approximation，SGA)算法求得多个可能的传送讯号。
序列高斯逼近算法利用了迫零算法，因此受迫零算法的影响而造成效能衰减。另一方面，美国专利第7,108,047号所提出的方法是在接收讯号空间中检测与传送讯号最相似的讯号，无须进行信道矩阵的反矩阵运算。然而，美国专利第7,108,047号所提出的方法会产生严重的系统误差，并且容易在低位错误率时造成误差地板效应(Error Floor)。
[0016] 尽管上述利用正交振幅调制的多层级架构检测传送讯号的技术，可降低系统的复杂度，但系统误差的问题仍有待克服，才能提高多输入多输出检测的准确度。随着行动通讯的需求成长，多输入多输出系统已为主流的无线通讯系统所采用，因此，多输入多输出检测方法必须不断进步以因应成长中的数据传输量，同时以降低复杂度并兼顾效能为目标。
发明内容
[0017] 因此，本发明的主要目的是提供用于一多输入多输出系统的一接收机的多输入多输出检测方法及相关多输入多输出检测器，以降低多输入多输出检测的系统复杂度。
[0018] 本发明揭示了一种使用一多维度的正交振幅调制(N-QAM)的一多输入多输出接收机的检测方法。该检测方法包含有产生多个平均码元向量集合及多个搜寻半径，每一平均码元向量集合及每一搜寻半径皆对应于N-QAM星座图的多层级架构除最底层之外的其中一层；选择对应于多层级架构的最上层的一候选码元向量集合；根据该候选码元向量集合，产生对应于多层级架构的下一层搜寻空间；确认该下一层搜寻空间所对应的多层级架构的层级；若该下一层搜寻空间非为最底层时，则产生下一层的候选码元向量集合；若于该下一层搜寻空间所对应的多层级架构的层级已至最底层时，根据该下一层搜寻空间产生一输出讯号。
[0019] 本发明还揭示了一种用于一多输入多输出系统的一接收机的多输入多输出检测器，该多输入多输出系统使用一多维度的正交振幅调制(N-QAM)。该多输入多输出检测器包含有一接收端、一平均码元向量集合产生单元、一搜寻半径产生单元、一丛集搜寻单元及一精确搜寻单元。该接收端用来接收一接收讯号。该平均码元向量集合产生单元用来产生多个平均码元向量集合，每一平均码元向量集合对应于N-QAM星座图的多层级架构中除最底层之外其中一层。该搜寻半径产生单元用来根据该多个平均码元向量集合及该信道估测单元所产生的一信道矩阵，产生多个搜寻半径，每一搜寻半径对应于多层级架构中除最底层之外其中一层。该丛集搜寻单元包含有一搜寻空间产生单元、一确认单元及一候选码元向量集合产生单元。该搜寻空间产生单元用来根据对应于多层级架构除最底层之外其中一层的一候选码元向量集合，产生对应于多层级架构的下一层的一搜寻空间。该确认单元用来确认该搜寻空间所对应的多层级架构的层级。该候选码元向量集合产生单元用来在对应于多层级架构除最底层之外其中一层的一搜寻空间中，选择符合一限制条件的一候选码元向量集合，该限制条件对应于该搜寻空间所对应的多层级架构的层级。该精确搜寻单元用来于该确认单元确认该搜寻空间所对应的多层级架构的层级已至最底层时，根据该搜寻空间，产生一输出讯号。
附图说明
[0020] 图1为现有的一4×4多输入多输出系统的示意图。
[0021] 图2为现有的一64-QAM星座图。
[0022] 图3为本发明实施例一多输入多输出检测方法的流程图。
[0023] 图4为图3的多输入多输出检测方法用于一64-QAM星座图的多层级架构的示意图。
[0024] 图5为本发明实施例一误差向量的示意图。
[0025] 图6为本发明实施例一分支定界方法的流程图。
[0026] 图7为本发明实施例一多输入多输出检测方法的流程图。
[0027] 图8及图9为本发明实施例多输入多输出检测器的功能方块图。
[0028] 附图符号说明
[0029] 10、30 多输入多输出方法
[0030] 20 分支定界方法
[0031] 40、50 多输入多输出检测器
[0032] 400 接收端
[0033] 42 信道估测单元
[0034] 402 平均码元向量集合产生单元
[0035] 404 搜寻半径产生单元
[0036] 406 候选码元向量集合产生单元
[0037] 408 精确搜寻单元
[0038] 410 候选码元向量集合产生单元
[0039] 412 搜寻空间产生单元
[0040] 414 确认单元
[0041] 420 部分欧几里得距离运算单元
[0042] 422 比较单元
[0043] 424 判断单元
[0044] 426 第一选择单元
[0045] 428 第二选择单元
[0046] 500 相位决定单元
[0047] 502 运算单元
[0048] 504 选择单元
[0049] 100～114、200～212、300～316 步骤
具体实施方式
[0050] 由前述可知，一N-QAM星座图具有多层级架构的特性，本发明据此特性提出一种多输入多输出检测方法，其概念是于接收讯号空间中进行共二阶段的搜寻：第一阶段为丛集搜寻(Cluster Matching)，其是一广度优先搜寻；第二阶段为精确搜寻(Detail Matching)。丛集搜寻阶段起始于N-QAM星座图的多层级架构的最上层，即第L层(L＝Llog4N)，以第L层的平均码元向量集合X 作为初始搜寻空间(Searching Space)，总共进行(L-1)层的丛集搜寻以限缩搜寻空间，进而找出可能与传送讯号相距最近的码元向量所属的丛集。精确搜寻阶段是于N-QAM星座图的多层级架构的最底层，(若由下层往上层计数即第一层)，找出与传送讯号相距最小的码元向量，也就是最可能为传送讯号的码元向量。
[0051] 在此先定义使用本发明的系统为一NT×NR多输入多输出系统，其中发射机包含有NT个传送天线，接收机包含有NR个接收天线，并且使用N-QAM调制欲传送的数据流。传送讯号表示为 xj表示第j个传送天线所传送的讯号，以一N-QAM星座图表示。接收讯号表示为 yj表示第j个接收天线所接收的
讯号。一N-QAM星座图可分为L个层级，L＝log4N，对应于第l层(1≤l≤L)的一平均码l 1-l
元集合S 表示为 i＝1，2，...，Nl，Nl＝4 ×N。举例来说，对应于N-QAM星座
图的多层级架构的最上层的平均码元集合包含有四个平均码元，而对应于最底层的平均码元集合即N-QAM星座图中的N个码元。就NT×NR多输入多输出系统而言，对应于N-QAM星座图的多层级架构的第l层的一平均码元向量集合表示为
l，i l，i
平均码元向量x 中每一元素对应至一传送天线。一丛集C 对应于第l层的平均码元向l，i l-1
量x 在第(l-1)层所延伸出的 个平均码元向量，视为平均码元向量集合X 的一子集合。关于后文中出现的其它集合的数学符号及意义，请参考前述，在此不重复说明。
[0052] 请参考图3，图3为本发明实施例一多输入多输出检测方法10的流程图。多输入多输出检测方法10包含有以下步骤：
[0053] 步骤100：开始。
[0054] 步骤102：产生(L-1)个平均码元向量集合及(L-1)个搜寻半径，每一平均码元向量集合及每一搜寻半径皆对应于N-QAM星座图的多层级架构中除最底层之外的其中一层，L＝log4N。
[0055] 步骤104：在对应于N-QAM星座图的多层级架构的最上层的一平均码元向量集合所形成的一初始搜寻空间中，选择符合一初始限制条件的一候选码元向量集合。
[0056] 步骤106：根据该候选码元向量集合，产生对应于N-QAM星座图的多层级架构的下一层的一搜寻空间。
[0057] 步骤108：确认该搜寻空间所对应的N-QAM星座图的多层级架构的层级，若已至N-QAM星座图的多层级架构的最底层，进行步骤112；若位于其它层级，则进行步骤110。
[0058] 步骤110：于该搜寻空间中，选择符合一限制条件的一候选码元向量集合，并回到步骤106。
[0059] 步骤112：根据该搜寻空间，产生一输出讯号。
[0060] 步骤114：结束。
[0061] 步骤104至步骤110描述丛集搜寻阶段，其中步骤106至步骤110形成一循环，逐层进行丛集搜寻；步骤108用来确认丛集搜寻阶段完成与否。步骤112描述最底层的精确搜寻阶段。初始搜寻空间即对应于N-QAM星座图的多层级架构的第L层的平均码元向量集L L 3合X。以一4×4多输入多输出系统为例，若使用64-QAM调制，初始搜寻空间∏ ＝X ＝
3，i
{x }，i＝1，2，...，256，共包含256个平均码元向量。最上层丛集搜寻的初始限制条件及l
其后各层丛集搜寻的限制条件意义相同，是用来于搜寻空间∏ 中，选择那些经过信道后与l l，i
接收讯号y之间的误差向量的欧几里得距离小于一搜寻半径γ 的平均码元向量x ，即候l
选码元向量集合Ω。每一层丛集搜寻所用的搜寻半径皆不同，搜寻半径的设定方式于后详述。第l层(1＜l≤L)丛集搜寻所使用的限制条件表示如下式(1)，候选码元向量集合l
Ω 表示如下式(2)：
[0062] ||y-Hxl，i||＜γl (1)
[0063]
[0064] 首先，在步骤104中，多输入多输出检测方法10进行最上层的丛集搜寻，搜寻符合L，i L L初始限制条件||y-Hx ||＜γ 的候选码元向量集合Ω。步骤106至步骤110描述逐层丛集搜寻，以下叙述皆以第l层称之。在步骤106中，多输入多输出检测方法10根据候选L
码元向量集合Ω，产生对应于N-QAM星座图的多层级架构的下一层，即第(l-1)层的搜寻l-1 l l，i
空间∏ 。详细来说，候选码元向量集合Ω 中每一平均码元向量x 于第(l-1)层将延伸出的 个平均码元向量，又称为丛集Cl，i，因此，搜寻空间∏l-1等于多个丛集Cl，i的集合。
选择候选码元向量集合也就是选择候选丛集。
[0065] 接下来，于步骤108中，多输入多输出检测方法10确认搜寻空间∏l-1所对应的N-QAM星座图的多层级架构的层级，以确认丛集搜寻阶段是否完成。若此时(l-1)＝1，表1
示搜寻空间∏ 已对应于N-QAM星座图的多层级架构的最底层，丛集搜寻阶段已完成。若此l-1
时(l-1)≠1，表示搜寻空间∏ 尚未进行到多层级架构的最底层，多输入多输出检测方法
10回到步骤106，重复进行步骤106至步骤110的循环运作，直到产生的搜寻空间对应至最底层为止。在丛集搜寻阶段中，多输入多输出检测方法10利用限制条件搜寻候选码元向量l l
集合Ω，候选码元向量集合Ω 中所有平均码元向量在经过信道后，与接收讯号y之间的l
误差向量的欧几里得距离皆小于搜寻半径γ。换言之，多输入多输出检测方法10删除了不符合限制条件的平均码元向量，逐层限缩搜寻空间。
[0066] 于丛集搜寻达到最底层时，多输入多输出检测方法10进入精确搜寻阶段，以产生最后的输出讯号，即估测的传送讯号。步骤112进一步包含两种产生输出讯号的方法，分别可产生硬决定(Hard-Decision)输出讯号或软决定(Soft-Decision)输出讯号。以产生硬1
决定输出讯号而言，步骤114是于最底层的搜寻空间∏ 中，利用最大相似度算法，于搜寻
1
空间∏ 中选择经过信道效应后与接收讯号y之间的误差向量具有最小欧几里得距离的码元向量 即硬决定输出讯号。最后选择的码元向量 表示如下：
[0067]
[0068] 另一方面，本发明亦可产生软决定输出讯号，以配合多输入多输出检测器后端的维特比译码器(Viterbi Decoder)。在此情形下，步骤112是计算经过通道的搜寻空间∏1中所有码元向量与接收讯号y之间的误差向量的欧几里得距离，并根据所有误差向量的欧几里得距离的大小值，对搜寻空间∏1中所有码元向量进行排序，接着选择其中K个码元向量以产生软决定输出讯号，这K个码元向量对应于最小的K个误差向量的欧几里得距离。举例来说，本发明实施例选择4个码元向量(x1，1，x1，2，x1，3，x1，4)，其对应于所有误差向量的欧几里得距离中，最小的4个欧几里得距离(d1，d2，d3，d4)。4个码元向量(x1，1，x1，2，x1，3，x1，4)所产生的软决定的输出讯号 表示如下：
[0069]
[0070] D＝w1+w2+w3+w4 (5)
[0071]
[0072] 请参考图4，图4为多输入多输出检测方法10用于一64-QAM星座图的多层级架构的示意图。为方便说明，图4仅表示传送讯号中对应于一传送天线的一元素。由图4可知，64-QAM星座图的多层级架构分为三层，搜寻空间逐层限缩；最后，于进行精确搜寻时，对应于64-QAM星座图的最底层的码元向量集合仅留下16个码元向量。如第一层中的实点。因此，多输入多输出检测方法10仅对这16个码元向量进行比对。以效能最佳的最大相似度算法而言，其须对所有的码元向量进行比对；相较之下，本发明实施例通过丛集搜寻阶段及精确搜寻阶段检测传送码元向量，大幅减少了搜寻空间，进而降低系统的复杂度。
[0073] 多输入多输出检测方法10中搜寻半径γl的设定方式如下。在此先定义一误差l，c l，c l，i l，i向量v ＝(x -x )，x 为对应于N-QAM星座图的多层级架构的第l层的一平均码元向l，c
量，对应于N-QAM星座图最底层的第i区块；x 是由N-QAM星座图最底层的第i区块的四个边界星座点所合成的码元向量， 每一平均码元向量xl，i皆对应至 个误
差向量。请参考图5，图5为一误差向量的示意图。图5描述对应于64-QAM星座图的第三层的一平均码元向量x3，i(如图中方点)其中一元素所对应的四个误差向量v3，1，v3，2，v3，3，v3，4，以及第二层的一码元向量x2，i(如图中星点)其中一元素所对应的四个误差向量v2，1，v2，2，v2，3，v2，4。在不考虑可加性白色高斯噪声的情形下，平均码元向量xl，i经过信道后，与接收讯号y之间的误差向量 的欧几里得距离表示如下：
[0074] ||z||＝||y-Hxl，i||＝||Hxl，k-Hxl，i||＝||H(xl，k-xl，i)||≤||Hvl，c||(7)[0075] 在传送讯号空间中，平均码元向量xl，i所对应的误差向量vl，c的长度皆相同，然l，c而，多输入多输出系统的信道各有不同的增益，在接收讯号空间中误差向量v 的长度不再l
相同，因此误差向量z的欧几里得距离的最大值d 表示如下：
[0076]
[0077] 本发明考虑噪声的影响，令第l层的丛集搜寻的搜寻半径γl为误差向量z的欧几里得距离的最大值dl与一噪声抑制参数αl的乘积，γl＝αl·dl，αl是大于1的实数。越上层的丛集搜寻，其搜寻半径越大，因此噪声抑制参数对于提升效能的效果也越明显。
[0078] 在此请注意，多输入多输出检测方法10于第l层中选择符合限制条件||y-Hxl，i||＜γl的平均码元向量xl，i时，是计算每一误差向量z的完整欧几里得距离以决定平均码元向量xl，i是否符合限制条件。在传送天线的数量增加的情形下，为了计算完整的欧几里得距离，多输入多输出系统的运算量势必大增。因此，本发明进一步提出一分支定界(Branch and Bound)方法，藉由计算误差向量z的部分欧几里得距离，删除不符限制条件的平均码元向量xl，i以更快速地减少搜寻空间。分支定界方法的数学原理简述如下。首先，本发明利用QR分解法，将通道矩阵H分解为一正交矩阵Q与一上三角矩阵R的积。误差向量z的欧几里得距离表示如下：
[0079] ||z||＝||y-Hxl，i||＝||y-QRxl，i||＝||y′-Rxl，i||＜γl (9)
[0080] 上述式(9)中，z＝y′-Rxl，i以矩阵表示如下：
[0081]
[0082] 上述式(10)中，误差向量z中每一元素的欧几里得距离表示如下：
[0083]
[0084] 部分误差向量z(j)及相对应的部分欧几里得距离表示如下：
[0085]
[0086]
[0087] 由式(9)及式(13)可知，符合限制条件的平均码元向量xl，i必使下列各式成立：
[0088]
[0089]
[0090]
[0091]
[0092] 由上可知，分支定界方法总共进行NR层搜寻。请参考图6，图6为本发明实施例一分支定界方法20的流程图。分支定界方法20用于图3的多输入多输出检测方法10的步骤104及步骤110中，以选择符合限制条件的平均码元向量。分支定界方法20包含有以下步骤：
[0093] 步骤200：开始。
[0094] 步骤202：进行对应于该搜寻空间中一平均码元向量的一部分欧几里得距离运算程序，计算该平均码元向量经过信道后，与一接收讯号之间的一误差向量的一部分欧几里得距离。
[0095] 步骤204：比较该部分欧几里得距离及一搜寻半径，以产生一比较结果。若该比较结果显示该部分欧几里得距离大于该搜寻半径时，进行步骤206；反的，进行步骤208。
[0096] 步骤206：停止该部分欧几里得距离运算程序，并排除该平均码元向量于该候选码元向量集合之外。
[0097] 步骤208：判断该部分欧几里得距离运算程序是否已计算至完整的欧几里得距离；若是，进行步骤210；反之，回到步骤202，并增加该误差向量的一元素至该部分欧几里得距离的运算程序中。
[0098] 步骤210：选择该平均码元向量作为该候选码元向量集合其中一候选码元向量。
[0099] 步骤212：结束。l l，i
[0100] 于步骤202中，分支定界方法20进行对应于搜寻空间∏ 中一平均码元向量xl，i的部分欧几里得距离运算程序，也就是计算平均码元向量x 经过信道后，与接收讯号y之(j)
间的误差向量z的部分欧几里得距离||z ||，如式(13)所示。在此请注意，本发明实施例由最小的部分欧几里得距离开始计算，于每次进行部分欧几里得距离运算程序时，逐一增加部分欧几里得距离所包含的元素数量，因此下述说明以最小的部分欧几里得距离的计算开始。
l，i
[0101] 首先，分支定界方法20计算平均码元向量x 经过信道后，与接收讯号y之间的误差向量z的部分欧几里得距离 接着于步骤204中，将部分欧几里得距离 与l
搜寻半径γ 进行比较，如式(14)所示。若比较结果显示误差向量z的部分欧几里得距l l，i
离 已大于搜寻半径γ，分支定界方法20确知平均码元向量x 必定不符合限制条
件，因此进行步骤210，停止部分欧几里得距离的运算程序，换言之即排除平均码元向量xl，i作为候选码元向量的可能性。另一方面，若比较结果显示误差向量z的部分欧几里得距l
离 小于搜寻半径γ，于步骤206中，进一步判断部分欧几里得距离的运算程序是否已计算至完整的欧几里得距离。因多输入多输出系统包含有多个接收天线，分支定界方法
20必再次进行部分欧几里得距离运算程序，回到步骤202，于部分欧几里得距离运算程序中增加误差向量z中一元素 以计算误差向量z的部分欧几里得距离 再与搜寻
l
半径γ 进行比较，依此类推。当部分欧几里得距离运算程序进行至完整的欧几里得距离(1) (1) l l，i
||z ||并确认||z ||小于搜寻半径γ，分支定界方法20选择平均码元向量x 作为一候选码元向量。
[0102] 在此请注意，分支定界方法20是说明对应于单一平均码元向量的部分欧几里得l距离运算程序。在实作上，本发明以广度优先方式，同时对搜寻空间∏ 中所有的平均码元l
向量进行同一层级的部分欧几里得距离运算程序，最终产生候选码元向量集合Ω。由于分l，i
支定界方法20仅计算误差向量的部分欧几里得距离即能得知平均码元向量x 是否符合限制条件，因此可降低系统运算的复杂度，更快速地减少搜寻空间。
[0103] 对分支定界方法20而言，各层丛集搜寻中符合限制条件的候选码元向量集合的大小不是固定值，系统的复杂度仍有改进空间。本发明进一步对分支定界方法20所产生的候选码元向量集合中所有平均码元向量所对应的误差向量，进行欧几里得距离大小的排序；接着于候选码元向量集合中，选择对应的误差向量的欧几里得距离为最小的K个平均码元向量，形成一最佳候选码元向量集合。简言之，本发明于保留下来的平均码元向量中，固定选择最佳的K个平均码元向量，以有效地降低系统的复杂度。在本发明其它实施例中，各层丛集搜寻所使用的K值可不相同。
[0104] 在多输入多输出检测方法10中，前(L-1)层的丛集搜寻皆利用限制条件搜寻候选码元向量集合。本发明进一步提出一相位决定法，根据接收讯号的相位决定最上层的丛集搜寻的结果，可大幅简化复杂度。请参考图7，图7为本发明另一实施例一多输入多输出检测方法30的流程图。多输入多输出检测方法30包含有以下步骤：
[0105] 步骤300：开始。
[0106] 步骤302：产生(L-1)个平均码元向量集合及(L-1)个搜寻半径，每一平均码元向量集合及每一搜寻半径皆对应于N-QAM星座图的多层级架构中除最底层之外的其中一层，L＝log4N。
[0107] 步骤304：根据一最小均方误差算法处理一接收讯号，以取得一估测的传送讯号及该估测的传送讯号的相位。
[0108] 步骤306：根据该估测的传送讯号的相位，选择对应于N-QAM星座图的多层级架构的最上层的一候选码元向量集合。
[0109] 步骤308：根据该候选码元向量集合，产生对应于N-QAM星座图的多层级架构的下一层的一搜寻空间。
[0110] 步骤310：确认该搜寻空间所对应的N-QAM星座图的多层级架构的层级，若已至N-QAM星座图的多层级架构的最底层，进行步骤314；若位于其它层级，则进行步骤312。
[0111] 步骤312：于该搜寻空间中，选择符合一限制条件的一候选码元向量集合，并回到步骤308。
[0112] 步骤314：根据该搜寻空间，产生一输出讯号。
[0113] 步骤316：结束。
[0114] 步骤304至步骤312描述丛集搜寻阶段，其中步骤304及步骤306描述最上层的丛集搜寻；步骤308至步骤312形成一循环，逐层进行丛集搜寻；步骤310用来确认丛集搜寻阶段完成与否。步骤314描述最底层的精确搜寻阶段。相位决定法分为两阶段，如步骤304及步骤306所示。在步骤304中，相位决定法以最小均方误差算法处理接收讯号y，以取得估测的传送讯号 并计算传送讯号 中各元素的相位 表示如下：
[0115]
[0116]
[0117] 上述式中，I为单位矩阵，σ2为噪声的变异数，估测的传送讯号 中的元素对应于第j支传送天线。以对应于单一天线的一元素而言，N-QAM星座图的多层级架构的最上层的平均码元向量集合根据I-Q平面的第一至第四象限依序表示为A、B、C、D。在步骤308中，相位决定法根据估测的传送讯号 的相位 选择候选码元向量集合L
Ω。详细来说，相位决定法是根据传送讯号 其中一元素 的相位 所在的范围，
选择平均码元向量集合{A，B，C，D}其中二个或三个平均码元向量(以下称二相位决定法L
或三相位决定法)，作为候选码元向量集合Ω 中一平均码元向量
L，i L，i L，i L，i
其中一元素xj 所有可能的值。定义Δ2(xj )及Δ3(xj )为元素xj 所有可能的码元L，i
向量的组合，分别为平均码元向量集合{A，B，C，D}中四取二或四取三所得。Δ2(xj )及L，i
Δ3(xj )与对应的元素 所在的范围如下：
[0118]
[0119]
[0120] 由式(20)可知，若本发明使用二相位决定法选择候选码元向量集合ΩL，候选码元L L，i向量集合Ω 中的平均码元向量xL，i的每一元素皆可能为Δ2(xj )其中一种组合的一元L
素；因此，候选码元向量集合Ω 共包含有 个平均码元向量。同理，若本发明使用三相位L L
决定法选择候选码元向量集合Ω，候选码元向量集合Ω 将包含有 个平均码元向量。在此请注意，多输入多输出检测方法30可依照系统的需求，选择运用二相位决定法或三相位决定法进行最上层的丛集搜寻。在天线数增加及使用高维度正交振幅调制的情形下，使用三相位决定法比使用二相位决定法所得到的效能要好。于最上层的丛集搜寻完成之后，步骤308至步骤312所描述的逐层丛集搜寻及步骤314的精确搜寻阶段，与多输入多输出检测方法10的步骤106至步骤112相同，在此不赘述。
[0121] 多输入多输出检测方法10及多输入多输出检测方法30的差异仅在于最上层的丛集搜寻的方法不同。以多输入多输出检测方法10而言，最上层的丛集搜寻为步骤104；以多输入多输出检测方法30而言，最上层的丛集搜寻为步骤304及步骤306，皆为了选择对应于N-QAM星座图的多层级架构的最上层的候选码元向量集合。
[0122] 关于上述多输入多输出方法10的硬件实现，请参考图8，图8为本发明实施例一多输入多输出检测器40的功能方块图。多输入多输出检测器40用于一NT×NR多输入多输出系统的一接收机，NT×NR多输入多输出系统使用N-QAM调制欲传送的数据流。多输入多输出检测器40包含有一接收端400、一平均码元向量集合产生单元402、一搜寻半径产生单元404、一丛集搜寻单元406及一精确搜寻单元408。关于多输入多输出检测器40中各单元的详细运作，请参考多输入多输出检测方法10的介绍，在此仅简述。
[0123] 接收端400用来接收接收讯号y，其是多输入多输出接收机的接收天线阵列所接收的讯号 平均码元向量集合产生单元402及搜寻半径产生单元404用来进行多输入多输出检测方法10的步骤102。平均码元向量集合产生单元402l
产生对应于N-QAM星座图的多层级架构除最底层之外的每一层的平均码元向量集合X(1＜l≤L)。搜寻半径产生单元404耦接于平均码元产生单元402及多输入多输出接收机所包含的一信道估测单元42，信道估测单元42用来产生一通道矩阵H，搜寻半径产生单元404l
产生对应于N-QAM星座图的多层级架构除最底层之外的每一层的搜寻半径γ(1＜l≤L)。
[0124] 丛集搜寻单元406用来进行第一阶段的丛集搜寻，包含有一候选码元向量集合产生单元410、一搜寻空间产生单元412及一确认单元414。候选码元向量集合产生单元410耦接于接收端400、平均码元向量集合产生单元402、搜寻半径产生单元404、信道估测单元42、确认单元414及搜寻空间产生单元412；候选码元向量集合产生单元410用来进行步骤l
104及步骤110，在对应于N-QAM星座图的多层级架构其中第l层的一搜寻空间∏ (包含L L l
初始搜寻空间∏ ＝X 以及搜寻空间∏ ，1＜l＜L)中，选择符合一限制条件的一候选码l
元向量集合Ω。搜寻空间产生单元412耦接于平均码元向量集合产生单元402及候选码l
元向量集合产生单元410，用来进行步骤106，根据选码元向量集合Ω 产生对应于下一层l-1
的一搜寻空间∏ 。确认单元414耦接于搜寻空间产生单元412，用来进行步骤108，确认搜寻空间所对应的层级，以决定进入第二阶段的精确搜寻或进行下一层的丛集搜寻。精确搜寻单元408耦接于接收端100、信道估测单元42及确认单元414，用来进行第二阶段的丛l-1
集搜寻，于确认单元414确认搜寻空间∏ 所对应的N-QAM星座图的多层级架构的层级已至最底层(l-1＝1)时，根据搜寻空间产生一输出讯号。
[0125] 进一步地，候选码元向量集合产生单元410所包含的单元可用来进行前述的分支界定方法20，候选码元向量集合产生单元410包含有一部分欧几里得距离运算单元420、一比较单元422、一判断单元424、一第一选择单元426及一第二选择单元428。部分欧几里得距离运算单元420耦接于接收端400、平均码元向量集合产生单元402、信道估测单元42及确认单元414，用来进行分支界定方法20的步骤202，以计算误差向量的部分欧几里得距离。比较单元422耦接于部分欧几里得距离运算单元420及搜寻半径产生单元404，用来(j) l进行步骤204，比较部分欧几里得距离||z ||及搜寻半径γ 以产生一比较结果。判断单元424耦接于部分欧几里得距离运算单元420，用来进行步骤206，判断部分欧几里得距离(1)
运算单元420所进行的运算程序是否已计算至完整的欧几里得距离||z ||，以产生一判断结果。第一选择单元426耦接于比较单元422及判断单元424，用来根据比较结果及判断l
结果，选择候选码元向量集合Ω。第二选择单元428耦接于第一选择单元426，用来由候l
选码元向量集合Ω 中，进一步选择对应的误差向量的欧几里得距离为最小的K个平均码元向量，形成一最佳候选码元向量集合。
[0126] 此外，关于上述多输入多输出方法30的硬件实现，请参考图9，图9为本发明实施例一多输入多输出检测器50的功能方块图。多输入多输出检测器50包含与多输入多输出检测器40相同的所有单元，并还包含有一相位决定单元500。在多输入多输出检测器50中，相位决定单元500用来选择对应于N-QAM星座图的多层级架构的最上层的一候选码元向量L l集合Ω ；除了最上层之外的其它层级的候选码元向量集合Ω(1＜l＜L)，由多输入多输出检测器50中的丛集搜寻单元406完成。相位决定单元500包含有一运算单元502及一选择单元504。运算单元502耦接于接收端400及信道估测单元42，用来进行多输入多输出方法30的步骤304，根据最小均方误差算法处理接收讯号y，以取得一估测的传送讯号及其相位。选择单元504耦接于运算单元502，用来根据估测的传送讯号的相位，选择候选码L
元向量集合Ω。因此，多输入多输出检测器50中的搜寻空间产生单元412除了耦接于平均码元向量集合产生单元402及候选码元向量集合产生单元410之外，还耦接于相位决定单元500。关于多输入多输出检测器50中各单元的详细运作，请参考多输入多输出检测方法30以及上述多输入多输出检测器40，于此不再赘述。
[0127] 综上所述，本发明实施例的多输入多输出方法及多输入多输出检测器利用N-QAM星座图所具有的多层级架构特性，于接收讯号空间中进行多层丛集搜寻以快速限缩搜寻空间，并以最后一层的精确搜寻产生输出讯号，供后端译码使用。此外，本发明所提出的分支界定方法，选择最佳的K个候选码元向量的方法及相位决定方法，可进一步降低丛集搜寻的系统复杂度，提升多输入多输出检测的效能。
[0128] 以上所述仅为本发明的较佳实施例，凡依本发明的权利要求所做的均等变化与修饰，皆应属本发明的涵盖范围。
