This work focuses on angle of arrival estimation algorithms of massive MIMO LEO satellite-ground networks. In particular, the performance is investigated under pilot contamination effects caused by residual Doppler frequency shifts, a common phenomenon in non-stationary satellite communications, especially when operating in higher frequency bands. This study provides pertinent insights on such impairments and concludes on the suitability as well as shortcomings of these AoA estimation techniques with respect to the different system parameters of massive MIMO LEO satellite networks. Overall, results show that a larger number of antenna elements on-board the satellite provides a better estimation quality and aids to reduce the adverse effects of pilot contamination.

This paper considers the design of heterogeneous multi-cloud systems for big data storage and computing in the presence of cloud collusion and failures. A fundamental concept of such a system is the secrecy capacity, which represents the maximum amount of information that can be stored for each unit of storage space under the requirements of secure distributed computing. A capacity-achieving code is designed for matrix multiplication, a computing subroutine widely used in machine learning applications. The code allows fast parallel decoding and unequal data allocation in the clouds. Such a flexibility leads naturally to the idea of optimizing data allocation to minimize the computing time. Given any feasible storage budget, the optimal solution is derived, characterizing explicitly the fundamental tradeoff between storage and computing. Furthermore, it is shown via majorization theory that the whole tradeoff curve improves if the cloud computing rates are more even. Experiments on Amazon EC2 clusters are conducted, corroborating our theoretical observations and the negligibility of decoding overhead.

Abstract In this paper, a communication system with digital burst‐mode transmission and distributed reception in the presence of carrier frequency offset and Additive White Gaussian Noise (AWGN) is considered. The distributed receiver consists of distributed nodes and a fusion center. Data‐aided frequency estimation at a receiving node can be performed using a preamble. However, accurate frequency estimation may not be achievable at nodes with low signal‐to‐noise ratio (SNR). The problem can be alleviated by collaboration between nodes. Low‐SNR nodes can improve their data‐aided frequency estimation by fetching already decoded symbols from the fusion center. This paper investigates deterministic and data dependent criteria for selecting and fetching of additional symbols. The mean‐square error (MSE) of frequency estimation errors achieved by different criteria are numerically compared via Monte‐Carlo simulations. The Cramer–Rao Lower Bounds (CRLB) for frequency estimation under the considered criteria are presented. The bit‐error‐rates (BER) of the distributed receiver across different symbol fetching schemes are numerically compared.

This work considers cache placement for ultra-dense fog radio access networks (F-RANs). In an F-RAN, the fog access points (F-APs) form overlapping clusters based on their geographical locations. A cluster of F-APs then acts as a distributed cache to cooperatively serve user requests. The fronthaul traffic minimization problem is formulated in information-theoretic terms. For the k-association networks, cache placement can be optimized by concatenating an MDS code with a repetition code. By repeating the same packet in some F-APs, multicasting over the fronthaul link can be done in cache placement, which saves energy and bandwidth. Such an idea is applied to both uncoded and coded caching schemes based on hypergraph coloring. Their associated optimization problems are shown to be NP-complete. For the uncoded case, a suboptimal algorithm is proposed, which carefully repeats the subfiles. For the coded case, a heuristic algorithm that minimizes the field size requirement of the MDS repetition scheme is proposed. Simulation results demonstrate the outstanding performance of the proposed uncoded and coded caching schemes during both the cache placement phase and content delivery phase in reducing fronthaul traffic load and energy consumption.

In fog radio access networks, the limited capacity of the fronthaul link is the bottleneck, which renders a high quality of service for video streaming difficult. To circumvent the problem, popular files can be cached in fog access points during off-peak hours. This work points out that beamforming in the access network can be exploited to reduce fronthaul traffic load by a joint design of cache placement scheme at the fog access points and index-coded transmission scheme over the fronthaul. Simulation results show that a percentage reduction of fronthaul traffic by more than 30% can be achieved.

Cloud computing provides a flexible and cost-effective solution to big data applications. Data privacy, however, is a main concern. To avoid information leakage to a cloud service provider, a user may store portions of encoded data in multiple clouds and perform computing tasks in a distributed way. In this work, nested MDS codes and the criterion of perfect secrecy are adopted. The allocation of encoded data to be stored in heterogeneous clouds with different computing capability is formulated as an optimization problem, subject to data reliability and security constraints. The problem is shown to be feasible if and only if the storage budget is above a certain level. The tradeoff between minimum computation time and storage budget is analytically characterized, and the former is proved to be a piecewise-linear decreasing function of the latter. When the storage budget increases beyond a certain threshold, the optimal computation time levels off. Closed-form expressions of minimum computation time and optimal storage allocation are obtained. Numerical results show that the optimized allocation outperforms equal allocation significantly if the computing rates of different clouds have large variation.

