We characterise bounds on the optimal broadcast rate for a few classes of pliable-index-coding instances. Unlike the majority of currently solved instances, which belong to a special class where all receivers with a certain side-information cardinality are either present or absent, we consider more general instances without this constraint. We devise a novel algorithm that constructs a decoding chain by iteratively adding a message that can be decoded by a receiver whose side information is already in the chain. If the decoding chain cannot proceed due to the absence of a receiver with the required messages, weskipa message by adding it to the chain regardless. We prove that a lower bound on the optimal broadcast rate is a function of the number of skipped messages, across all possible decoding choices of the receivers and any realisation of the algorithm for each decoding choice. While this result is not computationally feasible in isolation, it serves as a basis for deriving explicit lower bounds on the broadcast rate for specific classes of pliable-index-coding instances. These lower bounds depend on the number of absent receivers or the pattern of their side-information sets. Specifically, we explicitly characterise the optimal broadcast rate for instances with up to and including four absent receivers with any side-information pattern, as well as instances where the side-information sets are nested in particular ways.

Central to the field of information theory is the study of the entropy function and the possible values it can attain when applied to subsets of sets of arbitrarily correlated random variables. The set of attainable entropy vectors over three variables $\Gamma _3^{\ast}$ is not fully understood. A complete description of $\Gamma _3^{\ast}$ requires the analysis and characterization of the faces of the related polymatroid, Γ3. Thus far, only three faces of Γ3have been fully characterized. These faces are either one or two dimensional. Less concrete success has been attained for more complex faces. This paper focuses on a four-dimensional face $F_6^4$, and presents a novel approach to analyzing a complex face of Γ3by reducing the problem to a two-dimensional subset of the face. Through this approach, this paper attains novel insights and a tighter inner bound on $F_6^4$ than those that have been established thus far. This method demonstrates a possible way to fully characterize $F_6^4$ through the analysis of the simpler two dimensional subset.

This paper introduces a novel class of PICOD$(t)$problems referred to as g-group complete-S PICOD$(t)$problems. It constructs a multi-stage achievability scheme to generate pliable index codes for group complete PICOD problems when$S=\{s\}$is a singleton set. Using the maximum acyclic induced sub graph bound, lower bounds on the broadcast rate are derived for singleton$S$, which establishes the optimality of the achievable scheme for a range of values for$t$and for any$g$and$s$. For all other values, it is shown that the achievability scheme is optimal among a restricted class of broadcast codes.

We propose and study a variant of pliable index coding (PICOD) where receivers have preferences for their unknown messages and give each unknown message a preference ranking. We call this the preferential pliable index-coding (PPICOD) problem and study the Pareto trade-off between the code length and overall satisfaction metric among all receivers. We derive theoretical characteristics of the PPICOD problem in terms of interactions between achievable code length and satisfaction metric. We also conceptually characterise two methods for computation of the Pareto boundary of the set of all achievable code length-satisfaction pairs. As for a coding scheme, we extend the Greedy Cover Algorithm for PICOD by Brahma and Fragouli, 2015, to balance the number of satisfied receivers and average satisfaction metric in each iteration. We present numerical results which show the efficacy of our proposed algorithm in approaching the Pareto boundary, found via brute-force computation.

In the pliable variant of index coding, receivers are allowed to decode any new message not known a priori. Optimal code design for this variant involves identifying each receiver’s choice of a new message that minimises the overall transmission rate. This paper proposes a formulation that further relaxes the decoding requirements of pliable index coding by allowing receivers to decode different new messages depending on message realisations. Such relaxation is shown to offer no rate benefit when linear codes are used, but can achieve strictly better rates in general. Scenarios are demonstrated for which the transmission rates are better when the message size is finite than when it is asymptotically large. This is in stark contrast to traditional communication setups.

