Search

An approach to approximate the 2D Gaussian filter for all possible kernel sizes based on the binary optimization technique is introduced. The approximate filter coefficients are designed as negative powers of two, allowing hardware implementation with remarkable savings in the chip area. The proposed approximate filters were evaluated and compared with competing methods using both similarity analysis and edge detection applications. The proposed method and the competing works for masks of size 3 × 3 , 5 × 5 , and 7 × 7 were implemented in a Xilinx Artix-7 FPGA. The proposed method showed up to a 60.0% reduction in DSP usage and a 75.0% increase in the maximum operating frequency when compared with state-of-art methods for the 7 × 7 kernel size case and a 48.8% reduction in the dynamic power normalized by the maximum operating frequency. [ABSTRACT FROM AUTHOR]

An approach to approximate the 2D Gaussian filter for all possible kernel sizes based on the binary optimization technique is introduced. The approximate filter coefficients are designed as negative powers of two, allowing hardware implementation with remarkable savings in the chip area. The proposed approximate filters were evaluated and compared with competing methods using both similarity analysis and edge detection applications. The proposed method and the competing works for masks of size 3×3, 5×5, and 7×7 were implemented in a Xilinx Artix-7 FPGA. The proposed method showed up to a 60.0% reduction in DSP usage and a 75.0% increase in the maximum operating frequency when compared with state-of-art methods for the 7×7 kernel size case and a 48.8% reduction in the dynamic power normalized by the maximum operating frequency.

The fractional Fourier transform (FrFT) is a useful mathematical tool for signal and image processing. In some applications, the eigendecomposition-based discrete FrFT (DFrFT) is suitable due to its properties of orthogonality, additivity, reversibility and approximation of continuous FrFT. Although recent studies have introduced reduced arithmetic complexity algorithms for DFrFT computation, which are attractive for real-time and low-power consumption practical scenarios, reliable hardware architectures in this context are gaps in the literature. In this paper, we present two hardware architectures based on the referred algorithms to obtain N-point DFrFT ( N = 4 L , L is a positive integer). We validate and compare the performance of such architectures by employing field-programmable gate array implementations, co-designed with an embedded hard processor unit. In particular, we carry out computer experiments where synthesis, error and latency analyses are performed, and consider an application related to compact signal representation. [ABSTRACT FROM AUTHOR]

Öz The purpose of this study was to investigate what factors third-grade students took into consideration when posing problems for their peers and how these factors affected the mathematical complexities of the problems. Free and semi-structured problem-posing tasks were given to 27 third-grade students, and the problems they created for their peers were analyzed in terms of their semantic structure and arithmetic complexity. According to the findings of the study, there was a statistically significant difference between the semantic structures of the problems in both tasks created for the more mathematically proficient student, but there was no difference between their arithmetic complexities. In addition, according to the qualitative findings of the study, the magnitude of the numbers, the operation types, the number of operations used, and the interests of the students were taken into consideration in posing problems for students with low and high levels of mathematical ability.

The objective of this paper was to present a new inverse problem statement and numerical method for the Volterra integral equations with piecewise continuous kernels. For such Volterra integral equations of the first kind, it is assumed that kernel discontinuity curves are the desired ones, but the rest of the information is known. The resulting integral equation is nonlinear with respect to discontinuity curves which correspond to integration bounds. A direct method of discretization with a posteriori verification of calculations is proposed. The family of quadrature rules is employed for approximation purposes. It is shown that the arithmetic complexity of the proposed numerical method is O (N 3) . The method has first-order convergence. A generalization of the method is also proposed for the case of an arbitrary number of discontinuity curves. The illustrative examples are included to demonstrate the efficiency and accuracy of proposed solver. [ABSTRACT FROM AUTHOR]

We study the possibility of computing cryptographic primitives in a fully black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits that make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions. We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under coding-related intractability assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, additively homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions. [ABSTRACT FROM AUTHOR]

This paper explores the influence of product type and arithmetic task complexity on users’ perceived mental effort and satisfaction in the context of online grocery shopping. A two-factor within-subject experiment was conducted with 32 participants. Results show that experience products and complex arithmetic tasks are associated with higher perceived mental effort compared to search products and simple arithmetic tasks. Perceived mental effort and satisfaction are negatively related. The more cognitive effort users need to invest in their online shopping tasks, the less satisfied they are likely to be with their online experience. Our results suggest that cognitive absorption mediates the relationship between cognitive effort and satisfaction. The study contributes to our understanding of online grocery shopping by explaining the effect of arithmetic complexity and product type on user satisfaction. It also offers shopping website designers a way to improve consumers’ online grocery shopping experience by implementing simple technology features in their websites to help users reduce their mental effort.

