pseudo-random array is a two-dimensional array in which eachn1×n2nonzero matrix is contained exactly once as a window in the array. The pseudo-random arrays we consider have many desirable properties in addition, such as the shift-and-add-property, i.e., the addition of the array to any of its nontrivial shifts is another nontrivial shift of the array. A pseudorandom array code is a linear code ofr1×r2arrays in which eachn1×n2nonzero matrix is contained exactly once as a window in one of the arrays. In this paper, new parameters for pseudo-random arrays are presented, and their construction is generalized to pseudo-random array codes. Our constructions of pseudo-random array codes are based on the folding of sequences. Two techniques to verify whether an array or a set of arrays constructed by folding is a pseudo-random array or a pseudo-random array code, respectively, are presented. These verification techniques can also be used for VLSI testing.

The Additive-Multiplicative Matrix Channel (AMMC) was introduced by Silva, Kschischang and Kötter in 2010 to model data transmission using random linear network coding. The input and output of the channel are$n\times m$matrices over a finite field$\mathbb {F}_{q}$. When the matrix X is input, the channel outputs$Y=A(X+W)$where A is a uniformly chosen$n\times n$invertible matrix over$\mathbb {F}_{q}$and where W is a uniformly chosen$n\times m$matrix over$\mathbb {F}_{q}$of rank t. Silva et al. considered the case when$2n\leq m$. They determined the asymptotic capacity of the AMMC when t, n and m are fixed and$q\rightarrow \infty $. They also determined the leading term of the capacity when q is fixed, and t, n and m grow linearly. We generalise these results, showing that the condition$2n\geq m$can be removed. (Our formula for the capacity falls into two cases, one of which generalises the$2n\geq m$case.) We also improve the error term in the case when q is fixed.

Non-overlapping codes have been studied for almost 60 years. In such a code, no proper, non-empty prefix of any codeword is a suffix of any codeword. In this paper, we study codes in which over-laps of certain specified sizes are forbidden. We prove some general bounds and we give several constructions in the case of binary codes. Our techniques also allow us to provide an alternative, elementary proof of a lower bound on non-overlapping codes due to Levenshtein [9] in 1964.

In 2010, Silva et al. studied certain classes of finite-field matrix channels in order to model random linear network coding where exactly t random errors are introduced. In this paper, we consider a generalization of these matrix channels where the number of errors is not required to be constant, indeed the number of errors may follow any distribution. We show that a capacity-achieving input distribution can always be taken to have a very restricted form (the distribution should be uniform given the rank of the input matrix). This result complements, and is inspired by a paper of Nobrega et al., which establishes a similar result for a class of matrix channels that model network coding with link erasures. Our result shows that the capacity of our channels can be expressed as maximization over probability distributions on the set of possible ranks of input matrices: a set of linear rather than exponential size.

There has been much recent interest in private information retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being a simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy, and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient PIR protocols. In this paper, we are interested in designing PIR array codes. We consider the case when we have m servers, with each server storing a fraction (1/s) of the bits of the database; here s is a fixed rational number with s > 1. A PIR array code with the k-FIR property enables a k-server PIR protocol (with k ≤ m) to be emulated on m servers, with the overall storage requirements of the protocol being reduced. The communication complexity of a PIR protocol reduces as k grows, so the virtual server rate, defined to be k/m, is an important parameter. We study the maximum virtual server rate of a PIR array code with the k-PIR property. We present upper bounds on the achievable virtual server rate, some constructions, and ideas how to obtain the PIR array codes with the highest possible virtual server rate. In particular, we present constructions that asymptotically meet our upper bounds and the exact largest virtual server rate is obtained when 1 <; s ≤ 2. A k-PIR code (and similarly a k-PIR array code) is also a locally repairable code with symbol availability k-1. Such a code ensures k parallel reads for each information symbol. So the virtual server rate is very closely related to the symbol availability of the code when used as a locally repairable code. The results of this paper are discussed also in this context where subspace codes also have an important role.

