A hybrid Radio Frequency/Free Space Optical (RF/FSO) communication system exploits the benefits of channel physical layer diversity to improve data rate and link availability. The realisable benefits depend on the respective channel attenuations and their level of independence in the presence of degrading effects. The impact of weather on link attenuations is reported in this paper based on empirical data obtained from a hybrid RF/FSO system where the physical paths were near-coincident and the RF was in the E band. The system was operated in six cities (across five countries) around the world and approximately 15,000 hours of logged data, including weather, was available. This paper is possibly the first to use empirical data to investigate the correlation between the RF and FSO channels across a wide range of weather conditions including dust storms, fog, drizzle, rain, snow, showers and clear skies. It reports 1) the distributions of RF attenuation under different FSO channel states; 2) the joint distribution of the RF and FSO attenuations; and 3) the Pearson correlation coefficient and mutual information. Our empirical data illustrate a negative non-linear correlation during dust storm and a positive linear correlation during fog and snow.

Existing models for Radio Frequency (RF) and Free Space Optical (FSO) attenuations, such as the recommendations published by the International Telecommunication Union (ITU), require physical parameters along the communication channels. In practice, the weather parameters of the entire path are usually unavailable. This paper presents RF and FSO attenuation models built using machine learning algorithms and applied to empirical data. The empirical data consists of weather parameters collected at one end of the channel. Seven pairs of RF/FSO models are trained for specific weather conditions. The importance of each weather parameter is compared. RF attenuation is found to be sensitive to humidity, while FSO attenuation is closely related to scintillation. This paper shows how to obtain a pair of generic random forests that are applicable to seven specific weather conditions. The generic random forests predict the RF and FSO attenuations which have a joint distribution similar to the empirically observed distributions. They preserve the correlation between the RF and FSO attenuations as measured by the correlation coefficient and mutual information. When applied to empirical data, the generic random forests outperform the ITU models and models constructed by linear regression with interaction, both in terms of Root-Mean-Square-Error and R-squared.

The problem of channel gain estimation in visible light communications and positioning is considered in this article. Pilot sequences are designed for simultaneously estimating the channel gains of multiple transmitters in a light system and satisfying the average and maximum transmit power constraint due to illumination purpose. This article illustrates how to design the optimal pilot sequences that minimise the noise variance experienced by a receiver although the optimisation problem is non-convex. Lower bounds on the noise variance are derived for systems with ambient light and systems without ambient light. These bounds reveal the relationship between noise variance, the average transmit power, the maximum transmit power, the number of light sources and pilot length. The necessary and sufficient conditions for the bounds to hold with equality are derived. These conditions establish a bridge between block design theory and channel estimation in visible light systems. Optimal pilot designs which achieve the lower bounds on noise variance can be obtained from balanced block designs and pairwise balanced designs. This article also shows how to optimise the average transmit power of a pilot design for minimising noise variance.

Proving or disproving an information inequality is a crucial step in establishing the converse results in coding theorems. However, an information inequality involving more than a few random variables is difficult to be proved or disproved manually. In 1997, Yeung developed a framework that uses linear programming for verifying linear information inequalities. Under the framework, this paper considers a few other problems that can be solved by using Lagrange duality and convex approximation. We will demonstrate how linear programming can be used to find an analytic proof of an information inequality or an analytic counterexample to disprove it if the inequality is not true in general. The way to automatically find a shortest proof or a smallest counterexample is explored. When a given information inequality cannot be proved, the sufficient conditions for a counterexample to disprove the information inequality are found by linear programming. Lastly, we propose a scalable algorithmic framework based on the alternating direction method of multipliers to accelerate solving a multitude of user-specific problems whose overall computational cost can be amortized with the number of users, and present its publicly-available software implementation for large-scale problems.

