We investigate uniquely decodable match-length functions (MLFs) in conjunction with Lempel-Ziv (1977) type data compression. An MLF of a data string is a function that associates a nonnegative integer with each position of the string. The MLF is used to parse the input string into phrases. The codeword for each phrase consists of a pointer to the beginning of a maximal match consistent with the MLF value at that point. We propose several sliding-window variants of LZ compression employing different MLF strategies. We show that the proposed methods are asymptotically optimal for stationary ergodic sources and that their convergence compares favorably with the LZ1 variant of Wyner and Ziv (see Proc. IEEE, vol.82, no.6, p.872, 1994).

A pair of real-valued sequences A=(a/sub 1/,a/sub 2/,...,a/sub N/) and B=(b/sub 1/,b/sub 2/,...,b/sub N/) is called complementary if the sum R(/spl middot/) of their autocorrelation functions R/sub A/(/spl middot/) and R/sub B/(/spl middot/) satisfies R(/spl tau/)=R/sub A/(/spl tau/)+R/sub B/(/spl tau/)=/spl Sigma//sub i=1//sup N$/ -/sup /spl tau//a/sub i/a/sub i+/spl tau//+/spl Sigma//sub j=1//sup N-/spl tau//b/sub j/b/sub j+/spl tau//=0, /spl forall//spl tau//spl ne/0. In this paper we introduce a new family of complementary pairs of sequences over the alphabet /spl alpha//sub 3/=+{1,-1,0}. The inclusion of zero in the alphabet, which may correspond to a pause in transmission, leads both to a better understanding of the conventional binary case, where the alphabet is /spl alpha//sub 2/={+1,-1}, and to new nontrivial constructions over the ternary alphabet /spl alpha//sub 3/. For every length N, we derive restrictions on the location of the zero elements and on the form of the member sequences of the pair. We also derive a bound on the minimum number of zeros necessary for the existence of a complementary pair of length N over /spl alpha//sub 3/. The bound is tight, as it is met by some of the proposed constructions, for infinitely many lengths.>

The authors propose a general model for a sequential coder, and investigate the associated coding delay. This model is employed to derive lower and upper bounds on the delay associated with commonly used encoders and decoders for noiseless data compression.>

The estimation and universal compression of discrete sources are considered, and a sequential algorithm for the universal coding of finite memory sources, attaining asymptotically minimum redundancy, is presented. The algorithm performs an online estimation of the source states and uses an arithmetic code.>

The authors consider the problem of ordering strings of a fixed length over a discrete alphabet according to decreasing probabilities of having been emitted by an unknown finite-state source. Data compression is applied to derive a universal algorithm that solves this problem with an optimal asymptotic performance. This result is employed in the solution of the following problem: discriminate an individual sequence as emitted by an independently identically distributed random source of equally likely symbols or as a signal corrupted by noise. Tight lower and upper bounds on the asymptotic performance of finite-state discriminators are given.>

Motivated by the study of various kinds of machines as recognizers of formal languages, the authors compare the encoding and decoding power of finite state sequential machines and extensions thereof. They show that, with a forward moving head, the best compression achievable for a given sequence, to be decoded by a finite state decoder, is the same as the best ratio attainable for that sequence when encoded by a finite state information lossless encoder. They cannot gain in compression by allowing a finite state encoder to move its head back and forth on an input sequence, even if the decoder has unrestricted power. However, better compression can be achieved for specific infinite sequences using an unrestricted encoder and a two-way finite state decoder.>

The authors consider the problem of ordering of strings of a fixed length over a discrete alphabet, according to decreasing probabilities of having been emitted by an unknown finite-state source. Data compression is applied to derive a universal algorithm that solves this problem with an optimal asymptotic performance. The result is applied to discriminate an individual sequence as emitted by an i.i.d. random source or as a signal corrupted by noise. Tight lower and upper bounds on the asymptotic performance of finite-state discriminators are given.>

Explicit formulas are given for sets of p elements forming a self-complementary normal basis of GF(q/sup p/) over GF(q), where p is the characteristic of GF(q). Using these formulas, a straightforward construction of self-complementary bases for GF(q/sup alpha /) (where alpha =p/sup m/) over GF(q) is also presented.>

Distortion-free compressibility of individual pictures by finite-state encoders is investigated. In a recent paper (see IEEE Trans. Inform. Theory, vol.32, no.1, p.1-8, 1986) the compressibility of a given picture I was defined and shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved for I by any finite-state encoder. Here, a different and more direct approach is taken to prove similar results, which are summarized in a converse-to-coding theorem and a constructive-coding-theorem that leads to a universal asymptotically optimal compression algorithm.>