We study the problem of strong coordination of the actions of two nodes X and Y that communicate over a discrete memoryless channel (DMC) such that the actions follow a prescribed joint probability distribution. We propose two novel random coding schemes and a polar coding scheme for this noisy strong coordination problem, and derive inner and outer bounds for the respective strong coordination capacity region. The first scheme is a joint coordination-channel encoding scheme that utilizes the randomness provided by the communication channel to reduce the amount of local randomness required to generate the sequence of actions at Node Y. Based on this random coding scheme, we provide a characterization of the capacity region for a special case of the noisy strong coordination setup, namely, when the DMC is a deterministic channel. The second scheme exploits separate coordination and channel encoding where local randomness is extracted from the channel after decoding. Moreover, by leveraging the random coding results for this problem, we present an example in which the proposed joint encoding scheme is able to strictly outperform the separate encoding scheme in terms of achievable communication rate for the same amount of injected randomness into both systems. Thus, we establish the sub-optimality of the separation of strong coordination and channel encoding with respect to the communication rate over the DMC in this problem. Finally, the third scheme is a joint coordination-channel polar coding scheme for strong coordination. We show that polar codes are able to achieve the established inner bound to the strong noisy coordination capacity region and thus provide a constructive alternative to a random coding proof. Our polar coding scheme also offers a constructive solution to a channel simulation problem where a DMC and shared randomness are employed together to simulate another DMC.

General intelligence, the ability to solve arbitrary solvable problems, is supposed by many to be artificially constructible. Narrow intelligence, the ability to solve a given particularly difficult problem, has seen impressive recent development. Notable examples include self-driving cars, Go engines, image classifiers, and translators. Artificial General Intelligence (AGI) presents dangers that narrow intelligence does not: if something smarter than us across every domain were indifferent to our concerns, it would be an existential threat to humanity, just as we threaten many species despite no ill will. Even the theory of how to maintain the alignment of an AGI's goals with our own has proven highly elusive. We present the first algorithm we are aware of for asymptotically unambitious AGI, where “unambitiousness” includes not seeking arbitrary power. Thus, we identify an exception to the Instrumental Convergence Thesis, which is roughly that by default, an AGI would seek power, including over us.

An equivalence was shown between network coding and index coding. The equivalence allows for a network code for any given network-coding instance to be translated to an index code for a suitably constructed index-coding instance, and vice versa. The equivalence also holds for the opposite direction. A secure version of the equivalence in the presence of eavesdroppers was proven for the case where there is no decoding error and no information leakage to the eavesdroppers. For the case of non-zero decoding error and non-zero leakage, three out of the four directions required for an equivalence were proven. This paper proves the last direction, thereby completing the equivalence between secure network coding and secure index coding.

We characterise the optimal broadcast rate for a few classes of pliable-index-coding problems. This is achieved by devising new lower bounds that utilise the set of absent receivers to construct decoding chains with skipped messages. This work complements existing works by considering problems that are not complete-S, i.e., problems considered in this work do not require that all receivers with a certain side-information cardinality to be either present or absent from the problem. We show that for a certain class, the set of receivers is critical in the sense that adding any receiver strictly increases the broadcast rate.

We consider the problem of tracking, in realtime, an unstable autoregressive (AR) source over a discrete memoryless channel (DMC). We present computable achievable bounds on the optimal tracking error for general DMCs, and we particularize these bounds to the binary erasure, packet erasure, and binary symmetric channels. The achievable bounds in this paper are proved using a partially separatesource quantizationandchannel codingarchitecture. We do not use complete or strict separation in usual Shannon sense: 1) the quantiser’s resolution is optimized against the error-correction capabilities of the channel code and the channel code is optimized against anAR Hamming distortion functionmatched to the source (a weighted Hamming distortion function that provides unequal error protection to different parts of the AR source). The achievability results for general DMCs are proved by combining the AR Hamming distortion function with new realtime (streaming) versions of therandom coding unionanddependence testing bounds. When applied to erasure channels, these general bounds combine with simple converses to demonstrate that the channel’s cutoff rate plays an important role in realtime tracking.

