基于FFT的直扩序列周期相关函数的计算

１引言

随着全球定位系统（ＧＰＳ，ＧｌｏｂａｌＰｏｓｉｔｉｏｎＳｙｓｔｅｍ）、移动码分多址（ＣＤＭＡ，ＣｏｄｅＤｉｖｉｓｉｏｎＭｕｌｔｉｐｌｅＡｃｃｅｓｓ）、ＩＥＥＥ８０２．１１ｂ无限局域网（ＷＬＡＮ，ＷｉｒｅｌｅｓｓＬｏｃａｌＡｒｅａＮｅｔｗｏｒｋ）和直扩扩谱超宽带无线电（ＤＳＳＳ－ＵＷＢ，ＤｉｒｅｃｔＳｅｑｕｅｎｃｅＳｐｒｅａｄＳｐｅｃｔｒｕｍＵｌｔｒａＷｉｄｅｂａｎｄ）等技术的兴起，目前研究直扩序列（ＤＳ，ＤｉｒｅｃｔＳｅｑｕｅｎｃｅ）的焦点已经由它的伪随机性能转向了它的多址性能。人们希望构造出具有优良多址性能的直扩序列，从而减小各个用户之间的多址干扰。

直扩序列的多址性能一般采用周期相关函数来评估，当序列的周期较长（这也是目前使用直扩序列的实际情况）时，周期相关函数的计算量是惊人的。虽然，对于某些序列（例如具有三值互相关特性的Ｇｏｌｄ序列），更多地关心它的相关函数的取值。但是，这些相关函数值的分布状况也同样有意义。这一点对于目前正在被广泛研究和讨论的一类新的直扩序列——

—零相关区（ＺＣＺ，ＺｅｒｏＣｏｒｒｅｌａｔｉｏｎＺｏｎｅ）直扩序列［１－４］尤其重要。对于ＺＣＺ－ＤＳ，已经不再关心它的最大相关值是多少，而是重点研究它在某一段区域内的相关值分布状况。因此，如何快速有效地计算出直扩序列的周期相关函数，已经成为一个需要解决的问题。

本文基于快速傅立叶变换（ＦＦＴ，ＦａｓｔＦｏｕｒｉｅｒＴｒａｎｓｆｏｒｍ），给出了一种计算周期相关函数的计算方法。该方法可以显著提高运算效率，从而为直扩序列的构造和性能评估提供了便利的工具。

２直扩序列的周期相关函数及其运算量

周期相关函数是评估直扩序列相关性能的重要指标，可以使用两个直扩序列矢量的内积来计算。令ａｉ＝｛ａ

０

ｉ

，ａ

１

ｉ

，…，ａ

Ｌ－１

ｉ

｝和

ａｊ＝｛ａ

０

ｊ

，ａ

１

ｊ

，…，ａ

Ｌ－１

ｊ

｝分别表示两个周期为Ｌ的直扩序列，则它们的周期相关函数可定义如下：

Ｄｉｊ（!）＝

Ｌ－１

ｋ＝０

!ａｋｉａｋ＋!ｊ（１）

基于ＦＦＴ的直扩序列周期相关函数的计算

张振宇１，２，宣贵新２，曾凡鑫２

ＺＨＡＮＧＺｈｅｎ－ｙｕ１，２，ＸＵＡＮＧｕｉ－ｘｉｎ２，ＺＥＮＧＦａｎ－ｘｉｎ２

１．重庆大学通信工程学院，重庆４０００４４

２．重庆通信学院信息工程系，重庆４０００３５

１．ＣｏｌｌｅｇｅｏｆＣｏｍｍｕｎｉｃａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＣｈｏｎｇｑｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ４０００４４，Ｃｈｉｎａ

２．ＤｅｐａｒｔｍｅｎｔｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＣｈｏｎｇｑｉｎｇＣｏｍｍｕｎｉｃａｔｉｏｎＩｎｓｔｉｔｕｔｅ，Ｃｈｏｎｇｑｉｎｇ４０００３５，Ｃｈｉｎａ