There has been much recent interest in Private information Retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient protocols. In this paper we are interested in designing PIR array codes. We consider the case when we have m servers, with each server storing a fraction (1/s) of the bits of the database; here s is a fixed rational number with s > 1. We study the maximum PIR rate of a PIR array code with the k-PIR property (which enables a k-server PIR protocol to be emulated on the m servers), where the PIR rate is defined to be k/m. We present upper bounds on the achievable rate, some constructions, and ideas how to obtain PIR array codes with the highest possible PIR rate. In particular, we present constructions that asymptotically meet our upper bounds, and the exact largest PIR rate is obtained when 1 <; s ≤ 2.

In the classical model for (information theoretically secure) Private Information Retrieval (PIR) due to Chor, Goldreich, Kushilevitz and Sudan, a user wishes to retrieve one bit of a database that is stored on a set of n servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise the total communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into R-bit records with R 1, and the user wishes to retrieve one record rather than one bit. When R is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Work of Shah, Rashmi and Ramchandran shows that at least R + 1 bits must be downloaded from servers in the worst case, and provides PIR schemes meeting this bound. Sun and Jafar have considered the download cost of a scheme, defined as the ratio of the message length R and the total number of bits downloaded. They determine the best asymptotic download cost of a PIR scheme (as R → ∞) when a database of k messages is stored by n servers. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number n of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes. These constructions include explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average.

Immink and Weber recently defined and studied a channel with both gain and offset mismatch, modeling the behavior of charge-leakage in flash memory. They proposed a decoding measure for this channel based on minimizing Pearson distance (a notion from cluster analysis). This paper derives a formula for maximum likelihood decoding for this channel, and also defines and justifies a notion of minimum distance of a code in this context.

The Pearson distance has been advocated for improving the error performance of noisy channels with unknown gain and offset. The Pearson distance can only fruitfully be used for sets of q-ary codewords, called Pearson codes, that satisfy specific properties. We will analyze constructions and properties of optimal Pearson codes. We will compare the redundancy of optimal Pearson codes with the redundancy of prior art T-constrained codes, which consist of q-ary sequences in which T pre-determined reference symbols appear at least once. In particular, it will be shown that for q ≤ 3, the two-constrained codes are optimal Pearson codes, while for q ≥ 4 these codes are not optimal.

We say that a q-ary length n code is non-overlapping if the set of non-trivial prefixes of codewords and the set of non-trivial suffices of codewords are disjoint. These codes were first studied by Levenshtein in 1964, motivated by applications in synchronization. More recently these codes were independently invented (under the name cross-bifix-free codes) by Bajic and Stojanovic. We provide a simple construction for a class of non-overlapping codes which has optimal cardinality whenever n divides q. Moreover, for all parameters n and q, we show that a code from this class is close to optimal, in the sense that it has cardinality within a constant factor of an upper bound due to Levenshtein from 1970. Previous constructions have cardinality within a constant factor of the upper bound only when q is fixed. Chee, Kiah, Purkayastha, and Wang showed that a q-ary length n non-overlapping code contains at most qn/(2n-1) codewords; this bound is weaker than the Levenshtein bound. Their proof appealed to the application in synchronization: we provide a direct combinatorial argument to establish the bound of Chee et al. We also consider codes of short length, finding the leading term of the maximal cardinality of a non-overlapping code when n is fixed and q → ∞. The largest cardinality of non-overlapping codes of lengths 3 or less is determined exactly.

Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, t̅-separable codes lie somewhere between t-frameproof and (t - 1)-frameproof codes: all t-frameproof codes are t̅-separable, and all t̅-separable codes are (t - 1)-frameproof. Results for frameproof codes show that (when q is large) there are q-ary t̅-separable codes of length n with approximately q[n/t]codewords, and that no q-ary t̅-separable codes of length n can have more than approximately q[n/(t-l)]codewords. This paper provides improved probabilistic existence results for t-separable codes when t ≥ 3. More precisely, for all t ≥ 3 and all n ≥ 3, there exists a constant κ (depending only on t and n), such that there exists a q-ary t̅-separable code of length n with at least κqn/(t-1)codewords for all sufficiently large integers q. This shows, in particular, that the upper bound [derived from the bound on (t - 1)-frameproof codes] on the number of codewords in a t̅-separable code is realistic. The results above are more surprising after examining the situation when t = 2. Results due to Gao and Ge show that a q-ary 2̅-separable code of length n can contain at most 3/2q2[n/3]- 1/2q[n/3]codewords, and that codes with at least κq2n/3codewords exist. Thus, optimal 2̅-separable codes behave neither like two-frameproof nor one-frameproof codes. This paper also observes that the bound of Gao and Ge can be strengthened to show that the number of codewords of a q-ary 2̅-separable code of length n is at most q[2n/3]+ 1/2 q[n/3](q[n/3]-1).

