百色学院，数学与统计学院，广西 百色

收稿日期：2022年2月21日；录用日期：2022年3月15日；发布日期：2022年3月22日

摘要

目前，对最优冲突回避码的具体构造取得的结果不多，利用欧拉函数和同余数在整数环的特性给出一种构造的新方法，进一步具体构造码重k = 3，4，5，6时最优冲突回避码的一系列新结果。

关键词

冲突回避码，二次剩余，欧拉函数

New Constructions of Optimal Conflict-Avoiding Codes

Bichang Huang

College of Mathematics and Statistics, Baise University, Baise Guangxi

Received: Feb. 21^st, 2022; accepted: Mar. 15^th, 2022; published: Mar. 22^nd, 2022

ABSTRACT

Previously, there are very few results of explicit constructions of optimal conflict-avoiding code. In this paper, combing new constructions with Euler function and congruent numbers’ properties in integer rings, a new infinite series of optimal conflict-avoiding codes with weight k = 3, 4, 5, 6 are obtained.

Keywords:Conflict-Avoiding Code, Quadratic Residue, Euler Function

Copyright © 2022 by author(s) and Hans Publishers Inc.

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

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

1. 引言

冲突回避码(Conflict-avoiding Code，简记CAC)在无反馈多分址信道(冲突信道)有重要的应用 [1] [2]。类似于文献 [3] 其数学描述如下：

设 ${\mathbb{Z}}_n$ 表示模 $n$ 的剩余类环， ${\mathbb{Z}}_n^{\ast }$ 表示 ${\mathbb{Z}}_n\backslash \left\{0\right\}$。对于 $k$ 阶子集 $A\subseteq {\mathbb{Z}}_n$，定义 $A$ 的差集为多重集合

$\Delta \left(A\right)=\left\{x-y\left(\mathrm{mod}n\right):x,y\in A,x\ne y\right\}.$

设 $\mathcal{C}$ 是 ${\mathbb{Z}}_n$ 一些 $k$ 阶子集 $A\subseteq {\mathbb{Z}}_n$ 的集合，则 $\mathcal{C}$ 被称为长度为 $n$ 重量为 $k$ 的冲突回避码若其满足以下条件

$\Delta \left(A_1\right)\cap \Delta \left(A_2\right)=\varnothing ,\forall A_1,A_2\in \mathcal{C},A_1\ne A_2.$

每个元素 $A\in \mathcal{C}$ 称为一个码字。对于给定的 $n$ 和 $k$，符号 $\text{CAC}\left(n,k\right)$ 表示所有长度为 $n$ 重量为 $k$ 的冲突回避码。

对于冲突回避码 $C\in \text{CAC}\left(n,k\right)$，码字的重量 $k$ (汉明码重量)表示用户在每个时段的 $n$ 个时槽里发送 $k$ 个数据包 [4]。对于给定的正整数 $n,k$，如果 $C\in \text{CAC}\left(n,k\right)$ 是一个码字个数最多的码，那么称 $C$ 为一个最优码。

若 $A\subseteq Z_n$ 可以表示成为 $A=\left\{0,g,2g,\cdots ,\left(k-1\right)g\right\},g\in Z_n^{\ast }$ 的形式，则称 $A$ 为等差(equi-difference)码字。 $g$ 称为 $A$ 的生成元。不难验证 $\Delta \left(A\right)=\left\{\pm g,\pm 2g,\cdots ,\pm \left(k-1\right)g\right\}$。若码 $C\in \text{CAC}\left(n,k\right)$ 的每个码字 $A\in C$ 都是等差码字，则称为 $C$ 等差码。类似的，符号 ${\text{CAC}}^{\text{e}}\left(n,k\right)$ 表示所有长度为 $n$ 重量为 $k$ 的等差码。用符号 $\Gamma \left(C\right)$ 表示等差码 $C$ 所有码字生成元的集合。等差码是一种特殊的码，人们通常利用它构造最优码。

