西北师范大学数学与统计学院，甘肃 兰州

收稿日期：2021年7月28日；录用日期：2021年8月31日；发布日期：2021年9月7日

摘要

具有较低重量的线性码在数据存储系统、设计具有良好访问结构的秘密共享方案等领域有着重要的应用。基于布尔函数的Walsh谱值分布，该文利用一类具有五值Walsh谱的布尔函数构造了一类具有六重的线性码，确定了码的参数及其重量分布，并编制Magma程序验证了结论的正确性。结果表明，所构造的码为不满足A~B条件的极小线性码，且可用来设计具有良好访问结构的秘密共享方案。

关键词

布尔函数，Bent函数，Walsh变换，二元线性码

Construction of a Class of Minimal Binary Linear Code Based on Boolean Function

Jiawei Du

College of Mathematics and Statistics, Northwest Normal University, Lanzhou Gansu

Received: Jul. 28^th, 2021; accepted: Aug. 31^st, 2021; published: Sep. 7^th, 2021

ABSTRACT

Linear codes with few-weight have important applications in data storage system and designing the secret sharing scheme with good access structures. Based on the Walsh spectrum distribution of Boolean function, this paper constructs a class of Boolean functions with five-valued Walsh spectra. The type of six-weight linear code is derived from this new function, and parameters of the code such as length and dimension are determined. And magma program is used to verify the correctness of the conclusion. The results show that the new code is minimal linear code which does not satisfy the A-B condition, and it can be used to design the secret sharing scheme with good access structures.

Keywords:Boolean Function, Bent Function, Walsh Transform, Binary Linear Code

Copyright © 2021 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. 引言

布尔函数在密码学、纠错码理论 [1] 以及信号序列设计 [2] 等领域有着广泛的应用，其本质是从有限域 ${\mathbb{F}}_{2^n}$ 到 ${\mathbb{F}}_2$ 上的一个映射。布尔函数密码学性质的好坏直接关系到密码体制的安全性。一般地，可以通过布尔函数的平衡性、非线性度以及代数免疫度等相关指标来衡量其密码学性质。而布尔函数的Walsh变换，也称Walsh谱，它不仅是研究布尔函数非常有力的工具 [3] [4] [5]，而且也能反映函数的密码学性质。特别地，具有低值Walsh谱值的布尔函数在密码学、序列设计、组合设计、编码理论、强正则图等领域有着重要的应用。

具有较低重量的线性码可被应用于强正则图、鉴别代码 [6]、数据存储系统、构造具有良好访问结构的秘密共享方案 [7] 等领域，因此构造较低重量的线性码一直是编码理论中的一个重要课题。线性码的重量分布是反应其性能的一个重要参数，不仅表明了码的纠错能力还可以用来计算信息在传输过程中产生的错误概率。然而，确定线性码的长度、维数和最小距离是比较困难的，能确定重量分布的码字则更占很小的一部分。设计具有较低重量的线性码的主要方法之一是基于定义集的构造，该方法最早是由Baumert等人 [8] 提出。近年来，国内外众多学者利用该方法研究了大量线性码的重量分布，并利用A-B条件判定了码的极小性。2018年，Ding等人 [9] 给出了另一种判断极小二元码的充要条件，并构造了三类极小二元码，同时确定了这些码的重量分布。本论文利用布尔函数Walsh谱值构造了一类不满足A-B条件的极小二元线性码。具体为，首先构造了一类新的布尔函数，然后通过确定该函数的Walsh谱值分布，研究了其在极小码中的应用。

该文的组织结构如下，第二部分主要介绍了一些基础知识。第三部分首先，构造了一类新的布尔函数并确定了函数的Walsh谱值分布；然后，利用新函数构造了一类极小二元线性码。第四部分总结了全文。

2. 基础知识

在下文中，设n是一个正整数。 ${\mathbb{F}}_{2^n}$ 是含有 $2^n$ 个元素的有限域， ${\mathbb{F}}_{2^n}^{*}={\mathbb{F}}_{2^n}\backslash \left\{0\right\}$。 ${\mathbb{B}}_n$ 表示从 ${\mathbb{F}}_{2^n}$ 到 ${\mathbb{F}}_2$ 上的布尔函数集。

