In the deletion channel, an important problem is to determine the number of subsequences derived from a string $U$ of length $n$ when subjected to $t$ deletions. It is well-known that the number of subsequences in the setting exhibits a strong dependence on the number of runs in the string $U$, where a run is defined as a maximal substring of identical characters. In this paper we study the number of subsequences of a non-binary string in this scenario, and propose some improved bounds on the number of subsequences of $r$-run non-binary strings. Specifically, we characterize a family of $r$-run non-binary strings with the maximum number of subsequences under any $t$ deletions, and show that this number can be computed in polynomial time.

Maximum distance separable (MDS) codes are widely used in distributed storage, but naively repairing a single failure in an $(n,k)$ MDS code requires downloading the full contents of $k$ surviving nodes. Minimum storage regenerating (MSR) codes, introduced by Dimakis et al., minimize repair bandwidth while preserving the MDS property by contacting $d>k$ helper nodes and downloading only a fraction of each helper. For scalar MDS codes, Guruswami and Wootters established a linear repair framework, and Tamo, Ye, and Barg subsequently gave the first explicit Reed-Solomon (RS) codes achieving the MSR point. Their construction yields RS-MSR codes with subpacketization $\ell=s\prod_{i=1}^n p_i$, where $s=d+1-k$ and the distinct primes $p_i$ satisfy $p_i\equiv 1\pmod{s}$. In this paper, we show that this congruence condition is not intrinsic to the RS repair problem. We develop a basis-transformation approach to the construction of repair-enabling subspaces. The approach consists of three deterministic operations -- Euclidean Square Partition, Transposition, and Column Aggregation -- which construct the required repair-enabling subspaces directly from the standard monomial basis of the repair field. Consequently, we obtain RS-MSR codes with subpacketization $\ell=s\prod_{i=1}^n p_i$ for arbitrary distinct primes $p_i>s$. For fixed $s$, this improves the subpacketization of the Tamo--Ye--Barg construction by a factor asymptotic to $φ(s)^{n+\mathrm{o}(n)}$, where $φ(\cdot)$ denotes Euler's totient function.

Levenshtein first introduced the sequence reconstruction problem in $2001$. In the realm of combinatorics, the sequence reconstruction problem is equivalent to determining the value of $N(n,d,t)$, which represents the maximum size of the intersection of two metric balls of radius $t$, given that the distance between their centers is at least $d$ and the sequence length is $n$. In this paper, We present a lower bound on $N(n,3,t)$ for $n\geq \max\{13,t+8\}$ and $t \geq 4$. For $t=4$, we prove that this lower bound is tight. This settles an open question posed by Pham, Goyal, and Kiah, confirming that $N(n,3,4)=20n-166$ for all $n \geq 13$.

For scalar maximum distance separable (MDS) codes, the conventional repair schemes that achieve the cut-set bound with equality for the single-node repair have been proven to require a super-exponential sub-packetization level.As is well known, such an extremely high level severely limits the practical deployment of MDS codes.To address this challenge, we introduce a partial-exclusion (PE) repair scheme for scalar linear codes.In the proposed PE repair framework, each node is associated with an exclusion set.The cardinality of the exclusion set is called the flexibility of the node.The maximum value of flexibility over all nodes defines the \textit{flexibility} of the PE repair scheme. Notably, the conventional repair scheme is the special case of PE repair scheme where the flexibility is 1. Under the PE repair framework, for any valid flexibility, we establish a lower bound on the sub-packetization level of MDS codes that meet the cut-set bound with equality for single-node repair. To realize MDS codes attaining the cut-set bound under the PE repair framework, we propose two generic constructions of Reed-Solomon (RS) codes. Moreover, we demonstrate that for a sufficiently large flexibility, the sub-packetization level of our constructions is strictly lower than the known lower bound established for the conventional repair schemes.This implies that, from the perspective of sub-packetization level, our constructions outperform all existing and potential constructions designed for conventional repair schemes. Finally, we implement the repair process for these codes as executable Magma programs, thereby exhibiting the practical efficiency of our constructions.

Constant dimension codes (CDCs) are essential for error correction in random network coding. A fundamental problem of CDCs is to determine their maximal possible size for given parameters. Inserting construction and multilevel construction are two effective techniques for constructing CDCs. We first provide a sufficient condition for a subspace to be added to the code from the mixed dimension construction in Lao et al. (IEEE Trans. Inf. Theory 69(7): 4333-4344, 2023). By appropriately combining matrix blocks from small CDCs and rank-metric codes, we introduce three inserting constructions based on the mixed dimension construction. Furthermore, the mixed dimension construction and these inserting constructions are improved by the multilevel construction that is based on lifting rank-restricted Ferrers diagram rank-metric codes. Our constructions yield some new lower bounds for CDCs, which are superior to the previously best-known ones.

The sequence reconstruction problem was proposed by Levenshtein in 2001. In this model, a sequence from a code is transmitted over several channels, and the decoder receives the distinct outputs from each channel. The main problem is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the sequence reconstruction problem is equivalent to finding the value ofNq(n,d,t), defined as the size of the largest intersection of two metric balls of radiust, where the distance between their centers is at leastdand the sequences areq-ary sequences of lengthn. Levenshtein first discussed this problem in the uncoded sequence setting and determined the value ofNq(n, 1, t)for anyn≥t. Moreover, Gabrys and Yaakobi studied this problem in the context of binary one-deletion-correcting codes and determined the value ofN2(n, 2, t)fort≥ 2. In this paper we study this problem for 3-ary sequences of lengthnover the deletion channel, where the transmitted sequence belongs to a one-deletion-correcting code and there aretdeletions in every channel. Specifically, we determineN3(n, 2, t)fort≥ 2.

Bent partitions ofV(p)nplay an important role in constructing (vectorial) bent functions, partial difference sets, and association schemes, whereV(p)ndenotes ann-dimensional vector space over the finite field Fp,nis an even positive integer, and p is a prime. It is a challenging open problem whether the depth of any bent partition ofV(p)nis always a power ofp. Notably, the depths of all currently known bent partitions ofV(p)nare powers ofp. In this paper, we prove that for a bent partition Γ ofV(p)nfor which all thep-ary bent functions generated by Γ are regular or all are weakly regular but not regular, the depth of Γ must be a power ofp. We present new constructions of bent partitions that (do not) correspond to vectorial dual-bent functions. In particular, a new construction of vectorial dual-bent functions is provided. Additionally, for general bent partitions ofV(2)n, we establish a characterization in terms of Hadamard matrices.

Self-orthogonal codes are a significant class of linear codes in coding theory and have attracted a lot of attention. In [20], [26],p-ary self-orthogonal codes were constructed by usingp-ary weakly regular bent functions, wherepis an odd prime. In [42], two classes of non-degenerate quadratic forms were used to construct q-ary self-orthogonal codes, whereqis a power of a prime. In this paper, we construct new families ofq-ary self-orthogonal codes using vectorial dual-bent functions. Some classes of at least almost optimal linear codes are obtained from the dual codes of the constructed self-orthogonal codes. In some cases, we completely determine the weight distributions of the constructed self-orthogonal codes. From the view of vectorial dual-bent functions, we illustrate that the works on constructing self-orthogonal codes fromp-ary weakly regular bent functions [20], [26] and non-degenerate quadratic forms withqbeing odd [42] can be obtained by our results. We partially answer an open problem on determining the weight distribution of a class of self-orthogonal codes given in [42]. As applications, we construct new infinite families of at least almost optimalq-ary linear complementary dual codes (for short, LCD codes) and quantum codes.

Self-orthogonal codes have received great attention due to their important applications in quantum codes, LCD codes and lattices. Recently, several families of self-orthogonal codes containing the all-1 vector were constructed by augmentation technique. In this paper, utilizing plateaued functions, we construct some classes of linear codes which do not contain the all-1 vector. We also investigate their punctured codes. The weight distributions of the constructed codes are explicitly determined. Under certain conditions, these codes are proved to be self-orthogonal. Furthermore, some classes of optimal linear codes are obtained from their duals. Using the self-orthogonal punctured codes, we also construct several new families of at least almost optimal quantum codes and optimal LCD codes.

Abstract In this paper we carry out an in-depth study on the average decoding error probability of the random parity-check matrix ensemble over the erasure channel under three decoding principles, namely unambiguous decoding, maximum likelihood decoding and list decoding. We obtain explicit formulas for the average decoding error probabilities of the random parity-check matrix ensemble under these three decoding principles and compute the error exponents. Moreover, for unambiguous decoding, we compute the variance of the decoding error probability of the random parity-check matrix ensemble and the error exponent of the variance, which implies a strong concentration result, that is, roughly speaking, the ratio of the decoding error probability of a random linear code in the ensemble and the average decoding error probability of the ensemble converges to 1 with high probability when the code length goes to infinity.