目前，当 $k=3$ 时的最优冲突回避码构造证明已经基本解决 [5] - [10]。当 $k>3$ 的最优冲突回避码具体构造较少 [3] [4] [11]。本文利用利用欧拉函数和同余数在整数环的特性给出一种构造得新方法，给出新的构造方法，进一步给出当 $k=3,4,5,6$ 时对最优冲突回避码具体构造的一些新结果。

2. 相关的构造

为了方便理解，我们介绍一些常用的概念和符号。

设 $p=2em+1$ 是奇素数， $\theta \in Z_p^{\ast }$ 是 $Z_p^{\ast }$ 的生成元，设 $\theta \in H_0^{2e}=\left\{{\theta }^{2es}:s=0,1,\cdots ,m-1\right\}$ 是 $Z_p^{\ast }$ 的 $m$ 阶乘法子群，则 $Z_p^{\ast }$ 有陪集分解： $Z_p^{\ast }={\displaystyle \underset{i=0}{\overset{2e-1}{\cup }}{H}_i^{2e}}$，其中 $H_i^{2e}={\theta }^i{H}_0^{2e},0\le i\le 2e-1$ 称陪集 $H_i^{2e}$ 为 $2e$ 阶分圆类。若 $j_t\in H_i^{2e},0\le i\le 2e-1$。则称 $\left\{j_0,j_1,\cdots ,j_{2e-1}\right\}$ 一个为 $2e$ 阶分圆类代表系。

引理1 [4]. 设 $e\ge 1$ 和 $s>1$ 都是整数， $p=2em+1$ 是素数且使得每一个 $\left(\pm s,\pm 2s,\cdots ,\pm es\right)$ 和 $\left(i-es,i-\left(e-1\right)s,\cdots ,i+\left(e-1\right)s\right),1\le i\le s-1$ 都各自形成一个 $2e$ 阶分圆类代表系。那么存在一个码 $C\in {\text{CAC}}^{\text{e}}\left(sp,k=es+1\right)$ 包含 $m$ 个码字，且满足 $Z_{sp}\backslash \Delta \left(C\right)=p{Z}_{sp}$。

引理2 [11]. 若 $m>s$，则引理1构造的码 $C\in {\text{CAC}}^{\text{e}}\left(sp,k=es+1\right)$ 是最优的。

引理3 [4]. 设 $k\ge 3$，$L_1,L_2$ 和 $s$ 都是正整数，且 $s|L_1$，$\gcd \left(l,L_2\right)=1,l=2,3,\cdots ,\left(k-1\right)$。设 $C_1\in {\text{CAC}}^{\text{e}}\left(L_1,k\right)$ 包含 $m_1$ 个码字 $A_1,A_2,\cdots ,A_{m_1}$ 使得

$Z_{L_1}\backslash {\displaystyle \underset{j=1}{\overset{m_1}{\cup }}\Delta \left(A_j\right)}\supseteq \left(\frac{L_1}{s}\right)Z_{L_1}$.

设 $C_2\in {\text{CAC}}^{\text{e}}\left(s{L}_2,k\right)$ 包含 $m_2$ 个码字。设码 $C$ 是由

$\Gamma \left(C\right)=\left\{i+j{L}_1:i\in \Gamma \left(C_1\right),j\in Z_{L_1}\cup \left\{\left(\frac{L_1}{s}\right)y:y\in \Gamma \left(C_2\right)\right\}\right\}$

生成。则 $C\in {\text{CAC}}^{\text{e}}\left(L_1{L}_2,k\right)$ 且包含 $m_1{L}_1+m_2$ 个码字。

利用引理1和引理2来具体构造一些最优冲突回避码。再利用引理3构造出一系列的冲突回避码

