Respiratory disorder is a highly prevalent condition associated with many adverse health problems. As the current means of diagnosis are obtrusive and ill-suited for real-time m-health applications, we explore a convenient and low-cost automatic approach that uses wearable microelectromechanical system sensor technology. The proposed system introduces the use of motion sensors to detect the changes in the anterior-posterior diameter of the chest wall during breathing function as well as extracting the informative respiratory features to be used for breathing disorders classification. Extensive evaluations are provided on six well-known classifiers with novel feature extraction techniques to distinguish among eight different pathological breathing patterns. The effects of the number of sensors, sensor placement, as well as feature selection on the classification performance are discussed. The experimental results conducted with ten subjects show the best accuracy rates of 97.50% by support vector machine and 97.37% with decision tree bagging (DTB) with all features and after feature selection, correspondingly. Furthermore, a binary classification is proposed for distinguishing between healthy people and patients with breath problems. The different assessments of classification parameters are provided by measuring the accuracy, sensitivity, specificity, F1-score and Mathew correlation coefficient. The accuracy rates above 98% suggest superior performance of DTB in binary recognition supported by the suggested new features.

A reliable long-term monitoring and diagnosis of breath disorders at an early stage provides an improvement of medical act, life expectancy, and quality of life while decreasing the costs of treatment and medical services. Therefore, a real-time unobtrusive monitoring of respiration patterns, as well as breath parameters, is a critical need in medical applications. In this paper, we propose an intelligent system for patient home care, capable of measuring respiration rate and tidal volume variability via a wearable sensing technology. The proposed system is designed particularly for the goal of diagnosis and treatment in patients with pathological breathing, e.g., respiratory complications after surgery or sleep disorders. The complete system was comprised of wearable calibrated accelerometer sensor, Bluetooth low energy, and cloud database. The experiments are conducted with eight subjects and the overall error in respiration rate calculation is obtained 0.29%±0.33% considering SPR-BTA spirometer as the reference. We also introduce a method for tidal volume variability estimation while validated using Pearson correlation. Furthermore, since it is essential to detect the critical events resulted from sudden rise or fall in per breath tidal volume of the patients, we provide a technique to automatically find the accurate threshold values based on each individual breath characteristics. Therefore, the system is able to detect the major changes, precisely by more than 98%, and provide immediate feedback such as sound alarm for round-the-clock respiration monitoring.

Automated methods of real-time and un-obstructive patient's respiration and position monitoring have been subjects of interests in e-health applications. The present study implements a low-cost and convenient monitoring system for patients with breathing problems or sleep disorders. We have also captured the Rib Cage (RC) and Abdomen (AB) movements using accelerometer sensors. In addition to measurement of phase shift between the chest wall compartments, the impacts of different body positions on AB and RC motions have been investigated. The performance of the presented system is evaluated and the average Mean Square Error (MSE) of 0.14 is achieved for three breath timing variables. Moreover, the overall errors of phase angles for paradoxical and synchronous breath patterns are 0.25°±0.06 and 0.26°±6E-03, respectively. The system properly indicates a significant increase in the degree of ribcage and abdomen asynchrony in the paradoxical breathing compared to normal pattern.

Accelerometers are vital parts of many industrial and biomedical applications. Such applications have high demands for accuracy. Multi-sensor fusion is an efficient approach to deliver accurate sensor readouts that are tolerant to multiple faults. This paper proposes an efficient data fusion algorithm, which minimizes Mean-Square-Error (MSE) and keeps the overall precision of the system high. We make use of a convex optimization scheme to tackle the problem. Furthermore, a pre-processing step called screening is used to exclude the potentially faulty sensors from the data fusion. The screening process makes it possible to quickly detect multiple faulty sensors. Our data fusion approach is applicable to any multi-sensor system, for which the post-calibration statistical characteristics of sensors can be measured experimentally. However, the results are presented for accelerometers.

