基于奇异辛空间上码本的构造
The Construction of Codebook Based on Singular Symplectic Space
DOI: 10.12677/PM.2023.132018, PDF, HTML, XML,    科研立项经费支持
作者: 林远鹏, 陈延林, 崔玉涛, 刘雪梅:中国民航大学理学院,天津;王钰洁, 张海纳:中国民航大学电子信息与自动化学院,天津
关键词: 奇异辛空间码本Welch界Singular Symplectic Space Codebook Welch Bound
摘要: 码本可以应用于区分不同用户发出的信号的码分多址系统中,基于奇异辛空间构造了一类新的码本,运用奇异辛空间的计数定理,得到了码本的相关参数,计算了该新码本的最大互相关振幅,计算出了最大互相关振幅渐近到达Welch的限制条件,从而证明了根据奇异辛空间构造出的码本是渐近最优码本。
Abstract: The codebook can be used to distinguish the signals sent by different users in the code division multiple access system. Based on the singular symplectic space, a new codebook is constructed. Using the counting theorem of the singular symplectic space, the relevant parameters of the codebook are obtained, the maximum cross-correlation amplitude of the new codebook is calcu-lated, and the limiting conditions for the maximum cross-correlation amplitude to reach mathbit Welch asymptotically are calculated. It is proved that the codebook constructed from singular symplectic space is asymptotically optimal.
文章引用:林远鹏, 陈延林, 崔玉涛, 王钰洁, 张海纳, 刘雪梅. 基于奇异辛空间上码本的构造[J]. 理论数学, 2023, 13(2): 158-165. https://doi.org/10.12677/PM.2023.132018

1. 引言

码本是传输不同种类信息的载体,有着低重复率和强保密性的优点。一个参数为 ( N , K ) 的码本C是由N个单位向量 { C 1 , C 2 , C 3 , , C n } 构成的集合, C j 长度为K,其中 1 j N 。最大互相关幅度是刻画码本优劣的一个重要参数,一般用 I max ( C ) 来表示。在信息的传递过程中,由于受到自身因素和外力因素的影响,码本会出现错误。避免出现错误就需要码本中的两两码字之间的相关性较小。在码本的实际应用过程中,对于一定长度的K,我们总希望码本向量个数N尽可能的大,从而使得最大互相关幅度尽可能的小,减少在信息传递过程中的信号之间的干扰。但码本参数的选择要符合一定的规则,其最大互相关幅度和参数N,K之间要满足一个特定的界,即Welch [1] 界。当 N > K 时,如果码本C的最大互相关幅度与Welch界大小相等,那么就称该码本为MWBE (maximal Welch bound equality codebook)码本 [2] 或者最优码本。最优码本对于参数的限制较多,构造较为困难,其最优构造可以分为几方面:

第一方面:对 N > 1 ,使用m-序列构造参数为 ( N , N 1 ) 的MWBE码本 [2] ;

第二方面:对 N > 1 ,基于离散傅里叶变换构造 ( N , N 1 ) 的MWBE码本 [2] ,基于 Z N 中的 ( N , K , λ ) 差集构造参数为 ( N , K ) 的MWBE码本 [3] ;

第三方面:设d是正整数,当 N = 2 K = 2 d + 1 N = 2 K = p d + 1 ,且p是素数时,用协商矩阵构造参数为 ( N , K ) 的MWBE码本 [4] [5] ;

第四方面:利用有限域 F q 中的 ( N , K , λ ) 循环差集 [2] 和阿贝尔差集 [6] 构造参数为 ( N , K ) 的MWBE码本,用 ( 2 , k , υ ) -Steiner系构造 ( N , K ) MWBE码本 [7] ;

第五方面:用图论和有限几何构造 ( N , K ) MWBE码本 [8] [9] [10] 。

