OpenRaiser/Intern-Atlas huggingface dataset:
On Bounded Weight Codes
Venue: arXiv cs.IT 2010
Year: 2010

The maximum size of a binary code is studied as a function of its length N, minimum distance D, and minimum codeword weight W. This function B(N,D,W) is first characterized in terms of its exponential growth rate in the limit as N tends to infinity for fixed d=D/N and w=W/N. The exponential growth rate of B(N,D,W) is shown to be equal to the exponential growth rate of A(N,D) for w <= 1/2, and equal to the exponential growth rate of A(N,D,W) for 1/2< w <= 1. Second, analytic and numerical upper bounds on B(N,D,W) are derived using the semidefinite programming (SDP) method. These bounds yield a non-asymptotic improvement of the second Johnson bound and are tight for certain values of the parameters.
Optimizing Computation of Recovery Plans for BPEL Applications
Venue: arXiv cs.SE 2010
Year: 2010

Web service applications are distributed processes that are composed of dynamically bounded services. In our previous work [15], we have described a framework for performing runtime monitoring of web service against behavioural correctness properties (described using property patterns and converted into finite state automata). These specify forbidden behavior (safety properties) and desired behavior (bounded liveness properties). Finite execution traces of web services described in BPEL are checked for conformance at runtime. When violations are discovered, our framework automatically proposes and ranks recovery plans which users can then select for execution. Such plans for safety violations essentially involve "going back" - compensating the executed actions until an alternative behaviour of the application is possible. For bounded liveness violations, recovery plans include both "going back" and "re-planning" - guiding the application towards a desired behaviour. Our experience, reported in [16], identified a drawback in this approach: we compute too many plans due to (a) overapproximating the number of program points where an alternative behaviour is possible and (b) generating recovery plans for bounded liveness properties which can potentially violate safety properties. In this paper, we describe improvements to our framework that remedy these problems and describe their effectiveness on a case study.
Fault Tolerant Variable Block Carry Skip Logic (VBCSL) using Parity Preserving Reversible Gates
Venue: arXiv cs.AR 2010
Year: 2010

Reversible logic design has become one of the promising research directions in low power dissipating circuit design in the past few years and has found its application in low power CMOS design, digital signal processing and nanotechnology. This paper presents the efficient design approaches of fault tolerant carry skip adders (FTCSAs) and compares those designs with the existing ones. Variable block carry skip logic (VBCSL) using the fault tolerant full adders (FTFAs) has also been developed. The designs are minimized in terms of hardware complexity, gate count, constant inputs and garbage outputs. Besides of it, technology independent evaluation of the proposed designs clearly demonstrates its superiority with the existing counterparts.
Deriving Specifications of Dependable Systems: toward a Method
Venue: arXiv cs.SE 2010
Year: 2010

This paper proposes a method for deriving formal specifications of systems. To accomplish this task we pass through a non trivial number of steps, concepts and tools where the first one, the most important, is the concept of method itself, since we realized that computer science has a proliferation of languages but very few methods. We also propose the idea of Layered Fault Tolerant Specification (LFTS) to make the method extensible to dependable systems. The principle is layering the specification, for the sake of clarity, in (at least) two different levels, the first one for the normal behavior and the others (if more than one) for the abnormal. The abnormal behavior is described in terms of an Error Injector (EI) which represents a model of the erroneous interference coming from the environment. This structure has been inspired by the notion of idealized fault tolerant component but the combination of LFTS and EI using rely guarantee thinking to describe interference can be considered one of the main contributions of this work. The progress toward this method and the way to layer specifications has been made experimenting on the Transportation and the Automotive Case Studies of the DEPLOY project.
The Lazy Flipper: MAP Inference in Higher-Order Graphical Models by Depth-limited Exhaustive Search
Venue: arXiv cs.DS 2010
Year: 2010

This article presents a new search algorithm for the NP-hard problem of optimizing functions of binary variables that decompose according to a graphical model. It can be applied to models of any order and structure. The main novelty is a technique to constrain the search space based on the topology of the model. When pursued to the full search depth, the algorithm is guaranteed to converge to a global optimum, passing through a series of monotonously improving local optima that are guaranteed to be optimal within a given and increasing Hamming distance. For a search depth of 1, it specializes to Iterated Conditional Modes. Between these extremes, a useful tradeoff between approximation quality and runtime is established. Experiments on models derived from both illustrative and real problems show that approximations found with limited search depth match or improve those obtained by state-of-the-art methods based on message passing and linear programming.
Asymptotic Spectral Efficiency of Multi-antenna Links in Wireless Networks with Limited Tx CSI
Venue: arXiv cs.IT 2010
Year: 2010

