移动通信中无三阶互调的实时频率分配算法及实现方案
摘要：短波、超短波移动电台通信, 卫星通信与其它通信设备中, 由于收发信机, 特别是收信前级与发信末级放大器的非线性, 会产生大量交叉调制分量, 其中以三阶互调影响最大。在指定的使用频带宽度内, 如何分配尽可能多的频道, 使同一地区内各频率无三阶互调, 所有地区的全部使用频率无重复, 这就是移动电台的频率分配间题。工程界对这问题尚缺乏合适的数学理论, 仅在频道数目小时, 有一些用计算机试算的办法（实质上是穷举法）。文献[3]借助抽象代数与组合数学等工具, 提出了一个准最优的频率分配方法。在文献[3]的基础上, 本文给出了无三阶互调的频道数目的上界公式。为了使工程界能具体使用文献[3]提出的数学方法, 给出了简化算法及有关的理论分析。还给出了应用此算法得到的计算结果, 这些结果可以直接供工程界用于频率分配。
频率分配的数学问题
移动电台的频率分配问题可以归结为以下数学问题:
设l 为区域数,t 为每个区域内的频道数,h 为频率序列所占用的频带宽度。
设 2 3. /为个正整数序列, 它们满足以下条件:
( ) ( )
(1)每个序列 的 ( ) 个正差值 ( ) 两
( )
( )
( )
( )
( )
( )
两相异;
(2)每个序列 的正差值都大于1;
(3)l个序列所有lt 个元两两相异, 即 。
把序列组* +记为 , 而把满足条件(1)-(3)的 的全体记为 ( ) 。令
( ) 2 3
( ) * ( ) ( )+.
所谓频率分配问题, 就是给定t,l, 设法构造出较好的序列组 ( ) , 使 ( ) 尽量小, 即接近或达到 ( ) 。这样的 所设计的频率分配, 由条件（1）保证了同一地区内使用的频率间无三阶交调；由条件（2）保证了同一地区内使用的频率间有工程技术所要求的间隔；由条件（3）保证了各地区的全部使用频率无重复；由 ( ) 尽量小, 使其总占用频带尽量窄。通信工程上常用l=7或5，t>l。
频率分配问题的另一种等价提法是：
令 ( ) { 存在 ( ) 使 ( ) }, 给定l,h ，求 ( ) ，使t 尽量大，即接近或达到 ( ) 。
本文主要根据文献[1]、[2]、[3],综合出一个准最优频率分配的简化算法，在此基础上进一步推导出一种 时的简化算法。
( )
( )
( )
算法的理论基础
定理 1 （H(t,l)的下界公式）
( ) ( )( )
( ) {
, -}
当 时，上式中 , 可进一步改为0 1 ,
-。
定理 2 （序列组的构造）
设p 为素数，m 为正整数， ， ，令 ( ) 为有限域 上以二次本原多项式f(x)为联结多项式的q 元二次最长线性移位寄存器序列。用序列( ) 的全部非零元定义q-1个 序列
2 3
其中 满足 ，且 ( ) ，则这
( ) ( ) ( )
( ) ( ) ( ) ( )
q-1个序列满足条件(1)和(3)。
定理 3 （渐近估计）
若 ，则有 ( ) 。 更进一步有 ( ) 的正常数，ε为任意小正数。
定理 4 （渐近估计） 若 , 更进一步有 定理 5
以 为联结多项式的q 元，二次线性移位寄存器序列
，这里 为与t 无关
, 则有 ( ) 。
( ) 。
( ) 为m 序列的充要条件是：存在某个i ，使
为本原元（即满足 的最
小正整数k 为q-1）。
p 为奇素数，关于GF(p)上二次本原多项式和不可约多项式，有下面定理：
定理 6
设 是GF(p)的本原元， ( ) ，则形如 的多项式中，有 ( ) ( ) 个是本原元多项式。
定理 7
设f(x)是GF(p)上首一的二次本原多项式，则f(0)是GF(p)的本原元。
定理 8
设 是GF(p)的本原元， ( )，则 在GF(p)上可约，当且仅当 ( ) ( ) 。
定理 9
设 是GF(p)的本原元，则GF(p)上形如 的不可约多项式有( ) 个。
定理1、2、3、4的证明见文献[1]，定理5的证明见文献[2]，定理6、7、8、9的证明见文献[3]。
频率分配的算法
(1) 输入t 、l ，求不小于t 且大于l 的最小素数p 。 (2) 求模p 的最小正原根 。
， ( ) ， ( ) ( ) ， 。当r(i+1)=1(mod p) (i=0,1,…,p-2) 为真时， 为p 的最小正原根 ，否则 ，继续上面过程，直至求出模p 的最小正原根。 (3) 求GF(p)上形如 的全部不可约多项式。
( ) * +。
先计算 { ( ) ( ) }, 再计算 * ( ) +，则I 中的每一多项式均不可约。
(4) 求一个p 元二次m 序列b 。
任取 ，置 ， ，及 。若( ) ( ) ( 是 ( ) 的本原元) 为真，则b 为p 元二次m 序列，否则从I 中另选 重算。 (5) 求出准最优的序列组 。
把 中全部非零元记为1,2, …,q-1，任取定 中一个非零元i ，当b 中的 时，取出下标号j, 共有q 个j ，j 从小到大排列后的序列记为 2 3,(即 ( ) ) 。对一个b 可得到
( ) ( ) ( )
q-1个 ,i=1,2,…,q-1。则在所有b 求出的 中挑出一组带宽最窄的。
(6) 由 求所需的频率序列。
2 3 , 根据准最优序列组 , 按两种情况分配所需的频率序列组
( )
( )
( )
( )
2 3 。 ① 给定起始频率 和最小频率间隔 则
( )
( ) ( ) ( )
. / 。
( )
② 给定频段范围，即起始频率 和终止频率 则
( )
( )
( )
( )
. / 。
计算结果
用C 语言编程列出了l=1时的一些准最优的无三阶互调序列 。
具体的C 语言程序
在VC6.0下运行。程序可以实现输入一个素数p ，可以输出p 个无三阶互调的序列组，并且该序列组是占用频带最窄的。
#include #include #include #include
#include //头文件
int minp(int p); //求p 的最小正原根的子函数
int main(void) {
int p,x1,k,i,j,q; //q为p 的最小正原根，k 为可约的项数，p
为素数，多项式如x^2+ax+b=0 可约项为 b=-x(x+a)，i 表示可约项r[i],j表示p 的加勒法域GF[j].
int GF[110]; //加勒法域 int b[5000]; //b序列
int **s; //s序列，即通过b 序列求得的序列组
int sn;
s=(int**)malloc(sizeof(int*)*500); for(sn=0;sn
s[sn]=(int*)malloc(sizeof(int)*500);
int r[50]; //r[50]为不可约的
int k1,k2,k3,k4,m,n; //k1为不可约的项数,m 判断有相同数的
标志
int l,key; //key为求s 序列时 所用GF[]中的数
scanf("%d",&p); //输入素数 q=minp(p); //求最小正原根 k1=(p-1)/2; k2=p-1;
int marka,markb; //标记 int rand1,rand2; //随机数
for(i=1;i
{
r[i]=-(pow(q,i)+pow(q,(p-i))); r[i]=r[i]%p; // r[i]=p+r[i];
} //r[i]为可约多项式系数 求可约多项式 k=1;
for(j=1;j
n=0;
{ } if(n==0) { }
GF[k++]=j; m=j-r[i]; if(m==0) { }
n=1;
} //GF[]为不可约多项式系数实现数组的减运算
for(k=1;k
{ //标记 } b[1]=0; b[2]=1;
for(key=1;key
if(abs(GF[k])>k2)
k2=k;
数
for(i=0;i
{
k=1+(int)((k2-1)*rand()/(RAND_MAX+1.0)); l=1;
for(k3=3;k3
b[k3]=-GF[k]*b[k3-1]-q*b[k3-2];
b[k3]=b[k3]%p; if(b[k3]
{ }
b[k3]=p+b[k3];
for(k3=2;k3
{
if(b[k3]==key) {
s[k][l++]=k3;
printf("%d ",s[k][l-1]);
宽
}
} markb=s[k][p]; } printf("**"); printf("%d",markb-marka);//标记量用于找到最窄的带 } } printf("***"); printf("\n"); free(s); getchar(); return 0;
int minp(int p) //求最小正原根的子函数 {
int q,r,n; for(q=2;q
} } { } if(n
移动通信中无三阶互调的实时频率分配算法及实现方案
摘要：短波、超短波移动电台通信, 卫星通信与其它通信设备中, 由于收发信机, 特别是收信前级与发信末级放大器的非线性, 会产生大量交叉调制分量, 其中以三阶互调影响最大。在指定的使用频带宽度内, 如何分配尽可能多的频道, 使同一地区内各频率无三阶互调, 所有地区的全部使用频率无重复, 这就是移动电台的频率分配间题。工程界对这问题尚缺乏合适的数学理论, 仅在频道数目小时, 有一些用计算机试算的办法（实质上是穷举法）。文献[3]借助抽象代数与组合数学等工具, 提出了一个准最优的频率分配方法。在文献[3]的基础上, 本文给出了无三阶互调的频道数目的上界公式。为了使工程界能具体使用文献[3]提出的数学方法, 给出了简化算法及有关的理论分析。还给出了应用此算法得到的计算结果, 这些结果可以直接供工程界用于频率分配。
频率分配的数学问题
移动电台的频率分配问题可以归结为以下数学问题:
设l 为区域数,t 为每个区域内的频道数,h 为频率序列所占用的频带宽度。
设 2 3. /为个正整数序列, 它们满足以下条件:
( ) ( )
(1)每个序列 的 ( ) 个正差值 ( ) 两
( )
( )
( )
( )
( )
( )
两相异;
(2)每个序列 的正差值都大于1;
(3)l个序列所有lt 个元两两相异, 即 。
把序列组* +记为 , 而把满足条件(1)-(3)的 的全体记为 ( ) 。令
( ) 2 3
( ) * ( ) ( )+.
所谓频率分配问题, 就是给定t,l, 设法构造出较好的序列组 ( ) , 使 ( ) 尽量小, 即接近或达到 ( ) 。这样的 所设计的频率分配, 由条件（1）保证了同一地区内使用的频率间无三阶交调；由条件（2）保证了同一地区内使用的频率间有工程技术所要求的间隔；由条件（3）保证了各地区的全部使用频率无重复；由 ( ) 尽量小, 使其总占用频带尽量窄。通信工程上常用l=7或5，t>l。
频率分配问题的另一种等价提法是：
令 ( ) { 存在 ( ) 使 ( ) }, 给定l,h ，求 ( ) ，使t 尽量大，即接近或达到 ( ) 。
本文主要根据文献[1]、[2]、[3],综合出一个准最优频率分配的简化算法，在此基础上进一步推导出一种 时的简化算法。
( )
( )
( )
算法的理论基础
定理 1 （H(t,l)的下界公式）
( ) ( )( )
( ) {
, -}
当 时，上式中 , 可进一步改为0 1 ,
-。
定理 2 （序列组的构造）
设p 为素数，m 为正整数， ， ，令 ( ) 为有限域 上以二次本原多项式f(x)为联结多项式的q 元二次最长线性移位寄存器序列。用序列( ) 的全部非零元定义q-1个 序列
2 3
其中 满足 ，且 ( ) ，则这
( ) ( ) ( )
( ) ( ) ( ) ( )
q-1个序列满足条件(1)和(3)。
定理 3 （渐近估计）
若 ，则有 ( ) 。 更进一步有 ( ) 的正常数，ε为任意小正数。
定理 4 （渐近估计） 若 , 更进一步有 定理 5
以 为联结多项式的q 元，二次线性移位寄存器序列
，这里 为与t 无关
, 则有 ( ) 。
( ) 。
( ) 为m 序列的充要条件是：存在某个i ，使
为本原元（即满足 的最
小正整数k 为q-1）。
p 为奇素数，关于GF(p)上二次本原多项式和不可约多项式，有下面定理：
定理 6
设 是GF(p)的本原元， ( ) ，则形如 的多项式中，有 ( ) ( ) 个是本原元多项式。
定理 7
设f(x)是GF(p)上首一的二次本原多项式，则f(0)是GF(p)的本原元。
定理 8
设 是GF(p)的本原元， ( )，则 在GF(p)上可约，当且仅当 ( ) ( ) 。
定理 9
设 是GF(p)的本原元，则GF(p)上形如 的不可约多项式有( ) 个。
定理1、2、3、4的证明见文献[1]，定理5的证明见文献[2]，定理6、7、8、9的证明见文献[3]。
频率分配的算法
(1) 输入t 、l ，求不小于t 且大于l 的最小素数p 。 (2) 求模p 的最小正原根 。
， ( ) ， ( ) ( ) ， 。当r(i+1)=1(mod p) (i=0,1,…,p-2) 为真时， 为p 的最小正原根 ，否则 ，继续上面过程，直至求出模p 的最小正原根。 (3) 求GF(p)上形如 的全部不可约多项式。
( ) * +。
先计算 { ( ) ( ) }, 再计算 * ( ) +，则I 中的每一多项式均不可约。
(4) 求一个p 元二次m 序列b 。
任取 ，置 ， ，及 。若( ) ( ) ( 是 ( ) 的本原元) 为真，则b 为p 元二次m 序列，否则从I 中另选 重算。 (5) 求出准最优的序列组 。
把 中全部非零元记为1,2, …,q-1，任取定 中一个非零元i ，当b 中的 时，取出下标号j, 共有q 个j ，j 从小到大排列后的序列记为 2 3,(即 ( ) ) 。对一个b 可得到
( ) ( ) ( )
q-1个 ,i=1,2,…,q-1。则在所有b 求出的 中挑出一组带宽最窄的。
(6) 由 求所需的频率序列。
2 3 , 根据准最优序列组 , 按两种情况分配所需的频率序列组
( )
( )
( )
( )
2 3 。 ① 给定起始频率 和最小频率间隔 则
( )
( ) ( ) ( )
. / 。
( )
② 给定频段范围，即起始频率 和终止频率 则
( )
( )
( )
( )
. / 。
计算结果
用C 语言编程列出了l=1时的一些准最优的无三阶互调序列 。
具体的C 语言程序
在VC6.0下运行。程序可以实现输入一个素数p ，可以输出p 个无三阶互调的序列组，并且该序列组是占用频带最窄的。
#include #include #include #include
#include //头文件
int minp(int p); //求p 的最小正原根的子函数
int main(void) {
int p,x1,k,i,j,q; //q为p 的最小正原根，k 为可约的项数，p
为素数，多项式如x^2+ax+b=0 可约项为 b=-x(x+a)，i 表示可约项r[i],j表示p 的加勒法域GF[j].
int GF[110]; //加勒法域 int b[5000]; //b序列
int **s; //s序列，即通过b 序列求得的序列组
int sn;
s=(int**)malloc(sizeof(int*)*500); for(sn=0;sn
s[sn]=(int*)malloc(sizeof(int)*500);
int r[50]; //r[50]为不可约的
int k1,k2,k3,k4,m,n; //k1为不可约的项数,m 判断有相同数的
标志
int l,key; //key为求s 序列时 所用GF[]中的数
scanf("%d",&p); //输入素数 q=minp(p); //求最小正原根 k1=(p-1)/2; k2=p-1;
int marka,markb; //标记 int rand1,rand2; //随机数
for(i=1;i
{
r[i]=-(pow(q,i)+pow(q,(p-i))); r[i]=r[i]%p; // r[i]=p+r[i];
} //r[i]为可约多项式系数 求可约多项式 k=1;
for(j=1;j
n=0;
{ } if(n==0) { }
GF[k++]=j; m=j-r[i]; if(m==0) { }
n=1;
} //GF[]为不可约多项式系数实现数组的减运算
for(k=1;k
{ //标记 } b[1]=0; b[2]=1;
for(key=1;key
if(abs(GF[k])>k2)
k2=k;
数
for(i=0;i
{
k=1+(int)((k2-1)*rand()/(RAND_MAX+1.0)); l=1;
for(k3=3;k3
b[k3]=-GF[k]*b[k3-1]-q*b[k3-2];
b[k3]=b[k3]%p; if(b[k3]
{ }
b[k3]=p+b[k3];
for(k3=2;k3
{
if(b[k3]==key) {
s[k][l++]=k3;
printf("%d ",s[k][l-1]);
宽
}
} markb=s[k][p]; } printf("**"); printf("%d",markb-marka);//标记量用于找到最窄的带 } } printf("***"); printf("\n"); free(s); getchar(); return 0;
int minp(int p) //求最小正原根的子函数 {
int q,r,n; for(q=2;q
} } { } if(n