Ｅ－ｍａｉｌ：ｃｑｚｈａｎｇｚｙ＠ｙａｈｏｏ．ｃｏｍ．ｃｎ

ＺＨＡＮＧＺｈｅｎ－ｙｕ，ＸＵＡＮＧｕｉ－ｘｉｎ，ＺＥＮＧＦａｎ－ｘｉｎ．ＦＦＴ－ｂａｓｅｄｃｏｍｐｕｔａｔｉｏｎｏｆｐｅｒｉｏｄｉｃｃｏｒｒｅｌａｔｉｏｎｆｕｎｃｔｉｏｎｓｏｆｄｉｒｅｃｔｓｅｑｕｅｎｃｅｓ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（１０）：９３－９５．

Ａｂｓｔｒａｃｔ：Ｔｈｅｐｅｒｉｏｄｉｃｃｏｒｒｅｌａｔｉｏｎｆｕｎｃｔｉｏｎｉｓａｎｉｍｐｏｒｔａｎｔｉｎｄｅｘｔｏｅｖａｌｕａｔｅｄｉｒｅｃｔｓｅｑｕｅｎｃｅｓ．Ｗｈｅｎｔｈｅｐｅｒｉｏｄｏｆｄｉｒｅｃｔｓｅｑｕｅｎｃｅｓｉｎｃｒｅａｓｅｓ，ｔｈｅｎｕｍｂｅｒｏｆｃｏｍｐｕｔａｔｉｏｎｓｏｆｔｈｉｓｆｕｎｃｔｉｏｎｗｉｌｌｉｎｃｒｅａｓｅｒａｐｉｄｌｙ．Ｉｎｏｒｄｅｒｔｏｓｏｌｖｅｓｕｃｈｐｒｏｂｌｅｍ，ａＦＦＴ－ｂａｓｅｄｆａｓｔｍｅｔｈｏｄｔｏｃｏｍｐｕｔｅｔｈｅｐｅｒｉｏｄｉｃｃｏｒｒｅｌａｔｉｏｎｆｕｎｃｔｉｏｎｉｓｐｒｅｓｅｎｔｅｄ．Ｂｙｕｓｉｎｇｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄ，ｔｈｅｎｕｍｂｅｒｏｆｃｏｍｐｕｔａｔｉｏｎｓｃａｎｂｅｇｒｅａｔｌｙｄｅｃｒｅａｓｅｄ，ｗｈｉｃｈｇｉｖｅｓｆａｃｉｌｉｔｉｅｓｆｏｒａｎａｌｙｓｉｓａｎｄｃｏｎｓｔｒｕｃｔｉｏｎｓｏｆｄｉｒｅｃｔｓｅｑｕｅｎｃｅｓ．

Ｋｅｙｗｏｒｄｓ：ｄｉｒｅｃｔｓｅｑｕｅｎｃｅｓ；ｐｅｒｉｏｄｉｃｃｏｒｒｅｌａｔｉｏｎｆｕｎｃｔｉｏｎ；ＦａｓｔＦｏｕｒｉｅｒＴｒａｎｓｆｏｒｍ

摘要：周期相关函数是评估直扩序列相关性能的重要指标。随着直扩序列周期的增加，该函数的运算量将迅速增加。为了解决大运算量问题，论文基于ＦＦＴ给出了一种快速计算周期相关函数的方法。通过使用该方法，可以大大减少运算次数，从而为直扩序列的分析和构造提供便利的工具。

关键词：直扩序列；周期相关函数；快速傅立叶变换

文章编号：１００２－８３３１（２００７）１０－００９３－０３文献标识码：Ａ中图分类号：ＴＮ９１１

基金项目：重庆市自然科学基金项目（ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｏｎｇｑｉｎｇＣｉｔｙｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．２００６ＢＢ２１３２）；重庆邮电大学开放基金项目。