In wireless distributed storage systems, storage nodes are connected by wireless channels, which are broadcast in nature. This paper exploits this unique feature to design an efficient repair mechanism, called broadcast repair, for wireless distributed storage systems in the presence of multiple-node failures. Due to the broadcast nature of wireless transmission, we advocate a new measure on repair performance called repair-transmission bandwidth. In contrast to repair bandwidth, which measures the average number of packets downloaded by a newcomer to replace a failed node, repair-transmission bandwidth measures the average number of packets transmitted by helper nodes per failed node. The storage system we considered can undergo an unlimited number of repair rounds. We obtain an upper bound on the maximum file size that can be supported by a cut analysis of a finite graph. The achievability is shown by codes constructed over a refined information flow graph, which is unbounded. In addition, the optimal storage-bandwidth tradeoff is obtained. The performance of broadcast repair is compared both analytically and numerically with that of cooperative repair, the basic repair method for wired distributed storage systems with multiple-node failures. While cooperative repair is based on the idea of allowing newcomers to exchange packets, broadcast repair is based on the idea of allowing a helper to broadcast packets to all newcomers simultaneously. We show that broadcast repair outperforms cooperative repair, offering a better tradeoff between storage efficiency and repair-transmission bandwidth.

The minimal set of Shannon-type inequalities (or elemental inequalities) plays a central role in efficiently determining whether a given inequality is in fact Shannon-type or not and in computing the linear programming bound for network coding capacity. In many cases, random variables under consideration are subject to additional constraints, such as functional dependence and conditional independence constraints. For example, functional dependence constraints are common in many communication problems due to deterministic encoding and decoding constraints. In other situations, the variables involved may form a Markov chain or in general a Markov random field, leading to conditional independence constraint. Subject to additional constraints, the challenge is how to identify the non-redundant inequalities. While one can always numerically determine the non-redundant inequalities (subject to additional linear equality constraints), it will be instrumental and also important if the non-redundant inequalities can be listed explicitly. In this paper, we show that this is achievable under the functional dependence and full conditional independence constraints.

The majority of works in distributed storage networks assume a simple network model with a collection of identical storage nodes with the same communication cost between the nodes. In this paper, we consider a realistic multi-rack distributed data storage network and present a code design framework for this model. Considering the cheaper data transmission within the racks, our code construction method is able to locally repair the nodes failure within the same rack by using only the survived nodes in the same rack. However, in the case of severe failure patterns when the information content of the survived nodes is not sufficient to repair the failures, other racks will participate in the repair process. By employing the criteria of our multi-rack storage code, we establish a linear programming bound on the size of the code in order to maximize the code rate.

The minimal set of Shannon-type inequalities, called elemental inequalities, plays a central role in efficiently determining whether a given inequality is in fact Shannon-type or not and in computing the linear programming bound for network coding capacity. In previous work we characterised a minimal set when functional dependence constraints are present. In this work we further generalize the characterisation to include Markov random field (MRF) structures which are defined by full conditional mutual independence constraints.

Recently, crowdsourcing-based content delivery networks (CDN) emerge as a promising technology that can distribute massive video content to a vast number of Internet users by crawling bandwidth and storage resources from Internet end devices. Any ordinary Internet users with excessive resources can be recruited into such systems as mini-servers. Different from edge servers equipped with dedicated resources in traditional CDNs, the resource of a single mini-server is scarce and volatile that can vary severely with time, since its bandwidth is shared by many different applications. How to build a robust high performance crowdsourcing-based CDN system has attracted contributions from both academia and industry, but how to solve the drawback caused by unstable uploading bandwidth is still a challenging problem. So far, a prevalent methodology is to migrate the strategies implemented by traditional CDNs into crowdsourcing-based CDN systems based on the fact that these two kinds of systems share many similarities. In this paper, our argument is that the content delivery time can be reduced by replicating coded content on mini-servers (which is almost useless for edge servers in traditional CDNs) to enable downloading users to automatically adapt their downloading progress with oscillating bandwidth capacity from different mini-servers. Theoretical model is created to derive the performance improvement (evaluated in term of average file downloading time) achieved by our strategy, which is further validated via simulation. This paper not only provides system designers a more efficient content replication solution, but also can push forward the development of the crowdsourcing-based CDNs.

The knowledge of view preferences of users is crucial for online video providers to improve their system operations and video recommendations. However, it is challenging to accurately acquire this knowledge by merely relying on a single online video system. In this paper, we conduct a joint statistical study using the cross-platform information obtained from Douban, the largest online video database with video rating functionality in China, and Youku, one of the largest online video streaming systems in China. The Douban dataset includes feedbacks (e.g., movie ratings, comments, and reviews) from all users of different online video systems, and movie metadata (e.g., release date, actors, and directors), based on which we can statistically explore effective and significant factors attributing to video view counts. Meanwhile, our study unveils user behaviors that are latent when only observing a single video system. Finally, a multiple correlation analysis reveals that factors extracted from Douban can significantly increase our ability to predict video view counts. Our study can benefit video caching, video procurement, and advertisement campaign for online video providers.