$C\in {\text{CAC}}^{\text{e}}\left(\left(k-1\right){\displaystyle \underset{i=1}{\overset{r}{\prod }}{p}_i},k\right)$ [3] [4]。但是，实际情况下，我们很难得到最优 $C\in {\text{CAC}}^{\text{e}}\left(\left(k-1\right){\displaystyle \underset{i=1}{\overset{r}{\prod }}{p}_i},k\right)$。本文首次利用欧拉函数和同余数的特性，对 $Z_{p^r}^{\ast }$ 进行划分，得到类似于引理2的一般构造，并给出具体构造码重 $k=3,4,5,6$ 时最优冲突回避码的一系列新结果。

3. 新的构造方法及其证明

设 $n$ 为一个正整数，称 $G=\left\{a|\left(a,n\right)=1,a\in Z_n^{*}\right\}$ 是 $Z_n^{\ast }$ 简约剩余系，则 $\left|G\right|=\Phi \left(n\right)$，其中 $\Phi \left(n\right)$ 是欧拉函数。显然， $G=\left\{a|\left(a,n\right)=1,a\in Z_n^{*}\right\}$ 是一个乘法群。

设 $p=2m+1$ 是奇素数， $r$ 为一个正整数，元素 ${\theta }_j\in Z_{p^j}^{\ast }$ 是乘法群 $G_j=\left\{a|\left(a,n\right)=1,a\in Z_{p^j}^{*}\right\},1\le j\le r.$ 的一个生成元，则 $\left|G_j\right|=\Phi \left(p^j\right)$。又设 $H_{j0}^2=\left\{{\theta }^{2s}:s=0,1,\cdots ,m-1\right\},1\le j\le r$ 是 $G_j=\left\{a|\left(a,n\right)=1,a\in Z_{p^j}^{*}\right\}$ 的 $m$ 阶乘法子群，则 $G_j$ 有陪集分解： $G_j=H_{j0}^2\cup H_{j1}^2$,其中 $H_{j1}^2={\theta }_j{}^1{H}_{j0}^2$，称陪集 $H_{ji}^2$ 为2阶分圆类。若 $d_i\in H_{ji}^2,0\le i\le 1$。则称 $\left\{d_0,d_1\right\}$ 为 $G_j$ 的一个2阶分圆类代表系。下面得到类似于引理2的一般构造。

定理1. 设 $s,r$ 是正整数， $p$ 是奇素数且使得每一个 $\left(i-s,i\right),1\le i\le s-1$ 和 $\left(\pm s\right)$ 都各自形成 $G_j,j=1,2,\cdots ,r$ 的一个2阶分圆类代表系。那么存在一个码 $C\in {\text{CAC}}^{\text{e}}\left(s{p}^r,k=s+1\right)$ 包含 $\frac{p^r-1}{2}$ 个码字，且满足 $Z_{s{p}^r}\backslash \Delta \left(C\right)=p{Z}_{s{p}^r}$。

证 在 $Z_s\times Z_{p^r}$ 上设 ${\Gamma }_j\left(C\right)=\left\{1\right\}\times \left(p^{r-j}{H}_{jo}^2\right),j=1,2,\cdots ,r.$ 则 $C$ 的码字表示如下：

$x_j^l=\left\{\left(0,0\right),\left(1,1\right),\cdots ,\left(\left(k-1\right),\left(k-1\right)\right)\right\}\cdot \left\{1,p^{r-j}{\theta }_j^{2l}\right\},l=0,1,\cdots ,\Phi \left(p^j\right),j=1,2,\cdots ,r.$

故

