Clarion University

We design low-density parity-check (LDPC) codes that perform at rates extremely close to the Shannon capacity. The codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. Our theoretical analysis of the codes is based on the work of Richardson and Urbanke (see ibid., vol.47, no.2, p.599-618, 2000). Assuming that the underlying communication channel is symmetric, we prove that the probability densities at the message nodes of the graph possess a certain symmetry. Using this symmetry property we then show that, under the assumption of no cycles, the message densities always converge as the number of iterations tends to infinity. Furthermore, we prove a stability condition which implies an upper bound on the fraction of errors that a belief-propagation decoder can correct when applied to a code induced from a bipartite graph with a given degree distribution. Our codes are found by optimizing the degree structure of the underlying graphs. We develop several strategies to perform this optimization. We also present some simulation results for the codes found which show that the performance of the codes is very close to the asymptotic theoretical bounds.

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

Multiuser diversity is a form of diversity inherent in a wireless network, provided by independent time-varying channels across the different users. The diversity benefit is exploited by tracking the channel fluctuations of the users and scheduling transmissions to users when their instantaneous channel quality is near the peak. The diversity gain increases with the dynamic range of the fluctuations and is thus limited in environments with little scattering and/or slow fading. In such environments, we propose the use of multiple transmit antennas to induce large and fast channel fluctuations so that multiuser diversity can still be exploited. The scheme can be interpreted as opportunistic beamforming and we show that true beamforming gains can be achieved when there are sufficient users, even though very limited channel feedback is needed. Furthermore, in a cellular system, the scheme plays an additional role of opportunistic nulling of the interference created on users of adjacent cells. We discuss the design implications of implementing. this scheme in a complete wireless system.

An important means to cope with fading in wireless channels is the use of diversity. Diversity can be obtained over time (interleaving of coded bits), frequency (combining of multipaths in CDMA systems) and space (multiple antennas). The basic idea is to improve performance by creating several independent signal paths between the transmitter and the receiver. In this paper, we propose a scheme that induces random fading when the environment has little scattering and/or the fading is slow. We focus on the downlink of a cellular system. We use multiple antennas at the base-station to transmit the same signal from each antenna modulated by a gain whose phase and magnitude is changing in time in a controlled but pseudo random fashion.

We develop improved algorithms to construct good low-density parity-check codes that approach the Shannon limit very closely. For rate 1/2, the best code found has a threshold within 0.0045 dB of the Shannon limit of the binary-input additive white Gaussian noise channel. Simulation results with a somewhat simpler code show that we can achieve within 0.04 dB of the Shannon limit at a bit error rate of 10/sup -6/ using a block length of 10/sup 7/.

Density evolution is an algorithm for computing the capacity of low-density parity-check (LDPC) codes under message-passing decoding. For memoryless binary-input continuous-output additive white Gaussian noise (AWGN) channels and sum-product decoders, we use a Gaussian approximation for message densities under density evolution to simplify the analysis of the decoding algorithm. We convert the infinite-dimensional problem of iteratively calculating message densities, which is needed to find the exact threshold, to a one-dimensional problem of updating the means of the Gaussian densities. This simplification not only allows us to calculate the threshold quickly and to understand the behavior of the decoder better, but also makes it easier to design good irregular LDPC codes for AWGN channels. For various regular LDPC codes we have examined, thresholds can be estimated within 0.1 dB of the exact value. For rates between 0.5 and 0.9, codes designed using the Gaussian approximation perform within 0.02 dB of the best performing codes found so far by using density evolution when the maximum variable degree is 10. We show that by using the Gaussian approximation, we can visualize the sum-product decoding algorithm. We also show that the optimization of degree distributions can be understood and done graphically using the visualization.

In this paper, we are concerned with the finite-length analysis of low-density parity-check (LDPC) codes when used over the binary erasure channel (BEC). The main result is an expression for the exact average bit and block erasure probability for a given regular ensemble of LDPC codes when decoded iteratively. We also give expressions for upper bounds on the average bit and block erasure probability for regular LDPC ensembles and the standard random ensemble under maximum-likelihood (ML) decoding. Finally, we present what we consider to be the most important open problems in this area.

