Symmetric fix-free codes are prefix condition codes in which each codeword is required to be a palindrome. Their study is motivated by the topic of joint source-channel coding and by some information retrieval problems. Although they have been considered by a few communities they are not well understood. In earlier work, we used a collection of instances of Boolean satisfiability problems as a tool in the generation of all optimal binary symmetric fix-free codes with n codewords and observed that the number of different optimal codelength sequences grows slowly compared with the corresponding number for prefix condition codes. We demonstrate that all optimal symmetric fixfree codes can alternatively be obtained by sequences of codes generated by simple manipulations starting from one particular code. We also discuss simplifications in the process of searching for this set of codes as well as a conjecture, which if correct, together with the other results leads to a relatively fast algorithm which has been implemented in MATLAB to construct all optimal binary symmetric fix-free codes.

Symmetric fix-free codes are prefix condition codes in which each codeword is required to be a palindrome. Their study is motivated by the topic of joint source-channel coding. Although they have been considered by a few communities they are not well understood. In earlier work we used a collection of instances of Boolean satisfiability problems as a tool in the generation of all optimal binary symmetric fix-free codes with n code words and observed that the number of different optimal code length sequences grows slowly compared with the corresponding number for prefix condition codes. We demonstrate that all optimal symmetric fix-free codes can alternatively be obtained by sequences of codes generated by simple manipulations starting from one particular code. We also discuss simplifications in the process of searching for this set of codes.

We propose a new way to construct a multicast coding scheme for linear deterministic relay networks. Our construction can be regarded as a generalization of the well-known multicast network coding scheme of Jaggito linear deterministic relay networks and is based on the notion of flow for a unicast session that was introduced by the authors in earlier work. We present randomized and deterministic polynomial-time versions of our algorithm and show that for a network with$g$destinations, our deterministic algorithm can achieve the capacity in$\left \lceil \log (g+1)\right \rceil $uses of the network and has the fastest construction time among algorithms for this problem.

Fix-free codes are prefix condition codes which can also be decoded in the reverse direction. They have attracted attention from several communities and are used in video standards. Two variations (with additional constraints) have also been considered for joint source-channel coding: 1) “symmetric” codes, which require the codewords to be palindromes; 2) codes with distance constraints on pairs of codewords. Approaches to determine the existence of a fix-free code with a given set of codeword lengths, for each of the three variations, are proposed. These appear to involve the first use of Boolean satisfiability (SAT) for the existence and design of source codes. Branch-and-bound algorithms to find the collection of optimal codes for asymmetric and symmetric fix-free codes are described. The first bound for the performance of optimal symmetric binary fix-free codes is provided. An earlier conjecture on optimal symmetric binary fix-free codes is proven and related results for asymmetric fix-free codes are presented. A variation of the 3/4 conjecture for fix-free codes is introduced. A key idea in the first conjecture and the new one is a definition of how one sequence of nondecreasing natural numbers dominates another.

The linear deterministic model of relay networks (LDRN) is a generalization of the traditional directed network model which has become popular in the study of the flow of information over wireless communication networks. The max-flow/min-cut theorem for a multicast session over a directed network has been extended to this wireless relay model. The result was first proved by a random coding scheme over large blocks of transmitted signals. In this paper, in the special case of a unicast session, a simple capacity-achieving transmission scheme for LDRN which codes over one symbol of information at each use of the network is obtained by a connection to the submodular flow problem and through the application of tools from matroid theory and submodular optimization theory. Polynomial-time algorithms for calculating the capacity of the network and the optimal coding scheme are implied by our analysis.

Line and star networks with both node and edge constraints are studied in the network coding framework. For line networks, the capacity region of the general multiple multicast problem is established. The coding theorem is based on a binary linear coding scheme, while the converse requires new upper bounds that improve on standard cut-based bounds. For star networks, the multiple unicast problem is examined. Capacity upper bounds are derived and a simple linear coding scheme is proposed which is based on the combinatorial optimization problem of cycle packing in directed graphs. The optimality of this scheme is established for a broad class of demands. The connection of node-constrained network coding in star networks, and index coding with side information is discussed and used to partially characterize the optimal linear code for general rates.

Fix-free or reversible-variable-length codes are prefix condition codes which can also be decoded in the reverse direction. They have attracted attention from several communities and are used in video standards. Two variations of fix-free codes (with additional constraints) have also been considered for joint source-channel coding: 1) "symmetric" fix-free codes, which require the codewords to be palindromes; 2) fix-free codes with distance constraints on pairs of codewords. We propose a new approach to determine the existence of a fix-free code with a given set of codeword lengths, for each of the three variations of the problem. We also describe a branch-and-bound algorithm to find the collection of optimal codes for asymmetric and symmetric fix-free codes.

