OpenRaiser/Intern-Atlas huggingface dataset:
Low-delay, Low-PAPR, High-rate Non-square Complex Orthogonal Designs
Venue: arXiv cs.IT 2008
Year: 2008

The maximal rate for non-square Complex Orthogonal Designs (CODs) with $n$ transmit antennas is ${1/2}+\frac{1}{n}$ if $n$ is even and ${1/2}+\frac{1}{n+1}$ if $n$ is odd, which are close to 1/2 for large values of $n.$ A class of maximal rate non-square CODs have been constructed by Liang (IEEE Trans. Inform. Theory, 2003) and Lu et. al. (IEEE Trans. Inform. Theory, 2005) have shown that the decoding delay of the codes given by Liang, can be reduced by 50% when number of transmit antennas is a multiple of 4. Adams et. al. (IEEE Trans. Inform. Theory, 2007) have shown that the designs of Liang are of minimal-delay for $n$ equal to 1 and 3 modulo 4 and that of Lu et.al. are of minimal delay when $n$ is a multiple of $4.$ However, these minimal delays are large compared to the delays of the rate 1/2 non-square CODs constructed by Tarokh et al (IEEE Trans. Inform. Theory, 1999) from rate-1 real orthogonal designs (RODs). In this paper, we construct a class of rate-1/2 non-square CODs for any $n$ with the decoding delay equal to 50% of that of the delay of the rate-1/2 codes given by Tarokh et al. This is achieved by giving first a general construction of rate-1 square Real Orthogonal Designs (RODs) which includes as special cases the well known constructions of Adams, Lax and Phillips and Geramita and Pullman, and then making use of it to obtain the desired rate-1/2 non-square COD. For the case of 9 transmit antennas, our rate-1/2 COD is shown to be of minimal-delay. The proposed construction results in designs with zero entries which may have high Peak-to-Average Power Ratio (PAPR) and it is shown that by appropriate postmultiplication, a design with no zero entries can be obtained with no change in the code parameters.
Positive circuits and maximal number of fixed points in discrete dynamical systems
Venue: arXiv cs.DM 2008
Year: 2008

We consider the Cartesian product X of n finite intervals of integers and a map F from X to itself. As main result, we establish an upper bound on the number of fixed points for F which only depends on X and on the topology of the positive circuits of the interaction graph associated with F. The proof uses and strongly generalizes a theorem of Richard and Comet which corresponds to a discrete version of the Thomas' conjecture: if the interaction graph associated with F has no positive circuit, then F has at most one fixed point. The obtained upper bound on the number of fixed points also strongly generalizes the one established by Aracena et al for a particular class of Boolean networks.
An image processing analysis of skin textures
Venue: arXiv cs.CV 2008
Year: 2008

Colour and coarseness of skin are visually different. When image processing is involved in the skin analysis, it is important to quantitatively evaluate such differences using texture features. In this paper, we discuss a texture analysis and measurements based on a statistical approach to the pattern recognition. Grain size and anisotropy are evaluated with proper diagrams. The possibility to determine the presence of pattern defects is also discussed.
Integrating OPC Data into GSN Infrastructures
Venue: arXiv cs.SE 2008
Year: 2008

This paper presents the design and the implementation of an interface software component between OLE for Process Control (OPC) formatted data and the Global Sensor Network (GSN) framework for management of data from sensors. This interface, named wrapper in the GSN context, communicates in Data Access mode with an OPC server and converts the received data to the internal GSN format, according to several temporal modes. This work is realized in the context of a Ph.D. Thesis about the control of distributed information fusion systems. The developed component allows the injection of OPC data, like measurements or industrial processes states information, into a distributed information fusion system deployed in a GSN framework. The component behaves as a client of the OPC server. Developed in Java and based on the Opensaca Utgard, it can be deployed on any computation node supporting a Java virtual machine. The experiments show the component conformity according to the Data Access 2.05a specification of the OPC standard and to the temporal modes.
A 8 bits Pipeline Analog to Digital Converter Design for High Speed Camera Application
Venue: arXiv cs.RO 2008
Year: 2008

