Advances in Applied Mathematics
Vol. 08  No. 01 ( 2019 ), Article ID: 28622 , 7 pages
10.12677/AAM.2019.81016

Constructions of Nearly Optimal Codebooks Based on Cyclotomic Classes of Order Four

Rui Ma1, Wanfeng Qi1, Lingli Tang2

1School of Mathematics, Liaoning Normal University, Dalian Liaoning

2College of Science, Dalian Minzu University, Dalian Liaoning

Received: Jan. 2nd, 2019; accepted: Jan. 17th, 2019; published: Jan. 24th, 2019

ABSTRACT

Codebooks meeting the Welch bound are widely used in many research areas and applications. However, it is usually difficult to construct codebooks exactly meeting the Welch bound. A good substitute is to construct asymptotically optimal (N,K) codebooks which can approach codebooks meeting the Welch bound when N is large enough. In this paper, we construct a new class of codebook nearly meeting the Welch bound by using almost difference sets which consists of 4 order cyclotomic classes.

Keywords:Codebook, Welch Bound, Cyclotomic Class, Almost Difference Set

基于4阶分圆类的近似最佳码本的构造

马瑞1,亓万锋1,唐玲丽2

1辽宁师范大学,数学学院,辽宁 大连

2大连民族大学,理学院,辽宁 大连

收稿日期:2019年1月2日;录用日期:2019年1月17日;发布日期:2019年1月24日

摘 要

最佳码本在许多理论与实践中有着重要的应用。但构造最佳码本相对困难。一种替代方法是构造渐进最优码本,使得当码字足够长时,构造的渐进最优码本与最优码本足够接近。本文中利用基于四阶分圆类的几乎差集构造一类新的近似最佳码本。

关键词 :码本,Welch界,分圆类,几乎差集

Copyright © 2019 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

一个参数为 ( N , K ) 码本C是N个单位复向量构成的序列 { c 0 , c 1 , , c N } ,对于每个子码本 c i = ( c i , 0 , c i , 1 , , c i , K ) T 称为码字。码本C的最大相关值 [1] 定义为

I max ( C ) = max 0 i < j N 1 | c i c j H | ,

其中 c H 表示复向量c的共轭转置。在许多应用中,码本的性质与 I max ( C ) 大小紧密相关。特别的,希望码本C的最大互相关尽可能地小。Welch [1] 指出给定参数 ( N , K ) 后,码本的最大互相关有下界 I W

引理1 [1] . 对于任意的参数为 ( N , K ) 的码本 ( N , K ) 且满足 N K

I max ( C ) I W = N K ( N 1 ) K ,

等号成立当且仅当对于任意的 ( i , j ) i j | c i c j H | = N K ( N 1 ) K ,这时称C为最佳码本。

构造最佳码本十分困难,Fickus和Mixon给出了一些已有的最佳码本 [2] 。一种替代方法是构造近似最佳码本,使得当N足够大时,近似最佳码本的最大互相关值与最佳码本的足够接近。近似最佳码本的构造相对简单,并且在很多场合中与最佳码本性质近似。目前已有的方法主要可以归纳为采用几乎差集法 [3] [4] 、域上特征和法 [5] [6] 和bent函数法 [7] 等。张和冯 [8] 给出了八阶分圆类上的几乎差集构造的近似最佳码本。Hu和Wu [9] 采用定义了在差集的笛卡尔积上的近似最佳码本。本文将Hu和Wu的方法进行推广,构造了四阶分圆类对应的几乎差集的笛卡尔积上的近似最佳码本。

2. 基础知识

设G是一个有限交换群,D是群G的k阶子集。定义 Γ D ( ω ) = | D + ω D | ,其中 D + ω = { d + ω : d D } 。D被称为有限交换群G中参数为 ( v , k , λ , t ) 的几乎差集合,如果G中的t个非零元 ω 对应的 Γ D ( ω ) 取值为 λ ,其它 ( v 1 t ) 个非零元 ω 对应的 Γ D ( ω ) 取值为 λ + 1