In this paper, we focus on Singleton-optimal$(r,\delta)$LRCs with disjoint local repair groups. We provide an improved bound for the length of q-ary Singleton-optimal$(r,\delta)$LRCs based on the parity-check matrix approach. Specifically, for$d \geq 3\delta $, we prove that$n\le O(q^{\delta })$when$d-3\delta \lt r\le d-2\delta +1$. We also show that the code length$n\le q+\delta +2$when$r=2$and$d=3\delta +2$. We present a sufficient and necessary condition for the existence of Singleton-optimal$(n,k,d;r,\delta)$LRCs with disjoint local repair groups, where the minimum distance satisfies$3\delta +1\le d \le 3\delta +2$and locality$r=2$. This condition imposes an upper bound on the code length,$n\le O(q^{2})$, and indicates the existence of a code length approximately given by$n\approx \sqrt {2}q$when$d=3\delta +1$and$r=2$. Finally, we utilize blocking sets to provide a general construction of Singleton-optimal$(n,k,d=2\delta +2,r=2,\delta)$LRC with code length$n\approx O\left ({{q^{\frac {h+1}{h}}}}\right)$for any$h\ge 3$. To the best of our knowledge, this is the first family of Singleton-optimal$(n,k,d=2\delta +2,r=2,\delta)$LRC with super-linear code length.

Locally repairable array codes (LRACs) constitute an important class of array codes due to their applications in storage systems. In this paper, we first provide an effective generic decoding method for the erased errors. Numerous studies have shown that the syndrome computations account for the main computational overhead of the decoding procedure, especially when the code rate is large. Based on this observation, we present a fast algorithm of syndrome computations for binary optimal LRACs with disjoint local repair groups and certain specific amounts of redundancies, leveraging the vector Reed-Muller (RM)-type transform. In this case, as the code length increases, the number of XORs per data bit required in our algorithm approaches 3, matching that of Reed-Solomon (RS) codes with 4 to 7 redundancies. However, our studied LRACs significantly reduce the number of nodes required for repairing a failed node compared to these RS codes. Moreover, relative to optimal LRACs with 4 redundancies, our algorithm introduces only one additional XOR but tolerates more failures. Furthermore, we generalize our proposed algorithm to support any number of redundancies. We also derive an upper bound on its computational complexity, i.e., the number of XORs per data bit required in the generalized algorithm is at most ⌊log2(d−1)⌋+1, wheredrepresents the minimum distance of our studied LRACs.

Constantinescu et al. introduced the homogeneous weight on the integer residue ring$\mathbb {Z}_{m}$which can reflect more information compared with the Hamming weight. Few homogeneous weight linear codes over finite chain rings have important applications in cryptography, lattices, modular forms and combinatorics. In this paper, we construct an infinite class of cyclic codes over the finite chain ring$\mathbb {F}_{p^{t}}[\omega]/(\omega ^{2})$by the trace function, and determine their homogeneous weight distributions by applying the theory of exponential sums. In order to investigate the minimality of linear codes over finite chain rings, we firstly present the necessary and sufficient condition for linear codes over the finite chain ring$\mathbb {F}_{p^{t}}[\omega]/(\omega ^{2})$to be minimal or almost minimal by the Hamming weights of codewords. Then, based on the proposed condition and few Hamming weight cyclic codes, we give several classes of minimal and almost minimal linear codes. Furthermore, we derive several families of strongly regular graphs, strongly walk-regular graphs and triple sum sets by few homogeneous weight linear codes.

At present, existing multi-receiver authentication (MRA) schemes can only handle situations where the capacities of all receivers in the schemes are the same. However, in reality, different receivers may need to have different storage capacities. In this paper, inspired by the secret sharing scheme based on the Chinese Remainder Theorem (CRT) for polynomial rings where each participant holds the share with different sizes, we propose three new constructions of unconditionally secure MRA schemes for multiple messages using the CRT for polynomial rings, including a$(k,n)$-threshold MRA scheme, a$(k,n,\omega)$-weighted threshold MRA scheme, and a$(\mathcal {Q},\mathcal {F})$-general MRA scheme. As far as we know, our proposed MRA schemes are the first MRA schemes with different storage capacities for different receivers and the first ones based on the CRT for polynomial rings. Moreover, the proposed schemes can be seen as extensions of the MRA scheme in Safavi-Naini and Wang. In particular, as for our$(\mathcal {Q},\mathcal {F})$-general MRA scheme, it has generally more communication complexity and much less computation complexity than the existing$(\mathcal {Q},\mathcal {F})$-general MRA scheme.

At present, existing multi-receiver authentication (MRA) schemes can only handle situations where the capabilities of all receivers are the same. However, in reality, different receivers may need to have different storage capabilities. In this paper, inspired by the secret sharing scheme based on the Chinese Remainder Theorem (CRT) for polynomial rings where distinct participants save shares with distinct sizes, we propose a new unconditionally secure MRA scheme for multiple messages by the same technique. As far as we know, our MRA scheme is the first MRA scheme with different storage capacities for different receivers and the first one based on the CRT for polynomial rings supporting general access structures. In contrast to the existing general MRA scheme, although our MRA scheme has more communication complexity, it has less computation complexity.

In this paper, for the first time, we propose a new explicit hierarchical threshold secret sharing (HTSS) scheme based on the Chinese Remainder Theorem (CRT) for polynomial rings, where the participant set is divided into disjoint subsets and the threshold of a superior subset is less than the threshold of an inferior subset. In addition, we present a rigorous security analysis to show that our HTSS scheme is both perfect and ideal. Moreover, a toy example of our HTSS scheme is given to enable readers to better understand our construction. By comparison, it appears that our scheme is the first CRT-based HTSS for polynomial rings and also the first ideal and perfect CRT-based HTSS scheme, which is easier to construct than its counterpart for integer rings, where different participants hold shares of different sizes. Besides, our HTSS can also distribute shares of the same size, similar to other HTSS.

In this paper, we construct a new class of rank metric codes, called$\lambda$-twisted Gabidulin codes, and prove some properties of this class of codes. Furthermore, we show an explicit description of the dual of a class of$\lambda$-twisted Gabidulin codes, which is also applicable to twisted Gabidulin codes. Finally, we explore the application of$\lambda$-twisted Gabidulin codes in cryptography.

An$(r,\ \delta)$-locally repairable code (LRC) is an$[n,\ k,\ d]$linear code that permits the reconstruction of each code symbol by accessing up to$r$other symbols in the event of at most$\delta-1$erasures. In this paper, by characterizing the weight type hierarchy of codewords, we offer explicit expressions of the weight distributions for q-ary optimal$(r=2,\ \delta)$-LRCs with minimum distance$2\delta+1$and even code dimension, as well as for$(r,\ \delta)$-LRCs with minimum distance$\delta+1$under the condition that$k\geq 5r-1$. These corresponding parameter conditions ensure all the$(r,\ \delta)$-LRCs we studied possess disjoint locality groups. Furthermore, we demonstrate that the weight distributions of optimal$(r=2,\ \delta)$-LRCs can be uniquely determined only for specific minimum distances of$\delta, \delta+1$or$2\delta+1$.

In this paper, we consider the vector linear function computing problem in a network where communication links may suffer from errors. A sink node is required to compute with zero error a vector linear function over a finite field, and the inputs of the target function are generated by multiple source nodes. The nodes in this network can combat errors by network coding. Given a nonnegative integer$\tau$, the robust computing capacity for the above model is defined as the maximum average number of times that the target function can be computed with zero error at the sink node for one use of the network, in which at most$\tau$links may suffer from errors. When$\tau=0$, the robust computing capacity degenerates into the computing capacity without errors. For$\tau\geq 0$, we propose two cut-set bounds on the robust computing capacity. By comparing their performance under the same conditions, we find that the latter bound is superior to the former. Furthermore, we present an improved Singleton bound for linear network codes in the above model, and show that the improved Singleton bound performs better and is tight in a specific scenario. Moreover, we present the Hamming bound and an improved Hamming bound for linear network codes.