首先介绍一些关于线性码的基础知识。

有限域 ${\mathbb{F}}_2$ 上的一个 $\left[n,k,d\right]$ 线性码 $\mathcal{C}$ 是 ${\mathbb{F}}_2$ 上n维空间 ${\mathbb{F}}_2^n$ 的一个k维子空间，其最小Hamming距离为d， $\mathcal{C}$ 中的每一个向量称为码字。设 $A_i$ 表示码 $\mathcal{C}$ 中重量为i的码字的个数。 $1+A_{1}z+A_2{z}^2+\cdots +A_n{z}^n$ 为码 $\mathcal{C}$ 的重量计数器。序列 $\left(1,A_1,A_2,\cdots ,A_n\right)$ 称为码 $\mathcal{C}$ 的重量分布。若在 $A_1,A_2,\cdots ,A_n$ 中，使得 $A_i\ne 0\left(1\le i\le n\right)$ 的个数为t，称码 $\mathcal{C}$ 为t重码。 $\mathcal{C}$ 中码字 $c=\left(c_0,c_1,\cdots ,c_{n-1}\right)$ 的支撑集，定义为

$Suppt\left(c\right)=\left\{0\le i\le n-1:c_i\ne 0\right\}.$

若对向量 $u,v$，有 $Suppt\left(v\right)\subseteq Suppt\left(u\right)$，则称 $u$ 覆盖 $v$。若码 $\mathcal{C}$ 的一个非零码字 $c$ 只覆盖它的纯量倍数，则称 $c$ 是一个极小向量。若 $\mathcal{C}$ 中的任意码字均是极小向量，则称线性码 $\mathcal{C}$ 是极小线性码。

下面介绍有关有限域及布尔函数的相关知识。

设整数k和n满足 $k|n$，迹函数 ${\text{Tr}}_k^n(\cdot )$ 表示从 ${\mathbb{F}}_{2^n}$ 到 ${\mathbb{F}}_{2^k}$ 上的映射，定义为 [10]

${\text{Tr}}_k^n\left(x\right)=x+x^{2^k}+\cdots +x^{2^{n-k}}$，其中 $x\in {\mathbb{F}}_{2^n}$。

特别地，当 $k=1$ 时， ${\text{Tr}}_1^n(\cdot )={\displaystyle \underset{i=0}{\overset{n-1}{\sum }}{x}^{2^i}}$ 称为绝对迹函数。

设 $f\in {\mathbb{B}}_n$，f的Walsh变换是一个实值函数 $\hat{f}:{\mathbb{F}}_{2^n}\to \mathbb{Z}$，对任意的 $a\in {\mathbb{F}}_{2^n}$，其定义为

$\hat{f}\left(a\right)={\displaystyle \underset{x\in {\mathbb{F}}_{2^n}}{\sum }{\left(-1\right)}^{f\left(x\right)+{\text{Tr}}_1^n\left(ax\right)}}.$ (1)

若函数f的Walsh谱值仅有t个不同的取值，则称函数f具有t-值Walsh谱。显然，若令 $N_i=\left|\left\{\alpha \in {\mathbb{F}}_{2^n}:\hat{f}\left(a\right)=v_i\right\}\right|$，其中 $\alpha \in {\mathbb{F}}_{2^n}$，$1\le i\le t$。由Walsh变换的性质，有如下方程组：

