1. 引言
冲突回避码(Conflict-avoiding Code,简记CAC)在无反馈多分址信道(冲突信道)有重要的应用 [1] [2]。类似于文献 [3] 其数学描述如下:
设
表示模
的剩余类环,
表示
。对于
阶子集
,定义
的差集为多重集合
设
是
一些
阶子集
的集合,则
被称为长度为
重量为
的冲突回避码若其满足以下条件
每个元素
称为一个码字。对于给定的
和
,符号
表示所有长度为
重量为
的冲突回避码。
对于冲突回避码
,码字的重量
(汉明码重量)表示用户在每个时段的
个时槽里发送
个数据包 [4]。对于给定的正整数
,如果
是一个码字个数最多的码,那么称
为一个最优码。
若
可以表示成为
的形式,则称
为等差(equi-difference)码字。
称为
的生成元。不难验证
。若码
的每个码字
都是等差码字,则称为
等差码。类似的,符号
表示所有长度为
重量为
的等差码。用符号
表示等差码
所有码字生成元的集合。等差码是一种特殊的码,人们通常利用它构造最优码。
目前,当
时的最优冲突回避码构造证明已经基本解决 [5] - [10]。当
的最优冲突回避码具体构造较少 [3] [4] [11]。本文利用利用欧拉函数和同余数在整数环的特性给出一种构造得新方法,给出新的构造方法,进一步给出当
时对最优冲突回避码具体构造的一些新结果。
2. 相关的构造
为了方便理解,我们介绍一些常用的概念和符号。
设
是奇素数,
是
的生成元,设
是
的
阶乘法子群,则
有陪集分解:
,其中
称陪集
为
阶分圆类。若
。则称
一个为
阶分圆类代表系。
引理1 [4]. 设
和
都是整数,
是素数且使得每一个
和
都各自形成一个
阶分圆类代表系。那么存在一个码
包含
个码字,且满足
。
引理2 [11]. 若
,则引理1构造的码
是最优的。
引理3 [4]. 设
,
和
都是正整数,且
,
。设
包含
个码字
使得
.
设
包含
个码字。设码
是由
生成。则
且包含
个码字。
利用引理1和引理2来具体构造一些最优冲突回避码。再利用引理3构造出一系列的冲突回避码
[3] [4]。但是,实际情况下,我们很难得到最优
。本文首次利用欧拉函数和同余数的特性,对
进行划分,得到类似于引理2的一般构造,并给出具体构造码重
时最优冲突回避码的一系列新结果。
3. 新的构造方法及其证明
设
为一个正整数,称
是
简约剩余系,则
,其中
是欧拉函数。显然,
是一个乘法群。
设
是奇素数,
为一个正整数,元素
是乘法群
的一个生成元,则
。又设
是
的
阶乘法子群,则
有陪集分解:
,其中
,称陪集
为2阶分圆类。若
。则称
为
的一个2阶分圆类代表系。下面得到类似于引理2的一般构造。
定理1. 设
是正整数,
是奇素数且使得每一个
和
都各自形成
的一个2阶分圆类代表系。那么存在一个码
包含
个码字,且满足
。
证 在
上设
则
的码字表示如下:
故
即
由
,
得,
。
定理 2. 定理1构造的码
是最优的。
因为
。
下面,根据同余性质结合定理1具体构造码重
时最优冲突回避码的一系列新结果,由定理2知,结果是最优的。
设
是奇素数,对于
,若同余方程
有解,称
为模
的二次剩余(quadratic residue) (即
)。否则,称
模
的二次非剩余(quadratic non-residue)
。定义
上的勒让德符号
为:
且具有性质
。
关于勒让德符号有如下结果。
引理 4 [12]. 若
是奇素数,则
引理5 [13]. 同余方程
,有解的充要条件是
。
推论1. 若素数
,
是正整数,则存在最优码
包含
个码字。
证 根据定理1~2和引理4~5并结合勒让德符号的性质,在
中只需证
对于每对
。即只需证
而当
时以上条件满足。从而命题得证。
推论2. 若素数
,
是正整数,则存在最优码
包含
个码字。
证 根据定理1~2和引理4~5并结合勒让德符号的性质,在
中只需证
对于每对
。即只需证
而当
时以上条件满足。从而命题得证。
推论3. 若素数
,
是正整数,则存在最优码
包含
个码字。
证 根据定理1~2和引理4~5并结合勒让德符号的性质,在
中只需证
对于每对
。即只需证
而当
时以上条件满足。从而命题得证。
推论4. 若素数
,
是正整数,则存在最优码
包含
个码字。
证 根据定理1~2和引理4~5并结合勒让德符号的性质,在
中只需证
对于每对
。即只需证
而当
时以上条件满足。从而命题得证。
4. 结论
本文给出新的构造方法具体构造出一系列最优的冲突回避码得。该方法也可以给光正交码的构造提供借鉴。
基金项目
广西自然科学基金项目(2018GXNSFAA281259)。
参考文献