(n × m, 4,1,2)光正交码的上界

Bounds of (n × m, 4,1,2)-Optical Orthogonal Oodes

摘要: 一个光正交码是指具有良好的自相关性和互相关性的序列族。它是为光码分多址(CDMA)系统而设计的一种专用码。本文通过计算每个权重为4的码字所含3-子集轨道代表元的个数，给出汉明权重为4，自相关值为1，互相关值为2的二维光正交码的码字容量的上界。

Abstract: An optical orthogonal code is a family of sequences with good auto-correlation and cross-correlation. It is a special code designed for optical code-division multiple access (CDMA) system. In this paper, the upper bound of the capacity of two-dimensional optical orthogonal codes with hamming weight 4, auto-correlation value of 1 and cross-correlation value of 2 is given by calculating the number of 3-subset orbit representations of each code with weight 4.

1. 引言

设 $n,m,k,{\lambda }_a,{\lambda }_c$ 是正整数，参数为 $\left(n\times m,k,{\lambda }_a,{\lambda }_c\right)$ 的二维光正交码 $\mathcal{C}$ (记作 $2-D\left(n\times m,k,{\lambda }_a,{\lambda }_c\right)-OOC$ )是 $n\times m$ 阶的 $\left(0,1\right)$ 矩阵C (码字)的集合，其中 $k,{\lambda }_a,{\lambda }_c$ 分别表示光正交码的权重，自相关值和互相关值，并且满足下列两个条件：

1) 自相关性：对任意 $C={\left(c_{ij}\right)}_{n\times m}\in \mathcal{C}$ 和任意正整数 $l\in \left\{1,2,\cdots ,m-1\right\}$ ，有

${\displaystyle \underset{i=0}{\overset{n-1}{\sum }}{\displaystyle \underset{j=0}{\overset{m-1}{\sum }}{c}_{ij}{c}_{i,j+l}\le {\lambda }_a}}$ ；

2) 互相关性：对任意 $C={\left(c_{ij}\right)}_{n\times m}\in \mathcal{C}$ ， $D={\left(d_{ij}\right)}_{n\times m}\in \mathcal{C}$ ， $C\ne D$ ，以及任意正整数 $l\in \left\{0,1,\cdots ,m-1\right\}$ ，有 ${\displaystyle \underset{i=0}{\overset{n-1}{\sum }}{\displaystyle \underset{j=0}{\overset{m-1}{\sum }}{c}_{ij}{d}_{i,j+l}\le {\lambda }_c}}$。

任意 $C={\left(c_{ij}\right)}_{n\times m}\in \mathcal{C}$ ，行标i取自 $I_n$ ，列标j取自 $Z_m$ ，其中 $I_n=\left\{0,1,\cdots ,n-1\right\}$ ， $Z_m$ 是模m的剩余类

加群，若 $c_{ij}\ne 0$ 则令 $\left(i,j\right)\in B_C$, $B_C$ 表示C中非零元素的坐标集合，所以 $B_C$ 是 $I_n\times Z_m$ 中一个k元组。于是， $2-D\left(n\times m,k,{\lambda }_a,{\lambda }_c\right)-OOC$ 可视为 $I_n\times Z_m$ 中k元组的集合记作 $\mathcal{B}$ ，满足下列两个条件：

1') 自相关性：对任意 $B\in \mathcal{B}$ 和任意正整数 $l\in Z_m\backslash \left\{0\right\}$ ，有

$\left|B\cap \left(B+l\right)\right|\le {\lambda }_a$ ；

2') 互相关性：对任意 $A,B\in \mathcal{B},A\ne B$ 和任意正整数 $l\in Z_m$ ，有

$\left|A\cap \left(B+l\right)\right|\le {\lambda }_c$ ，

其中 $B+l=\left\{\left(i,j+l\right):\left(i,j\right)\in B\right\}$ ，并且所有加法运算在 $Z_m$ 上进行。

