Source coding and graph entropies

A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in two communication scenarios and relate this number to the chromatic and Korner (1973) entropies of a naturally defined graph     

Asymptotic component densities in Programmable Gate Arrays realizing all circuits of a given size

A Programmable Gate Array (PGA) is modeled as a square grid. Some grid nodes are processing nodes containing electrical elements. The rest are switching nodes capable of connecting wires incident on them. Two possible types of switching nodes are considered. In vertex connectivity each switching node can connect only one pair of wires. In edge connectivity each switching node can simultaneously connect two pairs of wires. The PGA must be capable of implementing any graph of size at mostk and degree at most 4. We prove tight bounds on the highest achievable density of processing nodes.In edge connectivity the highest achievable density is (1/k). In vertex connectivity the highest achievable density is (1/k ²). If the grid is augmented by the diagonal edges, then the highest achievable density is (1/k) even with vertex connectivity. These extend known results for embedding graphs in grids.Small graphs of degree 1 are further examined. Fork=2 andk=3 the highest density of processing nodes equals the highest density of parked cars in a square parking lot where each car can exit. Both densities are two-thirds. Fork=4 the highest density is one-half.This work was supported in part by NSF Grants NCR-8903288 and IAI-9005849.     

Stopping set distribution of LDPC code ensembles

Stopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a /spl radic/1-/spl lambda/'(0)/spl rho/'(1) fraction of codes with /spl lambda/'(0)/spl rho/'(1)<1, and in particular for almost all codes with smallest variable degree >2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability /spl epsi/, showing in particular that for codes with lowest variable degree 2, if /spl epsi/ is below a certain threshold, the asymptotic average block error probability is 1-/spl radic/1-/spl lambda/'(0)/spl rho/'(1)/spl epsi/.     

Coding for computing

A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturally defined graph. We also determine the number of bits needed when the communicators exchange two messages     

Universal compression of memoryless sources over unknown alphabets

It has long been known that the compression redundancy of independent and identically distributed (i.i.d.) strings increases to infinity as the alphabet size grows. It is also apparent that any string can be described by separately conveying its symbols, and its pattern-the order in which the symbols appear. Concentrating on the latter, we show that the patterns of i.i.d. strings over all, including infinite and even unknown, alphabets, can be compressed with diminishing redundancy, both in block and sequentially, and that the compression can be performed in linear time. To establish these results, we show that the number of patterns is the Bell number, that the number of patterns with a given number of symbols is the Stirling number of the second kind, and that the redundancy of patterns can be bounded using results of Hardy and Ramanujan on the number of integer partitions. The results also imply an asymptotically optimal solution for the Good-Turing probability-estimation problem.     

Self-avoiding random loops

A random loop, or polygon, is a simple random walk whose trajectory is a simple Jordan curve. The study of random loops is extended in two ways. First, the probability P_n(x,y) that a random n-step loop contains a point (x,y) in the interior of the loop is studied, and (1/2, 1/2) is shown to be (1/2)-(1/ n). It is plausible that P_n(x,y) tends toward 1/2 for all ( x,y), but this is not proved even for (x,y)=(3/2,1/2) A way is offered to simulate random n-step self-avoiding loops. Numerical evidence obtained with this simulation procedure suggests that the probability P_n (3/2,1/2)≈(1/2)-(c/n), for some fixed c      

Average-case interactive communication

X and Y are random variables. Person P_x knows X, Person P_y knows Y, and both know the joint probability distribution of the pair (X,Y). Using a predetermined protocol, they communicate over a binary error-free channel in order for P_y to learn X. P_x may or may not learn Y. It is determined how many information bits must be transmitted (by both persons) on the average. The results show that, when the arithmetic average number of bits is considered, there is no asymptotic advantage to P_x knowing Y in advance and four messages are asymptotically optimum. By contrast, for the worst-case number of bits, communication can be significantly reduced if P_x knows Y in advance, and it is not known whether a constant number of messages is asymptotically optimum     

Limit results on pattern entropy

We determine the entropy rate of patterns of certain random processes including all finite-entropy stationary processes. For independent and identically distributed (i.i.d.) processes, we also bound the speed at which the per-symbol pattern entropy converges to this rate, and show that patterns satisfy an asymptotic equipartition property. To derive some of these results we upper bound the probability that the nth variable in a random process differs from all preceding ones.