Hardware implementation of 4x4 DCT/Quantization block using multiplication and error-free algorithm

The 4ÃÂ4 discrete cosine transform is one of the most important building blocks for the emerging video coding standard, viz. H.264. The conventional implementation does some approximation to the transform matrix elements to facilitate integer arithmetic, for which hardware is suitably prepared. Though the transform coding does not involve any multiplications, quantization process requires sixteen 16-bit multiplications. The algorithm used here eliminates the process of approximation in transform coding and multiplication in the quantization process, by usage of algebraic integer coding. We propose an area-efficient implementation of the transform and quantization blocks based on the algebraic integer coding. The designs were synthesized with 90 nm TSMC CMOS technology and were also implemented on a Xilinx FPGA. The gate counts and throughput achievable in this case are 7000 and 125 Msamples/sec.

STEM+: A Fair and Efficient Algorithm for Scheduling on the DSCH in UMTS Networks

In Universal Mobile Telecommunication Systems (UMTS), the Downlink Shared Channel (DSCH) can be used for providing streaming services. The traffic model for streaming services is different from the commonly used continuously- backlogged model. Each connection specifies a required service rate over an interval of time, k, called the "control horizon". In this paper, our objective is to determine how k DSCH frames should be shared among a set of I connections. We need a scheduler that is efficient and fair and introduce the notion of discrepancy to balance the conflicting requirements of aggregate throughput and fairness. Our motive is to schedule the mobiles in such a way that the schedule minimizes the discrepancy over the k frames. We propose an optimal and computationally efficient algorithm, called STEM+. The proof of the optimality of STEM+, when applied to the UMTS rate sets is the major contribution of this paper. We also show that STEM+ performs better in terms of both fairness and aggregate throughput compared to other scheduling algorithms. Thus, STEM+ achieves both fairness and efficiency and is therefore an appealing algorithm for scheduling streaming connections.

Exploring isospectral spring-mass systems with firefly algorithm

This paper investigates in-line spring-mass systems (An), fixed at one end and free at the other, with n-degrees of freedom (d.f.). The objective is to find feasible in-line systems (B(n)) that are isospectral to a given system. The spring-mass systems, A(n) and B(n), are represented by Jacobi matrices. An error function is developed with the help of the Jacobi matrices A(n) and B(n). The problem of finding the isospectral systems is posed as an optimization problem with the aim of minimizing the error function. The approach for creating isospectral systems uses the fact that the trace of two isospectral Jacobi matrices A(n) and B(n) should be identical. A modification is made to the diagonal elements of the given Jacobi matrix (A(n)), to create the isospectral systems. The optimization problem is solved using the firefly algorithm augmented by a local search procedure. Numerical results are obtained and resulting isospectral systems are shown for 4 d.f. and 10 d.f. systems.

A Randomized Algorithm for Large Scale Support Vector Learning

We propose a randomized algorithm for large scale SVM learning which solves the problem by iterating over random subsets of the data. Crucial to the algorithm for scalability is the size of the subsets chosen. In the context of text classification we show that, by using ideas from random projections, a sample size of O(log n) can be used to obtain a solution which is close to the optimal with a high probability. Experiments done on synthetic and real life data sets demonstrate that the algorithm scales up SVM learners, without loss in accuracy. 1

Structural Alignment based Kernels for Protein Structure Classification

Structural alignments are the most widely used tools for comparing proteins with low sequence similarity. The main contribution of this paper is to derive various kernels on proteins from structural alignments, which do not use sequence information. Central to the kernels is a novel alignment algorithm which matches substructures of fixed size using spectral graph matching techniques. We derive positive semi-definite kernels which capture the notion of similarity between substructures. Using these as base more sophisticated kernels on protein structures are proposed. To empirically evaluate the kernels we used a 40% sequence non-redundant structures from 15 different SCOP superfamilies. The kernels when used with SVMs show competitive performance with CE, a state of the art structure comparison program.

An O(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn).All the algorithms currently known for constructing a Gomory-Hu tree [8,9] use n-1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ(n20/9) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n20/9n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs.We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

A fast algorithm for finding frequent episodes in event streams

Frequent episode discovery is a popular framework for mining data available as a long sequence of events. An episode is essentially a short ordered sequence of event types and the frequency of an episode is some suitable measure of how often the episode occurs in the data sequence. Recently,we proposed a new frequency measure for episodes based on the notion of non-overlapped occurrences of episodes in the event sequence, and showed that, such a definition, in addition to yielding computationally efficient algorithms, has some important theoretical properties in connecting frequent episode discovery with HMM learning. This paper presents some new algorithms for frequent episode discovery under this non-overlapped occurrences-based frequency definition. The algorithms presented here are better (by a factor of N, where N denotes the size of episodes being discovered) in terms of both time and space complexities when compared to existing methods for frequent episode discovery. We show through some simulation experiments, that our algorithms are very efficient. The new algorithms presented here have arguably the least possible orders of spaceand time complexities for the task of frequent episode discovery.

Influences of the springtime northern Indian biomass burning over the central Himalayas

The influences of the springtime northern Indian biomass burning are shown for the first time over the central Himalayas by using three years (2007-2009) of surface and space based observations along with a radiative transfer model. Near-surface ozone, black carbon (BC), spectral aerosol optical depths (AODs) and the meteorological parameters are measured at a high altitude site Nainital (29.37 degrees N, 79.45 degrees E, 1958 m amsl) located in the central Himalayas. The satellite observations include the MODIS derived fire counts and AOD (0.55 mu m), and OMI derived tropospheric column NO(2), ultraviolet aerosol index and single scattering albedo. MODIS fire counts and BC observations are used to identify the fire-impacted periods (372 h during 2007-2009) and hence the induced enhancements in surface BC, AOD (0.5 mu m) and ozone are estimated to be 1802 ng m(-3) (similar to 145%), 0.3 (similar to 150%) and 19 ppbv (similar to 34%) respectively. Large enhancements (53-100%) are also seen in the satellite derived parameters over a 2 degrees x 2 degrees region around Nainital. The present analysis highlights the northern Indian biomass burning induced cooling at the surface (-27 W m(-2)) and top of the atmosphere (-8 W m(-2)) in the lesser polluted high altitude regions of the central Himalayas. This cooling leads to an additional atmospheric warming of 19 W m(-2) and increases the lower atmospheric heating rate by 0.8 K day(-1). These biomass burning induced changes over the central Himalayan atmosphere during spring may also lead to enhanced short-wave absorption above clouds and might have an impact on the monsoonal rainfall.