Zhengkang Zuo, Yue Fang, Qing Huang et al. · 2020
The development of loop invariants for recursive problems of nonlinear data structures is always difficult problem in formal development. The paper studies the derivation and formal proof of binary tree traversal class non-recursive algorithm. The non-recursive Apla (Abstract Programming Language) algorithms of binary tree traversal class problems and their exact and simple loop invariants are derived. Then, the correctness of the algorithm is proved by Dijkstra-Gries standard proving technique. Finally, the PAR platform is used to automatically generate C++ code, which realizes the complete refinement process from abstract specification to concrete executable program. The results of this study point out the direction for the exploration of the loop invariant of the nonrecursive algorithm for recursive problems and have guiding significance for the derivation and formal proof of the algorithm program of the nonlinear data structure.
Cited by 0
Fatima Lounoughi, Mohamed Djendi · 2023
This paper presents a new adaptive decision directed equalizer (DDE) for the receivers of Advanced Wireless communication systems. The proposed approach is based on the use of a recursive non quadratic (RNQ) adaptive algorithm in a DDE system with a training sequence, the new algorithm is denoted DDE-RNQ. The proposed DDE-RNQ equalizer achieves better performances in different situations even when strong noise components are present in the channel. In the proposed DDERNQ, the non quadratic distance criterion between the equalizer output and the decision circuit is used rather than the squared mean square error (MSE) distance for the computation of the branch metrics. Compared to the conventional DDE based normalized least mean square (DDE-NLMS) equalizer, the proposed DDE-RNQ shows superior performances of speed convergence and residual error versus the original DDE-NLMS equalizer in terms of MSE.
Cited by 1
Nematollah Ghahramani, Abolghasem Naghash, Farzad Towhidkhah · Proceedings of the Institution of Mechanical Engineers Part G Journal of Aerospace Engineering · 2008
In this article, a robust non-linear recursive algorithm, featuring a highly reduced computational load, is proposed to estimate the thrust acceleration of a typical flight vehicle. The robustness of this new algorithm allows a significant increase of deviations in initial values of the estimated parameters. In the proposed algorithm, at first, a transformation of the non-linear measurement equation to a linear one, without any approximation, is obtained. Then the recursive least squares algorithm is applied to the transformed equation. The maximum achievable accuracy of the estimation for the non-linear problem is obtained analytically by the Cramer—Rao lower bound and is compared with simulation results. Extensive simulations showed that the new method provides an unbiased as well as a more robust thrust acceleration estimate in comparison with the extended Kalman filter. Moreover, the proposed method is beneficial in that it has a lower number of parameters and results in a simple design with less computational effort.
Cited by 0
Shaoxue Jing, Tianhong Pan, Zhengming Li · International Journal of Automation and Computing · 2017
Cited by 5
Vinu V. Das · 2010
This paper presents a new non-recursive algorithm for reconstructing a binary tree from its traversals. Binary tree traversal refers to the process of visiting each node in a specified order. Given the in order traversal of a binary tree, along with one of its preorder or post order traversals, the original binary tree can be uniquely identified. This algorithm is efficient and requires O(n) time and O(n) space. The implementation of this algorithm was done in C and the complete algorithm was tested. The new algorithm was found to be faster than other non-recursive algorithms.
Cited by 12
Jue Zhang, Zhengwei Sui, Jingnong Weng et al. · 2010
This paper mainly focuses on non-recursive algorithm on the base of the quad-tree for the situation that some data is missing during real-time visualization of massive multiplex dataset. This study introduces different kinds of basic data structures, including wait-static, wait-queue, main-static, missing-static and missing-queue. Upper level of the missing data can be found because of controllability of non-recursive algorithm and coordination between stacks and queues. The result of experiments shows that non-recursive algorithm is more efficient than recursive algorithm in solving the problem of data missing.
Cited by 0
Min Zhang, Zhenchun Li, Hua Zhang et al. · Applied Geophysics · 2010
Cited by 2
Harith H. Thannoon, Ivan A. Hashim · International Journal of Electronics and Telecommunications · 2023
In this paper, Recursive Least Square (RLS) and Affine Projection (AP) adaptive filters are designed using Xilinx System Generator and implemented on the Spartan6 xc6slx16- 2csg324 FPGA platform. FPGA platform utilizes the non-restoring division algorithm and the COordinate Rotation DIgital Computer (CORDIC) division algorithm to perform the division task of the RLS and AP adaptive filters. The Non-restoring division algorithm demonstrates efficient performance in terms of convergence speed and signal-to-noise ratio. In contrast, the CORDIC division algorithm requires 31 cycles for division initialization, whereas the non-restoring algorithm initializes division in just one cycle. To validate the effectiveness of the proposed filters, a set of ten ECG records from the BIT-MIT database is used to test their ability to remove Power Line Interference (PLI) noise from the ECG signal. The proposed adaptive filters are compared with various adaptive algorithms in terms of Signal-to-Noise Ratio (SNR), convergence speed, residual noise, steady-state Mean Square Error (MSE), and complexity.
Cited by 0Open access
A.R. Braga, Walmir M. Caminhas, Carmela Maria Polito Braga · International Journal of Systems Science · 2018
A multiple model recursive least squares algorithm combined with a first-order low-pass filter transformation method, named λ-transform, is proposed for the simultaneous identification of multiple model orders continuous transfer functions from non-uniformly sampled input–output data. The λ-transformation is shown to be equivalent to a canonical transformation between discrete z-domain and δ-domain using the negative value of the λ-transform filter time-constant instead of the sampling interval parameter. The proposed algorithm deals with oversampling, sampling jitter or non-uniform sample intervals without the need for extra digital anti-aliasing pre-filtering, downsampling or interpolation algorithms, producing multiple models with a cost function that facilitates automatic selection of best-fitted models. Besides, measurement noise is noted as beneficial, bringing up an inherent bias toward low-order models. Simulated examples and a drum-boiler level experimental result exhibiting non-minimum phase behaviour illustrate the application of the proposed method.
Cited by 1
Gregory Levitin, Liudong Xing, Suprasad V. Amari · IEEE Transactions on Reliability · 2012
Many practical systems are phased-mission systems (PMS), where the mission consists of multiple, consecutive, and non-overlapping phases of operation. An accurate reliability analysis of a PMS must consider the statistical dependencies of component states across phases, as well as dynamics in system configurations, success criteria, and component behavior. In this paper, we propose a method for exact reliability evaluation of arbitrary binary or multi-state PMS consisting of non-identical binary non-repairable elements. The method is invariant to changes in system structure and demand among missions, and takes into account the time-varying and phase-dependent failure rates and associated cumulative damage effects. The proposed method is based on conditional probabilities, and an efficient recursive formula to compute these probabilities based on branch and bound. The main advantage of this method is that it does not require composition of decision diagrams, and can be fully automated. The method is illustrated using both an analytical example, and a numerical example.
Cited by 43
K. K. Soundra Pandian, Kailash Chandra Ray · International Journal of Computers and Applications · 2016
In this paper, a new algorithm along with its first order hardware architecture is proposed to build the pseudorandom non-recursive binary sequence using sequence folding technique to protect the confidential information and data integrity in cryptography applications. Unlike the existing techniques to build the pseudorandom recursive sequence. The novelty of this proposed algorithm along with first order architecture is to generate non-recursive nibble of thirty one (O) from the input seed of four () bits. In the sequence folding technique, an arbitrary linear recursive binary sequence is folded to a minimum state by an empirical approach to build the non-linear Boolean function and realized using algebraic normal form. In this proposed first order architecture, the constructed non-linear Boolean functions are utilized to engender the pseudorandom binary non-recursive sequence. The proposed first order architecture is implemented using Verilog HDL and further prototyped on commercially available FPGA device ‘Spartan 3E xc3s500e-4fg320’. The realization of proposed architecture in this FPGA device accomplishes an improved data throughput, and efficiency (i.e. throughput/area) is compared to existing techniques. The generated binary sequence from the experiment is further analyzed briefly for sequence size, number of stages, correlation and verified for randomness by using NIST statistical test suites.
Cited by 1
Masato Ikenoue · Transactions of the Institute of Systems Control and Information Engineers · 2025
The recursive form for the standard least squares estimation cannot be applied to recursively compute the weighted least squares estimate if the weight matrix is not diagonal. The instrumental variable estimate obtained by the least squares solution of an over-determined system of equations can be viewed as one of the weighted least squares estimates with a non-diagonal weight matrix. In this paper, a recursive form for the weighted least squares estimation with a non-diagonal weight matrix is considered. A new effective and numerically stable recursive algorithm is proposed using QR factorization and J-orthogonal QR factorization for Isermann et al.'s weighted least squares estimate.
Cited by 1Open access
Bragard, Philippe, Institut National Polytechnique de Grenoble (INPG), 38 (France) · OpenGrey (Institut de l'Information Scientifique et Technique) · 1990
Cited by 0Open access
Shaoxue Jing, Tianhong Pan, Zhengming Li · International Journal of Modelling Identification and Control · 2017
To identify a system with non-uniformly sampled data, a recursive Bayesian algorithm combined dynamic filter with covariance resetting is proposed. First, the input-output data is filtered by the estimated noise transfer function, and the system is decomposed into two fictitious sub-systems with a low dimension. Second, the estimated variance of the noise is employed in the proposed algorithm to improve the estimates. Furthermore, an efficient covariance resetting strategy is integrated into the algorithm to increase the convergence rate. Finally, the proposed algorithm is validated by a numeric example.
Cited by 0
Korean Science Education Society for the Gifted, Juhyeong Lee, Sangsu Jeong · Korean Science Education Society for the Gifted · 2023
The objective of this study is to present an efficient tree traversal algorithm in terms of execution time and implementation complexity. Trees, defined as acyclic connected graphs, are widely used in various fields of computer science. Unlike traditional recursive methods or depth first search implementations, this research proposes an implementation based on breadth first search. The algorithm improves execution time using a non-recursive approach and reduces implementation complexity by using only one-dimensional arrays and loops. Additionally, the algorithm has been optimized through a preprocessing phase. To evaluate the performance of the proposed algorithm compared to existing ones, trees with random structures were generated and their execution times were measured. The results demonstrated that the proposed algorithm exhibits efficient performance.
Cited by 0
Ying‐Chang Liang, Shuxun Wang, Yisong Dai · Journal of Electronics (China) · 1993
Cited by 0
Zhongyu Mo, Chen Ouyang, Hongtruong Pham et al. · Research Square · 2024
<title>Abstract</title> In recent years, extrapolation acceleration technology has been widely employed across various algorithms; however, its application in machine learning has yielded limited achievements. Therefore, building upon the foundation of inertial acceleration technology, we conducted a study and analysis of the small-batch variant of the Stochastic Average Recursive Adaptive Hyperparameter (SARAH) algorithm. By integrating extrapolation acceleration technology into the SARAH framework, we developed an inertial stochastic recursive gradient method tailored for addressing empirical risk minimization problems in scenarios involving non-convex loss functions and machine learning. In this paper, under specific moderate assumptions, we have demonstrated the convergence of the algorithm to the global optimum. Furthermore, we have derived its linear convergence rate with respect to the non-convex objective function. The numerical results obtained from evaluating two widely utilized machine learning problems clearly illustrate the superior performance and practical feasibility of the proposed algorithm. Keywords: extrapolation; Algorithm; non-convex; global optimum; convergence; numerical results.
Cited by 1Open access
Zhongyu Mo, Chen Ouyang, Hongtruong Pham et al. · International Journal of Machine Learning and Cybernetics · 2025
Cited by 6
Zheng Wen Peng, Xin Lu · 2014
The methods to construct the Hilbert-Peano curve are recursive and non-recursive, methods of L-grammar system, different methods have different characteristics. In this document, from the prospective of non-recursive to analyze the characteristics of Hilbert-Peano curve, adopt the amplification curve characteristic matrix iteration algorithm constructs the Hilbert-Peano curve, compares the algorithm with the non-recursive algorithm in time-space-consuming. Prove that this algorithm has more advantages on large scale than L - system of non-recursive algorithm.
Cited by 0
Annapurna H. S, S. Devi · 2024
This study evaluates the performance of the Recursive Non-Quadratic (RNQ) algorithm for adaptive equalization in digital communication systems, comparing it with the Normalized Least Mean Squares (NLMS) algorithm. Using simulations with 16-Phase Shift Keying (16-PSK) and 16-Quadrature Amplitude Modulation (16-QAM) signals, transmitted through a Rayleigh multi-path channel with Additive White Gaussian Noise (AWGN) at various Signal-to-Noise Ratios (SNRs), the RNQ algorithm was found to outperform NLMS. RNQ demonstrated superior symbol recovery accuracy, a more open eye diagram, and lower Mean Square Error (MSE), converging faster to the optimal solution. High roll-off factors and smaller filter sizes further enhanced RNQ's performance. These results affirm the RNQ algorithm's effectiveness in improving communication system performance and suggest future research directions.
Cited by 0