CN107094063B - 半穷举迭代块解码方法和设备 - Google Patents

Abstract

本发明的实施例提供了用于在通信系统中对通过传输信道接收的信号进行解码的解码器，所述信号携带从给定字母表选择的并且与信号向量相关联的信息符号，所述传输信道由信道矩阵表示，其中所述解码器包括：‑子块划分单元(301)，其被配置为对应于与所述信道矩阵有关的矩阵的划分，将所述接收的信号向量划分为子向量的集合，‑候选集合估计单元(305)，用于递归地确定发送的信号的对应于所述子向量的子块的候选估计，给定子块的每个估计可以从先前处理的子块的至少一个候选估计确定，‑信号估计单元(306)，用于从针对所述子块确定的所述候选估计来计算发送的信号的估计。

Description

半穷举迭代块解码方法和设备

背景技术

一般来讲，本发明涉及数字通信，具体来讲，本发明涉及用于解码接收的数据信号的方法、系统和计算机程序产品。

近年来，无线通信系统已经正在加速增长，从而变成现代模式的通信的中心组件。

现在有不同无线通信系统可用，诸如适应使用单个或多个天线的单个或多个发射机/接收机(诸如MIMO(多输入多输出)系统)的蜂窝和无线自组织网络。无线MIMO通信系统指的是在发射机一侧和接收机一侧与多个天线的无线链路。

MIMO系统在富分散无线信道上的重大发展是由于它们满足通信可靠性和无线网络上的数据速率方面的增长需求的能力。

已经建议了很多解码器用于取回在这些无线通信系统上发送的信号流，其在数据速率和可靠性方面具有提高的性能。但是，这些解码器的主要挑战是复杂度成本。为了保证实时和高吞吐量应用的部署，需要满足规定的计算复杂度的编码操作和解码算法，所述计算复杂度对于给定设备和应用是固定的。

例如，最大似然(ML)解码器，诸如球解码器(E.Viterbo and E.Biglieri.Auniversal decoding algorithm for lattice codes.In Quatorzieme colloqueGRETSI,1993)或Schnorr Euchner解码器(C.P.Schnorr and M.Euchner.Lattice BasisReduction:Improved Practical Algorithms and Solving Subset Sum Problems.InMath.Programming,pages 181–191,1993)是要求天线数量中的指数复杂度的优化解码器(B.Hassibi and H.Vikalo.On the sphere-decoding algorithm i.expectedcomplexity.Signal processing,IEEE Transactions on,53(8):2806–2818,Aug 2005)。

这些解码器已经被适配以便根据两个不同方法，以复杂度和性能之间的权衡的方式以性能降级为可能的代价降低它们的复杂度。在第一方法中，该解码器以基于节点修剪的树搜索算法为基础，其被配置为在每一层中丢弃一些与低可能性引起优化求解方案的函数相关联的节点(以及它们的子节点)。根据所述第一方法操作的示例性解码器包括，例如：

-概率性树修剪球解码(Byonghyo Shim and Insung Kang.Sphere decodingwith a probabilistic tree pruning.Signal Processing,IEEE Transactions on,56(10):4867–4878,Oct 2008；Tao Cui,Shuangshuang Han,and C.Tellambura.Probabilitydistribution-based node pruning for sphere decoding.Vehicular Technology,IEEETransactions on,62(4):1586–1596,May 2013)

-k-最佳算法(Qingwei Li and Zhongfeng Wang.Improved k-best spheredecoding algorithms for mimo systems.In Circuits and Systems,2006.ISCAS2006.Proceedings.2006IEEE International Symposium on,pages 4pp.–1162,May2006)；以及

-增加半径算法(R.Gowaikar and B.Hassibi.Statistical pruning for nearmaximum likelihood decoding.Signal Processing,IEEE Transactions on,55(6):2661–2675,June 2007)。

第二方法与迭代解码器有关。迭代解码器基于从代码结构导出的等效信道矩阵形式以确定要被迭代地解码的划分的信号集合。这一迭代方法降低了解码复杂度同时不保持理想的错误性能和完整的分集。

例如，在文章“Won-Joon Choi,R.Negi,and J.M.Cioffi.Combined ML and DFEdecoding for the v-blast system.In Communications,2000.ICC 2000.2000IEEEInternational Conference on,volume 3,pages 1243–1248 vol.3,2000”中，信道矩阵被分割为两个块，第一个块具有尺寸q。在尺寸q的第一块上执行ML解码方案，同时给定在第一块上执行的ML解码的输出，将决策反馈均衡器(也称为ZF-DFE)应用于剩余系统(即，从接收的信号减掉该ML输出)。即使这一求解方案提高性能，但是该解码是次优化的并且不确保目标分集阶数。

另一种求解方案，提出了空间-时间编码系统，其可以与球解码器兼容，主要在于将接收的信号划分到每个具有给定基数λ的数量L(L≥2)个子集中。给定信号点集合中的另一个，执行关于信号点集合中的一个的似然函数的有条件的最大化。这包括：

-根据接收的信号的划分将该等效信道矩阵划分到L个子矩阵中；

-根据给定标准在接收的信号的L个子集中选择信号集合；

-针对从该字母表取用的剩余L-1个子集的所有可能值，在移除子集间干扰之后执行所选择信号子集的有条件的ZF(ACZF)或ZF-DFE(ACZF-SIC)检测(在下文中也称为“解码”)；

-从全部计算出的求解方案中选择对应于接收的信号和估计出的之间的最小化的Euclidean距离的一个优化方案。

以剩余信号子集的值为条件对要被检测的(在下文中也称为“解码的”)信号集合的选择对算法性能有影响。启示来自于S.D.Howard,S.Sirianunpiboon,andA.R.Calderbank.Low Complexity Essentially Maximum Likelihood Decoding ofPerfect Space-Time Block Codes.In Acoustics,Speech and Signal Processing,2009.ICASSP 2009.IEEE International,a selection criterion for n×n space-timecoded systems using the Perfect codes has been proposed in L.P.Natarajan andB.S.Rajan.An Adaptive Conditional Zero-Forcing Decoder with Full-diversity,Least Complexity and Essentially-ML Performance for STBCs.In InformationTheory and its Applications(ISITA),2012International Symposium on,pages 235–239,Oct 2012,所公开的工作，尤其是针对a 2x2MIMO系统使用黄金代码,3x3以及4x4配置。

因此，在上述第二步骤中选择的信号集合是对应于整体分割的子矩阵的协方差矩阵的最大行列式的等效信道矩阵的分割的子矩阵。此外，涉及使用的空间-时间块编码的特性的该等效信道矩阵的子矩阵的特性上的充分条件已经L.P.Natarajan andB.S.Rajan.An Adaptive Conditional Zero-Forcing Decoder with Full-diversity,Least Complexity and Essentially-ML Performance for STBCs.In InformationTheory and its Applications(ISITA),2012International Symposium on,pages 235–239,Oct 2012.中公开。这些充分条件之一强制了为了实现ACZF或ACZF-SIC解码下的完全分集阶数，L子矩阵的至少一个应该是满秩的。

虽然现有的子检测方法提供了比次优化线性和非线性联合解码方案更好的性能，但是它们不允许在实现降低复杂度的同时控制分集阶数。

发明内容

为了解决这些和其它问题，提供了用于对通过通信系统中的传输信道接收的信号进行解码的解码器，该信号携带从给定的值的集合选择的并且与信号向量相关联的信息符号，该传输信道由信道矩阵表示，该解码器包括：

-子块分区单元，其被配置为对应于与所述信道矩阵有关的矩阵的划分将接收的信号向量划分为子向量的集合，

-候选集合估计单元，其用于递归地确定发送的信号的对应于所述子向量的子块的候选估计，给定子块的每个估计可以根据先前处理的子块的至少一个候选估计确定，

所述候选集合估计单元被配置为通过应用使用针对先前处理的子块确定的估计的解码算法的至少一次迭代，从而确定发送的信号的至少一个子块的候选估计的集合，针对所述子块确定的候选估计的数量严格低于给定的值的集合的基数，该解码器还包括信号估计单元，其用于根据针对所述子块确定的所述候选估计来计算发送的信号的估计。

在一个实施例中，该解码器可以被配置为通过执行来自该信道矩阵的QR分解来预先确定正交矩阵Q和上三角矩阵R，并且该子块划分单元被配置为将该上三角矩阵R划分为若干个上三角子矩阵和若干个矩形矩阵，上三角子矩阵的数量高于或等于二，该子块划分单元被配置为将接收的信号向量划分为子向量的集合，使得接收的信号向量的每个子向量对应于所述上三角子矩阵之一。

然后，该解码器可以被提供用于通过将该正交矩阵的转置矩阵乘以接收的信号来确定接收的信号向量。

