通信系统中特殊同步序列的快速搜索法

摘要

本发明涉及一种特殊同步序列的快速搜索方法,是在待搜索比特流中,从搜索指针向前跳跃N比特再逆向搜索比较的跳跃式搜索方法。包括:选择一个起点作为搜索指针;在向前跳跃N比特的位置处进行逆向搜索比较;从比较比特不匹配位置向前路跃N比特的位置处再进行逆向搜索比较;重复执行上述步骤,直至找到同步特殊序列或搜索完整个比特流。由于本次还需搜索的比特个数为N减去上次搜索已找到的匹配比特的个数,因而可提高搜索效率及降你搜索成本。

说明书

本发明涉及通信技术领域中同步序列的搜索方法，更确切地说是涉及一种通信系统中特殊同步序列的快速搜索方法。

在通信系统中，为保证发送方的数据能准确传送到接收方，同步技术措施是必不可少的。其中，同步序列的搜索有硬件和软件两种方法。硬件搜索方法的优点是搜索速度快，但需要较高的成本；软件搜索方法的优点是搜索灵活性好、成本低，但搜索速度较慢。由于同步序列的搜索需在通信系统中占据一定的时间资源，因此为了降低搜索成本和提高搜索效率，有必要不断改进同步序列的搜索方法。

现有的许多搜索方法都是基于普遍性原理作出的，对具有特殊特征的同步序列的搜索则较少涉及。但事实上，这种具有特殊特征的同步序列在通信系统中却很常见，例如全‘0’序列、全‘1’序列等。

本发明的目的是设计一种通信系统中特殊同步序列的快速搜索法，解决具有特殊特征的同步序列的搜索问题，根据同步序列的特殊特征，而提供一种快速搜索方法，以加快搜索速度、提高搜索效率及降低搜索成本。

本发明的目的是这样实现的：一种通信系统中特殊同步序列的快速搜索法，其特征在于：是在待搜索比特流中，从搜索指针向前跳跃N比特再逆向搜索比较的跳跃式搜索方法。

所述的跳跃式搜索方法包括以下步骤：

a.在由若干比特组成的比特流中任意选择一个起点作为搜索指针；

b.从搜索指针处向前跳跃N比特的位置处进行逆向搜索比较；

c在发现待比较比特不匹配时，将该不匹配位置作为新的搜索指针，再从该搜索指针处向前跳跃N比特的位置处进行逆向搜索比较；

d.重复执行步骤c的操作，直至找到特殊同步序列或搜索完整个比特流。

每次跳跃发生后，下次还需要搜索的比特个数为N减去上次搜索已找到的匹配比特的个数。

所述的N是特殊同步序列的长度。

所述的特殊同步序列为全‘0’序列或全‘1’序列。

本发明的特殊同步序列的快速搜索法是在待搜索比特流中，从搜索指针向前跳跃N比特再逆向比较搜索的跳跃式搜索方法。在由若干比特组成的比特流中，假定同步序列为N个全‘0’(或全‘1’)序列，选择一个起点即搜索指针，然后从起点即搜索指针处向前跳跃(偏移)N比特，并从该位置处开始逆向搜索。从该位置逆向搜索的N个比特中只要有任一比特不匹配，则总的满足匹配要求的比特数必然小于N，也就是说，若搜索到某一位置后，发现待比较比特不匹配，则从当前位置即搜索指针向前跳跃N比特，并从该处再逆向搜索。依次类推，直到找到同步或搜索完整个比特流。

本发明的通信系统中特殊同步序列的快速搜索法，是利用通信系统中的同步序列具有某种特殊性而提出的，可加快搜索速度提高搜索效率，且特殊同步序列的长度越长，则本发明搜索方法的优势就越明显。

下面结合实施例及附图进一步说明本发明的技术

图1是本发明特殊同步序列的跳跃式搜索方法的过程示意图

图2是本发明特殊同步序列效率问题的说明示意图

参见图1，图中示意给出特殊同步序列的快速跳跃式搜索方法的过程。这种搜索方法，之所以称之为跳跃式搜索，是因为它不比较所有待搜索的比特位，而是有选择的比较“某些”更有意义的比特位。

