On a Class of Traceability Codes

Traceability codes are designed to be used in schemes that protect copyrighted digital data against piracy. The main aim of this paper is to give an answer to a Staddon–Stinson–Wei's problem of the existence of traceability codes with q< w ² and b>q. We provide a large class of these codes constructed by using a new general construction method for q-ary codes.     

Symplectic spread-based generalized Kerdock codes

Kerdock codes (Kerdock, Inform Control 20:182–187, 1972) are a well-known family of non-linear binary codes with good parameters admitting a linear presentation in terms of codes over the ring (see Nechaev, Diskret Mat 1:123–139, 1989; Hammons et al., IEEE Trans Inform Theory 40:301–319, 1994). These codes have been generalized in different directions: in Calderbank et al. (Proc Lond Math Soc 75:436–480, 1997) a symplectic construction of non-linear binary codes with the same parameters of the Kerdock codes has been given. Such codes are not necessarily equivalent. On the other hand, in Kuzmin and Nechaev (Russ Math Surv 49(5), 1994) the authors give a family of non-linear codes over the finite field F of q = 2 ^l elements, all of them admitting a linear presentation over the Galois Ring R of cardinality q ² and characteristic 2². The aim of this article is to merge both approaches, obtaining in this way new families of non-linear codes over F that can be presented as linear codes over the Galois Ring R. The construction uses symplectic spreads.      

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

Codes with the identifiable parent property for multimedia fingerprinting

Let \({\mathcal {C}}\) be a q-ary code of length n and size M, and \({\mathcal {C}}(i) = \{\mathbf{c}(i) \ | \ \mathbf{c}=(\mathbf{c}(1), \mathbf{c}(2), \ldots , \mathbf{c}(n))^{T} \in {\mathcal {C}}\}\) be the set of ith coordinates of \({\mathcal {C}}\). The descendant code of a sub-code \({\mathcal {C}}^{'} \subseteq {\mathcal {C}}\) is defined to be \({\mathcal {C}}^{'}(1) \times {\mathcal {C}}^{'}(2) \times \cdots \times {\mathcal {C}}^{'}(n)\). In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or t-MIPPC(n, M, q), so that given the descendant code of any sub-code \({\mathcal {C}}^{'}\) of a multimedia t-IPP code \({\mathcal {C}}\), one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in \({\mathcal {C}}^{'}\). We first derive a general upper bound on the size M of a multimedia t-IPP code, and then investigate multimedia 3-IPP codes in more detail. We characterize a multimedia 3-IPP code of length 2 in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia 3-IPP code of length 2, and construct several infinite families of (asymptotically) optimal multimedia 3-IPP codes of length 2.     

A new concatenated type construction for LCD codes and isometry codes

We give a new concatenated type construction for linear codes with complementary dual (LCD) over small finite fields. In this construction,we need a special class of inner codes that we call isometry codes. Our construction generalizes a recent construction of Carlet et al. (2014–2016) and of Güneri et al. (2016). In particular, it allows us to construct LCD codes with improved parameters directly.     

Explicit constructions of separating hash families from algebraic curves over finite fields

Let X be a set of order n and Y be a set of order m. An (n,m,{w ₁, w ₂})-separating hash family is a set of N functions from X to Y such that for any with , |X ₁| = w ₁ and |X ₂| = w ₂, there exists an element such that . In this paper, we provide explicit constructions of separating hash families using algebraic curves over finite fields. In particular, applying the Garcia–Stichtenoth curves, we obtain an infinite class of explicitly constructed (n,m,{w ₁,w ₂})–separating hash families with for fixed m, w ₁, and w ₂. Similar results for strong separating hash families are also obtained. As consequences of our main results, we present explicit constructions of infinite classes of frameproof codes, secure frameproof codes and identifiable parent property codes with length where n is the size of the codes. In fact, all the above explicit constructions of hash families and codes provide the best asymptotic behavior achieving the bound , which substantially improve the results in [ 8, 15, 17] give an answer to the fifth open problem presented in [11].     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Construction of MDS self-dual codes over Galois rings

The purpose of this paper is to construct nontrivial MDS self-dual codes over Galois rings. We consider a building-up construction of self-dual codes over Galois rings as a GF(q)-analogue of (Kim and Lee, J Combin Theory ser A, 105:79–95). We give a necessary and sufficient condition on which the building-up construction holds. We construct MDS self-dual codes of lengths up to 8 over GR(3²,2), GR(3³,2) and GR(3⁴,2), and near-MDS self-dual codes of length 10 over these rings. In a similar manner, over GR(5²,2), GR(5³,2) and GR(7²,2), we construct MDS self-dual codes of lengths up to 10 and near-MDS self-dual codes of length 12. Furthermore, over GR(11²,2) we have MDS self-dual codes of lengths up to 12.      

Vectorial Resilient PC（l） of Order k Boolean Functions from AG-Codes

Propagation criteria and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1–4, 7, 8, 10, 11, 16]). Kurosawa, Stoh [8] and Carlet [1] gave a construction of Boolean functions satisfying PC(l) of order k from binary linear or nonlinear codes. In this paper, the algebraic-geometric codes over GF(2m) are used to modify the Carlet and Kurosawa-Satoh’s construction for giving vectorial resilient Boolean functions satisfying PC(l) of order k criterion. This new construction is compared with previously known results.     