具体来讲，该解码器还可以被布置用于通过置换该信道矩阵的行或列来确定来自该信道矩阵的置换矩阵集合，以及执行每个置换矩阵的QR分解以确定中间的上三角矩阵，该解码器被配置为根据与针对每个置换矩阵获取的中间上三角矩阵的分量有关的标准来选择所述置换矩阵之一，该子块划分单元被配置为将该上三角矩阵R划分为对应于所选择的置换矩阵相关联的中间上三角矩阵。

在某些实施例中，该解码算法可以是格解码算法。

具体来讲，该解码算法可以被配置为求解关于一门限的每个块的累积度量的条件。

该解码算法可以是顺序解码算法，并且该门限是该顺序解码算法的累积度量门限。

另外，该解码算法可以是球约束解码算法，并且该门限是该球约束解码算法的球的初始半径。

在一个实施例中，该门限可以根据目标服务质量指示符来确定。

该目标服务质量指示符可以是目标分集阶数。

具体来讲，该解码器还可以包括门限估计单元，其被配置为确定每个子块的解码的门限。

门限估计单元可以被配置为根据该目标分集阶数以及根据从由以下项构成的分组当中选择的至少一个其它参数来确定门限：信噪比的估计、接收的信号的维度和所述子块的维度。

门限估计单元可以包括查找表，其存储针对每一个值的多元组的门限的值，所述每一个值的多元组包括该目标分集阶数的值和至少一个其它参数。

在一个实施例中，子块的数量可以等于二，并且查找表的门限值可以是根据对应于第一子块的所选路径在由解码算法实现的树搜索过程中没有被访问到的概率确定的，该解码算法应用于第一子向量来确定该第一子块的候选估计和所述信噪比。

门限估计单元可以被配置为取决于与至少一个其它信号的解码有关的统计数据来更新该查找表。在某些实施例中，每个候选估计的集合可以是按照针对每个估计获取的累积度量的增加值来进行排序的数据结构。

候选集合估计单元还可以被配置为取决于与至少一个子块相关联的候选估计的目标数量，进一步降低所述子块的当前的候选估计集合中确定的候选者数量。

与子块相关联的候选估计的目标数量可以根据先前处理的子块的候选估计的数量来进行确定。

与子块相关联的候选估计的目标数量可以是先前处理的子块的候选估计的数量的乘法函数，该乘法函数具有低于一的斜率系数。

候选集合估计单元还可以包括通过应用根据预定义标准选择的优化的或次优化的解码算法来确定上一个处理的子块的一个估计。

所述优化或次优化解码算法可以从由以下项构成的分组当中进行选择：ML解码算法(优化解码算法)、ZF-DFE解码算法、以及MMSE解码算法(ZF-DFE解码算法和MMSE解码算法是次优化解码算法)。该ML解码算法尤其可以是任何有优化格解码算法。

在某些实施例中，该信号估计单元可以被配置为确定最小化目标度量的估计的多元组，每个多元组估计包括来自针对该信息符号的子块获取的候选估计的集合的每一个的一个候选估计。

在本发明的一个应用中，通信系统可以是使用空间-时间块编码来对在传输信道上发送的数据信号进行编码的编码系统，该解码器被配置为使用等效信道矩阵来向量化所述信号向量，并且将该等效信道矩阵划分为若干个矩形等效信道子矩阵，每个矩形子矩阵是代表对应于所述接收的信号的、在传输信道上发送的信号的线性离散矩阵的函数。该子块划分单元包括与等效信道矩阵的划分相对应地将接收的信号向量划分为子向量的集合。

该解码器可以被配置为取决于每个等效信道子矩阵与等效信道信道子矩阵的共轭转置乘积的行列式的值来对所述矩形子矩阵重新排序。

本发明还提供用于接收和解码经编码的信号的接收机，该接收机包括根据用于对信号进行解码的前述权利要求中的任一项的解码器。

还提供了一种能够在无线通信网络中发送和接收数据的移动设备，该移动设备包括用于接收的信号的这种接收机。

还提供了对通过通信系统中的传输信道接收的信号进行解码的方法，该信号携带从给定的值的集合选择的并且与信号向量相关联的信息符号，该传输信道由信道矩阵表示，该方法包括：

-对应于与所述信道矩阵有关的矩阵的划分将接收的信号向量划分为子向量的集合，

-递归地确定发送的信号的对应于所述子向量的子块的候选估计，给定子块的每个估计可以从先前处理的子块的至少一个候选估计确定，

所述递归地确定估计的步骤包括，针对至少一个子块，通过应用使用针对先前处理的子块确定的估计的解码算法的至少一次迭代，从而确定发送的信号的该子块的候选估计的集合，针对所述子块确定的候选估计的数量严格低于给定的值的集合的基数，该方法还包括根据针对所述子块确定的所述候选估计来计算发送的信号的估计。

该方法还可以包括：

-通过执行来自该信道矩阵的QR分解来确定正交矩阵Q和上三角矩阵R；

-将该上三角矩阵R划分为若干个上三角子矩阵和若干个矩形矩阵，所述上三角子矩阵的数量高于或等于二，

将接收的信号向量划分为子向量集合的步骤包括对应于所述上三角子矩阵之一来划分接收的信号向量的每个子向量。

还提供了一种用于对通过通信系统中的传输信道接收的信号进行解码的计算机程序产品，该信号携带从给定的值的集合选择的并且与信号向量相关联的信息符号，该传输信道由信道矩阵表示，该计算机程序产品包括：

非暂时性计算机可读存储介质；以及

存储在所述非暂时性计算机可读存储介质上的指令，当所述指令由处理器执行时，使所述处理器：

-对应于与所述信道矩阵有关的矩阵的划分将接收的信号向量划分为子向量的集合，

-递归地确定发送的信号的对应于所述子向量的子块的候选估计，给定子块的每个估计可以根据先前处理的子块的至少一个候选估计确定，

该处理器还通过应用使用针对先前处理的子块确定的估计的解码算法的至少一次迭代，从而确定发送的信号的至少一个子块的候选估计的集合，针对所述子块确定的候选估计的数量严格低于给定的值的集合的基数，该处理器还根据针对所述子块确定的所述候选估计来计算发送的信号的估计。

本发明的各个实施例使得有可能避免常规的穷举搜索，同时提供需要的分集阶数的灵活性和降低的复杂度。

根据对附图和详细描述的审查，本发明的其它优势对于技术人员将会变得清楚。因此任何额外的优势可以被合并到本文中。

附图说明

被并入并且构成这一说明书的一部分的附图示出了本发声明的各个实施例，并且与上面给出的本发明的概述以及下面给出的对实施例的详细描述用于解释本发明的实施例。

图1概要地表示实现该解码方法的示例性通信系统；

图2是表示根据本发明的示例性实施例的空间-时间解码设备的框图；

图3是表示根据本发明的示例性实施例的子块检测设备的框图；

图4是描述了根据某些实施例的解码方法的流程图；

图5是表示根据本发明的另一个实施例的子块检测设备的框图；

图6是表示根据某些实施例的用解码器获得的性能的示意图；

图7表示被划分为两个上三角的示例性上三角矩阵；

图8到图10是示出了在本发明针对编码系统的示例性应用中，针对SNR的不同值获得的示例性经验分布的示意图；

图11示出了表示R矩阵到两个子块中的划分和该符号的子向量的相应解码的示例性树；以及

图12是根据某些实施例的解码器的示例性硬件架构的框图。

图13是示出了根据一些实施例的作为本发明对8x8空间复用系统的示例性应用中获得的信噪比的函数的符号错误率的示意图。

图14是示出了根据一些实施例的作为在本发明对4x4空间复用系统的示例性应用中获得的信噪比的函数的平均计算复杂度的示意图。

具体实施方式

本发明的实施例提供用于根据半穷举和递归方法来对接收的信号进行解码的子块解码方法。根据本发明的实施例的该子块解码方法和设备根据关于信道矩阵H的矩阵划分而对接收的信号y中包含的信息符号进行划分，其提供了信息符号s^(K)的N个分组(在下文中也称为“信息符号的块”)，k的范围从N到1。该信号携带从给定的值的集合选择的信息符号。该值的集合可以是值的有限的并且离散的集合，诸如字母表，或者替代的值的无限集合，诸如，维度n的无线格Zⁿ。

在一个实施例中，接收的信号y中包含的信息符号的划分是对应于将信道矩阵H进行QR分解得到

个子块而获取的上三角矩阵的划分做出的，N至少等于二。下面对某些实施例的描述为了解释说明的目的将参考根据上三角矩阵R的划分而生成信息符号的子块。