All large-scale online video systems, for example, Netflix and Youku, make a significant investment on video recommendations that can dramatically affect video information diffusion processes among users. However, there is a lack of efficient methodology to interpret how various recommendation mechanisms affect information diffusion processes resulting in the difficulty to evaluate video recommendation efficiency. In this paper, we propose to quantify and explain video recommendation mechanisms by using epidemic models to mine video view count traces. It is well known that an epidemic model is an efficient approach to model information diffusion processes; while view count traces can be viewed as the results of video information diffusion driven by video recommendations. Thus, we propose a framework based on extended epidemic models to quantify and interpret two recommendation mechanisms, that is, direct and word-of-mouth (WOM) recommendations, by fitting video view count traces collected from Tencent Video, a large-scale online video system in China. Our approach is a novel methodology to evaluate video recommendation mechanisms, and a new perspective to interpret how recommendation mechanisms drive view count evolution.

The minimal set of Shannon-type inequalities (referred to as elemental inequalities), plays a central role in determining whether a given inequality is Shannon-type. Often, there arises a situation where one needs to check whether a given inequality is a constrained Shannon-type inequality. Another important application of elemental inequalities is to formulate and compute the Shannon outer bound for multi-source multi-sink network coding capacity. Under this formulation, it is the region of feasible source rates subject to the elemental inequalities and network coding constraints that is of interest. Hence it is of fundamental interest to identify the redundancies induced amongst elemental inequalities when given a set of functional dependence constraints. In this paper, we characterize a minimal set of Shannon-type inequalities when functional dependence constraints are present.

The online video streaming service is of huge market values with billions of worldwide users. For online video providers, e.g., Netflix, Youku, the crucial question is how to understand users' view behaviors and preferences because this knowledge is important for their business operation. Existing solutions mainly rely on analyzing users' historical view records, which however are not always available, especially for new videos and unprovided videos. Different from existing solutions, we propose to infer user behaviors and preferences by jointly analyzing data collected from multiple platforms (e.g., video streaming systems, video databases, etc.). In particular, we use the movie data crawled from a leading video streaming system (i.e., Youku), and a well-known video database in China (i.e., Douban) for this study. Our investigation points out that movie quality (evaluated in terms of Douban scores) and release date jointly influence viewers' preferences. In addition, we reveal a series of user behaviors, e.g., users are reluctant to post comments or ratings for movies they do not like, and user eyeballs are heavily captured by new movies. Understanding of these user behaviors covered by this study is essential for video recommendation and video popularity prediction which can benefit video procurement and advertisement campaign.

Characterising the capacity region for a network can be extremely difficult. Even with independent sources, determining the capacity region can be as hard as the open problem of characterising all information inequalities. The majority of computable outer bounds in the literature are relaxations of the linear programming bound, which involves entropy functions of random variables related to the sources and link messages. When sources are not independent, the problem is even more complicated. Extension of linear programming bounds to networks with correlated sources is largely open. Source dependence is usually specified through a joint probability distribution, and one of the main challenges in extending linear program bounds is the difficulty (or impossibility) of characterising arbitrary dependences via entropy functions. This paper tackles the problem by answering the question of how well entropy functions can characterise correlation among sources. We show that by using carefully chosen auxiliary random variables, the characterisation can be fairly “accurate”. Using such auxiliary random variables, we also give implicit and explicit outer bounds on the capacity of networks with correlated sources. The characterisation of correlation or joint distribution via Shannon entropy functions is also applicable to other information measures, such as Rényi entropy and Tsallis entropy.

An achievable rate of soliton communication system is derived based on the noise model we studied. Compared to existing results, ours is derived for the system where both eigenvalues and spectral amplitudes are modulated. In addition, we also show an increment of the communication rate by modulating the spectral amplitude of a soliton.

For a user to store data in the cloud, using services provided by multiple cloud storage providers (CSPs) is a promising approach to increase the level of data availability and confidentiality, as it is unlikely that different CSPs are out of service at the same time or collude with each other to extract information of a user. This paper investigates the problem of storing data reliably and securely in multiple CSPs constrained by given budgets with minimum cost. Previous works, with variations in problem formulations, typically tackle the problem by decoupling it into sub-problems and solve them separately. While such a decoupling approach is simple, the resultant solution is suboptimal. This paper is the first one which considers the problem as a whole and derives a jointly optimal coding and storage allocation scheme, which achieves perfect secrecy with minimum cost. The analytical result reveals that the optimal coding scheme is the nested maximum-distance-separable code and the optimal amount of data to be stored in the CSPs exhibits a certain structure. The exact parameters of the code and the exact storage amount to each CSP can be determined numerically by simple 2-D search.

Explicit characterization of the capacity region of communication networks is a long-standing problem. While it is known that network coding can outperform routing and replication, the set of feasible rates is not known in general. Characterizing the network coding capacity region requires the determination of the set of all entropic vectors. Furthermore, computing the explicitly known linear programming bound is infeasible in practice due to an exponential growth in complexity as a function of network size. This paper focuses on the fundamental problems of characterization and computation of outer bounds for multi-source multi-sink networks. Starting from the known local functional dependence induced by the communication network, we introduce the notion of irreducible sets, which characterize implied functional dependence. We provide recursions for the computation of all maximal irreducible sets. These sets act as information-theoretic bottlenecks, and provide an easily computable outer bound for networks with correlated sources. We extend the notion of irreducible sets (and resulting outer bound) for networks with independent sources. We compare our bounds with existing bounds in the literature. We find that our new bounds are the best among the known graph theoretic bounds for networks with correlated sources and for networks with independent sources.

