用户: 鲖阳路人/有限环上的线性码的 Singleton 界

本文译自

•	Shiromoto, K. Singleton Bounds for Codes over Finite Rings. Journal of Algebraic Combinatorics 12, 95–99 (2000). https://doi.org/10.1023/A:1008767703006

1引言

设 $R$ 是一个有限交换拟 Frobenius (QF) 环 (参见 [1]) , 并设 $V:=R^n$ 是由 $R$ 中元素的所有 $n$ 元组组成的秩为 $n$ 的自由模. $R$ 上的一个长度为 $n$ 的码 $C$ 是 $V$ 的一个 $R$-子模. $C$ 的元素称为 $C$ 的码字.

在本文中, 我们将使用一个从 Hamming 权重、Lee 权重和 Euclid 权重中抽象出来的一般权重概念. 对于每个 $x=(x_1,\dots ,x_n)\in V$ 和 $r\in R$, $x$ 的完全权重定义为$$n_r(x):=|\{i\mid x_i=r\}|.$$为了定义一般权重函数 $w(x)$, 设 $a_r$, $(0\ne )r\in R$, 为正实数, 并设 $a_0=0$. 设$$w(x):=\sum _{r\in R}{a}_r{n}_r(x).$$(1)如果我们设 $a_r=1$, $(0\ne )\forall r\in R$, 那么 $w(x)$ 就是 $x$ 的 Hamming 权重. 为了后续使用, 我们记$$A:=\max \{a_r\mid r\in R\}.$$(2)例如, 如果 $R={\mathbb{Z}}_4=\{0,1,2,3\}$, 那么设 $a_1=a_3=1$ 和 $a_2=2$ 就得到了 Lee 权重, 而设 $a_1=a_3=1$ 和 $a_2=4$ 就得到了 Euclid 权重.

设 $N:=\{1,2,\dots ,n\}$. 定义向量 $x=(x_1,\dots ,x_n)\in V$ 的支撑 $\mathrm{supp}(x)$ 为$$\mathrm{supp}(x):=\{i\in N\mid x_i\ne 0\}.$$

码 $C$ 的最小权重, 记为 $d$, 定义为

$$d:=\min \{w(x)|(0\ne )x\in C\}.$$

我们做出一个重要 (且基本) 的观察:

$$w(x)\le A|\mathrm{supp}(x)|.$$(3)

向量 $x=(x_1,\dots ,x_n)$ 和 $y=(y_1,\dots ,y_n)\in V$ 的内积定义为

$$⟨x,y⟩=x_1{y}_1+\cdots +x_n{y}_n.$$

$C$ 的对偶码定义为

$$C^{\perp }:=\{y\in V|⟨x,y⟩=0(\forall x\in C)\}.$$

以下命题是众所周知的 Singleton 界 (参见 [4]) .

命题 1.1. 设 $C$ 是 ${\mathbb{F}}_q$ 上的线性 $[n,k,d]$-码, 其中 $d$ 是 $C$ 的最小 Hamming 权重. 那么,

$$d\le n-k+1.$$

本文的主要目的是对 $R$ 上一般权重函数 $w(x)$ 的最小权重找到类似的界.

2Singleton 界

对于 $V$ 的一个子模 $D$ 和一个子集 $M\subseteq N=\{1,2,\dots ,n\}$, 设$$\begin{array}{rl}D(M)& :=\{x\in D|\mathrm{supp}(x)\subseteq M\},\\ D^{\ast }& :={\mathrm{Hom}}_R(D,R).\end{array}$$显然 $D(M)=D\cap V(M)$ 是 $V$ 的一个子模, 且 $|V(M)|=|R{|}^{|M|}$. 对于 $V$ 的任何子模, 也有 $|D|=|D^{\ast }|$. 以下引理是关键的 (在 ${\mathbb{F}}_q$ 上有类似的结果, 参见 [6]) .

引理 2.1. 设 $C$ 是 $R$ 上的长度为 $n$ 的码, 且 $M\subseteq N$. 那么存在一个 $R$-模的正合序列: $$0\to C^{\perp }(M)\stackrel{\mathrm{inc}}{\to }V(M)\stackrel{f}{\to }{C}^{\ast }\stackrel{\mathrm{res}}{\to }C(N\setminus M{)}^{\ast }\to 0,$$其中映射 $\mathrm{inc}$、$\mathrm{res}$ 分别表示包含映射和限制映射, 而映射 $f$ 定义为$$f:y\mapsto (\hat{y}:x\mapsto ⟨x,y⟩).$$

证明. 序列在 $C^{\perp }(M)$ 和 $V(M)$ 处的正合性是显然的. 映射 $\mathrm{res}$ 的满射性由 $R$ 是自身的单射模 (即 $R$ 是 QF 环的含义) 得出.

显然我们有 $\mathrm{Im}f\subseteq \ker (\mathrm{res})$. 反之, 如果我们取任意 $\lambda \in \ker (\mathrm{res})$, 那么$$\lambda (x)=0(\forall x\in C(N\setminus M)).$$注意到 $V\to C^{\ast }$; $v\mapsto \hat{v}$ 是满射, 因此存在 $y\in V$ 使得 $\lambda =\hat{y}$. 对于任何 $x\in C(N\setminus M)$, $⟨x,y⟩=0$, 因此$$\begin{gathered} y\in (C(N\setminus M){)}^{\perp }=(C\cap V(N\setminus M){)}^{\perp } \\ =C^{\perp }+V(N\setminus M{)}^{\perp }=C^{\perp }+V(M). \end{gathered}$$由于对于任何 $z\in C^{\perp }$ 都有 $\hat{z}=0$, 我们有$$\ker (\mathrm{res})\subseteq \mathrm{Im}f.$$因此序列在 $C^{\ast }$ 处也是正合的, 引理得证.

