CN1656695B - 用于增强对网格的搜索的方法和装置 - Google Patents

Abstract

本发明涉及用于在检测器(220)中增强对网格的搜索的方法和装置，其中该检测器被安排在该网格的每一级来选择所述级的某组状态索引以便继续。当该网格的每一级被计算时，该检测器(220)被安排来：规定不止一个不相等的阈值用于所述状态索引的值，每个阈值规定一个状态索引组；为每个状态索引计算路径度量；通过比较所述状态索引的路径度量值与所述阈值，把所述计算的状态索引安排到不同的组中去。此外该检测器以这样一种方式从所述组中选择一定数量的状态索引以便继续：从包括最高的状态索引的组开始，选择整个组以便继续，直到下一整个组并不适合。从这个组起，只选择随机地选择的状态索引直到收集了给定的个数。

Description

用于增强对网格的搜索的方法和装置

发明领域

本发明涉及用于增强对网格的搜索的方法和装置，其中在网格的每一级，该级的某状态索引组被选择以便继续。

背景

电信系统中使用的信道常常引起对数据传输的干扰。干扰出现在各种各样的系统中，但尤其是出现在无线通信系统中，传输路径以多种不同的方式使被发送的信号衰减和失真。信号的多径传播、不同的衰落及反射，以及在同样的传输路径上发送其它信号通常引起在传输路径上的干扰。

为了降低干扰的影响，已经提出了几种编码方法来保护信号免受干扰、并竭力消除由信号中的干扰引起的错误。卷积编码是通常使用的编码方法。在卷积编码中，由码元组成的待发送的信号被编码成基于待发送的码元与它们自己或者与另一个信号的卷积的码字。编码速率和生成器多项式规定了卷积码。编码速率(k/n)指待编码的码元的个数(k)和产生的编码后的码元个数(n)的比值。编码器常常是移位寄存器。代码的约束长度(K)常常指移位寄存器的长度。编码器可以被看作具有2^K-1个状态的状态机。

接收机译码经过信道传播的编码后的信号。卷积码通常使用网格进行译码，其中网格的节点描述了在编码信号中使用的编码器状态，并且在属于网格的不同级的节点之间的路径描述了允许的状态转移。译码器试图找出编码器的连续的状态，即，从一个状态到另一个状态的转移。为了找出转移，译码器计算度量，存在两种类型的度量：路径度量(或者状态度量)和分支度量。路径度量代表了接收到的信号中码元组导致讨论中的节点所描述的状态的概率。分支度量代表了不同的转移的概率。

卷积码通常借助于维特比(Viterbi)算法被译码。维特比算法是一项计算上要求较高的任务。维特比算法的一般问题是：当约束长度较长时(例如9，象在UMTS系统的WCDMA中那样)，维特比算法必须搜索2^(9-1)，即256个状态来译码一个比特。仍在寻找有效的信号处理算法来特别用于无线电信系统，其中目标是最小化用户终端的尺寸及功耗。用于语音或数据译码的高效计算算法是M算法，它是从维特比算法简化而来的搜索算法。使用M算法使得减少被搜索的状态数成为可能，因为只有M个最佳路径而不是所有的路径被选择用于在网格级中的拓展。当为M选择了适当的值时，译码器的性能却没有变得显著恶化。例如，在上面提到的系统中，M可以得到值128，即，可能路径的一半被选择用于在每级的拓展。

使用M算法的一个问题是在所有的路径中选择以便继续的路径。典型地，n个元素的排序需要n²/2次比较运算，而且这是一项计算上要求较高的任务。让我们假设当使用全搜索算法时，在WCDMA中DSP(数字信号处理)译码一个比特需要大约500个时钟周期。如果使用M算法，要被搜索的状态数较小，但是相应地，排序增加了复杂性。当对16个元素排序时，需要128次比较运算，这样使用具有最佳的16条路径的M算法导致几乎跟全搜索算法一样的复杂性。如果使用256个状态的代码，全部的排序需要n²/2，即32768次比较。全搜索是一项如此复杂的运算以致于不能用常规的方法实现。