子块解码方法递归地对信息符号的每个子块s^(K)进行解码，信息符号的至少一个子块s^(K)的解码包括使用针对先前处理的子块s^(k+1),…,s^(N)确定的候选估计的集合Γ_k+1,…,Γ_N来应用解码算法的至少一次迭代D_k以便确定信息符号的当前子块s^(k)的候选估计集合Γ_k，当前候选集合Γ_k的候选估计

的数量严格低于从中选择所述信息符号的值的集合的基数(例如，字母表的基数)。候选集合Γ_k中存储的每个候选估计代表信息符号的向量。下面对某些实施例的描述将参考从有限的整数值集合(诸如字母表)选择的信息符号。

具体来讲，解码算法D_k可以是格解码算法。在一个实施例中，所述格解码算法可以应用于求解对应于子块s^(K)的累积度量m(s^(k))的门限条件，格解码算法的每个迭代对应于一个候选估计。

在一个实施例中，该门限条件可以关于从目标QoS指示符Q_target(诸如目标分集阶数d_target)获得的

这确保了对目标服务质量指示符更好的控制同时确保降低复杂度。

然后，该信号的估计

可以从候选集合Γ₁,…,Γ_N中存储的估计构造，例如通过选择将总体度量

最小化的值的多元组，该多元组的每个值对应于一个候选集合Γ_i的值。

按照惯例，在下面对本发明的某些实施例的描述中，第一个处理的子块的索引将被称为k＝N，而最后一个处理的子块的索引将会被称为k＝1。根据这一惯例，信息符号的子块s^(K)因此被从k＝N到k＝1递归地处理，k针对信息符号的下一个子块s^(k-1)的处理递减。

在本发明的一个实施例中，所述信息的最后一个子块s⁽¹⁾的解码可以包括通过应用取决于预定义的标准(例如，ML解码标准)的子优化解码算法D₁(诸如ZF-DFE解码算法)只确定该候选集合Γ₁的一个估计。

这提供了可在不同类型的系统中实现的对接收的信号的半穷举递归块解码，诸如在无线或光学通信系统、信号处理系统、密码系统和定位系统等等中。

在本发明对无线通信系统的一个应用中，该通信系统可以包括用于通过通信信道同时发送多个信息符号的至少一个发射机，以及用于接收由该发射机以独立信号的形式发送的符号中的一个或多个的至少一个接收机。该通信信道可以是任何线性AWGN(加性高斯白噪声)信道或使用单载波或多载波调制类型(诸如OFDM(正交频分复用))的多路信道。

该MIMO系统可以呈现发送天线集中在同一个用户处的中央化配置。另外，该MIMO系统可以是发送天线分布在通信网络中并且位于不同用户处的分布式MIMO系统(或多用户MIMO)。这些多用户MIMO配置可以使用在例如应用于例如蜂窝3G、4G和LTE标准的上行链路通信中的移动网络中，或者使用在应用于例如自组织网络(无线传感器网络、机器到机器通信、物联网)的协作式通信中。在这些多用户配置中，该通信系统还可以单独使用或结合诸如时分多址(TDMA)、频分多址(FDMA)、码分多址(CDMA)和空分多址(SDMA)之类的任何多址技术使用。

该通信系统可以另外是单天线多载波通信系统，其使用多载波通信技术来抢占频率选择性信道并管理诸如像IEEE 802.11(WiFi)之类的无线标准中采用的OFDM调制和滤波器组的多载波(FBMC)调制之类的干扰和延迟。

在本发明的其它应用中，该通信系统可以是基于光纤的通信系统，诸如偏分复用-OFDM(PDM-OFDM)系统，其用作例如接入网络、城域网或计算机网络中的电信介质以便生成承认线性(格子)呈现的光学通信信道输出。在这些实施例中，在光发射机设备传送的信息符号可以由根据该光纤的不同偏振状态偏振的光学信号携带。该光学信号可以根据一个或多个传播模式沿着基于光纤的传输信道传播直到到达光学接收机设备。

在对应于光学通信的一些实施例中，可以使用单个波长的激光生成携带信息符号的光学信号。

在其它实施例中，波分复用(WDM)技术可以用在光学发射机设备处以便能够使用多个独立波长来生成光学信号。

在本发明对尤其使用多模式光纤的光学通信的另一个应用中，空分复用技术还可以用于根据各个传播模式来复用信息符号。

此外，诸如WDMA(波分多址)之类的多址技术可以用于针对光学通信系统的应用中。

该无线网络环境可以包括多个能够工作在无线或光学环境中的无线或光学设备，诸如基站、用户设备、终端，每个无线或光学设备包括发射机和/或接收机，它们包括一个或多个天线，每个无线和光学设备通过无线或光学连接与其它无线或光学设备进行通信。

当应用于MIMO解码时，针对单个用户或多个用户检测，接收的信号或信道输出的维度取决于发射机处的信号空间的维度，取决于发送(Tx)天线的数量(n_t)和/或接收(Rx)天线的数量(n_r)。

参考图1，使用MIMO传输的发射机和接收机之间的示例性无线通信系统100，在传输中实现STBC(空间时间块编码)编码以便将调制的符号分布到信道的各个自由角度上。仅仅为了解释说明的目的，图1将参考通信基站进行描述，但是技术人员将很容易地理解可以使用其它类型的无线设备。站的每个发射机2可以根据无线通信系统与另一个站的接收机3交换数据。无线网络100可以依赖于集中式架构(控制器被提供用于控制基站的操作)或去集中式架构(基站可以直接相互通信)。用户终端(诸如无线设备、蜂窝电话、个人数字助理、膝上型计算机、机器人、物联网设备等等)可以在前向链路或反向链路上与一个或多个基站通信。所述用户终端可以是固定的或移动的。

MIMO配置可以是对称的，在这种情况中其包括相同数量(n_t)的发送天线和该数量(n_r)的接收天线。另外，该MIMO配置可以是不对称的，在这种情况总中发送天线的数量(n_t)不同于接收天线的数量(n_r)(尤其是接收机一侧的数量n_r高于发送一侧的数量n_t以避免秩亏损)。

发射机2可以用有噪声的MIMO信道向接收机3发送信号。该数据发射机2尤其可以集成在该基站中。发射机2可以包括例如：

-用于提供卷积码的信道编码器101，

-用于传递符号的诸如QAM调制器之类的调制器102；

-用于传递码字的空间/时间编码器103；

-n_t个传输天线106，每个传输天线与OFDM调制器相关联。

该发射机2使用信道编码器101提供的卷积码将接收的二进制信号编码作为输入。该信号可以由调制器102根据调制方案(例如，正交振幅调制nQAM)来进行调制。该调制器102还可以实现生成复杂符号s_c的调制方案，每个复杂符号属于一个符号分组s_i。因此获得的调制符号然后可以由空间-时间编码器104编码来形成码字STBC，诸如黄金编码("TheGolden Code:A 2x2 Full-Rate Space-Time Code with Non-Vanishing Determinants",J.-C.Belfiore,G.Rekaya,E.Viterbo,IEEE Transactions on Information Theory,vol.51,no.4,pages 1432-1436,April 2005)。该STBC编码可以基于维度n_t*T的复合矩阵，其中，n_t指定传输天线的数量，而T是STBC编码的时长，或者可以基于空间复用(经调制的符号可以直接发送给传输天线)。

因此生成的码字从时域被转换到频域(图1中标注的X)并且分布在n_t个传输天线上。然后，每个专用信号由各自的OFDM调制器调制，并且可选地在滤波、频率变换和放大之后在相对应的传输天线109上发送。

接收机3也可以集成到基站中，接收机3可以被配置为在无线信道中接收由发射机2发送的信号Y_c。该信道可以是有噪声的(例如，具有遭受衰减的加性高斯白噪声(AWGN)的信道)。发射机2发送的信号可以进一步受到由于多路的回声和/或由于具有非零相对速度的发射机和接收机的多普勒效应的影响。

在一个示例性实施例中，接收机3可以包括：

-n_r个用于接收的信号y的接收天线108，每个接收天线与各自的OFDM解调器相关联；OFDM解调器(n_r个解调器)被配置为对在每个接收天线处观察到的接收的信号进行解调并传递解调后的信号。频率/时间转换器可以用于执行传输中实现的时间/频率的转换操作，并且用于在频域中传递信号；

-空间/时间解码器110，其被配置为根据本发明的实施例，根据子块解码方法来传递经解码的信号

-解码器112，其被配置为执行与解码相关联的解调制。

应该注意的是，接收机3实现传输中实现的处理的逆处理。因此，如果在传输中实现的是单载波调制而不是多载波调制，则所述n_r个OFDM解调器由相对应的单载波解调器替代。

本领域的技术人员将很容易地理解，本发明的各个实施例不仅限于具体应用。这一新的解码器的示例性应用包括但并不仅限于多用户通信系统，配置中的MIMO解码可实现在诸如WiFi(IEEE 802.11n)、蜂窝WiMax(IEEE 802.16e)、协作式WiMax(IEEE 802.16j)、长期演进(LTE)、高级LTE、正在开发的5G标准和光学通信之类的无线标准中。