假设同步序列的长度为N比特，从位置0开始搜索。定义两个变量PrevHeadLeft和HeadSearch来说明本发明的搜索过程，其中变量PrevHeadLeft表示前次搜索中还需搜索的‘0’(或‘1’)的个数(初始为N)，变量HeadSearch表示本次搜索中需搜索‘0’(或‘1’)的个数(初始为N)。

第一次搜索时，从位置0即搜索指针向前跳跃(偏移)N比特，即从位置A开始逆向搜索，每搜索到一个匹配比特时，则本次搜索中还需搜索‘0’(或‘1’)的个数减1，用变量表示为：

                     HeadSearch＝HeadSearch-1

若在位置B搜索到不匹配比特，则从当前的B位置即新的搜索指针向前跳跃N比特，到达位置C，此时上次还需搜索的比特数为：

                     PrevHeadLeft＝HeadSearch

而此时从位置C往回只需搜索：

            HeadSearch＝N-(N-PrevHeadLeft)＝PrevHeadLeft

若从C处开始继续逆向搜索到下一个不匹配比特是位置D，此时共找到匹配比特的个数是上次剩余的未搜索比特个数与本次还需搜索的比特个数的差值，那么上次还需搜索的比特个数用变量表示为：

   HeadSearch＝N-(PrevHeadLeft-HeadSearch)...................(1)

再从新的搜索指针即从位置D向前跳跃N比特到达位置E，因此，下一个开始逆向搜索的位置是与D距离为N比特的位置E，那么上次搜索中还需搜索的比特个数用变量表示为：

  PrevHeadLeft＝HeadSearch＝N-(PrevHeadLeft-HeadSearch).......(2)

若位置E的搜索比特就不匹配，则PrevHeadLeft＝HeadSearch，按照公式(1)、(2)计算出

                      PrevHeadLeft＝HeadSearch＝N

这和初始状态相同，因此初始状态也满足计算公式(1)、(2)。

采用本发明的同步搜索方法，最好的情况应是在第一次逆向搜索中就找到同步序列，即起始位置及其后的连续N个比特就是同步序列；最坏的情况是每个比特都被搜索了一次。其中最坏情况出现的条件是每次逆向搜索到N-1个连续匹配比特，而第N个比特不匹配。

参见图2，图中每一个小方格代表一个比特，图中有ASCII字母的方格表示该位置比特不匹配。比特流按照从左到右、从上到下的方式存放。每行的比特数为N个。若搜索指针从A前面的比特开始逆向搜索，到第N比特即位置0时搜索到不匹配比特，应从位置A处开始跳跃，由于位置A处的比特不匹配，则应从位置C的前一比特位置处开始逆向搜索。依此类推，在无法搜索到同步序列的情况下，每个比特最多搜索一次。但实际上，这种最坏情况下的比特流是很少存在的，因为它不含任何有用的信息。

将上述特殊同步序列的快速算法应用在GSM移动通信系统中作为本发明方法的实施例，GSM移动通信系统中有一个码率适配单元TRAU，用于将20ms的语音/数据中的有效比特取出进行编码。从另一个角度来说，就是将16kb/s的数据转换成13kb/s(语音业务)或12kb/s及以下(数据业务)的速率。根据协议要求，在其转换过程中，必然要搜索作为同步的16个连续‘0’(N＝16)。

根据前面的分析，最好的情况是比特流的首16个比特已满足同步序列的要求，它所需搜索的次数就是16次。由于TRAU帧格式的特殊性，每16个比特中有一个同步比特‘1’，按照逆向进行搜索，在搜索过程中，搜索指针位总是向这个同步比特靠拢。一旦搜索到同步比特‘1’，则以后每16个比特只要进行一次搜索。因此，在最差的情况下，共需比较16个同步序列比特、18个同步比特‘1’和向同步比特‘1’靠拢的16个比特，即可用16+16+18＝50次搜索完整个16+16+18×16＝320比特。采用此种搜索方法，估计的平均比较次数是(16+50)/2＝33次，效率是逐位比较的平均次数160(320/2)的5倍多。