Approximating Huffman codes in parallel

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) with n/logn processors, if the elements are sorted.     

On constant composition codes

A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword is the same for each codeword. These specialize to constant weight codes in the binary case, and permutation codes in the case that each symbol occurs exactly once. Constant composition codes arise in powerline communication and balanced scheduling, and are used in the construction of permutation codes. In this paper, direct and recursive methods are developed for the construction of constant composition codes.     

New Linear Codes with Covering Radius 2 and Odd Basis

On the way of generalizing recent results by Cock and the second author, it is shown that when the basis q is odd, BCH codes can be lengthened to obtain new codes with covering radius R=2. These constructions (together with a lengthening construction by the first author) give new infinite families of linear covering codes with codimension r=2k+1 (the case q=3, r=4k+1 was considered earlier). New code families with r=4k are also obtained. An updated table of upper bounds on the length function for linear codes with 24, R=2, and q=3,5 is given.     

Inhomogeneous quantum codes (II): non-additive case

The quantum codes have been generalized to inhomogeneous case and the stabilizer construction has been established to get additive inhomogeneous quantum codes in [Sci. China Math., 2010, 53: 2501–2510]. In this paper, we generalize the known constructions to construct non-additive inhomogeneous quantum codes and get examples of good d-ary quantum codes.     

On the construction of prefix-free and fix-free codes with specified codeword compositions

We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimize the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost.     

On repeated-root multivariable codes over a finite chain ring

In this work we consider repeated-root multivariable codes over a finite chain ring. We show conditions for these codes to be principally generated. We consider a suitable set of generators of the code and compute its minimum distance. As an application we study the relevant example of the generalized Kerdock code in its r-dimensional cyclic version.      

Linear Codes with Non-Uniform Error Correction Capability

This paper introduces a class of linear codes which are non-uniform error correcting, i.e. they have the capability of correcting different errors in different code words. A technique for specifying error characteristics in terms of algebraic inequalities, rather than the traditional spheres of radius e, is used. A construction is given for deriving these codes from known linear block codes. This is accomplished by a new method called parity sectioned reduction. In this method, the parity check matrix of a uniform error correcting linear code is reduced by dropping some rows and columns and the error range inequalities are modified.     

Coprimitive sets and inextendable codes

Complete (n,r)-arcs in PG(k−1,q) and projective (n,k,n−r) _q -codes that admit no projective extensions are equivalent objects. We show that projective codes of reasonable length admit only projective extensions. Thus, we are able to prove the maximality of many known linear codes. At the same time our results sharply limit the possibilities for constructing long non-linear codes. We also show that certain short linear codes are maximal. The methods here may be just as interesting as the results. They are based on the Bruen–Silverman model of linear codes (see Alderson TL (2002) PhD. Thesis, University of Western Ontario; Alderson TL (to appear) J Combin Theory Ser A; Bruen AA, Silverman R (1988) Geom Dedicata 28(1): 31–43; Silverman R (1960) Can J Math 12: 158–176) as well as the theory of Rédei blocking sets first introduced in Bruen AA, Levinger B (1973) Can J Math 25: 1060–1065.      

Galois LCD codes over finite fields

In this paper, we generalize the linear complementary dual codes (LCD codes for short) to k-Galois LCD codes, and study them by a uniform method. A necessary and sufficient condition for linear codes to be k-Galois LCD codes is obtained, two classes of k-Galois LCD MDS codes are exhibited. Then, necessary and sufficient conditions for λ-constacyclic codes being k-Galois LCD codes are characterized. Some classes of k-Galois LCD λ-constacyclic MDS codes are constructed. Finally, we study Hermitian LCD λ-constacyclic codes, and present a class of Hermitian LCD λ-constacyclic MDS codes.     

Estimating a mean matrix: boosting efficiency by multiple affine shrinkage

The unknown matrix M is the mean of the observed response matrix in a multivariate linear model with independent random errors. This paper constructs regularized estimators of M that dominate, in asymptotic risk, least squares fits to the model and to specified nested submodels. In the first construction, the response matrix is expressed as the sum of orthogonal components determined by the submodels; each component is replaced by an adaptive total least squares fit of possibly lower rank; and these fits are then summed. The second, lower risk, construction differs only in the second step: each orthogonal component is replaced by a modified Efron-Morris fit before summation. Singular value decompositions yield computable formulae for the estimators and their asymptotic and estimated risks. In the asymptotics, the row dimension of M tends to infinity while the column dimension remains fixed. Convergences are uniform when signal-to-noise ratio is bounded. This research was supported in part by National Science Foundation Grant DMS 0404547.     

Optical orthogonal codes and arcs in

We present a new construction for (n,w,λ)-optical orthogonal codes (OOCs). The construction is pleasingly simple, where codewords correspond to arcs, specifically normal rational curves. Moreover, our construction yields for each λ>1 an infinite family of OOCs which are asymptotically optimal (with respect to the Johnson bound).