此外，根据本发明的各个实施例的半穷举解码方法和设备可以应用于经编码的和未解码的系统二者。经编码的通信系统使用空间-时间编码(STBC)来在发射机一侧编码数字数据序列，在传输信道上发送的信号包括独立符号的集合，该空间-时间块编码由生成矩阵G表示。在未编码的通信系统中，该生成矩阵等于单位矩阵。

在本发明针对Rayleigh衰减无线多天线系统用于对多天线系统(MIMO)接收的信号进行解码的一个应用中，具有使用空间复用的n_t个发送和n_r个接收天线，数据信号y_c作为复数值向量接收，根据该信道输出的复数值表示给出如下：

y_c＝H_cs_c+w_c (1)

在公式(1)中，

指定根据分布N(0,1)绘制的元素的信道矩阵H的复数值，s_c指定表示发送的数据信号向量的向量s的复数值，并且

指定加性高斯白噪声向量w的复数值。然后可以将接收的信号y_c变换到实数值表示，例如根据公式(2):

在公式(2)中，R(.)和J(.)分别表示复数值输入(向量或矩阵)的实数和虚数部分。

然后，该等效信道输出可以写为：

y＝Hs+W (3)

在使用长度T的空间-时间编码的实施例中，该信道输出可以用与公式(3)相同的形式写出，该等效信道矩阵H_eq给出为：

H_eq＝H_cΦ (4)；在公式(4)中，

对应于基础代码的编码矩阵。为了便于显示并且假设未编码和经编码的方案得出相同的实数值格表示，下面的描述将参考n_t＝n_r并且n＝2n_t的空间复用和对称情况。

根据公式(3)中获得的等效系统，接收的信号可以被视为由H生成的并且由噪声向量w扰乱的格子的点。

当要求优化检测时，接收机实现ML解码器，其尝试在给定信道输出和信道矩阵的前提下，根据最小错误概率从H和y中给出的数据来确定初始发送的符号向量的估计

使得：

在公式(5)中，有限子集

代表该信息符号的实数和虚数部分所属于的字母表。例如，使用2^M-ary QAM星座图LAI构造复合信息符号，该字母表是

(

可以代表例如该复合信息符号所属于的M-ary QAM星座图)给出的整数子集。ML检测下的最小错误概率等效于下面给出的最小化问题：

假设使用最小平方估计、优化ML检测之类的估计技术在接收机处完全知道或估计出H的相干系统简化为在H生成的n-维格子中求解最近相邻问题，以便根据公式6的最小化问题搜索到等效的接收的信号y的最近格子点。

因此，该ML检测器(等效的ML解码器)选择在接收的向量y和假定的消息Hs之间产生最小Euclidean距离的符号向量s。该ML检测器代表所选择的字母表中候选向量s上的离散优化问题。在高星座图尺寸和高系统维度(天线数量)的情况中，以穷举方式对ML解决方案的搜索一般要求非常高的复杂度。

实现树搜索策略的顺序解码器使用解码树结构搜索到接收的向量的最近格子点。在将信号向这一顺序解码器进行传输之前，可以使用信道矩阵的QR分集来执行预解码，使得H＝QR，其中Q指定正交矩阵，R指定上三角矩阵。给定Q的正交性，公式(3)可以重写为下面的形式：

通过表示

公式(7)可以重写为：

然后，该ML解码问题相当于求解下面给出的等效系统：

因此该三角形结构R将最近点的搜索简化为顺序树搜索。该树中的节点代表符号s_i的不同的可能值。

图2是根据某些实施例的代表空间时间解码器110的框图。

解码器110可以包括复数到实数转换器201，用于将接收的信号y_c转换为实数值表示，以及QR分解单元206，用于执行信道矩阵的QR分解，使得H＝QR，其中Q指定正交矩阵，而R指定上三角矩阵。解码器110还可以包括修改器单元209，用于将接收的信号向量y重写为等效的接收的信号向量

以及子块检测器(也称为子块解码器)210，其被配置为在块中递归地检测来自根据上三角矩阵R的相对应的划分执行的等效的接收的信号向量

的划分的接收的信号。在某些实施例中，解码器110还可以包括信道矩阵置换单元204，其用于在QR分解之前置换信道矩阵H的列或行。

空间-时间解码器110还可以包括实数到复数转换器211，其被配置为通过将实数值向量

转换为复数值向量

来传递复数值发送信号的估计。该转换操作是在复数到实数转换器201处执行的处理的反转。

参考图3，示出了根据某些实施例的子块解码器210的示意图表示。

子块解码器210可以包括子块分解单元301(也称为“子块划分单元”)，其被配置为：

-将等效接收向量

分解为N个子向量

-与接收的信号向量的划分对应地将所述上三角矩阵R划分为子矩阵。

具体来讲，上三角矩阵R可以被划分为N个上三角子矩阵R^(k),k＝1,…,N和

个矩形子矩阵B^(kj),k＝1,…,N；j＝k+1,…,N。

因此，该向量

被划分为长度l_k的N个子向量

k＝1,…,N，使得

并且

相同的向量划分被应用于符号s的向量以获取长度为l_k的N个子向量s^(k)，k＝1,…,N，使得

因此所述上三角矩阵R被划分为由N个上三角子矩阵R^(k)，k＝1,…,N和

个矩形子矩阵B^(kj),k＝1,…,N；j＝k+1,…,N组成的

个矩阵，使得：

每个上三角子矩阵R^(k)，k＝1,…,N代表维度l_k×l_k的正方形矩阵并且对应于子向量

k＝1,…,N。此外，每个子矩阵B^(kj),k＝1,…,N；j＝k+1,…,N代表维度l_k×l_j的矩形矩阵并且对应于从块j到块k的反馈矩阵。

因此，(8)可以被重写为：

公式(9)的ML解码问题可以因此被重写：

例如，考虑块的数量N＝2，所述R矩阵可以划分如下：

在上面的上三角矩阵R的两个块划分的示例中：

-R⁽¹⁾是尺寸为(n-p)×(n-p)具有实数分量(R⁽²⁾∈R^(n-p)×(n-p))的上三角子矩阵，其中n指定了等效接收的信号的维度

-R⁽²⁾是尺寸为p×p具有实数分量(R⁽¹⁾∈R^p×p)的上三角子矩阵；

-B指定尺寸为(n-p)×p具有实数分量(R⁽²⁾∈R^(n-p)×p)的矩形子矩阵。

因此，相对应的符号向量是尺寸分别为p和n-p的s⁽²⁾和s⁽¹⁾：

应用于这一示例性两块子解码的公式(12)可以重写为：

这一问题可以使用下面的近似公式求解：

应该注意的是，对应于公式(15)的划分可以生成次优化的解码结果，使得公式(15)的解答可以不对应于ML总体解答。

子块检测器210还可以包括至少一个候选集合估计单元305，用于确定每个子块s^(k)的候选估计集合Γ_k，以及符号估计单元306，用于确定来自数据集合Γ₁,…,Γ_N的等效发送信号的估计

现在参考图4，示出了描述根据某些实施例的可以由接收机3执行以便解码接收的信号y的子块解码方法的流程图。

在步骤401中，信道矩阵H_c和接收的信号Y_c可以被转换为实数值矩阵H和实数值接收的信号y。

在步骤402中，执行信道矩阵H_c的QR分解以确定正交矩阵Q和上三角矩阵R。在某些实施例中，可以在执行所述QR分解之前使用任何置换技术来置换信道矩阵H_c，包括将信道矩阵H_c乘以一个置换矩阵。另外，从QR分解获得的上三角矩阵R可以根据其它排序方法来进行排序。

在步骤403中，通过将接收的实数值信号y乘以转置矩阵Q^t来确定所述等效接收的信号

在步骤404中，矩阵R被划分为N个上三角矩阵R^(k)，k＝1,…,N，和

个矩形矩阵B^(kj),k＝1,…,N；j＝k+1,…,N，并且等效信号向量

被划分为N个子向量

相同的向量划分被应用于符号s的向量以获取N个长度为的l_k的子向量s^(k)，k＝1,…,N，使得

解码方法取决于从k＝N开始的子块s^(k)的数量继续进行若干次步骤407到408的迭代，N对应于用于确定与每个子块s^(k)相关联的每个候选集合Γ_k的子块数量(步骤405)。

更具体地，在步骤407中，如果k≠N，则从存储器取回先前估计的候选集合Γ_N,…,Γ_k+1。

然后在步骤408中，使用给定解码算法D_k的若干次迭代来确定Γ_k的候选估计，该算法求解关于第k个块s^(k)的累积度量m(s^(k))的条件，如果k≠N，该条件还取决于先前估计的候选集合Γ_N,…,Γ_k+1。因此候选集合Γ_k包括A_k个值

