Вісники та науково-технічні збірники, журнали
Permanent URI for this communityhttps://ena.lpnu.ua/handle/ntb/12
Browse
14 results
Search Results
Item Порівняльний аналіз функцій обчислення модульної експоненти(Видавництво Львівської політехніки, 2022-02-28) Процько, І. О.; Рикмас, Р. В.; Грищук, О. В.; Protsko, I. O.; Rykmas, R. V.; Gryshchuk, O. V.; Національний університет “Львівська політехніка”; ТОВ "ЮніСервіс"; ТОВ "СофтСерв"; Lviv Polytechnic National University; LtdS "Uniservice"; LtdS "Softserve"Обчислення модульної експоненти для великих чисел широко використовується для знаходження дискретного логарифму, в теоретико-числових перетвореннях та в криптографічних алгоритмах. Для ефективного обчислення модульної експоненти проводяться дослідження нових методів, алгоритмів та засобів їх реалізації. Виділяють три напрями методів модульного піднесення до степеня: загальне модульне піднесення до степеня, та обчислення модульної експоненти з фіксованим показником або з фіксованою основою. Розроблено спеціальні функції для виконання піднесення до степені за модулем у математичних і криптографічних програмних бібліотеках. У роботі проведено порівняльний аналіз вільнодоступних функцій обчислення модульної експоненти з бібліотек Crypto++, OpenSSL, Pari/GP та MPIR та розроблених трьох функцій на основі алгоритму бінарного зсуву справа на ліво. Для роботи з великими числами у розроблених функціях використовується окремий тип числових даних з бібліотеки MPIR. Розроблені функції реалізують бінарний ітераційний алгоритм в одному основному потоці, у двох потоках та одному потоці з використанням передобчислення. За основу порівняння вибрано усереднений тривалість виконання обчислення модульної експоненти для псевдовипадкових даних розрядністю 1К і 2К біт, що відповідає розрядності біля 300 і 600 десяткових знаків. Результати часу виконання, що зведені у таблицю, показують, що найшвидше обчислюється модульна експонента функцією з бібліотеки OpenSSL в універсальних комп'ютерних системах. Реалізації математичними та криптографічними програмними бібліотеками функції обчислення модульної експоненти використовує більш оптимальний алгоритм множення за модулем, так зване множення Монтгомері. У розроблених трьох функціях використовуються операції множення за модулем для множників менших за значення модуля. Окремо проаналізовано функцію з використанням передобчислення залишків для фіксованої основи та модуля, що може ефективно використовуватись для обчислення дискретного логарифму.Item Аналіз похибки обчислення швидких перетворень класу Фур'є на підставі циклічних згорток(Видавництво Львівської політехніки, 2020-09-23) Процько, І. О.; Островка, Д. В.; Protsko, I. O.; Ostrovka, D. V.; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityПроаналізовано особливості обчислювальної моделі дискретних перетворень класу Фур'є на підставі циклічних згорток для визначення алгоритмічної похибки розрахунку. На підставі підходу ефективного обчислення дискретного перетворення класу Фур'є довільного обсягу N, що ґрунтується на використанні твірного масиву для переформування дискретної базисної матриці перетворення у набір блочно-циклічних під матриць, розглянуто складові обчислювальних затрат. Ці складові обчислювальних затрат залежать від виду перетворення, обсягу та від блочно-циклічної структури ядра перетворення. Подано приклади обчислювальної моделі та блочно-циклічної структури матриць спрощених аргументів базисів для взаємозворотних дискретних косинусних перетворень типів ІІ, ІІІ. Обчислювальна модель характеризує накопичення похибок округлення на етапах додавання вхідних даних, обчислення циклічних згорток, об'єднання результатів згорток. Дискретні циклічні згортки можуть бути реалізовані за допомогою швидких алгоритмів або виді систем, що відповідають цифровим фільтрам зі скінченними імпульсними характеристиками. Можливість паралельного обчислення зменшеної кількості циклічних згорток робить аналіз похибок нечутливим до переупорядкування їх обчислень. Операції множення, що здійснюється при обчисленні циклічної згортки, використовують меншу кількість коефіцієнтів базису перетворення, що дорівнює N/4 або N/2 залежно від обсягу перетворення. Розглянуто формати представлення дійсних чисел в обчислювальній систем, що також визначають величину похибки обчислення перетворень. Подано результати виконання прямого та швидкого обчислення дискретного косинусного перетворення типу ІІ на підставі циклічних згорток обсягом N=58 у форматі з рухомою крапкою подвійної точності та похибки обчислення між ними. Апріорний процес дослідження похибок перетворення відповідного виду та обсягу методом математичного моделювання та обчислювального експерименту носить наближений характер, який дає змогу передбачити статистичні середні значення точності обчислення дискретного перетворення класу Фур'є довільного обсягу на підставі циклічних згорток.Item Швидкі перетворення класу Фур'є в OFDM технології систем безпровідної передачі інформації(Видавництво Львівської політехніки, 2019-09-26) Процько, І. О.; Prots'ko, I. O.; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityВиділено основні модифікації та стандарти технології OFDM, що забезпечують високу якість зв'язку при багатопроменевому поширенні переданого сигналу. Проаналізовано в структурі передавача комунікаційної системи на підставі OFDM технології виконання швидких перетворень класу Фур'є. Функцію мультиплексування/демультиплексування з ортогональним частотним розділенням покладено на обчислювач швидких перетворень, а прекодер застосовується для зменшення високого значення пік-фактора, що властиве OFDM технології. Визначено основні елементи та вимоги до обчислювачів, що виконують швидкі перетворення у структурній схемі реалізації OFDM технології. Розглянуто зв'язок кількості піднесучих частот та обсягу базового перетворення OFDM технології. З'ясовано можливість використання у прекодері перетворень Фурє, Хартлі та косинусних перетворень. Сформульовано основні етапи побудови структурних схем швидких перетворень класу Фур'є на підставі циклічних згорток. Визначені етапи містять: побудову твірного масиву, визначення спрощеного твірного масиву доповненого масивом знаків, побудову й аналіз узагальненої структури базисної матриці, побудову блоків об'єднання вхідних даних, побудову блоків циклічних згорток, побудову блоків об'єднання результатів циклічних згорток, виходами яких є результат прямого/зворотного перетворення класу Фур'є на підставі циклічних згорток. Розглянуто приклад для обсягу N=16 визначення твірного масиву, спрощеного твірного масиву й масиву знаків, базисної блочно-циклічної матриці, що використовуються при побудові структурної схеми обчислювача. Встановлено можливість використання процесу побудови структурних для автоматизації проектування структурних обчислювачів швидких перетворень класу Фур'є на підставі циклічних згорток.Item Розробка схеми узагальненого ефективного алгоритму гармонічного перетворення даних(Видавництво Національного університету “Львівська політехніка”, 2005-03-01) Процько, І. О.; Національний університет “Львівська політехніка”Для прийняття рішень з організації процесу обчислення гармонічних перетворень даних змінних обсягів використовується сформований циклічний розклад підстановки, який визначається на основі базисної матриці перетворень. Розлянуто узагальнену схему ефективного алгоритму на основі формування блочно-матричних структур аргументів базису гармонічного дискретного перетворення.Item Автоматичне генерування ефективних алгоритмів ДКП-II на основі циклічних згорток(Видавництво Львівської політехніки, 2017-03-28) Процько, І. О.; Рикмас, Р. В.; Protsko, I.; Rykmas, R.; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityРозглянуто програмну реалізацію дискретного косинусного перетворення другого типу ДКП-II на основі циклічних згорток. Визначено етапи автоматичного генерування ефективних алгоритмів для обчислення ДКП-II довільного обсягу N. Алгоритм ДКП-II має швидшу програмну реалізацію для коротких обсягів порівняно з відомою бібліотекою FFTW.Item Огляд алгоритмів ефективного обчислення ДПФ на основі циклічних згорток(Видавництво Львівської політехніки, 2016) Процько, І. О.Розглянуто підходи ефективного обчислення дискретних перетворень класу Фур’є на основі циклічних згорток. Описано сутність переформулювання базисних матриць перетворення ДПФ на блочно-циклічні структури для кожного підходу. Аналізуються переваги і недоліки алгоритмів для кожного підходу. The enumeration approaches of efficient computation discrete transform of Fourier class using cyclic convolutions is considered. The formulation of the basis matrix of transforms into the block cyclic structures is described of each approach. The analysis of the advantages and imperfections of the algorithms are discussed.Item Секціонування базової матриці дискретного гармонічного перетворення даних(Видавництво Національного університету «Львівська політехніка», 2006) Никифорчин, Р. Б.; Процько, І. О.Розглянуто програмну модель визначення еквівалентних циклічних секцій для матриці показників і матриці знаків дійсного базису дискретного гармонічного перетворення даних. Результати програмної моделі можуть застосовуватись для проектування розподілу завантаження ресурсів розподілених обчислювальних структур та створення ефективних алгоритмів виконання перетворень. The program model of determination the equivalent sections of the matrix of arguments and signs of the real discrete harmonic transform basis is considered. The program can be used for scheduling design on the computing distributed structures and for implementation different efficient algorithms of discrete harmonic transform.Item Формування блочно-матричних структур для алгоритмів гармонічного перетворення даних(Видавництво Львівської політехніки, 2005) Никифорчин, Р. Б.; Процько, І. О.Для прийняття рішень з організації обчислення гармонічних дискретних перетворень даних змінних обсягів використовується сформований циклічний розклад підстановки, який визначається на основі базисної матриці перетворень. Розлянуто програмну реалізацію і результати формування блочно-матричних структур за циклічним розкладом підстановки для алгоритмів перетворення даних. The passing decisions for synthesis efficient algorithm calculation of the harmonic discrete transforms the arbitrary size of data are used the formed cycle decomposition of substitution what determine for the discrete basis matrix of transform. Program implementation and results of the constructed block-matrix structures on base of the cycle decomposition of substitution for algorithm of the harmonic discrete transforms is considered.Item Ефективне обчислення дискретного перетворення Хартлі на основі циклічних згорток(Видавництво Львівської політехніки, 2010) Процько, І. О.Розглянуто узагальнений підхід ефективного обчислення дискретного перетворення Хартлі (ДПХ) на основі циклічних згорток. Підхід ґрунтується на приведенні матриці аргументів і матриці знаків дійсного базису ДПХ до еквівалентних циклічних секцій. The general method of efficient computation discrete Hartley transform using of circular convolutions is considered. The method is based on the presentation of the matrix of arguments and signs of the real basis the discrete Hartley transform to the equivalent cyclic sections.Item Алгоритм обчислення основних видів ДСП на базі циклічних згорток(Видавництво Львівської політехніки, 2012) Процько, І. О.Розглянуто підхід ефективного обчислення основних чотирьох видів дискретного синусного перетворення (ДСП) на базі циклічних згорток. Параметри твірного масиву базисної квадратної матриці використано для синтезу алгоритму. The general method of efficient computation four types discrete sine transform using ofcircular convolutions is considered. The parameters of hash array the basis square matrix for algorithm synthesis are used.