Sensor data fusion is a common approach to provide accurate and fault-tolerant sensor readouts in a multisensor system. This paper proposes an efficient data fusion algorithm using convex optimization for a multi-sensor system with given post-calibration statistical characteristics. A preprocessing step called screening is proposed to quickly detect multiple faulty sensors and exclude them from the fusion. Experimental results are evaluated on temperature sensors.

Fixed-point accuracy analysis and optimization of polynomial data-flow graphs with respect to a reference model is a challenging task in many digital signal processing applications. Range and precision analysis are two important steps of this process to assign suitable integer and fractional bit-widths to the fixed-point variables and constant coefficients in a design such that no overflow occurs and a given error bound on maximum mismatch (MM) or mean-square-error (MSE) and signal-to-quantization-noise ratio (SQNR) is satisfied. This paper explores efficient optimization algorithms based on robust analyses of MM and MSE/SQNR for fixed-point polynomial data-flow graphs. Experimental results illustrate the robustness of our analyses and the efficiency of the optimization algorithms compared to previous work.

Fixed-point accuracy analysis of imprecise datapaths in terms of Maximum-Mismatch (MM) [1], or Mean-Square-Error (MSE) [14], w.r.t. a reference model is a challenging task. Typically, arithmetic circuits are represented with polynomials; however, for a variety of functions, including trigonometric, hyperbolic, logarithm, exponential, square root and division, Coordinate Rotation Digital Computer (CORDIC) units can result in more efficient implementations with better accuracy. This paper presents a novel approach to robustly analyze the fixed-point accuracy of an imprecise datapath, which may consist of a combination of polynomials and CORDIC units. The approach builds a global polynomial for the error of the whole datapath by converting the CORDIC units and their errors into the lowest possible order Taylor series. The previous work for almost accurate analysis of MM [1] and MSE [14, 15] in large datapaths can only handle polynomial computations.

Multi-sensor data fusion is an efficient method to provide both accurate and fault-tolerant sensor readouts. Furthermore, detection of faults in a reasonably short amount of time is crucial for applications dealing with high risks. In order to deliver high accuracies for the sensor measurements, it is required to perform a calibration for each sensor. This paper focuses on designing a fault-tolerant calibrated multisensor system. First, the least squares method is applied to calibrate each sensor using a linear curve fitting function. Next, an analytical technique is proposed to carry out a fault-tolerant multi-sensor data fusion, while minimizing the Mean-Square-Error (MSE) for the final sensor readout. While our data fusion approach is applicable to different multi-sensor systems, the experimental results are shown for 16 temperature sensors, where an environmental thermal chamber was used as the reference model to calibrate the sensors and perform the measurements.

Arithmetic Transform (AT) [1, 16, 17] is an efficient spectral technique, to analyze range and precision of fixed-point polynomial datapaths, among other methods including AA [4, 15] and SMT [5]. However, the major inefficiency of AT is that it cannot handle the datapaths with comparator units, which imply the non-arithmetic if-statements. This paper presents the approach, Constrained Arithmetic Transform (CAT), to perform range and precision analysis of fixed-point datapaths with comparator units. A custom branch-and-bound search is also introduced to provide more cutting branches and perform faster analyses of range and precision, by making use of safe and negligible overestimations. Experimental results prove the efficiency of our approach.

Analyses of range and precision are important for high-level synthesis and verification of fixed-point circuits. Conventional range and precision analysis methods mostly focus on combinational arithmetic circuits and suffer from major inefficiencies when dealing with sequential linear-time-invariant circuits. Such problems mainly include inability to analyze precision when quantization of constant coefficients is taken into account, and lacking efficient word-length optimization algorithms to handle both variables and constants, while satisfying the error metrics. The algorithms presented in this paper solve these problems. Experiments illustrate the efficiency and robustness of our algorithms.

