Aspekty algorytmiczne wyznaczania współczynników wielomianu Reeda-Mullera na podstawie trókąta Pascala

• Autorzy: Tariova G. , Tariov A.
• Języki publikacji: PL

Abstrakty

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.

Słowa kluczowe

PL

wielomian Reeda-Mullera; szybkie algorytmy; trójkąt Pascala

EN

Reed-Muller polynomial; fast algorithms; Pascal triangle

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2009
• Tom: nr 1 (18)
• Strony: 119--124
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Tariova G.

autor

Tariov A.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki

Bibliografia

• [1] B. J. Falkowski, M. A. Perkowski, One more way to calculate generalized Reed-Muller expansions of Boolean functions, Int. J. Electron., 1991, vol. 71, No.3, pp. 385-96.
• [2] B. J. Falkowski, A note on the polynomial form of Boolean functions and related topics, IEEE Transactions on Computers, 1999, vol.48, No 8, pp. 860-864.
• [3] P. Porwik, Efficient calculation of the Reed-Muller form by means of the Walsh transform. Int. J. Appl. Math. Comput. Sci., 2002, vol.12, No.4, pp. 571-579.
• [4] G. A., Kukharev, V. P. Shmerko, S. N. Yanushkevich, Technique of Binary Data Parallel Processing on VLSI, Publishing House "High School", Minsk, Belarus, 1, 220p.
• [5] R. Tolimieri M. An, C. Lu, Algorithms for Discrete Fourier Transform and Convolution, Springer-Verlag, 1989.
• [6] A. P. Ţariov, Modele algorytmiczne i struktury wysokowydajnych procesorów cyfrowej obróbki sygnałów, Szczecin, Informa, 2001.
• [7] E. E. Dagman., G. A. Kukharev. Szybkie dyskretne transformaty ortogonalne, Wydawnictwo Nauka, 1983.