$\square$

我们注意到, 我们可以通过使用引理 2.1 来证明 ${\mathbb{Z}}_4$ 上码的 MacWilliams 恒等式 (参见 [3]) (在 ${\mathbb{F}}_q$ 上有类似的结果, 参见 [5] 和 [6]) .

利用上述引理, 我们建立了 $R$ 上一般权重函数的 Singleton 界.

定理 2.2. 设 $C$ 是有限交换 QF 环 $R$ 上的长度为 $n$ 的码. 设 $w(x)$ 是 $C$ 上的一般权重函数, 如 (1) 所示, 且最大 $a_r$ 值为 $A$, 如 (2) 所示. 假设 $w(x)$ 在 $C$ 上的最小权重为 $d$. 那么$$\lfloor \frac{d-1}{A}\rfloor \le n-{\log }_{|R|}|C|,$$其中 $\lfloor b\rfloor$ 是 $b$ 的整数部分.

证明. 根据引理 2.1, 我们有$$|C|\cdot |C^{\perp }(N\setminus \tilde{M})|=|V(N\setminus \tilde{M})|\cdot |C(\tilde{M})|,$$其中 $\tilde{M}=N\setminus M$. 如果我们取 $N$ 的子集 $M$, 使得 $|\tilde{M}|=\lfloor \frac{d-1}{A}\rfloor$, 那么根据 (3), $|C(\tilde{M})|=1$. 由于我们总是有 $|C^{\perp }(N\setminus \tilde{M})|\ge 1$, 我们得到$$|C|\le |V(N\setminus \tilde{M})|=|R{|}^{|N\setminus \tilde{M}|}.$$因此定理得证.

$\square$

3在 ${\mathbb{Z}}_{\ell }$ 上码的应用

环 $R={\mathbb{Z}}_{\ell }$ 是有限交换 QF 环的一个很好的例子. 设 $k:=\lfloor \ell /2\rfloor$, 并将 ${\mathbb{Z}}_{\ell }$ 视为集合 $\{0,\pm 1,\dots ,\pm k\}$ (当 $\ell =2k$ 为偶数时, $k=-k$) . 在 ${\mathbb{Z}}_{\ell }$ 上的码上, 有三个特殊的权重函数:

1. Hamming 权重, 其中每个 $a_i=1$, $i\ne 0$,

2. Lee 权重, 其中 $a_i=|i|$,

3. Euclid 权重, 其中 $a_i=|i{|}^2$.

将码 $C$ 相对于这三个权重的最小权重分别记为 $d_H$、$d_L$ 和 $d_E$. 显然, 最大 $a_r$ 值 $A$ 分别为 $1$, $k$ 和 $k^2$. 以下结果直接由定理 2.2 得出.

定理 3.1. 使用上述符号, 对于 ${\mathbb{Z}}_{\ell }$ 上的长度为 $n$ 的码 $C$, 有以下关于最小权重的界: $$d_H\le n-{\log }_{\ell }|C|+1,$$$$\lfloor \frac{d_L-1}{k}\rfloor \le n-{\log }_{\ell }|C|,$$$$\lfloor \frac{d_E-1}{k^2}\rfloor \le n-{\log }_{\ell }|C|.$$

Gray 映射 $\varphi :{\mathbb{Z}}_4\to {\mathbb{Z}}_2^2$ 定义为 $\varphi (0)=00$, $\varphi (1)=01$, $\varphi (2)=11$, $\varphi (3)=10$. 众所周知, $\varphi$ 是一个从 (${\mathbb{Z}}_4^n$, Lee 权重) 到 (${\mathbb{Z}}_2^{2n}$, Hamming 权重) 的权重保持映射 (参见 [2]) . 利用上述定理, 我们得到了某些二进制非线性码的 Singleton 界.

推论 3.2. 如果一个二进制非线性 $(2n,M,d)$-码 $B$, 其中 $M:=|B|$ 且 $d$ 是 $B$ 的最小 Hamming 权重, 是 ${\mathbb{Z}}_4$ 上长度为 $n$ 的码 $C$ 的 Gray 映射像, 那么$$\lfloor \frac{d-1}{2}\rfloor \le n-{\log }_{4}M.$$

证明. 由于 $M=|C|$ 且 $d$ 也是 $C$ 的最小 Lee 权重, 推论由定理 3.1 得出.

$\square$

参考文献

[1]	C.W. Curtis and I. Reiner, Representation Theory of Finite Groups and Associative Algebras, Interscience Publishers, New York, 1962.
[2]	A.R. Hammons, P.V. Kumar, A.R. Calderbank, N.J.A. Sloane, and P. Solé, "The ${\mathbb{Z}}_4$-linearity of Kerdock, Preparata, Goethals, and related codes," IEEE Trans. Inform. Theory 40 (1994), 301-319.
[3]	M. Klemm, "Über die Identität von MacWilliams für die Gewichtsfunktion von Codes," Arch. Math. 49 (1987), 400-406.
[4]	F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1977.
[5]	K. Shiromoto, "A new MacWilliams type identity for linear codes," Hokkaido Math. J. 25 (1996), 651-656.
[6]	T. Yoshida, "MacWilliams identities for linear codes with group action," Kumamoto Math. J. 6 (1993), 29-45.