Tracking analysis of an LMS decision feedback equalizer for a wireless channel

We consider a time varying wireless fading channel, equalized by an LMS Decision Feedback equalizer (DFE). We study how well this equalizer tracks the optimal MMSEDFE (Wiener) equalizer. We model the channel by an Autoregressive (AR) process. Then the LMS equalizer and the AR process are jointly approximated by the solution of a system of ODEs (ordinary differential equations). Using these ODEs, we show via some examples that the LMS equalizer moves close to the instantaneous Wiener filter after initial transience. We also compare the LMS equalizer with the instantaneous optimal DFE (the commonly used Wiener filter) designed assuming perfect previous decisions and computed using perfect channel estimate (we will call it as IDFE). We show that the LMS equalizer outperforms the IDFE almost all the time after initial transience.

On the Production of Anorexic Plan Diagrams

A "plan diagram" is a pictorial enumeration of the execution plan choices of a database query optimizer over the relational selectivity space. We have shown recently that, for industrial-strength database engines, these diagrams are often remarkably complex and dense, with a large number of plans covering the space. However, they can often be reduced to much simpler pictures, featuring significantly fewer plans, without materially affecting the query processing quality. Plan reduction has useful implications for the design and usage of query optimizers, including quantifying redundancy in the plan search space, enhancing useability of parametric query optimization, identifying error-resistant and least-expected-cost plans, and minimizing the overheads of multi-plan approaches. We investigate here the plan reduction issue from theoretical, statistical and empirical perspectives. Our analysis shows that optimal plan reduction, w.r.t. minimizing the number of plans, is an NP-hard problem in general, and remains so even for a storage-constrained variant. We then present a greedy reduction algorithm with tight and optimal performance guarantees, whose complexity scales linearly with the number of plans in the diagram for a given resolution. Next, we devise fast estimators for locating the best tradeoff between the reduction in plan cardinality and the impact on query processing quality. Finally, extensive experimentation with a suite of multi-dimensional TPCH-based query templates on industrial-strength optimizers demonstrates that complex plan diagrams easily reduce to "anorexic" (small absolute number of plans) levels incurring only marginal increases in the estimated query processing costs.

Self Assessment-Based Decision Making for Multiagent Cooperative Search

This paper addresses a search problem with multiple limited capability search agents in a partially connected dynamical networked environment under different information structures. A self assessment-based decision-making scheme for multiple agents is proposed that uses a modified negotiation scheme with low communication overheads. The scheme has attractive features of fast decision-making and scalability to large number of agents without increasing the complexity of the algorithm. Two models of the self assessment schemes are developed to study the effect of increase in information exchange during decision-making. Some analytical results on the maximum number of self assessment cycles, effect of increasing communication range, completeness of the algorithm, lower bound and upper bound on the search time are also obtained. The performance of the various self assessment schemes in terms of total uncertainty reduction in the search region, using different information structures is studied. It is shown that the communication requirement for self assessment scheme is almost half of the negotiation schemes and its performance is close to the optimal solution. Comparisons with different sequential search schemes are also carried out. Note to Practitioners-In the futuristic military and civilian applications such as search and rescue, surveillance, patrol, oil spill, etc., a swarm of UAVs can be deployed to carry out the mission for information collection. These UAVs have limited sensor and communication ranges. In order to enhance the performance of the mission and to complete the mission quickly, cooperation between UAVs is important. Designing cooperative search strategies for multiple UAVs with these constraints is a difficult task. Apart from this, another requirement in the hostile territory is to minimize communication while making decisions. This adds further complexity to the decision-making algorithms. In this paper, a self-assessment-based decision-making scheme, for multiple UAVs performing a search mission, is proposed. The agents make their decisions based on the information acquired through their sensors and by cooperation with neighbors. The complexity of the decision-making scheme is very low. It can arrive at decisions fast with low communication overheads, while accommodating various information structures used for increasing the fidelity of the uncertainty maps. Theoretical results proving completeness of the algorithm and the lower and upper bounds on the search time are also provided.

A unification-based decision procedure for cryptographic protocol analysis

We present a sound and complete decision procedure for the bounded process cryptographic protocol insecurity problem, based on the notion of normal proofs [2] and classical unification. We also show a result about the existence of attacks with “high” normal cuts. Our proof of correctness provides an alternate proof and new insights into the fundamental result of Rusinowitch and Turuani [9] for the same setting.

An Actor-Critic Algorithm for Finite Horizon Markov Decision Processes

We develop a simulation based algorithm for finite horizon Markov decision processes with finite state and finite action space. Illustrative numerical experiments with the proposed algorithm are shown for problems in flow control of communication networks and capacity switching in semiconductor fabrication.