The additional discrete transforms from cosine (DCT) and sine (DST) families that come with the Adaptive Multiple Transform (AMT) approach is one of the major enhancements involved in the new Versatile Video Coding (VVC) standard. They have increasingly brought additional complexity compared to HEVC standard. The transform module is one of the most consuming stages in terms of time and hardware resources. This paper focuses on the optimization of the DST-VII transform. It deals with a multicriteria optimization algorithm for approximate computing that aims at the identification of the optimal approximation of the DST-VII according to several approximation measures. The resulting transform matrix has extremely low arithmetic complexity as well as close proximity to the exact DST-VII. Moreover, hardware synthesis results denote that the simplified design of DST-VII consumes only a third of the hardware resources used by the original algorithm. Experimental results obtained from joint exploration model simulations show a slight bit-rate increase while maintaining almost the same video quality. Such results confirm the effectiveness of the proposed approximate transform. The latter yields good performance in terms of computational complexity reduction and proximity to the exact transform while exhibiting a video coding performance comparable to the original algorithm. [ABSTRACT FROM AUTHOR]

The objective of this paper was to present a new inverse problem statement and numerical method for the Volterra integral equations with piecewise continuous kernels. For such Volterra integral equations of the first kind, it is assumed that kernel discontinuity curves are the desired ones, but the rest of the information is known. The resulting integral equation is nonlinear with respect to discontinuity curves which correspond to integration bounds. A direct method of discretization with a posteriori verification of calculations is proposed. The family of quadrature rules is employed for approximation purposes. It is shown that the arithmetic complexity of the proposed numerical method is O(N3). The method has first-order convergence. A generalization of the method is also proposed for the case of an arbitrary number of discontinuity curves. The illustrative examples are included to demonstrate the efficiency and accuracy of proposed solver.

This paper explores the influence of product type and arithmetic task complexity on users' perceived mental effort and satisfaction in the context of online grocery shopping. A two-factor within-subject experiment was conducted with 32 participants. Results show that experience products and complex arithmetic tasks are associated with higher perceived mental effort compared to search products and simple arithmetic tasks. Perceived mental effort and satisfaction are negatively related. The more cognitive effort users need to invest in their online shopping tasks, the less satisfied they are likely to be with their online experience. Our results suggest that cognitive absorption mediates the relationship between cognitive effort and satisfaction. The study contributes to our understanding of online grocery shopping by explaining the effect of arithmetic complexity and product type on user satisfaction. It also offers shopping website designers a way to improve consumers' online grocery shopping experience by implementing simple technology features in their websites to help users reduce their mental effort. [ABSTRACT FROM AUTHOR]

Abstract Background Arithmetic processing in adults is known to rely on a frontal-parietal network. However, neurocognitive research focusing on the neural and behavioral correlates of arithmetic development has been scarce, even though the acquisition of arithmetic skills is accompanied by changes within the fronto-parietal network of the developing brain. Furthermore, experimental procedures are typically adjusted to constraints of functional magnetic resonance imaging, which may not reflect natural settings in which children and adolescents actually perform arithmetic. Therefore, we investigated the longitudinal neurocognitive development of processes involved in performing the four basic arithmetic operations in 19 adolescents. By using functional near-infrared spectroscopy, we were able to use an ecologically valid task, i.e., a written production paradigm. Results A common pattern of activation in the bilateral fronto-parietal network for arithmetic processing was found for all basic arithmetic operations. Moreover, evidence was obtained for decreasing activation during subtraction over the course of 1 year in middle and inferior frontal gyri, and increased activation during addition and multiplication in angular and middle temporal gyri. In the self-paced block design, parietal activation in multiplication and left angular and temporal activation in addition were observed to be higher for simple than for complex blocks, reflecting an inverse effect of arithmetic complexity. Conclusions In general, the findings suggest that the brain network for arithmetic processing is already established in 12–14 year-old adolescents, but still undergoes developmental changes.