The accuracy of channel gain estimation affects the performance of systems for visible light communications (VLC) and visible light positioning (VLP). Pilot sequences were designed for simultaneously estimating the channel gains of multiple transmitters and minimising the total noise variance experienced by receivers. Due to illumination purpose, the sequences also satisfy the constraints on the average and maximum transmitted power. The existing pilot designs in the literature can only be applied to some special cases of average transmitted power. The pilot length is sometimes unnecessarily long. For pilot designs satisfying the power constraints, this paper shows a lower bound on the total noise variance. This bound reveals the relationship between the average and maximum power constraints, the number of LED and pilot length. The necessary and sufficient conditions for the bound to hold with equality are derived. This paper also illustrates some conditions under which the incidence matrix of a balanced incomplete block design is equivalent to a pilot design achieving the minimum total noise variance. So the results in block design theory can be used to construct optimal schemes for channel gain estimation in VLC and VLP systems. Methods for constructing pilot sequences, which satisfy an arbitrary average power constraint, are shown.

Proving or disproving linear information theoretic inequalities is a fundamental task in information theory, and it has also been proved to be important in fields like cryptography and quantum communication theory. Manually proving information inequalities involving more than a few random variables can often be tedious or even intractable. In 1997, Yeung proposed a linear programming framework for verifying information inequalities, which was later extended to construct analytical proofs and disproofs. However, in practice this framework can be very slow for inequalities involving more than ten random variables, thus it is impossible to be applied to a wide range of practical problems. In this paper, we further extend this optimization-theoretic framework by reformulating the LPs and applying the Alternating Direction Method of Multipliers (ADMM) technique, where all the subproblems have closed-form solutions and thus can be solved efficiently. The proposed algorithm is also parallelizable so the performance can be further improved by running it on a GPU. An online web service is developed to allow users to prove or disprove their problem-specific inequalities without installing any software package or dependency.

In visible light communications (VLC) and visible light positioning (VLP), channel gains between receiver and light sources are required to be estimated. Although Time Division Multiple Access (TDMA) is typically used in the channel estimation phase of radio frequency systems, it may not be applicable for VLC and VLP systems due to the maximum power constraint and desired average power constraint that are unique to visible light systems. Recently, combinational code has been proposed as a coding scheme for channel estimation in VLC and VLP. Combinational code can work under the maximum and average power constraints, and it minimises the total and maximum noise variances experienced by the receiver. This paper reports some experimental results to compare combinational code and two schemes based on TDMA. Experimental results show that in terms of noise variance experienced by a receiver, combinational code significantly outperforms other schemes based on TDMA under the same power constraints. Challenges encountered in experiments for channel estimation are discussed and solutions are suggested to overcome these challenges.

In visible light communications (VLC) and visible light positioning (VLP), it is essential to obtain accurate estimates of the channel gains between receiver and multiple light sources. When there are multiple transmitters, time-division multiple access (TDMA) is typically used in the channel estimation phase of radio frequency systems. However, the estimation performance of TDMA-based schemes in VLC and VLP systems is substantially impacted by the maximum power constraint and desired average power constraint that are unique to visible light systems. Under these constraints, this paper explores coding schemes for the simultaneous channel gain estimations of multiple light sources such that the total and maximum noise variances of the channel estimates by the receiver are minimized. Although the minimization problem is non-convex, criteria for optimal codes are found by using majorization theory. Coding scheme satisfying these criteria is proposed that helps to characterize the fundamental tradeoff between noise variance and codeword length.

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.

In a visible light communications system (VLC), light sources are responsible for both illumination, communications and positioning. These light sources inevitably interfere each others at the receiver. To retain the appealing advantage that VLC systems can reuse existing lighting infrastructure, using an extra network to control or synchronize the light sources should be avoided. This paper proposes an uncoordinated multiple access scheme for VLC systems with positioning capability. The proposed scheme does not require a central unit to coordinate the transmission of the transmitters. Transmitters can be asynchronous with one another and with the receiver. Each transmitter is allocated a unique codeword with L chips for a system with up to L-1/2 transmitters where L is prime. Due to the linear growth in complexity with respect to number of transmitters, our proposed scheme is feasible for systems with large numbers of transmitters. Our novel decoder can minimize the effect of additive Gaussian noise at the receiver side. Simulation results show that the proposed decoder outperforms zero-forcing decoder.