对光正交码的研究始于1989年文献 [1]。实际应用中需要大容量相关性好的光正交码，二维光正交码具有良好的稳定性及所需容量。在文献 [2] [3] [4] 中研究了 $k=3,4;{\lambda }_a=1,2;{\lambda }_c=k-1$ 时， $\left(n\times m,k,{\lambda }_a,k-1\right)$ 光正交码的上界，并确定了 $\Phi \left(n\times m,k,k-1\right)$ 的计算公式。文献 [5] 中计算了汉明权重为 $k;{\lambda }_a=k-2;{\lambda }_c=k-1$ 时 $\Phi \left(n\times m,k,k-2,k-1\right)$ 的具体表达式并确定了 $\left(n\times m,5,3,4\right)$ 光正交码的上界。在文献 [6] [7] [8] 中具体分析了 $\left(n\times m,3,2,1\right)$ 光正交码的部分上界及构造问题。当 ${\lambda }_a={\lambda }_c$ 时，在文献 [9] 中利用辅助设计建立递归构造的方式得到 $\left(n\times m,4,2\right)$ 光正交码的上界及部分无穷类结果。本文研究了当 $k=4,{\lambda }_a=1,{\lambda }_c=2$ 时， $\left(n\times m,4,1,2\right)$ 光正交码的最大容量 $\Phi \left(n\times m,4,1,2\right)$ 的问题。本文的研究丰富了多维光正交码的研究内容。

定理1.1 设n和m是正整数，则

$M\left(n\times m,4,1,2\right)=\{\begin{array}{ll}\lfloor \frac{n\left(n^2{m}^2-3nm-3m+5\right)}{24}\rfloor ,\hfill & \left(m,12\right)=1,\hfill \\ \lfloor \frac{n\left(n^2{m}^2-6nm-3m+14\right)}{24}\rfloor ,\hfill & \left(m,12\right)=2,\hfill \\ \lfloor \frac{n\left(n^2{m}^2-3nm-3m+9\right)}{24}\rfloor ,\hfill & \left(m,12\right)=3,\hfill \\ \lfloor \frac{n\left(n^2{m}^2-6nm-3m+20\right)}{24}\rfloor ,\hfill & \left(m,12\right)=4,\hfill \\ \lfloor \frac{n\left(n^2{m}^2-6nm-3m+18\right)}{24}\rfloor ,\hfill & \left(m,12\right)=6,\hfill \\ \lfloor \frac{n\left(n^2{m}^2-6nm-3m+24\right)}{24}\rfloor ,\hfill & \left(m,12\right)=12.\hfill \end{array}$

在本文的第二节提出判别 $2-D\left(n\times m,4,1,2\right)-OOC$ 的等价条件；第三节给出了计算 $\Phi \left(n\times m,4,1,2\right)$ 的过程及结果；第四节对本文进行总结和 $\Phi \left(n\times m,4,1,2\right)$ 的不够紧密的原因进行分析。

2. 基础知识

设B是 $I_n\times Z_m$ 的k-子集，根据B的第一坐标，定义B的 $\left(x,x\right)$ -纯差为B的差多重集

${\Delta }_{xx}\left(B\right)=\left\{b-a:\left(x,a\right),\left(x,b\right)\in B,a\ne b\right\}$ ，其中运算为模m；令 $supp\left(\Delta B\right)$ 表示多重集 ${\displaystyle \underset{x\in I_n}{\cup }{\Delta }_{xx}\left(B\right)}$ 中所有不同元素的集合； $\lambda \left(B\right)$ 表示多重集 ${\displaystyle \underset{x\in I_n}{\cup }{\Delta }_{xx}\left(B\right)}$ 中元素的最大重数。于是，

$\lambda \left(B\right)=\max \left\{\left|B\cap \left(B+l\right)\right|:l\in Z_m\backslash \left\{0\right\}\right\}$。

对于 $I_n\times Z_m$ 的任意k-子集B和 $l\in Z_m$ ，定义 $B+l=\left\{\left(i,j+l\right),\left(i,j\right)\in B\right\}$ 为B的轨道记为 $O\left(B\right)$ ，其中加法运算在 $Z_m$ 上进行。若B在 $Z_m$ 的作用下，轨道 $O\left(B\right)$ 含有m个元素，则称其为长轨道，否则为短轨道。

根据任意 $A,B\in \mathcal{B},A\ne B$ 和任意正整数 $l\in Z_m$ ，有

$\left|A\cap \left(B+l\right)\right|\le {\lambda }_c=2$ ，

所以B包含的3-子集轨道代表元只出现在B中一次；若有一个3-子集轨道代表元同时包含在 $A,B$ 中，则

$\left|A\cap \left(B+l\right)\right|\ge 3$。

令 $\mathcal{B}$ 是 $I_n\times Z_m$ 中4元组的集合，对于 $B\in \mathcal{B}$ ，若 $\mathcal{B}$ 满足以下两个条件：

1) 自相关性： ${\lambda }_a=\max \left\{\lambda \left(B\right):B\in \mathcal{B}\right\}$ ，