LMS versus Wiener filter for a decision feedback equalizer

In this paper we study an LMS-DFE. We use the ODE framework to show that the LMS-DFE attractors are close to the true DFE Wiener filter (designed considering the decision errors) at high SNR. Therefore, via LMS one can obtain a computationally efficient way to obtain the true DFE Wiener filter under high SNR. We also provide examples to show that the DFE filter so obtained can significantly outperform the usual DFE Wiener filter (designed assuming perfect decisions) at all practical SNRs. In fact, the performance improvement is very significant even at high SNRs (up to 50%), where the popular Wiener filter designed with perfect decisions, is believed to be closer to the optimal one.

Spatial Decision Support System for Assessing Micro, Mini and Small Hydel Potential

This study describes the design and implementation of DSS for assessment of Mini, Micro and Small Schemes. The design links a set of modelling, manipulation, spatial analyses and display tools to a structured database that has the facility to store both observed and simulated data. The main hypothesis is that this tool can be used to form a core of practical methodology that will result in more resilient in less time and can be used by decision-making bodies to assess the impacts of various scenarios (e.g.: changes in land use pattern) and to review, cost and benefits of decisions to be made. It also offers means of entering, accessing and interpreting the information for the purpose of sound decision making. Thus, the overall objective of this DSS is the development of set of tools aimed at transforming data into information and aid decisions at different scales.

Decision support system for regional electricity planning

Electricity appears to be the energy carrier of choice for modern economics since growth in electricity has outpaced growth in the demand for fuels. A decision maker (DM) for accurate and efficient decisions in electricity distribution requires the sector wise and location wise electricity consumption information to predict the requirement of electricity. In this regard, an interactive computer-based Decision Support System (DSS) has been developed to compile, analyse and present the data at disaggregated levels for regional energy planning. This helps in providing the precise information needed to make timely decisions related to transmission and distribution planning leading to increased efficiency and productivity. This paper discusses the design and implementation of a DSS, which facilitates to analyse the consumption of electricity at various hierarchical levels (division, taluk, sub division, feeder) for selected periods. This DSS is validated with the data of transmission and distribution systems of Kolar district in Karnataka State, India.

Analysis of a linear one-dimensional active noise control system by means of block diagrams and transfer functions

In arriving at the ideal filter transfer function for an active noise control system in a duct, the effect of the auxiliary sources (generally loudspeakers) on the waves generated by the primary source has invariably been neglected in the existing literature, implying a rigid wall or infinite impedance. The present paper presents a fairly general analysis of a linear one-dimensional noise control system by means of block diagrams and transfer functions. It takes into account the passive as well as active role of a terminal primary source, wall-mounted auxiliary source, open duct radiation impedance, and the effects of mean flow and damping. It is proved that the pressure generated by a source against a load impedance can be looked upon as a sum of two pressure waves, one generated by the source against an anechoic termination and the other by reflecting the rearward wave (incident on the source) off the passive source impedance. Application of this concept is illustrated for both the types of sources. A concise closed-form expression for the ideal filter transfer function is thus derived and discussed. Finally, the dynamics of an adaptive noise control system is discussed briefly, relating its standing-wave variables and transfer functions with those of the progressive-wave model presented here.

Bounds on Probability of Error in Decision Feedback Equalizers

Evaluation of the probability of error in decision feedback equalizers is difficult due to the presence of a hard limiter in the feedback path. This paper derives the upper and lower bounds on the probability of a single error and multiple error patterns. The bounds are fairly tight. The bounds can also be used to select proper tap gains of the equalizer.

Decision tree design and applications in speech processing

The design and operation of the minimum cost classifier, where the total cost is the sum of the measurement cost and the classification cost, is computationally complex. Noting the difficulties associated with this approach, decision tree design directly from a set of labelled samples is proposed in this paper. The feature space is first partitioned to transform the problem to one of discrete features. The resulting problem is solved by a dynamic programming algorithm over an explicitly ordered state space of all outcomes of all feature subsets. The solution procedure is very general and is applicable to any minimum cost pattern classification problem in which each feature has a finite number of outcomes. These techniques are applied to (i) voiced, unvoiced, and silence classification of speech, and (ii) spoken vowel recognition. The resulting decision trees are operationally very efficient and yield attractive classification accuracies.

Validation of Decision Tables Used in Process Control

Process control rules may be specified using decision tables. Such a specification is superior when logical decisions to be taken in control dominate. In this paper we give a method of detecting redundancies, incompleteness, and contradictions in such specifications. Using such a technique thus ensures the validity of the specifications.