A quality-of-service (QoS) routing protocol is developed for mobile ad hoc networks. It can establish QoS routes with reserved bandwidth on a per flow basis in a network employing TDMA. An efficient algorithm for calculating the end-to-end bandwidth on a path is developed and used together with the route discovery mechanism of AODV to setup QoS routes. In our simulations the QoS routing protocol produces higher throughput and lower delay than its best-effort counterpart.

Learning from a few examples and generalizing to markedly different situations are capabilities of human visual intelligence that are yet to be matched by leading machine learning models. By drawing inspiration from systems neuroscience, we introduce a probabilistic generative model for vision in which message-passing-based inference handles recognition, segmentation, and reasoning in a unified way. The model demonstrates excellent generalization and occlusion-reasoning capabilities and outperforms deep neural networks on a challenging scene text recognition benchmark while being 300-fold more data efficient. In addition, the model fundamentally breaks the defense of modern text-based CAPTCHAs (Completely Automated Public Turing test to tell Computers and Humans Apart) by generatively segmenting characters without CAPTCHA-specific heuristics. Our model emphasizes aspects such as data efficiency and compositionality that may be important in the path toward general artificial intelligence.

Fear of missing out (FoMO) is a unique term introduced in 2004 to describe a phenomenon observed on social networking sites. FoMO includes two processes; firstly, perception of missing out, followed up with a compulsive behavior to maintain these social connections. We are interested in understanding the complex construct of FoMO and its relations to the need to belong and form stable interpersonal relationships. It is associated with a range of negative life experiences and feelings, due to it being considered a problematic attachment to social media. We have provided a general review of the literature and have summarized the findings in relation to mental health, social functioning, sleep, academic performance and productivity, neuro-developmental disorders, and physical well-being. We have also discussed the treatment options available for FoMo based on cognitive behavior therapy. It imperative that new findings on FoMO are communicated to the clinical community as it has diagnostic implications and could be a confounding variable in those who do not respond to treatment as usual.

The cell surface receptor T cell immunoglobulin mucin domain 1 (TIM-1) dramatically enhances filovirus infection of epithelial cells. Here, we showed that key phosphatidylserine (PtdSer) binding residues of the TIM-1 IgV domain are critical for Ebola virus (EBOV) entry through direct interaction with PtdSer on the viral envelope. PtdSer liposomes but not phosphatidylcholine liposomes competed with TIM-1 for EBOV pseudovirion binding and transduction. Further, annexin V (AnxV) substituted for the TIM-1 IgV domain, supporting a PtdSer-dependent mechanism. Our findings suggest that TIM-1-dependent uptake of EBOV occurs by apoptotic mimicry. Additionally, TIM-1 enhanced infection of a wide range of enveloped viruses, including alphaviruses and a baculovirus. As further evidence of the critical role of enveloped-virion-associated PtdSer in TIM-1-mediated uptake, TIM-1 enhanced internalization of pseudovirions and virus-like proteins (VLPs) lacking a glycoprotein, providing evidence that TIM-1 and PtdSer-binding receptors can mediate virus uptake independent of a glycoprotein. These results provide evidence for a broad role of TIM-1 as a PtdSer-binding receptor that mediates enveloped-virus uptake. Utilization of PtdSer-binding receptors may explain the wide tropism of many of these viruses and provide new avenues for controlling their virulence.