每个估计对应于格解码算法的迭代。候选集合Γ_k中存储的每个估计代表符号的向量。生成候选集合Γ_k中的候选估计使得候选集合Γ_k中的候选估计的数量严格低于从其生成所述信息符号的值的集合(诸如字母表)的基数。

例如，可以使用枚举ML解决方案(对应于将累积度量m(s^(k))最小化的值)的格解码算法D_k的迭代集合，和满足提供剩余候选估计的选择标准C_k的邻居的集合来确定候选估计。每个候选集合Γ_k可以是按照所述累积度量的增加的值排序的列表，ML解决方案对应于

而所述邻居对应于

如本申请中所使用的，第k个块s^(k)的累积度量m(s^(k))可以定义为：

术语

对应于符号间干扰，如果k≠N，则针对j＝k+1到N的术语

是从Γ₁,…,Γ_N的先前估计知道的。

通过设置

所述累积的度量可以被重写为：

在某些实施例中，格解码算法被配置为在每个迭代处提供对下面关于累积度量的条件的解决方案：

m(s^(k))≤Rth_k (18)在条件(18)中，Rth_k指定针对每个块s^(k)定义的门限。

如果k≠1可以针对k＝k-1指定新的步骤407到408的迭代，以便类似地确定Γ_k-1的候选估计。

如果k＝1，可以使用选择的解码算法D₁，使用先前估计的候选集合Γ_N,…,Γ₂针对最后一个候选集合Γ₁来确定一个或多个候选估计。在一个实施例中，可以使用选择的解码算法D₁(诸如ML或ZF-DFE或MMSE)和选择标准C₁针对最后一个候选集合Γ₁只确定一个候选估计。该候选集合Γ₁因此包括一个值

该选择标准C₁可以关于度量最小化并且可以用于选择解码算法D₁。例如，如果选择标准C₁主要在于选择将该度量最小化的点，则可以应用ML解码算法。否则，如果该选择标准C₁主要在于选择ML点的相邻点，则可以在这一后面的迭代中应用诸如ZF-DFE或MMSE之类的次优化解码。

在某些实施例中，选择标准C₁可以取决于上三角矩阵R的非零结构或上三角矩阵R的正交性。例如，如果该上三角矩阵R是正交的，则ZF(迫零算法)解码足够生成该ML解决方案。

在步骤410中，根据候选集合Γ_N,…,Γ₂,Γ₁构造等效发送信号的估计

在一个实施例中，通过确定将总体度量

最小化的多元组

来构造估计

在步骤411中，实数值向量

可以被转换为复数值向量

以便传递复数值发送信号的估计。

用于在步骤408中估计每个候选集合Γ_k的格解码算法D_k可以是能够求解条件(10)的任何类型的格解码算法，诸如：

-基于“最大似然”解码问题的ML解码算法(也称为“ML”解码)，用于估计在Euclidean距离最小化标准下到观察到的接收的信号最近的向量，诸如基于星座字母表中的所有可能值上的穷举搜索的ML解码方法；

-基于最佳优先树搜索的解码方法，其使用ML优化问题的树表示(解码树)并且只探索具有最小权重而不是预定义的权重约束的路径，诸如顺序、栈或SB-栈解码算法(SB-栈指的是在2008年10月Proceedings of International Conference on Wireless andMobile Computing,pages 322-327中由G.R.Ben-Othman,R.Ouertani和A.Salah的题为“The Spherical Bound Stack Decoder”的文章中介绍的球约束堆解码器)。从根节点开始，解码算法探索所有子节点并且通过将其存储入栈只保留具有满足所述约束的权重的节点。然后生成栈内顶节点的子节点并且计算它们的累积权重。被探索的节点是根据它们的权重搜索的，并且只保留具有最小累积权重的节点。该搜索继续进行直到找到叶节点并返回优化路径s。

-基于深度优先树搜索的解码方法，诸如球约束解码器和Schnorr-Euchner解码器，其使用ML优化问题的树表示(解码树)并且从该解码树的根节点开始，探索第一子节点s_n，然后探索它最近的子节点s_n-1，以此类推直到到达叶节点s₁。给定找到这一第一路径，通过返回树的第二层继续搜索，并探索已经探索过的节点s₂的相邻节点。在找到所有可能路径并且计算它们的相对累积权重之后，输出最短路径。

具体来讲，如果解码算法基于球约束解码算法，则门限R_thk对应于该球的初始半径。如果解码算法是栈算法，则门限R_thk可以对应于关联到该栈中存储的节点的累积权重的限制门限，或者用于存储候选点的数量的第二个栈的尺寸(如果栈解码器使用第二个栈的话)。如果所述格解码算法是SB-栈解码器，则门限R_thk可以另外对应于球半径。

例如，对于N＝2，该解码方案可以只包括使用球约束解码算法的一个或多个迭代的步骤408的一个迭代，该门限R_thk是最小搜索球半径。候选集合Γ₂因此只包括位于确定的球半径之内的格子点。可以生成位于半径为R_thk的球内的近似ML解决方案，并且存储为扩展到针对下一个针对候选集合Γ₁的解码步骤迭代中，其主要在于使用任何类型的解码算法(诸如ML解码)找到先前生成的一个分支的剩余部分。

在本发明对将接收的信号划分为长度分别为p和n-p的两个块S⁽²⁾和S⁽¹⁾的一个示例性应用中，步骤408可以包括应用栈解码算法D₂来确定候选集合Γ₂。该栈解码器首先生成给出系统y₂＝R⁽²⁾s⁽²⁾+w⁽²⁾的ML解码的ML解决方案，并且将第一个点存储在用于存储候选格子点的第二个栈。该栈解码算法继续地递归，其(A₂-1)度量方面邻居的搜索并且将它们存储在第二栈中。因此，该第二栈提供候选集合Γ₂的潜在候选。栈解码算法是在例如2008年10月在A.Salah,G.Othman,R.Ouertani,and S.Guillouard.New soft stack decoder formimo channel.In Signals,Systems and Computers,2008 42nd Asilomar Conferenceon,pages 1754-1758中描述的。

在本发明的将接收的信号划分为长度分别为p和n-p的两个块S⁽²⁾和S⁽¹⁾的另一个示例性应用中，步骤408可以包括应用SB-栈解码算法D₂来确定候选集合Γ₂。该SB-栈解码器是栈解码器的简化复杂度版本。门限R_thk对应于在用于以高概率寻找的接收向量为中心的初始半径r，至少一个格子点包括该ML解决方案。这一半径可以被确定为以高概率寻找包括ML解决方案的格子点集合A₂，以及其(A₂-1)度量方面的邻居。通过将半径(R2是Λ的生成矩阵)的半球内包含的格子点的数量表示为N_p(N_p＝A₂)，该初始半径r(r＝R_thk)满足：

在公式19中，vol(Λ)＝det(R₂)和V_p指定实数空间

中单元半径球的体积

这一半径保证只针对N_p的高值找到N_p个格子点。

另外，通过使用基于使用的星座形状获得的球内部的有效数量N_e个点和乘法的星座依赖因数α_Α(例如，

α_16QAM＝4和

)，列表中的格子点的有效数量如下关于该球的半径：

在公式20中，β指定确保我们在球内部找到所需要的N_p个格子点的额外因数。

在本发明将接收的信号划分为长度分别为p和n-p的两个块s⁽²⁾和s⁽¹⁾的又另一个示例性应用中，步骤408可以包括应用球约束解码算法D₂来确定候选集合Γ₂。为了得到A₂格子点，该算法以接收的向量为中心第一次运行以便在该球半径r内找到ML向量。然后，以这一解决方案为中心，该算法重新开始寻找其A₂-1邻居。

另外，步骤408还可以包括基于经验和或统计数据减少每个候选集合Γ_k中维护的候选的数量。在每个候选集合Γ_k是按照累积度量的增加值排序的实施例中，这些统计数据可以从每个候选值秩在数据流的先前解码上的出现来确定。

另外，每一块的门限R_thk可以基于这一统计数据来更新以便限制每个候选集合Γ_k中生成的候选的数量。

在另一个实施例中，步骤408可以包括，针对每个子块s^(k)：

-预先确定候选集合Γ_k中要维护的候选估计的目标数量A_k为先前候选集合Γ_k+1的候选数量A_k+1的函数(例如，A_k＝α.A_k+1类型的线性或乘法函数，斜率系数α低于1)，并且

-通过应用解码算法D_k减少获取的候选估计的数量。

