The Chow–Liu algorithm (IEEE Trans. Inform. Theory, 1968) has been a mainstay for the learning of tree-structured graphical models from i.i.d. sampled data vectors. Its theoretical properties have been well-studied and are well-understood. In this paper, we focus on the class of trees that are arguably even more fundamental, namelyhomogeneoustrees in which each pair of nodes that forms an edge has the same correlation$\rho $. We ask whether we are able to further reduce the error probability of learning the structure of the homogeneous tree model whenactive learningis allowed. Our figure of merit is theerror exponent, which quantifies the exponential rate of decay of the error probability with an increasing number of data samples. We design and analyze an algorithmActiveLearningAlgorithm forTrees withHomogeneousEdges (ACTIVE-LATHE), which surprisingly boosts the error exponent by at least 40% when$\rho $is at least 0.8. For all other values of$\rho $, we also observe commensurate, but more modest, improvements in the error exponent. Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph in which we are less confident of being correct.

The Chow-Liu algorithm has been a mainstay for the learning of tree-structured graphical models from i.i.d. sampled data vectors. Its theoretical properties have been well-studied and are well-understood. In this paper, we focus on the class of trees that are arguably even more fundamental, namely homogeneous trees in which each pair of nodes that forms an edge has the same correlation ρ. We ask whether we are able to further reduce the error probability of learning the structure of the homogeneous tree model when active learning is allowed. Our figure of merit is the error exponent, which quantifies the exponential rate of decay of the error probability with an increasing number of data samples. We design and analyze an algorithm Active Learning Algorithm for Trees with Homogeneous Edges (ACTIVE-LATHE), which surprisingly boosts (increases) the error exponent. Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph in which we are less confident of being correct.

We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise with unknown statistics. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure; that is, a structure belonging to the equivalence class containing the true tree. This paper presents a systematic improvement of Katiyar et al. (2020). First, we present a novel impossibility result by deriving a bound on the necessary number of samples for partial recovery. Second, we derive a significantly improved sample complexity result in which the dependence on the minimum correlation $\rho_{\min}$ is $\rho_{\min}^{-8}$ instead of $\rho_{\min}^{-24}$. Finally, we propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery. We provide error exponent analyses and extensive numerical results on a variety of trees to show that the sample complexity of SGA is significantly better than the algorithm of Katiyar et al. (2020). SGA can be readily extended to Gaussian models and is shown via numerical experiments to be similarly superior.

Constrained coding is used widely in digital communication and storage systems. In this article, we study a generalized sliding window constraint called the skip-sliding window. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L + kJ is determined by k+1 windows of length L where window i starts at (iJ + 1)th symbol for all non-negative integers i such that i ≤ k; and the cost constraint E in each window must be satisfied. SSW coding constraints naturally arise in applications such as simultaneous energy and information transfer, and SSW codes are also potential candidates for visible light communications. In this work, two methods are given to enumerate the size of SSW codes and further refinements are made to reduce the enumeration complexity. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and some useful observations are made, such as the fact that SSW codes provide greater capacity than certain related classes of constrained codes. Moreover, we provide noisy capacity bounds for SSW codes.

