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.

Reduced Rate Ultra Low Delay Audio Coder using Multistage Vector Quantization

Communication applications are usually delay restricted, especially for the instance of musicians playing over the Internet. This requires a one-way delay of maximum 25 msec and also a high audio quality is desired at feasible bit rates. The ultra low delay (ULD) audio coding structure is well suited to this application and we investigate further the application of multistage vector quantization (MSVQ) to reach a bit rate range below 64 Kb/s, in a scalable manner. Results at 32 Kb/s and 64 Kb/s show that the trained codebook MSVQ performs best, better than KLT normalization followed by a simulated Gaussian MSVQ or simulated Gaussian MSVQ alone. The results also show that there is only a weak dependence on the training data, and that we indeed converge to the perceptual quality of our previous ULD coder at 64 Kb/s.

High-rate analysis of channel-optimized vector quantization

High-rate analysis of channel-optimized vector quantizationThis paper considers the high-rate performance of channel optimized source coding for noisy discrete symmetric channels with random index assignment. Specifically, with mean squared error (MSE) as the performance metric, an upper bound on the asymptotic (i.e., high-rate) distortion is derived by assuming a general structure on the codebook. This structure enables extension of the analysis of the channel optimized source quantizer to one with a singular point density: for channels with small errors, the point density that minimizes the upper bound is continuous, while as the error rate increases, the point density becomes singular. The extent of the singularity is also characterized. The accuracy of the expressions obtained are verified through Monte Carlo simulations.

Geometric representations of graphs in low dimension

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $\Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.

Evolving Random Geometric Graph Models for Mobile Wireless Networks

We consider evolving exponential RGGs in one dimension and characterize the time dependent behavior of some of their topological properties. We consider two evolution models and study one of them detail while providing a summary of the results for the other. In the first model, the inter-nodal gaps evolve according to an exponential AR(1) process that makes the stationary distribution of the node locations exponential. For this model we obtain the one-step conditional connectivity probabilities and extend it to the k-step case. Finite and asymptotic analysis are given. We then obtain the k-step connectivity probability conditioned on the network being disconnected. We also derive the pmf of the first passage time for a connected network to become disconnected. We then describe a random birth-death model where at each instant, the node locations evolve according to an AR(1) process. In addition, a random node is allowed to die while giving birth to a node at another location. We derive properties similar to those above.

High-Rate Vector Quantization for Noisy Channels With Applications to Wideband Speech Spectrum Compression

This paper considers the high-rate performance of source coding for noisy discrete symmetric channels with random index assignment (IA). Accurate analytical models are developed to characterize the expected distortion performance of vector quantization (VQ) for a large class of distortion measures. It is shown that when the point density is continuous, the distortion can be approximated as the sum of the source quantization distortion and the channel-error induced distortion. Expressions are also derived for the continuous point density that minimizes the expected distortion. Next, for the case of mean squared error distortion, a more accurate analytical model for the distortion is derived by allowing the point density to have a singular component. The extent of the singularity is also characterized. These results provide analytical models for the expected distortion performance of both conventional VQ as well as for channel-optimized VQ. As a practical example, compression of the linear predictive coding parameters in the wideband speech spectrum is considered, with the log spectral distortion as performance metric. The theory is able to correctly predict the channel error rate that is permissible for operation at a particular level of distortion.

Geometric Decision Tree

In this paper, we present a new algorithm for learning oblique decision trees. Most of the current decision tree algorithms rely on impurity measures to assess the goodness of hyperplanes at each node while learning a decision tree in top-down fashion. These impurity measures do not properly capture the geometric structures in the data. Motivated by this, our algorithm uses a strategy for assessing the hyperplanes in such a way that the geometric structure in the data is taken into account. At each node of the decision tree, we find the clustering hyperplanes for both the classes and use their angle bisectors as the split rule at that node. We show through empirical studies that this idea leads to small decision trees and better performance. We also present some analysis to show that the angle bisectors of clustering hyperplanes that we use as the split rules at each node are solutions of an interesting optimization problem and hence argue that this is a principled method of learning a decision tree.

Percolation and connectivity in AB random geometric graphs

Given two independent Poisson point processes Phi((1)), Phi((2)) in R-d, the AB Poisson Boolean model is the graph with the points of Phi((1)) as vertices and with edges between any pair of points for which the intersection of balls of radius 2r centered at these points contains at least one point of Phi((2)). This is a generalization of the AB percolation model on discrete lattices. We show the existence of percolation for all d >= 2 and derive bounds fora critical intensity. We also provide a characterization for this critical intensity when d = 2. To study the connectivity problem, we consider independent Poisson point processes of intensities n and tau n in the unit cube. The AB random geometric graph is defined as above but with balls of radius r. We derive a weak law result for the largest nearest-neighbor distance and almost-sure asymptotic bounds for the connectivity threshold.

Threshold voltage modeling under size quantization for ultra-thin silicon double-gate metal-oxide-semiconductor field-effect transistor