F q 是q阶有限域, q = p m ,p是 F q 的特征。设 α F q 的一个本原元, F q * = F q \ { 0 } = α 。对有限域 F q ,存在q个从 F q 到复平面单位圆上的同态 χ ,满足

χ ( x + y ) = χ ( x ) χ ( y ) , x , y F q .

这种同态称为有限域 F q 的加法特征,简称特征 [10] 。这q个特征的集合记为 F ^ q 。如果 χ ( x ) 1 , x F q ,则称为平凡特征。设D是 F q 的子集,定义 χ ( D ) = x D χ ( x ) ,对两个不同的特征 χ 1 , χ 2 ,定义 ( χ 1 χ 2 ) ( g ) : = χ 1 ( g ) χ 2 ( g ) , g F q ,仍然是 F q 是的特征 [10] 。

对有限域 F q q = e f + 1 ( e 2 , f 2 ) ,可将其非零元素均分为 个子集: C l ( e , q ) = α l α e , 0 l e 1 C l ( e , q ) 称为e阶分圆类,显然有 F q * = l = 0 e 1 C l ( e , q ) | C l ( e , q ) | = f

引理1 [11] :设 q = 4 f + 1 ,f是奇数。 q = s 2 + 4 t 2 是其二次划分,且 s = 1 ( mod 4 ) ,t的符号由选取的本原元决定。则当 C 0 ( 4 , q ) C 1 ( 4 , q ) ( q , q 1 2 , q 5 4 , q 1 2 ) 几乎差集当且仅当 t = ± 1 。此时有