By exploiting superimposed signals at relays, physicallayer network coding (PNC) could significantly improve the throughput of wireless communications systems. However, it is challenging to achieve perfect synchronization between superimposed signals at the relay. In this paper, we propose an approach to resolve the issue of frame-misalignment in PNC using type-I Euclidean geometry low-density parity-check (EG-LDPC) codes with cyclic prefix or zero padding. To estimate the arrival delay between two transmitted signals at the relay, Gold sequences are adopted as pilot sequences in our transmit frames. Simulation results show that our approach can effectively resolve the frame-misalignment issue in PNC.

Private information retrieval scheme for coded data storage is considered in this paper. We focus on the case where the size of each data record is large and hence only the download cost (but not the upload cost for transmitting retrieval queries) is of interest. We prove that the tradeoff between storage cost and retrieval/download cost depends on the number of data records in the system. We propose a class of linear storage codes and retrieval schemes, and derive conditions under which our schemes are error-free and private. Tradeoffs between the storage cost and retrieval costs are also obtained.

In this paper, we make the first step on encoding information using the spectral amplitudes, which provides a potential of increasing the data rate of N-soliton communication systems. Specifically, we propose a noise model for the magnitudes of the spectral amplitudes. Its statistics are obtained without the Gaussian approximation on the noise distribution when N = 1.

This paper considers an entropy maximisation problem subject to functional dependency constraints. We compare Delsarte's linear programming (LP) bound, an information theoretic LP bound, and functional dependency bounds and prove that both Delsarte's LP bound and the information theoretic LP bound are at least better than the functional dependency bound.

The problem of storing data reliably and securely in multiple cloud storage providers (CSPs) with minimum cost is investigated. A jointly optimal coding and storage allocation scheme, which achieves perfect secrecy with minimum cost, is derived. The optimal coding scheme is shown to be the nested maximum-distance-separable code and the optimal amounts of data to be stored in the CSPs is proven to exhibit a three-level structure. The exact parameters of the code and the exact storage amount to each CSP can be determined numerically by simple one-dimensional search.

Luby transform (LT) codes are a class of rateless codes that automatically adapt their rate to the quality of the communication channel. In the original LT codes, fixed check-node degree distributions are used to combine variable nodes uniformly at random to extend the code graph and produce code bits. Here we propose a different approach: we design a sequence of rate-compatible degree distributions, and develop an algorithm that produces code bits in a manner such that the resulting degree distributions follow the designed sequence. Using this new design framework, we develop low-complexity LT codes suitable for time-varying noisy channels. Performance and complexity of the proposed LT codes are measured in terms of bit error rate and average number of edges per information and coded bit, respectively. Numerical examples illustrate the resulting trade-off between performance and complexity of the designed LT codes.

Following the recent proposed nonlinear frequency division multiplexing (NFDM) scheme [1] for integrable communication channels, we have designed a class of signals called spatially periodic signals that maintain their shape periodically during transmission. This class of signals is of interest because the encoding and decoding processes are much simpler. This paper establishes properties of spatially periodic signals, leading to a better understanding of how spatially periodic signals should be designed and the tradeoff between various system parameters including signal energy and minimum period.

Locally repairable codes are used in distributed storage networks to minimise the number of survived nodes required to repair a failed node. However, the robustness of these codes is a main concern since locally repair procedure may fail when there are multiple node failures. This paper proposes a new class of robust locally repairable codes which guarantees that a failed node can be repaired locally even when there are multiple node failures. Upper bound on the size of robust locally repairable codes using linear programming tools are obtained and examples of robust locally repairable codes attaining these bounds are constructed.

In practical distributed storage networks, data centres house hundreds of racks, each of which contains several storage nodes. However, the majority of works in distributed storage assume a simple network model with a collection of identical storage nodes with same communication cost between the nodes. In this paper, we consider a more realistic rack model of storage network and present a code design framework for this model. Using our code construction method, node failures within a rack can be repaired locally by survived nodes in the same rack or by the other survived racks when the information content of the same rack is not sufficient to repair the failed nodes.

Locally repairable (LR) codes are used in distributed storage systems to minimize the number of storage nodes involved in node repair. While existing constructions of LR codes do not take the topology of the storage network into account, this work focuses on designing LR codes over a network. A new concept called node locality is introduced. It is shown that the decision problem of determining whether a binary linear LR code exists, subject to the constraints of code rate, symbol locality, node locality, and repair cost, is NP-complete. The corresponding optimization version, which aims to maximize the code rate, is also considered. It is proved that the problem can be reduced to the minimum k-set cover problem, and can be solved in polynomial time for the special case where the symbol locality is one. For the general case where the symbol locality is greater than or equal to two, the problem is NP-hard and can be approximately solved by a greedy algorithm.