In visible light communication (VLC) systems, information are conveyed by visible light instead of radio-frequency electromagnetic waves. Based on received signal strength, accurate indoor positioning systems can also be built. Since a receiver obtains the superposition of signals from all light sources within line of sight together with ambient light, a multiple access scheme is necessary for the receiver to distinguish the received symbol and signal strength from each light source. This paper proposes two multiple access schemes for VLC. The first scheme supports information broadcast and positioning. By using 2Ntimeslots, N transmitters transmit 2N- 1 symbols in total. The second scheme supports positioning only but places emphasis on minimizing the required timeslots. In each 2N timeslots for an odd integer N, the channel gains of 3N - 1/2 transmitters can be estimated.

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.

The major issue of indoor localization system is the trade-off between implementation cost and accuracy. A low-cost system which demands only few hardware devices could save the cost but often it turns out to be less reliable. Aiming at improving classical triangulation method that requires several reference points, this paper proposes a new method, called Two-Step Movement (2SM), which requires only one reference point (RP) by exploiting useful information given by the position change of a mobile terminal (MT), or the user movement. This method can minimize the number of reference points required in a localization system or navigation service and reduce system implementation cost. Analytical result shows that the user position can be thus derived and given in simple closed-form expression. Finally, simulation is conducted to demonstrate its effectiveness under noisy environment.

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.

Entropy is well known to be Schur concave on finite alphabets. Recently, the authors have strengthened the result by showing that for any pair of probability distributions P and Q with Q majorized by P, the entropy of Q is larger than the entropy of P by the amount of relative entropy D(P||Q). This result applies to P and Q defined on countable alphabets. This paper shows the counterpart of this result for the Rényi entropy and the Tsallis entropy. Lower bounds on the difference in the Rényi (or Tsallis) entropy are given in terms of a new divergence which is related to the Rényi (or Tsallis) divergence. This paper also considers a notion of generalized mutual information, namely α-mutual information, which is defined through the Rényi divergence. The convexity/concavity for different ranges of α is shown. A sufficient condition for the Schur concavity is discussed and upper bounds on α-mutual information are given in terms of the Rényi entropy.

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.

This paper proposes two novel and practical designs of angle diversity receivers to achieve multiple-input-multiple-output (MIMO) capacity for indoor visible light communications (VLC). Both designs are easy to construct and suitable for small mobile devices. By using light emitting diodes for both illumination and data transmission, our receiver designs consist of multiple photodetectors (PDs), which are oriented with different inclination angles to achieve high-rank MIMO channels and can be closely packed without the requirement of spatial separation. Due to the orientations of the PDs, the proposed receiver designs are named pyramid receiver (PR) and hemispheric receiver (HR). In a PR, the normal vectors of PDs are chosen the same as the normal vectors of the triangle faces of a pyramid with equilateral N-gon base. On the other hand, the idea behind HR is to evenly distribute the PDs on a hemisphere. Through analytical investigation, simulations and experiments, the channel capacity and bit-error-rate (BER) performance under various settings are presented to show that our receiver designs are practical and promising for enabling VLC-MIMO. In comparison to induced link-blocked receiver, our designs do not require any hardware adjustment at the receiver from location to location so that they can support user mobility. Besides, their channel capacities and BER performance are quite close to that of link-blocked receiver. Meanwhile, they substantially outperform spatially-separated receiver. This study reveals that using angle diversity to build VLC-MIMO system is very promising.

We consider two secret key generation problems under a pairwise independent network model, and propose low complexity key generation schemes in a framework that connects our problems to network flow problems in graphs. Our schemes have two components: 1) local key generation and 2) global key propagation. In the local key generation, we use point-to-point source coding with side information to establish pairwise keys, from which we construct a graph with the capacity of each edge being the key rate of the corresponding point-to-point local key. In the global key propagation, depending on the particular problem, secret keys are delivered to users in the network using various network flow algorithms. In particular, in the first problem in which one is required to generate a group key for a group of users in the network, we propose a network coding-based global key propagation approach. This approach has a low complexity and has a better performance than the existing approach. In the second problem, in which one is required to generate multiple keys simultaneously for different pairs of users, we propose a multicommodity flow-based global key propagation approach. We show that the proposed approach is optimal for the case of generating two keys. For the general case of generating more than two keys, we show that the sum rate of the proposed scheme is larger than an upper bound characterized in this paper divided by a constant.