Γ D ( x ) = { q 3 2 t 4 , x C 0 ( 4 , q ) C 2 ( 4 , q ) , q 3 + 2 t 4 , x C 1 ( 4 , q ) C 3 ( 4 , q ) .

我们首先估计任意非平凡特征 χ 在集合 C 0 ( 4 , q ) C 1 ( 4 , q ) 的值。实际上该值Ding等人在文 [11] 中已经给出,我们重新整理可以得到:

引理2 [11] :有限域 F q ,则有

| χ ( C 0 ( 4 , q ) C 1 ( 4 , q ) ) | = q ± 1 2 , | χ ( C 2 ( 4 , q ) C 3 ( 4 , q ) ) | = q ± 1 2 .

证明:设 c C m ( 4 , q ) ,则 c C i ( 4 , q ) = { c x , x C i ( 4 , q ) } = C ( m + i ) mod 4 ( 4 , q )

| χ ( c C 0 ( 4 , q ) c C 1 ( 4 , q ) ) | 2 = x C 0 ( 4 , q ) C 1 ( 4 , q ) χ ( c x ) y C 0 ( 4 , q ) C 1 ( 4 , q ) χ ( c y ) = x , y C 0 ( 4 , q ) C 1 ( 4 , q ) χ ( c x c y ) = q 1 2 + x , y C 0 ( 4 , q ) C 1 ( 4 , q ) y x χ ( c x c y ) .

根据引理1有

| χ ( c C 0 ( 4 , q ) c C 1 ( 4 , q ) ) | 2 = q 1 2 + q 3 2 t 4 χ ( c C 0 ( 4 , q ) c C 2 ( 4 , q ) ) + q 3 + 2 t 4 χ ( c C 1 ( 4 , q ) c C 3 ( 4 , q ) ) = q 1 2 + q 3 2 t 4 χ ( C m mod 2 ( 2 , q ) ) + q 3 + 2 t 4 χ ( C ( m + 1 ) mod 2 ( 2 , q ) ) = q 1 2 + q 3 2 t 4 χ ( C m mod 2 ( 2 , q ) ) + q 3 + 2 t 4 ( 1 χ ( C m mod 2 ( 2 , q ) ) ) = q + 1 2 t 4 t χ ( C m mod 2 ( 2 , q ) ) .

Ding等 [11] 证明了 χ ( C 0 ( 2 , q ) ) = 1 q 2 χ ( C 1 ( 2 , q ) ) = 1 ± q 2 。于是

| χ ( c C 0 ( 4 , q ) c C 1 ( 4 , q ) ) | 2 = q + 1 2 t 4 t 1 q 2 = q ± 2 q + 1 4 .

所以 | χ ( C 0 ( 4 , q ) C 1 ( 4 , q ) ) | = q ± 1 2 | χ ( C 2 ( 4 , q ) C 3 ( 4 , q ) ) | = q ± 1 2

3. 构造码本

F q i 是有限域, i = 1 , 2 , , n 且都满足引理1的条件。 D i = C 0 ( 4 , q i ) C 1 ( 4 , q i ) F q i 中参数为 ( q i , q i 1 2 , q i 5 4 , q i 1 2 ) 的几乎差集, 1 i n D ¯ i = C 2 ( 4 , q i ) C 3 ( 4 , q i ) { 0 } 。对 i = 1 , 2 , , n ,令 χ i , j i F ^ q i , j i = 0 , 1 , , q i 1 ,且 χ i , 0 是相应的平凡特征。设 F = F q 1 × F q 2 × × F q n 。对 ( g i 1 , g i 2 , , g i n ) F ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( g i 1 , g i 2 , , g i n ) : = χ 1 , j 1 ( g i 1 ) χ 1 , j 2 ( g i 21 ) χ 1 , j n ( g i n ) 。这时 χ 1 , j 1 χ 2 , j 2 χ n , j n 是F上的特征。这种特征的集合记为 F ^ 。显然有 | F ^ | = q 1 q 2 q n

现在我们构造F一个的子集D。设 E 1 = D 1 ,对于任意的 1 i n ,设

E i + 1 : = ( E i × D ¯ i + 1 ) ( E ¯ i × D i + 1 ) .

最后,设 D = E n , K = | D | 。用数学归纳法容易得到 | E i | = q 1 q 2 q i 1 2 , 1 i n K = | D | = q 1 q 2 q n 1 2

定义3. 上面的集合D,我们定义码本:

C D = { C j 1 , j 2 , , j n , j i = 0 , 1 , , q i 1 , i = 1 , 2 , , K } . (1)

对于每个 ( j 1 , j 2 , , j n )

C j 1 , j 2 , , j n = 1 K ( ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( g i 1 , g i 2 , , g i n ) ) i = 1 K = 1 K ( χ 1 , j 1 ( g i 1 ) χ 1 , j 2 ( g i 21 ) χ 1 , j n ( g i n ) ) i = 1 K . (2)

下面我们证明码本 是几乎最佳码本,证明的关键是计算最大相关值 I max ( C D ) 。因为码本 C D 中的码字 C j 1 , j 2 , , j n 是定义在D上的,所以需要估计特征在D中元素值的累加和。

引理4. 对于F中的特征 χ 1 , j 1 χ 2 , j 2 χ n , j n j i = 0 , 1 , , q i 1 i = 1 , 2 , , n

| ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( D ) | { K , ( j 1 , j 2 , , j n ) = ( 0 , 0 , , 0 ) , | 1 + q 1 | | 1 + q n | 2 , ( j 1 , j 2 , , j n ) ( 0 , 0 , , 0 ) .

证明:我们用数学归纳法证明该引理。

n = 1 时,若 χ 1 , j 1 是平凡特征,显然有 χ 1 , j 1 ( D ) = K ;若 χ 1 , j 1 不是平凡特征,则根据引理2知 | χ 1 , j 1 ( D ) | q + 1 2 ,那么以上的结果成立。

现假设 n 1 时结果是正确的,下面分析n的情况。

如果 ( j 1 , j 2 , , j n ) = ( 0 , 0 , , 0 ) ,那么 χ 1 , j 1 χ 2 , j 2 χ n , j n 是平凡特征。因此,以上结果是正确的。如果 ( j 1 , j 2 , , j n ) ( 0 , 0 , , 0 ) ,则又分为以下三种情形:

1) ( j 1 , j 2 , , j n ) = ( 0 , 0 , , 0 ) j n 0

( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( D ) = ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( ( E n 1 × D ¯ n ) ( E ¯ n 1 × D n ) ) = | E n 1 | χ n , j n ( D ¯ n ) + | E ¯ n 1 | χ n , j n ( D n ) = | E n 1 | χ n , j n ( D n ) + | E ¯ n 1 | χ n , j n ( D n ) = χ n , j n ( D n ) .

所以

| ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( D ) | = | χ n , j n ( D n ) | = | 1 + q n | 2 < | 1 + q 1 | | 1 + q n | 2 .

2) ( j 1 , j 2 , , j n 1 ) ( 0 , 0 , , 0 ) j n = 0

在这种情况中我们可以得到:

( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( D ) = ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( ( E n 1 × D ¯ n ) ( E ¯ n 1 × D n ) ) = ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E n 1 ) | D ¯ n | + ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E ¯ n 1 ) | D n | = ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E n 1 ) | D ¯ n | ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E n 1 ) | D n | = ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E n 1 ) .