This paper presents a flexible irregular model for heterogeneous cloud storage systems and investigates how the cost of repairing failed nodes can be minimized. The fractional repetition code, originally designed for minimizing repair bandwidth for homogeneous storage systems, is generalized to the irregular fractional repetition code, which is adaptable to heterogeneous environments. The code structure and the associated storage allocation can be obtained by solving an integer linear programming problem. For moderate sized networks, a heuristic algorithm is proposed and shown to be near-optimal by computer simulations.

In this paper, we use entropy functions to characterize the set of rate-capacity tuples achievable with either zero decoding error, or vanishing decoding error, for general network coding problems for acyclic networks. We show that when sources are colocated, the outer bound is tight and the sets of zero-error achievable and vanishing-error achievable rate-capacity tuples are the same. Then, we extend this paper to networks subject to linear encoding constraints, routing constraints (where some or all nodes can only perform routing), and secrecy constraints. Finally, we show that even for apparently simple networks, design of optimal codes may be difficult. In particular, we prove that for the incremental multicast problem and for the single-source secure network coding problem, characterization of the achievable set can be very hard and linear network codes may not be optimal.

We propose a framework for robust content distribution in networks such that each network node stores a description of the source for users to access and it is robust against any single node failure. The fundamental problem is to identify the tradeoff among various parameters such as storage size, repair bandwidth and the level of distortion in the reconstructed estimate. We show that when we design a robust multiple description code, it is usually favourable that the descriptions should be as correlated as possible to reduce the amount of repair bandwidth in our network.

The max-flow outer bound is achievable by regenerating codes for functional repair distributed storage system. However, the capacity of exact repair distributed storage system is an open problem. In this paper, the linear programming bound for exact repair distributed storage systems is formulated. A notion of symmetrical sets for a set of random variables is given and equalities of joint entropies for certain subsets of random variables in a symmetrical set is established. Concatenation coding scheme for exact repair distributed storage systems is proposed and it is shown that concatenation coding scheme is sufficient to achieve any admissible rate for any exact repair distributed storage system. Equalities of certain joint entropies of random variables induced by concatenation scheme is shown. These equalities of joint entropies are new tools to simplify the linear programming bound and to obtain stronger converse results for exact repair distributed storage systems.

It is a well known result that the Kraft inequality is a necessary and sufficient condition for the existence of a uniquely decodable code. This paper provides an inequality which is a counterpart of the Kraft inequality in Error free Perfect Secrecy (EPS) system. Our inequality is a necessary and sufficient condition for the existence of an EPS system. It also illustrates some necessary and sufficient conditions for an EPS system to achieve the minimal expected key consumption.

Characterising the capacity region for a network can be extremely difficult. Even with independent sources, determining the capacity region can be as hard as the open problem of characterising all information inequalities. The majority of computable outer bounds in the literature are relaxations of the Linear Programming bound which involves entropy functions of random variables related to the sources and link messages. When sources are not independent, the problem is even more complicated. Extension of Linear Programming bounds to networks with correlated sources is largely open. Source dependence is usually specified via a joint probability distribution, and one of the main challenges in extending linear program bounds is the difficulty (or impossibility) of characterising arbitrary dependencies via entropy functions. This paper tackles the problem by answering the question of how well entropy functions can characterise correlation among sources. We show that by using carefully chosen auxiliary random variables, the characterisation can be fairly “accurate”.

Quasi-uniform random vectors have probability distributions that are uniform over their projections. They are of fundamental interest because a linear information inequality is valid if and only if it is satisfied by all quasi-uniform random vectors. In this paper, we investigate properties of codes induced by quasi-uniform random vectors. We prove that quasi-uniform codes (which include linear and almost affine codes as special cases) are distance-invariant and that Greene's Theorem and the Critical Theorem of Crapo and Rota hold in the setting of quasi-uniform codes. We show that both theorems are essentially combinatorial but not algebraical in nature. Linear programming bounds proposed by Delsarte are extended for quasi-uniform codes.

In a heterogenous networking environment, a new practical distributed storage model is defined by introducing the concepts of repair topology and retrieval sets. How to repair a failed storage node so as to minimize the system repair cost is investigated. It is shown that the repair cost minimization problem can be decomposed into a combinatorial problem and an integer linear programming problem. Moreover, a heuristic algorithm to find suboptimal repair topologies is given.

In this paper, we show that the characterisation of all determinant inequalities for n × n positive definite matrices is equivalent to determining the smallest closed and convex cone containing all entropy functions induced by n scalar jointly Gaussian random variables. We have obtained inner and outer bounds on the cone by using representable functions and entropic functions. In particular, these bounds are tight and explicit for n ≤ 3, implying that determinant inequalities for 3 × 3 positive definite matrices are completely characterized by Shannon-type information inequalities.

This paper investigates a new method in proving converses in secure communication problems. The method gives a converse result in terms of the logarithm of support size instead of entropy. The results are connected to constrained information inequalities involving three random variables. A new constrained non-Shannon type inequality is shown.

Exploiting the recent framework of normal factor graphs, this paper presents a transparent exposition of the Krawtchouk transform and its relationship to the Fourier transform and the MacWilliams identities. Such treatment of the subject is believed to be more accessible to wider audience of coding theory.