作者简介：张振宇（１９７７－），男，重庆大学博士研究生，讲师，目前主要研究方向为序列设计、信号与信息处理；宣贵新（１９８０－），女，硕士研究生，目前主要研究方向为序列设计、信号与信息处理；曾凡鑫（１９６４－），男，硕士研究生导师，目前主要研究方向为序列设计、信号与信息处理、超宽带无线电和纠错编码理论。

９３

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

２００７，４３（１０）其中，下标ｋ＋!采用模Ｌ的运算。两序列ａｉ，ａｊ∈｛１，－１｝，当直扩序列是由移位寄存器产生的｛０，１｝序列时，变换关系为０→１，

１→－１。当ｉ＝ｊ时，Ｄｉｉ（!）表示序列ａｉ的周期自相关函数；当ｉ≠ｊ

时，Ｄｉｊ（!）表示序列ａｉ和序列ａｊ周期互相关函数。既然Ｄｉｊ（!）（或Ｄｉｉ（!））是周期的，那么时移!只要取在一个周期内就可以表示全部的信息，一般有０≤!≤Ｌ－１。

下面来分析直接计算式（１）的运算量。当计算任意一个时移!的Ｄｉｊ（!）时，需要Ｌ次实数乘法，Ｌ－１次实数加法。那么，当

!取遍０到Ｌ－１时，总共需要Ｌ２次实数乘法，Ｌ（Ｌ－１）次实数加

法。可以看出，周期相关函数的直接运算量是序列周期的平方函数（或近似为平方函数）。

从而，随着序列周期的增加，运算量将急剧增大。这就给分析和评估直扩序列的性能带来了不便，需要找到一种快速的计算方法来减少运算量。

３基于ＦＦＴ的周期相关函数的计算

ＦＦＴ是离散傅立叶变换的一种快速算法。

在数字信号处理中，人们通常基于ＦＦＴ并利用圆周卷积定理来计算两个序列的线性卷积。根据这种思想，基于ＦＦＴ并利用圆周相关定理来计算两个直扩序列的周期相关函数。与以往人们利用ＦＦＴ、圆周相关定理和维纳－欣钦公式来计算随机信号的功率谱密度不同，本文要处理的信号是两个等周期的确定信号，不需要由线性相关到圆周相关的转换关系。另外，直扩序列的周期都近似等于（或完全等于，例如对于目前已经构造的绝大多数的ＺＣＺ－

ＤＳ的周期）２的整数次幂，那么运算时只需要补上很少的零值

（或不用补零）就可以计算ＦＦＴ，这更增加了计算周期相关函数的效率。为了详细阐述本文所提出的计算方法，首先介绍圆周相关定理。

圆周相关定理［５］：令ｘ［ｎ］和ｙ［ｎ］分别表示两个Ｎ点的序列，

Ｘ［ｋ］表示ｘ［ｎ］的Ｎ点ＤＦＴ，Ｙ［ｋ］表示ｙ［ｎ］的Ｎ点ＤＦＴ。那么，两

个序列ｘ［ｎ］和ｙ［ｎ］的圆周相关ｒｘｙ［ｍ］＝

Ｎ－１

ｎ＝０

%ｘ［ｎ］・ｙ［ｎ＋ｍ］（这里ｎ＋ｍ

采用模Ｎ运算，并且有０≤ｍ≤Ｎ－１）的点ＤＦＴ满足如下关系，

Ｒｘｙ［ｋ］＝Ｘ［ｋ］・Ｙ＊［ｋ］

（２）

其中Ｙ＊［ｋ］，表示Ｙ［ｋ］的共轭序列。

从上面的圆周相关定理能够看出，计算两个直扩序列的周期相关函数（在这里相当于圆周相关），可以通过以下三个步骤来完成。

（１）计算两个直扩序列各自的ＤＦＴ；

（２）将其中一个ＤＦＴ取共轭后与另一个ＤＦＴ相乘；（３）对该乘积取离散傅立叶反变换（ＩＤＦＴ，ＩｎｖｅｒｓｅＤｉｓｃｒｅｔｅ

ＦｏｕｒｉｅｒＴｒａｎｓｆｏｒｍ）。