$\Delta \left(x_j^l\right)=\{\begin{array}{l}\left\{0\right\}\times \left\{s{\theta }_j^2{p}^{r-j},-s{\theta }_j^2{p}^{r-j}\right\},i=0,\hfill \\ \left\{i\right\}\times \left\{\left(i-s\right){\theta }_j^2{p}^{r-j},i{\theta }_j^2{p}^{r-j}\right\},1\le i\le s-1,\hfill \end{array}$

即

$\begin{array}{l}\Delta \left(C\right)=\underset{j=1}{\overset{r}{{\displaystyle \cup }}}\underset{l=1}{\overset{\Phi (p^j)}{{\displaystyle \cup }}}\Delta \left(x_j^l\right)\\ =\underset{j=1}{\overset{r}{{\displaystyle \cup }}}\left(\underset{i=1}{\overset{s-1}{{\displaystyle \cup }}}\left(\left\{i\right\}\times \left(p^{r-j}{H}_{jo}^2\right)\right)\cdot \left(i-s,i\right)\right)\cup \left(\left(\left\{0\right\}\times \left(p^{r-j}{H}_{jo}^2\right)\right)\cdot \left(-s,s\right)\right)\\ =\underset{j=1}{\overset{r}{{\displaystyle \cup }}}\underset{i=1}{\overset{s-1}{{\displaystyle \cup }}}\left(\left\{i\right\}\times \left(p^{r-j}{G}_j\right)\right)\\ =Z_s\times Z_{p^r}^{\ast }\end{array}$

由 $s=k-1$，$p^r-1={\displaystyle \underset{j=1}{\overset{r}{\sum }}\Phi \left(p^j\right)}$ 得， $\left|C\right|=\frac{s{\displaystyle \underset{j=1}{\overset{r}{\sum }}\Phi \left(p^j\right)}}{2\left(k-1\right)}=\frac{s\left(p^r-1\right)}{2\left(k-1\right)}=\frac{p^r-1}{2}$。

定理 2. 定理1构造的码 $C\in {\text{CAC}}^{\text{e}}\left(s{p}^r,k=s+1\right)$ 是最优的。

因为 $\lfloor \frac{s{p}^r-1}{2\left(k-1\right)}\rfloor =\lfloor \frac{s{p}^r-s+s-1}{2\left(k-1\right)}\rfloor =\lfloor \frac{s{p}^r-s+s-1}{2s}\rfloor =\frac{p^r-1}{2}$。

下面，根据同余性质结合定理1具体构造码重 $k=3,4,5,6$ 时最优冲突回避码的一系列新结果，由定理2知，结果是最优的。

设 $p$ 是奇素数，对于 $a\in Z_p^{\ast }$，若同余方程 $x^2\equiv a\left(\mathrm{mod}p\right)$ 有解，称 $a$ 为模 $p$ 的二次剩余(quadratic residue) (即 $a\in H_0^2$)。否则，称 $a$ 模 $p$ 的二次非剩余(quadratic non-residue) $a\in H_1^2$。定义 $Z_p$ 上的勒让德符号 $\left(\frac{a}{p}\right)$ 为：

$\left(\frac{a}{p}\right)=\{\begin{array}{l}1,若a\in H_0^2,\hfill \\ -1,若a\in H_1^2,\hfill \\ 0,若p|a.\hfill \end{array}$

且具有性质 $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$。

关于勒让德符号有如下结果。

引理 4 [12]. 若 $p$ 是奇素数，则

$\left(\frac{-1}{p}\right)=\{\begin{array}{c}1,若p\equiv 1\left(\mathrm{mod}4\right),\\ -1,若p\equiv 3\left(\mathrm{mod}4\right).\end{array}$

$\left(\frac{2}{p}\right)=\{\begin{array}{c}1,若p\equiv \pm 1\left(\mathrm{mod}8\right),\\ -1,若p\equiv \pm 3\left(\mathrm{mod}8\right).\end{array}$

$\left(\frac{3}{p}\right)=\{\begin{array}{c}1,若p\equiv \pm 1\left(\mathrm{mod}12\right),\\ -1,若p\equiv \pm 5\left(\mathrm{mod}12\right).\end{array}$

引理5 [13]. 同余方程 $x^2\equiv a\left(\mathrm{mod}{p}^j\right),j=1,2,3,\cdots ,r$，有解的充要条件是 $\left(\frac{a}{p}\right)=1$。

推论1. 若素数 $p\equiv 7\left(\mathrm{mod}8\right)$，$r$ 是正整数，则存在最优码 $C\in {\text{CAC}}^{\text{e}}\left(2p^r,3\right)$ 包含 $\frac{p^r-1}{2}$ 个码字。

证 根据定理1~2和引理4~5并结合勒让德符号的性质，在 $G_j,j=1,2,\cdots ,r$ 中只需证 $\left(\frac{a}{p}\right)\ne \left(\frac{b}{p}\right)$ 对于每对 $\left\{a,b\right\}\in \left\{\left\{-2,2\right\},\left\{-1,2\right\}\right\}$。即只需证

$\left(\frac{-1}{p}\right)=-1,\left(\frac{2}{p}\right)=1.$

而当 $p\equiv 7\left(\mathrm{mod}8\right)$ 时以上条件满足。从而命题得证。

推论2. 若素数 $p\equiv 7\left(\mathrm{mod}8\right)$，$r$ 是正整数，则存在最优码 $C\in {\text{CAC}}^{\text{e}}\left(3p^r,4\right)$ 包含 $\frac{p^r-1}{2}$ 个码字。

证 根据定理1~2和引理4~5并结合勒让德符号的性质，在 $G_j,j=1,2,\cdots ,r$ 中只需证 $\left(\frac{a}{p}\right)\ne \left(\frac{b}{p}\right)$ 对于每对 $\left\{a,b\right\}\in \left\{\left\{-3,3\right\}\left\{-2,1\right\},\left\{-1,2\right\}\right\}$。即只需证

$\left(\frac{-1}{p}\right)=-1,\left(\frac{2}{p}\right)=1.$

而当 $p\equiv 7\left(\mathrm{mod}8\right)$ 时以上条件满足。从而命题得证。

推论3. 若素数 $p\equiv 11\left(\mathrm{mod}12\right)$，$r$ 是正整数，则存在最优码 $C\in {\text{CAC}}^{\text{e}}\left(4p^r,5\right)$ 包含 $\frac{p^r-1}{2}$ 个码字。

证 根据定理1~2和引理4~5并结合勒让德符号的性质，在 $G_j,j=1,2,\cdots ,r$ 中只需证 $\left(\frac{a}{p}\right)\ne \left(\frac{b}{p}\right)$ 对于每对 $\left\{a,b\right\}\in \left\{\left\{-4,4\right\},\left\{-3,1\right\},\left\{-2,2\right\},\left\{-1,3\right\}\right\}$。即只需证

$\left(\frac{-1}{p}\right)=-1,\left(\frac{3}{p}\right)=1.$

而当 $p\equiv 11\left(\mathrm{mod}12\right)$ 时以上条件满足。从而命题得证。

推论4. 若素数 $p\equiv 23\left(\mathrm{mod}24\right)$，$r$ 是正整数，则存在最优码 $C\in {\text{CAC}}^{\text{e}}\left(5p^r,6\right)$ 包含 $\frac{p^r-1}{2}$ 个码字。

证 根据定理1~2和引理4~5并结合勒让德符号的性质，在 $G_j,j=1,2,\cdots ,r$ 中只需证 $\left(\frac{a}{p}\right)\ne \left(\frac{b}{p}\right)$ 对于每对 $\left\{a,b\right\}\in \left\{\left\{-5,5\right\},\left\{-4,1\right\},\left\{-3,2\right\},\left\{-2,1\right\},\left\{-1,4\right\}\right\}$。即只需证

$\left(\frac{-1}{p}\right)=-1,\left(\frac{2}{p}\right)=\left(\frac{3}{p}\right)=1.$

而当 $p\equiv 23\left(\mathrm{mod}24\right)$ 时以上条件满足。从而命题得证。

4. 结论

本文给出新的构造方法具体构造出一系列最优的冲突回避码得。该方法也可以给光正交码的构造提供借鉴。

基金项目

广西自然科学基金项目(2018GXNSFAA281259)。

文章引用

黄必昌. 最优冲突回避码新的构造方法
New Constructions of Optimal Conflict-Avoiding Codes[J]. 应用数学进展, 2022, 11(03): 1134-1139. https://doi.org/10.12677/AAM.2022.113122

参考文献