在某些实施例中，步骤480处使用的用于枚举候选集合Γ_k的候选点的门限R_thk可以是目标服务质量指示符Q_target(在下文中也称为“QoS指示符”)的函数。具体来讲，该目标服务质量指示符Q_target可以是目标分集阶数，其可以达到d_target。通过取决于目标服务质量指示符Q_target用门限R_thk限制在步骤408的每次迭代处要枚举的候选点的数量，这确保目标服务质量指示符可以有效地达到或实现。门限R_thk可以是每一块k定义的门限或者针对块的集合或所有块s^(k)定义的门限。

如本申请中所使用的，表达式“目标服务质量指示符”指的是关于要实现的目标QoS的参数，诸如目标分集阶数、目标解码器复杂度、目标错误概率等等。仅仅为了解释说明的目的，下面对本发明的某些实施例的描述将主要参考由目标分集阶数代表的目标QoS指示符。

参考图5，解码器110可以包括门限估计单元500，其包括查找表501，被配置为从下面的方面提供每个数据集合Γ_k的估计的门限R_thk的值：

-QoS指示符Q_target，

-接收的信号的维度n(对于未编码系统等于2n_r，或者对于经编码系统等于2n_rT，T对应于空间时间编码的时间维度)，以及

-信噪比(SNR)。

该SNR可以由候选集合估计单元305中或者更一般地解码器110中提供的SNR估计单元504估计。该门限估计单元500还可以包括查找表管理器501，用于基于在先前数据流的解码期间收集到的统计数据来更新该查找表。

在解码器110接收对应于目标分集阶数d_target的目标QoS指示符Q_target并且应用所述接收的信号到数量N＝2个子块的子块解码的实施例中，已经发现该查找表的门限值可以从所选择的对应于该第一子块的路径不会在由如下解码算法实现的树搜索过程中访问到的概率预先确定，所述解码算法应用于该第一子向量来确定该第一子块的候选估计和信噪比，并且具体通过求解下面公式：

在公式21中，σ²指定噪声方差，p指定第二个块的尺寸，ρ是SNR，并且r是对应于要确定的门限R_thk的未知变量。Γ(x,y)指定Gamma函数

f是χ²(p)的概率密度函数(卡方分布)，并且

是标准化的上Gamma函数)。

第一术语

对应于所选择的对应于第一子块的路径不会由如下解码算法实现的树搜索期间被访问到的概率，所述解码算法应用于所述第一子向量来确定该第一子块的候选估计。公式21等效于确定门限值，使该标准化噪声

关于该第一子块的概率大于标准化门限

标准化噪声

是根据χ²(p)分布的。

例如，如果两个块长度分别为p和n-p(N＝2)，并且ML解码算法D₁针对块s⁽¹⁾的处理，则查找表的每个R_thk值可以通过求解下面公式理论上地确定

在公式22中，c₁和c₂指定正值常量，σ²指定噪声差，p指定块的尺寸，ρ是SNR，并且r是对应于要确定的门限R_thk的未知变量。Γ(x,y)指定Gamma函数。

公式22的第一项

对应于当针对块s⁽¹⁾的处理应用ML解码时计算出的帧错误概率(每一发送的帧有错误的概率)，公式22的第二项

对应于目标帧错误概率。

公式22的第一项来自使用ML解码访问在半径r的球之外的路径的概率：

w⁽¹⁾指定对应于块s⁽¹⁾的噪声。

在公式22的第一项中，用应用的解码方案来控制可达到的分集阶数d_target的项是

而项c₁ρ^-n+c₂ρ^-n指示完全分集。因此，查找表的每个R_thk值可以通过求解下面的公式来确定：

在另一个示例中，如果解码器110针对块s⁽¹⁾的处理使用ZF-DFE解码算法D₁，应用接收的信号到长度分别为p和n-p(N＝2)的两个块s⁽²⁾和s⁽¹⁾的次优化解码，则查找表的每个值R_thk可以通过求解下面的公式理论上地确定：

在公式24中，N_e指定星座中的最近邻居的平均数量，使用最近邻居并集范围，σ²指定噪声差，p指定块s⁽²⁾的尺寸，ρ是SNR，并且r是对应于要确定的门限R_thk的未知变量。Γ(x,y)指定Gamma函数。此外，ε由下面的公式给出

代表星座的最小距离。公式24的第一项

已经从解码错误符号s_p+1的概率P_r(E_p+1)满足P_r(E_p+1)≤N_eε的事实获得。

在公式24的第一项中，用应用的解码方案来控制可达到的分集阶数d_target的项是

而额外的项

代表在对应于块s⁽²⁾的处理的第二解码阶段中ZF-DFE的使用所造成的性能降级。因此，查找表的每个R_thk值可以通过求解下面的公式来预先确定：

在一些实施例中，解码器110可以接收对应于目标分集阶数d_target的目标QoS指示符Q_target，并且应用接收的信号到数量N≥2个尺寸为p₁,…,p_N的子块的子块解码。在这些实施例中，查找表的门限值可以从错误概率的分析来预先确定，该分析能够与长度p_i的每个子块s⁽ⁱ⁾相对应地求导出门限值r_i,th。

错误概率的分析可以考虑相等或不同的子块尺寸导出。此外，该错误概率可以取决于最后阶段中使用的解码算法。例如，当针对块s⁽¹⁾的处理实现ML解码器时，帧错误概率的上限可以根据下面：

在公式(26)中：

-I指定在树搜索过程中由对应于向量s的所有子块的向量访问的所选择路径的集合；

-r_i针对i＝1,…,N，指定对应于要确定的门限r_i,th的未知变量。

因此，查找表的针对i＝1,…,N的每个值r_i,th可以根据满足下面不等式来预先确定：

在不等式(27)中，δ指定能够控制信噪比增益的负常量。不等式(27)可以用尽可能小的误差幅度在模拟中数字上求解。

给定确定的门限，解码器110可以被配置为根据下面步骤执行N≥2个尺寸为p₁,…,p_N的子块的子块解码：

1)通过应用对应于每个子块的解码算法D_k估计针对k＝2,…,N的集合Γ_k；

2)根据累计度量的升序对集合Γ_N-1中的候选排序；

3)针对集合Γ_N-1中的每个候选，使用ML解码器D₁寻找集合Γ₁中的候选，并且在当前检查的候选的累积度量低于或等于集合Γ_N-1中存储的下一个候选的累积度量时停止。

图6是表示针对具有最佳编码并且使用4-QAM星座的4×4MIMO经编码系统的，根据某些实施例用解码器110获得的性能(曲线C1)的示意图。该复杂度可以随着总的乘法次数来计算。最佳代码编码16个复数符号(32个实数符号)。针对这一代码存在R矩阵的块划分的不同示例。图7中所表示的划分已经用于获取图6的示意图。图7中表示的上三角矩阵R被划分为两个上三角矩阵R⁽¹⁾＝R1(维度为18×8的矩阵)和R⁽²⁾＝R2(维度为28×8的矩阵)，以及矩形矩阵B。考虑实数符号，R1∈R^16×16并且R2∈R^16×16。使用4-QAM星座，针对Γ₂(A₂＝50)只考虑2¹⁶＝65356种可能解决方案上的50个候选。应该注意的是，在针对模拟考虑的示例中，对应于s⁽²⁾的解码步骤中考虑的潜在候选的数量不是优化的。在图6中，曲线C2对应于常规的球解码器。图6示出了用本发明的递归解码器110获取的保持基本不变的复杂度相比于用常规球解码器实现的复杂度有所降低。应该注意的是，在SNR＝10^-3处的3dB的损失可以通过优化候选集合Γ₂中选择的候选的数量来补偿。

图13和14表示分别示出了针对使用4-QAM调制的8×8空间复用MIMO系统，根据一些实施例用解码器110获取的符号错误率性能和平均计算复杂度的示意图。图13和图14对应于上三角矩阵R到4个上三角矩阵的划分。图13和图14中示出的各个曲线对应于使用每个子块的相同或不同长度的不同场景。两个附图中的图例都如下写出：d/SNR增益/p₁p₂p₃p₄，d指定目标分集阶数，SNR增益指定信噪比增益，而p₁p2p₃p₄指定针对该上三角矩阵到4个上三角矩阵的划分考虑的子块的长度。另外，在图13和图14中，引用“SD88”对应于使用用于解码信息符号的传统球解码算法获得的曲线。图13和图14示出了本发明的各个实施例以降低的计算复杂度在实现目标分集阶数方面提供灵活性。具体来讲，示出了任何目标分集阶数总是可实现的，并且使用子块长度的各种值获取额外的信噪比增益。应该注意的是，错误性能和计算复杂度是对子块的长度敏感的。更具体地说，最佳错误性能是用第一子块的最高长度p₁实现的，并且该最高平均复杂度随着长度p₄的增加而增加。