An$(n, k, d; r)_{q}$-locally repairable code (LRC) is called a Singleton-optimal LRC if it achieves the Singleton-type bound. Analogous to the classical MDS conjecture, the maximal length problem of Singleton-optimal LRCs has attracted a lot of attention in recent years. In this paper, we give an improved upper bound for the length of q-ary Singleton-optimal LRCs with disjoint repair groups such that$(r+1)\mid n$based on the parity-check matrix approach. In particular, for any Singleton-optimal$(n, k, d; r)_{q}$-LRCs, we show that: 1)$n\le q+d-4$, when$r=2$and$d=3e+8$with$e\ge 0$; 2)$n\leq (r+1)\left \lfloor {{\frac {2(q^{2}+q+1)}{r(r+1)} +e+1}}\right \rfloor $, when$d\ge 8$and$\max \left \{{{3,\frac {d-e-6}{e+1}}}\right \}\le r\le \frac {d-e-3}{e+1}$for any$0\le e\le \left \lfloor {{\frac {d-6}{4} }}\right \rfloor $. Furthermore, we establish equivalent connections between the existence of Singleton-optimal$(n,k,d;r)_{q}$-LRCs for$d=6, r=3$and$d=7, r=2$with disjoint repair groups and some subsets of lines in finite projective space with certain properties. Consequently, we prove that the length of q-ary Singleton-optimal LRCs with minimum distance$d=6$and locality$r=3$is upper bounded by$O(q^{1.5})$. We construct Singleton-optimal$(8\le n\le q+1,k,d=6,r=3)_{q}$-LRC with disjoint repair groups such that$4\mid n$and determine the exact value of the maximum code length for some specific q. We also prove the existence of$(n, k, d=7; r=2)_{q}$-Singleton-optimal LRCs for$n \approx \sqrt {2}q$.

Cyclic codes are an important class of linear codes. Bounding the minimum distance of cyclic codes is a long-standing research topic in coding theory, and several well-known and basic results have been developed on this topic. Recently, locally repairable codes (LRCs) have attracted much attention due to their repair efficiency in large-scale distributed storage systems. In this paper, by employing the singleton procedure technique, we first provide a sufficient condition for bounding the minimum distance of cyclic codes with typical defining sets. Secondly, by considering a specific case, we establish a connection between bounds for the minimum distance of cyclic codes and solutions to a system of inequalities. This connection leads to the derivation of new bounds, including some with general patterns. In particular, we provide three new bounds with general patterns, one of which serves as a generalization of the Betti-Sala bound. Finally, we present a generalized lower bound for a special case and construct several families of (2, δ)-LRCs with unbounded length and minimum distance 2δ. It turns out that these LRCs are distance-optimal, and their parameters are new. To the best of our knowledge, this work represents the first construction of distance-optimal (r, δ)-LRCs with unbounded length and minimum distance exceedingr+ δ - 1.

Vectorial dual-bent functions have recently attracted some researchers’ interest as they play a significant role in constructing partial difference sets, association schemes, bent partitions, and linear codes. In this paper, we further study vectorial dual-bent functions$F: V_{n}^{(p)}\rightarrow V_{m}^{(p)}$, where$2\leq m \leq \frac {n}{2}$, and$V_{n}^{(p)}$denotes an n-dimensional vector space over the prime field$\mathbb {F}_{p}$. For certain vectorial dual-bent functions (called vectorial dual-bent functions with Condition A), we present a more concise characterization in terms of partial difference sets than the one given in Wang et al. (2023), and give new characterizations in terms of amorphic association schemes, linear codes, and generalized Hadamard matrices, respectively. When$p=2$, we characterize vectorial dual-bent functions with Condition A in terms of bent partitions. Through the relationship between vectorial dual-bent functions and bent partitions, new characterizations of certain bent partitions in terms of amorphic association schemes, linear codes, and generalized Hadamard matrices are obtained. For a vectorial dual-bent function$F: V_{n}^{(p)}\rightarrow V_{m}^{(p)}$with$F(0)=0, F(x)=F(-x)$, where$2\leq m \leq \frac {n}{2}$, we give a necessary and sufficient condition under which the preimage set partition of F induces an association scheme. By using two classes of vectorial dual-bent functions, more association schemes are obtained.

Locally repairable codes (LRCs) are an important class of codes to minimize the number of nodes contacted during repairing in distributed storage systems (DSSs). LRCs with locality (r,δ) were introduced by Prakash et al. that one can recover at most δ−1 erasures code symbols by accessing up to r other code symbols. In this paper, we first propose the Hamming-type bound of (r,δ)-LRCs by extending the definition of ℒ-space proposed by Wang et al. Then we define perfect and k-optimal (r,δ)-LRCs. And we construct two classes of perfect (r = 2,δ)-LRCs which cover the results in [16] for perfect r-LRCs. Meanwhile, we present a construction of k-optimal LRCs for general parameters based on the parity-check matrix and Vandermonde matrix.

It is well-known that MacWilliams identities play a significant role in coding theory. In [5]-[7], MacWilliams-like identities for p-ary bent functions $f:\mathbb{F}_p^n \to {\mathbb{F}_p}$ were given, where p is a prime. The aim of this paper is to investigate MacWilliams-like identities for vectorial bent functions. We give MacWillaims-like identities for certain vectorial bent functions $F:\mathbb{F}_q^t \to {\mathbb{F}_q}$, where q is a power of a prime p. We illustrate that when q = p, the MacWilliams-like identities for weakly regular p-ary bent functions can be obtained by our results. Based on the obtained MacWilliams-like identities, we give some nonexistence results on vectorial bent functions.

Bent partitions of$V_{n}^{(p)}$are quite powerful in constructing bent functions, vectorial bent functions and generalized bent functions, where$V_{n}^{(p)}$is an$n$-dimensional vector space over$\mathbb {F}_{p}$,$n$is an even positive integer and$p$is a prime. The classical examples of bent partitions are obtained from (partial) spreads. In Anbar and Meidl (2022) and Meidl and Pirsic (2021), two classes of bent partitions which are not obtained from (partial) spreads were presented. In Anbar et al. (2023), more bent partitions$\Gamma _{1}, \Gamma _{2}, \Gamma _{1}^{\bullet }, \Gamma _{2}^{\bullet }, \Theta _{1}, \Theta _{2}$were presented from (pre)semifields, including the bent partitions given in Anbar and Meidl (2022) and Meidl and Pirsic (2021). In this paper, we investigate the relations between bent partitions and vectorial dual-bent functions. For any prime$p$, we show that one can generate certain bent partitions (called bent partitions satisfying Condition$\mathcal {C}$) from certain vectorial dual-bent functions (called vectorial dual-bent functions satisfying Condition A). In particular, when$p$is an odd prime, we show that bent partitions satisfying Condition$\mathcal {C}$one-to-one correspond to vectorial dual-bent functions satisfying Condition A. We give an alternative proof that$\Gamma _{1}, \Gamma _{2}, \Gamma _{1}^{\bullet }, \Gamma _{2}^{\bullet }, \Theta _{1}, \Theta _{2}$are bent partitions in terms of vectorial dual-bent functions. We present a secondary construction of vectorial dual-bent functions, which can be used to generate more bent partitions. We show that any weakly regular ternary bent function$f: V_{n}^{(3)}\rightarrow \mathbb {F}_{3}$($n$is even) of 2-form can generate a bent partition. When such$f$is weakly regular but not regular, the generated bent partition from$f$is not coming from a normal bent partition, which answers an open problem proposed in Anbar and Meidl (2022). We give a sufficient condition on constructing partial difference sets from bent partitions, and when$p$is an odd prime, we provide a characterization of bent partitions satisfying Condition$\mathcal {C}$in terms of partial difference sets.

Visual cryptography scheme is a method of encrypting secret image into n noiselike shares. The secret image can be reconstructed by stacking adequate shares. In the past two decades, many schemes have been proposed to realize the cheating prevention visual cryptography scheme (CPVCS). Significantly, Ren et al. [ 9 ] first introduced the idea of CPVCS with the help of Latin square. Inspired by their work, in this article, a new reliable scheme is proposed. More precisely, to facilitate the certification process, we embed meaningful characters into the randomly chosen authentication patterns in each divided blocks. Furthermore, we fix the security vulnerability in the stacked results of share S g and verification Ver g , where 1≤ g ≤ n . Since the improved scheme encrypts the secret image by utilizing random grids, the generated shares have no pixel expansion. Finally, theoretical analysis and experimental results are conducted to evaluate the efficiency and security of the proposed scheme.

There has been a lot of works about constructing optimal LRCs via cyclic codes because of their elegant algebraic structure and efficient encoding procedure. Constructing optimal cyclic LRCs with large code lengths for relatively large minimum distances has been an attractive problem. Recently, Fang et al. firstly constructed two classes of q-ary cyclic Singleton-optimal 2-LRCs with length n > q + 1 and minimum distance d = 6 in [23]. In this paper, we generalize the constructions to the (r,δ)-LRCs. Specifically, we obtain two classes of optimal cyclic (2,δ)-LRCs with length $n = \frac{{(\delta + 1)(q + 1)}}{{{2^t}}}$ and minimum distance 2δ + 2, two classes of almost optimal cyclic (2,δ)-LRCs with length $n = \frac{{(\delta + 1)(q + 1)}}{{{2^t}}}$ and minimum distance 2δ +1, where t is a non-negative integer.

