Source-linked AI summary
A Construction of Binary Linear Codes from Boolean Functions
Cunsheng Ding
TL;DR
Binary linear codes from Boolean functions have been extensively studied, but determining their parameters can remain difficult for general defining sets and function families. This paper surveys recent constructions, especially codes with few weights, and proposes open problems, including conjectures about difference sets, o-polynomials, and corresponding codes. The survey presents many one- through four-weight codes, some optimal or nearly optimal, while several parameter claims remain conjectural or difficult to determine generally.
Problem
Determining code parameters is difficult for general defining sets and function families, motivating a survey of recent constructions and open problems.
Method
The paper surveys binary linear codes from Boolean functions and functions on GF(2^m) obtained from the second generic construction, focusing on codes with at most five weights.
Results
The survey presents many one-weight, two-weight, three-weight, and four-weight codes, including some with optimal or almost optimal parameters.
Takeaways & Limitations
The presented codes may have applications in secret sharing and authentication codes, while the open problems invite further research.
Takeaways & Limitations
For general difference sets and some function families, determining the parameters of the resulting binary linear codes may be difficult, and several claims remain conjectural.
Abstract
from arXiv · showhide
Boolean functions have important applications in cryptography and coding theory. Two famous classes of binary codes derived from Boolean functions are the Reed-Muller codes and Kerdock codes. In the past two decades, a lot of progress on the study of applications of Boolean functions in coding theory has been made. Two generic constructions of binary linear codes with Boolean functions have been well investigated in the literature. The objective of this paper is twofold. The first is to provide a survey on recent results, and the other is to propose open problems on one of the two generic constructions of binary linear codes with Boolean functions. These open problems are expected to stimulate further research on binary linear codes from Boolean functions.
1. Introduction
The paper surveys binary linear codes constructed from Boolean functions and proposes open problems for one generic construction. Boolean functions support applications in cryptography and coding theory, including Reed-Muller and Kerdock codes.
- Boolean functions are important building blocks for certain stream ciphers and can be used to construct binary codes.
- Reed-Muller and Kerdock codes are two famous families of binary codes derived from Boolean functions.
- The paper surveys recent development on one of two well-investigated generic constructions of binary linear codes from Boolean functions.
- The paper proposes open problems on generic constructions of binary linear codes with Boolean functions.
2. Mathematical foundations
This section establishes foundational definitions for finite-field functions, Boolean functions, additive characters, difference sets, and specialized polynomials used in binary-code constructions.
- Difference sets: A (v, k, λ) difference set has constant difference count λ for every nonzero group element.Difference sets can be used to construct linear codes, and some surveyed codes are defined by them.
- Finite-field polynomials: Additive characters are nonzero complex-valued functions satisfying χ(x+y)=χ(x)χ(y), with χ1 designated as the canonical additive character.Every additive character over GF(q) can be expressed as χ_b(x)=χ1(bx).
- Finite-field polynomials: Dickson polynomials of order 5 provide defining functions for some linear codes presented later.The passage identifies Dickson permutation polynomials over GF(2^m) as the relevant special case.
- Finite-field polynomials: An e-to-1 polynomial maps each field value to either exactly e preimages or none, with e dividing q; permutation polynomials are 1-to-1.The survey uses e-to-1 polynomials over GF(2^m) in binary linear-code constructions.
- Boolean functions: A Boolean function maps GF(2^m) or GF(2)^m to GF(2), while linearity requires preservation of addition and affinity allows the function or its inverse to be linear.The support and Walsh spectrum provide associated representations of Boolean functions.
- Boolean functions: The support mapping f ↦ D_f is a one-to-one correspondence between Boolean functions on GF(2^m) and its power set.This correspondence connects Boolean-function descriptions with subset-based code constructions.
3. The first generic construction of linear codes from functions
The first generic construction defines linear codes from polynomials over finite fields, producing codes of length q or q−1 with dimension at most 2m. Its duals have correspondingly large dimensions, and the construction supports known Boolean-function characterizations.
- Code parameters: The polynomial-based code C(f) has length q, dimension at most 2m, and dual dimension at least q−2m.The dimension equals 2m in many cases.
- Code parameters: The variant C*(f), requiring f(0)=0, has length q−1, dimension at most 2m, and dual dimension at least q−1−2m.Its dimension equals 2m in many cases.
- Scope and connections: The construction has a long history and, when q=2, characterizes APN monomials, almost bent functions, and semibent functions through Delsarte’s Theorem.The paper states that it does not investigate this construction further.
4. The second generic construction of linear codes from functions
The second generic construction defines codes from arbitrary subsets D of GF(q), with code length determined by |D| and dimension at most m. Properly chosen defining sets can yield few-weight or good codes, while the construction also differs from the first in its flexible length and usually smaller dimension.
- Definition and parameters: The construction defines a linear code C_D over GF(p) from a subset D of GF(q), called its defining set, with length |D| and dimension at most m.The trace function maps code coordinates into GF(p).
- Defining-set design: Choosing D appropriately can produce known few-weight codes and may give good or optimal parameters; poor choices can produce bad parameters.The construction is generic because many code classes arise from different defining sets.
- Weight analysis: The code weights are connected to additive-character sums over scalar multiples of D.The canonical additive character and the sets aD are used in the associated expression.
- Comparison with the first construction: Unlike the first construction, this construction permits any length from 1 to q, depending on D.The first construction has length q or q−1.
- Comparison with the first construction: Its dimension is at most m and usually m, whereas the first construction usually has dimension 2m.This gives the second construction a generally smaller dimension scale.
5. Binary codes from the preimage f −1(b) of Boolean functions f
The construction maps Boolean-function supports to binary linear codes whose parameters and weight distributions are determined through Walsh spectra. Bent, semibent, quadratic, and other Boolean functions yield codes with structured few-weight distributions under stated conditions.
- General construction: The code C_Df has length n_f and, when 2n_f + f̂(w) ≠ 0 for every nonzero w, dimension m and a Walsh-spectrum-derived weight distribution.Theorem 1 connects the nonvanishing condition to the code parameters and weight distribution.
- General construction: Theorem 2 extends the construction by allowing repeated spectral values, giving dimension m−log2 e when zero has multiplicity e.The generalized result accounts for multiplicities in the relevant multiset.
- Bent functions: Bent functions are equivalent to two-weight codes C_Df for even m≥4, with parameters [n_f, m, (n_f−2^(m−2)/2)/2].The equivalence holds for Boolean functions satisfying f(0)=0.
- Semibent functions: Semibent functions are equivalent to three-weight codes C_Df for odd m, with parameters [n_f, m, (n_f−2^((m−1)/2))/2].The result again assumes f(0)=0 and characterizes the code through the Boolean-function class.
- Other Boolean-function classes: Almost bent functions and selected quadratic Boolean functions also produce three-weight or explicitly parameterized codes through their Walsh spectra.An almost bent function g with f=Tr(g) gives a three-weight code, while quadratic functions yield code parameters and weight distributions from spectral tables.
- Further constructions: Further spectral families produce codes ranging from two to five weights, with lengths and dimensions depending on exponents, congruence conditions, and function parameters.The listed cases include four-valued spectra, five-weight codes, and two-weight codes, alongside relative difference-set constructions with at most four weights.
6. Binary codes from the images of certain functions on GF(2m)
The image-based construction uses value sets D(f) of functions over GF(2^m), but determining their sizes and code weight distributions is generally difficult. Characteristic functions show that this construction is equivalent to the support-based Boolean-function construction.
- Image-set construction: For a function f: GF(2^m)→GF(2^m), the construction uses its image D(f) and optionally removes zero to form D(f)*.The two resulting codes coincide when zero is absent; otherwise removing zero shortens the code by one without changing its weight distribution.
- Image-set construction: Determining the image-set code length n_f and weight distribution is generally difficult, although special cases have settled parameters.The difficulty concerns both the size of the image and the resulting code distribution.
- Equivalence: The image-set construction is equivalent to the support construction because D(f) is the support of its characteristic Boolean function.Thus, codes defined from images can be analyzed through Boolean-function supports.
6.1. The codes CD(f) from o-polynomials on GF(2m)
This section surveys o-polynomials and the binary codes constructed from them, including established families, parameterized code results, and conjectured extensions. The code properties can vary substantially with the chosen o-polynomial.
- O-polynomials and their binary codes CD(fu): An o-polynomial is a permutation polynomial f on GF(2^m) with f(0)=0 whose perturbations f_u(x)=f(x)+ux are 2-to-1 for every nonzero u.This characterization underlies the construction of the codes C_D(f_u).
- O-polynomials and their binary codes CD(fu): For every nonzero u, the code C_D(f_u) has length 2^m−1, while its dimension, minimum weight, and weight distribution are not determined by the o-polynomial property alone.The dimension usually equals m but may be smaller than m.
- Translation o-polynomials: Translation o-polynomials f(x)=x^(2^h) with gcd(h,m)=1 yield one-weight codes with parameters [2^m−1, m−1, 2^(m−2)].These codes have the same parameters as a subcode of the first-order binary Reed–Muller code.
- Segre and Glynn o-polynomials: For odd m, Segre and Glynn families provide explicit o-polynomials, while the extended Glynn family is conjectured to produce five-weight codes when m≥9.For m∈{5,7}, the conjecture instead states that the codes have the weight distribution of Table 11.
- Subiaco o-polynomials: Subiaco o-polynomials yield codes with many weights and smaller minimum weights than codes from other o-polynomials described earlier.The reported experimental behavior indicates that code quality depends strongly on the specific o-polynomial.
6.2. Binary codes
The section surveys binary codes derived from APN and related functions, emphasizing their weight counts, dimensions, and parameter patterns. Several cases yield few-weight codes, while other APN monomials have many weights or difficult-to-determine distributions.
- For F(x)=x^(2^(m−1)/2+3) with odd m, CD(f) is conjectured to have three weights for m∈{5,7} and five weights for m≥9.
- For F(x)=x^(2^(2h)−2^h+1) with gcd(h,m)=1, h≥2, and odd m, CD(f) has three or five weights, with a three-weight case when h=3 under stated conditions.
- For F(x)=x^(2^h+1) with gcd(h,m)=1, CD(f) is a one-weight code with parameters [2^m−1, m−1, 2^(m−2)].
- Determining the weight distributions for three listed APN monomial classes is described as extremely difficult, despite their code lengths and dimensions being known.
6.3. Binary linear codes from some trinomials
This section presents conjectured difference sets and the binary linear codes obtained from them. The proposed constructions include one-, three-, and four-weight codes, but determining their parameters can be difficult in general.
- The section notes that many cyclic difference sets produce natural binary linear codes, but their code parameters and weight distributions may be difficult to determine.
- Conjecture 37 assigns the codes from specified odd-m difference sets parameters [2^m−1, m, 2^(m−2)−2^((m−3)/2)] and a conjectured weight enumerator.
- Conjecture 38 proposes parameters [2^m−1, m, 2^(m−2)−2^((m−2)/2)] and an explicit three-term weight enumerator for a polynomial with m≡2 mod 4 and m≥6.
- Conjecture 39 proposes a binary linear code with parameters [2^m−1, m, 2^(m−2)−2^((m−2)/2)] and the weight distribution of Table 12.
- Conjecture 41 predicts that codes from the difference sets in Conjecture 40 have parameters [2^m−1−1, m−1, 2^(m−2)] and are one-weight codes.
7. An expansion of the binary codes
The paper expands binary codes by adjoining the all-one vector and analyzes the resulting parameters and weight distributions. This produces codes with increased dimension and examples that are optimal or almost optimal.
- Adding the all-one vector gives a binary linear code with the same length, while its dimension is one greater in most presented cases.
- The weight distribution of the expanded code can often be deduced from that of the original code.
- For the construction in Theorem 42, the expanded code has parameters [2^m−1, m+1] and the weight distribution of Table 13.
- When m=5, the expanded code has parameters and is optimal; when m=7, it has parameters and is almost optimal.
8. Concluding remarks
The paper surveys binary linear codes from Boolean functions under the second generic construction, emphasizing codes with at most five weights and presenting open conjectures. Its scope is deliberately limited to that construction rather than all such codes.
- The survey focuses on binary linear codes from Boolean functions and functions on GF(2^m) obtained through the second generic construction.
- It presents many one-, two-, three-, and four-weight codes, including examples that are optimal or almost optimal.
- The paper presents open conjectures on difference sets, o-polynomials, and corresponding binary codes, many of which were confirmed for sufficiently many m by Magma.
- The survey is not comprehensive: it covers binary linear codes from Boolean functions only through the second generic construction described in Section 4.