Search

Shannon's fundamental bound for perfect secrecy says that the entropy of the secret message cannot be larger than the entropy of the secret key initially shared by the sender and the legitimate receiver. Massey gave an information theoretic proof of this result, however this proof does not require independence of the key and ciphertext. By further assuming independence, we obtain a tighter lower bound, namely that the key entropy is not less than the logarithm of the message sample size in any cipher achieving perfect secrecy, even if the source distribution is fixed. The same bound also applies to the entropy of the ciphertext. The bounds still hold if the secret message has been compressed before encryption. This paper also illustrates that the lower bound only gives the minimum size of the pre-shared secret key. When a cipher system is used multiple times, this is no longer a reasonable measure for the portion of key consumed in each round. Instead, this paper proposes and justifies a new measure for key consumption rate. The existence of a fundamental tradeoff between the expected key consumption and the number of channel uses for conveying a ciphertext is shown. Optimal and nearly optimal secure codes are designed., Submitted to the IEEE Trans. Info. Theory

International audience; In some visible light communication (VLC) systems, transmitters are light sources which support not only illumination but also information broadcast and positioning. Since transmit signals in these systems inevitably interfere with each other at the receiver side, extra devices may be added to synchronize the transmitters, but this impairs an appealing advantage in VLC systems that existing lighting infrastructure can be simply reused. This paper proposes a novel multiple access scheme to realize decentralized asynchronous VLC systems such that both the transmitters and receivers are asynchronous. For a system with N transmitters, two unique codewords of L chips are allocated to each transmitter where L is a prime number larger than 4N. Those codewords are designed to help maintain a constant transmitted average power and enhance channel estimation, as well as conveying data. Our scheme enables the receiver to obtain one channel estimate and one data symbol per L chips. Simulation results show that the proposed scheme significantly outperforms other schemes in the literature in terms of bit error rate and system throughput.

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.

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 Refereed/Peer-reviewed

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 kind of systems share many similarities. In this work, 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 miniservers. 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. Our work not only provides system designers a more efficient content replication solution, but also can push forward the development of the crowdsourcing-based CDNs. Refereed/Peer-reviewed

Shannon's fundamental bound for perfect secrecy says that the source entropy cannot be larger than the entropy of the secret key initially shared by the sender and the legitimate receiver. Massey gave an information theoretic proof of this result, and his proof does not require independence of the key and the source message. By further assuming independence, some stronger results, which govern the probability distributions of the key and the ciphertext, can be shown. These results illustrate that the key entropy is not less than the logarithm of the message sample size in any cipher achieving perfect secrecy, even if the source distribution is fixed. The same bound also applies to the entropy of the ciphertext. These results still hold if the source message has been compressed before encryption.

International audience; 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.

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 $C_{\text{SS}}$ are analyzed. By establishing and comparing lower bounds on $C$ and upper bounds on $C_{\text{SS}}$, various necessary conditions and sufficient conditions such that $C=C_{\text{SS}}$ are obtained. A new class of LOCs such that $C=C_{\text{SS}}$ is identified, which includes LOCs with uniform-given-rank transfer matrices as special cases. It is also demonstrated that $C_{\text{SS}}$ is 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 non-concave function. However, for a LOC with a unique subspace degradation, $C_{\text{SS}}$ can 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., Comment: To appear in IEEE Transactions on Information Theory

This paper studies the error performance of visible light communication systems consisting of multiple transmitter-receiver pairs, where mutual interference exists. Unlike the traditional method which approximates the interference signal as a Gaussian random process and express the bit error rate (BER) as a function of the signal-to-interference-plus-noise power ratio (SINR), we conduct a detailed analysis that captures the signal structure of the interference in terms of the number of light sources, and derive the BER explicitly. Simulation results show that under a realistic small-room scenario with basic illumination requirement, the BER predicted by the Gaussian model is much higher than the exact BER. To provide an alternative metric for resource allocation purpose, we propose a new approximate expression for the BER. This new approximation is shown to be very accurate under our simulation model. Refereed/Peer-reviewed

In visible light communications, it is common to have more than one light sources within the line of sight of a receiver. This paper proposes an adaptive modulation scheme for a system with two light sources and two receivers where two different data streams are sent to the two receivers. The transmitted powers of both light sources are optimized to reduce the bit error rate (BER) at the receivers. Although the optimization problem is non-convex, it can be transformed into a set of linear optimization problems. Analytical results show how to reduce the set and reduce the complexity of the optimization problem. Under various settings, our proposed scheme is compared with multi-user maximum likelihood, repetition coding, and linear zero-forcing precoding techniques. Simulation results show that the proposed scheme outperforms the other techniques in terms of BER. Refereed/Peer-reviewed

International audience; 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.

International audience; 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 be constructed 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 of 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.