We investigate how to design an error-free and perfectly secure crypto-system. In particular, we are interested in the efficiency of an EPS system. A approach based on prefix codes is introduced. Also an optimum partition code is introduced where the key consumption is minimum for fixed number of channel uses. Results obtained in this paper can also be applied to study the tradeoff between the key consumption and the number of channel uses needed to transmit the encrypted message.

The polymatroid axioms are dominantly used to study the capacity limits of various communication systems. In fact for most of the communication systems, for which the capacity is known, these axioms are solely required to obtain the characterization of capacity. Moreover, the polymatroid axioms are stronger tools to tackle the implication problem for conditional independencies compared to the axioms used in Bayesian networks. However, their use is prohibitively complex as the number of random variables increases since the number of inequalities to consider increases exponentially. In this paper we give a compact characterization of the minimal set of polymatroid axioms when arbitrary conditional independence and functional dependence constraints are given. In particular, we identify those elemental equalities which are implied by given constraints. We also identify those elemental inequalities which are redundant given the constraints.

Shannon's fundamental bound for perfect secrecy says that the entropy of the secret message U cannot be larger than the entropy of the secret key R shared by the sender and the legitimate receiver. Massey gave an information theoretic proof of this result and the proof does not require U and R to be independent. By adding an extra assumption that I(U; R) = 0, we show a tighter lower bound on H(R) by proving that the logarithm of the message sample size cannot be larger than the entropy of the secret key. Then we consider that a perfect secrecy system is used multiple times. A new parameter, namely effective key consumption, is defined and justified. This paper shows the existence of a fundamental tradeoff between the effective key consumption and the number of channel uses for transmitting a ciphertext.

The interval algorithm by Han and Hoshi is an efficient algorithm which can convert a sequence of random variables into another sequence of random variable with a required probability distribution. In this paper, we extend the interval algorithm to transform a pair of sequences of random variable into another pair of sequences of random variables. The extension allows some independency or functional dependency constraints between the input and output sequences. The possible applications in key extraction and random number generation are discussed. The proposed algorithm can asymptotically achieve the optimal output rate and it minimizes the length of the input sequence required to generate the output sequence for certain input distributions.

In this tutorial paper, we focus on the basic theory of linear secure network coding. Our goal is to present fundamental results and provide preliminary knowledge for anyone interested in the area. We first present a model for secure network coding and then a necessary and sufficient condition for a linear network code to be secure. Optimal methods to construct linear secure network codes are also provided. For further investigation of the secure properties of linear network codes, we illuminate different secure criteria and requirements, with a few alternative models.

Linear polymatroids have a strong connection to network coding. The problem of finding the linear network coding capacity region is equivalent to the characterization of all linear polymatroids. It is well known that linear polymatroids must satisfy the inequalities of Ingleton (Combin. Math. Appln., 1971). However, it has been an open question for years as to whether these inequalities are sufficient. It was until recently that new subspace rank inequalities have been discovered (independently by Kinser and Dougherty, ). In this paper, we propose a new approach to investigate properties of linear polymatroids. Specifically, we demonstrate how to construct a new polymatroid that satisfies not only the Ingleton and DFZ inequalities, but also lies outside the minimal closed and convex cone containing all linear polymatroids. Using this polymatroid, we prove that all truncation-preserving inequalities (including Ingleton inequalities and DFZ inequalities) are insufficient to characterize linear polymatroids.

The Ingleton inequalities are the inequality constraints known to be required of representable matroids. For a matroid ofnelements, there are 16nIngleton inequalities. In this paper, we show that many of these inequalities are redundant. We explicitly determine the unique minimal set of Ingleton inequalities, which number on the order of 6n/4-O(5n). In information theory, these inequalities are required of the entropy functions of certain random variables constructed from linear subspaces. As a result, these inequalities appear as constraints in linear programming outer bounds for the capacity region of multisource network coding where the codes are required to be linear. Ingleton inequalities have also played an instrumental role in demonstrating the insufficiency of linear codes for multisource network coding. The reduction that we obtain for Ingleton inequalities is sufficiently large to meaningfully reduce the complexity of these linear programming bounds.

We present an achievable rate region for the multistage successive-refinement problem with side-information. We also present an upper bound for the rate-distortion function for lossy source coding with side-information at many decoders. Characterising this rate-distortion function is a long-standing open problem, and it is widely believed that the tightest upper bound is provided by Theorem 2 of Heegard and Berger's paper “Rate distortion when side information may be absent” (IEEE Trans. Inf. Theory, 1985). We give a counterexample to Heegard and Berger's result.

We consider the problem of transmitting a Gaussian source over a Rayleigh fading channel where some side-information may be available to the receiver. Our objective is to minimize the average distortion at the receiver. We consider two source models with side-information: 1) the Heegard-Berger model where "side-information may be absent", and 2) successive refinement with degraded side-information. We show that the average distortion problem can be numerically solved by convex optimization techniques. Furthermore, in high SNR, we obtain an analytical solution that shows that the side-information does not affect the distortion exponent, but causes an offset with respect to the case without side information. Numerical results show that our analytical high SNR approximation gives accurate results even at medium SNR.

