OpenRaiser/Intern-Atlas huggingface dataset:
Diversity Order Gain with Noisy Feedback in Multiple Access Channels
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we study the effect of feedback channel noise on the diversity-multiplexing tradeoff in multiuser MIMO systems using quantized feedback, where each user has m transmit antennas and the base-station receiver has n antennas. We derive an achievable tradeoff and use it to show that in SNR-symmetric channels, a single bit of imperfect feedback is sufficient to double the maximum diversity order to 2mn compared to when there is no feedback (maximum is mn at multiplexing gain of zero). Further, additional feedback bits do not increase this maximum diversity order beyond 2mn. Finally, the above diversity order gain of mn over non-feedback systems can also be achieved for higher multiplexing gains, albeit requiring more than one bit of feedback.
Communication Requirements for Generating Correlated Random Variables
Venue: arXiv cs.IT 2008
Year: 2008

Two familiar notions of correlation are rediscovered as extreme operating points for simulating a discrete memoryless channel, in which a channel output is generated based only on a description of the channel input. Wyner's "common information" coincides with the minimum description rate needed. However, when common randomness independent of the input is available, the necessary description rate reduces to Shannon's mutual information. This work characterizes the optimal tradeoff between the amount of common randomness used and the required rate of description.
The Tsallis entropy and the Shannon entropy of a universal probability
Venue: arXiv cs.IT 2008
Year: 2008

We study the properties of Tsallis entropy and Shannon entropy from the point of view of algorithmic randomness. In algorithmic information theory, there are two equivalent ways to define the program-size complexity K(s) of a given finite binary string s. In the standard way, K(s) is defined as the length of the shortest input string for the universal self-delimiting Turing machine to output s. In the other way, the so-called universal probability m is introduced first, and then K(s) is defined as -log_2 m(s) without reference to the concept of program-size. In this paper, we investigate the properties of the Shannon entropy, the power sum, and the Tsallis entropy of a universal probability by means of the notion of program-size complexity. We determine the convergence or divergence of each of these three quantities, and evaluate its degree of randomness if it converges.
A Computer Search for N1L-Configurations
Venue: arXiv cs.IT 2008
Year: 2008

In an earlier paper the author defined N1L configurations, and stated a conjecture concerning them which would lead to an improvement by a constant factor to the sphere-packing bound for linear double error correcting codes. Here a computer search is presented, in an effort to gather evidence on the conjecture.
Wireless Secrecy in Cellular Systems with Infrastructure--Aided Cooperation
Venue: arXiv cs.IT 2008
Year: 2008

In cellular systems, confidentiality of uplink transmission with respect to eavesdropping terminals can be ensured by creating intentional inteference via scheduling of concurrent downlink transmissions. In this paper, this basic idea is explored from an information-theoretic standpoint by focusing on a two-cell scenario where the involved base stations are connected via a finite-capacity backbone link. A number of transmission strategies are considered that aim at improving uplink confidentiality under constraints on the downlink rate that acts as an interfering signal. The strategies differ mainly in the way the backbone link is exploited by the cooperating downlink- to the uplink-operated base stations. Achievable rates are derived for both the Gaussian (unfaded) and the fading cases, under different assumptions on the channel state information available at different nodes. Numerical results are also provided to corroborate the analysis. Overall, the analysis reveals that a combination of scheduling and base station cooperation is a promising means to improve transmission confidentiality in cellular systems.
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments
Venue: arXiv cs.LO 2008
Year: 2008

In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If, in contrast, the set of propositional operators is restricted, the complexity may decrease. This paper systematically studies the model-checking problem for LTL formulae over restricted sets of propositional and temporal operators. For almost all combinations of temporal and propositional operators, we determine whether the model-checking problem is tractable (in P) or intractable (NP-hard). We then focus on the tractable cases, showing that they all are NL-complete or even logspace solvable. This leads to a surprising gap in complexity between tractable and intractable cases. It is worth noting that our analysis covers an infinite set of problems, since there are infinitely many sets of propositional operators.
Spread Codes and Spread Decoding in Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we introduce the class of Spread Codes for the use in random network coding. Spread Codes are based on the construction of spreads in finite projective geometry. The major contribution of the paper is an efficient decoding algorithm of spread codes up to half the minimum distance.
Efficient recovering of operation tables of black box groups and rings
Venue: arXiv cs.IT 2008
Year: 2008

People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation * on S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x*y of single pairs (x,y) you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x*y for all x,y in S? This problem can trivially be solved by using |S|^2 queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries. In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that * is an abelian group operation. We also investigate black box rings and give lower and upper bounds for the number of queries needed to solve product recovering in this case.
Analysis of the Deterministic Polynomial Time Solvability of the 0-1-Knapsack Problem
Venue: arXiv cs.CC 2008
Year: 2008