- This paper describes a pipeline analog-to-digital converter is implemented for high speed camera. In the pipeline ADC design, prime factor is designing operational amplifier with high gain so ADC have been high speed. The other advantage of pipeline is simple on concept, easy to implement in layout and have flexibility to increase speed. We made design and simulation using Mentor Graphics Software with 0.6 μm CMOS technology with a total power dissipation of 75.47 mW. Circuit techniques used include a precise comparator, operational amplifier and clock management. A switched capacitor is used to sample and multiplying at each stage. Simulation a worst case DNL and INL of 0.75 LSB. The design operates at 5 V dc. The ADC achieves a SNDR of 44.86 dB. keywords: pipeline, switched capacitor, clock management
Design and Implementation a 8 bits Pipeline Analog to Digital Converter in the Technology 0.6 μm CMOS Process
Venue: arXiv cs.RO 2008
Year: 2008

This paper describes a 8 bits, 20 Msamples/s pipeline analog-to-digital converter implemented in 0.6 μm CMOS technology with a total power dissipation of 75.47 mW. Circuit techniques used include a precise comparator, operational amplifier and clock management. A switched capacitor is used to sample and multiplying at each stage. Simulation a worst case DNL and INL of 0.75 LSB. The design operate at 5 V dc. The ADC achieves a SNDR of 44.86 dB. keywords : pipeline, switched capacitor, clock management
Logics for the Relational Syllogistic
Venue: arXiv cs.LO 2008
Year: 2008

The Aristotelian syllogistic cannot account for the validity of many inferences involving relational facts. In this paper, we investigate the prospects for providing a relational syllogistic. We identify several fragments based on (a) whether negation is permitted on all nouns, including those in the subject of a sentence; and (b) whether the subject noun phrase may contain a relative clause. The logics we present are extensions of the classical syllogistic, and we pay special attention to the question of whether reductio ad absurdum is needed. Thus our main goal is to derive results on the existence (or non-existence) of syllogistic proof systems for relational fragments. We also determine the computational complexity of all our fragments.
How could the replica method improve accuracy of performance assessment of channel coding?
Venue: arXiv cs.IT 2008
Year: 2008

We explore the relation between the techniques of statistical mechanics and information theory for assessing the performance of channel coding. We base our study on a framework developed by Gallager in {\em IEEE Trans. Inform. Theory} {\bf 11}, 3 (1965), where the minimum decoding error probability is upper-bounded by an average of a generalized Chernoff's bound over a code ensemble. We show that the resulting bound in the framework can be directly assessed by the replica method, which has been developed in statistical mechanics of disordered systems, whereas in Gallager's original methodology further replacement by another bound utilizing Jensen's inequality is necessary. Our approach associates a seemingly {\em ad hoc} restriction with respect to an adjustable parameter for optimizing the bound with a phase transition between two replica symmetric solutions, and can improve the accuracy of performance assessments of general code ensembles including low density parity check codes, although its mathematical justification is still open.
Communication Through Jamming over a Slotted ALOHA Channel
Venue: arXiv cs.IT 2008
Year: 2008

This work derives bounds on the jamming capacity of a slotted ALOHA system. A system with n legitimate users, each with a Bernoulli arrival process is considered. Packets are temporarily stored at the corresponding user queues, and a slotted ALOHA strategy is used for packet transmissions over the shared channel. The scenario considered is that of a pair of illegitimate users that jam legitimate transmissions in order to communicate over the slotted ALOHA channel. Jamming leads to binary signaling between the illegitimate users, with packet collisions due to legitimate users treated as (multiplicative) noise in this channel. Further, the queueing dynamics at the legitimate users stochastically couples the jamming strategy used by the illegitimate users and the channel evolution. By considering various i.i.d. jamming strategies, achievable jamming rates over the slotted ALOHA channel are derived. Further, an upper bound on the jamming capacity over the class of all ergodic jamming policies is derived. These bounds are shown to be tight in the limit where the offered system load approaches unity.
Reducing Protocol Analysis with XOR to the XOR-free Case in the Horn Theory Based Approach
Venue: arXiv cs.CR 2008
Year: 2008