Proving an information inequality is a crucial step in establishing the converse results in coding theorems. However, an information inequality involving many random variables is difficult to be proved manually. In [1], Yeung developed a framework that uses linear programming for verifying linear information inequalities. Under this framework, this paper considers a few other problems that can be solved by using Lagrange duality and convex approximation. We will demonstrate how linear programming can be used to find an analytic proof of an information inequality. The way to find a shortest proof is explored. When a given information inequality cannot be proved, the sufficient conditions for a counterexample to disprove the information inequality are found by linear programming.

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.

Motivated by communication through a network employing linear network coding, capacities of linear operator channels (LOCs) with arbitrarily distributed transfer matrices over finite fields are studied. Both the Shannon capacity C and the subspace coding capacity CSSare analyzed. By establishing and comparing lower bounds on C and upper bounds on CSS, various necessary conditions and sufficient conditions such that C = CSSare obtained. A new class of LOCs such that C = CSSis identified, which includes LOCs with uniform-given-rank transfer matrices as special cases. It is also demonstrated that CSSis strictly less than C for a broad class of LOCs. In general, an optimal subspace coding scheme is difficult to find because it requires to solve the maximization of a nonconcave function. However, for an LOC with a unique subspace degradation, CSScan be obtained by solving a convex optimization problem over rank distribution. Classes of LOCs with a unique subspace degradation are characterized. Since LOCs with uniform-given-rank transfer matrices have unique subspace degradations, some existing results on LOCs with uniform-given-rank transfer matrices are explained from a more general way.

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.

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.

This paper considers source coding problems with the requirements of perfect secrecy and zero error at receivers. In the problems considered in this paper, there is always one transmitter but there can be one or two receivers. Two different scenarios depending on whether the receivers' side information are present at the transmitter or not are considered. By deriving bounds on the probability masses of the cipher-text and the key, the minimum transmission rate and key rate are characterized. Although zero-error capacities are typically difficult to characterize, the perfect secrecy constraint turns out to be the key that simplifies the problems considered in this paper and makes them analytically tractable.

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.

Single carrier systems with frequency domain equalization (SC-FDE) have been recently proposed for optical wireless systems as alternatives to optical orthogonal frequency division multiplexing (OFDM) to reduce the peak-to-average power ratio (PAPR) of the transmitted signal and improve the system performance. However, these SC-FDE systems have either higher complexity or lower spectrum efficiency. In this paper a low complexity SC-FDE system based on on-off-keying (OOK) modulation is proposed. Theoretical bit-error-rate (BER) analysis is provided based on minimum mean square error (MMSE) equalization for the proposed system and typical optical SC-FDE and OFDM systems. Both analytical and numerical results show that the proposed system significantly outperforms existing SC-FDE and OFDM systems in terms of PAPR, BER and implementation complexity.

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.

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 problem of simultaneously generating multiple independent keys for multiple pairs of users is considered. This problem is motivated by the fact that typically in wireless networks, multiple pairs of users need to establish secret keys for secure communications between these pairs. We propose a secure routing based key distribution approach to establish keys for the terminals. This approach connects the problem at the hand to that of multi-commodity flow problem studied in graph theory. Using the Max Bi-Flow Min Cut Theorem in the graph theory and developing a matching outer-bound, we show that the proposed approach achieves the key capacity region for the case of establishing two keys. For the general case of establishing more than two keys, an upper bound on the achievable sum rate is derived based on the concept of multicut and our proposed approach can achieve a sum rate equals to the upper bound divided by a constant factor.

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.

We study a secure distributed source coding problem. Two terminals with correlated observations would like to send their observations securely to a receiver using minimal transmission rates and key rates. By providing a converse, we show the optimality of a natural structure, in which Slepian-Wolf distributed compression is followed by an application of a onetime pad for encryption. Hence, in contrast to many multiuser setting, the separation of compression and encryption is optimal for this particular case. The optimality of the separation can simplify practical algorithm design. In addition, we constructively demonstrate that switching the order of compression and encryption does not incur any performance loss. Finally, we show that if one requires perfect secrecy and zero error probability, the required rates increase significantly and data compression becomes unnecessary.