The "bee-identification problem" was formally defined by Tandon, Tan and Varshney [IEEE Trans. Commun., vol. 67, 2019], and the error exponent was studied. This work extends the results for the "absentee bees" scenario, where a small fraction of the bees are absent in the beehive image used for identification. For this setting, we present an exact characterization of the bee-identification error exponent, and show that independent barcode decoding is optimal, i.e., joint decoding of the bee barcodes does not result in a better error exponent relative to independent decoding of each noisy barcode. This is in contrast to the result without absentee bees, where joint barcode decoding results in a significantly higher error exponent than independent barcode decoding. We also define and characterize the `capacity' for the bee-identification problem with absentee bees, and prove the strong converse for the same.

Clustering Internet of Things (IoT) networks, to alleviate the network scalability problem, provides an opportunity for an adversary to compromise a set of nodes by simply compromising the relay they are associated with. In such scenarios, an adversary who has compromised the relay can affect the network's performance by deliberately dropping the packets transmitted by the IoT devices and/or by corrupting the packets to be forwarded by the relay. In this way, the adversary can successfully mimic a bad radio channel between the IoT devices and the relay, thereby requiring the IoT devices to retransmit more frequently. Such a strategy increases the processing load on the IoT devices and will drain their batteries at a faster rate. To detect such an attack, we present hybrid intrusion detection systems that rely on the monitoring of uplink and downlink packets transmitted between IoT devices and the relay. Specifically, we compare the observed packet drop probabilities against their long-term expected values. The detection rules proposed originate from the generalized likelihood ratio test, where the adversary parameters are estimated using maximum likelihood estimation. A semi-analytical approach to obtain the expressions for the false alarm probability is presented in order to determine the decision thresholds. Results presented show the effectiveness of the proposed detection systems, demonstrate the impact of the choice of adversary parameters on them, and validate the expressions obtained for the false alarm probability.

We apply the generalized sphere-packing bound to two classes of subblock-constrained codes. À la Fazeli et al. (2015), we make use of automorphisms to significantly reduce the number of variables in the associated linear programming problem. In particular, we study binary constant subblock-composition codes (CSCCs), characterized by the property that the number of ones in each subblock is constant, and binary subblock energy-constrained codes (SECCs), characterized by the property that the number of ones in each subblock exceeds a certain threshold. For CSCCs, we show that the optimization problem is equivalent to finding the minimum of N variables, where N is independent of the number of subblocks. We then provide closed-form solutions for the generalized sphere-packing bounds for t-error correcting CSCCs for t ∈ {1, 2, 3}. For SECCs, we provide closed-form solutions for the generalized sphere-packing bounds for single errors in certain special cases. We also obtain improved bounds on the optimal asymptotic rate for CSCCs and SECCs, and provide numerical examples to highlight the improvement.

Communication systems for multicasting information and energy simultaneously to more than one user are investigated. In the system under study, a transmitter sends the same message and signal to multiple receivers over distinct and independent channels. The fundamental communication limit under a received energy constraint, called the multicast capacity-energy function, is studied and a single-letter expression is derived. This is based on coding theorems for compound channels. The problem of receiver segmentation, where receivers are divided into related groups, is also considered.

Consider the problem of identifying a massive number of bees, uniquely labeled with barcodes, using noisy measurements. We introduce this “bee-identification problem characterize the random coding exponent, and derive efficiently computable bounds for this exponent. We demonstrate that joint decoding of barcodes has much better exponent than separate decoding followed by permutation inference.

We consider binary skip-sliding window (SSW) codes which satisfy certain weight constraints over a skip-sliding window. When on-off keying is employed, these weight constraints ensure real-time energy content in the transmitted signal. For a given energy requirement and battery size at an energy harvesting receiver, we investigate the maximum achievable rate using SSW codes which avoid energy outage at the receiver. The SSW codes generalize sliding window constrained (SWC) codes and subblock energy constrained (SEC) codes; we show that SSW codes with window length equal to twice the skip-length can outperform both SWC and SEC codes in terms of outage-constrained rate.

Consider the problem of identifying a massive number of bees, uniquely labeled with barcodes, using noisy measurements. We formally introduce this “bee-identification problem”, define its error exponent, and derive efficiently computable upper and lower bounds for this exponent. We show that joint decoding of barcodes provides a significantly better exponent compared to separate decoding followed by permutation inference. For low rates, we prove that the lower bound on the bee-identification exponent obtained using typical random codes (TRC) is strictly better than the corresponding bound obtained using a random code ensemble (RCE). Further, as the rate approaches zero, we prove that the upper bound on the bee-identification exponent meets the lower bound obtained using TRC with joint barcode decoding.

Constrained coding is used widely in digital communication and storage systems. In this paper, we study a generalized sliding window constraint called the skip-sliding window constraint. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L+kJ is determined by k+1 windows of length L where window i starts at (iJ+1)th symbol for all non-negative integers i such that i ≤ k; and the cost constraint E in each window must be satisfied. In this work, two methods are given to enumerate the size of SSW codes. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and observations such as greater capacity than other classes of codes are made. Moreover, some noisy capacity bounds are given. SSW coding constraints arise in various applications including simultaneous energy and information transfer.

Subblock-constrained codes are an important class of constrained codes, having applications in many diverse fields. In this paper, we provide closed-form expressions for the best known upper bounds on the asymptotic rates of subblock-constrained codes for a range of relative distance values via a generalized sphere-packing approach. In particular, we study binary subblock energy-constrained codes (SECCs), characterized by the property that the number of ones in each subblock exceeds a certain thresh-old, and binary constant subblock-composition codes (CSCCs), characterized by the property that the number of ones in each subblock is constant. Improved bounds on the optimal asymptotic rate for SECCs and CSCCs are obtained by applying a generalized sphere-packing approach and judiciously choosing appropriate constrained spaces for estimating asymptotic ball sizes. We also use numerical examples to highlight the improvement.

Constant subblock-composition codes (CSCCs) are a type of constrained codes in which codewords are partitioned into smaller subblocks with each subblock having the same composition. These constrained codes have applications in diverse fields such as simultaneous energy and information transfer, visible light communication, and design of low-cost authentication methods. In this paper, we characterize the sphere packing error exponent for CSCCs over discrete memoryless channels. We also derive computationally efficient bounds on the CSCC sphere packing error exponent, and show that these bounds are asymptotically tight in the subblock length. In addition, we present several numerical examples, highlighting the impact of subblock length, subblock-composition, and transmission rate, on the CSCC sphere packing error exponent.

The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. The second class is binary subblock energy-constrained codes (SECCs), where the weight of every subblock exceeds a given threshold. We present novel upper and lower bounds on the code sizes and asymptotic rates for the binary CSCCs and SECCs. For a fixed subblock length and small relative distance, we show that the asymptotic rate for CSCCs (respectively SECCs) is strictly lower than the corresponding rate for constant weight codes (CWCs) [respectively heavy weight codes (HWCs)]. Furthermore, for codes with high weight and low relative distance, we show that the asymptotic rate for CSCCs is strictly lower than that of SECCs, which contrasts with the fact that the asymptotic rate for the CWCs is equal to that of the HWCs. We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate. In addition, we present several numerical examples comparing the rates for the CSCCs and SECCs with those for the CWCs and HWCs.

The study of binary constant subblock-composition codes (CSCCs) has recently gained attention due to their application in diverse fields. These codes are a class of constrained codes where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. We present novel upper and lower bounds on the asymptotic rate for binary CSCCs, using the sphere-packing and Gilbert-Varshamov (GV) type bounds, respectively. For a fixed subblock length and small code distance, we show that the asymptotic rate for CSCCs is strictly lower than the corresponding rate for constant weight codes (CWCs). We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate.

The subblock energy-constrained codes (SECCs) have recently been shown to be suitable candidates for simultaneous energy and information transfer, where bounds on SECC capacity were presented for communication over noisy channels. In this paper, we study binary SECCs with given error correction capability, by considering codes with a certain minimum distance. Binary SECCs are a class of constrained codes where each codeword is partitioned into equal sized subblocks, and every subblock has weight exceeding a given threshold. We present several upper and lower bounds on the optimal SECC code size, and also derive the asymptotic Gilbert-Varshamov (GV) and sphere-packing bounds for SECCs. A related class of codes are the heavy weight codes (HWCs) where the weight of each codeword exceeds a given threshold. We show that for a fixed subblock length, the asymptotic rate for SECCs is strictly lower than the corresponding rate for HWCs when the relative distance of the code is small. The rate gap between HWCs and SECCs denotes the penalty due to imposition of weight constraint per subblock, relative to the codeword based weight constraint.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy, which is employed to power its circuitry. In the scenario where the receiver has limited battery size, a signal with bursty energy content may cause power outage at the receiver since the battery will drain during intervals with low signal energy. The energy content in the signal may be regularized by partitioning each codeword into smaller subblocks and requiring that sufficient energy is carried in every subblock duration. In this paper, we study subblock energy-constrained codes (SECCs) which, by definition, are codes satisfying the subblock energy constraint. For SECCs, we provide a sufficient condition on the subblock length to avoid power outage at the receiver. We consider discrete memoryless channels and characterize the SECC capacity, and also provide different bounds on the SECC capacity. Further, we characterize and bound the random coding error exponent for SECCs.

We consider multi-source energy harvesting communication systems, where the energy harvested from two independent processes is used for the transmission of the data packets. The data packets arrive randomly and wait in a queue for accumulation of sufficient energy and for service completion of previously arrived packets. Thus, the data queue dynamics are influenced jointly by the energy arrival process, the data arrival process, and the data service process. This coupling between the data and energy queues makes an exact system analysis extremely hard, and has led researchers to resort to either computationally intensive numerical solutions or to make simplifying approximations. In this paper, we employ Diphase, a two phase queueing formulation, which decouples the wait stages for the energy arrival process and the service process, to derive closed-form expressions for the average packet delay and the probability of data packet loss due to buffer overflow. These expressions are shown to be exact when the service time is negligible, and robust for a relatively wide range of values of the average service time. We show that these expressions are useful in selecting system design parameters, which maximize the throughput while meeting the required quality of service constraints.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy, which is employed to power its circuitry. In the scenario where the receiver has limited battery size, a signal with bursty energy content may cause power outage at the receiver, since the battery will drain during intervals with low signal energy. In this paper, we analyze subblock energy-constrained codes (SECCs), which ensure that sufficient energy is carried within every subblock duration. We consider discrete memoryless channels and characterize the SECC capacity and the SECC error exponent, and provide useful bounds for these values. We also study constant subblock-composition codes (CSCCs), which are a subclass of SECCs where all the subblocks in every codeword have the same fixed composition, and this subblock composition is chosen to maximize the rate of information transfer while meeting the energy requirement. Compared with constant composition codes (CCCs), we show that CSCCs incur a rate loss and that the error exponent for CSCCs is also related to the error exponent for CCCs by the same rate loss term. We exploit the symmetry in CSCCs to obtain a necessary and sufficient condition on the subblock length for avoiding power outage at the receiver. Furthermore, for CSCC sequences, we present a tight lower bound on the average energy per symbol within a sliding time window. We provide numerical examples highlighting the tradeoff between the delivery of sufficient energy to the receiver and achieving high information transfer rates. It is observed that the ability to use energy in real-time imposes less of penalty compared with the ability to use information in real-time.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy to power its circuitry. When the receiver has limited battery size, a signal with bursty energy content may cause power outage since the battery will drain during intervals with low signal energy. The energy content in the signal may be regularized by requiring that sufficient energy is carried in every subblock duration. In this paper, we study constant subblock-composition codes (CSCCs) where all subblocks in every codeword have the same composition, and this composition is chosen such that the real-time energy requirement at the receiver is met. For a given energy storage capacity at the receiver, we give a necessary and sufficient condition on the subblock length for avoiding outage. We show that CSCC capacity on a discrete memoryless channel can be efficiently computed by exploiting certain symmetry conditions, and compare it with the capacity of constant composition codes. We provide numerical examples highlighting the tradeoff between delivery of sufficient energy to the receiver and achieving high information transfer rates.

Energy harvesting communication systems provide a “green” solution by obtaining energy from ambient sources, such as sunlight or vibrations. This energy is stored for transmission of data packets which arrive at the link layer of an energy harvesting transmitter. Since the data and energy arrival processes are independent and random, the data packets wait in a queue for the accumulation of sufficient amount of energy and for service completion of previously arrived packets. Thus, the energy arrival process and the data service process jointly impact the data queue dynamics. This makes the queueing analysis of an energy harvesting communication system challenging. In this paper, we formulate a two stage virtual queueing system which decouples the wait stages for the energy arrival process and the service process. This virtual queueing system leads to closed-form expressions for the average packet delay and the probability of data packet loss due to buffer overflow. We assume that the data and energy arrivals are independent Poisson processes and the service time for data packets may have any general distribution. The expressions for the average packet delay and the probability of buffer overflow are shown to be exact when the service time becomes negligible, and the packet delay gets dominated by data packets waiting for arrival of sufficient energy. These expressions are compared with Monte Carlo simulations and are shown to be robust even when the service time is increased up to sixty percent of the average packet delay.

Delay sensitive applications such as gaming and video streaming require relatively low average packet delay, an important higher layer metric which directly affects the user experience. In this paper, we consider a polling based multiple access scheme and study the impact of channel coding on the average packet delay where the link layer employs Automatic Repeat Request (ARQ) to provide error free packet transmission. The communication model assumes that users share a common physical channel and communicate with a central server which polls them for transmission in a cyclic order. Using an average waiting time analysis, we prove that, compared to an uncoded system, it is sufficient for a coding scheme to reduce the average service time in order to achieve lower average packet delay. We use the bounds on the minimum distance of linear codes to choose that code for which the reduction in the number of retransmissions (due to a decrease in probability of packet error) outweighs the increase in packet time (due to an increase in packet length by channel coding) such that the average service time is minimized. We also show that the percentage reduction in average service time by employing channel coding (compared to an uncoded system) results in corresponding reduction in average transmit energy required for successful transfer of a data packet. Numerical examples are provided to highlight the tradeoffs involved in the choice of an appropriate channel coding scheme.

A construction of a new family of distributed space time codes (DSTCs) having full diversity and low maximum likelihood (ML) decoding complexity is provided for the two phase based cooperative diversity protocols of Jing-Hassibi and the recently proposed generalized non-orthogonal amplify and forward (GNAF) protocol of Rajan et al. The salient feature of the proposed DSTCs is that they satisfy the extra constraints imposed by the protocols and are also four-group ML decodable which leads to significant reduction in ML decoding complexity compared to all existing DSTC constructions. Moreover these codes have uniform distribution of power among the relays as well as in time. Also, simulations results indicate that these codes perform better in comparison with the only known DSTC with the same rate and decoding complexity, namely the coordinate interleaved orthogonal design (CIOD). Furthermore, they perform very close to DSTCs from field extensions which have same rate but higher decoding complexity.