In the Horn theory based approach for cryptographic protocol analysis, cryptographic protocols and (Dolev-Yao) intruders are modeled by Horn theories and security analysis boils down to solving the derivation problem for Horn theories. This approach and the tools based on this approach, including ProVerif, have been very successful in the automatic analysis of cryptographic protocols w.r.t. an unbounded number of sessions. However, dealing with the algebraic properties of operators such as the exclusive OR (XOR) has been problematic. In particular, ProVerif cannot deal with XOR. In this paper, we show how to reduce the derivation problem for Horn theories with XOR to the XOR-free case. Our reduction works for an expressive class of Horn theories. A large class of intruder capabilities and protocols that employ the XOR operator can be modeled by these theories. Our reduction allows us to carry out protocol analysis by tools, such as ProVerif, that cannot deal with XOR, but are very efficient in the XOR-free case. We implemented our reduction and, in combination with ProVerif, applied it in the automatic analysis of several protocols that use the XOR operator. In one case, we found a new attack.
Cognitive MIMO Radio: A Competitive Optimality Design Based on Subspace Projections
Venue: arXiv cs.IT 2008
Year: 2008

Cognitive MIMO Radio: A Competitive Optimality Design Based on Subspace Projections
A new graph perspective on max-min fairness in Gaussian parallel channels
Venue: arXiv cs.IT 2008
Year: 2008

In this work we are concerned with the problem of achieving max-min fairness in Gaussian parallel channels with respect to a general performance function, including channel capacity or decoding reliability as special cases. As our central results, we characterize the laws which determine the value of the achievable max-min fair performance as a function of channel sharing policy and power allocation (to channels and users). In particular, we show that the max-min fair performance behaves as a specialized version of the Lovasz function, or Delsarte bound, of a certain graph induced by channel sharing combinatorics. We also prove that, in addition to such graph, merely a certain 2-norm distance dependent on the allowable power allocations and used performance functions, is sufficient for the characterization of max-min fair performance up to some candidate interval. Our results show also a specific role played by odd cycles in the graph induced by the channel sharing policy and we present an interesting relation between max-min fairness in parallel channels and optimal throughput in an associated interference channel.
A Class of Maximal-Rate, Low-PAPR, Non-square Complex Orthogonal Designs
Venue: arXiv cs.IT 2008
Year: 2008

Space-time block codes (STBCs) from non-square complex orthogonal designs are bandwidth efficient when compared with those from square real/complex orthogonal designs. Though there exists rate-1 ROD for any number of transmit antennas, rate-1 complex orthogonal designs (COD) does not exist for more than 2 transmit antennas. Liang (IEEE Trans. Inform. Theory, 2003) and Lu et al (IEEE Trans. Inform. Theory, 2005) have constructed a class of maximal rate non-square CODs where the rate is ${1/2}+\frac{1}{n}$ if number of transmit antennas $n$ is even and ${1/2}+\frac{1}{n+1}$ if $n$ is odd. In this paper, we present a simple construction for maximal rate non-square CODs obtained from square CODs which resembles the construction of rate-1 non-square RODs from square RODs. These designs are shown to be amenable for construction of a class of generalized CODs (called Coordinate-Interleaved Scaled CODs) with low peak-to-average power ratio (PAPR) having the same parameters as the maximal rate codes. Simulation results indicate that these codes perform better than the existing maximal rate codes under peak power constraint while performing the same under average power constraint.
Our Brothers' Keepers: Secure Routing with High Performance
Venue: arXiv cs.DC 2008
Year: 2008