A function $f:\mathbb{F}_2^n \to {\mathbb{F}_2}$ is called a 5-valued spectrum function if the Walsh transform Wftakes the values $0, \pm {2^{\frac{{n + {s_1}}}{2}}}, \pm {2^{\frac{{n + {s_2}}}{2}}}$ for some different non-negative integers si,i = 1,2 with n + sieven. In [IEEE Transactions on Information Theory, 67 (2), 2021], by spectral method, Hodžić et al. characterized the so-called basic 5-valued spectrum functions f whose duals $f_{[i]}^{\ast}(i = 1,2)$ are totally disjoint spectra functions. For a special case that the corresponding functions $\overline {f_{[i]}^{\ast}} (i = 1,2)$ are basic plateaued functions, Hodžić et al. gave a construction of basic 5-valued spectrum functions. They left open problems to provide constructions of 5-valued spectrum functions f such that f are basic and the corresponding functions $\overline {f_{[i]}^{\ast}} (i = 1,2)$ are non-basic plateaued functions, or f are non-basic. In this paper, we provide three new constructions of 5-valued spectrum functions f with totally disjoint spectra duals $f_{[i]}^{\ast}(i = 1,2)$, including the case that f are basic and the corresponding functions $\overline {f_{[i]}^{\ast}} (i = 1,2)$ are non-basic plateaued functions, and the case that f are non-basic, which provide answers to the problems proposed by Hodžić et al.. Since non-basic 5-valued spectrum functions are EA-inequivalent to basic ones, two constructions in this paper can produce 5-valued spectrum functions which are EA-inequivalent to ones in [IEEE Transactions on Information Theory, 67 (2), 2021].

Locally repairable codes (LRCs) are important for distributed storage systems due to their efficient repairing ability of the failed storage nodes. A$q$-ary optimal$(n,k,r)$-LRC is an$[n,k,d]$linear code over$\mathbb {F}_{q}$such that every code symbol has locality$r$, and the minimum distance attains the well-known Singleton-like bound. In this paper, we study the maximal code length, code constructions and weight distributions of$q$-ary optimal LRCs with locality 2 and distance 5, which are of both practical and theoretical interest. Firstly, it is proved that when the code dimension is even or odd, corresponding maximal code lengths of such$q$-ary optimal LRCs are$3 \cdot \lfloor \frac {q+1}{3} \rfloor $and$3 \cdot \left \lfloor{ \frac {q-1}{3} }\right \rfloor +5$, respectively. Up to the equivalence of linear codes, we propose constructions of all the possible$q$-ary optimal LRCs with locality 2, distance 5 and maximal code length. Then, by characterizing the weight type hierarchy of codewords, we show that the weight distribution of any$q$-ary optimal LRC with locality 2, distance 5 and even code dimension can be uniquely determined and explicit expression of the weight distribution is given. Moreover, it is shown that all$q$-ary optimal LRCs with locality 2, distance 5 and even code dimension are maximally recoverable.

In this paper, we study the duals of generalized bent functions$f: V_{n}\rightarrow \mathbb {Z}_{p^{k}}$, where$V_{n}$is an$n$-dimensional vector space over$\mathbb {F}_{p}$and$p$is an odd prime,$k$is a positive integer. It is known that weakly regular generalized bent functions always appear in pairs since the dual of a weakly regular generalized bent function is also a weakly regular generalized bent function. The duals of non-weakly regular generalized bent functions can be generalized bent or not generalized bent. By generalizing the construction of Çeşmelioğluet al., 2016, we provide an explicit construction of generalized bent functions whose duals can be generalized bent or not generalized bent. We show that the well-known direct sum construction and the generalized indirect sum construction given in Wang and Fu, 2021. can provide secondary constructions of generalized bent functions whose duals can be generalized bent or not generalized bent. By using the knowledge on ideal decomposition in cyclotomic fields, we prove that$f^{**}(x)=f(-x)$if$f$is a generalized bent function and its dual$f^{*}$is also a generalized bent function. For any non-weakly regular generalized bent function$f$which satisfies that$f(x)=f(-x)$and its dual$f^{*}$is generalized bent, we give a property and as a consequence, we prove that there is no self-dual generalized bent function$f: V_{n}\rightarrow \mathbb {Z}_{p^{k}}$if$p\equiv 3 ~(mod ~4)$and$n$is odd. When$p \equiv 1 ~(mod ~4)$or$p\equiv 3 ~(mod ~4)$and$n$is even, we give a secondary construction of self-dual generalized bent functions. In the end, by the decomposition of generalized bent functions, we characterize the relations between the generalized bentness of the dual of a generalized bent function$f$and the bentness of the duals of bent functions associated with the generalized bent function$f$, as well as the relations of self-duality between a generalized bent function$f$and bent functions associated with the generalized bent function$f$.

Locally repairable codes (LRCs) have emerged as an important coding scheme in distributed storage systems (DSSs) with relatively low repair cost by accessing fewer non-failure nodes. Theoretical bounds and optimal constructions of LRCs have been widely investigated. Optimal LRCs via cyclic codes provide significant benefit of elegant algebraic structure and efficient encoding procedure. In this paper, we continue to consider the constructions of optimal LRCs via cyclic codes with longer code length. Specifically, we first obtain two classes of Singleton-optimal cyclic LRCs with length$n=3(q+1)$when$3\vert (q-1)$and$q$is even, and length$n=\frac{3}{2}(q+1)$when$3\vert (q-1)$and$q$is odd, respectively. To the best of our knowledge, this is the first construction of q-ary cyclic Singleton-optimal LRCs with length$n > q+1$and minimum distance$d\geq 5$. By using cyclic codes as well, we construct a new family of perfect LRCs with$d=5$, which generalize the result of Goparaju and Calderbank.

A$q$-ary ($n, k, r$) locally repairable code (LRC) is an [$n, k, d$] linear code where every code symbol can be repaired by accessing at most$r$other code symbols. Its minimum distance satisfies the well-known Singleton-like bound. In this paper, we determine all the possible parameters of quaternary LRCs attaining this Singleton-like bound by employing a parity-check matrix approach. Explicit optimal code constructions are given for all the possible parameters.

Repair locality has been an important metric in a distributed storage system (DSS). Erasure codes with small locality are more popular in a DSS, which means fewer available nodes participating in the repair process of failed nodes. Locally repairable codes (LRCs) as a new coding scheme have given more rise to the system performance and attracted a lot of interest in the theoretical research in coding theory. The particular concern among the research problems is the bounds and optimal constructions of LRCs. The problem of optimal constructions of LRCs includes the most important case of Singleton-optimal LRCs whose minimum distance achieves the Singleton-like bound, which is the core consideration in this paper. In this work, we first of all derive an improved and general upper bound on the code length of Singleton-optimal LRCs with minimum distance d = 5, 6, some known constructions are shown to exactly achieve our new bound, which verifies its tightness. For locality r = 2 and distance d = 6, we construct three newSingleton-optimal LRCs whose code length n = 3(q + 1), n = 3(q + √q + 1) and n = 3(2q - 4), respectively. Moreover, we obtain a complete characterization for Singletonoptimal LRCs with r = 2 and d = 6. Such characterization has established an important connection between the existence of Singleton-optimal LRCs and that of a special subset of lines of finite projective plane P G(2, q), thus provides a methodology for constructing LRCs with longer length based on any advance on finite projective plane P G(2, q). In the end, we employ the well-known line-point incidence matrix and Johnson bounds for constant weight codes to derive tighter upper bounds on the code length. These new bounds further help us to prove that some of the previous Singleton-optimal constructions or their extensions achieve the longest possible code length for q = 3, 4, 5, 7. It's worth noting that all of our Singleton-optimal constructions possess small locality r = 2, which are attractive in a DSS.

The parameters of a q-ary MDS Euclidean self-dual codes are completely determined by its length and the construction of MDS Euclidean self-dual codes with new length has been widely investigated in recent years. In this paper, we give a further study on the construction of MDS Euclidean self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The main idea of our construction is to choose suitable evaluation points such that the corresponding (extended) GRS codes are Euclidean self-dual. Firstly, we consider the evaluation set consists of two disjoint subsets, one of which is based on the trace function, the other one is a union of a subspace and its cosets. Then four new families of MDS Euclidean self-dual codes are constructed. Secondly, we give a simple but useful lemma to ensure that the symmetric difference of two intersecting subsets of finite fields can be taken as the desired evaluation set. Based on this lemma, we generalize our first construction and provide two new families of MDS Euclidean self-dual codes. Finally, by using two multiplicative subgroups and their cosets which have nonempty intersection, we present three generic constructions of MDS Euclidean self-dual codes with flexible parameters. Several new families of MDS Euclidean self-dual codes are explicitly constructed.