Some individuals experience more difficulties with math than others, in particular when arithmetic problems get more complex. Math ability, on one hand, and arithmetic complexity, on the other hand, seem to partly share neural underpinnings. This study addresses the question of whether this leads to an interaction of math ability and arithmetic complexity for multiplication and division on behavioral and neural levels. Previously screened individuals with high and low math ability solved multiplication and division problems in a written production paradigm while brain activation was assessed by combined functional near-infrared spectroscopy (fNIRS) and electroencephalography (EEG). Arithmetic complexity was manipulated by using single-digit operands for simple multiplication problems and operands between 2 and 19 for complex multiplication problems and the corresponding division problems. On the behavioral level, individuals with low math ability needed more time for calculation, especially for complex arithmetic. On the neural level, fNIRS results revealed that these individuals showed less activation in the left supramarginal gyrus (SMG), superior temporal gyrus (STG) and inferior frontal gyrus (IFG) than individuals with high math ability when solving complex compared to simple arithmetic. This reflects the greater use of arithmetic fact retrieval and also the more efficient processing of arithmetic complexity by individuals with high math ability. Oscillatory EEG analysis generally revealed theta and alpha desynchronization with increasing arithmetic complexity but showed no interaction with math ability. Because of the discovered interaction for behavior and brain activation, we conclude that the consideration of individual differences is essential when investigating the neurocognitive processing of arithmetic.

• A low complexity algorithm for computing the discrete fractional Fourier transform is introduced. • The approach exploits properties of a specific discrete Fourier transform eigenbasis. • The technique requires half or less additions than what is required by state-of-the-art methods. • If a rounding strategy is applied, up to 65% of multiplications can be avoided. In this paper, we introduce a method for computing an eigendecomposition-based discrete fractional Fourier transform (DFrFT) with reduced arithmetic complexity, when compared to the O (N 2) complexity of the corresponding direct computation. Our approach exploits properties of a recently introduced closed-form Hermite-Gaussian-like discrete Fourier transform eigenbasis, which is used to define the DFrFT, and includes a rounding strategy. The proposed (exact) technique requires a slightly lower number of multiplications and half or less additions than what is required by other state-of-the-art methods; if the referred rounding strategy is applied, up to 65% of multiplications can be avoided. We validate our results by means of computer experiments where the application of the transform in signal filtering and compact representation is considered. [ABSTRACT FROM AUTHOR]

Some individuals experience more difficulties with math than others, in particular when arithmetic problems get more complex. Math ability, on one hand, and arithmetic complexity, on the other hand, seem to partly share neural underpinnings. This study addresses the question of whether this leads to an interaction of math ability and arithmetic complexity for multiplication and division on behavioral and neural levels. Previously screened individuals with high and low math ability solved multiplication and division problems in a written production paradigm while brain activation was assessed by combined functional near-infrared spectroscopy (fNIRS) and electroencephalography (EEG). Arithmetic complexity was manipulated by using single-digit operands for simple multiplication problems and operands between 2 and 19 for complex multiplication problems and the corresponding division problems. On the behavioral level, individuals with low math ability needed more time for calculation, especially for complex arithmetic. On the neural level, fNIRS results revealed that these individuals showed less activation in the left supramarginal gyrus (SMG), superior temporal gyrus (STG) and inferior frontal gyrus (IFG) than individuals with high math ability when solving complex compared to simple arithmetic. This reflects the greater use of arithmetic fact retrieval and also the more efficient processing of arithmetic complexity by individuals with high math ability. Oscillatory EEG analysis generally revealed theta and alpha desynchronization with increasing arithmetic complexity but showed no interaction with math ability. Because of the discovered interaction for behavior and brain activation, we conclude that the consideration of individual differences is essential when investigating the neurocognitive processing of arithmetic. [ABSTRACT FROM AUTHOR]

Using the proposed factorizations of discrete cosine transform (DCT) matrices, fast and recursive algorithms are stated. In this paper, signal flow graphs for the n-point DCT II and DCT IV algorithms are introduced. The proposed algorithms yield exactly the same results as with standard DCT algorithms but are faster. The arithmetic complexity and stability of the algorithms are explored, and improvements of these algorithms are compared with previously existing fast and stable DCT algorithms. A parallel hardware computing architecture for the DCT II algorithm is proposed. The computing architecture is first designed, simulated, and prototyped using a 40-nm Xilinx Virtex-6 FPGA and thereafter mapped to custom integrated circuit technology using 0.18-μm CMOS standard cells from Austria Micro Systems. The performance trade-off exists between computational precision, chip area, clock speed, and power consumption. This trade-off is explored in both FPGA and custom CMOS implementation spaces. An example FPGA implementation operates at clock frequencies in excess of 230 MHz for several values of system word size leading to real-time throughput levels better than 230 million 16-point DCTs per second. Custom CMOS-based results are subject to synthesis and place-and-route steps of the design flow. Physical silicon fabrication was not conducted due to prohibitive cost. [ABSTRACT FROM AUTHOR]