The Trinity (Brodsky et al., 2007) spam classification system is based on a distributed hash table that is implemented using a structured peer-to-peer overlay. Such an overlay must be capable of processing hundreds of messages per second, and must be able to route messages to their destination even in the presence of failures and malicious peers that misroute packets or inject fraudulent routing information into the system. Typically there is tension between the requirements to route messages securely and efficiently in the overlay. We describe a secure and efficient routing extension that we developed within the I3 (Stoica et al. 2004) implementation of the Chord (Stoica et al. 2001) overlay. Secure routing is accomplished through several complementary approaches: First, peers in close proximity form overlapping groups that police themselves to identify and mitigate fraudulent routing information. Second, a form of random routing solves the problem of entire packet flows passing through a malicious peer. Third, a message authentication mechanism links each message to it sender, preventing spoofing. Fourth, each peer's identifier links the peer to its network address, and at the same time uniformly distributes the peers in the key-space. Lastly, we present our initial evaluation of the system, comprising a 255 peer overlay running on a local cluster. We describe our methodology and show that the overhead of our secure implementation is quite reasonable.
Transitive-Closure Spanners
Venue: arXiv cs.DS 2008
Year: 2008

Given a directed graph G = (V,E) and an integer k>=1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, E_H) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were implicitly studied in access control, data structures, and property testing, and properties of these spanners have been rediscovered over the span of 20 years. The main goal in each of these applications is to obtain the sparsest k-TC-spanners. We bring these diverse areas under the unifying framework of TC-spanners. We initiate the study of approximability of the size of the sparsest k-TC-spanner for a given directed graph. We completely resolve the approximability of 2-TC-spanners, showing that it is Theta(log n) unless P = NP. For k>2, we present a polynomial-time algorithm that finds a k-TC-spanner with size within O((n log n)^{1-1/k}) of the optimum. Our algorithmic techniques also yield algorithms with the best-known approximation ratio for well-studied problems on directed spanners when k>3: DIRECTED k-SPANNER, CLIENT/SERVER DIRECTED k-SPANNER, and k-DIAMETER SPANNING SUBGRAPH. For constant k>=3, we show that the size of the sparsest k-TC-spanner is hard to approximate with 2^{log^{1-eps} n} ratio unless NP \subseteq DTIME(n^{polylog n}}). Finally, we study the size of the sparsest k-TC-spanners for H-minor-free graph families. Combining our constructions with our insight that 2-TC-spanners can be used for designing property testers, we obtain a monotonicity tester with O(log^2 n /eps) queries for any poset whose transitive reduction is an H-minor free digraph, improving the Theta(sqrt(n) log n/eps)-queries required of the tester due to Fischer et al (2002).
Better Bounds for Frequency Moments in Random-Order Streams
Venue: arXiv cs.DS 2008
Year: 2008

Estimating frequency moments of data streams is a very well studied problem and tight bounds are known on the amount of space that is necessary and sufficient when the stream is adversarially ordered. Recently, motivated by various practical considerations and applications in learning and statistics, there has been growing interest into studying streams that are randomly ordered. In the paper we improve the previous lower bounds on the space required to estimate the frequency moments of a randomly ordered streams.
Fixed-Point Design of Generalized Comb Filters: A Statistical Approach
Venue: arXiv cs.OH 2008
Year: 2008

This paper is concerned with the problem of designing computationally efficient Generalized Comb Filters (GCF). Basically, GCF filters are anti-aliasing filters that guarantee superior performance in terms of selectivity and quantization noise rejection compared to classical comb filters, when used as decimation filters in multistage architectures. Upon employing a partial polyphase (PP) architecture proposed in a companion paper, we develop a sensitivity analysis in order to investigate the effects of the coefficients' quantization on the frequency response of the designed filters. We show that the sensitivity of the filter response to errors in the coefficients is dependent on the particular split of the decimation factor between the two sub-filters constituting the PP architecture. The sensitivity analysis is then used for developing a fixed-point implementation of a sample filter from the class of GCF filters, used as reference filter throughout the paper. Finally, we present computer simulations in order to evaluate the performance of the designed fixed-point filters.
Author-choice open access publishing in the biological and medical literature: a citation analysis
Venue: arXiv cs.DL 2008
Year: 2008

In this article, we analyze the citations to articles published in 11 biological and medical journals from 2003 to 2007 that employ author-choice open access models. Controlling for known explanatory predictors of citations, only 2 of the 11 journals show positive and significant open access effects. Analyzing all journals together, we report a small but significant increase in article citations of 17%. In addition, there is strong evidence to suggest that the open access advantage is declining by about 7% per year, from 32% in 2004 to 11% in 2007.
A Refined Difference Field Theory for Symbolic Summation
Venue: arXiv cs.SC 2008
Year: 2008