虽然这种处理方法看似复杂，需要进行多次处理，但是其中的ＤＦＴ和ＩＤＦＴ都可以使用快速算法ＦＦＴ，从而大大减少了运算量。

对于这种基于ＦＦＴ和圆周相关定理的处理思想，下面给

出了使用Ｍａｔｌａｂ语言编写的简单程序。该程序是计算两个直扩序列的周期相关函数的处理步骤，如果需要其它处理，只要

增加相应的辅助程序即可实现。

％基于ＦＦＴ的直扩序列周期相关函数的计算；

ａ＝ｉｎｐｕｔ（‘Ｔｙｐｅｉｎｔｈｅｆｉｒｓｔｓｅｑｕｅｎｃｅ＝’）；ｂ＝ｉｎｐｕｔ（‘Ｔｙｐｅｉｎｔｈｅｓｅｃｏｎｄｓｅｑｕｅｎｃｅ＝’

）；Ａ＝ｆｆｔ（ａ）；Ｂ＝ｆｆｔ（ｂ）；Ｂ１＝ｃｏｎｊ（Ｂ）；Ｃ＝Ａ．＊Ｂ１；ｃ＝ｉｆｆｔ（Ｃ）；

为了体现本文所给出的直扩序列周期相关函数计算方法的效率，将分析使用该方法后的运算量。众所周知，对于一个Ｌ点的ＦＦＴ，需要

Ｌ

２

ｌｏｇ２Ｌ次复数乘法和Ｌｌｏｇ２Ｌ次复数加法。那么，根据上面所给出的三个步骤，利用圆周相关定理计算直扩序列的周期相关函数，总共需要Ｌ＋

３Ｌ

２

ｌｏｇ２Ｌ次复数乘法和３ｌｏｇ２Ｌ次复数加法。另外，一次复数乘法需要四次实数乘法和

二次实数加法，一次复数加法需要二次实数加法。所以可以得出如下结果：

实数乘法总数：

Ｎｍ＝４Ｌ＋６Ｌｌｏｇ２Ｌ

（３）实数加法总数：

Ｎａ＝２Ｌ＋９Ｌｌｏｇ２Ｌ

（４）

为了更加直观地比较周期相关函数的直接运算量与基于

ＦＦＴ的运算量的差异，以实数乘法次数为例，给出了图１。从图１中可以看出，随着序列周期的增加，通过式（１）直接计算直扩

序列周期相关函数的计算量将急剧增加，而采用ＦＦＴ之后，其

９４

１０）

（上接６２页）

例题的实验表明，结果是令人满意的。（收稿日期：２００６年８月）

参考文献：

［１］ＣｕｔｌｅｒＲＢ．Ｄｅｒｉｖａｔｉｏｎｏｆｍｉｎｉｍａｌｓｕｍｓｆｏｒｃｏｍｐｌｅｔｅｌｙｓｐｅｃｉｆｉｅｄｆｕｎｃｔｉｏｎｓ［Ｊ］．ＩＥＥＥＴｒａｎｓ，１９８７ｃ－３６（３）．

［２］ＢａｈｎｓｅｎＲＪ．Ｅｓｓｅｎｔｉａｌｐｒｉｍｅｉｍｐｌｉｃａｔｅｔｅｓｔｅｒ［Ｊ］．ＩＢＭＴｅｃｈＤｉｓｃｌｏｓｕｒｅ

Ｂｕｌｌｅｔｉｎ，２００４，２４（５）．

［４］ＢｒａｙｔｏｎＲ．ＬｏｇｉｃｍｉｎｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｆｏｒＶＬＳＩｓｙｎｔｈｅｓｉｓ［Ｄ］．Ｂｏｓｔｏｎ，ＭＡ：ＫｌｕｗｅｒＡｃａｄｅｍｉｃ，１９８４．