This is the first part of a two-part paper on the information theoretic study of biometric security systems. In this paper, the design of single-use biometric security systems is analyzed from an information theoretic perspective. A fundamental trade-off between privacy, measured by the normalized equivocation rate of the biometric measurements, and security, measured by the rate of the key generated from the biometric measurements, is identified. The privacy-security region, which characterizes the above-noted trade-off, is derived for this case. The scenario in which an attacker of the system has side information is then considered. Inner and outer bounds on the privacy-security region are derived in this case. Finally, biometric security systems with perfect privacy are studied, which is shown to be possible if and only if common randomness can be generated from two biometric measurements.

This is the second part of a two-part paper on the information theoretic study of biometric security systems. In this paper, the performance of reusable biometric security systems, in which the same biometric information is reused in multiple locations, is analyzed. The scenario in which the subsystems are jointly designed is first considered. An outer bound on the achievable trade-off between the privacy leakage of the biometric measurements and rates of keys generated at the subsystems is derived. A scheme that achieves the derived outer bound is then presented. Next, an incremental design approach is studied, in which the biometric measurements are reused while keeping the existing system intact. An achievable privacy-security trade-off region for this design approach is derived. It is shown that under certain conditions, the incremental design approach can achieve the performance of the joint design approach. Finally, examples are given to illustrate the results derived.

The performance of reusable biometric security systems in which the same biometric information is reused in several different locations is analyzed in this paper. The scenario in which the subsystems used at different locations are jointly designed is first considered. A fundamental limit of the privacy-security tradeoff is derived. Next, an incremental design approach is studied, in which the biometric measurements are reused while keeping the existing system intact. An achievable privacy-security tradeoff region for this design approach is derived. It is shown that under certain conditions, the incremental design approach can achieve the performance of the joint design approach. Finally, examples are given to illustrate the results.

Strong typicality and the Markov lemma have been used in the proofs of several multiterminal source coding theorems. Since these two tools can be applied to finite alphabets only, the results proved by them are subject to the same limitation. Recently, a new notion of typicality, namely unified typicality, has been defined. It can be applied to both finite or countably infinite alphabets, and it retains the asymptotic equipartition property and the structural properties of strong typicality. In this paper, unified typicality is used to derive a version of the Markov lemma which works on both finite or countably infinite alphabets so that many results in multiterminal source coding can readily be extended. Furthermore, a simple way to verify whether some sequences are jointly typical is shown.

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.

Fano's inequality relates the error probability of guessing a finitely-valued random variableXgiven another random variableYand the conditional entropy ofXgivenY. It is not necessarily tight when the marginal distribution ofXis fixed. This paper gives a tight upper bound on the conditional entropy ofXgivenYin terms of the error probability and the marginal distribution ofX. A new lower bound on the conditional entropy for countably infinite alphabets is also found. The relationship between the reliability criteria of vanishing error probability and vanishing conditional entropy is also discussed. A strengthened form of the Schur-concavity of entropy which holds for finite or countably infinite random variables is given.

Strong typicality, which is more powerful for theorem proving than weak typicality, can be applied to finite alphabets only, while weak typicality can be applied to countable alphabets. In this paper, the relation between typicality and information divergence measures is discussed. The new definition of information divergence measure in this paper leads to the definition of a unified typicality for finite or countably infinite alphabets which is stronger than both weak typicality and strong typicality. Unified typicality retains the asymptotic equipartition property and the structural properties of strong typicality, and it can potentially be used to generalize those theorems which are previously established by strong typicality to countable alphabets. The applications in rate-distortion theory and multisource network coding problems are discussed.

The relation between the Shannon entropy and variational distance, two fundamental and frequently-used quantities in information theory, is studied in this paper by means of certain bounds on the entropy difference between two probability distributions in terms of the variational distance between them and their alphabet sizes. We also show how to find the distribution achieving the minimum (or maximum) entropy among those distributions within a given variational distance from any given distribution. These results are applied to solve a number of problems that are of fundamental interest. For entropy estimation, we obtain an analytic formula for the confidence interval, solving a problem that has been opened for more than 30 years. For approximation of probability distributions, we find the minimum entropy difference between two distributions in terms of their alphabet sizes and the variational distance between them. In particular, we show that the entropy difference between two distributions that are close in variational distance can be arbitrarily large if the alphabet sizes of the two distributions are unconstrained. For random number generation, we characterize the tradeoff between the amount of randomness required and the distortion in terms of variation distance. New tools for non-convex optimization have been developed to establish the results in this paper.