The arbitrarily varying channel can be modeled as communication in the presence of a jammer. In this paper we propose a new model: a jammer who knows the channel input, and where the transmitter and receiver share a secret random key. Shared randomness differentiates this scenario from the case where the jammer knows the message. For sufficiently large key rate, we determine the capacity of this channel (which may be strictly smaller than the case where the jammer knows only the message). We also provide an upper bound on the minimum key rate required to achieve capacity. We prove that additionally revealing the message to the jammer does not change the capacity, provided the key rate is sufficiently large. This new capacity result differs from existing results for the AVC, and in fact coincides with a well-known upper bound on the deterministic coding capacity of the AVC with maximum error. Without secret keys, our problem degenerates to deterministic coding for the AVC with maximum probability of error, a well-known hard problem. Our results demonstrate that knowledge of the channel input is better than knowledge of the message for the jammer.

We study the network coding capacity of multi-source, multi-sink networks with colocated sources, but where each sink may demand a different subset of the sources. We show that in this scenario, the set of admissible (zero probability of decoding errors) and achievable (vanishing probability of decoding errors) rate capacity tuples are the same. We also simplify the capacity region by showing that the outer bound obtained in “A First Course in Information Theory” (Yeung, 2002) is in fact tight. We conjecture that this bound remains tight, even when the sources are not colocated.

Quasi-uniform random variables have probability distributions that are uniform over their supports. They are of fundamental interest because a linear information inequality is valid if and only if it is satisfied by all quasi-uniform random variables. In this paper, we investigate properties of codes induced by quasi-uniform random variables.We prove that quasi-uniform codes (which include linear and almost affine codes as special cases) are distance-invariant and that Greene's Theorem and the Critical Theorem of Crapo and Rota hold in the setting of quasi-uniform codes. We also outline how these results provide a coding theoretic approach to construct information inequalities.

An Ingletonian polymatroid satisfies, in addition to the polymatroid axioms, the inequalities of Ingleton. These inequalities are required for a polymatroid to be representable. It has been an open question as to whether these inequalities are also sufficient. Representable polymatroids are of interest in their own right. They also have a strong connection to network coding. In particular, the problem of finding the linear network coding capacity region is equivalent to the characterization of all representable, entropic polymatroids. In this paper, we describe a new approach to adhere two polymatroids together to produce a new polymatroid. Using this approach, we can construct a polymatroid that is not inside the minimal closed and convex cone containing all representable polymatroids. This polymatroid is proved to satisfy not only the Ingleton inequalities, but also the recently reported inequalities of Dougherty, Freiling and Zeger. A direct consequence is that these inequalities are not sufficient to characterize representable polymatroids.

We present a new inner bound for the admissible rate region of the t-stage successive-refinement problem with side-information. We also present a new upper bound for the rate-distortion function for lossy-source coding with multiple receivers and side-information. A single-letter characterisation of this rate-distortion function is a long-standing open problem, and it is widely believed that the tightest upper bound is provided by Theorem 2 of Heegard and Berger's paper “Rate Distortion when Side Information may be Absent,” IEEE Trans. Inform. Theory, 1985. We give a counterexample to Heegard and Berger's result.

Suppose a stationary memoryless source is observed through a discrete memoryless channel. Determining analytical confidence intervals on the source entropy is known to be a difficult problem, even when the observation channel is noiseless. In this paper, we determine confidence intervals for estimation of source entropy over discrete memoryless channels with invertible transition matrices. A lower bound is given for the minimum number of samples required to guarantee a desired confidence interval. All these results do not require any prior knowledge of the source distribution, other than the alphabet size. When the alphabet size is countably infinite or unknown, we illustrate an inherent difficulty in estimating the source entropy.

This paper considers a key agreement problem in which two parties aim to agree on a key by exchanging messages in the presence of adversarial tampering. The aim of the adversary is to disrupt the key agreement process, but there are no secrecy constraints (i.e. we do not insist that the key is kept secret from the adversary). The main results of the paper are coding schemes and bounds on maximum key generation rates for this problem.

In this paper, we show how to construct a factor graph from a network code. This provides a systematic framework for decoding using message passing algorithms. The proposed message passing decoder exploits knowledge of the underlying communications network topology to simplify decoding. For uniquely decodeable linear network codes on networks with error-free links, only the message supports (rather than the message values themselves) are required to be passed. This proposed simplified support message algorithm is an instance of the sum-product algorithm. Our message-passing framework provides a basis for the design of network codes and control of network topology with a view toward quantifiable complexity reduction in the sink terminals.

Explicit characterization and computation of the multi-source network coding capacity region (or even bounds) is long standing open problem. In fact, finding the capacity region requires determination of the set of all entropic vectors Gamma*, which is known to be an extremely hard problem. On the other hand, calculating the explicitly known linear programming bound is very hard in practice due to an exponential growth in complexity as a function of network size. We give a new, easily computable outer bound, based on characterization of all functional dependencies in networks. We also show that the proposed bound is tighter than some known bounds.