We introduce a family of binary prefix condition codes in which each codeword is required to have a Hamming weight which is a multiple of w for some integer w ¿ 2. Such codes have intrinsic error resilience and are a special case of codes with codewords constrained to belong to a language accepted by a deterministic finite automaton. For a given source over n symbols and parameter w we offer an algorithm to construct a minimum-redundancy code among this class of prefix condition codes which has a running time of O(nw+2).

We introduce a transform-based technique to represent a circuit layout image so that 1) it typically leads to better compression ratios for maskless lithography systems than Block C4, the state-of-the-art compression scheme for this application, and 2) it permits faster encoding and less complex decoding than Block C4, while 3) it requires a similar amount of memory for decoding.

The linear deterministic model of relay channels is a generalization of the traditional directed network model which has become popular in the study of the flow of information over wireless communication networks. The max-flow/min-cut theorem of Ford and Fulkerson has recently been extended to this wireless relay model. This result was first proved by a random coding scheme over large blocks of transmitted signals. We demonstrate the same result with a deterministic, polynomial-time algorithm which takes as input a single transmitted signal instead of a long block of signals. The max-flow/min-cut theorem of Ford and Fulkerson is related to a number of famous results in combinatorics including Hall's marriage theorem. Hall's marriage theorem is a special case of a well-known result in matroid theory and in transversal theory named the Rado-Hall theorem. We show that the max-flow/min-cut theorem for linear deterministic relay networks is connected to (1) a two-dimensional transversal theorem for block matrices which is a new application of the Rado-Hall theorem and (2) a combinatorial result on sequences of block matrices which is obtained through results in submodular optimization.

The “Japanese” theorem is extended to multiple multicast sessions in an arbitrary network to characterize the routing capacity region by the intersection of an infinite collection of halfspaces. An elimination technique is developed to simplify this infinite description into a finite one based upon the shortest routing paths and trees in the network graph. This result is used as a step in providing the capacity regions for two multimessage multicast problems on undirected ring networks; in the first case only unicast and broadcast sessions are considered, and in the second case multicast sessions where the source and destination vertices form lines of adjacent vertices are studied. Network coding is generally necessary to achieve network capacity, but for our multimessage multicast problems, new arguments are used to demonstrate that routing can achieve network coding bounds.

Fix-free codes are variable length codes in which no codeword is the prefix or suffix of another codeword. They are used in video compression standards because their property of efficient decoding in both the forward and backward directions assists with error resilience. This property also potentially halves the average search time for a string in a compressed file relative to unidirectional variable length codes. Relatively little is known about minimum-redundancy fix-free codes, and we describe some characteristics of and observations about such codes. We introduce a new heuristic to produce fix-free codes which is influenced by these ideas. The design of minimum-redundancy fix-free codes is an example of a constraint processing problem, and we offer the first approach to constructing them and a variation with an additional symmetry requirement.

We introduce an EDIF netlist graph-based compression algorithm which is lossy with respect to the original byte stream but lossless in terms of the circuit information it contains. The algorithm builds on the graph mining tool SUBDUE. Our algorithm, CEDIF (compressed EDIF), compresses the EDIF file to a size about 39% of the size of the compressed file resulting from the state-of-the-art PAQ text compression algorithm and to about 85% of the size of a GRAPHITOUR-like graph compression algorithm.

We investigate network coding in star networks with multiple unicast sessions. We use entropy arguments to upper bound the simultaneous rates of communication among the different nodes in the network and prove that in many cases, the optimal network code is related to the combinatorial optimization problem of finding the maximum number of edge disjoint cycles in the demand graph of the network. Finally, we propose a polynomial time algorithm with linear binary operations that achieves the capacity in many cases.

A new twist to the classical problem of compressing a discrete source over noiseless channel alphabets where different code symbols may have different transmission costs is considered. One-to-one or nonsingular codes map each letter from the source alphabet into a distinct codeword consisting of a string of channel alphabet letters; they need not be uniquely decodable. They have been studied for binary code alphabets with equal letter costs since the early 1970s and are extended here to memoryless cost channel alphabets. The study of optimal one-to-one codes is linked in this paper to three other well-known source coding problems. The algorithm to construct the optimal one-to-one code is closely related to the Varn code and the Tunstall code. These relationships and convexity arguments are used to establish some upper and lower bounds on the expected cost per source symbol of the optimal one-to-one code. Finally, the average cost per symbol of the optimal one-to-one code is demonstrated to offer a new lower bound to the average cost per symbol of the optimal uniquely decodable code which is sometimes tighter than the classic bound from Shannon's landmark 1948 paper.

In this paper, we propose an dictionary-based English text compression algorithm; we name it star word ending (StarWE) because of certain similarities to the StarNT algorithm. Furthermore, StarWE borrows techniques that are used in WRT such as EOL coding, punctuation mark modeling, and n-gram matching. The main difference between StarWE and StarNT is in the division of the external dictionary; StarWE divides it by word endings so that the compressor would be able to obtain some of the tag information