$\{\begin{array}{l}{\displaystyle \underset{i=1}{\overset{t}{\sum }}{N}_i=2^n,}\\ {\displaystyle \underset{i=1}{\overset{t}{\sum }}{N}_i{v}_i=2^n{\left(-1\right)}^{f\left(0\right)},}\\ {\displaystyle \underset{i=1}{\overset{t}{\sum }}{N}_i{v}_i^2=2^{2n}.}\end{array}$ (2)

定义1 [3] 设 $f\in {\mathbb{B}}_n$，$n=2m$，若对任意的 $\alpha \in {\mathbb{F}}_{2^m}$，都有 $\hat{f}\left(\alpha \right)=\pm 2^m$，则称 $f\left(x\right)$ 为Bent函数。

$f\left(x\right)$ 是Bent函数，则f的对偶函数 $\tilde{f}$ 也是Bent函数且与f的Walsh变换有如下关系

$\hat{f}\left(\alpha \right)=2^m{\left(-1\right)}^{\tilde{f}\left(\alpha \right)}.$

引理1 [11] 设 $n=2m$ 且 $\lambda \in {\mathbb{F}}_{2^m}$，则 $f\left(x\right)={\mathrm{Tr}}_1^m\left(\lambda x^{2^m+1}\right)$ 是一个Bent函数。显然，对任意的 $a\in {\mathbb{F}}_{2^n}$，$f\left(x\right)$ 在a点处的Walsh变换为

$\hat{f}\left(a\right)=2^m{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left({\lambda }^{-1}{a}^{2^m+1}\right)+1}.$

3. 主要结论及证明

下文中总假设 $n=2m>4$。

3.1. 新布尔函数的构造及其谱值分析

首先构造布尔函数如下：

$f_{\lambda ,\gamma }\left(x\right)={\mathrm{Tr}}_1^m\left(\lambda x^{2^m+1}\right){\mathrm{Tr}}_1^m\left(\gamma {\left(x+1\right)}^{2^m+1}\right)\in {\mathbb{B}}_n,$ (3)

其中 $\lambda ,\gamma \in F_{2^m}^{*}$，且 $\lambda \ne \gamma$。

下面我们计算该函数的Walsh谱值及其分布。先给出一个重要引理。

引理2 设函数f如式(3)定义，则对于任意的 $a\in {\mathbb{F}}_{2^n}$，$f\left(x\right)$ 的Walsh变换为

$\hat{f}\left(a\right)=\{\begin{array}{l}{2}^{n-1}-2^{m-1}{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left({\left(\gamma +\lambda \right)}^{-1}{\gamma }^{2^m+1}\right)+{\mathrm{Tr}}_1^m\left(\gamma \right)},a=0,\\ -2^{m-1}\left(2{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\gamma \right)}-{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left({\lambda }^{-1}{\gamma }^{2^m+1}\right)}\right),a=\gamma ,\\ -2^{m-1}\left({\left(-1\right)}^{{\mathrm{Tr}}_1^m\left({\gamma }^{-1}{a}^{2^m+1}\right)+{\mathrm{Tr}}_1^n\left(a\right)}-{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left({\lambda }^{-1}{a}^{2^m+1}\right)}+{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left({\left(\gamma +\lambda \right)}^{-1}{\gamma }^{2^m+1}\right)+{\mathrm{Tr}}_1^m\left({\left(\gamma +\lambda \right)}^{-1}{a}^{2^m+1}\right)+{\mathrm{Tr}}_1^m\left(\gamma \right)}\right),其它\text{.}\end{array}$ (4)

证明 对任意的 $a\in {\mathbb{F}}_{2^n}$，由式(1)可得， $f\left(x\right)$ 的Walsh变换为

$\begin{array}{c}\hat{f}\left(a\right)={\displaystyle \underset{x\in {\mathbb{F}}_{2^n}}{\sum }{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\lambda x^{2^m+1}\right){\mathrm{Tr}}_1^m\left(\gamma {\left(x+1\right)}^{2^m+1}\right)+{\mathrm{Tr}}_1^n\left(ax\right)}}\\ ={\displaystyle \underset{\begin{array}{c}x\in {\mathbb{F}}_{2^n}\\ {\text{Tr}}_1^m\left({\mathrm{Tr}}_1^m\left(\gamma {\left(x+1\right)}^{2^m+1}\right)\right)=0\end{array}}{\sum }{\left(-1\right)}^{{\mathrm{Tr}}_1^n\left(ax\right)}}+{\displaystyle \underset{\begin{array}{c}x\in {\mathbb{F}}_{2^n}\\ {\text{Tr}}_1^m\left({\mathrm{Tr}}_1^m\left(\gamma {\left(x+1\right)}^{2^m+1}\right)\right)=1\end{array}}{\sum }{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\lambda x^{2^m+1}\right){\mathrm{Tr}}_1^m\left(\gamma {\left(x+1\right)}^{2^m+1}\right)+{\mathrm{Tr}}_1^n\left(ax\right)}}\\ =\frac{1}{2}({\displaystyle \underset{x\in {\mathbb{F}}_{2^n}}{\sum }\left({\left(-1\right)}^{{\mathrm{Tr}}_1^n\left(ax\right)}+{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\gamma {\left(x+1\right)}^{2^m+1}\right)+{\mathrm{Tr}}_1^n\left(ax\right)}\right)}\\ -{\displaystyle \underset{x\in {\mathbb{F}}_{2^n}}{\sum }\left({\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\lambda x^{2^m+1}\right)}\cdot {\left(-1\right)}^{{\mathrm{Tr}}_1^n\left(ax\right)}-{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\gamma \left(x^{2^m+1}+x^{2^m}+x+1\right)\right)\text{+}{\mathrm{Tr}}_1^m\left(\lambda x^{2^m+1}\right)+{\mathrm{Tr}}_1^n\left(ax\right)}\right)})\\ =\frac{1}{2}{\displaystyle \underset{x\in {\mathbb{F}}_{2^n}}{\sum }{\left(-1\right)}^{{\mathrm{Tr}}_1^n\left(ax\right)}+\frac{1}{2}{\displaystyle \underset{x\in {\mathbb{F}}_{2^n}}{\sum }{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\gamma x^{2^m+1}\right)+{\mathrm{Tr}}_1^n\left(ax\right)+{\mathrm{Tr}}_1^n\left(a\right)}}}\\ -\frac{1}{2}{\displaystyle \underset{x\in {\mathbb{F}}_{2^n}}{\sum }{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\lambda x^{2^m+1}\right)+{\mathrm{Tr}}_1^n\left(ax\right)}}+\frac{1}{2}{\displaystyle \underset{x\in {\mathbb{F}}_{2^n}}{\sum }{\left(-1\right)}^{{\mathrm{Tr}}_1^m\left(\left(\gamma +\lambda \right)x^{2^m+1}\right)+{\mathrm{Tr}}_1^n\left(\left(\gamma +a\right)x\right)+{\mathrm{Tr}}_1^m(\; \gamma \; )}}\end{array}$