再根据假设有

| ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( D ) | = | ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E n 1 ) | | 1 + q 1 | | 1 + q n 1 | 2 < | 1 + q 1 | | 1 + q n | 2 .

3) ( j 1 , j 2 , , j n ) ( 0 , 0 , , 0 )

在这种情况中我们可以得到:

( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( D ) = ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( ( E n 1 × D ¯ n ) ( E ¯ n 1 × D n ) ) = ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E n 1 ) χ n , j n ( D ¯ n ) + ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E ¯ n 1 ) χ n , j n ( D n ) = 2 ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E n 1 ) χ n , j n ( D n ) .

所以根据假设及引理2有

| ( χ 1 , j 1 χ 2 , j 2 χ n , j n ) ( D ) | = | 2 ( χ 1 , j 1 χ 2 , j 2 χ n 1 , j n 1 ) ( E n 1 ) χ n , j n ( D n ) | 2 | 1 + q 1 | | 1 + q n 1 | 2 | 1 + q n | 2 < | 1 + q 1 | | 1 + q n | 2 .

定理5. C D 是由(1)式定义的码本。则 C D 的参数为 ( q 1 q 2 q n , q 1 q 2 q n 1 2 ) 且有

I max ( C D ) | 1 + q 1 | | 1 + q n | q 1 q 2 q n 1 .

证明:设 C j 1 , j 2 , , j n C j 1 , j 2 , , j n C D 中的两个码本且 ( j 1 , j 2 , , j n ) ( j 1 , j 2 , , j n ) 。由(2)式我们可以得到

| C j 1 , j 2 , , j n C j 1 , j 2 , , j n H | = 1 K | i = 1 K χ 1 , j 1 ( g i 1 ) χ 2 , j 2 ( g i 12 ) χ n , j n ( g i n ) χ ¯ 1 , j 1 ( g i 1 ) χ ¯ 2 , j 2 ( g i 12 ) χ ¯ n , j n ( g i n ) | = 1 K | i = 1 K ( χ 1 , j 1 χ ¯ 1 , j 1 ) ( g i 1 ) ( χ 2 , j 2 χ ¯ 2 , j 2 ) ( g i 12 ) ( χ n , j n χ ¯ n , j n ) ( g i n ) | = 1 K | i = 1 K ( ( χ 1 , j 1 χ ¯ 1 , j 1 ) ( χ 2 , j 2 χ ¯ 2 , j 2 ) ( χ n , j n χ ¯ n , j n ) ) ( g i 1 , g i 2 , , g i n ) | .