Previously the author has demonstrated that a representative polynomial search partition is required to solve a NP-complete problem in deterministic polynomial time. It has also been demonstrated that finding such a partition can only be done in deterministic polynomial time if the form of the problem provides a simple method for producing the partition. It is the purpose of this article to demonstrate that no deterministic polynomial time method exists to produce a representative polynomial search partition for the Knapsack problem.
On the Capacity of Free-Space Optical Intensity Channels
Venue: arXiv cs.IT 2008
Year: 2008

New upper and lower bounds are presented on the capacity of the free-space optical intensity channel. This channel is characterized by inputs that are nonnegative (representing the transmitted optical intensity) and by outputs that are corrupted by additive white Gaussian noise (because in free space the disturbances arise from many independent sources). Due to battery and safety reasons the inputs are simultaneously constrained in both their average and peak power. For a fixed ratio of the average power to the peak power the difference between the upper and the lower bounds tends to zero as the average power tends to infinity, and the ratio of the upper and lower bounds tends to one as the average power tends to zero. The case where only an average-power constraint is imposed on the input is treated separately. In this case, the difference of the upper and lower bound tends to 0 as the average power tends to infinity, and their ratio tends to a constant as the power tends to zero.
Cascaded Orthogonal Space-Time Block Codes for Wireless Multi-Hop Relay Networks
Venue: arXiv cs.IT 2008
Year: 2008

Distributed space-time block coding is a diversity technique to mitigate the effects of fading in multi-hop wireless networks, where multiple relay stages are used by a source to communicate with its destination. This paper proposes a new distributed space-time block code called the cascaded orthogonal space-time block code (COSTBC) for the case where the source and destination are equipped with multiple antennas and each relay stage has one or more single antenna relays. Each relay stage is assumed to have receive channel state information (CSI) for all the channels from the source to itself, while the destination is assumed to have receive CSI for all the channels. To construct the COSTBC, multiple orthogonal space-time block codes are used in cascade by the source and each relay stage. In the COSTBC, each relay stage separates the constellation symbols of the orthogonal space-time block code sent by the preceding relay stage using its CSI, and then transmits another orthogonal space-time block code to the next relay stage. COSTBCs are shown to achieve the maximum diversity gain in a multi-hop wireless network with flat Rayleigh fading channels. Several explicit constructions of COSTBCs are also provided for two-hop wireless networks with two and four source antennas and relay nodes. It is also shown that COSTBCs require minimum decoding complexity thanks to the connection to orthogonal space-time block codes.
Stochastic Optimization Approaches for Solving Sudoku
Venue: arXiv cs.NE 2008
Year: 2008

In this paper the Sudoku problem is solved using stochastic search techniques and these are: Cultural Genetic Algorithm (CGA), Repulsive Particle Swarm Optimization (RPSO), Quantum Simulated Annealing (QSA) and the Hybrid method that combines Genetic Algorithm with Simulated Annealing (HGASA). The results obtained show that the CGA, QSA and HGASA are able to solve the Sudoku puzzle with CGA finding a solution in 28 seconds, while QSA finding a solution in 65 seconds and HGASA in 1.447 seconds. This is mainly because HGASA combines the parallel searching of GA with the flexibility of SA. The RPSO was found to be unable to solve the puzzle.
Diversity-Integration Trade-offs in MIMO Detection
Venue: arXiv cs.OH 2008
Year: 2008

In this work, a MIMO detection problem is considered. At first, we derive the Generalized Likelihood Ratio Test (GLRT) for arbitrary transmitted signals and arbitrary time-correlation of the disturbance. Then, we investigate design criteria for the transmitted waveforms in both power-unlimited and power-limited systems and we study the interplay among the rank of the optimized code matrix, the number of transmit diversity paths and the amount of energy integrated along each path. The results show that increasing the rank of the code matrix allows generating a larger number of diversity paths at the price of reducing the average signal-to-clutter level along each path.
AGNOSCO - Identification of Infected Nodes with artificial Ant Colonies
Venue: arXiv cs.AI 2008
Year: 2008

If a computer node is infected by a virus, worm or a backdoor, then this is a security risk for the complete network structure where the node is associated. Existing Network Intrusion Detection Systems (NIDS) provide a certain amount of support for the identification of such infected nodes but suffer from the need of plenty of communication and computational power. In this article, we present a novel approach called AGNOSCO to support the identification of infected nodes through the usage of artificial ant colonies. It is shown that AGNOSCO overcomes the communication and computational power problem while identifying infected nodes properly.
Presentation of a Game Semantics for First-Order Propositional Logic
Venue: arXiv cs.LO 2008
Year: 2008