根据本发明的实施例的递归子块解码方法和设备因此允许有效地控制目标分集阶数，同时确保降低的复杂度。该复杂度降低能够取决于与每个子块s^(k)相关联的候选集合Γ_k中选择的候选估计的数量、针对每个子块s^(k)的解码所选择的格解码算法D_k的类型和/或根据其来处理子块s^(k)的顺序来进行优化。

图8到图10的示意图示出了在本发明对使用具有4-QAM星座，块的数量N等于2块的黄金代码的经编码系统的示例性应用中，针对SNR的不同值获得的不同经验分布。具体来讲，这些附图示出了在本发明对到N＝2块中的子编码的应用中，在数据流的先前编码上每个候选值秩的发生，在该实施例中，每个候选集合Γ_k按照累积度量的增加的值来进行排序，这一统计数据可以根据每个候选值秩在数据流的先前解码上的发生来确定。能够看到的是，在我们的列表中对应于第一秩

的本地ML解决方案是候选集合Γ₂中最频繁被选择的候选。这一统计分布可以用于限制每个候选集合Γ_k中维护的候选数量(通过在步骤408中进一步选择与从这些统计数据获得的目标数量匹配的候选集合)或者另外通过基于该统计数据更新门限R_thk来限制每个候选集合Γ_k中的候选估计的数量(例如，这一更新可以由方框501实现)。

图11示出了R矩阵到两个子块(N＝2)的划分的树表示和符号的子向量(长度为p的s⁽²⁾和尺寸n-p的s⁽¹⁾)的相应解码。

图11示出了对应于划定搜索空间的球的半径r的门限R_thk。此外，在图11中：

-路径[RO_pi]，R对应于根节点，而O_pi是该树中的P层处的节点，指定候选集合Γ₂中选择的候选子向量；

-路径

O_pi对应于该树中P层处的i-th节点，而O_pj对应于该树中P层处的j-th节点，指定对应于候选集合Γ₂中选择的候选和候选集合Γ₁中选择的候选的完整路径；

-路径

指定发送的信号的估计；

-其它分支是信息符号的未选择的子向量的一部分。

虽然已经关于从实数信道矩阵获得的上三角矩阵R的划分获得的接收的信号的划分描述了本发明，但是可以另外从复数向量化的信道输出执行子块半穷举解码方法。因此，可以从复数信道矩阵而不是使用实数信道矩阵执行到子块的划分。

此外，虽然已经关于到两个块的划分的某些示例，以及上三角矩阵R的某些示例描述了本发明，但是本发明并不仅限于特定的块的数量或上三角矩阵的配置。

一般来讲，即使本发明的半穷举子解码方法和设备在接收的信号的划分是从上三角矩阵R的划分获得的时具有特定优势，但是半穷举子解码方法和设备可以另外使用关于信道矩阵H的另一个矩阵来从其获取接收的信号的划分。例如，在本发明对使用空间-时间块编码(STBC)以便在发射机一侧编码数字数据序列的经编码系统的一个应用中，经编码信号通过传输信道发送并且包括q个独立符号的集合。通过传输信道发送的信号由码字矩阵X表示，

X属于密码本C。对于线性空间-时间块编码，该码字矩阵X以如下形式承认线性离散表示：

在公式(28)中，

和

分别对应于s_i复数信息符号的实数和虚数部分，而矩阵A_l表示线性离散矩阵(也称为LD矩阵)。

在接收机处接收的信号可以被写为：

Y＝HX+W (29)

接收的信号可以如下向量化：

vec(Y)＝H_eqS+vec(W) (30)操作符vec(.)被定义为将n×m复数值矩阵的m列插入mn复数列向量中的操作符。

在公式(28)中，H_eq指定维度n_r×q的等效信道矩阵如下：

向量s是通过根据如下来向量化码字矩阵X获得的：

vec(X)＝Gs，G表示所使用的线性STBC的生成矩阵。

H_eq可以如下重写为LD矩阵的函数：

H_eq＝[vec(A₁H)|vec(A₂H)|...|vec(A_2kH)] (31)

向量化的复数系统可以重写为：

y＝H_eqs+w (32)

在本发明的这一编码实施例中，子块分解单元301可以被配置为将等效的接收向量y划分为N个子向量y^(k)，并且对应于接收向量的划分来分解等效信道矩阵H_eq。该等效信道矩阵H_eq被划分为N个矩形子矩阵

其中k＝1,…,N，每个子矩阵

表示维度为n_r×l_k的矩形矩阵，并且由等效信道矩阵H_eq的l_k列向量组成：

接收的信号向量y被划分为长度为l_k的N个子向量y^(k),k＝1,…,N，使得

并且

相同的向量划分被应用于符号s的向量以获取长度为l_k的N个子向量s^(k),k＝1,…,N，使得

在一些实施例中，等效的信道子矩阵可以取决于乘积

(上标“.^H”表示共轭转置):

的行列式来重新排序，使得对应于乘积

的行列式的子矩阵的子向量s^(k)被放置在第一位置(k＝N)中。重排之后的等效信道子矩阵表示为：

相同的重新排序被应用于符号s的向量以便获取等效系统。

因此，公式(32)可以重写为：

在公式(33)中，s^(N)和因此的

对应于具有乘积

的最小行列式的子矩阵。

然后，候选集合估计单元305可以如上描述地确定每个块s^(k)的候选估计集合Γ_k，该候选集合Γ₁,…,Γ_N用于根据图4的步骤405到410确定发送信号的估计

图12代表本发明的SB-栈实施例中的接收机3的控件/时间解码器110的示例性架构。如图所示，该空间-时间解码器110可以包括下面的元件，它们可以由数据和地址总线64连接在一起：

-微处理器61(或CPU)，其可以是例如数字信号处理器(DSP)；

-非易失性存储器62(或ROM，只读存储器)；

-随机访问存储器RAM 63；

-用于从时间/频率转换器接收输入信号的接口65；

-用于向解调器31发送经解码数据的接口66。

非易失性ROM存储器62可以包括，例如：

-寄存器“Prog”620；

-门限R_thk或者另外的查找表621；

-目标服务质量指示符Q_target 622；

-块的数量N 623；以及

-可以以数据结构624的形式存储的候选集合Γ_k。

用于实现根据本发明的这一实施例的方法的算法可以被存储在程序620中。CPU处理器41可以被配置为将程序620下载到RAM存储器中并且运行相应指令。具体来讲，该CPU包括的指令在由CPU执行时，使得该CPU：

-对应于与所述信道矩阵(诸如从QR分集获得的矩阵R)有关的矩阵的划分，将接收的信号向量划分为子向量的集合

以及

-递归地确定所述发送的信号的对应于所述子向量

的子块s^(k)的候选估计，使得给定子块的每个估计是从先前处理的子块的至少一个候选估计确定的。

该CPU被用于通过应用使用针对先前处理的子块确定的估计

的解码算法Dk的至少一次迭代，确定所发送的信号的至少一个子块s^(k)的候选估计的集合Γ_k，针对所述子块确定的候选集合的数量严格低于从其选择信息符号的值的集合的基数。该CPU还用于根据针对子块确定的候选估计Γ₁，...，Γ_N来计算发送的信号的估计。

RAM存储器63可以包括：

-在寄存器Prog630中，由微处理器61运行的并且在空间-时间解码器30的活跃状态中下载的程序；

-寄存器631中的输入数据。

一般来讲，本申请中所描述的解码技术可以由各种方式实现。例如，这些技术可以在硬件、软件或它们的组合中实现。对于硬件实现，解码器的处理元件可以，例如根据仅硬件的配置(例如，在一个或多个具有相应存储器的FPGA、ASIC或VLSI集成电路中)或者根据使用VLSI和DSP二者的配置实现。

虽然已经关于无线通信系统描述了本发明，但是应该注意的是，本发明并不仅限于这些应用。例如，所述解码设备和方法可以集成到单个处理装置中，例如用在诸如音频分频器和音频控制之类的音频应用中的有限脉冲响应(FIR)的电子滤波器，用于解码来自给定输入序列的输出序列。给定数据的输入序列，FIR滤波器的M阶输出序列是在尺寸M的滑动窗口中观察到的最近输入值的加权和。给定输出序列的模型中的格状表示，本发明的某些实施例可以相应地集成以便生成输入序列的估计。

在另一个应用中，根据本发明的一些实施例的方法、设备和计算机程序产品可以实现在全球导航卫星系统(GNSS)(诸如IRNSS、Beidou、GLONASS、Galileo)；包括例如用于使用例如载波相位测量来估计定位参数的至少一个GPS接收机的GPS。

此外，根据本发明的一些实施例的方法、设备和计算机程序产品可以实现在密码学系统中，以用于确定对用于在数据或消息存储、处理或通信过程中对其加密/解密的密码学算法中的私有密钥值的估计。在基于格状的加密应用中，数据/消息以格子点的形式被加密。这些经加密数据的解密可以根据本发明的一些实施例有利地执行，能够以降低的复杂度进行高概率的密钥值的成功恢复。