Fixed-point Fast Fourier Transform (FFT) units are widely used in digital communication systems. The twiddle multipliers required for realizing large FFTs are typically implemented with the Coordinate Rotation Digital Computer (CORDIC) algorithm to restrict memory requirements. Recent approaches aiming to optimize the bit-widths of FFT units while satisfying a given maximum bound on Mean-Square-Error (MSE) mostly focus on the architectures with integer multipliers. They ignore the quantization error of coefficients, disabling them to analyze the exact error defined as the difference between the fixed-point circuit and the reference floating-point model. This paper presents an efficient analysis of MSE as well as an optimization algorithm for CORDIC-based FFT units, which is applicable to other Linear-Time-Invariant (LTI) circuits as well.

Range analysis is an important task in obtaining the correct, yet fast and inexpensive arithmetic circuits. The traditional methods, either simulation-based or static, have the disadvantage of low efficiency and coarse bounds, which may lead to unnecessary bits. In this paper, we propose a new method that combines several techniques to perform fixed-point range analysis in a datapath towards obtaining the much tighter ranges efficiently. We show that the range and the bit-width allocation can be obtained with better results relative to the past methods, and in significantly shorter time.

Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.

We present a way of synthesis of reversible circuits using redundant faults information obtained with the aid of its classical counterpart. We use Toffoli-based modules of classical standard gates and technology mapping to relate the effect of redundant stuck-at-value fault in classical irreversible gate level circuits and their reversible implementation. The simplified form of such Toffoli modules is proposed considering any fixed values of input signals (corresponding to stuck-at value effects). We also present redundant gates removal in reversible mapping.

As a new technique for low-power design and quantum computing, reversible logic has been paid much attention. A significant part of research lies in synthesizing a reversible network from non-reversible specification. However, current synthesis algorithms for reversible circuits suffer low efficiency and do not reach area optimization, so they are only applicable to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. Compared to BDD-based and Reed-Muller (RM) based synthesis methods, our algorithm can optimize area and have fast synthesis speed, so it is suitable for large functions.

Allocating bit-widths is a necessary step in high-level synthesis. The main disadvantages of past methods, such as dynamic analysis or affine arithmetic, lie in low efficiency and coarse results which may lead to huge execution time and unnecessary additional bits for representation. In this paper, an algorithm is based on static analysis is proposed to perform range analysis and allocate integer bit-widths for an arithmetic datapath. The efficient algorithm can calculate the error bound between the exact range and the obtained range.

Range and precision analysis are important steps in assigning suitable integer and fractional bit-widths to the fixed-point variables in a design such that no overflow occurs and a given error bound on maximum mismatch and (or) Mean-Square-Error (MSE) is satisfied. Although, range and maximum mismatch analysis of linear arithmetic circuits has been studied before [8], regarding analysis of MSE, the previous works [9,10,12] cannot analyze the error, when it is defined as the difference between the fixed-point circuit and the reference model, e.g., floating-point format. This paper presents an efficient analysis of MSE for linear arithmetic circuits narrowing on Fast Fourier Transform (FFT) units. Furthermore, an optimization algorithm is introduced to set the bit-widths in an FFT unit while satisfying a given maximum bound on MSE. Experimental results prove the robustness of our MSE analysis and the efficiency of the optimization algorithm compared to [12] for an 8K FFT unit.

This paper presents a new technique for scaling the intermediate variables in implementing fixed-point polynomial-based arithmetic circuits. Analysis of precision has been used first to set the input and coefficient bit-widths of the polynomial so that a given error bound is satisfied. Then, we present an efficient approach to scale and truncate different intermediate variables with no need of re-computing precision at each stage. After applying it to all the intermediate variables, a final precision computation and sensitivity analysis is performed to set the final values of truncation bits so that the given error bound remains satisfied. Experimental results on a set of polynomial benchmarks show the robustness and efficiency of the proposed technique.

