Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 16

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  fast algorithms
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
EN
In this paper, we offer and discuss three efficient structural solutions for the hardware-oriented implementation of discrete quaternion Fourier transform basic operations with reduced implementation complexities. The first solution – a scheme for calculating sq product, the second solution – a scheme for calculating qt product, and the third solution – a scheme for calculating sqt product, where s is a so-called i -quaternion, t is an j - quaternion, and q – is an usual quaternion. The direct multiplication of two usual quaternions requires 16 real multiplications (or two-operand multipliers in the case of fully parallel hardware implementation) and 12 real additions (or binary adders). At the same time, our solutions allow to design the computation units, which consume only 6 multipliers plus 6 two input adders for implementation of sq or qt basic operations and 9 binary multipliers plus 6 two-input adders and 4 four-input adders for implementation of sqt basic operation.
EN
In this correspondence, we discuss two efficient algorithms for the execution of forward (FDMWT) and inverse (IDMWT) discrete multiwavelet transform basic operations with reduced computational complexities. We used multiwavelet basis proposed by Geronimo, Hadrin, and Massopust (GHM). The direct implementation of GHM-FDMWT basic operation requires 23 multiplications and 19 additions. The direct implementation of GHM-IDMWT basic operation requires 23 multiplication and 16 additions. At the same time, our solutions allow designing the computation procedures, which take only 10 multiplications plus 15 additions for GHM-FDMWT basic operation and 10 multiplications plus 10 additions for GHM-IDMWT basic operation
EN
This paper presents a low multiplicative complexity fully parallel algorithm for multiplying two dual quaternions. The “pen-and-paper” multiplication of two dual quaternions requires 64 real multiplications and 56 real additions. More effective solutions still do not exist. We show how to compute a product of two dual quaternions with 24 real multiplications and 64 real additions. During synthesis of the discussed algorithm we use the fact that the product of two dual quaternions can be represented as a matrix–vector product. The matrix multiplicand that participates in the product calculating has unique structural properties that allow performing its advantageous factorization. Namely this factorization leads to significant reducing of the multiplicative complexity of dual quaternion multiplication. We show that by using this approach, the computational process of calculating dual quaternion product can be structured so that eventually requires only half the number of multipliers compared to the direct implementation of matrix-vector multiplication.
EN
In this work a rationalized algorithm for Dirac numbers multiplication is presented. This algorithm has a low computational complexity feature and is well suited to parallelization of computations. The computation of two Dirac numbers product using the naïve method takes 256 real multiplications and 240 real additions, while the proposed algorithm can compute the same result in only 128 real multiplications and 160 real additions. During synthesis of the discussed algorithm we use the fact that Dirac numbers product may be represented as vector-matrix product. The matrix participating in the product has unique structural properties that allow performing its advantageous decomposition. Namely this decomposition leads to significant reducing of the computational complexity.
EN
In this paper the authors show that fast parametrized biorthogonal transforms (FPBT) are well suited for adaptive generalized Wiener image filtering. Research results are obtained with a use of a new graphical user interface system for implementing various fast adaptive techniques, designed, implemented and published by the authors as a part of a project Innovative Economy Programme 2007-2013 „Platforma Informatyczna TEWI”.
EN
In this paper the authors propose a new low-complexity approximation of 8-point discrete cosine transform (DCT) that requires 18 additions and two bit-shift operations. It is shown that the proposed transform outperforms significantly the known transform of the same computational complexity when applied to a JPEG compression stream in practical cases of encoding and decoding of still images. As such, the proposed transform can be effectively used in any practical applications where significant limitations exist regarding the computational capabilities coding and / or decoding devices, i.e. mobile devices or industrial imaging devices.
EN
This paper introduces a new method for an adaptive synthesis of a wavelet transform using a fast neural network with a topology based on the lattice structure. The lattice structure and the orthogonal lattice structure are presented and their properties are discussed. A novel method for unsupervised training of the neural network is introduced. The proposed approach is tested by synthesizing new wavelets with an expected energy distribution between low- and high-pass filters. Energy compaction of the proposed method and Daubechies wavelets is compared. Tests are performed using sound and image signals.
8
Content available remote Zracjonalizowany algorytm mnożenia dwóch kwaternionów
PL
W pracy został przedstawiony syntezowany przez autorów zracjonalizowany algorytm mnożenia dwóch kwaternionów wymagający w najbardziej ogólnym przypadku wykonania mniejszej liczby operacji mnożenia w stosunku do bezpośredniego, naiwnego sposobu liczenia.
EN
The rationalized algorithm for two quaternion multiplication which require in the common case of a fewer number of multiplication operations then naive way of computing is presented.
EN
In the work the vectorized algorithm for Strassen's matrix product calculating is presented. Unlike the proposed in other works "some recommendations" relating to the Strassen's matrix multiplication implementation, we offer specific computational procedures that allow correctly describe the entire sequence of transformations needed to obtain the final result. The proposed algorithm can be successfully applied to accelerate calculations in the FPGA-based platforms.
PL
W pracy został przedstawiony wektoryzowany algorytm wyznaczenia iloczynu macierzowego Strassena. W odróżnieniu od poruszanych w innych publikacjach wybranych uwag dotyczących realizacji metody Strassena w niniejszej pracy zaproponowane są konkretne procedury, opisujące cały proces obliczeniowy i pozwalające na podstawie wykonania skończonej liczby etapów przetwarzania danych wejściowych otrzymać wynik końcowy. Została roztrząśnięta synteza proponowanego algorytmu oraz pokazana postać stosownego grafu przepływowego dla przykładu mnożenia macierzy drugiego rzędu. Zaproponowany algorytm może być sukcesywnie zastosowany do przyspieszonej realizacji obliczeń w platformach FPGA oraz zaimplementowany w wybranym środowisku sprzętowym. Niewątpliwym atutem odróżniającym przedstawione rozwiązanie od tradycyjnego algorytmu jest również brak rekurencji obliczeń, co daje dodatkowy zysk przy zrównolegleniu procesu wyznaczenia iloczynu.
10
Content available Szybki algorytm splotu kołowego dla N = 2^m
PL
W pracy został przedstawiony szybki algorytm liczenia splotu kołowego N-elementowych wektorów danych ze zredukowaną liczbą operacji arytmetycznych (lub układów mnożących i sumatorów, jeśli chodzi o implementację sprzętową) w przypadku, gdy N=2^m, m - liczba całkowita. Pozwala to przy implementacji zmniejszyć nakłady obliczeniowe lub zapotrzebowanie na zasoby sprzętowe oraz stworzyć dogodne warunki do efektywnej realizacji operacji splotu kołowego w dowolnym sprzętowo-programowym środowisku implementacyjnym.
EN
In the work the fast algorithm for 2n-point circular convolution calculating with the reduced number of arithmetic operations (or multipliers and adders - in hardware implementation case) is presented. Computational procedure for describing the algorithm, based on the successful decomposition of the circulant matrix of arbitrary order is shown. This approach allows to lower hardware expenses and to create favorable conditions for effective convolution realization in the reprogrammable platform. Computational procedure for circular convolution realization can be described by means of matrix algebra notation. Matrix algebra offers not only a formalism for describing the algorithm, but it enables the derivation by pure algebraic manipulations of an algorithm that is well suited to be implemented in vector and matrix digital signal processors with various levels of parallelism. In addition, the mentioned procedures can be directly used for easy implementation in matrix-oriented languages like Matlab.
PL
W artykule opisano własności algorytmiczne organizacji sieci logicznej do wyznaczania współczynników wielomianu Reeda-Mullera na podstawie trójkąta Pascala. Pod kątem złożoności proponowane rozwiązanie lokuje się pomiędzy metodą bezpośredniego wyznaczania tych współczynników za pomocą iloczynu macierzowo-wektorowego oraz algorytmem na podstawie szybkiej transformaty koniunkcyjnej. Oznacza to, że uzyskana ostatecznie struktura jest mniej skomplikowana niż w przypadku realizacji metody bezpośredniej, oraz wymaga przy sprzętowej implementacji mniej elementów logicznych. Natomiast w porównaniu do struktury opartej na realizacji „szybkich” algorytmów wymaga ona więcej elementów logicznych, posiadając jednak bardziej regularną oraz prostszą strukturę. Cechą charakterystyczną proponowanego podejścia jest to, że w razie obecności na wejściach sieci logicznej wszystkich wartości funkcji boolowskich, odpowiednie wartości współczynników wielomianu Reeda-Mullera mogą być po kolei wyznaczone w trakcie realizacji procesu przetwarzania danych po rozpoczęciu każdej kolejnej iteracji. Natomiast w przypadku sekwencyjnego sposobu realizacji procesu obliczeniowego odpowiednie wartości współczynników tego wielomianu mogą być wyznaczone w trakcie nadchodzenia kolejnych wartości funkcji boolowskich, nie oczekując na obecność całego wektora danych na wejściach sieci. Tych walorów nie posiadają obydwie wspomniane metody, służące w tej pracy za punkt odniesienia. Wszystko to sprawia, że zaprezentowane w artykule podejście stanowi w pełni konkurencyjne rozwiązanie w stosunku do rozwiązań porównywanych.
EN
In the paper the approach to the rational organization of logical network structure for simplified calculation of Reed-Muller polynomial coefficients with the reduced number of logical operation (EXOR gates or modulo-2 adders - in hardware implementation case) is presented.
12
Content available remote Szybki algorytm realizacji bazowej operacji wyznaczania średniej kroczącej
EN
The effective algorithm of realization of basic operation for calculation of a simple moving average is described. For realization of calculations the. algorithm requires only L operations of multiplication and 2(L-l) operations of additions.
13
EN
Strategies of rationalization of computing of constant coefficient matrix by vector multiplication are offered. The concrete example of synthesis of fast algorithm, for matrix by vector multiplication is considered. The offered example allows tracking all stages of construction of the algorithm rationalized from point of view number multiplication minimization.
14
Content available remote Efektywne algorytmy wyznaczania wyrażenia postaci Y=(AÄB)X
EN
The two algorithms of Y=(AÄB)X expression realization with reduced number of arithmetic operations are proposed.
15
Content available remote Fast adaptive algorithm for two-dimensional Fourier transform
EN
Fast adaptive algorithm for two-dimensional Fourier transform is presented. It enables automatic selection of time domain discretisation steps depending on the required accuracy of numerical calculation of signal spectrum. Errors of spectrum calculation can be estimated with help of the proposed formulas constructed in relative and absolute: maximum difference, mean square error and peak signal to noise ratio metrics. All calculations are performed in accordance with the structures of fast time decimated algorithms.
PL
Przedstawiono szybki algorytm adaptacyjnego obliczania dwuwymiarowego przekształcenia Fouriera, umożliwiający dobór kroków dyskretyzacji w zależności od żądanej dokładności numerycznego obliczenia widma, przy czym obliczenia realizowane są w oparciu o struktury szybkich algorytmów z przerzedzeniem w czasie. Ponadto zaproponowano wyrażenia oceny błędu obliczenia widma we względnych i bezwzględnych metrykach: maksymalnego odchylenia, błędu średniokwadratowego oraz szczytowego stosunku sygnału do szumu.
PL
W pracy zostało przedstawione podejście do zoptymalizowanej organizacji struktur algorytmicznych jednostek obliczeniowych dla realizacji bazowych operacji FDWT/IDWT ze zredukowaną liczbą mnożeń (lub układów mnożących w przypadku implementacji sprzętowej). Podejście to pozwala zmniejszyć nakłady obliczeniowe, zapotrzebowanie na zasoby sprzętowe oraz stworzyć dogodne warunki do efektywnej realizacji metod falkowego przetwarzania danych w układzie reprogramowalnym.
EN
This paper is concerned with the novel algorithmic structures for the realization of FDWT and IDWT basic procedures with the reduced number of arithmetic operations. As to well-known approaches, the immediate implementation of the above procedures requires 2L multipliers both for the DWT and IDWT basic procedures plus 2(L-1) adders for DWT and L adders for IDWT. At the same time, proposed algorithms require only 11oL multipliers for the both procedures plus 2L-1 adders for FDWT and L+1 adders for IDWT basic procedures. The proposed structures can be successfully applied to accelerate calculations in the FPGA-based platforms as well as to enhance the efficiency of hardware in general.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.