Game semantics aim at describing the interactive behaviour of proofs by interpreting formulas as games on which proofs induce strategies. In this article, we introduce a game semantics for a fragment of first order propositional logic. One of the main difficulties that has to be faced when constructing such semantics is to make them precise by characterizing definable strategies - that is strategies which actually behave like a proof. This characterization is usually done by restricting to the model to strategies satisfying subtle combinatory conditions such as innocence, whose preservation under composition is often difficult to show. Here, we present an original methodology to achieve this task which requires to combine tools from game semantics, rewriting theory and categorical algebra. We introduce a diagrammatic presentation of definable strategies by the means of generators and relations: those strategies can be generated from a finite set of ``atomic'' strategies and that the equality between strategies generated in such a way admits a finite axiomatization. These generators satisfy laws which are a variation of bialgebras laws, thus bridging algebra and denotational semantics in a clean and unexpected way.
Fabrication of Embedded Microvalve on PMMA Microfluidic Devices through Surface Functionalization
Venue: arXiv cs.OH 2008
Year: 2008

The integration of a PDMS membrane within orthogonally placed PMMA microfluidic channels enables the pneumatic actuation of valves within bonded PMMA-PDMS-PMMA multilayer devices. Here, surface functionalization of PMMA substrates via acid catalyzed hydrolysis and air plasma corona treatment were investigated as possible techniques to permanently bond PMMA microfluidic channels to PDMS surfaces. FTIR and water contact angle analysis of functionalized PMMA substrates showed that air plasma corona treatment was most effective in inducing PMMA hydrophilicity. Subsequent fluidic tests showed that air plasma modified and bonded PMMA multilayer devices could withstand fluid pressure at an operational flow rate of 9 mircoliters/min. The pneumatic actuation of the embedded PDMS membrane was observed through optical microscopy and an electrical resistance based technique. PDMS membrane actuation occurred at pneumatic pressures of as low as 10kPa and complete valving occurred at 14kPa for 100 micrometers x 100 micrometers channel cross-sections.
On the determination of Poisson's ratio of stressed monolayer and bilayer submicron thick films
Venue: arXiv cs.OH 2008
Year: 2008

In this paper, the bulge test is used to determine the mechanical properties of very thin dielectric membranes. Commonly, this experimental method permits to determine the residual stress (s0) and biaxial Young's modulus (E/(1-u)). Associating square and rectangular membranes with different length to width ratios, the Poisson's ratio (u) can also be determined. LPCVD Si3N4 monolayer and Si3N4/SiO2 bilayer membranes, with thicknesses down to 100 nm, have been characterized giving results in agreement with literature for Si3N4, E = 212 $\pm$ 14 GPa, s0 = 420 $\pm$ 8 and u = 0.29.
Design And Fabrication of High Numerical Aperture And Low Aberration Bi-Convex Micro Lens Array
Venue: arXiv cs.OH 2008
Year: 2008

Micro lens array is crucial in various kinds of optical and electronic applications. A micro lens array with high numerical aperture (NA) and low aberration is in particular needed. This research is aimed to design and fabricate such a micro lens array with simple structure while keeps the same NA of a same-diameter hemisphere lens. A bi-convex semispherical micro lens array, with corresponding NA 0.379, by PDMS is first designed and analyzed. Experiments are further conducted to fabricate the designed micro lens array by the thermal reflow process. The formed profile is then sputtered with copper to serve as the mold. The front and the rear micro lens array are fabricated by plating PDMS to the mold and then assembled to form the designed micro lens array.
Integrated 3D Sound Intensity Sensor with Four-Wire Particle Velocity Sensors
Venue: arXiv cs.OH 2008
Year: 2008

A new symmetrical four-wire sensor configuration has resulted in a fully integrated sound intensity sensor with significant lower noise floor and smaller size than its predecessors. An integrated sound pressure sensor was further miniaturized by using a folded "back chamber" at both sides of the chip.
High Aspect Pattern Formation by Integration of Micro Inkjetting and Electroless Plating
Venue: arXiv cs.OH 2008
Year: 2008

This paper reports on formation of high aspect micro patterns on low temperature co-fired ceramic (LTCC) substrates by integrating micro inkjetting with electroless plating. Micro inkjetting was realized by using an inkjetting printer that ejects ink droplets from a printhead. This printhead consists of a glass nozzle with a diameter of 50 micrometers and a piezoelectric transducer that is coated on the nozzle. The silver colloidal solution was inkjetted on a sintered CT800 ceramic substrate, followed by curing at 200 degrees C for 60 minutes. As a result, the silver trace with a thickness of 200 nm was obtained. The substrate, with the ejected silver thin film as the seed layer, was then immersed into a preinitiator solution to coat a layer of palladium for enhancing the deposition of nickel. Electroless nickel plating was successfully conducted at a rate of 0.39 micrometers /min, and the thickness of traces was plated up to 84 micrometers. This study demonstrates that the integration of inkjetting with plating is an effective method to form high aspect patterns at the demand location.
Copper Electrodeposition for 3D Integration
Venue: arXiv cs.OH 2008
Year: 2008