The iterated Johnson bound is the best known upper bound on the size of an error-correcting code in the GrassmannianGq(n,k). The iterated Schönheim bound is the best known lower bound on the size of a covering code inGq(n,k). We prove that both bounds are asymptotically attained for fixedkand fixed radius, asnapproaches infinity. Our methods rely on results from the theory of quasi-random hypergraphs which are proved using probabilistic techniques. We also determine the asymptotics of the size of the best Grassmannian codes and covering codes whenn-kand the radius are fixed, asnapproaches infinity.

A two-dimensional (2-D) grid with dots is called aconfiguration with distinct differencesif any two lines which connect two dots are distinct either in their length or in their slope. These configurations are known to have many applications such as radar, sonar, physical alignment, and time-position synchronization. Rather than restricting dots to lie in a square or rectangle, as previously studied, we restrict the maximum distance between dots of the configuration; the motivation for this is a new application of such configurations to key distribution in wireless sensor networks. We consider configurations in the hexagonal grid as well as in the traditional square grid, with distances measured both in the Euclidean metric, and in the Manhattan or hexagonal metrics. We note that these configurations are confined inside maximal anticodes in the corresponding grid. We classify maximal anticodes for each diameter in each grid. We present upper bounds on the number of dots in a pattern with distinct differences contained in these maximal anticodes. Our bounds settle (in the negative) a question of Golomb and Taylor on the existence of honeycomb arrays of arbitrarily large size. We present constructions and lower bounds on the number of dots in configurations with distinct differences contained in various 2-D shapes (such as anticodes) by considering periodic configurations with distinct differences in the square grid.

A distinct difference configuration is a set of points in$\BBZ ^{2}$with the property that the vectors (difference vectors) connecting any two of the points are all distinct. Many specific examples of these configurations have been previously studied: the class of distinct difference configurations includes both Costas arrays and sonar sequences, for example. Motivated by an application of these structures in key predistribution for wireless sensor networks, we define the$k$-hop coverage of a distinct difference configuration to be the number of distinct vectors that can be expressed as the sum of$k$or fewer difference vectors. This is an important parameter when distinct difference configurations are used in the wireless sensor application, as this parameter describes the density of nodes that can be reached by a short secure path in the network. We provide upper and lower bounds for the$k$-hop coverage of a distinct difference configuration with$m$points, and exploit a connection with$B_{h}$sequences to construct configurations with maximal$k$-hop coverage. We also construct distinct difference configurations that enable all small vectors to be expressed as the sum of two of the difference vectors of the configuration, an important task for local secure connectivity in the application.

Let $\cal C$ be a code of length n over an alphabet of size q. A word $\mathbf{d}$ is a descendant of a pair of codewords $\mathbf{x},\mathbf{y} \in \cal C$ if $d_i \in \{x_i ,y_i \}$ for $1 \leq i \leq n$. A code $\cal C$ is an identifiable parent property (IPP) code if the following property holds. Whenever we are given $\cal C$ and a descendant $\mathbf{d}$ of a pair of codewords in $\cal C$, it is possible to determine at least one of these codewords. The paper introduces the notion of a prolific IPP code. An IPP code is prolific if all $q^n$ words are descendants. It is shown that linear prolific IPP codes fall into three infinite (“trivial”) families, together with a single sporadic example which is ternary of length 4. There are no known examples of prolific IPP codes which are not equivalent to a linear example: the paper shows that for most parameters there are no prolific IPP codes, leaving a relatively small number of parameters unsolved. In the process the paper obtains upper bounds on the size of a (not necessarily prolific) IPP code which are better than previously known bounds.