The design of high-performance adders has experienced a renewed interest in the last few years; among high performance schemes, parallel prefix adders constitute an important class. They require a logarithmic number of stages and are typically realized using AND-OR logic; moreover with the emergence of new device technologies based on majority logic, new and improved adder designs are possible. However, the best existing majority gate-based prefix adder incurs a delay of 2\mathbflo\mathbfg_2(\boldsymboln) - 1 (due to the \boldsymboln th carry); this is only marginally better than a design using only AND-OR gates (the latter design has a 2\mathbflo\mathbfg_2(\boldsymboln) + 1 gate delay). This paper initially shows that this delay is caused by the output carry equation in majority gate-based adders that is still largely defined in terms of AND-OR gates. In this paper, two new majority gate-based recursive techniques are proposed. The first technique relies on a novel formulation of the majority gate-based equations in the used group generate and group propagate hardware; this results in a new definition for the output carry, thus reducing the delay. The second contribution of this manuscript utilizes recursive properties of majority gates (through a novel operator) to reduce the circuit complexity of prefix adder designs. Overall, the proposed techniques result in the calculation of the output carry of an \boldsymboln -bit adder with only a majority gate delay of \mathbflo\mathbfg_2(\boldsymboln) + 1 . This leads to a reduction of 40percent in delay and 30percent in circuit complexity (in terms of the number of majority gates) for multi-bit addition in comparison to the best existing designs found in the technical literature. [ABSTRACT FROM AUTHOR]

One of the fundamental open questions in computational complexity is whether the class of problems solvable by use of stochasticity under the Random Polynomial time (RP) model is larger than the class of those solvable in deterministic polynomial time (P). However, this question is only open for Turing machines, not for Random Access Machines (RAMs). Simon (1981) [31] was able to show that for a sufficiently equipped Random Access Machine, the ability to switch states nondeterministically entails no computational advantage. On the other hand, in the same paper, Simon describes a different (and arguably more natural) model for RAM stochasticity. According to Simon's proposal, instead of receiving a new random bit at each execution step, the RAM program is able to execute the pseudofunction RAND ( y ) , which returns a uniformly distributed random integer in the range [ 0 , y ) . Whether the ability to allot a random integer in this fashion is more powerful than the ability to allot a random bit remained an open question for the last 30 years. In this paper, we close Simon's open problem by fully characterising the class of languages recognisable in polynomial time by each of the RAMs regarding which the question was posed. We show that for some of these stochasticity does not entail any advantage, but, more interestingly, we show that for others it does. These results carry over also to BPP-like and coRP-like acceptance criteria. [ABSTRACT FROM AUTHOR]

This paper focuses on online (or relaxed ) algorithms for the multiplication of power series over a field and their complexity analysis. We propose a new online algorithm for the multiplication using middle and short products of polynomials as building blocks, and we give the first precise analysis of the arithmetic complexity of various online multiplications. Our algorithm is faster than Fischer and Stockmeyer's by a constant factor; this is confirmed by experimental results. [ABSTRACT FROM AUTHOR]

We consider the growth of some indicators of arithmetical complexity of rational orbits of (piecewise) affine maps of the plane, with rational parameters. The exponential growth rates are expressed by a set of exponents; one exponent describes the growth rate of the so-called logarithmic height of the points of an orbit, while the others describe the growth rate of the size of such points, measured with respect to the p -adic metric. Here p is any prime number which divides the parameters of the map. We show that almost all the points in a domain of linearity (such as an elliptic island in an area-preserving map) have the same set of exponents. We also show that the convergence of the p -adic exponents may be non-uniform, with arbitrarily large fluctuations occurring arbitrarily close to any point. We explore numerically the behaviour of these quantities in the chaotic regions, in both area-preserving and dissipative systems. In the former case, we conjecture that wherever the Lyapunov exponent is zero, the arithmetical exponents achieve a local maximum. [ABSTRACT FROM AUTHOR]

We present an algorithm for sorting an arbitrary number of arbitrary-length integers in constant time on a random access machine (RAM). The algorithm forms a Straight Line Program (SLP). [ABSTRACT FROM AUTHOR]