An (r, δ)-locally repairable code ((r, δ)-LRC for short) was introduced by Prakash et al. [14] for tolerating multiple failed nodes in distributed storage systems, which was a generalization of the concept of r-LRCs produced by Gopalan et al. [5]. An (r, δ)-LRC is said to be optimal if it achieves the Singleton-like bound. Recently, Chen et al. [2] generalized the construction of cyclic r-LRCs proposed by Tamo et al. [19], [20] and constructed several classes of optimal (r, δ)-LRCs of length n for n (q-1) or n (q+1), respectively in terms of a union of the set of zeros controlling the minimum distance and the set of zeros ensuring the locality. Following the work of [2], [3], this paper first characterizes (r, δ)-locality of a cyclic code via its zeros. Then we construct several classes of optimal cyclic (r, δ)-LRCs of length n for n (q - 1) or n (q+1), respectively from the product of two sets of zeros. Our constructions include all optimal cyclic (r, δ)-LRCs proposed in [2], [3], and our method seems more convenient to obtain optimal cyclic (r, δ)-LRCs with flexible parameters. Moreover, many optimal cyclic (r, δ)-LRCs of length n for n (q - 1) or n (q + 1), respectively with (r + δ - 1) n can be obtained from our method.

Locally repairable codes (LRCs) with locality r were introduced to recover an erased code symbol by accessing at most r other code symbols. An LRC achieving the well-known Singleton-type bound is called an optimal LRC. Constructing optimal LRCs has been a hot topic of coding theory in recent years. Similar to the famous MDS conjecture, the maximum code length of an optimal LRC has been investigated by Guruswami et al. (TIT2019) and some constructions of optimal LRCs with large code length are also presented by Jin (TIT2019) and Xing and Yuan (arXiv2018). In this paper, we consider the maximum code length of optimal LRCs with minimum distance 6 and locality 2. Firstly, we give a complete characterization for optimal LRCs with d = 6 and r = 2, which shows that the existence of such an LRC is equivalent to the existence of a special subset of lines of finite projective plane PG(2, q). Based on this characterization, we generalize the results of Chen et al. (ISIT2018) and obtain two new constructions of optimal (n, k, d = 6; r = 2)-LRCs with n = 3(q + √q + 1) and n = 3(2q -4), respectively. By using the techniques of line-point incidence matrix and Johnson bound, we show that the code length of any q-ary optimal LRCs with d = 6 and r = 2 must be bounded by O(q1.5). To the best of our knowledge, both of the code length of our new constructions and upper bounds are better than previously known ones. Moreover, we also determine the exact value of the maximum code length of q-ary optimal LRCs with d = 6 and r = 2 for q = 4, 5.

Linear codes with locality, called locally repairable codes (LRCs), have been applied in distributed storage systems (DSSs) to minimize the number of storage nodes to be downloaded during repairing a failed node. A linear code has locality r if one can recover an erased code symbol by accessing at most r other code symbols. Bounds and constructions of LRCs have been widely investigated in recent years. In this paper, we first propose the definition of perfect LRCs, whose dimension k achieves the Hamming-type bound proposed by Wang et al. (TIT2019). Then we establish important connections of the existence of LRCs with finite geometry and finite fields, and two systematic constructions of perfect LRCs are obtained. Rewriting the Hamming-type bound by the property of integers, we present a new construction of k-optimal LRCs achieving this bound, which have longer code length than the previously known ones.

The weight distribution of a q-ary [n, k, d] linear code is an important research subject in coding theory. In a linear code, a code symbol is said to have locality r if it can be recovered by accessing at most r other code symbols. A q-ary locally repairable code (LRC) is an [n, k, d] linear code over Fq such that every code symbol has locality r, and is said to be optimal if the minimum distance attains the well-known Singleton-like bound. In this paper, we focus on the weight distributions of q-ary optimal LRCs with locality 2, minimum distance 5 and even dimension k. By analyzing the parity-check matrices involving locality, it is shown that the weight distributions of all q-ary optimal LRCs with locality 2, distance 5, even dimension k and code length n can be uniquely determined and explicit expressions of the weight distributions are given.

A verifiable multi‐secret sharing (VMSS) scheme allows distributors to share multiple secrets simultaneously and can detect fraud by both distributors and participants. After analysing the security of the VMSS schemes proposed by Dehkordi and Mashhadi in 2015, the authors point out that they could not detect the fraudulent behaviour of the dealer. By using the non‐homogeneous linear recursion and linear feedback shift rigister (LFSR) public key cryptosystem, they introduce two new VMSS schemes. The proposed schemes can not only overcome the defects mentioned above, but also have shorter private and public key lengths at the same level of security. Besides, the proposed schemes are dynamic.

Let m be an arbitrary positive integer and D8mbe the dihedral group of order 8m, i.e., D8m= (x, y | x4m= 1, y2= 1, yxy = x-1). Left ideals of the dihedral group algebra F2[D8m] are called binary left dihedral codes of length 8m, and abbreviated as binary left D8m-codes. In this paper, we give an explicit representation and enumeration for all distinct self-dual binary left D8m-codes. These codes make up an important class of self-dual binary [8m, 4m]-codes such that the dihedral group D8mis necessarily a subgroup of the automorphism group of each code. In particular, we provide recursive algorithms to solve congruence equations over finite chain rings for constructing all distinct self-dual binary left D8m-codes and obtain a Mass formula to count the number of all these self-dual codes. As a preliminary application, we obtain the extremal self-dual binary [48, 24, 12]-code and an extremal self-dual binary [56, 28, 12]code from self-dual binary left D48-codes and left D56-codes respectively.

In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out that the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length n > q+1 are also obtained.

Information-theoretic security is considered in the paradigm of network coding in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, also referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this paper, we consider the problem of secure network coding when the information rate and the security level can change over time. To efficiently solve this problem, we put forward local-encoding-preserving secure network coding, where a family of secure linear network codes (SLNCs) is called local-encoding-preserving if all the SLNCs in this family share a common local encoding kernel at each intermediate node in the network. We first consider the design of a family of local-encoding-preserving SLNCs for a fixed security level and a flexible rate. A simple approach is presented for efficiently constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same security level and the rate reduced by one. By applying this approach repeatedly, we can obtain a family of local-encoding-preserving SLNCs with a fixed security level and multiple rates. We further consider the design of a family of local-encoding-preserving SLNCs for a fixed rate and a flexible security level. We present a novel and efficient approach for constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same rate and the security level increased by one. Next, we consider the design of a family of local-encoding-preserving SLNCs for a fixed dimension (equal to the sum of rate and security level) and a flexible pair of rate and security level. We propose another novel approach for designing an SLNC such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. Also, two polynomial-time algorithms are developed for efficient implementations of the later two proposed approaches, respectively. Furthermore, we prove that all our three approaches do not incur any penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, we consider the ultimate problem of designing a family of local-encoding-preserving SLNCs that can be applied to all possible pairs of rate and security level. By combining the constructions of the three families of local-encoding-preserving SLNCs in the paper in suitable ways, we can obtain a family of local-encoding-preserving SLNCs that can be applied for all possible pairs of rate and security level. Three possible such constructions are presented.

A locally repairable code (LRC) is a linear code such that every code symbol can be recovered by accessing a small number of other code symbols. In this paper, we study bounds and constructions of LRCs from the viewpoint of parity-check matrices. Firstly, a simple and unified framework based on parity-check matrix to analyze the bounds of LRCs is proposed, and several new explicit bounds on the minimum distance of LRCs in terms of the field size are presented. In particular, we give an alternate proof of the Singleton-like bound for LRCs first proved by Gopalan et al. Some structural properties on optimal LRCs that achieve the Singleton-like bound are given. Then, we focus on constructions of optimal LRCs over the binary field. It is proved that there are only five classes of possible parameters with which optimal binary LRCs exist. Moreover, by employing the proposed parity-check matrix approach, we completely enumerate all these five classes of optimal binary LRCs attaining the Singleton-like bound in the sense of equivalence of linear codes.

Locally repairable codes (LRCs) are introduced in distributed storage systems due to their low repair overhead. An LRC is called optimal if its minimum distance attains the Singleton-like upper bound. Chen et al. (2018) recently studied the constructions of optimal (r, δ)-LRCs with length n | (q+1) and (r + δ - 1) | n, where many classes of optimal cyclic constructions were obtained. In this paper, by employing constacyclic MDS codes, we construct seven classes of optimal (r, δ)-LRCs with new parameters. After adding these new optimal LRCs via constacyclic codes, we have completely obtained all optimal (r, δ)-LRCs with length n | (q + 1) and (r + δ - 1) | n for all possible parameters for the completeness in the coding theory. It is worth noting that the optimal constacyclic LRCs with new parameters provide more alternatives to cyclic LRCs in the practical demands of distributed storage systems, where specific values of n, k, r, and δ are required. Moreover, constacyclic LRCs also possess the encoding and decoding efficiency as cyclic LRCs.

