In this paper, we consider a synchronization problem between nodes A and B that are connected through a two-way communication channel. Node A contains a binary file X of length n and node B contains a binary file Y that is generated by randomly deleting bits from X, by a small deletion rate β. The location of deleted bits is not known to either node A or node B. We offer a deterministic, polynomial-time synchronization scheme between nodes A and B that needs a total of O(n βlog 1/β) transmitted bits and reconstructs X at node B with probability of error that is exponentially low in the size of X. Orderwise, the rate of our scheme matches the optimal rate for this channel.

Conventional communications theory assumes that the data transmission is noisy but the processing at the receiver is entirely error-free. Such assumptions may have to be revisited for advanced (silicon) technologies in which hardware failures are a major concern at the system-level. Hence, it is important to characterize the performance of a communication system with both noisy processing components and noisy data transmission. Coding systems based on low-density parity check (LDPC) codes are widely used for a variety of applications. In this paper, we focus on probabilistic analysis of the LDPC Gallager B decoder built out of faulty components. Using the density evolution technique, we find approximations for the optimal threshold of the decoder and the symbol error rate (SER) of the decoded sequence as functions of both the channel error rate and error rates of the decoder components, for both binary and non-binary regular LDPC codes. Furthermore, we study the convergence of the output SER and the decoding threshold of the decoder for different ranges of error rates. We verify our results using MATLAB simulations and hardware emulation of noisy decoders. Results presented in this paper can serve as systematic design guidelines in resource allocation for noisy decoders. Informed resource allocation is of particular relevance to emerging data storage and processing applications that need to maintain high levels of reliability despite hardware errors in advanced technologies.

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.

Today's mainstream electronic systems typically assume that transistors and interconnections operate correctly over their useful lifetime. For coming generations of silicon technologies, several causes of hardware failures, such as erratic bit errors, transient (soft) errors, and process variations, are becoming significant. In contrast to the traditional redundancy-based reliability solutions, the aim of a probabilistic design is to achieve high quality results and efficiency using erroneous or imperfect components along with a judicious allocation of resources. In this paper we focus on a probabilistic analysis of an LDPC Gallager B decoder made out of unreliable hardware components. Our analysis reveals the dependencies between the final BER at the output of the decoder and the errors in the components of the decoder. We demonstrate that a system design guided by our analysis can produce higher quality results compared to an arbitrary resource allocation. This resource allocation is of particular relevance to emerging storage applications that need to maintain extremely high levels of reliability even as the underlying technology scales deep into the nano-regime.

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.

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.

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.

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.