2) 互相关性：B包含的3-子集轨道代表元只出现在B中一次，

则 $\mathcal{B}$ 构成一个 $2-D\left(n\times m,4,1,2\right)-OOC$。

3. $2-D\left(n\times m,4,1,2\right)$ 的最大容量

在 $2-D\left(n\times m,4,1,2\right)-OOC$ 中，令 $x,y,z,w\in I_n$ ， $a,b,c\in Z_m$ 对于任意 $B\in \mathcal{B}$ ，B是轨道 $O\left(B\right)$ 的代表元，因此可将B表示为 $\left\{\left(x,0\right),\left(y,a\right),\left(z,b\right),\left(w,c\right)\right\}$ 的形式，因此根据码字的第一坐标可以分为五种类型：

类型1： $x=y=z=w$ ， $B_1=\left\{\left(x,0\right),\left(x,a\right),\left(x,b\right),\left(x,c\right)\right\}$ ，其中 $a\ne b\ne c\in Z_m\backslash \left\{0\right\}$ ；

类型2： $x=y=z\ne w$ ， $B_2=\left\{\left(x,0\right),\left(x,a\right),\left(x,b\right),\left(w,c\right)\right\}$ ，其中 $a\ne b\in Z_m\backslash \left\{0\right\},c\in Z_m$ ；

类型3： $x=y\ne z=w$ ， $B_3=\left\{\left(x,0\right),\left(x,a\right),\left(z,b\right),\left(z,c\right)\right\}$ ，其中 $a\in Z_m\backslash \left\{0\right\},b\ne c\in Z_m$ ；

类型4： $x=y\ne z\ne w$ ， $B_4=\left\{\left(x,0\right),\left(x,a\right),\left(z,b\right),\left(w,c\right)\right\}$ ，其中 $a\in Z_m\backslash \left\{0\right\},b,c\in Z_m$ ；

类型5： $x\ne y\ne z\ne w$ ， $B_5=\left\{\left(x,0\right),\left(y,a\right),\left(z,b\right),\left(w,c\right)\right\}$ ，其中 $a,b,c\in Z_m$。

引理3.1 [10] 令B是 $Z_m$ 的任意4-子集轨道代表元且 $\lambda \left(B\right)\le 3$。B包含3个不同的3-子集轨道代表元

当且仅当B形如 $\{0,a,2a,3a\}$ ，其中 $a\in Z_m$ 且 $a\ne \frac{m}{5},\frac{2m}{5}$ ；B包含2个不同的3-子集轨道代表元当且仅当B形如 $\{0,a,2a,3a\}$,其中 $a\in \{\frac{m}{5},\frac{2m}{5}\}$ ；其余形式的B均包含4个不同的3-子集轨道代表元。

引理3.2令B是 $Z_m$ 的任意4-子集轨道代表元且 $\lambda \left(B\right)\le 1$ ，B包含4个不同的3-子集轨道代表元。

证明：根据引理3.1可知，若B是形如 $\left\{0,a,2a,3a\right\}$ ， $\lambda \left(B\right)\ge 2$ ，所以，当 $\lambda \left(B\right)\le 1$ 时，B包含4个不同的3-子集轨道代表元。