实现M算法的一个已知的解决方案公开于出版物S.J.Simmons：ANonsorting VLSI structure for implementing the(M，L)algorithm(用于实现(M，L)算法的非排序VLSI结构)，IEEE Journal onSelected Areas in Communications，Vol.6，No.3，1988年4月，538页到546页。所公开的解决方案不执行实际的排序，而是从最高有效比特开始，同时检查几条不同的路径度量。当检查不同的路径时，作出关于保留还是丢弃这个路由的决定。如果被检查的路由是跟已经选择的路由相反，则它被丢弃。然而，在该出版物中公开的这个解决方案在如举例而言UMTS系统的WCDMA中、网格很大的情形中作用很差。

网格结构不仅被用于译码卷积码，还被用于几种其它的应用，例如信道均衡。当网格的尺寸变大时，上面提到的同样的问题也适用于这些解决方案。

因此，为了最小化设备的尺寸和功耗，需要用于搜索网格的比以前更有效的方法、快速的并且其实现如ASIC结构不需要很多空间的方法。

发明概述

本发明的一个目的是提供一种方法以及以这样一种方式实现该方法的装置：可能有受限的网格搜索以便比以前更有利地执行。这是由用于增强对网格的搜索的方法达到的，其中在网格的每一级，级的某组状态索引被选择以便继续。本发明的方法包括在网格的每一级规定不止一个不相等的阈值用于状态索引值，每个阈值规定一个状态索引组，为每个状态索引计算路径度量，通过比较状态索引的路径度量值和阈值而安排计算的状态索引到不同的状态索引组，以这样一种方式从组中选择状态索引以便继续：通过从包含最高的状态索引的组开始，状态索引以随机的顺序从组中被选择直到组的所有索引都已经被选择，然后继续从下一个组选择状态索引，并且重复这个过程直到已经选择了一定数量的状态索引。

本发明也涉及用于在被安排在网格的每一级来选择该级的某组状态索引以便继续的检测器中，增强对网格的搜索的装置。在装置中，检测器被安排为当网格的每一级被计算以规定不止一个不相等的阈值用于状态索引值，而每个阈值规定一个状态索引组时，为每个状态索引计算路径度量，通过比较状态索引的路径度量值和阈值，而安排计算的状态索引到不同的组，以这样一种方式从组中选择一定数量的状态索引以便继续：通过从包含最高状态索引的组开始，整个组被选择以便继续直到下一整个组不适合(fit in)，并且从这个组中只有随机地选择的状态索引被选择，直到搜集了给定数量的状态索引。

本发明的优选实施例在从属权利要求中被描述。

本发明的方法和装置因此提供了几个优点。在接收机中实现本发明的优选解决方案是简单的。M算法由于其所要求的计算而在实际中还没有被太多地使用。借助于本解决方案，M算法可以被有效地利用，因为本解决方案检查比维特比算法少的状态，因此需要较少的存储器用于计算路径。这导致设备费用的节省。此外，当使用本解决方案时，因为需要较少的计算和较少的存储空间，因此接收机的功耗降低。然而，本解决方案提供了在实际中等同于早先的方法的足够的性能。

一个替代的实现使用模运算来实现本发明所需要的计算。因为这个原因，对于计算的度量，不需要换算(scaling)。这简化了解决方案的计算和实现。

尤其是在与高的数据速率相结合时，本解决方案提供了显著的好处，因为在这种情况下，网格的尺寸通常很大。大的网格也需要被使用，例如当几个天线、复杂的调制方法和强编码(strong code)被用于传输和接收时。译码大的网格增加了需要的计算量，并且在这种情况下，本解决方案有助于抑制计算量。

优选实施例的解决方案可被用于使用网格的所有应用中。除了上面提到的卷积码的译码以外，这样的应用还包括其它类型的码的译码、均衡、多用户译码和语音识别。

附图清单

现在本发明将借助于优选实施例进行更详细的描述，参考附图，其中

图1示出了优选实施例可被应用到的电信系统的实例，

图2示出了发射机和接收机的实例，

图3说明了网格，

图4A和4B是说明了优选方法的实例的流程图，

图5A和5B说明了使用模运算的计算，

图6A和6B示出了一种装置的实例，以及