We develop an extension of the Japanese theorem to multiple multicast sessions and interpret the result in terms of the collection of minimal length routing trees for the various multicast sessions. We use this result as a step in providing the capacity region for multiple unicast and broadcast sessions on an undirected ring network via a simple characterization of the family of bounds needed. We further demonstrate that routing is rate-optimal using new extensions to progressive d-separating edge set bounds.

A rate distortion problem is solved that is motivated by a quantum data compression problem. The goal is to send information about a source string x so that a receiver can construct a second string y for which the joint empirical probability distribution of x and y is close to some desired distribution. The problem differs from the usual rate distortion problems in that one must consider both remote sources and distortion functions that are not averages of per-letter distortion functions

We study the Tunstall code using the machinery from the analysis of algorithms literature. In particular, we propose an algebraic characterization of the Tunstall code which, together with tools like the Mellin transform and the Tauberian theorems, leads to new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates

The capacity region for multiple unicast sessions on a bidirectional ring network is established and is shown to be achieved by routing. The proof uses recently developed progressive d-separating edge set bounds, new extensions of these bounds, as well as tools from the literature on the multicommodity flow problem

A bound on network coding rates is developed that generalizes an edge-cut bound on routing rates. The bound involves progressively removing edges from a network graph and checking whether certain strengthened d-separation conditions are satisfied. The bound improves on the cut-set bound, and its efficacy is demonstrated by showing that routing is rate-optimal for some commonly cited examples in the networking literature

A network of two way channels (TWCs) is specified by a graph having an edge between vertex u and vertex v if there is a TWC between these vertices. A new cut-set bound is determined for such networks when network coding is permitted, and some implications of this bound are discussed.

This paper generalizes one-to-one encodings of a discrete random variable to finite code alphabets with memoryless letter costs and establish some upper and lower bounds on the expected cost per source symbol of the best one-to-one codes. We show that the average cost per symbol of the optimal one-to-one code sometimes is a tighter lower bound to the average cost per symbol of the optimal uniquely decodable code than Shannon's original bound.

Concurrency is a fundamental concept in computer science which is concerned with the study of systems involving multiple processes. The order of events in a concurrent system is unpredictable because of the independence of events occurring in the individual processes. Trace theory is a successful model for the execution of concurrent processes which employs congruence classes of words over partially commutative alphabets. These congruence or interchange classes generalize the more familiar notions of strings and type classes. Motivated by recent work in the areas of program profiling and compression of executable code, we consider a rate distortion problem in which the objective is to reproduce a string which is equivalent to the original string. This leads to a generalization of Kolmogorov complexity and a new graph entropy called the interchange entropy. We provide some of the basic properties of the interchange entropy. We also consider some universal compression schemes for this problem and show that for a large collection of dependence alphabets we can asymptotically attain the interchange entropy.

The use of strings is standard in modeling the temporal ordering of events in a sequence computation. A recent prize-winning paper in the computer architecture literature applies a grammar-based lossless data compression algorithm to the sequence of events that transpire while a computer program runs and utilizes the resulting grammar to better understand the program's dynamic behavior and improve its performance. Lossless data compression is most suitable for this purpose then there is a well-defined total ordering of event occurrences. In concurrent systems, i.e., systems involving multiple processes, there is a partial ordering of events. Trace theory employs congruence or interchange classes of words over partially commutative alphabets as a way to generalize strings to executions of concurrent processes. Universal compression schemes for a rate distortion problem in which the goal is to reproduce a string, which is equivalent to the original string are considered, and it is shown that for a large collection of dependence alphabets, interchange entropy, i.e., the rate distortion limit can be attained asymptotically.

A novel predictive lossless coding scheme is proposed. The prediction is based on a new weighted cascaded least mean squared (WCLMS) method. To obtain both a high compression ratio and a very low encoding and decoding delay, the residuals from the prediction are encoded using either a variant of adaptive Huffman coding or a version of adaptive arithmetic coding. WCLMS is especially designed for music/speech signals. It can be used either in combination with psycho-acoustically pre-filtered signals to obtain perceptually lossless coding, or as a stand-alone lossless coder. Experiments on a database of moderate size and a variety of pre-filtered mono-signals show that the proposed lossless coder (which needs about 2 bit/sample for pre-filtered signals) outperforms competing lossless coders, such as ppmz, bzip2, Shorten, and LPAC, in terms of compression ratios. The combination of WCLMS with either of the adaptive coding schemes is also shown to achieve better compression ratios and lower delay than an earlier scheme combining WCLMS with Huffman coding over blocks of 4096 samples.