In this paper, we consider the problem for which lengths a maximum distance separable (MDS) Euclidean self-dual code over Fq exists. This problem is completely solved for the case where q is even. For q is odd, some q-ary MDS Euclidean self-dual codes were obtained in the literature. In this paper, we construct six new classes of q-ary MDS Euclidean self-dual codes by using generalized Reed-Solomon (GRS for short) codes and extended GRS codes.

It is an important task to construct quantum maximum-distance-separable (MDS) codes with good parameters. In the present paper, we provide six new classes of$q$-ary quantum MDS codes by using generalized Reed–Solomon (GRS) codes and Hermitian construction. The minimum distances of our quantum MDS codes can be larger than$\frac {q}{2}+1$. Three of these six classes of quantum MDS codes have longer lengths than the ones constructed in[1]and[2], hence some of their results can be easily derived from ours via the propagation rule. Moreover, some known quantum MDS codes of specific lengths can be seen as special cases of ours and the minimum distances of some known quantum MDS codes are also improved as well.

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the qℓ-incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the qℓ-incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all [n,k] linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all [n,nR] linear codes.

Pseudo-cyclic codes is a generalization of cyclic codes and provides a way to obtain MDS codes with more parameters in coding theory. Specially, if a is not a quadratic residue in Fq, xn-a only has quadratic factors over Fqfor even n and k. Based on these facts, we consider the constructions of optimal q-ary pseudo-cyclic (r, δ) locally repairable codes (LRCs) with length n | q+1 in this paper. To be specific, we obtain four classes of optimal pseudo-cyclic (r, δ) -LRCs with new parameters.

Prakash et al. [2] introduced the concept of (r, δ) locally repairable codes ((r, δ)-LRCs for short) for tolerating multiple failed nodes. An (r, δ)-LRC is called optimal if it achieves the Singleton-type bound. In this paper, inspired by the work of [3], we firstly construct two classes of optimal cyclic (r, δ)-LRCs with unbounded lengths (i.e., lengths of these codes are independent of the alphabet size) and minimum distances δ+1 or δ + 2, which generalize the results about the δ = 2 case given in [3]. Secondly, with a slightly stronger condition, we present a construction of optimal cyclic (r, δ)-LRCs with unbounded length and larger minimum distance 2δ. Furthermore, when δ = 3, we provide another class of optimal cyclic (r, 3)-LRCs with unbounded length and larger minimum distance 6.

Optimal (r, δ) locally repairable codes ((r, δ)-LRCs for short) with length n | (q+1) have been studied in [5] and [6]. In this paper, along with their ideas, by using cyclic or constacyclic codes, we construct three classes of such LRCs with new parameters which are not obtained in [5] and [6]. Thus, optimal (r, δ)-LRCs with length n | (q+1) and (r + δ - 1) | n are completely determined for all possible parameters.

A code is said to be an r-local locally repairable code (LRC) if each of its coordinates can be repaired by accessing at most r other coordinates. When some of the r coordinates are also erased, the r-local LRC cannot accomplish the local repair, which leads to the concept of (r, δ)-locality. A q-ary [n, k] linear code C is said to have (r, δ)-locality (δ ≥ 2) if for each coordinate i, there exists a punctured subcode of C with support containing i, whose length is at most r+δ-1, and whose minimum distance is at least δ. The (r, δ)-LRC can tolerate δ-1 erasures in every local code (i.e., punctured subcode), which degenerates to an r-local LRC when δ = 2. A q-ary (r, δ) LRC is called optimal if it meets the singleton-like bound for (r, δ)-LRCs. A class of optimal q-ary cyclic r-local LRCs with lengths n | q - 1 were constructed by Tamo, Barg, Goparaju, and Calderbank based on the q-ary Reed-Solomon codes. In this paper, we construct a class of optimal q-ary cyclic (r, δ)-LRCs (δ ≥ 2) with length n | q - 1, which generalizes the results of Tamo et al. Moreover, we construct a new class of optimal q-ary cyclic r-local LRCs with lengths n | q + 1 and a new class of optimal q-ary cyclic (r, δ)-LRCs (δ ≥ 2) with lengths n | q + 1. The constructed optimal LRCs with length n = q + 1 have the best-known length for a given finite field with size q when the minimum distance is larger than 4.

An (n, k, r) locally repairable code (LRC) is an [n, k, d] linear code where every code symbol can be repaired from at most r other code symbols. An LRC is said to be optimal if the minimum distance attains the Singleton-like bound d ≤ n - k - ⌈k/r⌉ + 2. The generalized Hamming weights (GHWs) of linear codes are fundamental parameters which have many useful applications. In this paper, we study the GHWs of LRCs. Firstly, we obtain a generalized Singleton-like bound on the i-th (1 ≤ i ≤ k) GHWs of (n, k, r) LRCs. The proposed bound can give the Singleton-like bound when i = 1 and reduce to the classical generalized Singleton bound when there is no locality constraint. Then, it is shown that for optimal (n, k, r) LRCs with r | k, the weight hierarchy can be completely determined. For optimal (n, k, r) LRCs with r | k, some lower bounds on GHWs of LRCs and their dual codes are given. Finally, two general bounds on linear codes in terms of GHWs are presented.

Multi‐receiver authentication plays an important role in network security. Many researchers have studied the constructions and the properties of the multi‐receiver authentication scheme. However, most of these schemes treat the capability of all the receivers equally. In practice, receivers may have different other than equal powers in many cases. The authors consider the new scenario in the multi‐receiver authentication. The authors propose a multi‐receiver authentication scheme with hierarchical structure among the receivers. The authors construct an unconditionally secure multi‐receiver authentication code by using the Birkhoff interpolation. The authentication scheme is also able to send multiple messages.

Recently, binary 0-1 measurement matrices, especially those from coding theory, were introduced to compressed sensing. Dimakis et al. found that the linear programming (LP) decoding of LDPC codes is very similar to the LP reconstruction of compressed sensing, and they further showed that the sparse binary parity-check matrices of good LDPC codes can be used as provably good measurement matrices for compressed sensing under basis pursuit (BP). Moreover, Khajehnejad et al. made use of girth to certify the good performances of sparse binary measurement matrices. In this paper, we examine the performance of binary measurement matrices with uniform column weight and arbitrary girth under BP. For a fixed measurement matrix, we first introduce a performance indicator wminBPcalled minimum BP weight, and show that any k-sparse signals could be exactly recovered by BP if and only if k ≤ (wminBP- 1)/2. Then, lower bounds of wminBPare studied. Borrowing ideas from the tree bound for the LDPC codes, we obtain several explicit lower bounds of wBPmin, which improve on the previous results in some cases. These lower bounds also imply explicit ℓ1/ℓ1, ℓ2/ℓ1and ℓ∞/ℓ1sparse approximation guarantees, and further confirm that large girth has positive impacts on the performance of binary measurement matrices under BP.

FOX is a family of block ciphers published in 2004 and several attacks on reduced FOX have been published, and the best known attacks are on 7-round FOX64 and 5-round FOX128. In this paper, we present impossible differential attacks on 8-round FOX64 and 6-round FOX128 with various techniques such as the multiple differentials, the state-test technique, the quick sort method and the early abort technique. For 8-round FOX64, the data complexity and the time complexity is |$2^{42}$| and |$2^{239.54}$| one-round encryptions, respectively, and the memory required is |$2^{44}$| bytes. For 6-round FOX128, the data complexity and the time complexity is |$2^{75}$| and |$2^{209.55}$| one-round encryptions, respectively, and the memory required is |$2^{77}$| bytes.

Let G(m,3,r)= (x, y | xm= 1, y3= 1, yx = xry) be a metacyclic group of order 3m, where gcd(m, r) = 1, 13≡ 1 (mod m). Then, left ideals of the group algebra Fq[G(m,3,r)] are called left metacyclic codes over Fq of length 3m, and abbreviated as left G(m,3,r)-codes. A system theory for left G(m,3,r)-codes is developed for the case of gcd(m, q) = 1 and r ≡ qE(mod m) for some positive integer ε, only using finite field theory and basic theory of cyclic codes and skew cyclic codes. The fact that any left G(m,3 1)-code is a direct sum of concatenated codes with inner codes λiand outer codes Ciis proved, where . Aiis a minimal cyclic code over Fqof length m and Ciis a skew cyclic code of length 3 over an extension field of Fq. Then, an explicit expression for each outer code in any concatenated code is provided. Moreover, the dual code of each left G(m,3,r)-code is given and self-orthogonal left G(m,3,r)-codes are determined.

