Minimality conditions clarified for binary codes from weight layers and graph cuts
Minimality of Binary Codes From Weight Layers and Graph Cut Spaces
Information Theory
Summary
The paper studies when certain binary codes have a property called minimality, which is important in secret-sharing and understanding code structure. The authors fully describe when codes made from specific weight groups are minimal and explore other related code properties. They connect minimality in codes from graph cuts to a simple condition about the graph’s shape. This work sharpens the understanding of these code families and their key characteristics.
What this means in practice
- •For cryptography developers: Design secret-sharing schemes that require minimal binary codes with fully classified minimality conditions for better security guarantees.
- •For coding theory engineers: Optimize code constructions by applying precise minimality and dual code criteria to improve error detection and correction properties.
Authors
Xianhong Xie, Mengni Wang, Tingting Wu
Abstract
Minimal binary linear codes play an important role in secret-sharing schemes and in the structural study of linear codes. We study the minimality of three classes of known constructions: codes from a single complete Hamming-weight layer, codes from arbitrary unions of such layers and graph cut-space codes. For the previously studied single-layer codes C, we give a complete minimality classification: C is minimal if and only if t is even. For t = 4, we determine the minimum and maximum weights, and show that the family strictly violates the binary Ashikhmin Barg sufficient condition for every k. We also calculate the minimum distance of the dual code. For arbitrary unions of complete Hamming-weight layers, we obtain an if-and-only-if classification of minimality and uniform criteria for evenness, self-orthogonality, the doubly even property and hull dimension. We further analyze the family for odd k. Finally, using the classical bond characterization of cuts, we translate minimality of graph cut space codes into a graph-theoretic condition: a nonempty simple graph has a minimal cut code precisely when it has one edge-containing component and that component is complete. We also give a graph-function realization of the known binary tetrahedron code and explicitly identify the resulting code equivalence.