引理3.3 设 $\mathcal{B}$ 是 $\left(n\times m,4,1,2\right)$ 光正交码，任意 $B\in \mathcal{B}$ ，B包含4个不同的3-子集轨道代表元。

证明：下面将根据码字的不同类型分类讨论B包含的3-子集轨道代表元。

若 $B_1=\left\{\left(x,0\right),\left(x,a\right),\left(x,b\right),\left(x,c\right)\right\}\in \mathcal{B}$ ，对于任意 $x\in I_n$ ， $2-D\left(\left\{x\right\}\times m,4,1,2\right)-OOC$ ，即为 $1-D\left(m,4,1,2\right)-OOC$。考虑 $B_1$ 的派生集 $X=\left\{0,a,b,c\right\}$ ，根据引理3.2，可得 $B_1$ 包含4个不同的3-子集轨道代表元。

若 $B_2=\left\{\left(x,0\right),\left(x,a\right),\left(x,b\right),\left(w,c\right)\right\}\in \mathcal{B}$ ， $B_2$ 包含的4个3-子集轨道代表元为 $B_{21}=\{\left(x,0\right),\left(x,a\right),\left(x,b\right)\}$ ， $B_{22}=\left\{\left(x,0\right),\left(x,a\right),\left(w,c\right)\right\}$ ， $B_{23}=\left\{\left(x,0\right),\left(x,b\right),\left(w,c\right)\right\}$ ， $B_{24}=\left\{\left(x,a\right),\left(x,b\right),\left(w,c\right)\right\}$。根据第一坐标， $B_{21}$ 与 $B_{22},B_{23},B_{24}$ 不在同一轨道；由于 $\lambda \left(B_2\right)=1$ 当且仅当 $\left|supp\left(\Delta \left(B_2\right)\right)\right|=6$ 所以 ${\Delta }_{xx}\left(B_2\right)=\left\{\pm a,\pm b,\pm \left(b-a\right)\right\}$ 中元素互不相等，则 ${\Delta }_{xx}\left(B_{22}\right)=\{\pm a\},{\Delta }_{xx}\left(B_{23}\right)=\{\pm b\},{\Delta }_{xx}\left(B_{24}\right)=\{\pm \left(b-a\right)\}$ 三者互不相等。于是 $B_2$ 包含4个不同的3-子集轨道代表元。

若 $B_3=\left\{\left(x,0\right),\left(x,a\right),\left(z,b\right),\left(z,c\right)\right\}\in \mathcal{B}$ ， $B_3$ 包含的4个3-子集轨道代表元为 $B_{31}=\{\left(x,0\right),\left(x,a\right),\left(z,b\right)\}$ ， $B_{32}=\left\{\left(x,0\right),\left(x,a\right),\left(z,c\right)\right\}$ ， $B_{33}=\left\{\left(x,0\right),\left(z,b\right),\left(z,c\right)\right\}$ 和 $B_{34}=\left\{\left(x,a\right),\left(z,b\right),\left(z,c\right)\right\}$。根据第一坐标，只有 $B_{31}$

与 $B_{32}$ 或 $B_{33}$ 与 $B_{34}$ 可能在同一轨道。若 $B_{31}$ 和 $B_{32}$ 在同一轨道，则 $B_{31}+l=B_{32},l\in Z_m\backslash \left\{0\right\}$ 可得 $l=a=\frac{m}{2}$ ，又因为 $\lambda \left(B_3\right)=1$ ，所以 $a\ne \frac{m}{2}$ ，产生矛盾，则 $B_{31}$ 与 $B_{32}$ 不在同一轨道。同理可得 $B_{33}$ 与 $B_{34}$ 不在同一轨道。

于是 $B_3$ 包含4个不同的3-子集轨道代表元。