一般来讲，虽然本发明的实施例已经通过各个示例的描述示出，并且虽然这些实施例已经在相当多的细节中描述，但是本申请的意图并非将所附权利要求约束或以任何方式限制于这些细节。具体来讲，本发明并不仅限于特定类型的格解码器。一般来讲，任何类型的格解码器可以用于步骤408中，正如使用最佳优先树搜索以搜索候选格向量的任何顺序解码器，比如栈解码器、Fano解码器、实现M-算法的解码器、专利申请EPN14306517.5中描述的SB-栈和Zigzag栈解码器。

Claims (29)

1.一种用于在通信系统中对通过传输信道接收的信号进行解码的解码器，所述信号携带从给定值的集合选择的并且与信号向量相关联的信息符号，所述传输信道由信道矩阵表示，其中，所述解码器包括：

-子块划分单元(301)，其被配置为对应于与所述信道矩阵有关的矩阵的划分，将接收的信号向量划分为子向量的集合；

-候选集合估计单元(305)，其用于递归地确定发送的信号中对应于所述子向量的子块的候选估计，给定子块的每个估计是根据先前处理的子块的至少一个候选估计确定的，

其中，所述候选集合估计单元被配置为通过应用使用针对所述先前处理的子块确定的所述估计的解码算法的至少一次迭代，来确定针对所述发送的信号的至少一个子块的候选估计的集合，针对所述子块确定的所述候选估计的数量严格低于所述给定值的集合的基数，所述解码器还包括信号估计单元(306)，其用于根据针对所述子块确定的所述候选估计来计算所述发送的信号的估计。

2.如权利要求1所述的解码器，其中，所述解码器被配置为通过执行来自所述信道矩阵的QR分解来预先确定正交矩阵Q和上三角矩阵R，并且所述子块划分单元(301)被配置为将所述上三角矩阵R划分为若干个上三角子矩阵和若干个矩形矩阵，所述上三角子矩阵的数量高于或等于二，所述子块划分单元(301)被配置为将所述接收的信号向量划分为子向量的集合，使得所述接收的信号向量的每个子向量对应于所述上三角子矩阵中的一个。

3.如权利要求2所述的解码器，其中，所述解码器被提供用于通过将所述正交矩阵的转置矩阵乘以所述接收的信号来确定所述接收的信号向量。

4.如前述权利要求2和3中的任一项所述的解码器，其中，所述解码器还被布置为通过交换所述信道矩阵的行或列来根据所述信道矩阵确定置换矩阵的集合，并且执行每个置换矩阵的QR分解以确定中间上三角矩阵，所述解码器被配置为根据与针对每个置换矩阵获取的所述中间上三角矩阵的分量有关的标准来选择所述置换矩阵中的一个，所述子块划分单元(301)对应于与选择的置换矩阵相关联的所述中间上三角矩阵来对所述上三角矩阵R进行划分。

5.如权利要求1所述的解码器，其中，所述解码算法是格解码算法。

6.如权利要求5所述的解码器，其中，所述格解码算法被配置为关于门限来求解每个块的累积度量的条件。

7.如权利要求6所述的解码器，其中，所述格解码算法是顺序解码算法，并且所述门限是所述顺序解码算法的累积度量门限。

8.如权利要求6所述的解码器，其中，所述格解码算法是球约束解码算法，并且所述门限是所述球约束解码算法的球的初始半径。

9.如权利要求6到8中的任一项所述的解码器，其中，所述门限是根据目标服务质量指示符确定的。

10.如权利要求9所述的解码器，其中，所述目标服务质量指示符是目标分集阶数。

11.如权利要求10所述的解码器，其中，所述解码器还包括门限估计单元(500)，其被配置为确定用于每个子块的解码的门限。

12.如权利要求11所述的解码器，其中，所述门限估计单元(500)被配置为根据所述目标分集阶数并且根据由以下项构成的分组当中选择的至少一个其它参数来确定所述门限：信噪比的估计、所述接收的信号的维度、以及所述子块的维度。

13.如权利要求12所述的解码器，其中，所述门限估计单元(500)包括存储用于每个值的多元组的所述门限的值的查找表，所述每个值的多元组包括所述目标分集阶数的值和所述至少一个其它参数。

14.如权利要求13所述的解码器，其中，所述子块的数量等于二，并且所述查找表的所述门限值是根据对应于第一子块的所选择的路径在由解码算法实现的树搜索期间没有被访问到的概率来预先确定的，所述解码算法应用于第一子向量以确定所述第一子块的所述候选估计和所述信噪比。

15.如权利要求13所述的解码器，其中，所述门限估计单元(500)被配置为取决于与先前的数据流的解码相关的统计数据来更新所述查找表。

16.如权利要求6所述的解码器，其中，每个候选估计的集合是按照针对每个估计获取的所述累积度量的增加值来进行排序的数据结构。

17.如权利要求1所述的解码器，其中，所述候选集合估计单元(305)被配置为取决于与所述子块相关联的候选估计的目标数量来进一步减少在所述至少一个子块的当前候选估计的集合中确定的候选的数量。

18.如权利要求17所述的解码器，其中，与所述子块相关联的所述候选估计的目标数量是根据所述先前处理的子块的候选估计的数量来确定的。

19.如权利要求18所述的解码器，其中，与所述子块相关联的所述候选估计的目标数量是所述先前处理的子块的所述候选估计的数量的乘法函数，所述乘法函数具有不超过一的斜率系数。

20.如权利要求1所述的解码器，其中，所述候选集合估计单元(305)还包括通过应用根据预定义的标准选择的解码算法来确定上一个处理的子块的一个估计。

21.如权利要求20所述的解码器，其中，所述解码算法是从由以下项构成的分组当中选择的：ML解码算法、ZF-DFE解码算法、以及MMSE解码算法。

22.如权利要求1所述的解码器，其中，所述信号估计单元被配置为确定使总体度量最小化的估计的多元组，每个多元组估计包括来自针对所述信息符号的子块获取的所述候选估计的集合中的每一个的一个候选估计。

23.如权利要求1所述的解码器，其中，所述通信系统是使用空间-时间块编码来对在所述传输信道上发送的数据信号进行编码的经编码的系统，所述解码器被配置为使用等效信道矩阵来对所述信号向量进行向量化，并且将所述等效信道矩阵划分为若干个矩形等效信道子矩阵，每个矩形子矩阵是表示对应于所述接收的信号的在所述传输信道上发送的信号的线性离散矩阵的函数，所述子块划分单元(301)被配置为对应于所述等效信道矩阵的所述划分，将所述接收的信号向量划分为子向量的集合。

24.如权利要求23所述的解码器，其中，所述解码器还被配置为取决于每个等效信道子矩阵的共轭转置和所述等效信道子矩阵的乘积的行列式的值来对所述矩形子矩阵进行重新排序。

25.一种用于对经编码的信号进行接收和解码的接收机，其中，所述接收机包括如权利要求1-24中的任一项所述的用于对所述信号进行解码的解码器。

26.一种能够在无线通信网络中发送和接收数据的移动设备，其中，所述移动设备包括根据权利要求25的用于接收信号的接收机。

27.一种在通信系统中对通过传输信道接收的信号进行解码的方法，所述信号携带从给定值的集合选择的并且与信号向量相关联的信息符号，所述传输信道由信道矩阵表示，其中，所述方法包括：

-对应于与所述信道矩阵有关的矩阵的划分，将接收的信号向量划分为子向量的集合；

-递归地确定发送的信号中对应于所述子向量的子块的候选估计，给定子块的每个估计是根据先前处理的子块的至少一个候选估计确定的，

其中，所述递归地确定估计的步骤包括，针对至少一个子块，通过应用使用针对所述先前处理的子块确定的所述估计的解码算法的至少一次迭代，来确定针对所述发送的信号的所述子块的候选估计的集合，针对所述子块确定的所述候选估计的数量严格低于所述给定值的集合的基数，所述方法还包括根据针对所述子块确定的所述候选估计来计算所述发送的信号的估计。

28.如权利要求27所述的方法，其中，所述方法还包括：

-通过执行来自所述信道矩阵的QR分解来确定正交矩阵Q和上三角矩阵R；

-将所述上三角矩阵R划分为若干个上三角子矩阵和若干个矩形矩阵，所述上三角子矩阵的数量高于或等于二，

-将所述接收的信号向量划分为子向量的集合的步骤包括，对应于所述上三角子矩阵中的一个来对所述接收的信号向量的每个子向量进行划分。

29.一种非暂时性计算机可读存储介质，其上存储有指令，当由处理器执行时，所述指令使所述处理器用于执行根据权利要求27-28中的任一项所述的方法。

Images