Використання похибки заокруглення в сучасних комп’ютерних технологіях

Мета роботи. Звернути увагу фахівців з обчислювальної та прикладної математики на необхідність врахування похибки заокруглення при аналізі якості наближеного розв’язку задач. Це важливо для задач математичного моделювання, задач, які використовують Bigdata, цифрової обробки сигналів і зображень, кіб...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Кібернетика та комп’ютерні технології
Datum:	2021
Hauptverfasser:	Задірака, В.К., Швідченко, І.В.
Format:	Artikel
Sprache:	Ukrainisch
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2021
Schlagworte:	Математичне моделювання та чисельні методи
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/181349
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Використання похибки заокруглення в сучасних комп’ютерних технологіях / В.К. Задірака, І.В. Швідченко // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 3. — С. 43-52. — Бібліогр.: 10 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859838606413135872
author	Задірака, В.К. Швідченко, І.В.
author_facet	Задірака, В.К. Швідченко, І.В.
citation_txt	Використання похибки заокруглення в сучасних комп’ютерних технологіях / В.К. Задірака, І.В. Швідченко // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 3. — С. 43-52. — Бібліогр.: 10 назв. — укр.
collection	DSpace DC
container_title	Кібернетика та комп’ютерні технології
description	Мета роботи. Звернути увагу фахівців з обчислювальної та прикладної математики на необхідність врахування похибки заокруглення при аналізі якості наближеного розв’язку задач. Це важливо для задач математичного моделювання, задач, які використовують Bigdata, цифрової обробки сигналів і зображень, кібербезпеки і багатьох інших. У статті продемонстровано конкретні оцінки похибки заокруглення для розв’язання ряду задач: оцінки математичного очікування, обчислення дискретного перетворення Фур’є, використання багаторазрядної арифметики і застосування оцінок похибки заокруглення в алгоритмах розв’язання задач комп’ютерної стеганографії. Результати. Наведено оцінки похибки заокруглення алгоритмів розв’язання вищеперерахованих класів задач при різних правилах заокруглення і для різних режимів обчислень. Для задач конструюючої комп’ютерної стеганографії показано використання оцінок похибки заокруглення в комп’ютерних технологіях розв’язання задач прихованої передачі інформації. Цель работы. Обратить внимание специалистов по вычислительной и прикладной математике на необходимость учета погрешности округления при анализе качества приближенного решения задач. Это важно для задач математического моделирования, задач, использующих Bigdata, цифровой обработки сигналов и изображений, кибербезопасности и многих других. В статье продемонстрированы конкретные оценки погрешности округления для решения ряда задач: оценки математического ожидания, вычисления дискретного преобразования Фурье, использования многоразрядной арифметики и применения оценок погрешности округления в алгоритмах решения задач компьютерной стеганографии. Результаты. Приведены оценки погрешности округления алгоритмов решения вышеперечисленных классов задач при разных правилах округления и для разных режимов вычислений. Для задачи конструирующей компьютерной стеганографии показано использование оценок погрешности округления в компьютерных технологиях решения задач скрытой передачи информации. The purpose of the article is to draw the attention of the specialists in computational and applied mathematics to the need to take into account the rounding error when analyzing the quality of the approximate solution of problems. This is important for mathematical modeling problems, problems using Bigdata, digital signal and image processing, cybersecurity, and many others. The article demonstrates specific estimates of the rounding error for solving a number of problems: estimating the mathematical expectation, calculating the discrete Fourier transform, using multi-digit arithmetic and using the estimates of the rounding error in algorithms for solving computer steganography problems. The results. The estimates of the rounding error of the algorithms for solving the above-mentioned classes of problems are given for different rounding-off rules and for different calculation modes. For the problem of constructing computer steganography, the use of the estimates of the rounding error in computer technologies for solving problems of hidden information transfer is shown.
first_indexed	2025-12-07T15:36:09Z
format	Article
fulltext	МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ЧИСЕЛЬНІ МЕТОДИ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 43 КІБЕРНЕТИКА та КОМП'ЮТЕРНІ ТЕХНОЛОГІЇ Показана важливість врахування похибок заокруглення в сучасних комп’ютерних тех- нологіях розв’язання задач обчислювальної та прикладної математики з заданими зна- ченнями характеристик якості за точністю та швидкодією. Розглянуті наступні класи задач: розв’язання систем лінійних алгебраї- чних рівнянь, задач цифрової обробки сигна- лів, задач комп’ютерної стеганографії та використання багаторозрядної арифметики для контролю та зменшення похибки заокру- глення при розв’язанні задач трансобчислю- вальної складності. Ключові слова: похибка заокруглення, ком- п’ютерні технології, дискретне перетво- рення Фур’є, багаторозрядна арифметика, комп’ютерна стеганографія.   В.К. Задірака, І.В. Швідченко, 2021 УДК 519.65 DOI:10.34229/2707-451X.21.3.4 В.К. ЗАДІРАКА, І.В. ШВІДЧЕНКО ВИКОРИСТАННЯ ПОХИБКИ ЗАОКРУГЛЕННЯ В СУЧАСНИХ КОМП’ЮТЕРНИХ ТЕХНОЛОГІЯХ Вступ. Похибка заокруглення – одна з видів похибок, яка разом зі спадковою похибкою і похибкою методу, впливає на точність наближеного розв’язку задач. Якщо до 60-х років похибкою заокруглення нехту- вали (вважали її значно менше за інші види похибок), то в подальшому завдяки роботам Дж.Х. Вілкінсона, В.В. Воєводіна та інших вчених і збільшенні складно- сті задач, що розв’язуються, їй почали приділяти значну увагу. Найбільш досліджуваним класом задач з точки зору накопичення похибки заокруглення була лінійна ал- гебра, але потім методи теорії похибок заокруглення почали використовуватися і для інших класів задач. Кожна арифметична операція вносить свій «вне- сок» в оцінку похибки заокруглення. І чим більше операцій, тим більший цей «внесок». При розв’язанні задач трансобчислювальної складності неврахування похибки заокруглення призводить до того, що отри- мані комп’ютерні моделі досліджуваних явищ нічого спільного з фізичними моделями не мають. Для таких класів задач часто похибка заокруглення стає самою значущою – її «внесок» в оцінку повної похибки обчислювального алгоритму стає значним, і не врахо- вувати його не тільки не можна, але й неврахування її не дає можливості отримати ε -розв’язок задачі. Проаналізуємо різні правила заокруглення: класич- не, відсікання і рандомізоване. Саме задачі АСУ та комп’ютерна техніка ЄС ЕОМ «підштовхнули» елект- ронників перейти від класичного правила заокруглен- ня до відсікання (оскільки схемно дуже просто реалі- зується і задачі АСУ мали відносно невелику склад- ність). Якщо розташувати зазначені правила заокруг- лення в порядку накопичення похибки заокруглення, то найповільніше похибка заокруглення накопичуєть- ся при рандомізованому правилі заокруглення, потім йде класичне правило і найгірше – відсікання. Незважаючи на критику математиків на адресу відсі- кання, електронники не можуть відійти від простоти його реалізації і, як ми бачимо, і в персональних ЕОМ і навіть у суперкомп’ютерах залишається відсікання. https://doi.org/10.34229/2707-451X.21.3.4 В.К. ЗАДІРАКА, І.В. ШВІДЧЕНКО 44 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 Ми «женемося» за швидкодією, забуваючи про точність, і про те, що час, точність і викорис- товувана пам’ять комп’ютера взаємопов’язані. Основними постановками задач оптимізації обчислень є: – мінімізація часу  , ,T I X Y при дотриманні реальних  Re обмежень на точність  , ,E I X Y і пам’ять  , ,M I X Y :   , , , , min I X Y T I X Y  ,   Re, ,E I X Y E ,   Re, ,M I X Y M , (1) – мінімізація повної похибки  , ,E I X Y при дотриманні обмежень на T і M   , , , , min I X Y E I X Y  ,   Re, ,T I X Y T ,   Re, ,M I X Y M , (2) де , ,I X Y – скінченні множини параметрів, від яких істотно залежать відповідно задача, алгоритм, комп’ютер. Неврахування обмежень може призвести до абсурдних постановок задач і результатам, отри- маними в рамках таких постановок. Наприклад, якщо в (1) не враховувати обмеження на  , ,E I X Y , то можна стверджувати, що оптимальний за швидкодією алгоритм вимагає час рівний часу вибірки числа з пам’яті комп’ютера. , ,T E M як правило, нам невідомі, але нам відомі їхні оцінки , ,T E M . Оцінки можуть бути апріорними, апостеріорними, мажорантними, асімтотичними, детермінованими, статистичними. Мажорантні оцінки, які найбільш часто використовуються, можуть бути різної якості: грубі і непокращувальні. З точки зору математичного аналізу, теорії функцій, наприклад, непокращу- вальні оцінки точності – це суперрезультати. Але на практиці задачі, на які вони досягаються (або асимптотично досягаються), не зустрічаються, хоча формально належать класу задач, що роз- глядається. Так що непокращувальні оцінки на практиці є завищеними (для реальних задач). Як бути? Є два способи. Перший – це «занурити» задачу в більш вузький клас (звужувати до тих пір, поки непокращувальні оцінки не будуть досягатися на реальних задачах). В цьому випадку оцінкам можна «довіряти». Це важливо, оскільки на їх підставі визначаються оцінки обчислюваль- них ресурсів, необхідних для розв’язання задач (1), (2), а також вони використовуються в комп’ютерних технологіях розв’язання задач обчислювальної і прикладної математики із заданими значеннями характеристик якості за точністю і швидкодією. Другий шлях – вважати вектор I випадковим і знаходити статистичні оцінки характеристик. Статистичні характеристики краще відображають поведінку похибок для задач середньої складності. Важливе значення має отримання асимптотичних оцінок похибок, які знаходяться порівняно просто за рахунок врахування малих величин лише головних порядків і які поблизу граничних значень варійованих параметрів виявляються близькими до реальних похибок. Нагадаємо, що використовуються два режими обчислень – плаваюча кома та фіксована. Оцінки похибки заокруглення безумовно різні. Режим фіксованої коми дозволяє пришвидшити обчислювальний процес (не треба вирівнювати порядки) але за рахунок втрати точності. Режим плаваючої коми дозволяє здійснювати більш точні розрахунки але при цьому час розв’язку задачі збільшується в порівнянні з фіксованою комою. Вибір режиму обчислень здійснюється на основі обмежень в (1), (2) на T і E . Наведемо оцінки похибок заокруглення алгоритмів розв’язання деяких найбільш поширених задач обчислювальної, прикладної математики та захисту інформації. 1. Оцінка середнього для нормального розподілу Нехай x – випадкова величина з областю значень  ,a b , ;a b    p x – щільність розподілу x . Математичним очікуванням або середнім значенням x називається число     b x a x M M x xp x dx    . ВИКОРИСТАННЯ ПОХИБКИ ЗАОКРУГЛЕННЯ В СУЧАСНИХ КОМП’ЮТЕРНИХ ТЕХНОЛОГІЯХ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 45 А. Оцінка в режимі off-line. Нехай в пам’яті комп’ютера є вибірка з N значень, які позначимо , 1,x N   . Зазвичай за оцінку x приймають вибіркове середнє  * * * 1 1 x N NS x M M x x N        . (1) Оцінимо похибку заокруглення при обчисленні на комп’ютері за формулою (1). Будемо при- пускати, що обчислення виконуються в режимі плаваючої коми з  розрядами у мантис чисел. При обчисленні на комп’ютері співвідношення (1) набуде вигляду:       1 1 1 : 1 N N NS x N x E N                 , де індекс  означає заміну відповідних операцій на псевдооперації з заокругленням результатів арифметичних операцій, а  1,06 2 2E N        , 2 0,1N   , 1, .N  Детермінована мажорантна оцінка похибки заокруглення має вигляд [1]:   2 1 1 1 1,06 1 1 1 1 1 2 23 N N N NS S x E x N N N N                       , 2 0,1.N   Б. Оцінка в режимі on-line. Нехай в пам’ять комп’ютера надходять наближені значення x випадкової величини x і потрібно отримати значення NS в темпі надходження , 1,x N   , з міні- мальною витратою пам’яті комп’ютера. Цього можна досягти застосуванням формули 1 1 ,i i i xi S S i i     1,i N , 0 0S  . (2) Для співвідношення (2) будемо мати з точністю до перших ступенів 2 [1]:     1 1 3 7 2 maxN N N S S N x        . 2. Розв’язання систем лінійних алгебраїчних рівнянь Наведемо зведення апріорних асимптотичних детермінованих і статистичних оцінок похибок заокруглення для основних прямих методів розв’язання систем лінійних алгебраїчних рівнянь n -го порядку Ax y , для яких матриця A має обернену матрицю 1A . Оцінки мають вигляд (в режимі плаваючої коми з  розрядами у мантис і з накопиченням суми парних добутків) [2]:    2 x x f n A x      і      1 12 2 2 2 2 2 x x M n M A x                     , де x – розв’язок, отриманий на комп’ютері, а   1 E E A A A  . В.К. ЗАДІРАКА, І.В. ШВІДЧЕНКО 46 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 Для методу Гаусса з вибором головного елемента по стовпцю    3 1f n q n  ,     1 22 1 3 n n         , 1 2nq  . Для методу відображень   3,35f n n ,     1 24 1 . 3 n n         Для методу квадратного кореня   1f n  ,   5 3 n  . Для методу обертань (оптимального виключення)   12f n n ,   1 2.n n  Для методу ортогоналізації (з процедурою доортогоналізації)   1f n  ,   1n  . Наведені співвідношення справедливі з урахуванням малих щодо першого порядку відносно 1 n і 2 . 3. Обчислення дискретного перетворення Фур’є Розглянемо задачу наближеного обчислення перетворення Фур’є фінітної з носієм  0,T функції  f t :     0 T i tF f t e dt    у випадку, коли  f t на  0,T задана в N точках рівномірної сітки . T t N        Застосувавши для наближеного обчислення  F  формулу прямокутників і використавши крок за частотою 2r r f   , 1 f T   (частота Найквіста), отримаємо:         21 0 N i rk N r N r k F F F r t f k e           ,    kf k f t . (3) Зробивши заміну 2 i N NW e    , отримаємо:     1 0 N rk N k F r t f k W      , 0, 1r N  . (4) Співвідношення (4) визначає дискретне перетворення Фур’є (ДПФ) функції  f t ,   , 0, 1F r r N  називаються коефіцієнтами ДПФ. У векторно-матричній формі співвідношення (4) має вигляд    rk NF r W f k           , (5) де  F r   и  f k   – вектор-стовпці  1N  , а rk NW    – квадратна матриця порядку  N N . ВИКОРИСТАННЯ ПОХИБКИ ЗАОКРУГЛЕННЯ В СУЧАСНИХ КОМП’ЮТЕРНИХ ТЕХНОЛОГІЯХ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 47 Як видно зі співвідношення (5) стандартний метод визначення вектору коефіцієнтів ДПФ вимагає 2N операцій комплексного множення і стільки ж операцій комплексного додавання (від- німання). Прискорений метод обчислення   , 0, 1F r r N     (швидкого перетворення Фур’є – ШПФ), який заснований на факторизації матриці , , 0, 1rk NW k r N      , потребує порядку 2logN N операцій комплексного додавання (віднімання) і порядку 2log 2 N N операцій комплексного множення. Порядок коефіцієнта прискорення 2log N N показує, що ми прискорюємося на кілька по- рядків. Це особливо важливо для задач великої розмірності і для забезпечення обробки інформації в режимі on-line. Можна вказати таке число 0N , що для 0N N кількість операцій алгоритму ШПФ становитиме лише 1% від кількості операцій стандартного методу. Цим пояснюється широкий спектр застосувань алгоритму ШПФ. Можна назвати класи задач, в яких алгоритм ШПФ «добре впровадився». Це цифрова обробка сигналів та зображень, прикладна статистика, аналіз сейсмограм землетрусів, ядерна спектроскопія, розв’язання крайових задач для рівнянь у частинних похідних, моделювання систем автоматичного регулювання та ін. Нас буде цікавити питання порівняльного аналізу стандартного алгоритму і ШПФ не тільки за складністю, а й за похибкою заокруглення. Нехай обчислення проводяться на комп’ютері в режимі з плаваючою комою з  двійковими розрядами у мантис чисел. Наведемо лему Дж.Х. Вілкінсона [3], яка нам знадобиться. Лема. Якщо A – дійсна  p q -матриця і B – дійсна  q r -матриця, а  fl  позначає резуль- тат обчислення виразу, що стоїть в дужках, то   1,06 2 E EE fl AB AB q A B      . На підставі цієї леми можна отримати наступні оцінки похибки заокруглення стандартного алгоритму і ШПФ: для стандартного методу   3 2 ε 2 E c N  , (6) для ШПФ при 1 2...N N N N    3 2 1 ε 2 ;jE i c N     (7) для ШПФ при 2N  ε 8 E c  , (8) де  ε fl F F  , 1,06 2 E c F   . Порівнюючи оцінку (6) з оцінками (7), (8), бачимо, що алгоритм ШПФ не тільки зменшує оці- нку складності задачі обчислення коефіцієнтів ДПФ, а й істотно зменшує оцінку похибки заокруг- лення. Не завжди зменшення кількості операцій веде до зменшення оцінки похибки заокруглення, але для алгоритму ШПФ це так. Наведемо оцінки ε E в припущенні, що елементи матриці W обчислені наближено:     1sin sinfl fl      ,    cos cosfl fl      , В.К. ЗАДІРАКА, І.В. ШВІДЧЕНКО 48 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 де 0  – абсолютна константа, 1 1   , 1 2  , обчислення ведуться в режимі з плаваючою комою. Константа  залежить від способу обчислення синусів і косинусів і їх аргументів і не за- лежить від вхідних даних. Оцінки при 1...N N N мають вигляд    2 1 1ε , ; E E k N O F            2 1 11 1 ε , E Nk N O F N          , де        1 , 1 3 2j j k N N           і   2jN  при 2jN  ,   5jN  при 4jN  ,    2j j jN N N    в інших випадках. Для алгоритмів ШПФ за основами 2 і 4      2 , 3 2 2 3 2k           і      4 , 8 2 3 2k          . У разі обчислення багатовимірного ДПФ:     1 2 1 1 2 2 1 2 1 2 1 2 , ,..., ... exp ... , ,..., m m m m m ms s s s ts t s t F t t t f s s s N N N             , де , 0, 1i i is t N  , 1,i m , наведемо оцінки похибок заокруглення алгоритму ШПФ. Нехай       1 1 2 1 2 1 2, ,..., , ,..., , ,...,m m mE t t t fl F t t t F t t t  ,   1 2 1 2 2 1 1 1 2... , ,..., m mE t t t E E t t t            ,   1 2 1 1 1 21 , ,..., max , ,..., m m t t t E E t t t . Тоді    2 1 1 1 1 , m iE E i E k N O F              ,         1 2 2 1 1 1 2 11 1 2 1 1 2 1 , ,... , . , ,... m m i E i m E N N N k N O F N N N             В роботі [5] для сигналу  f t у вигляді «білого» шуму при певних обмеженнях для рандо- мізованого правила заокруглення отримано наступний вираз для відношення дисперсії похибки заокруглення до дисперсії вектора ДПФ: 2 2 2 0,21 2 E F         . (9) При відсіченні результатів у правій частині (9) буде не лінійна залежність від , а квадратична. У разі детермінованого сигналу   1 2 f t  , рандомізованого правила заокруглення і обчислень в режимі фіксованої коми має місце наступна двостороння оцінка: ВИКОРИСТАННЯ ПОХИБКИ ЗАОКРУГЛЕННЯ В СУЧАСНИХ КОМП’ЮТЕРНИХ ТЕХНОЛОГІЯХ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 49   2 2 2 2 2 2 2,5 2 2 2 E F c k             , де   1 2 0 1 ; N t k f t N     0,3c  для заокруглення, 0,4c  для відсікання результатів операцій. 4. Використання багатозарядної арифметики Багаторозрядні числа – це числа, розрядність яких ( n бітів) перевищує довжину розрядного слова. Такі числа будемо ще називати багатослівними або s -слівними. Якщо n велике ( 1024n  біт), то виконання операцій вимагає істотних витрат машинного часу і виникає необхідність в оптимізації за швидкодією відповідних алгоритмів і програм. Галузь застосування таких ефективних алгоритмів – двоключова криптографія, високоточні обчислення, при розв’язанні задач трансобчислювальної складності, боротьба з накопиченням похибки заокруглення при отриманні ε -розв’язку задачі. Стійкість деяких алгоритмів двоключової криптографії тримається на використанні саме багаторозрядних чисел (не менше 2048 бітів на одне число). І чим більша розрядність чисел, тим стійкіший алгоритм, тому що тим більше ускладнюється розв’язання задач факторизації чисел або дискретного логарифмування. При шифруванні, розшифруванні, керуванні ключами, у криптографічних протоколах, високо- точних обчисленнях використовується операція піднесення до степеня, яка є найбільш складною. Операція піднесення до степеня виконується за допомогою операції множення та піднесення до квадрату. Оскільки операція множення – ключова, то на неї лягає основне навантаження в алгори- тмах двоключової криптографії. Тому зупинимось на оптимізації алгоритмів множення багато- розрядних чисел. Відомо, що стандартний алгоритм множення вимагає  2O n операцій для множення n -розрядних чисел. Більш якісні алгоритми можна отримати, використовуючи ідею Карацуби – Офмана та її рекурентного застосування, а також швидкі дискретні ортогональні перетворення [6]. Алгоритм Карацуби – Офмана потребує   2log 3O n операцій, метод многочленів – 1 εn  ,  ε > 0 , алгоритм Тоома – Кука –  22log 2 n O n  , алгоритм Шенхаге – Штрассена потребує  2logO n n операцій. Суттєво зменшити час виконання операції множення дозволяє використання алгоритмів обчислення добутку n -розрядних чисел за модулем за допомогою добутку Монтгомері та розробка швидких алгоритмів обчислення арифметичної згортки. Усі ці алгоритми базуються на ідеї зве- дення множення n -розрядних чисел до множення чисел з меншою розрядністю. С. Кук разом з С. Ондераа довели теорему про найкращу нижню границю, в якій стверджуєть- ся, що за певних обмежень не існує алгоритму, який би множив n -розрядні числа менше, ніж за   2 2 2 2 log log log n n O n         операцій. В роботі [7] доведена асимптотична ефективність алгоритму Шенхаге – Штрассена в порів- нянні з алгоритмом Карацуби – Офмана. А взагалі кожний алгоритм має область свого ефективного застосування і тому варто мати бібліотеку програм для обчислення добутку багаторозрядних чисел. Метод множення багаторозрядних чисел з використанням ШПФ базується на ідеї використан- ня теореми про дискретну згортку двох функцій. В.К. ЗАДІРАКА, І.В. ШВІДЧЕНКО 50 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 Оскільки при використанні ШПФ використовуються комплексні числа rk NW , то при множенні цілих чисел ми виходимо з поля цілих чисел в поле дійсних чисел і основна кількість операцій здійснюється в полі дійсних чисел. А результат – це ціле число. Тому нам треба коректно поверну- тися в поле цілих чисел. Оцінка похибки заокруглення має бути меншою 1 2 . Тоді отримаємо точний результат. Для цього необхідно визначити число  – кількість правильних значущих цифр, необхідних для наближеного обчислення NW  , і величин, отриманих на кожному кроці алгоритму ШПФ. Для цього і потрібні оцінки (7)–(9). Це саме «тонке» місце алгоритму Шенхаге – Шрассена і без урахування оцінок похибок цей алгоритм не «спрацює». Наведемо таблицю значень  для різних N ( 2N – розмір матриці ШПФ). ТАБЛИЦЯ. Таблиця значень  для різних N N 2 4 8 16 32 64 128 256 512  35 40 43 44 48 51 53 55 58 Багаторозрядну арифметику можна використовувати для отримання ε -розв’язків задач тран- собчислювальної складності. За Дж.Х. Вілкінсоном структура оцінок похибок заокруглення ε заокр має наступну структуру:  ε 2 ,заокр c N   (10) де  c N – деяка функція від кількості вхідної інформації. Наприклад, в оцінці (7)     3 2 1 1,06 2 .j E i c N N F      Якщо оцінка (10) нас не задовольняє, переходимо до використання s -слівних чисел. Тоді замість оцінки (10) будемо мати  ε 2 .s заокр c N    (11) Підбором s можна намагатись отримати ε -розв’язок задачі (зауважимо, що на ε впливає також похибка методу та неусувна похибка). Для задач трансобчислювальної складності ε заокр може бути «головним членом». Тому s може бути тим параметром, який дозволить перевести задачу з розряду нерозв’язаної у розв’язну. Оскільки мова йде і про багатопроцесорні комп’ютери, то актуальним є питання побу- дови ефективних за швидкодією алгоритмів обчислення криптопримітивів у паралельні моделі обчислень [8]. 5. Застосування оцінки похибки заокруглення в алгоритмах розв’язання задач комп’ю- терної стеганографії Стеганографія – один із шляхів підтримки інформаційної безпеки. Вона являє собою метод організації зв’язку, який приховує сам факт наявності таємних повідомлень. Стеганографічні методи активно використовуються для захисту інформації від несанкціонованого доступу, для протидії системам моніторингу та керування ресурсами мереж, для маскування програмного забезпечення від незареєстрованих користувачів, а також для захисту авторського права на деякі види інтелектуальної власності. Стеганографічна система – це сукупність засобів та методів, які використовуються для формування таємного каналу зв’язку. Будь-яка інформація, в якій приховані таємні дані, називається контейнером. Контейнер, який не містить таємного повідомлення, називають порожнім, а той, що містить – стеганоконтейнером. Канал передачі стеганоконтейнера ВИКОРИСТАННЯ ПОХИБКИ ЗАОКРУГЛЕННЯ В СУЧАСНИХ КОМП’ЮТЕРНИХ ТЕХНОЛОГІЯХ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 51 має назву стеганографічного каналу. Таємний ключ, який необхідний для «вкраплення» інформації в контейнер, називається стеганоключем. Задача стеганографічної системи – розмістити вхідне повідомлення в контейнері таким чином, щоб будь-яка стороння людина не змогла помітити нічого, крім його основного вмісту, навіть якщо застосує додаткову статистичну обробку стеганоконтейнера. Актуальною є задача побудови цифрових контейнерів. Найбільш стійкими до спотворень є спектральні методи побудови стеганоконтейнерів [9], які базуються на використанні дискретних ортогональних перетворень (дискретне косинус-перетворення, Фур’є, Уолша та інші). Не будемо заглиблюватись у теорію комп’ютерної стеганографії, а відмітимо, причому тут похибка заокруглення стеганоалгоритмів. В одному з спектральних алгоритмів, який використовує алгоритм ШПФ, будується спектр цифрового контейнера, визначаються участки спектру, які відповідають спектру шуму і в компо- ненти спектру шуму приховують таємне повідомлення, причому в такий спосіб, що використовує оцінку похибки заокруглення стеганоалгоритму. З оцінок похибок заокруглення визначається остання правильна цифра спектральної компоне- нти шуму і в неї починають «вкраплювати» таємне повідомлення. Потім береться інша спектраль- на компонента шуму і так далі, поки не «вкрапимо» все повідомлення. Стеганоключем при цьому буде номер останньої вірної цифри і номери спектральних компонент шуму, куди ми «вкрапили» таємне повідомлення. Стеганоключ треба передати одержувачу таємного повідомлення по таємно- му каналу зв’язку. Тепер щодо стійкості такого стеганолгоритму. Безумовно, «вкраплюючи» таємне повідомлен- ня, ми збурюємо наш контейнер (обернене ШПФ від спектрального стеганоконтейнера). Але вели- чина цього збурення буде на рівні похибки заокруглення стеганоалгоритму і стеганоаналітик не зможе дослідити – чи це контейнер, чи стеганоконтейнер. В цьому полягає стійкість стеганоалго- ритму. За визначенням, якщо нам вдається приховати таємну інформацію в шуми контейнера, то ми вже маємо стійкий стеганоалгоритм. У нашому випадку ми пішли далі – нам вдалося не тільки приховати таємну інформацію в спектральні компоненти шуму, а і зробити це з похибкою, яка зіс- тавлювана із похибкою заокруглення стеганоалгоритму. Завершимо тим, що визначення номеру останньої правильної цифри залежить від якості оцінок заокруглення [10]. Чим точніші оцінки, тим менше збурення ми внесемо в стеганоконтейнер і тим краще буде стійкість стеганоалгоритму. Висновки. Врахування похибки заокруглення – важливий фактор при оцінці точності набли- женого розв’язання задач складності вище середньої. Список літератури 1. Иванов В.В. Методы вычисления на ЭВМ: Справочное пособие. Киев: Наук. думка, 1986. 584 с. 2. Воеводин В.В. Ошибки округления и устойчивость в прямых методах линейной алгебры. М.: ВЦ МГУ, 1969. 154 с. 3. Уилкинсон Дж.Х. Алгебраическая проблема собственных чисел. М.: Наука, 1970. 564 с. 4. Ramos G.U. Roundoff error analysis of the fast Fourier transform. Mathematics of Computation. 1971. 25 (116). 757–768. https://www.ams.org/journals/mcom/1971-25-116/S0025-5718-1971-0300488-0/S0025-5718-1971-0300488-0.pdf 5. Weinstein C.J. Roundoff noise in floating point fast Fourier transform computation. IEEE Trans. Audio and Electroaconst. 1969. 19 (2). P. 209–215. 6. Задірака В.К., Олексюк О.С. Комп’ютерна арифметика багаторозрядних чисел. Наукове видання. К.: 2003. 264 с. 7. Задірака В.К., Мельникова С.С., Терещенко А.М. Про асимптотичну ефективність алгоритму Шенхаге- Штрассена. Праці міжнар. конф. «Питання оптимізації обчислень (ПОО-XXXII)», присвяч. 75-річчю від дня народження академіка В.С. Михалевича. К.: Ін-т кібернетики ім. В.М. Глушкова НАН України, 2005. С. 82–83. https://www.ams.org/journals/mcom/1971-25-116/S0025-5718-1971-0300488-0/S0025-5718-1971-0300488-0.pdf https://www.ams.org/journals/mcom/1971-25-116/S0025-5718-1971-0300488-0/S0025-5718-1971-0300488-0.pdf В.К. ЗАДІРАКА, І.В. ШВІДЧЕНКО 52 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 8. Задірака В.К., Терещенко А.М. Комп’ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. К.: Наук. думка, 2021. 136 с. 9. Задірака В.К., Мельнікова С.С., Бородавка Н.В. Спектральні алгоритми комп’ютерної стеганографії. Искусст- венный интеллект. 2002. 3. С. 532–541. http://iai.dn.ua/public/JournalAI_2002_3/Razdel4/11_Zadiraka_spektralni.pdf 10. Задирака В.К., Швидченко И.В. Влияние качества оценки погрешности округления стеганоалгоритма на его стойкость. Математичне та комп’ютерне моделювання. Серія: Фізико-математичні науки. 2015. 12. С. 101–112. http://dspace.nbuv.gov.ua/bitstream/handle/123456789/133865/10-Zadiraka.pdf?sequence=1 Одержано 22.06.2021 Задірака Валерій Костянтинович, доктор фізико-математичних наук, професор, академік НАН України, завідуючий відділом Інституту кібернетики імені В.М. Глушкова НАН України, Київ, https://orcid.org/0000-0001-9628-0454 zvk140@ukr.net Швідченко Інна Віталіївна, кандидат фізико-математичних наук, старший науковий співробітник, провідний науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України, Київ. https://orcid.org/0000-0002-5434-2845 inetsheva@gmail.com UDC 519.65 Valerii Zadiraka, Inna Shvidchenko * Using Rounding Errors in Modern Computer Technologies V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv * Correspondence: inetsheva@gmail.com Introduction. When solving problems of transcomputational complexity, the problem of evaluating the rounding error is relevant, since it can be dominant in evaluating the accuracy of solving the problem. The ways to reduce it are important, as are the reserves for optimizing the algorithms for solving the prob- lem in terms of accuracy. In this case, you need to take into account the rounding-off rules and calculation modes. The article shows how the estimates of the rounding error can be used in modern computer technologies for solving problems of computational, applied mathematics, as well as information security. The purpose of the article is to draw the attention of the specialists in computational and applied mathe- matics to the need to take into account the rounding error when analyzing the quality of the approximate solu- tion of problems. This is important for mathematical modeling problems, problems using Bigdata, digital signal and image processing, cybersecurity, and many others. The article demonstrates specific estimates of the rounding error for solving a number of problems: esti- mating the mathematical expectation, calculating the discrete Fourier transform, using multi-digit arithmetic and using the estimates of the rounding error in algorithms for solving computer steganography problems. The results. The estimates of the rounding error of the algorithms for solving the above-mentioned clas- ses of problems are given for different rounding-off rules and for different calculation modes. For the problem of constructing computer steganography, the use of the estimates of the rounding error in computer technologies for solving problems of hidden information transfer is shown. Conclusions. Taking into account the rounding error is an important factor in assessing the accuracy of the approximate solution of problems of the complexity above average. Keywords: rounding error, computer technology, discrete Fourier transform, multi-digit arithmetic, computer steganography. http://dspace.nbuv.gov.ua/bitstream/handle/123456789/133865/10-Zadiraka.pdf?sequence=1 mailto:inetsheva@gmail.com
id	nasplib_isofts_kiev_ua-123456789-181349
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	2707-4501
language	Ukrainian
last_indexed	2025-12-07T15:36:09Z
publishDate	2021
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Задірака, В.К. Швідченко, І.В. 2021-11-12T15:14:30Z 2021-11-12T15:14:30Z 2021 Використання похибки заокруглення в сучасних комп’ютерних технологіях / В.К. Задірака, І.В. Швідченко // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 3. — С. 43-52. — Бібліогр.: 10 назв. — укр. 2707-4501 DOI: https://doi.org/10.34229/2707-451X.21.3.4 https://nasplib.isofts.kiev.ua/handle/123456789/181349 519.65 Мета роботи. Звернути увагу фахівців з обчислювальної та прикладної математики на необхідність врахування похибки заокруглення при аналізі якості наближеного розв’язку задач. Це важливо для задач математичного моделювання, задач, які використовують Bigdata, цифрової обробки сигналів і зображень, кібербезпеки і багатьох інших. У статті продемонстровано конкретні оцінки похибки заокруглення для розв’язання ряду задач: оцінки математичного очікування, обчислення дискретного перетворення Фур’є, використання багаторазрядної арифметики і застосування оцінок похибки заокруглення в алгоритмах розв’язання задач комп’ютерної стеганографії. Результати. Наведено оцінки похибки заокруглення алгоритмів розв’язання вищеперерахованих класів задач при різних правилах заокруглення і для різних режимів обчислень. Для задач конструюючої комп’ютерної стеганографії показано використання оцінок похибки заокруглення в комп’ютерних технологіях розв’язання задач прихованої передачі інформації. Цель работы. Обратить внимание специалистов по вычислительной и прикладной математике на необходимость учета погрешности округления при анализе качества приближенного решения задач. Это важно для задач математического моделирования, задач, использующих Bigdata, цифровой обработки сигналов и изображений, кибербезопасности и многих других. В статье продемонстрированы конкретные оценки погрешности округления для решения ряда задач: оценки математического ожидания, вычисления дискретного преобразования Фурье, использования многоразрядной арифметики и применения оценок погрешности округления в алгоритмах решения задач компьютерной стеганографии. Результаты. Приведены оценки погрешности округления алгоритмов решения вышеперечисленных классов задач при разных правилах округления и для разных режимов вычислений. Для задачи конструирующей компьютерной стеганографии показано использование оценок погрешности округления в компьютерных технологиях решения задач скрытой передачи информации. The purpose of the article is to draw the attention of the specialists in computational and applied mathematics to the need to take into account the rounding error when analyzing the quality of the approximate solution of problems. This is important for mathematical modeling problems, problems using Bigdata, digital signal and image processing, cybersecurity, and many others. The article demonstrates specific estimates of the rounding error for solving a number of problems: estimating the mathematical expectation, calculating the discrete Fourier transform, using multi-digit arithmetic and using the estimates of the rounding error in algorithms for solving computer steganography problems. The results. The estimates of the rounding error of the algorithms for solving the above-mentioned classes of problems are given for different rounding-off rules and for different calculation modes. For the problem of constructing computer steganography, the use of the estimates of the rounding error in computer technologies for solving problems of hidden information transfer is shown. uk Інститут кібернетики ім. В.М. Глушкова НАН України Кібернетика та комп’ютерні технології Математичне моделювання та чисельні методи Використання похибки заокруглення в сучасних комп’ютерних технологіях Использование погрешности округления в современных компьютерных технологиях Using Rounding Errors in Modern Computer Technologies Article published earlier
spellingShingle	Використання похибки заокруглення в сучасних комп’ютерних технологіях Задірака, В.К. Швідченко, І.В. Математичне моделювання та чисельні методи
title	Використання похибки заокруглення в сучасних комп’ютерних технологіях
title_alt	Использование погрешности округления в современных компьютерных технологиях Using Rounding Errors in Modern Computer Technologies
title_full	Використання похибки заокруглення в сучасних комп’ютерних технологіях
title_fullStr	Використання похибки заокруглення в сучасних комп’ютерних технологіях
title_full_unstemmed	Використання похибки заокруглення в сучасних комп’ютерних технологіях
title_short	Використання похибки заокруглення в сучасних комп’ютерних технологіях
title_sort	використання похибки заокруглення в сучасних комп’ютерних технологіях
topic	Математичне моделювання та чисельні методи
topic_facet	Математичне моделювання та чисельні методи
url	https://nasplib.isofts.kiev.ua/handle/123456789/181349
work_keys_str_mv	AT zadírakavk vikoristannâpohibkizaokruglennâvsučasnihkompûternihtehnologíâh AT švídčenkoív vikoristannâpohibkizaokruglennâvsučasnihkompûternihtehnologíâh AT zadírakavk ispolʹzovaniepogrešnostiokrugleniâvsovremennyhkompʹûternyhtehnologiâh AT švídčenkoív ispolʹzovaniepogrešnostiokrugleniâvsovremennyhkompʹûternyhtehnologiâh AT zadírakavk usingroundingerrorsinmoderncomputertechnologies AT švídčenkoív usingroundingerrorsinmoderncomputertechnologies

Використання похибки заокруглення в сучасних комп’ютерних технологіях

Institution

Ähnliche Einträge