［５］ＳｈａｎｎｏｎＣＥ．Ｔｈｅｓｙｎｔｈｅｓｉｓｏｆｔｗｏ－ｔｅｒｍｉｎａｌｓｗｉｔｃｈｉｎｇｃｉｃｕｉｔｓ［Ｊ］．ＢｅｌｌＳｙｓＴｅｃｈＪ，１９４８．

［６］ＤｒｅｃｈｓｌｅｒＲ．ＵｓｉｎｇｌｏｗｅｒｂｏｕｎｄｓｄｕｒｉｎｇｄｙｎａｍｉｃＢＤＤｍｉｎｉｍｉｚａ－ｔｉｏｎ［Ｊ］．ＩＥＥＥＴｒａｎｓｏｎＣＡＤ，２００１（１）：５１－５７．

计算量增长缓慢。这种结果与利用ＦＦＴ计算线性卷积的道理是一样的。另外，为了更加清楚地描绘两种计算量在序列周期较短时的关系，对计算量进行了取常用对数的处理（例如，将Ｎｍ变换成１０ｌｇＮｍ，这样仍然可以保持两种计算量的关系不变），并给出了图２。从图２中可以看出，当序列的周期Ｌ＜６４（即Ｌ＝２，４，８，１６，３２）时，直接计算量小于基于ＦＦＴ的计算量。当Ｌ≥６４（图２种虚线所示位置）时，基于ＦＦＴ的计算量开始小于直接计算量。

４应用举例

这种基于ＦＦＴ并利用圆周相关定理的方法可以快速计算直扩序列的周期相关函数，那么可以以周期相关函数为出发点，很方便地对直扩序列进行各种所需要的分析和观察。下面将利用这种计算方法，来分析ＺＣＺ－ＤＳ的相关性能。

使用文献［６］中构造ＩＩ的ＺＣＺ－ＤＳ为例进行说明，该类序列满足Ｆ（Ｌ，Ｍ，ＺＣＺ）＝（２２ｎ＋ｍＬ０，２ｎ＋１，２ｎ＋ｍ＋１）。其中Ｌ表示序列的周期，Ｍ表示序列的数目，ｎ、ｍ和Ｌ０是决定序列性能指标的参数，ＺＣＺ＝ｍｉｎ｛ＺＡＣＺ，ＺＣＣＺ｝，ＺＡＣＺ表示周期零自相关区的取值，ＺＣＣＺ表示周期零互相关区的取值。

对于ＺＣＺ－ＤＳ，人们最关心它的相关函数值的分布状况，

研究它具有怎样的零相关区特性。本例中取ｎ＝２，ｍ＝３，Ｌ０＝２，则可得到满足的Ｆ（Ｌ，Ｍ，ＺＣＺ）＝（２５６，８，３３）ＺＣＺ－ＤＳ。在这里，序列的周期Ｌ＝２８＝２５６，如果采用直接计算，需要Ｌ２＝２１６次的实数乘法，其运算量很大（尽管周期自相关函数具有对称性，可减少一半的运算量，但是直接计算仍然需要２１５次的实数乘法），所以应该使用本文所提出的快速计算方法。

经快速计算后，为了直观地观察该序列的零相关区特性，给出了序列周期相关函数值的分布状况。图３给出了所用的ＺＣＺ－ＤＳ中序列ａ５与ａ８序列的周期互相关分布状况，图４给出了所用的ＺＣＺ－ＤＳ中序列ａ５的周期自相关分布状况。为了更加清楚地在文中显示，只是截取了分布状况中的－５０≤!≤５０一段来进行观察。通过图３和图４可以看出，在零相关区ＺＣＺ＝３３的范围内，ＺＣＺ－ＤＳ的周期异相自相关值（即!≠０）和周期互相关值都为零，从而可以实现正交通信，有效地排除多址干扰。

５结束语

本文所提供的直扩序列周期相关函数的计算方法，可以有效地解决大运算量的问题。基于这种计算方法，能够方便地处理各类关于直扩序列周期相关函数的运算。它并不局限于本文所给出的周期相关函数值分布状况的例子，也可以进行求取最大相关值、最大相关值发生的位置以及各相关值所占比例等人们通常关心的直扩序列的研究问题。（收稿日期：２００６年８月）