An asymptotic technique is presented for finding the spectral efficiency of multi-antenna links in wireless networks where transmitters have Channel-State-Information (CSI) corresponding to their target receiver. Transmitters are assumed to transmit independent data streams on a limited number of channel modes which limits the rank of transmit covariance matrices. This technique is applied to spatially distributed networks to derive an approximation for the asymptotic spectral efficiency in the interference-limited regime as a function of link-length, interferer density, number of antennas per receiver and transmitter, number of transmit streams and path-loss exponent. It is found that targeted-receiver CSI, which can be acquired with low overhead in duplex systems with reciprocity, can increase spectral efficiency several fold, particularly when link lengths are large, node density is high or both. Additionally, the per-link spectral efficiency is found to be a function of the ratio of node density to the number of receiver antennas, and that it can often be improved if nodes transmit using fewer streams. These results are validated for finite-sized systems by Monte-Carlo simulation and are asymptotic in the regime where the number of users and antennas per receiver approach infinity.
Model Checking Classes of Metric LTL Properties of Object-Oriented Real-Time Maude Specifications
Venue: arXiv cs.LO 2010
Year: 2010

This paper presents a transformational approach for model checking two important classes of metric temporal logic (MTL) properties, namely, bounded response and minimum separation, for nonhierarchical object-oriented Real-Time Maude specifications. We prove the correctness of our model checking algorithms, which terminate under reasonable non-Zeno-ness assumptions when the reachable state space is finite. These new model checking features have been integrated into Real-Time Maude, and are used to analyze a network of medical devices and a 4-way traffic intersection system.
Distributed Real-Time Emulation of Formally-Defined Patterns for Safe Medical Device Control
Venue: arXiv cs.LO 2010
Year: 2010

Safety of medical devices and of their interoperation is an unresolved issue causing severe and sometimes deadly accidents for patients with shocking frequency. Formal methods, particularly in support of highly reusable and provably safe patterns which can be instantiated to many device instances can help in this regard. However, this still leaves open the issue of how to pass from their formal specifications in logical time to executable emulations that can interoperate in physical time with other devices and with simulations of patient and/or doctor behaviors. This work presents a specification-based methodology in which virtual emulation environments can be easily developed from formal specifications in Real-Time Maude, and can support interactions with other real devices and with simulation models. This general methodology is explained in detail and is illustrated with two concrete scenarios which are both instances of a common safe formal pattern: one scenario involves the interaction of a provably safe pacemaker with a simulated heart; the other involves the interaction of a safe controller for patient-induced analgesia with a real syringe pump.
CR-MAC: A multichannel MAC protocol for cognitive radio ad hoc networks
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes a cross-layer based cognitive radio multichannel medium access control (MAC) protocol with TDMA, which integrate the spectrum sensing at physical (PHY) layer and the packet scheduling at MAC layer, for the ad hoc wireless networks. The IEEE 802.11 standard allows for the use of multiple channels available at the PHY layer, but its MAC protocol is designed only for a single channel. A single channel MAC protocol does not work well in a multichannel environment, because of the multichannel hidden terminal problem. Our proposed protocol enables secondary users (SUs) to utilize multiple channels by switching channels dynamically, thus increasing network throughput. In our proposed protocol, each SU is equipped with only one spectrum agile transceiver, but solves the multichannel hidden terminal problem using temporal synchronization. The proposed cognitive radio MAC (CR-MAC) protocol allows SUs to identify and use the unused frequency spectrum in a way that constrains the level of interference to the primary users (PUs). Our scheme improves network throughput significantly, especially when the network is highly congested. The simulation results show that our proposed CR-MAC protocol successfully exploits multiple channels and significantly improves network performance by using the licensed spectrum band opportunistically and protects PUs from interference, even in hidden terminal situations.
A hybrid learning algorithm for text classification
Venue: arXiv cs.NE 2010
Year: 2010

Text classification is the process of classifying documents into predefined categories based on their content. Existing supervised learning algorithms to automatically classify text need sufficient documents to learn accurately. This paper presents a new algorithm for text classification that requires fewer documents for training. Instead of using words, word relation i.e association rules from these words is used to derive feature set from preclassified text documents. The concept of Naive Bayes classifier is then used on derived features and finally only a single concept of Genetic Algorithm has been added for final classification. Experimental results show that the classifier build this way is more accurate than the existing text classification systems.
3D-Mesh denoising using an improved vertex based anisotropic diffusion
Venue: arXiv cs.CV 2010
Year: 2010

This paper deals with an improvement of vertex based nonlinear diffusion for mesh denoising. This method directly filters the position of the vertices using Laplace, reduced centered Gaussian and Rayleigh probability density functions as diffusivities. The use of these PDFs improves the performance of a vertex-based diffusion method which are adapted to the underlying mesh structure. We also compare the proposed method to other mesh denoising methods such as Laplacian flow, mean, median, min and the adaptive MMSE filtering. To evaluate these methods of filtering, we use two error metrics. The first is based on the vertices and the second is based on the normals. Experimental results demonstrate the effectiveness of our proposed method in comparison with the existing methods.
Diversity Spectra of Spatial Multipath Fading Processes
Venue: arXiv cs.IT 2010
Year: 2010