Multipath dispersion is a serious challenge in visible light communication (VLC) systems as these systems are used for indoor applications where there can be many reflections of the transmitted signal from the ceiling, walls, equipment, etc. These reflected signals cause intersymbol interference in the receiver and can degrade the performance of the system considerably.Orthogonal frequency-division multiplexing (OFDM) for optical wireless communications was introduced to mitigate multipath dispersion and has been well investigated in the literature. Recently,single-carrier systems with frequency-domain equalization(SCFDE) have been proposed as alternatives to OFDM. In this paper,we present pulse amplitude modulated SCFDE (PAM-SCFDE)to mitigate multipath dispersion in VLC systems.We also compare the proposed PAM-SCFDE with existing OFDM and SCFDE techniques for optical wireless communications in terms of analytical and simulated bit-error-rate (BER) performance, power-spectral efficiency, peak-to-average power ratio (PAPR), and overall system complexity. The proposed PAM-SCFDE requires lower per bit signal-to-noise ratio to achieve a BER of 10−4 or smaller for modulation sizes common in practice, both with and without considering the effects of light-emitting diode transmitters, such as nonlinearity, forward current restriction, and bandwidth limitation.Furthermore, it exhibits better power efficiency for data rates less than 3 bit/s/Hz, lower PAPR and system complexity compared to other systems. Refereed/Peer-reviewed

International audience; Indoor positioning system is a key component for developing various location based services such as indoor navigation in large complex buildings (e.g., commercial center and hospital). Meanwhile, it is challenging to design a cost effective solution which is able to provide high accuracy. A new method, namely Two-Step Movement (2SM), was proposed in [1] to demonstrate how to build a positioning system which requires only one Reference Point (RP) by exploiting user movement. The method can offer good precision and minimize the number of RPs required so as to reduce system implementation cost. Built on 2SM, here we first improve the positioning performance through multi-sampling technique to combat measurement noise. Secondly, we propose the Generalized Two-Step Movement (G2SM) method for device-to-device (D2D) systems in which both the mobile terminal (MT) and RP can be mobile device. The mobile user's position can be derived analytically and given in simple closed-form expression. Its effectiveness in the presence of noise is shown in simulation results.

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. Refereed/Peer-reviewed

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 also propose a fairly general class of linear storage codes and retrieval schemes and derive conditions under which our retrieval schemes are error-free and private. Tradeoffs between the storage cost and retrieval costs are also obtained. Finally, we consider special cases when the underlying storage code is based on an MDS code. Using our proposed method, we show that a randomly generated retrieval scheme is indeed very likely to be private and error-free., Comment: submitted to IEEE Journal of Selected Topics in Signal Processing

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. Refereed/Peer-reviewed

International audience; Small cell techniques are recognized as the best way to deliver high capacity for broadband cellular communications. Femtocell and distributed antenna systems (DAS) are important components in the overall small cell story, but are not the complete solution. They have major disadvantages of very limited cooperation capability and expensive deployment cost, respectively. In this article, we propose a novel mobile-over-FTTx (MoF) network architecture, where a fiber-to-the-x (FTTx) network is enhanced as an integrated rather than a simple backhauling component of a new mobile network delivering low-cost and powerful small cell solutions. In part, the MoF architecture combines the advantages of femtocell and DAS, while overcoming their disadvantages. Implementation challenges and potential solutions are discussed. Simulation results are presented and demonstrate the strong potential of the MoF in boosting the capacity of mobile networks.

International audience; We show by the analytical and simulation results that pre-equalized OFDM based on base-field Hartley transform (BHT-OFDM), which is an alternative air interface for LTE-beyond or 5G, provides significantly better PAPR performance than conventional OFDM systems. We develop a tractable analytical closed-form expression of the statistical distribution of PAPR of pre-equalized BHT-OFDM based on correlated multivariate Rayleigh distributions and verify the result with comprehensive simulation studies. Comparisons show that the analytical and simulation results are consistent. Our study suggests that pre-equalized BHT-OFDM is not only favorable due to its inherent error correction capability but is also highly recommendable for its superiority in power efficiency beyond today's OFDM scheme.

We study a secure distributed source coding prob- lem. 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 one-time 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. Refereed/Peer-reviewed

This paper introduces a new code for asynchronous channel without a common clock between sender and receiver. In communication systems like magnetic recording systems, the existing solutions use the Run Length Limited (RLL) code to prevent errors due to time jitter. In addition, a long communication period is chopped into sessions so that other errors due to environmental noise cannot propagate over a session. However, some recent works have proposed a new code which can outperform RLL. Although this code is optimal for sessions with infinite length, this paper shows that the new code is suboptimal for finite sessions. In this paper, an algorithm is proposed to construct the optimal code for finite sessions. Another algorithm with lower complexity is proposed to construct the suboptimal code. These results can also give a lower bound on the capacity of an asynchronous channel with finite sessions. Refereed/Peer-reviewed

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 trade off between the amount of randomness required and the distortion in ters of variation distance. New tools for non-convex optimization have been developed to establish the results in this paper. 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 trade off 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. Refereed/Peer-reviewed

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., Comment: 5 pages, ISIT2010, Austin

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.

Fano's inequality relates the error probability of guessing a finitely-valued random variable X given another random variable Y and the conditional entropy of X given Y. It is not necessarily tight when the marginal distribution of X is fixed. This paper gives a tight upper bound on the conditional entropy of X given Y in terms of the error probability and the marginal distribution of X. 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.

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.