We study a variant of the successive refinement problem with receiver side information in which the receivers require identical, matching reconstructions. We present general inner and outer bounds for the rate region for this variant of the problem and present a single-letter characterization of the admissible rate region for several classes of the joint distribution of the source and the side information. Unlike in the general successive refinement problem, the characterization of the admissible rate region in the cases when the derived inner and outer bounds match requires only one auxiliary random variable. The characterization reveals that the side information can be fully used to reduce the communication rates via binning; however, the receiver reconstruction functions can depend only on a certain Gács-Körner common randomness between shared by the two receivers. Since the entropy of the Gács-Körner common randomness between two random variables is a discontinuous function of joint distribution of the variables, we establish the fact that the admissible rate region for this variant of the successive refinement problem is discontinuous in the underlying distribution of the source and side information even though the problem formulation does not involve the zero-error or functional reconstruction constraints.

We study the problem of compressing piecewise i.i.d. sources, which models the practical application of jointly compressing multiple disparate data files. We establish that universal compression of piecewise i.i.d data is possible by modeling the data as a Markov process whose memory grows suitably with the size of the data using the Krichevsky-Trofimov (KT) estimator. The memory order is chosen large enough so that successful learning of the distribution of the each piece of the data from the corresponding contexts is possible for almost any realization of any piecewise i.i.d. data process. This is, a priori, a surprising result given that we are employing a stationary model to asymptotically optimally (model and) compress non-stationary data.

A linear code equivalence between index coding and network coding was shown by El Rouayheb et al., which establishes that for any index-coding instance, there exists a network-coding instance for which any index code can be mapped to a suitable network code, and vice versa. Similarly, for any network-coding instance, there exists an index-coding instance for which a similar code equivalence can be constructed. Effros et al. extended the equivalence to include non-linear codes. Subsequently, we extended the code equivalence to the secure communication setting in the presence of an eavesdropper, in which we impose perfect decodability and secrecy. In this paper, we generalise the equivalence between secure index coding and secure network coding to include non-zero decoding error and non-zero leakage.

This work investigates the convergence rate of learning the stationary distribution of finite-alphabet stationary ergodic sources using a binarized context-tree weighting approach. The binarized context-tree weighting (CTW) algorithm estimates the stationary distribution of a symbol as a product of conditional distributions of each component bit, which are determined in a sequential manner using the well known binary context-tree weighting method. We establish that CTW algorithm is a consistent estimator of the stationary distribution, and that the worst-case L1-prediction error between the CTW and frequency estimates using n source symbols each of which when binarized consists of k > 1 bits decays as Θ(√{2k[logn/n]})·.

Recently, Kumar, Li, and EI Gamal proposed a notion of common information using a variation of a setup used to define Wyner common information rate. This notion, known as the exact common information, is the minimum common randomness required for the exact and separate generation of a pair of correlated discrete memoryless sources. While exact common information rate is not known to have a single-letter characterization, it was shown to equal the Wyner common information rate for the symmetric binary erasure source in Kumar-Li-EI Gamal-ISIT2014. The authors extended this result to establish the equality of the two notions of common information for general noisy typewriter, Z - and erasure sources in Vellambi - Kliewer - Allerton 2016. In this work, we investigate the connection between exact and Wyner common information rates to derive two new implicit conditions (on the joint source distribution) that ensure the equality of the two notions.

We study the index coding problem in the presence of an eavesdropper, where the aim is to communicate without allowing the eavesdropper to learn any single message aside from the messages it may already know as side information. We establish an outer bound on the underlying secure capacity region of the index coding problem, which includes polymatroidal and security constraints, as well as the set of additional decoding constraints for legitimate receivers. We then propose a secure variant of the composite coding scheme, which yields an inner bound on the secure capacity region of the index coding problem. For the achievability of secure composite coding, a secret key with vanishingly small rate may be needed to ensure that each legitimate receiver who wants the same message as the eavesdropper, knows at least two more messages than the eavesdropper. For all securely feasible index coding problems with four or fewer messages, our numerical results establish the secure index coding capacity region.

We analyze the problem of strong coordination over a multi-hop line network in which the node initiating the coordination is a terminal network node. We assume that each node has access to a certain amount of randomness that is local to the node, and that the nodes also have shared common randomness, which are used together with explicit hop-by-hop communication to achieve information-theoretic strong coordination. We derive the trade-offs among the required rates of communication on the network links, the rates of local randomness available at network nodes, and the rate of common randomness to realize strong coordination. We present an achievable coding scheme built using multiple layers of channel resolvability codes, and establish several settings in which this scheme offers the best possible trade-offs among network resources.