The Fourier transform technique is used to analyze and construct several families of double-circulant codes. The minimum distance of the resulting codes is lower-bounded by 2 square root r and can be decoded easily employing the standard BCH decoding algorithm or the majority-logic decoder of Reed-Muller codes. A decoding procedure for Reed-Solomon codes is presented, based on a representation of the parity-check matrix by circulant blocks. The decoding procedure inherits both the (relatively low) time complexity of the Berlekamp-Massey algorithm and the hardware simplicity characteristic of Blahut's algorithm. The procedure makes use of the encoding circuit together with a reduced version of Blahut's decoder.>

A construction is presented of long maximum-distance-separable (MDS) codes that are not generalized Reed-Solomon (GRS) type. The construction uses subsets S, mod S mod =m of a finite field F=GF(q) with the property that no t distinct elements of S add up to some fixed element of F. Large subsets of this kind are used to construct (n=m+2, k=t+1) non-GRS MDS codes over F.>

A special form of Cauchy matrix is used to obtain a tighter bound for the validity region of the maximum distance separable (MDS) conjecture and a new compact characterization of generalized Reed-Solomon codes. The latter is further used to obtain constructions and some existence results for long (2k, k) double-circulant MDS codes.>

It is shown that $\mathrm{GF} ( q^n )$ has a self complementary normal basis over $\mathrm{GF} ( q )$ if and only if n is odd or $n \equiv 2(\bmod{\text{-}}4)$ and q is even. All existence proofs are constructive and can be readily employed to obtain such bases.

It is shown that good linear (n,k,d) codes over a finite field GF(q) can be constructed by concatenating the generator matrices of Reed-Solomon codes. For the case of k=3, it is shown that many of the codes obtained using projective-geometry techniques can readily be obtained by the proposed algebraic approach.>

This paper presents an algorithm for generating all the permutations defined by linear transformations on a shuffle-exchange network of $2^n $ processors in $2n - 1$ passes. The proposed algorithm generates any such permutation in $O(n\log ^2 n)$ elementary steps. The subclass of bit-permutations is generated in $O(n)$ steps.

In certain applications it is necessary to communicate a description of a sequence of events where the information of interest is which one of a set of possible events has occurred, including multiplicity, but where the order of occurrence is irrelevant. Typical examples are online compilations of inventories, construction of histograms, or updating of relative frequencies. Suitable codes for this purpose need not be uniquely decipherable (UD). In fact, all that is required of such a code is that given a finite message over the code, every possible parsing of the message into codewords must yield the same multiset of codewords. A code with this property is referred to as a multiset decipherable (MSD) code. An MSD code is said to be proper if it is not a UD code. It is shown that for everyn > 3there exist proper MSD codes withnwords. Forn=2, every MSD code is necessarily a UD code and all evidence points to the same conclusion forn=3. It is further shown that no MSD code contains a full prefix code or a full suffix code as a proper subcode, and it is conjectured that despite the weaker decipherability condition, every MSD code satisfies the Kraft Inequality.

Distortion-free compressibility of individual pictures, i.e., two-dimensional arrays of data, by finite-state encoders is investigated. For every individual infinite pictureI, a quantity\rho(I)is defined, called the compressibility ofI, which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved forIby any finite-state information-lossless encoder. This is demonstrated by means of a constructive coding theorem and its converse that, apart from their asymptotic significance, might also provide useful criteria for finite and practical data-compression tasks. The proposed picture compressibility is also shown to possess the properties that one would expect and require of a suitably defined concept of two-dimensional entropy for arbitrary probabilistic ensembles of infinite pictures. While the definition of\rho(I)allows the use of different machines for different pictures, the constructive coding theorem leads to a universal compression scheme that is asymptotically optimal for every picture. The results are readily extendable to data arrays of any finite dimension.