One promising solution to reduce the computational complexity of discrete cosine transform (DCT) is to identify the redundant computations and to get rid of them. In this study, the authors present a new method to predict zero‐quantised DCT coefficients for efficient implementation of intra‐frame video encoding by identifying such redundant computations. Traditional methods use the Gaussian statistical model of residual pixels to predict all‐zero or partial‐zero blocks. The proposed method is based on two key ideas. At first, the bounds of DCT coefficients are derived from the intermediate signals of the Loeffler DCT algorithm instead of calculating the sum of absolute difference (SAD) of residual pixels. The sufficiency conditions are then suitably chosen to predict the zero‐quantised coefficients to reduce the arithmetic complexity without degrading the video quality. Simulation results are found to validate the analytical model and show that the proposed prediction eliminates more redundant computations than the existing methods. Moreover, the authors have derived a pipelined VLSI architecture of the proposed prediction scheme which offers a saving of more than 63 and 91% of multiplications of the second stage of one‐dimensional DCT for high and low bit‐rate intra‐video encoding, respectively. [ABSTRACT FROM AUTHOR]

Infinite permutations of use in this article were introduced in [1]. Here we distinguish the class of infinite permutations that are generated by the Sturmian words and inherit their properties. We find the combinatorial complexity of these permutations, describe their Rauzy graphs, frequencies of subpermutations, and recurrence functions. We also find their arithmetic complexity and Kamae complexity. [ABSTRACT FROM AUTHOR]

Abstract: We prove lower bounds for the complexity of deciding several relations in imaginary, norm-Euclidean quadratic integer rings, where computations are assumed to be relative to a basis of piecewise-linear operations. In particular, we establish lower bounds for deciding coprimality in these rings, which yield lower bounds for gcd computations. In each imaginary, norm-Euclidean quadratic integer ring, a known binary-like gcd algorithm has complexity that is quadratic in our lower bound. [Copyright &y& Elsevier]

This paper discusses a new approach for implementing flexible frequency-band reallocation (FFBR) networks for bentpipe satellite payloads which are based on variable oversampled complex-modulated filter banks (FBs). We consider two alternatives to process real signals using real input/output and complex input/output FFBR networks (or simply real and complex FFBR networks, respectively). It is shown that the real case has a lower overall number of processing units, i.e., adders and multipliers, compared to its complex counterpart. In addition, the real system eliminates the need for two Hilbert transformers, further reducing the arithmetic complexity. An analysis of the computational workload shows that the real case has a smaller rate of increase in the arithmetic complexity with respect to the prototype filter order and number of FB channels. This makes the real case suitable for systems with a large number of users. Furthermore, in the complex case, a high efficiency in FBR comes at the expense of high-order Hilbert transformers; thus, trade-offs are necessary. Finally, the performance of the two alternatives based on the error vector magnitude (EVM) for a 16-quadrature amplitude modulation (QAM) signal is presented. [ABSTRACT FROM AUTHOR]

A deterministic algorithm for calculating the roots of polynomials in one variable with coefficients in the ring of polynomials in several variables over an arbitrary integral domain is constructed. An estimate for the arithmetic complexity of the algorithm in the worst case is obtained. [ABSTRACT FROM AUTHOR]

Abstract: We present algorithms for the discrete cosine transform (DCT) and discrete sine transform (DST), of types II and III, that achieve a lower count of real multiplications and additions than previously published algorithms, without sacrificing numerical accuracy. Asymptotically, the operation count is reduced from to for a power-of-two transform size N. Furthermore, we show that an additional N multiplications may be saved by a certain rescaling of the inputs or outputs, generalizing a well-known technique for by Arai et al. These results are derived by considering the DCT to be a special case of a DFT of length , with certain symmetries, and then pruning redundant operations from a recent improved fast Fourier transform algorithm (based on a recursive rescaling of the conjugate-pair split-radix algorithm). The improved algorithms for the DCT-III, DST-II, and DST-III follow immediately from the improved count for the DCT-II. [Copyright &y& Elsevier]

Abstract: We present algorithms for the type-IV discrete cosine transform (DCT-IV) and discrete sine transform (DST-IV), as well as for the modified discrete cosine transform (MDCT) and its inverse, that achieve a lower count of real multiplications and additions than previously published algorithms, without sacrificing numerical accuracy. Asymptotically, the operation count is reduced from to for a power-of-two transform size N, and the exact count is strictly lowered for all . These results are derived by considering the DCT to be a special case of a DFT of length , with certain symmetries, and then pruning redundant operations from a recent improved fast Fourier transform algorithm (based on a recursive rescaling of the conjugate-pair split-radix algorithm). The improved algorithms for DST-IV and MDCT follow immediately from the improved count for the DCT-IV. [Copyright &y& Elsevier]