In this article we present a refined summation theory based on Karr's difference field approach. The resulting algorithms find sum representations with optimal nested depth. For instance, the algorithms have been applied successively to evaluate Feynman integrals from Perturbative Quantum Field Theory.
Spectrum Sensing Algorithms for Cognitive Radio Based on Statistical Covariances
Venue: arXiv cs.IT 2008
Year: 2008

Spectrum sensing, i.e., detecting the presence of primary users in a licensed spectrum, is a fundamental problem in cognitive radio. Since the statistical covariances of received signal and noise are usually different, they can be used to differentiate the case where the primary user's signal is present from the case where there is only noise. In this paper, spectrum sensing algorithms are proposed based on the sample covariance matrix calculated from a limited number of received signal samples. Two test statistics are then extracted from the sample covariance matrix. A decision on the signal presence is made by comparing the two test statistics. Theoretical analysis for the proposed algorithms is given. Detection probability and associated threshold are found based on statistical theory. The methods do not need any information of the signal, the channel and noise power a priori. Also, no synchronization is needed. Simulations based on narrowband signals, captured digital television (DTV) signals and multiple antenna signals are presented to verify the methods.
GossiCrypt: Wireless Sensor Network Data Confidentiality Against Parasitic Adversaries
Venue: arXiv cs.CR 2008
Year: 2008

Resource and cost constraints remain a challenge for wireless sensor network security. In this paper, we propose a new approach to protect confidentiality against a parasitic adversary, which seeks to exploit sensor networks by obtaining measurements in an unauthorized way. Our low-complexity solution, GossiCrypt, leverages on the large scale of sensor networks to protect confidentiality efficiently and effectively. GossiCrypt protects data by symmetric key encryption at their source nodes and re-encryption at a randomly chosen subset of nodes en route to the sink. Furthermore, it employs key refreshing to mitigate the physical compromise of cryptographic keys. We validate GossiCrypt analytically and with simulations, showing it protects data confidentiality with probability almost one. Moreover, compared with a system that uses public-key data encryption, the energy consumption of GossiCrypt is one to three orders of magnitude lower.
Optimizing Compiler for Engineering Problems
Venue: arXiv cs.PF 2008
Year: 2008

New information technologies provide a lot of prospects for performance improvement. One of them is "Dynamic Source Code Generation and Compilation". This article shows how this way provides high performance for engineering problems.
Queue-length Variations In A Two-Restaurant Problem
Venue: arXiv cs.GT 2008
Year: 2008

This paper attempts to find out numerically the distribution of the queue-length ratio in the context of a model of preferential attachment. Here we consider two restaurants only and a large number of customers (agents) who come to these restaurants. Each day the same number of agents sequentially arrives and decides which restaurant to enter. If all the agents literally follow the crowd then there is no difference between this model and the famous `Pólya's Urn' model. But as agents alter their strategies different kind of dynamics of the model is seen. It is seen from numerical results that the existence of a distribution of the fixed points is quite robust and it is also seen that in some cases the variations in the ratio of the queue-lengths follow a power-law.
Proving Noninterference by a Fully Complete Translation to the Simply Typed lambda-calculus
Venue: arXiv cs.PL 2008
Year: 2008

Tse and Zdancewic have formalized the notion of noninterference for Abadi et al.'s DCC in terms of logical relations and given a proof of noninterference by reduction to parametricity of System F. Unfortunately, their proof contains errors in a key lemma that their translation from DCC to System F preserves the logical relations defined for both calculi. In fact, we have found a counterexample for it. In this article, instead of DCC, we prove noninterference for sealing calculus, a new variant of DCC, by reduction to the basic lemma of a logical relation for the simply typed lambda-calculus, using a fully complete translation to the simply typed lambda-calculus. Full completeness plays an important role in showing preservation of the two logical relations through the translation. Also, we investigate relationship among sealing calculus, DCC, and an extension of DCC by Tse and Zdancewic and show that the first and the last of the three are equivalent.