A test sequence is called(s,t)-universal if it exercises every function depending on t or fewer inputs on a very large scale integration (VLSI) chip withsinputs. Randomized and deterministic procedures are deseribed for the design of(s,t)-universal sequences and for the signature analysis of the test outputs.

Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates2^{k \cdot g(n,k)full cycles of length2^{n}, using3n + k \cdot g(n, k)bits of storage, wherekis a free parameter in the range1 \leq k \leq 2^{((n-4)/2)}, andg(n, k)is of the order ofn - 2 \log k. The second algorithm generates about2^{n^{2}/4}full cycles of length2^{n}, using aboutn^{2}/2bits of storage. In both algorithms, the time required to produce the next bit from the lastnbits is close ton. A possible application to the construction of stream ciphers is indicated.

The distribution\gamma (c, n)of de Bruijn sequences of ordernand linear complexitycis investigated. It is shown that forn \geq 4, \gamma (2^{n} - 1, n) \equiv 0 \pmod{8}, and fork \geq 3, \gamma (2^{2k} - 1,2k) \equiv 0 \pmod{l6}. It is also shown that\gamma (c, n) \equiv 0 \pmod{4}for allc, andn \geq 3such thatcnis even.

It is well known that the linear complexity of a de Bruijn sequenceSof length2^{n}is bounded below by2^{n- 1} + nforn \geq 3. It is shown that this lower bound is attainable for alln.

We present an efficient maximum likelihood decoding algorithm for the punctured binary Reed-Muller code of order(m - 3)and length2^{m} - 1, M \geq 3, and we give formulas for the weight distribution of coset leaders of such codes.

Randomized protocols for signing contracts, certified mail, and flipping a coin are presented. The protocols use a 1-out-of-2 oblivious transfer subprotocol which is axiomatically defined. The 1-out-of-2 oblivious transfer allows one party to transfer exactly one secret, out of two recognizable secrets, to his counterpart. The first (second) secret is received with probability one half, while the sender is ignorant of which secret has been received. An implementation of the 1-out-of-2 oblivious transfer, using any public key cryptosystem, is presented.

In a recent paper Olsen, Scholtz, and Welch (OSW) describe the use of bent functions to construct families of sequences with asymptotically optimal correlation properties. We show that the sequences produced by the OSW construction possess the claimed correlation properties if and only if the underlying bent functions are pairwise orthogonal. Consequently, the cardinality of a family of OSW sequences of length2^{n}-1cannot exceed2^{n/2}. We also describe methods of selecting a maximal set of orthogonal bent functions.

A(k/n)code is a uniquely decipherable scheme mapping source words of lengthkinto channel words of lengthn. In a look-ahead code the encoding and/or decoding of a current word may depend on upcoming, as well as past, symbols. Given an\theta-ary source, a channel of

It is shown that a lower hound ofn^{3}or more on the straight-line complexity of a functionfover GF(2^{n})is also a lower bound on the network complexity offand, hence, on the product of run time and program size of Turing machines. It is further shown that most functions over a finite field are hard to compute and that for most hard functions there exists no approximation via an easy algorithm.

It is shown that every symmetric matrix A, with entries from a finite field F, can be factored over F into $A = BB'$, where the number of columns of B is bounded from below by either the rank $\rho (A)$ of A, or by $1 + \rho (A)$, depending on A and on the characteristic of F This result is applied to show that every finite extension $\Phi $ of a finite field F has a trace-orthogonal basis over F. Necessary and sufficient conditions for the existence of a trace-orthonormal basis are also given. All proofs are constructive, and can be utilized to formulate procedures for minimal factorization and basis construction.

Compressibility of individual sequences by the class of generalized finite-state information-lossless encoders is investigated. These encoders can operate in a variable-rate mode as well as a fixed-rate one, and they allow for any finite-state scheme of variable-length-to-variable-length coding. For every individual infinite sequencexa quantity\rho(x)is defined, called the compressibility ofx, which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved forxby any finite-state encoder. This is demonstrated by means of a constructive coding theorem and its converse that, apart from their asymptotic significance, also provide useful performance criteria for finite and practical data-compression tasks. The proposed concept of compressibility is also shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences. While the definition of\rho(x)allows a different machine for each different sequence to be compressed, the constructive coding theorem leads to a universal algorithm that is asymptotically optimal for all sequences.

The equivalence ofM-sequence matrices to Walsh-Hadamard matrices can be exploited to take advantage of the latter's fast transform algorithm. The nature of the obvious equivalence, its relation to theM-sequence and its implementation as address modifications realized by linear feedback shift-registers are discussed.

The construction of a class of balanced binary sequences with optimal autocorrelation properties is described. Given any odd primepand any positive integerm, a balanced( \pm 1)binary sequence of lengthp^{m} - 1whose cyclic autocorrelation functionc (\tau)satisfiesc (0) = p^{m} - 1, and, for\tau \neq 0, c (\tau) = +2or-2when(p^{m} - 1)/2is odd, andc(\tau) = 0or-4when(p^{m} - 1)/2is even is constructed. Optimality is proved by showing that every balanced binary sequence has at least two distinct out-of-phase correlation values which are at least as large as those obtained here.

A correspondence between linear(n,k,d)codes and algorithms for computing a system\psiofkbilinear forms is established under which the codelengthnis equal to the multiplicative complexity of the algorithm for computing\psi, and the code distancedis underbounded by the minimum number of multiplications required to compute any linear combination of thekforms in\psi. This hitherto unexplored approach to linear codes holds promise of a better understanding of the structure of existing codes as well as for methods of constructing new codes with prescribed rate and distance.

A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source.

A new approach to the problem of evaluating the complexity ("randomness") of finite sequences is presented. The proposed complexity measure is related to the number of steps in a self-delimiting production process by which a given sequence is presumed to be generated. It is further related to the number of distinct substrings and the rate of their occurrence along the sequence. The derived properties of the proposed measure are discussed and motivated in conjunction with other well-established complexity criteria.

The main result of this paper is a theorem showing that every binary, symmetric matrix A can be factored over $GF(2)$ into $A = BB'$, where the number of columns of B is bounded from below by either the rank $\rho (A)$ of A, or by $\rho (A) + 1$, depending on whether at least one, or none, of the main-diagonal entries of A is nonzero. An algorithm for a minimal factorization of a given matrix A and an application of this result for finding a trace-orthogonal basis of $GF(2^n )$ are presented.

We consider the spectral properties of the first difference of two-level codes. These considerations arise where signal recovery involves differencing or differentiation. We develop a general model and propose specific codes whose differences guarantee such properties as null dc, null midband, positive, and strictly positive midband content.

Abstract A clique of a graph is a maximal complete subgraph. A (p,q)‐graph has p points and q lines. A clique‐extremal (p,q)‐graph has either the maximum or the minimum number of cliques among all (p,q)‐graphs. Moon and Moser have determined constructively the maximum number of cliques in a p‐point graph. The problem of studying the clique‐extremal (p,q)‐graphs is now investigated. We first develop a standard form for such extremal graphs. These standard forms are shown to have a complementary kind of analogy with respect to maximum and minimum.

The unnormalized Hamming correlation between two sequences of equal length is the number of positions in which these sequences have identical symbols. In this paper, lower bounds on the out-of-phase autocorrelation and on the cross correlation of sequences of given length and alphabet size are derived. A method of constructing families of sequences that uniformly realize these hounds is presented.

We discuss the prefix encoding of aQ-ary source(Q \geq 2)into anL-symbol channel alphabet withL \geq Q. We present an optimal encoding scheme that minimizes the expected cost per symbol in the case of equally probable source symbols and arbitrary channel symbol costs.

A graph G with vertex set N = {1, 2, .-. , n} is called a permutation graph there exists a permutation P on N such that for i,j E N, (i -j)[P-'(i) -P-'(j)] < 0 if ar only if i and j are joined by an edge in G.A structural relationship is established between permutation graphs and transitive graph An algorithm for determining whether a given graph is a permutation graph is given.Efficie, algorithms for finding a maximum size clique and a minimum coloration of transitive grapl are presented.These algorithms are then shown to be applicable in solving problems in memo] allocation and circuit layout.

