Studies in crystal engineering: Crystal packing, topological photodimerization and structure-reactivity correlations in fluoro-substituted styrylcoumarins

In continuation of our studies on the influence of fluoro substitution on the solid state photobehaviour and packing pattern of styrylcoumarins, the results obtained for 4-(3-fluorostyryl)coumarin 1, 4-styryl-6-fluorocoumarin 2 and 4-styryl-7-fluorocoumarin 3 are presented. The configuration of the dimers was established on the basis of crystal packing of 1 and 2 (alpha-packed). A rationale for the significantly lower dimer yield in the crystal for 2 is proposed. In the observed centrosymmetric arrangement of the reactants the C=O ...pi (phenyl) contacts seem to provide additional attractive interactions. C-H ... O and C-H ... F hydrogen bonding seems to provide stability in these structures.

Distributed intrusion detection in the presence of correlated sensor readings: Signal-space and communication-complexity view-point

The problem of sensor-network-based distributed intrusion detection in the presence of clutter is considered. It is argued that sensing is best regarded as a local phenomenon in that only sensors in the immediate vicinity of an intruder are triggered. In such a setting, lack of knowledge of intruder location gives rise to correlated sensor readings. A signal-space view-point is introduced in which the noise-free sensor readings associated to intruder and clutter appear as surfaces f(s) and f(g) and the problem reduces to one of determining in distributed fashion, whether the current noisy sensor reading is best classified as intruder or clutter. Two approaches to distributed detection are pursued. In the first, a decision surface separating f(s) and f(g) is identified using Neyman-Pearson criteria. Thereafter, the individual sensor nodes interactively exchange bits to determine whether the sensor readings are on one side or the other of the decision surface. Bounds on the number of bits needed to be exchanged are derived, based on communication-complexity (CC) theory. A lower bound derived for the two-party average case CC of general functions is compared against the performance of a greedy algorithm. Extensions to the multi-party case is straightforward and is briefly discussed. The average case CC of the relevant greaterthan (CT) function is characterized within two bits. Under the second approach, each sensor node broadcasts a single bit arising from appropriate two-level quantization of its own sensor reading, keeping in mind the fusion rule to be subsequently applied at a local fusion center. The optimality of a threshold test as a quantization rule is proved under simplifying assumptions. Finally, results from a QualNet simulation of the algorithms are presented that include intruder tracking using a naive polynomial-regression algorithm. 2010 Elsevier B.V. All rights reserved.

The complexity of certain incremental code generation problems

This paper looks at the complexity of four different incremental problems. The following are the problems considered: (1) Interval partitioning of a flow graph (2) Breadth first search (BFS) of a directed graph (3) Lexicographic depth first search (DFS) of a directed graph (4) Constructing the postorder listing of the nodes of a binary tree. The last problem arises out of the need for incrementally computing the Sethi-Ullman (SU) ordering [1] of the subtrees of a tree after it has undergone changes of a given type. These problems are among those that claimed our attention in the process of our designing algorithmic techniques for incremental code generation. BFS and DFS have certainly numerous other applications, but as far as our work is concerned, incremental code generation is the common thread linking these problems. The study of the complexity of these problems is done from two different perspectives. In [2] is given the theory of incremental relative lower bounds (IRLB). We use this theory to derive the IRLBs of the first three problems. Then we use the notion of a bounded incremental algorithm [4] to prove the unboundedness of the fourth problem with respect to the locally persistent model of computation. Possibly, the lower bound result for lexicographic DFS is the most interesting. In [5] the author considers lexicographic DFS to be a problem for which the incremental version may require the recomputation of the entire solution from scratch. In that sense, our IRLB result provides further evidence for this possibility with the proviso that the incremental DFS algorithms considered be ones that do not require too much of preprocessing.

A New Full-diversity Criterion and Low-complexity STBCs with Partial Interference Cancellation Decoding

Recently, Guo and Xia gave sufficient conditions for an STBC to achieve full diversity when a PIC (Partial Interference Cancellation) or a PIC-SIC (PIC with Successive Interference Cancellation) decoder is used at the receiver. In this paper, we give alternative conditions for an STBC to achieve full diversity with PIC and PIC-SIC decoders, which are equivalent to Guo and Xia's conditions, but are much easier to check. Using these conditions, we construct a new class of full diversity PIC-SIC decodable codes, which contain the Toeplitz codes and a family of codes recently proposed by Zhang, Xu et. al. as proper subclasses. With the help of the new criteria, we also show that a class of PIC-SIC decodable codes recently proposed by Zhang, Shi et. al. can be decoded with much lower complexity than what is reported, without compromising on full diversity.

On the diversity and complexity of Zero Forcing receivers for MIMO Zero Padded systems

Zero padded systems with linear receivers are shown to be robust and amenable to fast implementations in single antenna scenarios. In this paper, properties of such systems are investigated when multiple antennas are present at both ends of the communication link. In particular, their diversity and complexity are evaluated for precoded transmissions. The linear receivers are shown to exploit multipath and receive diversities, even in the absence of any coding at the transmitter. Use of additional redundancy to improve performance is considered and the effect of transmission rate on diversity order is analyzed. Low complexity implementations of Zero Forcing receivers are devised to further enhance their applicability.

X-Codes: A Low Complexity Full-Rate High-Diversity Achieving Precoder for TDD MIMO Systems

