The paper is dedicated to construction of new fast and flexible hash-based message authentication codes (HMACs) that will provide large files with cryptographically stable digestions in the Postquantum era. These instruments can be used for detecting cyber-terrorist attacks, file audits and checking the integrity of messages during communication, We use algebraic properties of well known extremal graphs D(n, q) and A(n,q) with good expansion property for the construction of HMACS.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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”.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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.
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.
W artykule zostały poruszone różnorakie aspekty rozwojowe problemu racjonalizacji obliczeń. Wskazano na dialektyczną naturę rozwoju techniki racjonalizacji obliczeń, ewoluującego w procesie walki i jedności przeciwieństw. Należałoby jednak jeszcze raz zwrócić uwagę na to, iż przy realizacji rozmaitych zadań racjonalizacji obliczeń niemożliwe jest wynalezienie jedynego rozwiązania, spełniającego wszystkie, niekiedy sprzeczne wymagania. Na przykład, mimo niewątpliwej efektywności zrównoleglenia obliczeń, nie należy przeceniać jego znaczenia. Zrównoleglenie obliczeń nie może stanowić „celu w sobie” – jest ono tylko jednym z wielu sposobów podniesienia wydajności urządzeń przetwarzania danych. Oczywistym jest również fakt, iż każde z proponowanych przez projektanta lub producenta rozwiązań może okazać się efektywnym z punktu widzenia jednych kryteriów i słabo lub wcale nieefektywnym pod kątem innych. Co więcej: można stwierdzić istnienie pewnej „zasady zachowania”, czasem stwarzającej sytuację, gdy optymalizacja projektu pod kątem jednego parametru może spowodować utratę optymalności pod kątem innego. Na przykład optymalizacja procesu przetwarzania danych w celu przyspieszenia obliczeń pod kątem minimalizacji liczby mnożeń może spowodować taki wzrost liczby operacji dodawania lub na tyle skomplikować procedury transferu danych oraz sterowania zasobami operacyjnymi, iż cały ten wysiłek pójdzie na marne. Tutaj jednak należy podkreślić, że żadne urozmaicenie istniejących podejść do racjonalizacji obliczeń nie może stać się argumentem do przerwania poszukiwania nowych rozwiązań, możliwe bardziej efektywnych z punktu widzenia wcześniej nieuwzględnionych kryteriów. Dlatego ma prawo istnieć dowolne racjonalne podejście do rozwiązywania aktualnego problemu, ponieważ każdy nowy pogląd, każde nowe rozwiązanie nawet dobrze znanego tradycyjnego zadania, stymuluje rozwój teorii i praktyki, poszerza oraz pogłębia naszą wiedzę w odpowiedniej dziedzinie nauki lub techniki i, chociażby pod tym względem, jest pożytecznym.
EN
The paper drew attention to the dialectic nature of the dynamics of development in the area of streamlining computations. Pointed out that progress in the rationalization of computing is evolving, based on the known principle of unity and struggle of opposites. Existence of certain "law of conservations ", which makes impossible optimization of all parameters of calculation simultaneously is also noted.
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.
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.
9
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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.
W artykule przedstawiono nowe [podejście do efektywnej organizacji procesu obliczeniowego wyznaczania współczynników dyskretnej transformaty falkowej (prostei bez odwrotnej), bazujace na oryginalnyxh algorytmach dla realizacji bazowych operacji DWT/IDWT ze zredukowaną liczbą operacji arytmetycznych. Podejście to pozwala zmniejszyc nakłady obliczeniowe lub (w przypadku implementacji sprzetowej) zapotrzebowanie na zasoby sprzętowe oraz stworzyć warunki do efektywnejrealizacji metod falkowej obróbki danych w środowisku sprzetowo-programowym.
EN
This paper is concerned with the novel algorithms for the realization of DWT 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 multiplications both for the DWT and IDWT basic procedures plus 2(L-l) additions for DWT and L additions for IDWT. At the same time, proposed algo-rithms require only 1 1/2 L multiplications for the both procedures plus 2(L-1) additions for DWT and L+l additions for IDWT basic procedures. The proposed algorithms can be successfully applied to accel-erate calculations in the common-used computers as well as to enhance the efficiency of hardware in general.
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ć.