We study the problem of strong coordination of actions of two agents X and Y that communicate over a noisy communication channel such that the actions follow a given joint probability distribution. We propose two novel schemes for this noisy strong coordination problem, and derive inner bounds for the underlying strong coordination capacity region. The first scheme is a joint coordination-channel coding scheme that utilizes the randomness provided by the communication channel to reduce the local randomness required in generating the action sequence at agent Y. The second scheme exploits separate coordination and channel coding where local randomness is extracted from the channel after decoding. Finally, we present an example in which the joint scheme is able to outperform the separate scheme in terms of coordination rate.

We study the problem of achieving strong secrecy over wiretap channels at negligible cost, in the sense of maintaining the overall communication rate of the same channel without secrecy constraints. Specifically, we propose and analyze two source-channel coding architectures, in which secrecy is achieved by multiplexing public and confidential messages. In both cases, our main contribution is to show that secrecy can be achieved without compromising communication rate and by requiring only randomness of asymptotically vanishing rate. Our first source-channel coding architecture relies on a modified wiretap channel code, in which randomization is performed using the output of a source code. In contrast, our second architecture relies on a standard wiretap code combined with a modified source code termed uniform compression code, in which a small shared secret seed is used to enhance the uniformity of the source code output. We carry out a detailed analysis of uniform compression codes and characterize the optimal size of the shared seed.

We investigate the construction of weakly-secure index codes for a sender to send messages to multiple receivers with side information in the presence of an eavesdropper. We derive a sufficient and necessary condition for the existence of index codes that are secure against an eavesdropper with access to any subset of messages of cardinality t, for any fixed t. In contrast to the benefits of using random keys in secure network coding, we prove that random keys do not promote security in three classes of index-coding instances.

It is well known that lossless compression of a discrete memoryless source with near-uniform encoder output is possible at a rate above its entropy if and only if the encoder and decoder share a common random seed. This work focuses on deriving conditions for near-uniform encoder output(s) in the Wyner-Ziv and the distributed lossy compression problems. We show that in the Wyner-Ziv problem, near-uniform encoder output and operation close to the WZ-rate limit is simultaneously possible, whereas in the distributed lossy compression problem, jointly near-uniform outputs is achievable in the interior of the distributed lossy compression rate region if the sources share non-trivial Gács-Körner common information.

Anytime transmission has been shown to be an effective means of stabilizing an unstable system over noisy channels. A crucial issue in implementing anytime transmission strategies is the design of anytime codes that offer good finite-length performance and asymptotic anytime properties. This paper introduces an efficient anytime code derived from protograph-based low-density parity-check convolutional codes known as extended S-LDPCC (XS-LDPCC) codes. The asymptotic anytime properties of XS-LDPCC codes over both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise (BIAWGN) channel are demonstrated through density evolution. By means of certain observations verified by simulations, we provide accurate estimates of the delay exponents of XS-LDPCC codes over the BEC and the BIAWGN channel. Through simulations, the finite-length performance of XS-LDPCC codes and the effects of different code design parameters are quantified.

In this paper, an efficient anytime code derived from protograph-based low-density parity-check convolutional (P-LDPCC) code is proposed. Density evolution technique is applied to demonstrate the anytime properties of the P-LDPCC code over the binary erasure channel (BEC). Through simulation, the finite-length performance is evaluated and the effects of code design parameters are observed. The delay exponent is evaluated using the density evolution functions and simulations of finite-length codes. The simulation results show that P-LDPCC code outperforms existing LDPCC anytime codes.