In the literature, different reliability criteria are used in different coding theorems. Weak secrecy and strong secrecy are frequently used in information-theoretic security problems and their implications in terms of the average symbol error probability and block error probability of the adversary are studied in this paper. In particular, strong secrecy always ensures that the adversary has maximum error probability but it is too difficult to be satisfied for a serial source. Weak secrecy can ensure the maximum error probability if the source is stationary and memoryless. In the second part of this paper, the relation among different reliability criteria for source or channel coding are shown. With this result, the channel coding theorem for discrete memoryless channel is generalized with a strong reliability criterion for the direct part and a weak reliability criterion for the converse part.

The Shannon information measures are well known to be continuous functions of the probability distribution for a given finite alphabet. In this paper, however, we show that these measures are discontinuous with respect to almost all commonly used "distance" measures when the alphabet is countably infinite. Such "distance" measures include the Kullback-Leibler divergence and the variational distance. Specifically, we show that all the Shannon information measures are in fact discontinuous at all probability distributions. The proofs are based on a probability distribution which can be realized by a discrete-time Markov chain with countably infinite number of states. Our findings reveal that the limiting probability distribution may not fully characterize the asymptotic behavior of a Markov chain. These results explain why certain existing information-theoretical tools are restricted to finite alphabets, and provide hints on how these tools can be extended to countably infinite alphabet.

We introduce the continuous time asynchronous channel as a model for time jitter in a communication system with no common clock between the transmitter and the receiver. We have obtained a simple characterization for an optimal zero-error self-synchronizable code for the asynchronous channel. The capacity of this channel is determined by both a combinatorial approach and a probabilistic approach. Our results unveil the somewhat surprising fact that it is not necessary for the receiver clock to resynchronize with the transmitter clock within a fixed maximum time in order to achieve reliable communication. This means that no upper limit should be imposed on the run lengths of the self-synchronization code as in the case of run-length limited (RLL) codes which are commonly used in magnetic recording.

Fano's inequality relates the error probability and conditional entropy of a finitely-valued random variable X given another random variable Y. It is not necessarily tight when the marginal distribution of X is fixed. In this paper, we consider both finite and countably infinite alphabets. A tight upper bound on the conditional entropy of X given Y is given in terms of the error probability and the marginal distribution of X. A new lower bound on the conditional entropy for countably infinite alphabet is also found. The equivalence of the reliability criteria of vanishing error probability and vanishing conditional entropy is established in wide generality.

For two probability distributions with finite alphabets, a small variational distance between them does not imply that the difference between their entropies is small if one of the alphabet sizes is unknown. This fact, seemingly contradictory to the continuity of entropy for finite alphabet, is clarified in the current paper by means of certain bounds on the entropy difference between two probability distributions in terms of the variational distance between them and their alphabet sizes. These bounds are shown to be the tightest possible. The Lagrange multiplier cannot be applied here because the variational distance is not differentiable. We also show how to find the distribution achieving the minimum (or maximum) entropy among those distributions within a given variational distance from any given distribution. The results show the limitation of certain algorithms for entropy estimation. An upper bound is obtained for the rate-distortion function with respect to the error frequency criterion, and the minimal average complexity is determined for the generation of a probability distribution with a distortion criterion.

Strong typicality, which is more powerful for theorem proving than the weak typicality, can be applied to finite alphabet only, while weak typicality can be applied to both finite and countably infinite alphabets. In this paper, the relation between typicality and information divergence measures is discussed. This leads to the definition of a unified typicality for finite or countably infinite alphabet which is stronger than both weak typicality and strong typicality

It is well known that the Shannon information measures are continuous functions of the probability distribution when the support is finite. This, however, does not hold when the support is countably infinite. In this paper, we investigate the continuity of the Shannon information measures for countably infinite support. With respect to a distance based on the Kullback-Liebler divergence, we use two different approaches to show that all the Shannon information measures are in fact discontinuous at all probability distributions with countably infinite support

This paper presents three approaches to explore the relation between the Shannon entropy and the von Neumann entropy. The first two approaches are based on the measurement of the quantum state, while the third approach is based on the preparation of the quantum state. Each of these approaches leads to an alternative definition of the von Neumann entropy.