Dynamic resource allocation is an important means to increase the sum capacity of fading multiple-access channels (MACs). In this paper, we consider vector multi-access channels (channels where each user has multiple degrees of freedom) and study the effect of power allocation as a function of the channel state on the sum capacity (or spectral efficiency) defined as the maximum sum of rates of users per unit degree of freedom at which the users can jointly transmit reliably, in an information-theoretic sense, assuming random directions of received signal. Direct-sequence code-division multiple-access (DS-CDMA) channels and MACs with multiple antennas at the receiver are two systems that fall under the model. Our main result is the identification of a simple dynamic power-allocation scheme that is optimal in a large system, i.e., with a large number of users and a correspondingly large number of degrees of freedom. A key feature of this policy is that, for any user, it depends on the instantaneous amplitude of channel state of that user alone and the structure of the policy is "water-filling." In the contest of DS-CDMA and in the special case of no fading, the asymptotically optimal power policy of water-filling simplifies to constant power allocation over all realizations of signature sequences; this result verifies the conjecture made in Verdu and Shamai (1999). We study the behavior of the asymptotically optimal water-filling policy in various regimes of number of users per unit degree of freedom and signal-to-noise ratio (SNR). We also generalize this result to multiple classes, i.e., the situation when users in different classes have different average power constraints.

Chemical signals released by predators or injured prey often induce shifts in the traits of prey species, which may in turn affect species interactions. Here we investigate the role that chemical cues play in mediating species interactions in the littoral food web of lakes. Previous studies have shown that predators induce shifts in the morphology, life history, and behavior of the freshwater snail Physella , but the ecological consequences of developing these inducible defenses are not well documented. We observed habitat use of the freshwater snail Physella gyrina along a depth gradient in a natural lake, and found they increased their use of covered habitats with increasing depth. We hypothesized that this habitat shift was due to changes in the level and type of predation risk, and that the habitat shift would affect periphyton standing crops. These hypotheses were tested in a mesocosm experiment in which we manipulated the presence of molluscivorous fish and crayfish. Predators were confined to cages and snail density was identical in all treatments, so any effects of predators were mediated through trait shifts induced by chemical cues. In the presence of fish, Physella moved under cover, but in the presence of crayfish, Physella avoided cover and moved to the water surface. These non‐lethal effects of predators on snail habitat use influenced the interaction between snails and their periphyton resources. In the presence of fish, periphyton standing crop in covered habitats was reduced to just 8% of periphyton in the absence of fish. Crayfish had no significant effect on periphyton in covered habitats, but they reduced periphyton in near‐surface habitats to 39% of the standing crop in the absence of crayfish. The combined effects of fish and crayfish were generally intermediate to their individual effects. We conclude that because chemical cues often have strong effects on individual traits and trophic interactions are sensitive to trait values, chemical cues may play an important role in shaping the structure and dynamics of food webs.

We investigate the behavior of iteratively decoded low-density parity-check (LDPC) codes over the binary erasure channel in the so-called ldquowaterfall region.rdquo We show that the performance curves in this region follow a simple scaling law. We conjecture that essentially the same scaling behavior applies in a much more general setting and we provide some empirical evidence to support this conjecture. The scaling law, together with the error floor expressions developed previously, can be used for a fast finite-length optimization.

LDPC codes were invented in 1960 by R. Gallager. They were largely ignored until the discovery of turbo codes in 1993. Since then, LDPC codes have experienced a renaissance and are now one of the most intensely studied areas in coding. In this article we review the basic structure of LDPC codes and the iterative algorithms that are used to decode them. We also briefly consider the state of the art of LDPC design.

Predators often induce shifts in the traits of nearby prey, and these trait shifts are important in mediating a variety of evolutionary and ecological processes. However, little is known about the spatial and temporal scales over which predators induce trait shifts. We empirically determined the spatial scale of predator avoidance by measuring the habitat use and growth rates of snails (Physa acuta) held at varying distances from a caged pumpkinseed sunfish (Lepomis gibbosus). Refuge use was highest near the fish and gradually decayed to background level, with a characteristic response range of 1.0 m. Snail growth rates were negligible near the predator but increased with greater separation from fish. The dependence of behavior on the age of chemical cues was measured in a mesocosm experiment in which water was withdrawn from a tank holding pumpkinseeds and held for varying lengths of time before being added to experimental mesocosms with snails. Fresh cues elicited the strongest habitat shifts relative to well-water controls, and avoidance behavior decayed in an exponential manner with increasing cue age. The characteristic lifetime of avoidance behavior was 41 h. Taken together, these results allow us to begin to describe the behavioral landscape created by mobile predators. Corresponding Editor: S. P. Lawler