It is known that a sub-linear rate of source-independent random seed (common randomness) can enable the construction of lossless compression codes whose output is nearly uniform under the variational distance (Chou-Bloch-ISIT'13). This work uses finite-blocklength techniques to present an alternate proof that for near-uniform lossless compression, the seed length has to grow strictly larger than √n, where n represents the blocklength of the lossless compression code. In the lossy setting, we show the surprising result that a seed is not required to make the encoder output nearly uniform.

The demand for a highly accurate indoor positioning system is rapidly increasing. In the last few years, several positioning systems based on visible light communications that achieve good positioning accuracy have been proposed. However, these systems are based on assumptions such as complete knowledge of the height of the receiver, exact alignment of the transmitter and receiver normals to the normal of the ceiling. Recently, authors have proposed a positioning system without these assumptions. The system, however, does not support user mobility because it requires a user to vary the receiver orientation at a fixed location. In order to support user mobility, we propose a novel positioning system in this work using multiple optical receivers. The remarkable features of the proposed system are as follows: (a) the receiver can be mobile; (b) the positioning is done within 6 milliseconds in our experiment; (c) the heights of the transmitters need not be the same; (d) the receiver's height need not be known; and (e) the receiver's normal need not be aligned with those of the transmitters. We have tested our positioning system in a mobile scenario and results show that mean position errors of less than 0.06m is achievable.

A streaming communications model with an autoregressive distortion function is proposed. We show that the model is useful for delay-sensitive systems, and we present asymptotic and non-asymptotic achievability results that exhibit some fundamental tradeoffs between rate, reliability and delay.

We study the variant of the successive refinement problem where the receivers require identical reconstructions.We characterize the rate region when the joint support of the source and the side information variables is the Cartesian product of their individual supports. The characterization indicates that the side information can be fully used to reduce the communication rates via binning; however, the reconstruction functions can depend only on the Gács-Körner common randomness shared by the two receivers. Unlike existing (inner and outer) bounds to the rate region of the general successive refinement problem, the characterization for the variant studied requires only one auxiliary random variable.

Lossless coding for streaming sources is studied under a delay-constrained point-to-point setup. A variant of random binning, known as variable-length sequential random (VLSR) binning, is proposed for this setup. The performance of this binning scheme is evaluated by its delay exponent, which measures the asymptotic rate at which the decoding error probability decays with the delay. An achievable delay exponent is derived for VLSR binning, and numerical results show that the proposed binning achieves a better delay exponent than the existing fixed-length sequential random binning.

Indoor positioning has attracted a lot of attention in the literature. Positioning systems using the existing wireless network have low deployment cost but the position error can be up to several meters. Some proposed systems have low position error; however, they require extra hardware, thereby resulting in high deployment costs. In this work, we propose a positioning system that offers low position error at a low deployment cost. The proposed system uses visible light communications (VLC) together with the accelerometers in mobile devices. In contrast to existing works on VLC for positioning, our system neither requires the knowledge of the height of the receiver from the ground, nor does it require the receiver to be oriented such that the angle of irradiance of a transmitter equals the incidence angle at the receiver. The proposed system has low complexity, and simulation results show that it achieves position errors of less than 0.5 meter.

A bound on the maximum information transmission rate through a cascade of Gaussian links is presented. The network model consists of a source node attempting to send a message drawn from a finite alphabet to a sink, through a cascade of Additive White Gaussian Noise links each having an input power constraint. Intermediate nodes are allowed to perform arbitrary encoding/decoding operations, but the block length and the encoding rate are fixed. The bound presented in this paper is fundamental and depends only on the design parameters namely, the network size, block length, transmission rate, and signal-to-noise ratio.

This work investigates the problem of conveying discrete memoryless sources over general networks with specified lossless (vanishing error probability) and/or lossy (average per-symbol distortion) reconstruction demands. It presents two different sufficient conditions under which an edge carrying zero-rate messages is not crucial for the conveyance of the sources, i.e., the demands can be met even when the zero-rate edge is deleted and the rates on other edges are kept unchanged.

The variant of the Heegard-Berger problem where the receivers require identical reconstructions is studied, and the rate-distortion function for the following three settings is derived: (a) the encoder is also required to generate the reconstructions common to the receivers; (b) the side information at the receivers are physically degraded; and (c) the side information at the receivers are stochastically degraded, and the source satisfies a particular full-support condition. The characterizations indicate that the receiver side information can be fully exploited to perform Wyner-Ziv-style binning. However, the reconstruction functions can depend only on the randomness common to the receivers in the Gács-Körner sense.

This work focuses on the multi-terminal source coding problem and presents conditions when a rate point achievable with asymptotically zero-rate messages over a subset of network links, is also achievable with no communication over links in that subset. We show that when there exist block codes that are robust to small changes in the source distribution, zero-rate encoders can be ignored, i.e., their outgoing links can be assumed to be absent. Additionally, we show that when the decoder is given access to the strictly causal past realizations of the sources, zero-rate encoders can always be ignored.

This paper revisits earlier work on the achievable rate-region for the coded side-information problem. For specific source distributions we provide computable extreme rate points. As opposed to previous works, we present short and concise proofs and additional rate points below the time-sharing line of previously known rate points. Our results are based on a formulation as an optimization problem.

This work proves that in the multi-terminal source coding problem, any achievable rate point achievable with asymptotically zero rate on a subset of links can also be achieved without any communication over the same subset of links, or equivalently, when the links in the subset are removed from the network. This work shows that asymptotically zero-rate communication over a subset of links cannot be crucial for the inclusion of a rate point in the rate region in spite of the absence of an explicit characterization of the rate region.

New results on the achievable trade-off between the per-node throughput T(n) and the average delay D(n) in a static wireless network of n nodes are presented for physical link models. For links modeled by channels with additive white Gaussian noise with power-law attenuation, a trade-off of only D(n) = ⊖ (n (log n) T(n)) is guaranteed for T(n) = ⊖(n-½). This follows from showing that there is significant information loss in the network due to error propagation, unless the length of the channel code employed is sufficiently high. Constraining the block length to be bounded yields worse trade-offs: only ⊖(n (log n)2T(n)) is guaranteed for optimal throughput, provided there is rich fading diversity.

In this paper, we present an exact model for the analysis of the performance of Random Linear Network Coding (RLNC) in wired erasure networks with finite buffers. In such networks, packets are delayed due to either random link erasures or blocking by full buffers. We assert that because of RLNC, the content of buffers have dependencies which cannot be captured directly using the classical queueing theoretical models. We model the performance of the network using Markov chains by a careful derivation of the buffer occupancy states and their transition rules. We verify by simulations that the proposed framework results in an accurate measure of the network throughput offered by RLNC. Further, we introduce a class of acyclic networks for which the number of state variables is significantly reduced.

We consider the problem of communicating degraded message sets over multi-access channel with finite input and output alphabets that is controlled by an underlying i.i.d. state process. Inner and outer bounds are presented for the general case where encoders possess non-causal degraded state information. Two special cases of the general setup are then presented where the derived inner bound is shown to be the capacity region.

This work investigates the effect of finite buffer sizes on the throughput capacity and packet delay of line networks with packet erasure links that have perfect feedback. These performance measures are shown to be linked to the stationary distribution of an underlying irreducible Markov chain that models the system exactly. Using simple strategies, bounds on the throughput capacity are derived. The work then presents two iterative schemes to approximate the steady-state distribution of node occupancies by decoupling the chain to smaller queueing blocks. These approximate solutions are used to understand the effect of buffer sizes on throughput capacity and the distribution of packet delay. Using the exact modeling for line networks, it is shown that the throughput capacity is unaltered in the absence of hop-by-hop feedback provided packet-level network coding is allowed. Finally, using simulations, it is confirmed that the proposed framework yields accurate estimates of the throughput capacity and delay distribution and captures the vital trends and tradeoffs in these networks.

The exact Markov modeling analysis of erasure networks with finite buffers is an extremely hard problem due to the large number of states in the system. In such networks, packets are lost due to either link erasures or blocking by the full buffers. In this paper, we propose a novel method that iteratively estimates the performance parameters of the network and more importantly reduces the computational complexity compared to the exact analysis. This is the first work that analytically studies the effect of finite memory on the throughput and latency in general wired acyclic networks with erasure links. As a case study, a random packet routing scheme with ideal feedback on the links is used. The proposed framework yields a fairly accurate estimate of the probability distribution of buffer occupancies at the intermediate nodes using which we can not only identify the congested and starving nodes but also obtain analytical expressions for throughput and average delay of a packet in the network. The theoretical framework presented here can be applied to many wired networks, from Internet to more futuristic applications such as networks-on-chip under various communication and network coding scenarios.

We investigate the problem of reliable and energy-efficient one-to-all broadcasting in multihop wireless networks, and propose fractional transmission scheme (FTS) - a low-complexity and scalable broadcasting scheme. FTS exploits the broadcasting nature of wireless channels and random encoding of rateless codes to reduce energy consumption while ensuring reliable delivery of packets to all nodes in the network. In the proposed scheme, different neighbors of a node share the responsibility of transmitting packets by sending only a fraction of encoded packets required by the node to successfully receive the data sent by the source. A detailed analysis of the performance of FTS is presented for grid and random deployment networks. Further, extensive simulations compare our scheme with present energy-efficient methods such as random linear coding, multipoint relaying, dominant pruning, and broadcast incremental power scheme. Simulations reveal that FTS offers good performance and adaptability at a low computational cost.

Single-letter characterisations of the admissible rate regions of the Gu-Effros two-hop network and the Gray-Wyner network with side-information are open problems. We show that both problems permit single-letter solutions under the assumption of causal side-information. In particular, the special structure of the causal side-information decoder allows one to match converse theorems to known coding theorems using standard information-theoretic tools. This observation complements similar results by Maor and Merhav for the Heegard-Berger problem and the successive-refinement problem with side-information, and suggests that more general results for causal side-information networks may be possible.

Consider a mobile network wherein nodes are confined to move and communicate in a given area. The network is assumed to be sparse, wherein a direct communication path from a source node via multiple hops to a destination node almost never exists. The nodes resort to storing, carrying, and forwarding packets when a contact occurs, as a means of communication. This paper investigates the question of computing the throughput capacity of the resulting network, in other words, the rate at which a source node can send packets to a destination node using the other nodes in the network as relays. It proposes an accurate generalized framework valid for any mobility model that exhibits stationarity. The framework uses the embedded Markov-Chain approach using which the capacity of such a network can be accurately determined by computing certain well-defined characteristic parameters from the mobility model. Constraints posed by limited node storage and contention between nodes for the wireless channel are also considered in order to obtain a realistic model for the throughput. The paper also illustrates the proposed framework under two specific cases: the random walk, random waypoint, and restricted random waypoint mobility models, and validates the same using simulations.

In this paper, we study rate-compatible puncturing of finite-length low-density parity-check (LDPC) codes. We present a novel rate-compatible puncturing scheme that is easy to implement. Our scheme uses the idea that the degradation in performance is reduced by selecting a puncturing pattern wherein the punctured bits are far apart from each other in the Tanner graph of the code. Although the puncturing scheme presented is tailored to regular codes, it is also directly applicable to irregular parent ensembles. By simulations, the proposed rate-compatible puncturing scheme is shown to be superior to the existing puncturing methods for both regular and irregular LDPC codes over the binary erasure channel (BEC) and the additive white Gaussian noise (AWGN) channel.

In this paper, we propose a new multicast subgraph construction algorithm and a distributed source coding-based multicast (DSCM) protocol for multihop wireless networks. The DSCM emphasize reliability, rate optimality, and energy efficiency. Both algorithms are based on local knowledge of the network. DSCM uses rateless error correcting codes to provide reliability and rate optimality, and distributed source coding to ensure the energy efficiency. We compared our scheme to energy-efficient methods such as network coding (NC) and multicast incremental power (MIP). Simulation results show DSCM performs close to these algorithms. However unlike the proposed algorithm, NC and MIP assume full knowledge of the network topology and have much higher decoding complexity than DSCM.

In this paper, we propose and evaluate two distributed protocols for finding low-cost broadcast and multicast trees in wireless networks. The constructed trees can then be used for reliable and energy-efficient data broadcast and multicast in wireless networks. The proposed schemes, referred to as broadcast decremental power (BDP) and multicast decremental power (MDP), evolve a given spanning tree of a network and form other spanning trees with lower costs of broadcast/multicast. In our schemes, the Bellman-Ford (BF) tree is considered as the initial spanning tree. Links in a network are assumed to have some cost based on parameters such as the distance between nodes, link losses, etc. We consider two different network scenarios. In the first one, nodes in the network have adjustable transmission power, and in the second one, the transmission power is fixed. Exhaustive simulation results are provided for the two different communication power scenarios and different network topologies to evaluate the proposed schemes. We show that broadcast/multicast cost is substantially improved over BF and previous well-known centralized schemes such as broadcast incremental power (BIP) and multicast incremental power (MIP), which can be implemented for the adjustable radius model. For the fixed power model, substantial improvement over BF and Network Coding (NC) is observed.

This paper introduces a novel two-phase broadcast scheme referred to as collaborative rateless broadcast (CRBcast). CRBcast is a scalable approach for reliable and energy-efficient broadcasting in a multihop wireless sensor networks that also addresses load balancing, while requiring no knowledge of network topology. CRBcast combines the energy-efficiency offered by probabilistic broadcasting (PBcast) with the reliability features offered by application-layer rateless coding. In the first phase of CRBcast, packets encoded using a rateless code are dispersed into the network based on PBcast. In the second phase, simple collaboration of neighboring nodes ensures that all nodes recover original data with a very high probability of success. Since the performance of CRBcast rests heavily on that of PBcast, first part of this paper analyzes both analytically and via simulations the probabilistic broadcasting scheme. We then study the effectiveness of CRBcast. We show that CRBcast provides both reliability and energy efficiency simultaneously. Simulation results indicate that CRBcast provides an energy savings of at least 72% and 60% in comparison with flooding and PBcast, respectively.

The problem of reliable and energy-efficient one-to-all broadcasting in multihop wireless networks is investigated in this paper and a low-complexity and scalable scheme (referred to as FTS) is proposed. This scheme utilizes rateless coding and the broadcasting nature of wireless channels to reduce the cost of broadcasting. In FTS, raw data is first encoded, and each node requires to send only a fraction of the total encoded packets. We compare our schemes with present energy-efficient methods such as Network Coding (NC), Multipoint Relaying (MPR), Broadcast Incremental Power (BIP), and Collaborative Rateless Broadcast (CRBcast). Our simulations reveal that our scheme performs well in comparison with these strategies, while having lower complexity and higher adaptability in comparison with some of them.

In this correspondence, a generalization of rateless codes is proposed. The proposed codes provide unequal error protection (UEP). The asymptotic properties of these codes under the iterative decoding are investigated. Moreover, upper and lower bounds on maximum-likelihood (ML) decoding error probabilities of finite-length LT and Raptor codes for both equal and unequal error protection schemes are derived. Further, our work is verified with simulations. Simulation results indicate that the proposed codes provide desirable UEP. We also note that the UEP property does not impose a considerable drawback on the overall performance of the codes. Moreover, we discuss that the proposed codes can provide unequal recovery time (URT). This means that given a target bit error rate, different parts of information bits can be decoded after receiving different amounts of encoded bits. This implies that the information bits can be recovered in a progressive manner. This URT property may be used for sequential data recovery in video/audio streaming

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates

In this paper, we study rate-compatible puncturing of finite-length Low-Density Parity-Check (LDPC) codes. First, we derive simple and yet good bounds on the expected performance of punctured codes (constructed by random puncturing) over Binary Erasure Channel (BEC) as a function of the performance of their parent LDPC code. We then present a novel rate-compatible puncturing scheme that is very easy to implement. Our scheme uses the idea that a more uniform distribution of punctured bits across the Tanner graph results in punctured codes with better performance. Although the puncturing scheme tailored to regular codes is presented, it is also directly applicable to irregular parent ensembles. By simulations, the proposed rate-compatible puncturing scheme is shown to be superior to the existing puncturing methods for both regular and irregular LDPC codes over BEC and Additive White Gaussian Noise (AWGN) Channel.

This paper presents a new improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). The proposed algorithm combines the fact that a considerable fraction of unsatisfied check nodes are of degree two with the concept of guessing bits to perform simple graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to present improved decoding algorithms [H. Pishro-Nik et al., 2004]. Simulations of codes of very short lengths over BEC reveal the superiority of our algorithm over present improved decoding algorithms for a wide range of bit error rates.