We consider a time division duplex multiple-input multiple-output (nt × nr MIMO). Using channel state information (CSI) at the transmitter, singular value decomposition (SVD) of the channel matrix is performed. This transforms the MIMO channel into parallel subchannels, but has a low overall diversity order. Hence, we propose X-Codes which achieve a higher diversity order by pairing the subchannels, prior to SVD preceding. In particular, each pair of information symbols is encoded by a fixed 2 × 2 real rotation matrix. X-Codes can be decoded using nr very low complexity two-dimensional real sphere decoders. Error probability analysis for X-Codes enables us to choose the optimal pairing and the optimal rotation angle for each pair. Finally, we show that our new scheme outperforms other low complexity precoding schemes.

Topological phases, Majorana modes and quench dynamics in a spin ladder system

We explore the salient features of the `Kitaev ladder', a two-legged ladder version of the spin-1/2 Kitaev model on a honeycomb lattice, by mapping it to a one-dimensional fermionic p-wave superconducting system. We examine the connections between spin phases and topologically non-trivial phases of non-interacting fermionic systems, demonstrating the equivalence between the spontaneous breaking of global Z(2) symmetry in spin systems and the existence of isolated Majorana modes. In the Kitaev ladder, we investigate topological properties of the system in different sectors characterized by the presence or absence of a vortex in each plaquette of the ladder. We show that vortex patterns can yield a rich parameter space for tuning into topologically non-trivial phases. We introduce and employ a new topological invariant for explicitly determining the presence of zero energy Majorana modes at the boundaries of such phases. Finally, we discuss dynamic quenching between topologically non-trivial phases in the Kitaev ladder and, in particular, the post-quench dynamics governed by tuning through a quantum critical point.

Simultaneous MultiStreaming for complexity-effective VLIW architectures

Very Long Instruction Word (VLIW) architectures exploit instruction level parallelism (ILP) with the help of the compiler to achieve higher instruction throughput with minimal hardware. However, control and data dependencies between operations limit the available ILP, which not only hinders the scalability of VLIW architectures, but also result in code size expansion. Although speculation and predicated execution mitigate ILP limitations due to control dependencies to a certain extent, they increase hardware cost and exacerbate code size expansion. Simultaneous multistreaming (SMS) can significantly improve operation throughput by allowing interleaved execution of operations from multiple instruction streams. In this paper we study SMS for VLIW architectures and quantify the benefits associated with it using a case study of the MPEG-2 video decoder. We also propose the notion of virtual resources for VLIW architectures, which decouple architectural resources (resources exposed to the compiler) from the microarchitectural resources, to limit code size expansion. Our results for a VLIW architecture demonstrate that: (1) SMS delivers much higher throughput than that achieved by speculation and predicated execution, (2) the increase in performance due to the addition of speculation and predicated execution support over SMS averages around 12%. The minor increase in performance might not warrant the additional hardware complexity involved, and (3) the notion of virtual resources is very effective in reducing no-operations (NOPs) and consequently reduce code size with little or no impact on performance.

A Low-Complexity, Full-Rate, Full-Diversity 2x2 STBC with Golden Code's Coding Gain

This paper presents a low-ML-decoding-complexity, full-rate, full-diversity space-time block code (STBC) for a 2 transmit antenna, 2 receive antenna multiple-input multipleoutput (MIMO) system, with coding gain equal to that of the best and well known Golden code for any QAM constellation.Recently, two codes have been proposed (by Paredes, Gershman and Alkhansari and by Sezginer and Sari), which enjoy a lower decoding complexity relative to the Golden code, but have lesser coding gain. The 2 × 2 STBC presented in this paper has lesser decoding complexity for non-square QAM constellations,compared with that of the Golden code, while having the same decoding complexity for square QAM constellations. Compared with the Paredes-Gershman-Alkhansari and Sezginer-Sari codes, the proposed code has the same decoding complexity for nonrectangular QAM constellations. Simulation results, which compare the codeword error rate (CER) performance, are presented.

Low Complexity Wideband LSFQuantization Using GMM of Uncorrelated Gaussian Mixtures

We develop a Gaussian mixture model (GMM) based vector quantization (VQ) method for coding wideband speech line spectrum frequency (LSF) parameters at low complexity. The PDF of LSF source vector is modeled using the Gaussian mixture (GM) density with higher number of uncorrelated Gaussian mixtures and an optimum scalar quantizer (SQ) is designed for each Gaussian mixture. The reduction of quantization complexity is achieved using the relevant subset of available optimum SQs. For an input vector, the subset of quantizers is chosen using nearest neighbor criteria. The developed method is compared with the recent VQ methods and shown to provide high quality rate-distortion (R/D) performance at lower complexity. In addition, the developed method also provides the advantages of bitrate scalability and rate-independent complexity.

Low complexity Bit allocation algorithms for AAC encoding

We have developed two reduced complexity bit-allocation algorithms for MP3/AAC based audio encoding, which can be useful at low bit-rates. One algorithm derives optimum bit-allocation using constrained optimization of weighted noise-to-mask ratio and the second algorithm uses decoupled iterations for distortion control and rate control, with convergence criteria. MUSHRA based evaluation indicated that the new algorithm would be comparable to AAC but requiring only about 1/10 th the complexity.

Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Spin-polarized STM spectra of Dirac electrons on the surface of a topological insulator

We provide a theory for the tunneling conductance G(V) of Dirac electrons on the surface of a topological insulator as measured by a spin-polarized scanning tunneling microscope tip for low-bias voltages V. We show that if the in-plane rotational symmetry on the surface of the topological insulator is broken by an external field that does not couple to spin directly (such as an in-plane electric field), G(V) exhibits an unconventional dependence on the direction of the magnetization of the tip, i.e., it acquires a dependence on the azimuthal angle of the magnetization of the tip. We also show that G(V) can be used to measure the magnitude of the local out-of-plane spin orientation of the Dirac electrons on the surface. We explain the role of the Dirac electrons in this unconventional behavior and suggest experiments to test our theory.