We analyse the spatial diversity of a multipath fading process for a finite region or curve in the plane. By means of the Karhunen-Loève (KL) expansion, this diversity can be characterised by the eigenvalue spectrum of the spatial autocorrelation kernel. This justifies to use the term diversity spectrum for it. We show how the diversity spectrum can be calculated for any such geometrical object and any fading statistics represented by the power azimuth spectrum (PAS). We give rigorous estimates for the accuracy of the numerically calculated eigenvalues. The numerically calculated diversity spectra provide useful hints for the optimisation of the geometry of an antenna array. Furthermore, for a channel coded system, they allow to evaluate the time interleaving depth that is necessary to exploit the diversity gain of the code.
Modeling Instantaneous Changes In Natural Scenes
Venue: arXiv cs.CV 2010
Year: 2010

This project aims to create 3d model of the natural world and model changes in it instantaneously. A framework for modeling instantaneous changes natural scenes in real time using Lagrangian Particle Framework and a fluid-particle grid approach is presented. This project is presented in the form of a proof-based system where we show that the design is very much possible but currently we only have selective scripts that accomplish the given job, a complete software however is still under work. This research can be divided into 3 distinct sections: the first one discusses a multi-camera rig that can measure ego-motion accurately up to 88%, how this device becomes the backbone of our framework, and some improvements devised to optimize a know framework for depth maps and 3d structure estimation from a single still image called make3d. The second part discusses the fluid-particle framework to model natural scenes, presents some algorithms that we are using to accomplish this task and we show how an application of our framework can extend make3d to model natural scenes in real time. This part of the research constructs a bridge between computer vision and computer graphics so that now ideas, answers and intuitions that arose in the domain of computer graphics can now be applied to computer vision and natural modeling. The final part of this research improves upon what might become the first general purpose vision system using deep belief architectures and provides another framework to improve the lower bound on training images for boosting by using a variation of Restricted Boltzmann machines (RBM). We also discuss other applications that might arise from our work in these areas.
NCSA: A New Protocol for Random Multiple Access Based on Physical Layer Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

This paper introduces a random multiple access method for satellite communications, named Network Coding-based Slotted Aloha (NCSA). The goal is to improve diversity of data bursts on a slotted-ALOHA-like channel thanks to error correcting codes and Physical-layer Network Coding (PNC). This scheme can be considered as a generalization of the Contention Resolution Diversity Slotted Aloha (CRDSA) where the different replicas of this system are replaced by the different parts of a single word of an error correcting code. The performance of this scheme is first studied through a density evolution approach. Then, simulations confirm the CRDSA results by showing that, for a time frame of $400$ slots, the achievable total throughput is greater than $0.7\times C$, where $C$ is the maximal throughput achieved by a centralized scheme. This paper is a first analysis of the proposed scheme which open several perspectives. The most promising approach is to integrate collided bursts into the decoding process in order to improve the obtained performance.
Towards Quality of Service and Resource Aware Robotic Systems through Model-Driven Software Development
Venue: arXiv cs.RO 2010
Year: 2010

Engineering the software development process in robotics is one of the basic necessities towards industrial-strength service robotic systems. A major challenge is to make the step from code-driven to model-driven systems. This is essential to replace hand-crafted single-unit systems by systems composed out of components with explicitly stated properties. Furthermore, this fosters reuse by separating robotics knowledge from short-cycled implementational technologies. Altogether, this is one but important step towards "able" robots. This paper reports on a model-driven development process for robotic systems. The process consists of a robotics metamodel with first explications of non-functional properties. A model-driven toolchain based on Eclipse provides the model transformation and code generation steps. It also provides design time analysis of resource parameters (e.g. schedulability analysis of realtime tasks) as a first step towards overall resource awareness in the development of integrated robotic systems. The overall approach is underpinned by several real world scenarios.
Performance Analysis of Pulse Shaping Technique for OFDM PAPR Reduction
Venue: arXiv cs.IT 2010
Year: 2010

Orthogonal Frequency Division Multiplexing (OFDM) is an attractive modulation and multiple access techniques for channels with a nonflat frequency response, as it saves the need for complex equalizers. It can offer high quality performance in terms of bandwidth efficiency, robustness against multipath fading and cost-effective implementation. However, its main disadvantage is the high peak-to-average power ratio (PAPR) of the output signal. As a result, a linear behavior of the system over a large dynamic range is needed and therefore the efficiency of the output amplifier is reduced. In this paper, we investigate the effect of some of these sets of time waveforms on the OFDM system performance in terms of Bit Error Rate (BER). We evaluate the system performance in AWGN channels. The obtained results indicate that the reduction in PAPR of the investigated methods is associated with considerable improvement in BER performance of the system, in multipath channels, as compared to conventional OFDM. These promising results indicate that pulse shaping with reduced PAPR is an attractive solution for an OFDM system.
Extracting Symbolic Rules for Medical Diagnosis Problem
Venue: arXiv cs.NE 2010
Year: 2010