由于 ( j 1 , j 2 , , j n ) ( j 1 , j 2 , , j n ) ( χ 1 , j 1 χ ¯ 1 , j 1 ) ( χ 2 , j 2 χ ¯ 2 , j 2 ) ( χ n , j n χ ¯ n , j n ) 是F的非平凡特征。利用引理4即可得证:

注6. 对于一个参数为 ( q 1 q 2 q n , q 1 q 2 q n 1 2 ) 的码本。易算得

I w = q 1 q 2 q n + 1 q 1 q 2 q n 1 .

因此

1 I max ( C D ) I w = | 1 + q 1 | | 1 + q n | q 1 q 2 q n + 1 1 .

当所有 q i , 1 i n

推论7. 当定理5中所用的有限域都相同时,不妨设都是 F q 。此时对应的 ( q n , q n 1 2 ) 密码本满足:

I max ( C D ) | 1 + q | n q n 1 .

对应的Welch界是 I w = q n + 1 q n 1 。因此,

1 I max ( C D ) I w = | 1 + q | n q n + 1 1 .

基金项目

国家自然科学基金(No. 61502217)。

文章引用

马 瑞,亓万锋,唐玲丽. 基于4阶分圆类的近似最佳码本的构造
Constructions of Nearly Optimal Codebooks Based on Cyclotomic Classes of Order Four[J]. 应用数学进展, 2019, 08(01): 145-151. https://doi.org/10.12677/AAM.2019.81016

参考文献

  1. 1. Welch, L. (1974) Lower Bounds on the Maximum Cross Correlation of Signals. IEEE Transactions on Information Theory, 20, 397-399. https://doi.org/10.1109/TIT.1974.1055219

  2. 2. Fickus, M. and Mixon, D.G. (2016) Tables of the Existence of Equiangular Tight Frames. arXiv:1504.00253v2.

  3. 3. Li, C., Yue, Q. and Huang, Y. (2015) Two Families of Nearly Optimal Codebooks. Designs, Codes and Cryptography, 75, 43-57. https://doi.org/10.1007/s10623-013-9891-7

  4. 4. Zhang, A.X. and Feng, K.Q. (2012) Construction of Cyclotomic Codebooks Nearly Meeting the Welch Bound. Designs, Codes and Cryptography, 63, 209-224. https://doi.org/10.1007/s10623-011-9549-2

  5. 5. Heng, Z., Ding, C. and Yue, Q. (2017) New Constructions of Asymptotically Optimal Codebooks with Multiplicative Characters. IEEE Transactions on Information Theory, 63, 6179-6187. https://doi.org/10.1109/TIT.2017.2693204

  6. 6. Heng, Z. (2018) Nearly Optimal Codebooks Based on Generalized Jacobi Sums. Discrete Applied Mathematics, 250, 227-240. https://doi.org/10.1016/j.dam.2018.05.017

  7. 7. Heng, Z. and Yue, Q. (2017) Codebooks Achieving the Le-venshtein Bound from Generalized Bent Functions over Z4. Cryptography and Communications, 9, 41-53. https://doi.org/10.1007/s12095-016-0194-5

  8. 8. 张爱仙, 冯克勤. 一类近似最佳码本的构造[J]. 中国科学: 信息科学, 2015(12): 1632-1639.

  9. 9. Hu, H. and Wu, J. (2014) New Constructions of Codebooks Nearly Meeting the Welch Bound with Equality. IEEE Transactions on Information Theory, 60, 1348-1355. https://doi.org/10.1109/TIT.2013.2292745

  10. 10. Lidl, R. and Niederreiter, H. (1984) Finite Fields. Cambridge University Press, Cambridge.

  11. 11. Ding, C.S. (2006) Complex Codebooks from Combinatorial Designs. IEEE Trans-actions on Information Theory, 52, 4229-4235. https://doi.org/10.1109/TIT.2006.880058

期刊菜单