Arithmetic circuits in general do not match specifications exactly, leading to different implementations within allowed imprecision. We present a technique to search for the least expensive fixed-point implementations for a given error bound. The method is practical in real applications and overcomes traditional precision analysis pessimism, as it allows simultaneous selection of multiple word lengths and even some function approximation, primarily based on Taylor series. Starting from real-valued representation, such as Taylor series, we rely on arithmetic transform to explore maximum imprecision by a branch-and-bound search algorithm to investigate imprecision. We also adopt a new tight-bound interval scheme, and derive a precision optimization algorithm that explores multiple precision parameters to get an implementation with smallest area cost.

We consider synthesis of arithmetic DSP circuits with finite precision fixed-point operations. The aim is to choose the lowest cost implementation that matches a real-valued specification within the allowed imprecision. Starting from Taylor Series or real-valued polynomials, we demonstrate first a method to obtain satisfying implementations that uses intermediate Arithmetic Transform polynomials as an analytical apparatus suitable to precision analysis for both the quantization (bit-width) and approximation sources of imprecision. We then derive the precision optimization algorithm that explores multiple precision parameters in a branch-and-bound search.

This paper considers the synthesis of reversible circuits directly from an irreversible specification, with no need for producing a reversible embedding first. The authors present a feasible methodology for realizing the networks of reversible gates, in a manner that builds on the classical technology mapping. We do not restrict ourselves to the restricted notion of realizing permutation functions, and construct reversible implementations where extraneous signals are efficiently reused for overcoming the inherent fanout limitation

Quantum Fourier transform (QFT) plays a principal role in the development of efficient quantum algorithms. Since the number of quantum bits that can be built is limited, while many quantum technologies are inherently three (or more) valued, we consider extending the reach of the realistic quantum systems by building a QFT over ternary quantum digits. Compared to traditional binary QFT, the q-valued transform improves approximation properties and increases the state space by a factor of (q/2)n. Further, we use nonbinary QFT derivation to generalize and improve the approximation bounds for QFT

We consider self-testing of complete wireless nodes in the field through a low-energy software-based self-test (SBST) method. Energy consumption is optimized both for individual components such as a CPU, embedded memories, and an RF module, as well as at the system level, considering the interplay between module tests. We first derive a scheme for software-based tests with the least amount of cycles and with operands of least Hamming distance and weight. Time interleaving of module tests at the system level further reduces the overall test energy consumption

Quantum computing offers immense speedup in performing tasks such as data encryption and searching. The quantum algorithms can be modeled using classical computing devices, however classical computer simulations cannot deal efficiently with the parallelism present in quantum algorithms. The quantum circuit model for quantum algorithms is sufficient to describe the known quantum algorithms. Using analogies between quantum and digital circuits, we design the emulator of quantum algorithms in FPGAs that allows efficient experimentation with new quantum algorithms. This paper concentrates on new techniques for modeling quantum circuits, including the entanglement and probabilistic computing realization, as well as the critical issues in the required precision of computing.

Wireless sensor networks (WSNs) are being increasingly used in applications where low energy consumption and low cost are the overriding considerations. With increased use, their reliability, availability and serviceability need to be addressed from the outset. Conventional schemes of adding redundant nodes and incorporating reliability in control protocols can effectively improve only the reliability of the overall WSN. The availability and serviceability of WSN nodes can be addressed by providing the remote testing and repair infrastructure for the individual sensor nodes that is well matched with existing on-board test infrastructure, including standard JTAG chains. We propose and evaluate scalable architectures of WSN nodes for increased availability as well as implement the proposed solutions using COTS components.