We report on the threshold voltage modeling of ultra-thin (1 nm-5 nm) silicon body double-gate (DG) MOSFETs using self-consistent Poisson-Schrodinger solver (SCHRED). We define the threshold voltage (V th) of symmetric DG MOSFETs as the gate voltage at which the center potential (Φ c) saturates to Φ c (s a t), and analyze the effects of oxide thickness (t ox) and substrate doping (N A) variations on V th. The validity of this definition is demonstrated by comparing the results with the charge transition (from weak to strong inversion) based model using SCHRED simulations. In addition, it is also shown that the proposed V t h definition, electrically corresponds to a condition where the inversion layer capacitance (C i n v) is equal to the oxide capacitance (C o x) across a wide-range of substrate doping densities. A capacitance based analytical model based on the criteria C i n v C o x is proposed to compute Φ c (s a t), while accounting for band-gap widening. This is validated through comparisons with the Poisson-Schrodinger solution. Further, we show that at the threshold voltage condition, the electron distribution (n(x)) along the depth (x) of the silicon film makes a transition from a strong single peak at the center of the silicon film to the onset of a symmetric double-peak away from the center of the silicon film. © 2012 American Institute of Physics.

Theory and Algorithms for Hop-Count-Based Localization with Random Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function. Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

Nonuniform random geometric graphs with location-dependent radii

We propose a distribution-free approach to the study of random geometric graphs. The distribution of vertices follows a Poisson point process with intensity function n f(center dot), where n is an element of N, and f is a probability density function on R-d. A vertex located at x connects via directed edges to other vertices that are within a cut-off distance r(n)(x). We prove strong law results for (i) the critical cut-off function so that almost surely, the graph does not contain any node with out-degree zero for sufficiently large n and (ii) the maximum and minimum vertex degrees. We also provide a characterization of the cut-off function for which the number of nodes with out-degree zero converges in distribution to a Poisson random variable. We illustrate this result for a class of densities with compact support that have at most polynomial rates of decay to zero. Finally, we state a sufficient condition for an enhanced version of the above graph to be almost surely connected eventually.

Further results on geometric properties of a family of relative entropies

This paper extends some geometric properties of a one-parameter family of relative entropies. These arise as redundancies when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the Kullback-Leibler divergence. They satisfy the Pythagorean property and behave like squared distances. This property, which was known for finite alphabet spaces, is now extended for general measure spaces. Existence of projections onto convex and certain closed sets is also established. Our results may have applications in the Rényi entropy maximization rule of statistical physics.

Analysis of size quantization and temperature effects on the threshold voltage of thin silicon film double-gate metal-oxide-semiconductor field-effect transistor (MOSFET)

In this paper, we analyze the combined effects of size quantization and device temperature variations (T = 50K to 400 K) on the intrinsic carrier concentration (n(i)), electron concentration (n) and thereby on the threshold voltage (V-th) for thin silicon film (t(si) = 1 nm to 10 nm) based fully-depleted Double-Gate Silicon-on-Insulator MOSFETs. The threshold voltage (V-th) is defined as the gate voltage (V-g) at which the potential at the center of the channel (Phi(c)) begins to saturate (Phi(c) = Phi(c(sat))). It is shown that in the strong quantum confinement regime (t(si) <= 3nm), the effects of size quantization far over-ride the effects of temperature variations on the total change in band-gap (Delta E-g(eff)), intrinsic carrier concentration (n(i)), electron concentration (n), Phi(c(sat)) and the threshold voltage (V-th). On the other hand, for t(si) >= 4 nm, it is shown that size quantization effects recede with increasing t(si), while the effects of temperature variations become increasingly significant. Through detailed analysis, a physical model for the threshold voltage is presented both for the undoped and doped cases valid over a wide-range of device temperatures, silicon film thicknesses and substrate doping densities. Both in the undoped and doped cases, it is shown that the threshold voltage strongly depends on the channel charge density and that it is independent of incomplete ionization effects, at lower device temperatures. The results are compared with the published work available in literature, and it is shown that the present approach incorporates quantization and temperature effects over the entire temperature range. We also present an analytical model for V-th as a function of device temperature (T). (C) 2013 AIP Publishing LLC.

Channel quantization for physical layer network-coded two-way relaying

The design of modulation schemes for the physical layer network-coded two way relaying scenario is considered with the protocol which employs two phases: Multiple access (MA) Phase and Broadcast (BC) phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase. In other words, the set of all possible channel realizations (the complex plane) is quantized into a finite number of regions, with a specific network coding map giving the best performance in a particular region. We obtain such a quantization analytically for the case when M-PSK (for M any power of 2) is the signal set used during the MA phase. We show that the complex plane can be classified into two regions: a region in which any network coding map which satisfies the so called exclusive law gives the same best performance and a region in which the choice of the network coding map affects the performance, which is further quantized based on the choice of the network coding map which optimizes the performance. The quantization thus obtained analytically, leads to the same as the one obtained using computer search for 4-PSK signal set by Koike-Akino et al., for the specific value of M = 4.