Two dimensional (2D) integration has been the traditional approach for IC integration. Due to increasing demands for providing electronic devices with superior performance and functionality in more efficient and compact packages, has driven the semiconductor industry to develop more advanced packaging technologies. Three-dimensional (3D) approaches address both miniaturization and integration required for advanced and portable electronic products. Vertical integration proved to be essential in achieving a greater integration flexibility of disparate technologies, reason for which a general trend of transition from 2D to 3D integration is currently being observed in the industry. 3D chip integration using through silicon via (TSV) copper is considered one of the most advanced technologies among all different types of 3D packaging technologies. Copper electrodeposition is one of technologies that enable the formation of TSV structures. Because of its well-known application for copper damascene, it was believed that its transfer to filling TSV vias would be easily adopted. However, as any new technology at its beginning, there are several challenges that need to be addressed and resolved before becoming a fully mature technology. This paper will address the TSV fill processes using copper electrodeposition, the advantages as well as difficulties associated with this technology and approaches taken to overcome them. Electrochemical characterization of the organics behavior and their effect on via filling will be presented. The effect of wafer design on process performance and throughput, including necessary process optimizations that are required for achieving void-free via filling while reducing the processing time, will be discussed.
Fabrication of 3D Packaging TSV using DRIE
Venue: arXiv cs.OH 2008
Year: 2008

Emerging 3D chips stacking and MEMS/Sensors packaging technologies are using DRIE (Deep Reactive Ion Etching) to etch through-silicon via (TSV) for advanced interconnections. The interconnection step can be done prior to or post CMOS manufacturing, each requiring different etch process performances. A review of the DRIE capability in terms of etching profile, etch rate, etch depth has been carried out. Excellent tool flexibility allows a wide range of basic and complex profiles to be achieved. Unlike other techniques, DRIE has the capability to etch feature sizes ranging from sub-micron to millimeter width. The main specificity of the DRIE is that etch rate is sensitive to the total exposed area and the aspect ratio. For the TSV applications, where the total exposed area is lower than 10%, high etch rates are achievable. A study has also been done to highlight the importance of via profile for the success of the refilling step. In addition, due to the high flexibility of DRIE, we also explore the capability of using this technique for wafer thinning and plasma die separation.
Low Voltage Totally Free Flexible RF MEMS Switch With Anti-Stiction System
Venue: arXiv cs.OH 2008
Year: 2008

This paper concerns a new design of RF MEMS switch combined with an innovative process which enable low actuation voltage (<5V) and avoid stiction. First, the structure described with principal design issues, the corresponding anti-stiction system is presented and FEM simulations are done. Then, a short description of the process flow based on two non polymer sacrificial layers. Finally, RF measurements are presented and preliminary experimental protocol and results of anti-stiction validation is detailed. Resulting RF performances are -30dB of isolation and -0.45dB of insertion loss at 10 GHz.
A New Four States High Deflection Low Actuation Voltage Electrostatic Mems Switch for RF Applications
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents a new electrostatic MEMS (MicroElectroMechanical System) based on a single high reliability totally free flexible membrane. Using four electrodes, this structure enables four states which allowed large deflections (4$μ$m) with low actuation voltage (7,5V). This design presents also a good contact force and improve the restoring force of the structure. As an example of application, a Single Pole Double Throw (SPDT) for 24GHz applications, based on this design, has been simulated.
Design and Fabrication of a Novel Micro Electromagnetic Actuator
Venue: arXiv cs.OH 2008
Year: 2008

The present study presents a new micro electromagnetic actuator utilizing a PDMS membrane with a magnet. The actuator is integrated with micro coils to electromagnetically actuate the membrane and results in a large deflection. The micro electromagnetic actuator proposed in this study is easily fabricated and is readily integrated with existing bio-medical chips due to its planar structure.
Network Coding for Speedup in Switches
Venue: arXiv cs.NI 2008
Year: 2008

We present a graph theoretic upper bound on speedup needed to achieve 100% throughput in a multicast switch using network coding. By bounding speedup, we show the equivalence between network coding and speedup in multicast switches - i.e. network coding, which is usually implemented using software, can in many cases substitute speedup, which is often achieved by adding extra switch fabrics. This bound is based on an approach to network coding problems called the "enhanced conflict graph". We show that the "imperfection ratio" of the enhanced conflict graph gives an upper bound on speedup. In particular, we apply this result to K-by-N switches with traffic patterns consisting of unicasts and broadcasts only to obtain an upper bound of min{(2K-1)/K, 2N/(N+1)}.