Permutation codes are vector quantizers whose codewords are related by permutations and, in one variant, sign changes. Asymptotically, as the vector dimension grows, optimal Variant I permutation code design is identical to optimal entropy-constrained scalar quantizer (ECSQ) design. However, contradicting intuition and previously published assertions, there are finite block length permutation codes that perform better than the best ones with asymptotically large length; thus, there are Variant I permutation codes whose performances cannot be matched by any ECSQ. Along similar lines, a new asymptotic relation between Variant I and Variant II permutation codes is established but again demonstrated to not necessarily predict the performances of short codes. Simple expressions for permutation code performance are found for memoryless uniform and Laplacian sources. The uniform source yields the aforementioned counterexamples.

Renewal theory provides a wavy to derive fundamental results about source coding and is useful in the analysis and design of many lossless data compression algorithms. We consider two very different applications of renewal theory to source coding. The first one results in a variable-length counterpart to the asymptotic equipartition property for unifilar Markov sources. The second application leads to the first analysis of variable-to-fixed length codes with plurally parsable dictionaries.

Renewal theory is a powerful tool in the analysis of source codes. We use renewal theory to obtain some asymptotic properties of finite-state noiseless channels. We discuss the relationship between these results and earlier uses of renewal theory to analyze the Lempel-Ziv (1977, 1978) codes and the Tunstall (1967) code. As a new application of our results, we provide the asymptotic performance of two of the Perl, Garey and Even (1975) prefix condition codes.

The goal of lossless data compression is to map the set of strings from a given source into a set of binary code strings. A variable-to-fixed length encoding procedure is a mapping from a dictionary of variable length strings of source outputs to the set of codewords of a given length. For memoryless sources, the Tunstall procedure can be applied to construct optimal uniquely parsable dictionaries and the resulting codes are known to work especially well for sources with small entropies. We introduce the idea of plurally parsable dictionaries and show how to design plurally parsable dictionaries that can outperform the Tunstall dictionary of the same size on very predictable binary, memoryless sources.

For a large class of parsing rules, we introduce a "conservation of entropy" theorem for the output of a unifilar Markov source. Using this theorem and renewal theory, we find a procedure to generate asymptotically optimal generalized variable-to-fixed length codes.

A number of papers have investigated the compression obtained by some well-known lossless data compression algorithms in the limit as the dictionary size approaches infinity. Using a very detailed analysis of the Tunstall (1967) code as an example, we demonstrate that asymptotic analyses can fail to provide the performance of an algorithm in the important case of a predictable source with a small to moderate dictionary size.

For any given source output string from a unifilar, Markov source, we bound from above the amount by which the number of binary digits used by two variants of LZ'77 to encode the string exceeds its self-information as a function of its length and self-information.

The Lempel-Ziv codes are universal variable-to-fixed length codes that have become virtually standard in practical lossless data compression. For any given source output string from a Markov of unifilar source, we upper bound the difference between the number of binary digits needed by the Lempel-Ziv-Welch code (1977, 1978, 1984) to encode the string and the self-information of the string. We use this result to demonstrate that for unifilar, Markov sources, the redundancy of encoding the first n letters of the source output with LZW is O((ln n)/sup -1/), and we upper bound the exact form of convergence.

The Lempel-Ziv codes are universal variable-to-fixed length codes that have become virtually standard in practical lossless data compression. For any given source output string from a Markov or unifilar source, we upper-bound the difference between the number of binary digits needed to encode the string and the self-information of the string. We use this result to demonstrate that for unifilar or Markov sources, the redundancy of encoding the first n letters of the source output with the Lempel-Ziv incremental parsing rule (LZ'78), the Welch modification (LZW), or a new variant is O((ln n)/sup -1/), and we upper-bound the exact form of convergence. We conclude by considering the relationship between the code length and the empirical entropy associated with a string.

Tunstall codes are variable-to-fixed length codes that maximize the expected number of source letters per dictionary string for discrete, memoryless sources. We analyze a generalization of Tunstall coding to sources with memory and demonstrate that as the dictionary size increases, the number of code letters per source symbol comes arbitrarily close to the minimum among all variable-to-fixed length codes of the same size. We also find the asymptotic relationship between the dictionary size and the average length of a dictionary entry.

A duality between Varn (1971) coding and Tunstall (1968) coding is demonstrated and new bounds on the expected transmission cost per source symbol for Varn codes are established. For binary channels, the superiority of the new upper bound over Krause's (1962) upper bound is proven.>

The authors analyze the expected delay for infinite precision arithmetic codes, and suggest a practical implementation that closely approximates the idealized infinite precision model.>

For each of five generalizations of the odcl-even transposition sort to a sorting algorithm on a /77X W mesh of processors.we demonstrate that with "high probability," the number of steps required to sort a random permutation of N numbers is @(N).1

The authors analyze the expected delay for infinite precision arithmetic codes and suggest a practical implementation that concentrates on the issue of delay.>