The construction described in this note makes possible the generation of any given linear shift register sequence of maximal period p= 2n-1, at a rate k times faster than the shift pulse rate. The construction is valid for any positive integer k which is not a multiple of p and it employs at most k linear shift registers of degree n or less.

The analysis and synthesis of polynomials and sequences overGF(2)has received considerable attention in recent years with the increasing use of PN sequences. In this paper a new approach to the problem is presented in which the polynomial coefficients and the sequence digits are derived in terms of the values assumed by a special class of polynomials, called "cyclonomials," at an arbitrary primitive element ofGF(2^n). For each value ofnthe cyclonomials are determined by the partition of the set\{ 0,1,2, \cdots ,2^n - 2 \}into cyclotomic cosets. A method of deriving all primitive polynomials of degreenfrom a given one of the same degree is described. A short outline of an approach to the more difficult task of synthesizing an initial primitive polynomial is also presented.

A homomorphism of the de Bruijn graph that maps a graph of order n onto one of order n-1 and its applications to the design of nonsingular feedback shift registers are discussed. The properties preserved under this mapping suggest a new design technique whose main advantage is due to the fact that the problem of designing a desired n-stage shift register may be reduced to a problem of order n-1 or less. Among the results obtained is a recursive formula for a feedback function that generates a cycle of maximum length.

A state graph (SG) is a directed graph with exactly one arc issuing from every vertex of the graph. The degree of an SG is the smallest integer d such that at most d, arcs are entering any vertex of the graph. An SG is said to be k-stable if it contains k≤1 cycles of unit length (loops) and these are the only cycles of the graph. A k-stable SG with mn vertices and degree d is called a (k, m, n)-SG if m≥k, d and if the distance from any vertex to a loop of the graph is at most n.