Neural networks (NNs) have been successfully applied to solve a variety of application problems involving classification and function approximation. Although backpropagation NNs generally predict better than decision trees do for pattern classification problems, they are often regarded as black boxes, i.e., their predictions cannot be explained as those of decision trees. In many applications, it is desirable to extract knowledge from trained NNs for the users to gain a better understanding of how the networks solve the problems. An algorithm is proposed and implemented to extract symbolic rules for medical diagnosis problem. Empirical study on three benchmarks classification problems, such as breast cancer, diabetes, and lenses demonstrates that the proposed algorithm generates high quality rules from NNs comparable with other methods in terms of number of rules, average number of conditions for a rule, and predictive accuracy.
A System for Smart Home Control of Appliances based on Timer and Speech Interaction
Venue: arXiv cs.HC 2010
Year: 2010

The main objective of this work is to design and construct a microcomputer based system: to control electric appliances such as light, fan, heater, washing machine, motor, TV, etc. The paper discusses two major approaches to control home appliances. The first involves controlling home appliances using timer option. The second approach is to control home appliances using voice command. Moreover, it is also possible to control appliances using Graphical User Interface. The parallel port is used to transfer data from computer to the particular device to be controlled. An interface box is designed to connect the high power loads to the parallel port. This system will play an important role for the elderly and physically disable people to control their home appliances in intuitive and flexible way. We have developed a system, which is able to control eight electric appliances properly in these three modes.
On reverse-engineering the KUKA Robot Language
Venue: arXiv cs.RO 2010
Year: 2010

Most commercial manufacturers of industrial robots require their robots to be programmed in a proprietary language tailored to the domain - a typical domain-specific language (DSL). However, these languages oftentimes suffer from shortcomings such as controller-specific design, limited expressiveness and a lack of extensibility. For that reason, we developed the extensible Robotics API for programming industrial robots on top of a general-purpose language. Although being a very flexible approach to programming industrial robots, a fully-fledged language can be too complex for simple tasks. Additionally, legacy support for code written in the original DSL has to be maintained. For these reasons, we present a lightweight implementation of a typical robotic DSL, the KUKA Robot Language (KRL), on top of our Robotics API. This work deals with the challenges in reverse-engineering the language and mapping its specifics to the Robotics API. We introduce two different approaches of interpreting and executing KRL programs: tree-based and bytecode-based interpretation.
Approximation of DAC Codeword Distribution for Equiprobable Binary Sources along Proper Decoding Paths
Venue: arXiv cs.IT 2010
Year: 2010

Distributed Arithmetic Coding (DAC) is an effective implementation of Slepian-Wolf coding, especially for short data blocks. To research its properties, the concept of DAC codeword distribution along proper and wrong decoding paths has been introduced. For DAC codeword distribution of equiprobable binary sources along proper decoding paths, the problem was formatted as solving a system of functional equations. However, up to now, only one closed form was obtained at rate 0.5, while in general cases, to find the closed form of DAC codeword distribution still remains a very difficult task. This paper proposes three kinds of approximation methods for DAC codeword distribution of equiprobable binary sources along proper decoding paths: numeric approximation, polynomial approximation, and Gaussian approximation. Firstly, as a general approach, a numeric method is iterated to find the approximation to DAC codeword distribution. Secondly, at rates lower than 0.5, DAC codeword distribution can be well approximated by a polynomial. Thirdly, at very low rates, a Gaussian function centered at 0.5 is proved to be a good and simple approximation to DAC codeword distribution. A simple way to estimate the variance of Gaussian function is also proposed. Plenty of simulation results are given to verify theoretical analyses.
Application Delay Modelling for Variable Length Packets in Single Cell IEEE 802.11 WLANs
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we consider the problem of modelling the average delay experienced by an application packets of variable length in a single cell IEEE 802.11 DCF wireless local area network. The packet arrival process at each node i is assumed to be a stationary and independent increment random process with mean ai and second moment a(2) i . The packet lengths at node i are assumed to be i.i.d random variables Pi with finite mean and second moment. A closed form expression has been derived for the same. We assume the input arrival process across queues to be uncorrelated Poison processes. As the nodes share a single channel, they have to contend with one another for a successful transmission. The mean delay for a packet has been approximated by modelling the system as a 1-limited Random Polling system with zero switchover times. Extensive simulations are conducted to verify the analytical results.