A binary array is a (d1,k1,d2,k2) runlength constrained array if the runs of zeros in every row and column have length at least d1and at most k1, and the runs of ones in every row and column have length at least d2and at most k2. Such arrays arise in the context of digital storage devices. Writing N(m,n|d1,k1,d2,k2) for the number of (d1,k1,d2,k2) runlength constrained arrays of size mtimesn, the capacity C(d1,k1,d2,k2) is defined to be limm,nrarrinfin(1/mn)log2N(m,n|d1,k1,d2,k2). Let d2be an integer such that d2ges 1. The paper shows that C(1,d2+delta,d2,d2) is positive when delta ges 2, but is zero when delta les 1

Frameproof codes were first introduced by Boneh and Shaw in the context of digital fingerprinting. Variants of these codes have been studied by several authors, and several similar definitions of frameproof codes exist in the literature. The paper considers frameproof codes from a combinatorial point of view, where we define frameproof codes as follows. Let F be a (finite) set, and let $P\subseteq F^\ell$ be a set of words of length $\ell$ over the alphabet F. The set of descendants of P, desc$(P)$, is the set of all words $x\in F^\ell$ such that for all $i\in\{1,2,\ldots ,\ell\}$, the ith component of x agrees with the ith component of some member of P. Let c be an integer such that $c\geq 2$. A c-frameproof code is a subset $C\subseteq F^\ell$ such that for all $P\subseteq C$ with $|P|\leq c$, we have that desc$(P)\cap C= P$. The paper considers the following question: What is the largest cardinality n of a c-frameproof code of length $\ell$, over an alphabet of size q? The paper concentrates on the case when q is large. The paper shows that $n=\ell(q-1)$ in the case when $2\leq \ell\leq c$ and shows that if c=2, then n is approximately $t q^{\lceil \ell/2\rceil}$, where t=1 when $\ell$ is odd and t=2 if $\ell$ is even. The paper establishes improved upper bounds on n by applying techniques from extremal set theory (namely, a generalization of the Erdos--Ko--Rado theorem).

The self-shrinking generator, a stream cipher due to Meier and Staffelbach (see Advances in Cryptology-EUROCRYPT'94, Berlin, Germany, p.205-14, 1995 and Lecture Notes in Computer Science, vol.950), uses the output of a primitive binary linear-feedback shift register (LFSR) of length n to generate a keystream sequence of period dividing 2/sup n-1/. The article proves that the linear complexity of the keystream is at most 2/sup n-1/-(n-2). This confirms the surprising experimental observations of Meier and Staffelbach.

This paper argues that the cipher systems based on cellular automata (CA) proposed by S. Nandi et al. (1994) are affine and are insecure. A reply by S. Nandi and P. Pal Chaudhuri is given. The reply emphasizes the point that the regular, modular, cascadable structure of local neighborhood CA can be employed for building low cost cipher system hardware. This cost effective engineering solution can achieve desired level of security with larger size CA.

An asymptotically fast algorithm for solving the generalized rational interpolation problem is presented. This problem has been studied as part of system theory and is related to the solution of the classical and Welch-Berlekamp (1983) key equations which arise in Reed-Solomon decoding. The algorithm can also be used to compute the linear complexity profile of a binary sequence of length m using only O(m(log m)/sup 2/ log log m) bit operations.

Fitzpatrick's algorithm for solving the classical Reed-Solomon key equation is shown to be related to an algorithm for solving the Welch-Berlekamp key equation. It can be made more efficient when decoding binary BCH codes. Its efficiency is about the same as for the Berlekamp-Massey algorithm.

Let s be a periodic sequence whose elements lie in a finite field. The authors present an algorithm that calculates the minimal polynomial of s, assuming that a period of s is known. The algorithm generalises both the discrete Fourier transform and the Games-Chan algorithm.>