ABSTRACT Service operations that utilize cross‐trained employees face complex workforce staffing decisions that have important implications for both cost and productivity. These decisions are further complicated when cross‐trained employees have different productivity levels in multiple work activity categories. A method for policy analysis in such environments can be beneficial in determining low‐cost staffing plans with appropriate cross‐training configurations. In this paper, we present an integer linear programming model for evaluating cross‐training configurations at the policy level. The objective of the model is to minimize workforce staffing costs subject to the satisfaction of minimum labor requirements across a planning horizon of a single work shift. The model was used to evaluate eight cross‐training structures (consisting of 36 unique cross‐training configurations) across 512 labor requirement patterns. These structures, as well as the labor requirement patterns, were established based on data collected from maintenance operations at a large paper mill in the United States. The results indicate that asymmetric cross‐training structures that permit chaining of employee skill classes across work activity categories are particularly useful.

In this correspondence, we show that the problem of designing efficient multiple-antenna signal constellations for fading channels can be related to the problem of finding packings with large minimum distance in the complex Grassmannian space. We describe a numerical optimization procedure for finding good packings in the complex Grassmannian space and report the best signal constellations found by this procedure. These constellations improve significantly upon previously known results.

Abstract While the Web has become a worldwide platform for communication, terrorists share their ideology and communicate with members on the “Dark Web”—the reverse side of the Web used by terrorists. Currently, the problems of information overload and difficulty to obtain a comprehensive picture of terrorist activities hinder effective and efficient analysis of terrorist information on the Web. To improve understanding of terrorist activities, we have developed a novel methodology for collecting and analyzing Dark Web information. The methodology incorporates information collection, analysis, and visualization techniques, and exploits various Web information sources. We applied it to collecting and analyzing information of 39 Jihad Web sites and developed visualization of their site contents, relationships, and activity levels. An expert evaluation showed that the methodology is very useful and promising, having a high potential to assist in investigation and understanding of terrorist activities by producing results that could potentially help guide both policymaking and intelligence research.

Understanding spatial patterns of species diversity and the distributions of individual species is a consuming problem in biogeography and conservation. The Cape Floristic Region (CFR) of South Africa is a global hotspot of diversity and endemism, and the Protea Atlas Project, with some 60,000 site records across the region, provides an extraordinarily rich data set to analyze biodiversity patterns. Analysis for the region is developed at the spatial scale of one minute grid-cells (~37,000$ cells total for the region). We report on results for 40 species of a flowering plant family Proteaceae (of about 330 in the CFR) for a defined subregion. Using a Bayesian framework, we develop a two stage, spatially explicit, hierarchical logistic regression. Stage one models the suitability or potential presence for each species at each cell, given species attributes along with grid cell (site-level) climate, precipitation, topography and geology data using species-level coefficients, and a spatial random effect. The second level of the hierarchy models, for each species, observed presence$/$absence at a sampling site through a conditional specification of the probability of presence at an arbitrary location in the grid cell given that the location is suitable. Because the atlas data are not evenly distributed across the landscape, grid cells contain variable numbers of sampling localities. Indeed, some grid cells are entirely unsampled; others have been transformed by human intervention (agriculture, urbanization) such that none of the species are there though some may have the potential to be present in the absence of disturbance. Thus the modeling takes the sampling intensity at each site into account by assuming that the total number of times that a particular species was observed within a site follows a binomial distribution. In fact, a range of models can be examined incorporating different first and second stage specifications. This necessitates model comparison in a misaligned multilevel setting. All models are fitted using MCMC methods. A "best" model is selected. Parameter summaries offer considerable insight. In addition, results are mapped as the model-estimated potential presence for each species across the domain. This probability surface provides an alternative to customary empirical "range of occupancy" displays. Summing yields the predicted species richness over the region. Summaries of the posterior for each environmental coefficient show which variables are most important in explaining species presence. Other biodiversity measures emerge as model unknowns. A considerable range of inference is available. We illustrate with only a portion of the analyses we have conducted, noting that these initial results describe biogeographical patterns over the modeled region remarkably well.