图7示出了存储器的优选实现的实例。

优选实施方案描述

图1示出了对于本发明是必要的蜂窝式系统的结构的部分。该系统包括基站100和一组具有到基站的双向连接108到112的通常的移动用户终端102到106。基站将终端的连接切换到基站控制器114，基站控制器114接通它们到系统的其它部分以及到接通固定的网络。基站控制器114控制一个或多个基站的运行。

参考图2，让我们检查本发明的优选实施方案的解决方案可被应用到的发射机100和接收机102的实例。在图的实例中，发射机因此是基站并且接收机是用户终端，但是当接收机是基站接收机时，优选实施方案也可以被应用。在图2的实例中，发射机100和接收机102因此在无线电信道108上通信。发射机100包括可以是语音编码器或者某些其它数据源的数据源200。待被发送的信号202是从数据源的输出获得的，并且被带到信道编码器204，在本例中，信道编码器是卷积编码器。编码后的码元206被带到调制器208，在其中信号以已知的方式被调制。调制后的信号被带到射频部分210，在其中它被放大并借助于天线212被发送到无线电路径108。

在无线电路径108上，信号收到干扰以及典型地还有噪声。接收机102包括天线214，接收机102使用天线214接收通过射频部分216被带到解调器218的信号。解调后的信号被带到检测器220，在其中信号被译码、均衡以及根据本发明的优选实施方案被检测。信号222从检测器被带到接收机的其它部分。

接下来，借助于图3更详细地描述通过维特比译码器使用网格的实例。该图示出了8状态的网格图作为例子。网格图是基于所使用的编码被确定的：在本图中，每个点具有两个进入以及两个外出路由，即，讨论的编码是1/n编码速率的编码。每列可被称作网格的一级。通过在从左至右或者从右至左的级中行进，维特比算法在网格图中被求解。每个点可以经由两个不同的路由到达，而且在每个点中，进入路由的较好的一个被选择并被存储在存储器中。该选择是基于先前提到的度量的。路径度量代表了在接收的信号中的码元组导致由讨论的节点描述的状态的概率。反过来，分支度量代表了不同转移的概率。进入路由的度量因此在每个点中以这样一种方式被计算：在前一节点和正被处理的节点之间的转移的分支度量被加到在这个路由上的前一节点的路径度量上。依靠这个方法，这些中的较高的或者较小的被选择以便继续。

在常规的维特比算法中，所有的路径和节点被检查。当使用M算法时，在每一级只有M条路径被选择以便继续。如果M等于所有状态的数量，那么这是一个简单(plain)维特比算法。M算法本身对于本领域的技术人员是已知的并且在此不进行更详细地描述。参考出版物Schlegel：Trellis coding，(网格编码)，IEEE出版社，ISBN：0-7803-1052-7，153到189页。

让我们检查借助于图4A和4B的流程图来计算网格的实施方案的例子。所有的计算是通过使用模运算执行的。在初始化级，路径度量象在维特比算法中那样被初始化400，即以这样一种方式：状态索引号0被给定一个较大的路径度量(让我们将它记为PM_MAX)而且其它的状态索引被给定较小的路径度量。接下来，阈值TH₁，TH₂，...TH_N以这样一种方式被初始化402：最高的阈值TH₁等于PM_MAX+C₁MOD 2D，其中D是在任意两个路径度量之间的最大的可能的差。模运算稍后更详细地描述。下一个阈值TH₂等于PM_MAX+C₂MOD 2D等等。常数C₁可以是负的并且C₁＞C₂＞C₃...＞C_N.接下来，剩余的状态索引组以这样一种方式被初始化404：至少状态索引0被包括在内。剩余的状态索引指的是被包括在下一级的状态索引。

当计算网格的每一级时，首先新的路径度量被计算406，如在M和维特比算法中那样，用于从前面的级选择的以便继续的状态索引的新转移。通过比较计算后的值和阈值，根据每个新的路径度量的值，为每一个新的路径度量确定适当的组408。这可以例如通过找到比计算后的路径度量要小的最高的阈值来完成。阈值的索引确定适当的组。因此，其路径度量比TH₁大的状态索引被放在组1中，其路径度量值在TH₁和TH₂之间的状态索引被放在组2中，等等。最高的路径度量值被找到410并且记为PM_MAX。新的PM_MAX和以前的PM_MAX之间的差被计算而且该值被记为d。

