Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Search Results

Now showing 1 - 10 of 11

Learning Binaural Processing in Biological Networks
(1989) Gopalaswamy, Preetham; Shamma, S.; ISR
It has always intrigued man as to how the human body performs so many complicated functions with the speed and accuracy that it does. One such task is that of sound localization in space, the ability to determine the location of a sound source with considerable accuracy. A biologically realistic neural network is proposed for the binaural processing of interaural time and intensity cues that closely resembles computational schemes suggested for sterepsis (depth perception) in vision. The important feature of this network is that it does not use any neural delay lines to generate such attributes of binaural hearing such as lateralization of all audible frequencies and the detection of enhancement of signals in a noisy environment. Temporal shifts between the signals at the ears, arising from sound sources at different locations on the azimuth cause spatial disparities in the corresponding travelling waves set up on the basilar membranes in the two ears. The two dimensional network proposed uses these spatial differences between instantaneous outputs at the two ears to measure interaural differences. The network operation approximately computes the cross-correlation between the two cochlear outputs by combining the ipsilateral input at a given characteristic frequency (CF) with contralateral inputs from locally off-CF locations. Some of the results obtained from this network are presented. Having proposed a network, the next question is whether such a connection is genetically present in the body or whether it is formed over a long period of time by a gradual process of learning. Assuming that the latter solution is more plausible, two learning rules are suggested according to which the network could alter its initial random connectivities. The first learning rule is a supervised technique in which a teaching signal prespecifies the ideal response expected from the network to each input pattern presented. The error between the actual output and the desired response helps to guide the learning process in the desired direction. When the minimum of the error surface is reached, the network is said to have learned and the weights do not change any more. The teaching signal required for the supervised algorithm could be derived from the visual system. However, no physiological evidence exists that links the auditory and visual maps at the level of the olivary complex which is where early binaural processing occurs. To overcome this problem, an unsupervised learning rule is proposed which requires only the cochlear outputs from the two ears. The rule is a competitive learning strategy wherein only one neuron updates its connectivities for a particular input pattern. The neuron chosen to alter its weights is the one which responds maximally to the input. The inherent delays that exist in the neural system are used as guides to form the organized spatial map responses.
Combined Source-Channel Coding for Bandlimited Waveform Channels
(1989) Vaishampayan, V.A.; Farvardin, N.; ISR
We consider the problem of transmitting data from a continuous- ampltude, discrete-time source over a bandlimited waveform channel using a block-structured digital communication system. Our objective is to design the source encoder-decoder pair, the channel encoder-decoder pair and the modulator-demodulator pair so as to minimize a squared-error distortion measure betweent he source sequence and its replica in the receiver, subject to constrainsts on the transmitted signal power and bandwidth. We formulate the problem i a gneral sense and derive necessary conditions for optimality for the design variables, namely, the encorder map, the decoder map and the modulation signal set. We then consider two systems for which the necessary condition for optimality hold. The receiver of the first system consists of an unquantized soft-decision demodulator followed by a linear estimator-based decoder. We solve the necessary conditions for optimality using an iterative soution technique. We then study the perofrmance of this class of systems as the encoding rate increases, for a fixed bandwidth. Performance comparisons are made against a reference system as well as bounds from information theory. Significant improvements over the reference system are demonstrated and the performance is shown to coincide with an information-theoretic bound in two cases. The receiver of the second system consists of a quantized demodulator followed by an optimum decoder. For a fixed signal set, the optimal encoder and decoder conditions are solved using an iterative solution technique. Performance comparisons are made against the linear estimator-based stystem, the reference ystem and bounds from information theory. We then study the quantized demodulator- based system as the encoding rate becomes large, for a fixed bandwidth. We demonstrate that this system converges to a lienar analog modulation system in some cases to a nonlinear analog modulation system in others. Finally, we study the performance of the two systems to channel mismatch. We demonstrate that both of these systems are more robust to channel mismatch than the reference system.
Real Time Scheduling Problems with Applications to Communication Networks
(1989) Bhattacharya, Partha P.; Ephremides, Anthony; ISR
Queuing systems with time-critical customers can be encountered in packetized voice-communication systems, automated command and control systems and manufacturing systems with time-critical jobs among others. We consider the following model for these systems. Customers arriving at the system have individual deadlines and they must reach their destination by their extinction time or due time (arrival time plus deadline). A penalty is incurred otherwise and this implies either the complete loss of customer or another form of tardiness cost. We are interested in characterizing the strategy (of scheduling the customers bearing the label of their deadlines) which minimizes a cost function that reflects the nature of the penalty incurred. We first consider single queues. Under fairly general statistical assumptions on the arrivals, services and deadlines, we show, via simple probabilisitc arguments, that the policy of serving the customer with closest deadline minimizes either the number of lost customers or a generalized tardiness cost in a strong pathwise sense. The optimality results extend to the more general tree network of nodes under some additional assumptions. We then consdier the problem of priority assignment between two queues of heterogeneous time-critical customers. The customers of the two classes have different service requirements and incur tardiness penalty at different rates. A single server has to be allocated to a customer within a class so as to minimize the average tardiness per customer. We formulate the problem in the framework of Markovian Decision Theory and drive certain structural properties of the optimal policy through a novel use of the value iteration technique. These properties readily lead to some implementable (but possible sub-optimal) policies. The presence of time-constraints makes the analysis of these systems intractable in most cases and this motivates the search for qualitative properties which can provide useful design guidelines. Towards this end, we consider multi-server queues with lost customers which are being operated under the optimal scheduling policies and show that the lost and successful customer processes are stochastically monotone in the system parameters: arrivals, services, deadlines and the number of servers.
Performance Evaluation and Optimization of Parallel Systems with Synchronization
(1989) Gun, Levent; Makowski, A.; ISR
This thesis considers synchronization issues such as resequencing and fork/join in parallel architectures. The discussion is carried out in the context of K parallel single server queues with general servers where jobs are subject to resequencing. Both performance evaluation and optimal routing problems are addressed for such systems. In the first part, Poisson arrivals are assumed to be randomly allocated to different queues according to a Bernoulli switch. The distributions of the various delays in the system are obtained by sample path arguments. The problem of choosing the switching probabilities that minimize the average end-to-end delay is considered. In addition to obtaining exact results in some cases, simple but accurate approximations are provided when the service time distributions are exponential. The simple form of these approximations is then utilized to solve the optimization problem in the case when the service parameters are unknown, and a simple stochastic approximation algorithm is proposed. When the servers are all identical, several useful asymptotic results are obtained as K increases to infinity. Various stochastic monotonicity and convexity results are also provided for this parallel system. In the second part, the dynamic optimization of the same model is investigated under more general assumptions for the arrival process. The resequencing problem is combined with a fork/join problem, where the incoming packets are broken into smaller subpackets for processing at different queues. The problem of finding the optimal allocation policy that minimizes the average discounted and the long-run average costs is formulated as a Markov Decision problem, where the cost-per-stage is taken as the end-to-end delay of each packet. In both cases, the optimal policy is identified as the one that drives the workload in each queue to a balanced configuration as quickly as feasible.
Detection and Classification of Neural Signals and Identification of Neural Networks
(1989) Yang, X.; Shamma, S.; ISR
This thesis aims to develop the theoretical and experimental means to study the nature of the neural networks of the nervous system. The most important parameters in a neural network are its synaptic connectivities (connection weights). Once the unknown connectivities in the nervous system are discovered, appropriate neural network models can be designed and used to mimic their action. To study the functional connectivity, reliable recording and identification of the simultaneous activities of a group of neurons is essential. In the first part of this thesis, a system for neural spike detection and classification is presented, which does not require a priori assumptions about spike shape or timing. The system consists of two subsystems. The learning subsystem, comprising a Haar transform detection scheme, a feature learning phase and a template learning phase, extracts templates for each separable spike class. The real-time detection and classification subsystem identifies spikes in the noisy neural trace and sorts them into classes, according to the templates and the statistics of the background noise. Three fast algorithms are proposed for the real-time sorting subsystem, and comparisons are made among different schemes. Performance of the system is illustrated by using it to classify spike in segments of neural activity recorded extracellularly from monkey motor cortex and from guinea pig and ferret auditory cortices. The system is implemented without human supervision and therefore is suitable for real-time multichannel recording. In the second part, analytical and experimental methods are provided for estimating synaptic connectivities from simultaneous recordings of multiple neurons (after separation). The results are based on detailed, yet flexible neuron models in which spike trains are modeled as general doubly stochastic point processes. The expressions derived can be used with nonstationary or stationary records, and can be readily extended from pairwise to multineuron estimates. Furthermore, we show analytically how the estimates are improved as more neurons are sampled, and derive the appropriate normalizations to eliminate stimulus-related correlations. Finally, we illustrate the use and interpretation of the analytical expressions on simulated spike trains and neural networks, and give explicit confidence measures on the estimates.
Quantization Systems for Hidden Markov Sources
(1989) Goblirsch, David M.; Farvardin, Nariman; ISR
We consider the problem of transmitting data from a continuous- amplitude, discrete-time source over a bandlimited waveform channel using a block-structured digital communication system. Our objective is to design the source encoder-decoder pair, the channel encoder-decoder pair and the modulator-demodulator pair so as to minimize a squared-error distortion measure between the source sequence and its replica in the receiver, subject to constraints on the transmitted signal power and bandwidth. We formulate the problem in a general sense and derive necessary conditions for optimality for the design variables, namely, the encoder map, the decoder map and the modulation signal set. We then consider two systems for which the necessary conditions for optimality hold. The receiver of the first system consists of an unquantized soft-decision demodulator followed by a linear estimator-based decoder. We solve the necessary conditions for optimality using an iterative solution technique. We then study the performance of this class of systems as the encoding rate increases, for a fixed bandwidth. Performance comparisons are made against a reference system as well as bounds from information theory. Significant improvements over the reference system are demonstrated and the performance is shown to coincide with an information-theoretic bound in two cases. The receiver of the second system consists of a quantized demodulator followed by an optimum decoder. For a fixed signal set, the optimal encoder and decoder conditions are solved using an iterative solution technique. Performance comparisons are made against the linear estimator-based system, the reference system and bounds from information theory. We then study the quantized demodulator- based system as the encoding rate becomes large, for a fixed bandwidth. We demonstrate that this system converges to a linear analog modulation system in some cases and to a nonlinear analog modulation system in others. Finally, we study the performance of the two systems to channel mismatch. We demonstrate that both of these systems are more robust to channel mismatch than the reference system.
New Results in Discrete-Time Nonlinear Filtering
(1988) Sowers, R.B.; Makowski, A.; ISR
We consider a discrete-time linear system with correlated Gaussian plant and observation noises and non-Gaussian initial condition independent of the plant and observation noises. We firstly find a solution of the filtering problem; we find a representation for the conditional distribution of the state at time t given the observations up to time t - 1. This representation is in terms of a finite collection of easily- computable statistics. With this solution to the filtering problem, we then find representations for the MMSE and LLSE estimates of the state given the previous observations, and the mean-square error between the two. (Of course the MMSE estimate will in general be a nonlinear function of the observations, whereas the LLSE estimate is by definition linear and is given by the Kalman filtering equations.) We then consider the asymptotic behavior of the mean-square error between the MMSE and LLSE estimates as time tends to infinity. We find conditions on the system dynamics under which the effects of the initial condition die out; under these conditions the non-Gaussian nature of the initial condition becomes unimportant as t becomes large. The practical value of this result is clear - under these conditions, the LLSE estimate, which is usally less costly to generate than the MMSE estimate, is asymptotically as good as the MMSE estimate (i.e., asymptotically optimal) in the mean-square sense.
Deterministic Codes for Arbitrarily Varying Multiple-Access Channels
(1988) Gubner, John A.; Narayan, P.; ISR
The Arbitrarily Varying Multiple-Access Channel (AVMAC) is a model of a multiple-access channel with unknown parameters. In 1981, Jahn characterized the capacity region of the AVMAC, assuming that the region had a nonempty interior; however, he did not address the problem of deciding whether or not the capacity region had a nonempty interior. Using the method of types and an approach completely different from Jahn's, we have partially solved this problem. We begin by introducing the simple but crucial notion of symmetrizability for the two-user AVMAC. We show that if an AVMAC is symmetrizable, then its capacity region has an empty interior. For the two-user AVMAC, this means that at least one (and perhaps both) users cannot reliably transmit information across the channel. More importantly, we show that if the channel is suitably nonsymmetrizable, then the capacity region has a nonempty interior, and both users can reliably transmit information across the channel. In light of these results, it is indeed fortunate that to test a channel for symmetrizability, one simply solves a system of linear equations whose coefficients are the channel transition probabilities. Our proofs rely heavily on a rather complicated decoding rule. This leads us to seek conditions under which simpler multiple-message decoding techniques might suffice. In particular, we give conditions under which the universal maximum mutual information decoding rule will be effective. We then consider the situation in which a constraint is imposed on the sequence of "states" in which the channel can reside. We extend our approach to show that in the presence of a state constraint, the capacity region can increase dramatically. A striking example of this effect occurs with the adder channel. This channel is symmetrizable, and without a state constraint, neither user can reliably transmit information across the channel. However, if a suitable state constraint is imposed, each user can reliably transmit more that 0.4 bits of information per channel use.
A Simple Problem of Flow Control: Optimality and Adaptive Implementations
(1988) Ma, Dye-Jyun; Makowski, A.; ISR
The purpose of flow control is to reduce the congestion experienced in many systems, such as data networks or computer communications systems, by restricting access in order to achieve a desirable performance level. This dissertation considers the optimal flow control problem for a simple discrete-time queue, where the decision-maker seeks to maximize the throughput subject to the constraint that the average holding cost does not exceed a prespecified value. The problem is cast as a constrained Markov decision problem, and by making use of Lagrangian arguments, the optimal policy is shown to be a threshold policy which saturates the constraint. The key step of the analysis lies in establishing the concavity of the value function for the discounted version of the Lagrangian problem. The optimal threshold policy is a function of the model parameters, and is not implementable when some of these parameters are not known exactly. This naturally raises the question of how to design on-line implementable policies so that the same performance as the optimal threshold policy can be achieved. Several implementations of threshold policies are investigated in this study. Implementation is first discussed in terms of an adaptive algorithm of the Stochastic Approximations type, and the analysis relies on the strong consistency of the algorithm and makes use of ideas from the theory of Stochastic Approximations.
Some Problems in Queueing Systems with Resequencing
(1987) Varma, S.; Makoski, A.; ISR
The aim of this thesis is to solve some problems associated with queueing systems with resequencing of customers. Resequencing is associated with the presence of some disordering system which operates on an input arrival stream of customers and delays each customer by a random amount, so that they may leave the system in a different order than the one in which they entered it. However, if the constraint that the customers should leave the system in the same order in which they entered it, is imposed, then a customer may have to undergo an additional delay, which is known as resequencing delay. Such situations typically arise due to packet switching in a computer communication network, in an interconnection network of a multi-processor architecture and concurrency control schemes of distributed data bases among other places. The presence of resequencing makes the analysis of the queueing system intractable in most cases, and very few analytical results are known about these systems. Two general representation results for resequencing systems are the principal tools used in the thesis. The first representation gives the delay in a general resequencing system, in a recursive sample path form. It is used to investigate multistage resequencing systems and also to deduce some interesting structural properties of multiple server resequencing systems. It is shown that hop- by-hop resequencing leads to greater delay compared to end-to-end resequencing in N stage infinite server systems in the sense of strong stochastic ordering. The effect of varying the number of servers on the resequencing delay in a finite server system is investigated for both single stage as well as two stage disordering systems, and also several useful structural properties which can be used to develop bounds for intractable resequencing systems, are identified. The second represenation provides a Markovian state space description for the two server resequencing system with exponential interarrival and service times. The state occupation probabilities are calculated for the M/M/2/B queue with resequencing using this representation. The optimal policy for assigned cutomers to the two servers in the case when they have different service rates, to minimize the total delay (including the resequencing delay), is investigated using dynamic programming arguments. The optimal policy is shown to be of the threshold type in the number of customers in the main queue buffer and independent of the number of customers in the resequencing buffer.

Institute for Systems Research Technical Reports

Browse

Filters

Settings

Sort By

Results per page

Search Results