In network communication, the source often transmits messages at several different information rates within a session. How to deal with information transmission and network error correction simultaneously under different rates is introduced in this paper as a variable-rate network error correction problem. Apparently, linear network error correction maximum distance separable (MDS) codes are expected to be used for these different rates guaranteeing the maximal error-correcting capability. For this purpose, designing a linear network error correction MDS code based on the existing results for each information rate is an alternative solution, but it is inefficient due to its high complexity. In order to solve the problem more efficiently, we present the concept of variable-rate linear network error correction MDS codes preserving local encoding kernels, that is, these linear network error correction MDS codes of different rates have the same local encoding kernel at each internal node. Thus, each nonsource node always uses the same local kernel for coding, no matter what the rate is. Furthermore, we propose an approach to construct such a family of variable-rate network MDS codes and give an algorithm for efficient implementation. This approach economizes the storage space for each internal node, and saves resources and time for transmissions on networks. Moreover, the performance of our proposed algorithm is analyzed, including the field size, the time complexity, the encoding complexity at the source node, and the decoding methods. Finally, a random method is introduced for constructing such a family of variable-rate network MDS codes, and a lower bound on the success probability of this random method is given, which shows that this probability will approach to one as the base field size goes to infinity.

In this paper, we study the list decoding error probability of a linear code over the erasure channel. The notion of L-incorrigible sets of a linear code is introduced to characterize its performance under list decoding. The L-incorrigible set distribution of a linear code can also be used to completely determine its decoding error probability under maximum likelihood decoding over the erasure channel. Furthermore, we show that the L-incorrigible set distribution of a linear code can be determined by its support weight distribution. Finally, the error exponent of the unsuccessful decoding probability under optimal decoding for the ensemble of all [n, nR] linear codes is determined.

In the paradigm of network coding, when wiretapping attacks occur, secure network coding is introduced to prevent information leaking adversaries. In practical network communications, the source often multicasts messages at several different rates within a session. How to deal with information transmission and information security simultaneously under variable rates and fixed security-level is introduced in this paper as a variable-rate and fixed-security-level secure network coding problem. In order to solve this problem effectively, we propose the concept of locality-preserving secure linear network codes of different rates and fixed security-level, which have the same local encoding kernel at each internal node. We further present an approach to construct such a family of secure linear network codes and give an algorithm for efficient implementation. This approach saves the storage space for both source node and internal nodes, and resources and time on networks. Finally, the performance of the proposed algorithm is analyzed, including the field size, computational and storage complexities.

Stopping sets and stopping set distribution of a linear code play an important role in the performance analysis of iterative decoding for this linear code. Let C be an [n, k] linear code over Fqwith parity-check matrix H, where the rows of H may be dependent. Let [n] = {1, 2,...,n} denote the set of column indices of H. A stopping set S of C with parity-check matrix H is a subset of [n] such that the restriction of H to S does not contain a row of weight 1. The stopping set distribution {Ti(H)}i=0nenumerates the number of stopping sets with size i of C with parity-check matrix H. Denote H*, the parity-check matrix, consisting of all the nonzero codewords in the dual code C⊥. In this paper, we study stopping sets and stopping set distributions of some residue algebraic geometry (AG) codes with parity-check matrix H*. First, we give two descriptions of stopping sets of residue AG codes. For the simplest AG codes, i.e., the generalized Reed-Solomon codes, it is easy to determine all the stopping sets. Then, we consider the AG codes from elliptic curves. We use the group structure of rational points of elliptic curves to present a complete characterization of stopping sets. Then, the stopping sets, the stopping set distribution, and the stopping distance of the AG code from an elliptic curve are reduced to the search, counting, and decision versions of the subset sum problem in the group of rational points of the elliptic curve, respectively. Finally, for some special cases, we determine the stopping set distributions of the AG codes from elliptic curves.

On a binary erasure channel (BEC) with erasing probability e, the performance of a binary linear code is determined by the incorrigible sets of the code. The incorrigible set distribution (ISD) {Ii}i=0nenumerates the number of incorrigible sets with size i of the code. The probability of unsuccessful decoding under optimal decoding for the code could be formulated by the ISD and ∈. In this paper, we determine the ISDs for the Simplex codes, the Hamming codes, the first order Reed-Muller codes, and the extended Hamming codes, which are some Reed-Muller codes or their shortening or puncturing versions. Then, we show that the probability of unsuccessful decoding under optimal decoding for any binary linear code is monotonously non-decreasing on ∈ in the interval [0,1].

Recently, network error correction coding (NEC) has been studied extensively. Several bounds in classical coding theory have been extended to NEC, especially the Singleton bound. In this paper, following the research line using the extended global encoding kernels proposed by Zhang in 2008, the refined Singleton bound of NEC can be proved more explicitly. Moreover, we give a constructive proof of the attainability of this bound and indicate that the required field size for the existence of network maximum distance separable (MDS) codes can become smaller further. By this proof, an algorithm is proposed to construct general linear network error correction codes including the linear network error correction MDS codes. Finally, we study the error correction capability of random linear NEC. Motivated partly by the performance analysis of random linear network coding, we evaluate the different failure probabilities defined in this paper in order to analyze the performance of random linear NEC. Several upper bounds on these probabilities are obtained and they show that these probabilities will approach to zero as the size of the base field goes to infinity. Using these upper bounds, we slightly improve on the probability mass function of the minimum distance of random linear network error correction codes in a paper by Balli and colleagues, as well as the upper bound on the field size required for the existence of linear network error correction codes with degradation at mostd.

Stopping sets and stopping set distribution of a linear code are used to determine the performance of this code under iterative decoding over a binary erasure channel (BEC). LetCbe a binary [n,k] linear code with parity-check matrixH, where the rows ofHmay be dependent. A stopping setSofCwith parity-check matrixHis a subset of column indices ofHsuch that the restriction ofHtoSdoes not contain a row of weight one. The stopping set distribution {Ti(H)}i=0nenumerates the number of stopping sets with sizeiofCwith parity-check matrixH. Note that stopping sets and stopping set distribution are related to the parity-check matrixHofC. LetH*be the parity-check matrix ofCwhich is formed by all the nonzero codewords of its dual codeC⊥. A parity-check matrixHis called BEC-optimal ifTi(H)=Ti(H*),i=0,1,...,nandHhas the smallest number of rows. In this paper, we study stopping sets, stopping set distributions and BEC-optimal parity-check matrices of binary linear codes. Using finite geometry in combinatorics, we obtain BEC-optimal parity-check matrices and then determine the stopping set distributions for the Simplex codes, the Hamming codes, the first order Reed-Muller codes, and the extended Hamming codes, which are some Reed-Muller codes or their shortening or puncturing versions.

In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth , and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.

In this paper, we study the probability of undetected error for binary constant weight codes (BCWCs). First, we derive a new lower bound on the probability of undetected error. Next, we show that this bound is tight if and only if the BCWCs are generated from certain t-designs. This means that such BCWCs are uniformly optimal for error detection. Thus, we prove a conjecture of Xia, Fu, Jiang and Ling. Furthermore, we determine the distance distributions of such BCWCs. Finally, we derive some bounds on the exponent of the probability of undetected error for BCWCs. These bounds enable us to extend the region in which the exponent of the probability of undetected error is exactly determined

In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2.

In this correspondence, we study the probability of undetected error for binary constant weight codes. First, we derive a new lower bound on the probability of undetected error for binary constant weight codes. Next, we show that this bound is tight if and only if the binary constant weight codes are generated from certain t-designs in combinatorial design theory. This means that these binary constant weight codes generated from certain t-designs are uniformly optimal for error detection. Along the way, we determine the distance distributions of such binary constant weight codes. In particular, it is shown that binary constant weight codes generated from Steiner systems are uniformly optimal for error detection. Thus, we prove a conjecture of Xia, Fu, Jiang, and Ling. Furthermore, the distance distribution of a binary constant weight code generated from a Steiner system is determined. Finally, we study the exponent of the probability of undetected error for binary constant weight codes. We derive some bounds on the exponent of the probability of undetected error for binary constant weight codes. These bounds enable us to extend the region in which the exponent of the probability of undetected error is exactly determined

In this correspondence, we study the probability of undetected error for binary constant-weight codes. First, we derive a new formula on the probability of undetected error for binary constant-weight codes. Second, using this new formula and linear programming, we give two new lower bounds on the probability of undetected error for binary constant-weight codes. These two new lower bounds improve on previously known lower bounds in certain cases. Furthermore, we show that these two lower bounds are tight if and only if the binary constant-weight codes are generated from certain t-designs in combinatorial design theory. This means that these binary constant-weight codes generated from certain t-designs are uniformly optimal for error detection. Along the way, we determine the distance distributions of such binary constant-weight codes. Finally, several examples are given to illustrate the results obtained in this correspondence.

An inverse relative dimension/length profile (IRDLP) of a pair of codes was introduced to describe the equivocation. In this paper, the maximum distance separable (MDS) code is extended to a two-code format: relative MDS pair. For a code and a subcode, the pair is called a relative MDS pair if its inverse relative dimension-length profile (IRDLP) reaches the generalized singleton bound. We consider properties and constructions of relative MDS pairs.

In this correspondence, two new constructions of permutation arrays are given. A number of examples to illustrate the constructions are also provided.