接下来，阈值TH_i被例如如下地更新412：THi＝(THi+d)mod 2D，其中D是在任意两个路径度量之间最大的可能的差。

接下来，继续到下一级的M状态索引被选择414。该选择是从包括最大路径度量的组1，即比阈值TH₁高的状态索引被放到的组开始的。在这个组中的状态索引以随机的顺序被选择以便继续。接下来组2的状态索引以随机的顺序被选择。这一次持续一个组直到M个状态索引已经被选择。

让我们举一个数字的例子来阐明以便继续的选择。这里数字值被随机地选择以说明本实例。让我们假设组1具有10个状态索引，组2具有25个状态索引，组3具有23个状态索引，组4具有58个状态索引以及组5具有13个状态索引。也可能有比这里提到的更多的组。让我们进一步假设M＝128，即，为下一级的计算选择128个状态索引以便继续。然后来自组1、2、3和4的所有状态索引在每一组中以随机的顺序被选择以便继续。这样，116个索引被选择。接下来，12个状态索引以随机的顺序从组5中被选择以便继续以获得所期望的总数128。

接着让我们检查说明了通过使用模运算完成的计算的图5A。该图示出了当朝右移动时，在顶部500具有值0，以及当来自左边时在顶部500具有值2D、在底部502具有值D的模环。因此，在环的圆周上的两点之间的最大距离可以是D。利用模运算，为状态索引计算的所有路径度量可以被放置在这个圆周上。图5A说明了关于路径度量如何在时刻n被放置在圆周上，以及如何使用阈值的实例。该图示出了六个阈值TH₁，TH₂，...TH₆。此外，一组计算的路径度量在图中被标记为黑点，其中度量508大于最高的阈值TH₁，并且因此属于第一组。路径度量510属于下一组。被选择以便继续的状态索引因此在每一组中以随机的顺序从第一组508开始被选择。在优选实施方案中，最大的路径度量504和第二大的路径度量506之间的差d被规定，并且用于下一级，阈值TH₁，TH₂，...TH₆在圆周上顺时针移动到所述距离的范围。这在示出了圆周上在时刻n+1的阈值和路径度量的替代的图5B中被说明。这重复直至网格已经被搜索。

图6A示出了实施方案的可能的装置。该装置包括用于计算状态索引的路径度量的装置600。从网格的前一级到正被计算的级的点的先前的路径度量602和分支度量604被用作输入。状态索引的计算的路径度量606被带到装置608，在其中通过将它们与阈值进行比较，路径度量被安排在组中。关于每个状态索引的组的信息610被带到存储器装置612，正如关于计算的路径度量的信息606那样。最大的计算的路径度量被存储在存储器614中。控制装置616控制该装置的运行并且确定如上面所描述的以便继续的状态索引。控制装置也如上面所描述的那样更新阈值。实施方案所要求的装置优选地可以由处理器中的程序实现，或者作为独立的元件或者作为ASIC电路实现。

第二实施方案使用存储在例如ROM(只读存储器)存储器中的固定的阈值。这样，当计算不同的级时，实际的阈值不需要被重新计算，但是为新的组从已有的阈值中选择适当的限制。这个实施方案比早先描述的那个要快，因为不需要时间来计算阈值。在ROM存储器中很容易存储几个阈值，因为ROM的存储密度非常高。

这个实施方案借助于图5A说明。让我们假设当计算特定的网格级时，阈值以这样一种方式被规定：最好的组是从TH2到TH3的范围，第二好的组是从TH3到TH4以及第三好的组是从TH4到TH5。当计算下一级时，组可在环上以这样一种方式被前向“移动”：最好的组是从TH1到TH2的范围，第二好的组从TH2到TH3等等。实际的阈值TH1，TH2，...，TH5被存储在存储器中。