若 $B_4=\left\{\left(x,0\right),\left(x,a\right),\left(z,b\right),\left(w,c\right)\right\}\in \mathcal{B}$ ， $B_4$ 包含的4个3-子集轨道代表元为 $B_{41}=\{\left(x,0\right),\left(x,a\right),\left(z,b\right)\}$ ， $B_{42}=\left\{\left(x,0\right),\left(x,a\right),\left(w,c\right)\right\}$ ， $B_{43}=\left\{\left(x,0\right),\left(z,b\right),\left(w,c\right)\right\}$ ， $B_{44}=\left\{\left(x,a\right),\left(z,b\right),\left(w,c\right)\right\}$。根据第一坐标，只有 $B_{43}$ 与 $B_{44}$ 可能在同一轨道；若 $B_{43}$ 和 $B_{44}$ 在同一轨道，则 $a\equiv 0\left(\mathrm{mod}m\right)$ 而 $a\in Z_m\backslash \left\{0\right\}$ ，产生矛盾，所以 $B_{43}$ 与 $B_{44}$ 不在同一轨道。于是 $B_4$ 包含4个不同的3-子集轨道代表元。

若 $B_5=\left\{\left(x,0\right),\left(y,a\right),\left(z,b\right),\left(w,c\right)\right\}\in \mathcal{B}$ ， $B_5$ 包含的4个3-子集轨道代表元为 $B_{51}=\{\left(x,0\right),\left(y,a\right),\left(z,b\right)\}$ ， $B_{52}=\left\{\left(x,0\right),\left(y,a\right),\left(w,c\right)\right\}$ ， $B_{53}=\left\{\left(x,0\right),\left(z,b\right),\left(w,c\right)\right\}$ ， $B_{54}=\left\{\left(y,a\right),\left(z,b\right),\left(w,c\right)\right\}$。根据第一坐标，可得 $B_{51},B_{52},B_{53},B_{54}$ 不在同一轨道。于是 $B_5$ 包含4个不同的3-子集轨道代表元。

综上所述， $\left(n\times m,4,1,2\right)$ 光正交码的每个码字都包含4个不同的3-子集轨道代表元。

在文献 [4] 中定理1给出了， $2-D\left(n\times m,3,1,2\right)-OOC$ 的上界；

引理3.4 [4] 设n和m是正整数，则 $2-D\left(n\times m,3,1,2\right)-OOC$ 的上界