但是由于对于最优码本的构造需要对于参数的限制条件较多,而且束缚条件严格,所以难以构造最优码本,构造最优码本的途径较少。所以学者们找出了一个近似构造最优码本的方法。当码本的最大互相关幅度无限的趋近于Welch界时,称其为渐近最优码本。其构造放宽了对于码本的束缚条件,使其对于参数的选取范围更大,参数的选择更为灵活。当码字的长度达到足够长度时,渐近最优码本可以近似的代替最优码本来使用。所以构造渐近最优码本有着较大的意义。2008年,Ding使用几乎差集构造了出来一类渐近最优码本 [11] ;2012年,冯克勤等人运用类似于Ding的方法构造了束缚条件更为宽松的渐近最优码本 [12] ;2018年,何春燕等人利用高斯和构造了一类渐近最优码本 [13] 解决了Ding在文献 [11] 中遗留下的问题;2021年,刘雪梅等人利用仿射空间的相关性质构造了一类渐近最优码本 [14] 。

本文采取了构造渐近最优码本的方法,并创新性的使用了基于奇异辛空间的方式来构造码本,基于这个空间来进行码本构造的动机在于该空间的相关性质和计数定理能够满足一类新码本构造的条件,并通过对于该空间的相关参数进行范围限制可以得出渐近最优码本。该构造码本具有创新性和实用价值。

论文的其余部分组织如下。在第2节中我们给出了构造一类渐近最优码本应满足的条件和判断码本优劣的定义,以及奇异辛空间的相关定义定理。在第3节我们利用奇异辛空间的相关定义和计数定理来进行了码本的构造,并找出限制码本为渐近最优码本的相关条件。第4节就是对于结论的综合展示。

2. 预备知识

2.1. 码本的相关概念及界

定义2.1.1一个参数为 ( N , K ) 的码本C是由N个 1 × K 复单位向量 { c 1 , c 2 , , c N } 构成的集合, 1 i N ,其中向量 c i 称为码本的码字。

定义2.1.2码本C的最大相关幅度定义为

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

其中 c j H 表示复数向量 c j 的共轭转置。

引理2.1.3 (Welch界 [1] )对任意参数为 ( N , K ) 的码本C,且 N K ,有

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

等号成立当且仅当对任意的 ( i , j ) i j ,都有 | c i c j H | = N K ( N 1 ) K

为方便起见,记 I W = N K ( N 1 ) K

2.2. 奇异辛空间的相关概念及相关定理

定义2.2.1,定义2.2.2,定理2.2.3,引理2.2.4,引理2.2.5,引理2.2.6,定义2.2.7均来自参考文献 [15] 。

定义2.2.1假设 F q 是含有q个元素的有限域,其中q是一个素数的幂。令 F q ( 2 v + l ) F q 上的 ( 2 v + l ) 维行向量空间。假设 K = ( 0 I ( v ) I ( v ) 0 ) K l = ( K 0 ( l ) ) F q 上满足 T K l T t = K l ( 2 v + l ) × ( 2 v + l ) 非奇异矩阵T组成的集合构成了一个群,称该群为 F q 上的指标为v的 ( 2 v + l ) 阶奇异辛群,记为 S p 2 v + l , v ( F q ) 。容易验证 S p 2 v + l , v ( F q ) 是由所有的 ( 2 v + l ) × ( 2 v + l ) 形如 T = ( T 11 T 12 0 T 22 ) 的非奇异矩阵组成的。其中 T 11 K l T 11 t = K l T 22 是非奇异的。

定义2.2.2假设 F q ( 2 v + l ) F q 上的 ( 2 v + l ) 维行向量空间。定义 S p 2 v + l , v ( F q ) F q ( 2 v + l ) 上的作用为:

F q ( 2 v + l ) × S p 2 v + l , v ( F q ) F q ( 2 v + l ) ,

( ( x 1 , x 2 , , x 2 v + l ) , T ) ( x 1 , x 2 , , x 2 v + l ) T ,

称向量空间 F q ( 2 v + l ) 连同群 F q ( 2 v + l ) 的作用为 F q 上的奇异辛空间。

定理 2.2.3假设 e i ( 1 i 2 v + l ) F q ( 2 v + l ) 中的行向量, e i 的第i个分量是1,其余的分量全是0。记E是由 e 2 v + 1 , e 2 v + 2 , , e 2 v + l 生成的 F q ( 2 v + l ) 中的l维子空间。 F q ( 2 v + l ) 中的一个m维子空间P为 ( m , s , k ) 型子空间是指:

1) P K l P t M ( m , s ) 是合同的。

2) d i m ( P E ) = k ,其中

M ( m , s ) = ( 0 I ( s ) I ( s ) 0 0 ( m 2 s ) ) ,

F q ( 2 v + l ) 中所有 ( m , s , k ) 型子空间为 M ( m , s , k ; 2 v + l , v ) 容易验证 M ( m , s , k ; 2 v + l , v ) 是集合的充分必要条件是: 0 k l 2 s m k v + s 。记

N ( m , s , k ; 2 v + l , v ) = | M ( m , s , k ; 2 v + l , v ) | .

引理2.2.4 M ( m , s , k ; 2 v + l , v ) 非空当且仅当

0 k l , 2 s m k v + s ,

同时等价于

max { 0 , m v s } min { l , m 2 s } ,

如果 M ( m , s , k ; 2 v + l , v ) 非空,则其在 S p 2 v + l , v ( F q ) 作用下形成一条轨迹道,并且有

N ( m , s , k ; 2 v + l , v ) = q 2 s ( v + s m + k ) + ( m k ) ( l k ) i = v + s m + k + 1 v ( q 2 i 1 ) i = l k + 1 l ( q i 1 ) i = 1 s ( q 2 i 1 ) i = 1 m k 2 s ( q i 1 ) i = 1 k ( q i 1 ) ,

( 2 v + l ) 维奇异辛空间 F q ( 2 v + l ) 中所有的 ( m , s ) 子空间构成的集合为 M ( m , s ; 2 v + l ) ,且记

N ( m , s ; 2 v + l , v ) = | M ( m , s ; 2 v + l , v ) | .

引理2.2.5令 max { 0 , m v s } min { l , m 2 s } ,则有

N ( m , s ; 2 v + l , v ) = k = max { 0 , m v s } min { l , m 2 } N ( m , s , k ; 2 v + l , v ) ,

取定 ( 2 v + l ) 维奇异辛空间 F q ( 2 v + l ) 中的一个 ( m , s , k ) 型子空间P。记包含在P中的所以 ( m 1 , s 1 , k 1 ) 型子空间的构成的集合为 M ( m 1 , s 1 , k 1 ; m , s , k ; 2 v + l , v ) 。记

N ( m 1 , s 1 , k 1 ; m , s , k ; 2 v + l , v ) = | M ( m 1 , s 1 , k 1 ; m , s , k ; 2 v + l , v ) | .

引理2.2.6 M ( m 1 , s 1 , k 1 ; m , s , k ; 2 v + l , v ) 非空当且仅当