图6B示出了第二实施方案的可能的装置。该装置包括用于计算状态索引的路径度量的装置600。从网格的前一级到正被计算的级的点的先前的路径度量602和分支度量604被用作输入。关于计算的度量的信息被带到比较器620，在其中计算的度量同从存储器614得到的、关于迄今最大的计算度量的信息622相比较。如果新的度量大于早先的度量，存储器614被指示来存储624讨论的度量626。

计算的度量被带到控制单元616。控制单元616检查来自阈值存储器628的阈值限制。阈值存储器存储所使用的组的限制。控制单元能够例如发送关于计算的度量的值的信息到存储器628，然后存储器628返回关于计算的度量所属于组的信息632。在这之后，控制单元从一个维护存储器636检查634，度量可被存储在其中的存储器元件中。接着，控制单元616在度量存储器640所讨论的位置中存储638该度量。对讨论中的该位置更新维护存储器636。

维护存储器636是保存有关在度量存储器640的哪个位置存储什么的记录的存储器元件。因此维护存储器列出了度量存储器中不同组的位置。在某种意义上度量存储器640被动态地处理：属于较好组的度量可被存储在存储较差组的度量的存储器位置。

当继续移动以计算下一网格级时，控制单元616在阈值存储器628中从已经存在的阈值中选择适当的限制用于新的组。

当计算该网格的级时，M个被首先计算的值被直接写入到度量存储器640中，而且关于度量存储器的存储器位置的信息被更新到维护存储器636中。当下一个度量被计算时，属于较差组的值被属于在度量存储器中的较好组的值代替。这个替代提供了这样的优点：度量存储器的尺寸可以被限制为M个存储器位置，而且此外，需要小的维护存储器。

在本实施方案中，在计算级的度量时获得度量的最大和最小值。这些值之间的范围依赖于信道条件而变化，并且度量与这个范围成比例地被选择以便继续。

一个实施方案保留有关度量的最大和最小值的记录。因此监控这些值之间的范围是可能的。如果所有的值彼此接近，则阈值可以基于这个信息被改变。因此，避免其中所有的度量积累在一个组中的情形是可能的。

图7说明了用于实现存储器612的一个实施方案。图7示出了存储器612，其中每个水平线是用于存储关于一个状态索引的信息的一个存储器位置。左列700示出了存储器位置的地址。存储器位置的地址域被分成两个部分，第一部分702和第二部分704。地址的第一部分702直接指示了状态索引组。因此，在图7的实例中，如果地址以比特“111...”开始，则它指第一组706，存储最大的路径度量的状态索引到所述第一组中是可能的。相应地，如果地址以比特“000...”开始，则它指最后一组708。存储器位置的第二部分704指存储器位置在该组内部的位置。当计算状态索引的路径度量时，状态索引可以直接被存储在与同样组的状态索引一样的存储器区域中。在组内部的状态索引的顺序不具有重要性。这种存储器的地址安排允许有利地选择M个状态索引以便继续。当选择状态索引以便继续时，例程从第一组的已使用存储器位置开始、从组的底部向第一元素(在图的实例中的111000)读取存储器，然后跳过空的存储器位置向下一组移动。当已经读取了期望数量的状态索引时，该例程结束。

尽管本发明在上面已经根据附图参考实例进行了解释，但是很明显本发明不局限于它们，而是可在所附的权利要求的范围内以多种方式被修改。

Claims (16)

1.一种用于增强对网格的搜索的方法，其中在该网格的每一级，该级的某组状态索引被选择以便继续，其特征在于，在该网格的每一级，

为所述状态索引的值定义不止一个不相等的阈值，每个阈值定义一个状态索引组，

为每个状态索引计算路径度量，

通过比较所述状态索引的路径度量值与所述阈值，把所述计算的状态索引安排到不同的状态索引组中去，

以这样一种方式从所述组中选择状态索引以便继续：从包括最高状态索引的组开始，以随机的顺序从所述组中选择状态索引，直到该组的所有索引都已被选择，然后继续从下一组中选择状态索引，并且重复这个过程直到一定数量的状态索引已经被选择。

2.如在权利要求1中所要求的方法，其特征在于至少一部分所述状态索引路径度量的计算是使用模运算完成的。