One of the main theoretical motivations for the emerging area of network coding is the achievability of the max-flow/min-cut rate for single source multicast. This can exceed the rate achievable with routing alone, and is achievable with linear network codes. The multi-source problem is more complicated. Computation of its capacity region is equivalent to determination of the set of all entropy functions Gamma*, which is non-polyhedral. The aim of this paper is to demonstrate that this difficulty can arise even in single source problems. In particular, for single source networks with hierarchical sink requirements, and for single source networks with secrecy constraints. In both cases, we exhibit networks whose capacity regions involve Gamma*. As in the multi-source case, linear codes are insufficient.

The Ingleton-LP bound is an outer bound for the multicast capacity region, assuming the use of linear network codes. Computation of the bound is performed on a polyhedral cone obtained by taking the intersection of half-spaces induced by the basic (Shannon-type) inequalities and Ingleton inequalities. This paper simplifies the characterization of this cone, by obtaining the unique minimal set of Ingleton inequalities. As a result, the effort required for computation of the Ingleton-LP bound can be greatly reduced.

We consider the problem of source coding with receiver side information for the simple network proposed by R. Gray and A. Wyner in 1974. In this network, a transmitter must reliably transport the output of two correlated information sources to two receivers using three noiseless channels: a public channel which connects the transmitter to both receivers, and two private channels which connect the transmitter directly to each receiver. We extend Gray and Wyner's original problem by permitting side information to be present at each receiver. We derive inner and outer bounds for the achievable rate region and, for three special cases, we show that the outer bound is tight.

In communications networks, the capacity region of multisource network coding is given in terms of the set of entropy functions Gamma*. More broadly, determination of Gamma*would have an impact on converse theorems for multi-terminal problems in information theory. This paper provides several new dualities between entropy functions and network codes. Given a functiongges 0 defined on all subsets ofNrandom variables, we provide a construction for a network multicast problem which is ldquosolvablerdquo if and only ifgis the entropy function of a set of quasi-uniform random variables. The underlying network topology is fixed and the multicast problem depends ongonly through link capacities and source rates. A corresponding duality is developed for linear network codes, where the constructed multicast problem is linearly solvable if and only ifgis linear group characterizable. Relaxing the requirement that the domain ofgbe subsets of random variables, we obtain a similar duality between polymatroids and the linear programming bound. These duality results provide an alternative proof of the insufficiency of linear (and abelian) network codes, and demonstrate the utility of non-Shannon inequalities to tighten outer bounds on network coding capacity regions.

This paper studies properties of entropy functions that are induced by groups and subgroups. We showed that many information theoretic properties of those group induced entropy functions also have corresponding group theoretic interpretations. Then we propose an extension method to find outer bound for these group induced entropy functions.

We consider a network multicast example that relates the solvability of the multicast problem with the existence of an entropy function. As a result, we provide an alternative approach to the proving of the insufficiency of linear (and abelian) network codes and demonstrate the utility of non- Shannon inequalities to tighten outer bounds on network coding capacity regions.

It is well-known that linear network codes are sufficient to achieve maximal network throughput (or bandwidth utilization efficiency) in the single-session multicast scenario. However, it is not known whether they are still optimal in maximizing network throughput in the multiple-session scenario (either single-source or multiple-source ones). In this paper, we prove that a more general class of network codes - group network codes - are sufficient to achieve the maximal throughput in the single-source multiple-session multicast scenario.

A conditionally Gaussian channel is a vector channel in which the channel output, given the channel input, has a Gaussian distribution with (well-behaved) input-dependent mean and covariance. We study the capacity-achieving probability measure for conditionally Gaussian channels subject to bounded-input constraints and average cost constraints. Many practical communication systems, including additive Gaussian noise channels, certain optical channels, fading channels, and interference channels fall within this framework. Subject to bounded-input constraint (and average cost constraints), we show that the channel capacity is achievable and we derive a necessary and sufficient condition for a probability measure to be capacity achieving. Under certain conditions, the capacity-achieving measure is proved to be discrete.

A conditional Gaussian (CG) channel is a discrete-time memoryless channel such that an admissible channel input gives rise to a channel output that is Gaussian distributed with an expectation vector and a covariance matrix. In this paper, closed and bounded subset of receiver, and the channel constraint is called the bounded-input constraint is presented. The mutual information between the channel input and output with an input probability measure which satisfies the channel input constraints is maximized. An input probability measure is said to be discrete in amplitude and uniform in phase (DAUP) if the probability distribution of the amplitude is discrete with a finite number of probability mass points, and the phase is uniformly distributed

We establish a one-to-one correspondence between information inequalities and group inequalities. The major implication of our result is that we can prove information inequalities by proving the corresponding group inequalities, and vice versa. By giving a group-theoretic proof for all Shannon-type inequalities, we suggest that new inequalities could be discovered by making use of the rich set of tools in group theory. On the other hand, via a non-Shannon-type information inequality discovered by Zhang and Yeung (1997), we obtain a new inequality in group theory whose meaning is yet to be understood.