We investigate methodology for simulation-based verification under a fault model. Since it is currently not feasible to describe a comprehensive explicit model of design errors, we propose an implicit fault model. The model is based on the arithmetic transform (AT) spectral representation of faults. The verification of circuits under the small errors in spectral domain is then performed by the universal test set (UTS) approach to test vector generation. The major result shows that, for errors whose AT has at most t nonzero coefficients, there exist the UTS test vector set of size O(n/sub 2//sup log t/). Consequently, verification confidence can be parameterized by the size of the error t, where at most O(n/sub 2//sup log t/) verification vectors are simulated to verify the absence of faults belonging to such an implicitly defined fault class. The experimental confirmation of the feasibility of verification using such UTS is presented, together with the relations between the arithmetic and Walsh-Hadamard spectra that bound the AT error spectrum and show that a class of small error circuits has small error spectrum. The proposed approach has the advantage of compatibility with formal verification and testing methods.

We address verification of imprecise datapath circuits with sequential elements. Using Arithmetic Transform (AT) and its extensions, we verify the sequential datapath circuits with finite precision. An efficient formulation of the precision verification is presented as a polynomial maximization search over Boolean inputs. Using a branch-and-bound search for the precision error and the block-level composition of ATs, we verify the approximated, rounded and truncated pipelined datapaths.

We address the issue of obtaining compact canonical representations of datapath circuits with sequential elements, for the purpose of equivalence checking. First, we demonstrate the mechanisms for efficient compositional construction of arithmetic transform (AT), which is the underlying function representation, used in modern word-level decision diagrams. Next, we introduce a way of generating the canonical transforms of the sequential datapath circuits. Using these principles, we verify by AT the highly sequential distributed arithmetic architectures.

This paper considers verification of combinational circuits by test vectors under assumption of gate and wire replacement faults. Identifying redundant faults is critical to the quality and speed of such verification schemes. We propose the first known exact redundancy identification of gate replacement faults, together with its efficient approximations. While both solutions use the SAT formulation of redundancy identification, we propose the means to effectively use any single stuck-at-value redundancy identification in the approximate schemes, with varying detection accuracy. Critical to the latter are the novel uses of don't care approximations that detect many redundant faults and quickly identify those that can be detected by methods for stuck-at value faults. A test generation scheme that uses the error-correcting properties of Arithmetic Transforms is incorporated into the overall verification procedure, and is shown to provide high fault coverage for these fault models.

In this paper, we consider verification under error-model assumption. We exploit the algebraic properties of the arithmetic transforms that are used in compact graph-based representations of arithmetic circuits, such as *BMDs. Verification time can be shortened under the assumption of corrupting a bounded number of transform coefficients. Bounds are derived for a number of test vectors, and the vectors successfully verified arithmetic circuits under a class of error models derived from recently proposed basic design error classes, including single stuck-at faults.

In th,is paper, we consider a problem of interpolating a multivariate polynomial from its values at arbitrary t points ouf:r a field F. We derive a deterministic algorithm that finds an interpolating polynomial with at most t terms.Relative to the univariate inteq&otzon, minimal degree selection of terms and wxiqw:ness cannot be gualonteed.Our construction uses the nullspaces of th,e mlrltivnriate genwralized Vanderm.ondematrix associated ,with.the problem to make this mutrk nonsingulw in u series of stepas.Th.e strwtwe of this matrix ullows us to deterministicully find the terms thet increase the rank of this matrix.We pl'esent u pwctical algorithm for finite field interpolations, togeth,er with a set of heuristics for obtairhg fast CL small-de,gree interpolation polynomial.As a special case of interpolation a1gori.th.m. we propose the qlLadratic time algorithm for interpolation over GF(2) field.

A new built-in self-test (BIST) methodology is presented in which all generation and compaction functions are executed by basic building blocks such as adders, ALU's, and multipliers, performing regular arithmetic functions in digital signal processing (DSP) cores. It is demonstrated how these components are themselves tested, and subsequently used to perform more complex testing functions. The need for extra hardware is either entirely eliminated or drastically reduced, test vectors can be easily distributed to different modules of the system, test responses can be collected in parallel, and there is virtually no performance degradation. As an integral part of the proposed BIST environment, arithmetic two-dimensional (2-D) generators of pseudorandom test vectors are also introduced to further integrate the scheme with parallel scan and boundary scan designs used to test peripheral devices of the core.