3.如在权利要求1中所要求的方法，其特征在于找到小于通过上述计算所得的路径度量的最高阈值，把所述计算的状态索引安排到不同的状态索引组中去。

4.如在权利要求1中所要求的方法，其特征在于当计算每一级时，所使用的阈值是从特定的预置阈值中选择的。

5.如在权利要求1中所要求的方法，其特征在于所述阈值按照如下公式进行初始化：THi＝(PM_MAX+Ci)mod 2D，其中THi是阈值，PM_MAX是最高的路径度量值，Ci是负的常数，且C₁＞C₂＞C₃...C_N，D是任意两个路径度量之间可能的最大差，mod为模运算符。

6.如在权利要求1中所要求的方法，其特征在于所述阈值按照如下公式进行自我更新：THi＝(THi+d)mod 2D，其中THi是阈值，d是新的最高路径度量值与之前的最高路径度量值之间的差，D是任意两个路径度量之间可能的最大差，mod为模运算符。

7.如在权利要求1中所要求的方法，其特征在于所述阈值的选择是基于所述状态索引值完成的。

8.如在权利要求1中所要求的方法，其特征在于通过比较所述状态索引路径度量值与所述阈值，把所述计算的状态索引放置在状态索引组中，

检查在所述存储的状态索引中是否有属于较差组的状态索引并且如果有，

把所述计算的状态索引路径度量存储在属于较差组的状态索引值之上，以及

存储所述存储器位置的地址。

9.一种用于在检测器(220)中增强对网格的搜索的装置，其中该检测器被安排在该网格的每一级来选择该级的某组状态索引以便继续，其特征在于当计算该网格的每一级时，该检测器(220)被安排为，

为所述状态索引的值定义不止一个不相等的阈值，每个阈值定义一个状态索引组，

为每个状态索引计算路径度量，

通过比较所述状态索引的路径度量值与所述阈值，把所述计算的状态索引安排到不同的组中去，

以这样一种方式从所述组中选择状态索引以便继续：从包括最高状态索引的组开始，以随机的顺序从所述组中选择状态索引，直到该组的所有索引都已被选择，然后继续从下一组中选择状态索引，并且重复这个过程直到一定数量的状态索引已经被选择。

10.如在权利要求9中所要求的装置，其特征在于所述检测器被设置为至少一部分所述状态索引路径度量的计算是通过使用模运算来完成的。

11.如在权利要求9中所要求的装置，其特征在于该检测器包括

用于为不同的状态索引计算所述路径度量的装置(600)，

用于存储所述状态索引的路径度量的存储器(612)，

用于存储所述阈值的存储器(608)。

12.如在权利要求9中所要求的装置，其特征在于该检测器包括

用于存储所述最高的路径度量值的存储器(614)，

用于初始化阈值的装置(616)，所述阈值按照如下公式进行初始化：THi＝(PM_MAX+Ci)mod 2D，其中THi是阈值，PM_MAX是最高的路径度量值，Ci是负的常数，且C₁＞C₂＞C₃...C_N，D是任意两个路径度量之间可能的最大差，mod为模运算符。

13.如在权利要求9中所要求的装置，其特征在于该检测器包括

用于存储所述最高的路径度量值的存储器(614)，

用于规定阈值的装置(616)，所述阈值按照如下公式进行自我更新：THi＝(THi+d)mod 2D，其中THi是阈值，d是新的最高路径度量值与之前的最高路径度量值之间的差，D是任意两个路径度量之间可能的最大差，mod为模运算符。

14.如在权利要求9中所要求的装置，其特征在于该检测器包括一组阈值被事先存储到的存储器(628)，以及被安排来从所述预置的阈值中选择在每一级被计算时所使用的阈值的装置(616)。

15.如在权利要求9中所要求的装置，其特征在于该检测器被设置为根据所述状态索引值选择所述阈值。

16.如在权利要求9中所要求的装置，其特征在于该检测器包括用于为不同的状态索引计算路径度量的装置(600)，

用于存储所述状态索引的路径度量的存储器(640)，

用于存储所述状态索引的所述存储器位置的地址的存储器(636)，

用于存储所述阈值的存储器(628)。

Images