参考文献：

［１］ＳｕｅｈｉｒｏＮ．Ａｓｉｇｎａｌｄｅｓｉｇｎｗｉｔｈｏｕｔｃｏ－ｃｈａｎｎｅｌｉｎｔｅｒｆｅｒｅｎｃｅｆｏｒａｐ－ｐｒｏｘｉｍａｔｅｌｙｓｙｎｃｈｒｏｎｉｚｅｄＣＤＭＡｓｙｓｔｅｍ［Ｊ］．ＩＥＥＥＪＳｅｌＡｒｅａｓＣｏｍ－ｍｕｎ，１９９４，ＳＡＣ－１２：８３７－８４１．

［２］ＣｈａＪ，ＨｕｒＮ，ＭｏｏｎＫ，ｅｔａｌ．ＺＣＤ－ＵＷＢｓｙｓｔｅｍｕｓｉｎｇｅｎｈａｎｃｅｄＺＣＤｃｏｄｅｓ［Ｃ］／／ＰｒｏｃＵＷＢＳＴ＆ＩＷＵＷＢＳ２００４，Ｋｙｏｔｏ，Ｊａｐａｎ，Ｍａｙ１８－２１，２００４．

［３］ＺｈａｎｇＣ，ＬｉｎＸ，ＨａｔｏｒｉＭ．Ｎｏｖｅｌｔｗｏｄｉｍｅｎｓｉｏｎａｌｃｏｍｐｌｅｍｅｎｔａｒｙｓｅｑｕｅｎｃｅｓｉｎｕｌｔｒａｗｉｄｅｂａｎｄｗｉｒｅｌｅｓｓｃｏｍｍｕｎｉｃａｔｉｏｎｓ［Ｃ］／／ＰｒｏｃＩＥＥＥＵＷＢＳＴ２００３，Ｖｉｒｇｉｎｉａ，ＵＳＡ，Ｎｏｖ１６－１９，２００３．

［４］ＺｅｎｇＦ，ＺｈａｎｇＺ，ＧｅＬ．Ｔｈｅｏｒｅｔｉｃａｌｌｉｍｉｔｏｎｔｗｏｄｉｍｅｎｓｉｏｎａｌｇｅｎｅｒ－ａｌｉｚｅｄｃｏｍｐｌｅｍｅｎｔａｒｙｏｒｔｈｏｇｏｎａｌｓｅｑｕｅｎｃｅｓｅｔｗｉｔｈｚｅｒｏｃｏｒｒｅｌａｔｉｏｎｚｏｎｅｉｎｕｌｔｒａｗｉｄｅｂａｎｄｃｏｍｍｕｎｉｃａｔｉｏｎｓ［Ｃ］／／ＰｒｏｃＵＷＢＳＴ＆ＩＷＵＷＢＳ２００４，Ｋｙｏｔｏ，Ｊａｐａｎ，Ｍａｙ１８－２１，２００４．

［５］ＯｐｐｅｎｈｅｉｍＡＶ，ＳｃｈａｆｅＷＲ．Ｄｉｇｉｔａｌｓｉｇｎａｌｐｒｏｃｅｓｓｉｎｇ［Ｍ］．［Ｓ．ｌ．］：ＰｒｅｎｔｉｃｅＨａｌｌ，Ｉｎｃ，１９７５．

［６］ＦａｎＰ，ＳｕｅｈｉｒｏＮ，ＤｅｎｇＸ．Ａｃｌａｓｓｏｆｂｉｎａｒｙｓｅｑｕｅｎｃｅｓｗｉｔｈｚｅｒｏｃｏｒｒｅｌａｔｉｏｎｚｏｎｅ［Ｊ］．ＩＥＥＥｌｅｃｔｒｏｎＬｅｔｔ，１９９９，３５：７７７－７７９．

张振宇，宣贵新，曾凡鑫：基于ＦＦＴ的直扩序列周期相关函数的计算９５