$\Phi \left(n\times m,3,1,2\right)=\{\begin{array}{ll}\frac{n\left(n^2{m}^2-3nm-3m+5\right)}{6},\hfill & \left(m,12\right)=1,\hfill \\ \frac{n\left(n^2{m}^2-6nm-3m+14\right)}{6},\hfill & \left(m,12\right)=2,\hfill \\ \frac{n\left(n^2{m}^2-3nm-3m+9\right)}{6},\hfill & \left(m,12\right)=3,\hfill \\ \frac{n\left(n^2{m}^2-6nm-3m+20\right)}{6},\hfill & \left(m,12\right)=4,\hfill \\ \frac{n\left(n^2{m}^2-6nm-3m+18\right)}{6},\hfill & \left(m,12\right)=6,\hfill \\ \frac{n\left(n^2{m}^2-6nm-3m+24\right)}{6},\hfill & \left(m,12\right)=12.\hfill \end{array}$

下面证明定理1.1

证明：设 $\mathcal{B}$ 是 $\left(n\times m,4,1,2\right)$ 光正交码， $A,B\in \mathcal{B},A\ne B,l\in Z_m$。根据定义， $\left|B\cap \left(B+l\right)\right|\le 1$ ， $\left|A\cap \left(B+l\right)\right|\le 2$。令 $A^{\prime },B^{\prime }$ 分别是 $A,B$ 的一个3-子集轨道代表元，所以可得 $\left|B^{\prime }\cap \left(B^{\prime }+l\right)\right|\le 1$ ， $\left|A^{\prime }\cap \left(B^{\prime }+l\right)\right|\le 2$。于是 $\mathcal{B}$ 中码字的3-子集轨道代表元属于 $2-D\left(n\times m,3,1,2\right)-OOC$ ，再根据引理3.3，引理3.4，可得

$4\Phi \left(n\times m,4,1,2\right)\le \Phi \left(n\times m,3,1,2\right)$ ，

经进一步计算得定理1.1结果成立。通过附录中部分 $\left(n\times m,4,1,2\right)$ 光正交码的码字最大容量和表1的对比结果，可以更好的验证定理1.1的正确性。

Table 1. Partial comparison results

表1. 部分对比结果

4. 结论

本文根据每个码字中包含的3-子集轨道代表元的个数确定了 $\left(n\times m,4,1,2\right)$ 光正交码的最大容量 $\Phi \left(n\times m,4,1,2\right)$ ，但并不是每个属于 $\left(n\times m,3,1,2\right)$ 光正交码的码字都能构成 $\left(n\times m,4,1,2\right)$ 光正交码中满足自相关的码字，也不是 $\left(n\times m,4,1,2\right)$ 光正交码中满足自相关的码字构成最大容量的码字时每个属于 $\left(n\times m,3,1,2\right)$ 光正交码的码字都能出现一次；所以，定理1.1中 $\left(n\times m,4,1,2\right)$ 光正交码的最大容量 $\Phi \left(n\times m,4,1,2\right)$ 不够紧密，下一步为确定 $\left(n\times m,4,1,2\right)$ 光正交码精确的码字容量的上界，就要寻找 $\left(n\times m,3,1,2\right)$ 光正交码的码字和 $\left(n\times m,4,1,2\right)$ 光正交码的码字间更紧密的关系。

基金项目

国家自然科学基金资助项目(11401326)；内蒙古教育厅项目(NJZY22599, NJZY22600)；内蒙古师范大学研究生科研创新基金项目(CXJJS21122)。

附录

n=2, m=5

{(0, 0), (0, 1), (1, 0), (1, 2)}, {(0, 0), (0, 1), (1, 1), (1, 4)}, {(0, 0), (0, 2), (1, 0), (1, 1)}, {(0, 0), (0, 2), (1, 3), (1, 4)}.

n = 2, m = 6

{(0, 0), (0, 1), (1, 0), (1, 2)}, {(0, 0), (0 ,1), (1, 3), (1, 5)}, {(0, 0), (0, 2), (1, 0), (1, 1)}, {(0, 0), (0, 2), (1, 3), (1, 4)}.

n = 3, m = 3

{(0, 0), (0, 1), (1, 0), (2, 0)}, {(0, 0), (0, 1), (1, 2), (2, 2)}, {(0, 0), (1, 0), (1, 1), (2, 2)}, {(0, 0), (1, 0), (1, 2), (2, 1)}, {(0, 0), (1, 1), (1, 2), (2, 0)}.

n = 3, m = 4

{(0, 0), (0, 1), (1 ,0), (2, 0)}, {(0, 0), (0, 1), (1, 1), (2, 2)}, {(0, 0), (0, 1), (1, 2), (2, 1)}, {(0, 0), (0, 1), (1, 3), (2, 3)},

{(0, 0), (1, 0), (1, 1), (2, 3)}, {(0, 0), (1, 0), (1, 3), (2, 2)}, {(0, 0), (1, 2), (2, 0), (2, 3)}, {(0, 0), (1, 3), (2, 0), (2, 1)}.

n = 4, m = 2

{(0, 0), (1, 0), (2, 0), (3, 0)}, {(0, 0), (1, 0), (2, 1), (3, 1)}, {(0, 0), (1, 1), (2, 0), (3, 1)}, {(0, 0), (1, 1), (2, 1), (3, 0)}.

n = 5, m = 2

{(0, 0), (1, 0), (2, 0), (3, 0)}, {(0, 0), (1, 0), (2, 1), (3, 1)}, {(0, 0), (1, 1), (2, 0), (4, 0)}, {(0, 0), (1, 1), (3, 0), (4, 1)} {(0, 0), (2, 0), (3, 1), (4, 1)}, {(0, 0), (2, 1), (3, 0), (4, 0)}, {(1, 0), (2, 0), (3, 1), (4 ,0)}, {(1, 0), (2, 1), (3, 0), (4, 1)}.

NOTES

^*通讯作者。