则由引理1和函数 ${\mathrm{Tr}}_1^m\left(\lambda x^{2^m+1}\right)$ 的Bent性，对a的取值进行分类，经简单计算可得结果。

证毕。 □

下文中：令 $A={\mathrm{Tr}}_1^m\left({\left(\gamma +\lambda \right)}^{-1}{\gamma }^{2^m+1}\right)$，$B={\text{Tr}}_1^m\left(\gamma \right)$，$C={\mathrm{Tr}}_1^m\left({\lambda }^{-1}{\gamma }^{2^m+1}\right)$，$D={\mathrm{Tr}}_1^m\left(\left(\lambda +{\gamma }^{-1}\right)a^{2^m+1}\right)$，$E={\mathrm{Tr}}_1^m\left({\gamma }^{-1}{a}^{2^m+1}\right)$，$F={\text{Tr}}_1^n\left(a\right)$，$G={\mathrm{Tr}}_1^m\left({\lambda }^{-1}{a}^{2^m+1}\right)$。则有

$\hat{f}\left(0\right)=2^{n-1}-2^{m-1}{\left(-1\right)}^{A+B}.$

下面假设 $A=B$。所以，

$\hat{f}\left(0\right)=2^{n-1}-2^{m-1}.$

$\begin{array}{c}\hat{f}\left(\gamma \right)=-2^{m-1}\left(2{\left(-1\right)}^B-{\left(-1\right)}^C\right)\\ =\{\begin{array}{l}-2^{m-1},\left(B,C\right)=\left(0,0\right),\\ -3\cdot 2^{m-1},\left(B,C\right)=\left(0,1\right),\\ 3\cdot 2^{m-1},\left(B,C\right)=\left(1,0\right),\\ 2^{m-1},\left(B,C\right)=\left(1,1\right).\end{array}\end{array}$

当 $a\in {\mathbb{F}}_{2^n}\backslash \left\{0,\gamma \right\}$ 时，因为 ${\left(\lambda +\gamma \right)}^{-1}={\lambda }^{-1}+{\gamma }^{-1}$，所以有 $E+G=D$，因而仅存在以下八种情形。

$\begin{array}{c}\hat{f}\left(a\right)=-2^{m-1}\left({\left(-1\right)}^{E+F}-{\left(-1\right)}^G+{\left(-1\right)}^D\right)\\ =\{\begin{array}{l}-2^{m-1},若\left(E+F,G,D\right)\in \left\{\left(0,0,0\right),\left(0,1,1\right),\left(1,1,0\right)\right\},\\ 2^{m-1},若\left(E+F,G,D\right)\in \left\{\left(1,0,0\right),\left(0,0,1\right),\left(1,1,1\right)\right\},\\ 3\cdot 2^{m-1},若\left(E+F,G,D\right)\in \left\{\left(1,0,1\right)\right\},\\ -3\cdot 2^{m-1},若\left(E+F,G,D\right)\in \left\{\left(0,1,0\right)\right\}.\end{array}\end{array}$

定理1 符号含义与引理2相同。则当 ${\left(\lambda +\gamma \right)}^{-1}={\lambda }^{-1}+{\gamma }^{-1}$ 且 $A=B=C=0$ 时，式(3)定义的函数 $f\left(x\right)$ 的Walsh谱值分布为

$\hat{f}\left(a\right)=\{\begin{array}{c}{2}^{n-1}-2^{m-1},出现1次,\\ -2^{m-1},出现3\cdot 2^{n-3}-2^{m-2}次,\\ 3\cdot 2^{m-1},出现2^{n-3}+2^{m-2}次,\\ 2^{m-1},出现3\cdot 2^{n-3}次,\\ -3\cdot 2^{m-1},出现2^{n-3}次.\end{array}$

证明 显然，由定理1之前的讨论可知，当 $A=B=C=0$ 时，对 $a\in {\mathbb{F}}_{2^n}$，$f\left(x\right)$ 的Walsh变换为

$\hat{f}\left(a\right)\in \left\{2^{n-1}-2^{m-1},-2^{m-1},3\cdot 2^{m-1},2^{m-1},-3\cdot 2^{m-1}\right\}.$

当 $\hat{f}\left(a\right)=3\cdot 2^{m-1}$ 时，此时有 $\left(E,F,G,D\right)=\left(1,0,0,1\right)$，又因为 ${\left(\lambda +\gamma \right)}^{-1}={\lambda }^{-1}+{\gamma }^{-1}$，则 ${\mathbb{F}}_{2^n}$ 中满足此条件的元素a的个数 $S_a$ 为

$\begin{array}{c}{S}_a=\frac{1}{2^4}{\displaystyle \underset{a\in {\mathbb{F}}_{2^n}}{\sum }\left(\left(1-{\left(-1\right)}^E\right)\left(1+{\left(-1\right)}^F\right)\left(1+{\left(-1\right)}^G\right)\left(1-{\left(-1\right)}^D\right)\right)}\\ =\frac{1}{2^4}(2^n+2^m-2^m+2^m{\left(-1\right)}^{{\text{Tr}}_1^m\left({\left({\lambda }^{-1}+{\gamma }^{-1}\right)}^{-1}\right)}+2^m-2^m{\left(-1\right)}^{{\text{Tr}}_1^m\left(\lambda \right)}+2^m\\ +2^m{\left(-1\right)}^{{\text{Tr}}_1^m\left(\gamma \right)}+2^m+2^n-2^m{\left(-1\right)}^{{\text{Tr}}_1^m\left(\lambda \right)}+2^m{\left(-1\right)}^{{\text{Tr}}_1^m\left({\left({\lambda }^{-1}+{\gamma }^{-1}\right)}^{-1}\right)})\\ =2^{n-3}+3\cdot 2^{m-4}+2^{m-3}{\left(-1\right)}^{{\text{Tr}}_1^m\left({\left({\lambda }^{-1}+{\gamma }^{-1}\right)}^{-1}\right)}-2^{m-3}{\left(-1\right)}^{{\text{Tr}}_1^m\left(\lambda \right)}+2^{m-4}{\left(-1\right)}^{{\text{Tr}}_1^m\left(\gamma \right)}\\ =2^{n-3}+3\cdot 2^{m-4}+2^{m-3}{\left(-1\right)}^{{\text{Tr}}_1^m\left(\gamma \right)+{\text{Tr}}_1^m\left(\lambda \right)}-2^{m-3}{\left(-1\right)}^{{\text{Tr}}_1^m\left(\lambda \right)}+2^{m-4}{\left(-1\right)}^{{\text{Tr}}_1^m\left(\gamma \right)}\\ =2^{n-3}+2^{m-2}\end{array}$ (6)

下面记

$\begin{array}{l}{N}_1=\left|\left\{a\in {\mathbb{F}}_{2^n}:\hat{f}\left(a\right)=-2^{m-1}\right\}\right|,\\ N_2=\left|\left\{a\in {\mathbb{F}}_{2^n}:\hat{f}\left(a\right)=2^{m-1}\right\}\right|,\\ N_3=\left|\left\{a\in {\mathbb{F}}_{2^n}:\hat{f}\left(a\right)=-3\cdot 2^{m-1}\right\}\right|.\end{array}$

因为 $f\left(0\right)=0$，所以由式(2)和式(6)可得

$\{\begin{array}{l}1+2^{n-3}+2^{m-2}+N_1+N_2+N_3=2^n,\\ 2^{n-1}-2^{m-1}+3\cdot 2^{m-1}\left(2^{n-3}+2^{m-2}\right)-2^{m-1}{N}_1+2^{m-1}{N}_2-3\cdot 2^{m-1}{N}_3=2^n,\\ {\left(2^{n-1}-2^{m-1}\right)}^2+{\left(3\cdot 2^{m-1}\right)}^2\left(2^{n-3}+2^{m-2}\right)+{\left(2^{m-1}\right)}^2\left(N_1+N_2\right)+{\left(-3\cdot 2^{m-1}\right)}^2{N}_3=2^{2n}.\end{array}$

解上述方程组可得

$N_1=3\cdot 2^{n-3}-2^{m-2}-1,N_2=3\cdot 2^{n-3},N_3=2^{n-3}.$

证毕。 □

3.2. 构造一类极小线性码

在这一小节中，我们利用新函数的Walsh谱值构造极小线性码。

设 $g\left(x\right)\in {\mathbb{B}}_n$ 满足 $g\left(0\right)=0$，且对所有的 $v\in {\mathbb{F}}_{2^n}$，有 $g\left(x\right)\ne v\cdot x$，则定义 ${\mathbb{F}}_2$ 上的线性码 ${\mathcal{C}}_g$ 如下：

${\mathcal{C}}_g=\left\{{\left(ug\left(x\right)+\mathrm{Tr}\left(v\cdot x\right)\right)}_{x\in {\mathbb{F}}_{2^n}^{*}}:u\in {\mathbb{F}}_2,v\in {\mathbb{F}}_{2^n}\right\}$ (7)

引理3 [9] 设码 ${\mathcal{C}}_g$ 由式(8)定义，则 ${\mathcal{C}}_g$ 的长度为 $2^n-1$，维数为 $n+1$，且其重量分布可由下述多重集给出

$\left\{\left\{\frac{2^n-\hat{g}\left(w\right)}{2}:w\in {\mathbb{F}}_{2^n}\right\}\cup \left\{2^{n-1}:w\in {\mathbb{F}}_{2^n}^{*}\right\}\cup \left\{0\right\}\right\}.$

更进一步地， ${\mathcal{C}}_g$ 是极小码当且仅当

$\hat{f}\left(h\right)\pm \hat{f}\left(l\right)\ne 2^n$，其中 $h,l\in {\mathbb{F}}_{2^n}$，$h\ne l$。

引理4 [12] (A-B条件)令 $w_{\min }$ 与 $w_{\max }$ 分别表示码 $\mathcal{C}$ 的极小与极大Hamming重量，若 $w_{\min }/w_{\max }>1/2$，则 $\mathcal{C}$ 为 ${\mathbb{F}}_2$ 上的极小码。该条件为判断线性码为极小码的充分条件。

定理2 设符号含义如上，当 ${\left(\lambda +r\right)}^{-1}={\lambda }^{-1}+r^{-1}$ 且 $A=B=C=0$ 时，则由式(3)定义的函数f构造的线性码 ${\mathcal{C}}_f$ 为 $\left[2^n-1,n+1,2^{n-2}+2^{m-2}\right]$ 极小码，且其重量分布如表1所示。

表1. ${\mathcal{C}}_f$ 的重量分布

证明 当 ${\left(\lambda +r\right)}^{-1}={\lambda }^{-1}+r^{-1}$ 且 $A=B=C=0$ 时，由定理1中函数f的Walsh谱值分布和引理3中的结论可得， ${\mathcal{C}}_f$ 的重量分布如表1所示。

显然，由表1可知， $w_{\min }/w_{\max }<1/2$，不满足A-B条件。而又由函数f的Walsh谱值分布可知，对任意的 $h\ne l\in {\mathbb{F}}_{2^n}$，有 $\hat{f}\left(h\right)\pm \hat{f}\left(l\right)\ne 2^n$ 成立，即满足引理3中关于极小码的判定条件，所以 ${\mathcal{C}}_f$ 为最小码。

证毕。 □

例：记 $n=8$，$m=4$，$\alpha$ 是 ${\mathbb{F}}_{2^8}$ 的本原元，且满足 ${\alpha }^8+{\alpha }^4+{\alpha }^3+{\alpha }^2+1=0$。设 $\lambda ={\alpha }^{170}$，$\gamma ={\alpha }^{85}$，则我们有 ${\left(\lambda +\gamma \right)}^{-1}={\lambda }^{-1}+{\gamma }^{-1}$，且

${\mathrm{Tr}}_1^m\left({\left(\gamma +\lambda \right)}^{-1}{\gamma }^{2^m+1}\right)={\text{Tr}}_1^m\left(\gamma \right)={\mathrm{Tr}}_1^m\left({\lambda }^{-1}{\gamma }^{2^m+1}\right)=0,$

则由Magma程序可知，码 ${\mathcal{C}}_f$ 的参数为 $\left[255,9,68\right]$，其重量计数器为

$1+z^{68}+36z^{116}+96z^{124}+255z^{128}+92z^{132}+32z^{140},$

与定理2的结论一致。

注记：当 $A,B,C$ 取其他值时，所构造函数f的Walsh变换的值与 $A=B=C=0$ 时的相同，只是出现的频数不同，因此对所构造线性码的重量与定理2的一致，但出现的频数不同。

4. 结束语

该文首先构造了一类至多具有五值Walsh谱的布尔函数，并且确定了其谱值分布。其次，利用函数的谱值分布，研究了其在线性码中的应用。并设计Magma程序举例验证了结论的正确性。结论表明，该函数所构造的一类码为不满足A-B条件的六重极小线性码，且可用来设计具有良好访问结构的秘密共享方案。

文章引用

杜佳玮. 一类基于布尔函数的极小线性码的构造
Construction of a Class of Minimal Binary Linear Code Based on Boolean Function[J]. 理论数学, 2021, 11(09): 1623-1629. https://doi.org/10.12677/PM.2021.119179

参考文献