{ k 1 k l 2 s m k v + s 2 s 1 m 1 k 1 v + s 1 0 s s 1 ( m k ) ( m 1 k 1 ) ,

同时等价于

{ k 1 k l 2 s m k v + s max { 0 , m 1 k 1 s s 1 } min { m k 2 s , m 1 k 1 2 s 1 } ,

如果 M ( m 1 , s 1 , k 1 ; m , s , k ; 2 v + l , v ) 非空,则有

N ( m 1 , s 1 , k 1 ; m , s , k ; 2 v + l , v ) = q ( m 1 k 1 ) ( k k 1 ) N ( k 1 , k ) N ( m 1 k 1 , s 1 ; 2 s + ( m k 2 s ) , s ) .

定义2.2.7 设 a = ( a 1 , a 2 , , a n ) F q ( n ) 中的向量,则向量a的Hamming权定义为非零分量 a i 的个数,表示为 ω ( a ) ,即 ω ( a ) = # { i : 1 i n , a i 0 }

3. 码本构造

在构造新的码本之前,先利用奇异辛空间的子空间的包含关系构造一类二元等重码。

定义3.1给定整数

{ k 1 k l 0 m k v 0 m 1 k 1 v 0 ( m k ) ( m 1 k 1 )

令Φ是一个二元矩阵,其中它的行是由所有的 ( m 1 , 0 , k 1 ) 型子空间标定,列是由所有 ( m , 0 , k ) 型标定,Φ的第i行第j列为1,当且仅当第i行的 ( m 1 , 0 , k 1 ) 型子空间包含在第j列的 ( m , 0 , k ) 型子空间中。

由引理2.2.4,引理2.2.5和引理2.2.6知Φ是一个 K × N 的矩阵,并且它的列重都是ω,其中

K = N ( m 1 , 0 , k 1 ; 2 v + l , v ) = q ( m 1 k 1 ) ( l k 1 ) i = v m 1 + k 1 + 1 v ( q 2 i 1 ) i = l k 1 + 1 l ( q i 1 ) i = 1 m 1 k 1 ( q i 1 ) i = 1 k 1 ( q i 1 )

N = N ( m , 0 , k ; 2 v + l , v ) = q ( m k ) ( l k ) i = v m + k + 1 v ( q 2 i 1 ) i = l k + 1 l ( q i 1 ) i = 1 m k ( q i 1 ) i = 1 k ( q i 1 )

ω = N ( m 1 , 0 , k 1 ; m , 0 , k ; 2 v + l , v ) = q ( m 1 k 1 ) ( k k 1 ) N ( k 1 , k ) N ( m 1 k 1 , 0 ; 0 + ( m k ) , 0 )

由此,以每一列为一个码字,就得到了一个二元等重码C,参数 ( K , N ) 。对任意一个二元码 ,我们可以定义码本

S ω ( C ) = { c ω : c C } (1)

定理3.2对于任一 ( K × N ) 二元码C,在等式(1)中定义的集合 S ω ( C ) 是一个 ( N , K ) 码本,且最大互相关幅度为

I max ( S ω ( C ) ) = Q ω

其中 Q = max { N ( m 1 , 0 , k 1 ; m 1 , 0 , k ; 2 v + l , v ) , N ( m 1 , 0 , k 1 ; m 1 , 0 , k 1 ; 2 v + l , v ) }

证明

由非空条件 0 ( m k ) ( m 1 k 1 ) ,设 k 1 为x,有

( m k ) ( ( m 1 ) x ) 0

x k 1

k 1 k 所以x的取值为 k , k 1

构造码本的大小和码字的长度可以由二元码C的定义及参数得出。

对任意两个不同的向量 s i , s j S ω ( C ) , 1 i , j N ,有

| s i s j H | = ω ( s i s j ) ω

N ( m 1 , 0 , k 1 ; m 1 , 0 , k ; 2 v + l , v ) N ( m 1 , 0 , k 1 ; m 1 , 0 , k 1 ; 2 v + l , v ) 时, ω ( s i s j ) 取得最大值当且仅当存在 ( m 1 , 0 , k ) 型子空间既包含于第i个 ( m , 0 , k ) 型子空间,又包含于第j个 ( m , 0 , k ) 型子空间,则 ω ( s i s j ) = N ( m 1 , 0 , k 1 ; m 1 , 0 , k ; 2 v + l , v )

N ( m 1 , 0 , k 1 ; m 1 , 0 , k ; 2 v + l , v ) < N ( m 1 , 0 , k 1 ; m 1 , 0 , k 1 ; 2 v + l , v ) 时, ω ( s i s j ) 取得最大值当且仅当存在 ( m 1 , 0 , k 1 ) 型子空间既包含于第i个 ( m , 0 , k ) 型子空间,又包含于第j个 ( m , 0 , k ) 型子空间,则 ω ( s i s j ) = N ( m 1 , 0 , k 1 ; m 1 , 0 , k 1 ; 2 v + l , v )

综上可得 max ω ( s i s j ) = Q ,即 I max ( S ω ( C ) ) = Q ω

引理 3.3当 ( m 1 k 1 ) ( 4 v 3 m 1 + 3 k 1 3 ) = ( k 1 l ) 2 m 1 时,

lim v I max 1 K = 1

证明由引理2.2.4,引理2.2.5,引理2.2.6知

K = q ( m 1 k 1 ) ( l k 1 ) i = v m 1 + k 1 + 1 v ( q 2 i 1 ) i = l k 1 + 1 l ( q i 1 ) i = 1 m 1 k 1 ( q i 1 ) i = 1 k 1 ( q i 1 ) q ( m 1 k 1 ) ( l k 1 ) i = v m 1 + k 1 + 1 v q 2 i i = l k 1 + 1 l q i i = 1 m 1 k 1 q i i = 1 k 1 q i = q 2 ( m 1 k 1 ) ( v m 1 + k 1 ) + ( m 1 k 1 ) ( 1 + m 1 k 1 ) 2 + ( l k 1 ) m 1

Q ω max { q m 1 ( k 1 k 1 ) + ( m k ) ( m 1 k 1 ) ( m 1 k 1 ) 2 q m 1 ( k k 1 ) + ( m k ) ( m 1 k 1 ) ( m 1 k 1 ) 2 , q m 1 ( k k 1 ) + ( m k 1 ) ( m 1 k 1 ) ( m 1 k 1 ) 2 q m 1 ( k k 1 ) + ( m k ) ( m 1 k 1 ) ( m 1 k 1 ) 2 } = max { 1 q m 1 , 1 q m 1 k 1 }

根据非空条件 0 m 1 , m 1 k 1 , 0 k 1 k ,所以

Q ω 1 q m 1 k 1

( m 1 k 1 ) ( 4 v 3 m 1 + 3 k 1 3 ) = ( k 1 l ) 2 m 1 时,

lim v I max 1 K = q ( m 1 k 1 ) ( v m 1 + k 1 1 ) + ( m 1 k 1 ) ( 1 + m 1 k 1 ) 4 + ( l k 1 ) m 1 2 = 1

引理3.4当

{ ( m 1 k 1 ) ( v m 1 + k 1 ) < ( m k ) ( v m + k ) ( m 1 k 1 ) ( 1 + m 1 k 1 ) < ( m k ) ( 1 + m k ) ( l k 1 ) m 1 < ( l k ) m

时,有 lim v I W 1 K = 1

证明由引理2.2.4知

K = q ( m 1 k 1 ) ( l k 1 ) i = v m 1 + k 1 + 1 v ( q 2 i 1 ) i = l k 1 + 1 l ( q i 1 ) i = 1 m 1 k 1 ( q i 1 ) i = 1 k 1 ( q i 1 ) q 2 ( m 1 k 1 ) ( v m 1 + k 1 ) + ( m 1 k 1 ) ( 1 + m 1 k 1 ) 2 + ( l k 1 ) m 1

N = N ( m , 0 , k ; 2 v + l , v ) = q ( m k ) ( l k ) i = v m + k + 1 v ( q 2 i 1 ) i = l k + 1 l ( q i 1 ) i = 1 m k ( q i 1 ) i = 1 k ( q i 1 ) q 2 ( m k ) ( v m + k ) + ( m k ) ( 1 + m k ) 2 + ( l k ) m

因为

{ ( m 1 k 1 ) ( v m 1 + k 1 ) < ( m k ) ( v m + k ) ( m 1 k 1 ) ( 1 + m 1 k 1 ) < ( m k ) ( 1 + m k ) ( l k 1 ) m 1 < ( l k ) m

lim v K N = q 2 ( m 1 k 1 ) ( v m 1 + k 1 ) + ( m 1 k 1 ) ( 1 + m 1 k 1 ) 2 + ( l k 1 ) m 1 q 2 ( m k ) ( v m + k ) + ( m k ) ( 1 + m k ) 2 + ( l k ) m = 0

那么可以得到 lim v I W 1 K = lim v N K N 1 = lim v 1 K N 1 1 N = 1

定理3.5当参数 m , m 1 , k , k 1 , v , l ,满足 ( m 1 k 1 ) ( 4 v 3 m 1 + 3 k 1 3 ) = ( k 1 l ) 2 m 1 ( m 1 k 1 ) ( v m 1 + k 1 ) < ( m k ) ( v m + k ) ( m 1 k 1 ) ( 1 + m 1 k 1 ) < ( m k ) ( 1 + m k ) ( l k 1 ) m 1 < ( l k ) m 时,码本 S ω ( C ) 是渐近最优码本。

证明由引理3.3和引理3.4可得 lim v I W I max = 1

4. 结论

本文提供了一个通过奇异辛空间构造码本的方法。首先利用了奇异辛空间的子空间之间的包含关系构造二元等重码,然后用等重码构造了最大互相关振幅为 Q ω 的码本。当 ( m 1 k 1 ) ( 4 v 3 m 1 + 3 k 1 3 ) = ( k 1 l ) 2 m 1 时,码本的最大互相关振幅随v增大趋于 1 K ,当 ( m 1 k 1 ) ( v m 1 + k 1 ) < ( m k ) ( v m + k ) ( m 1 k 1 ) ( 1 + m 1 k 1 ) < ( m k ) ( 1 + m k ) ( l k 1 ) m 1 < ( l k ) m 时,Welch界随v增大也趋于 1 K ,由此得到码本 S ω ( C ) 的最大互相关振幅渐近达到Welch界的条件。

基金项目

中国民航大学大学生创新训练计划项目,项目编号:202210059097,项目类型:创新训练项目。

参考文献

[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] Sarwate, D.V. (1999) Meeting the Welch Bound with Equality. In: Ding, C., Helleseth, T. and Niederreiter, H., Eds., Sequences and Their Applications. Discrete Mathematics and Theoretical Computer Science, Springer, London, 79-102.
https://doi.org/10.1007/978-1-4471-0551-0_6
[3] Candès, E.J. and Wakin, M.B. (2008) An Introduction To Compressive Sampling. IEEE Signal Processing Magazine, 25, 21-30.
https://doi.org/10.1109/MSP.2007.914731
[4] Xia, P., Zhou, S. and Giannakis, G.B. (2005) Achieving the Welch Bound with Difference Sets. IEEE Transactions on Information Theory, 51, 1900-1907.
https://doi.org/10.1109/TIT.2005.846411
[5] Conway, J.H., Harding, R.H. and Sloane, N.J.A. (1996) Packing Lines, Planes, Etc.: Packings in Grassmannian Spaces. Experimental Mathematics, 5, 139-159.
https://doi.org/10.1080/10586458.1996.10504585
[6] Ding, C. (2006) Complex Codebooks from Combinatorial Designs. IEEE Transactions on Information Theory, 52, 4229-4235.
https://doi.org/10.1109/TIT.2006.880058
[7] Fickus, M., Mixon, D.G. and Tremain, J.C. (2012) Steiner Equi-angular Tight Frames. Linear Algebra and Its Applications, 436, 1014-1027.
https://doi.org/10.1016/j.laa.2011.06.027
[8] Fickus, M. and Mixon, D.G. (2015) Tables of the Existence of Equiangular Tight Frames. ArXiv: 1504.00253.
[9] Fickus, M., Mixon, D.G. and Jasper, J. (2016) Equiangular Tight Frames from Hyperovals. IEEE Transactions on Information Theory, 62, 5225-5236.
https://doi.org/10.1109/TIT.2016.2587865
[10] Massey, J.L. and Mittelholzer, T. (1993) Welch’s Bound and Se-quence Sets for Code-Division Multiple-Access Systems. In: Capocelli, R., De Santis, A. and Vaccaro, U., Eds., Se-quences II, Springer, New York, 63-78.
https://doi.org/10.1007/978-1-4613-9323-8_7
[11] Ding, C. and Feng, T. (2008) Codebooks from Almost Differencesets. Designs, Codes and Cryptography, 46, 113-126.
https://doi.org/10.1007/s10623-007-9140-z
[12] 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
[13] 张爱仙, 何春燕, 吉喆. 几类近似达到Welch界码本的构造[J]. 纯粹数学与应用数学, 2018, 34(3): 323-330.
[14] 刘雪梅, 贾丽华. 基于有限域上仿射空间构造新码本[J]. 中国民航大学学报, 2021, 39(3): 62-64.
[15] Wan, Z.X. (2002) Geometry of Classical Groups over Finite Field. 2nd Edition, Science Press, Beijing.