Write-unidirectional memories (WUMs) were introduced by Willems, Vinck, and Borden as an information-theoretic model for storing and updating information on a rewritable medium with the writing constraints: During the odd (resp., even) cycles of updating information, the encoder can only write 1's (resp., 0's) in selected bit positions of WUMs, and not change the contents of other positions. In this correspondence, motivated by the research works of Wolf, Wyner, Ziv, and Ko/spl uml/rner on write-once memories (WOMs), we study the problem of how to reuse a WUM for fixed T successive cycles with nonperiodic codes (i.e., all coding strategies are permitted for every cycle). For the situation where the encoder knows and the decoder does not know the previous content of the memory, we determine the zero-error capacity region, the average capacity, and the maximum total number of information bits stored in the WUM for fixed T successive cycles. Motivated by the research works of Heegard on WOMs with symmetric input noise, we introduce two models of WUMs with symmetric or asymmetric input noise. By using /spl epsiv/-error as performance criterion, we extend the above results for WUMs to the two models of WUMs with symmetric or asymmetric input noise.

In this paper, the undetected error probability for binary codes is studied. First complementary codes are studied. Next, a new proof of Abdel-Ghaffar's (1997) lower bound on the undetected error probability is presented and some generalizations are given. Further, upper and lower bounds on the undetected error probability for binary constant weight codes are given, and asymptotic versions are studied.

In this correspondence, we study binary asymmetric error-correcting codes. A general construction for binary asymmetric error-correcting codes is presented. We show that some previously known lower bounds for binary asymmetric error-correcting codes can be obtained from this general construction. Furthermore, some new lower bounds for binary asymmetric error-correcting codes are obtained from this general construction. These new lower bounds improve the existing ones.

A constant-composition code is a special constant-weight code under the restriction that each symbol should appear a given number of times in each codeword. In this correspondence, we give a lower bound for the maximum size of the q-ary constant-composition codes with minimum distance at least 3. This bound is asymptotically optimal and generalizes the Graham-Sloane bound for binary constant-weight codes. In addition, three construction methods of constant-composition codes are presented, and a number of optimum constant-composition codes are obtained by using these constructions.

For a binary code C of length n, let C~ = V/sub n//spl bsol/C, be the complementary code. The main result of this paper is to determine K(n), the largest integer such that C~ is good for error detection for all linear [n, k] codes C with k/spl les/K(n).

A permutation array (PA) of length n and minimum distance d is a set of permutations of n elements such that any two permutations coincide in at most n - d positions. Some constructions of PAs are given.

We study the problem of source coding with multiple descriptions, which is described as follows. Let X be a discrete memoryless source. There are two encoders, Encoders 1 and 2, and three decoders, Decoders 0, 1, and 2. Encoders 1 and 2 describe the source X at respective rates R/sub 1/ and R/sub 2/. Decoder 1 receives the output of Encoder 1 only, and it can recover X with distortion D/sub 1/. Decoder 2 receives the output of Encoder 2 only, and it can recover X with distortion D/sub 2/. Decoder 0 receives the outputs of both Encoders 1 and 2, and it can recover X with distortion D/sub 0/. We show that if Decoder 2 (or Decoder 1) is required to recover a function of the source X perfectly in the usual Shannon sense, the El Gamal-Cover (1982) inner bound on the rate distortion region is tight. This finding subsumes the Rimoldi (1994) rate-distortion region for successive refinement of information, the Kaspi (1994) rate-distortion function when side information may be present at the decoder, and the El Gamal-Cover achievable rate region for multiple descriptions with deterministic distortion measures. We have also obtained a new outer bound on the rate-distortion region which enhances the outer bound due to Witsenhausen (1981) and Wyner. This new outer bound implies some interesting facts regarding the achievable rate-distortion vectors. Finally, we pose a multilevel diversity source coding problem for further study.

Svanstrom (see IEEE ibid., vol.43, p.1630-2, Sept. 1997) gave a lower bound on the size of ternary constant-weight codes (CWCs). This bound is generalized and improved in some cases.

The well-known m-out-of-n code /spl Omega//sub n//sup m/ consists of all binary vectors of length n and weight m. It is known that it is good for error detection (in the technical sense, that is, the probability of undetected error P/sub ud/(/spl Omega//sub n//sup m/,p)/spl les/P/sub ud/(/spl Omega//sub n//sup m/,1/2) for all p, 0/spl les/p/spl les/1/2) only for a few small values of m and n. It is therefore of interest to determine (bounds for) the threshold in general, that is, find the range of bit-error probabilities p for which P/sub ud/ (/spl Omega//sub n//sup m/,p)/spl les/P/sub ud/ (/spl Omega//sub n//sup m/,1/2). In this article such bounds are given.

Write-efficient memories (WEMs) were introduced by Ahlswede and Zhang (1989) as a model for storing and updating information on a rewritable medium with cost constraints. We note that the research work of Justesen and Hoholdt (1984) on maxentropic Markov chains actually provide a method for calculating the capacity of WEM. By using this method, we derive a formula for the capacity of WEM with a double-permutation cost matrix. Furthermore, some capacity theorems are established for a special class of WEM called deterministic WEM. We show that the capacity of deterministic WEM is equal to the logarithm of the largest eigenvalue of the corresponding connectivity matrix, it is interesting to note that the deterministic WEM behaves like the discrete noiseless channels of Shannon (1948). By specializing our results, we also obtain some interesting properties for the maximization problem of information functions with multiple variables which are difficult to obtain otherwise. Finally, we present a method for constructing error-correcting codes for WEM with the Hamming distance as the cost function. The covering radius of linear codes plays an important role in the constructions.

The depth distribution of a linear code was recently introduced by T. Etzion (see ibid., vol.43, pp.1361-3, July 1997). In this correspondence, a number of basic and interesting properties for the depth of finite words and the depth distribution of linear codes are obtained. In addition, we study the enumeration problem of counting the number of linear subcodes with the prescribed depth constraints, and derive some explicit and interesting enumeration formulas. Furthermore, we determine the depth distribution of Reed-Muller code RM (m,r). Finally, we show that there are exactly nine depth-equivalence classes for the ternary [11,6,5] Golay codes.

Correlation immune functions and resilient functions play important role in cryptography. The concept of correlation immune functions was first introduced and studied by Siegenthaler (1984). Correlation immune functions are used in stream ciphers as combining functions for running-key generators that are resistant to a correlation attack. We present a number of methods for constructing new resilient functions from old ones. These methods are significant generalizations of some previously known methods. The nonlinearity of some new constructed resilient functions is also discussed.

We study the Hamming distance d/sub H/(X,Y) between two independent identical distributed (i.i.d.) random n-tuples X and Y over some finite set, both lower and upper bounds are derived for the expectation Ed/sub H/(X,Y) and the variance Dd/sub H/(X,Y). Also, a generalization of the Grey-Rankin bound is given.

The generalized write-once memory introduced by Fiat and Shamir (1984) is a q-ary information storage medium. Each storage cell is expected to store one of q symbols, and the legal state transitions are described by an arbitrary directed acyclic graph. This memory model can be understood as a generalization of the binary write-once memory which was introduced by Rivest and Shamir (1982). During the process of updating information, the contents of a cell can be changed from a 0-state to a 1-state but not vice versa. We study the problem of reusing a generalized write-once memory for T successive cycles (generations). We determine the zero-error capacity region and the maximum total number of information hits stored in the memory for T consecutive cycles for the situation where the encoder knows and the decoder does not know the previous state of the memory. These results extend the results of Wolf, Wyner, Ziv, and Korner (1984) for the binary write-once memory.

Hypothesis testing for an arbitrarily varying source (AVS) is considered. We determine the best asymptotic exponent of the probability of error of the second kind when the first kind error probability is less than 2/sup -nr/. This result generalizes the well-known theorem of Hoeffding (1965), Blahut (1974), Csiszar and Longo (1971) for hypothesis testing with an exponential-type constraint. As a corollary in information theory, the best asymptotic error exponent and the r-optimal rate (the minimum compression rate when the error probability is less than 2/sup -nr/, r/spl ges/0) of AVS coding are determined.

Two methods of constructing binary constant-weight codes from (1) codes over GF(q) and (2) constant-weight codes over GF(q) are presented. Several classes of binary optimum constant-weight codes are derived from these methods. In general, we show that binary optimum constant-weight codes, which achieve the Johnson bound, can be constructed from optimum codes over GF(q) which achieve the Plotkin bound. Finally, several classes of optimum constant-weight codes over GF(q) are constructed.

The undetected error probability of binary constant weight codes on a binary symmetric channel is studied in this correspondence. First, we present a necessary condition for the binary constant weight codes to be proper for error detection. Then, by using the necessary condition, we study the error detection capability of binary optimum constant weight codes.