Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов
Выполнен анализ структурно-функциональной организации сетевой архитектуры параллельно-иерархического (ПИ) преобразования цифровых сигналов и методов формирования масок при его реализации. Предложен метод оптимизированного формирования масок при ПИ преобразовании для кодирования информации и разработ...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2013 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/100837 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов / Л.И. Тимченко, А.А. Яровой, Н.И. Кокряцкая // Электронное моделирование. — 2013. — Т. 35, № 2. — С. 35-54 . — Бібліогр.: 17 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859589865104998400 |
|---|---|
| author | Тимченко, Л.И. Яровой, А.А. Кокряцкая, Н.И. |
| author_facet | Тимченко, Л.И. Яровой, А.А. Кокряцкая, Н.И. |
| citation_txt | Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов / Л.И. Тимченко, А.А. Яровой, Н.И. Кокряцкая // Электронное моделирование. — 2013. — Т. 35, № 2. — С. 35-54 . — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Выполнен анализ структурно-функциональной организации сетевой архитектуры параллельно-иерархического (ПИ) преобразования цифровых сигналов и методов формирования масок при его реализации. Предложен метод оптимизированного формирования масок при ПИ преобразовании для кодирования информации и разработан программный комплекс, в котором повышено быстродействие прямого и обратного ПИ преобразования информации без ее потерь.
Виконано аналіз особливостей структурно-функціональної організації сітчастої архітектури паралельно-ієрархічного (ПІ) перетворення цифрових сигналів і методів формування масок при його реалізації. Запропоновано метод оптимізованого формування масок при ПІ перетворенні для кодування інформації та розроблено програмний комплекс, в якому підвищено швидкість прямого та зворотнього ПІ перетворення інформації без її втрат.
An analysis of structural-functional organization of the network architecture of parallel-hierarhical transformation and mask generation methods has been performed. The method of optimized forming of masks by encoding information in parallel-hierarchical transformation is proposed. The software package with high speed performance of lossless direct and reversal parallel-hierarhical transformation of information has been developed.
|
| first_indexed | 2025-11-27T13:58:32Z |
| format | Article |
| fulltext |
ÓÄÊ 681.3:004.272
Ë.È. Òèì÷åíêî
1
, ä-ð. òåõí. íàóê,
À.À. ßðîâîé
2
, Í.È. Êîêðÿöêàÿ
1
, êàíäèäàòû òåõí. íàóê,
1
Ãîñóäàðñòâåííûé ýêîíîìèêî-òåõíîëîãè÷åñêèé
óíèâåðñèòåò òðàíñïîðòà
(Óêðàèíà, 03049, Êèåâ, óë. Ëóêàøåâè÷à, 19,
òåë. (044) 5915135, e-mail: timchen@list.ru),
2
Âèííèöêèé íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò
(Óêðàèíà, 21021, Âèííèöà, Õìåëüíèöêîå øîññå, 95,
òåë. (0432) 598243, e-mail: axa@vinnitsa.com)
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ïàðàëëåëüíî-èåðàðõè÷åñêîãî ìíîãîóðîâíåâîãî
ïðåîáðàçîâàíèÿ öèôðîâûõ ñèãíàëîâ *
Âûïîëíåí àíàëèç ñòðóêòóðíî-ôóíêöèîíàëüíîé îðãàíèçàöèè ñåòåâîé àðõèòåêòóðû ïàðàë-
ëåëüíî-èåðàðõè÷åñêîãî (ÏÈ) ïðåîáðàçîâàíèÿ öèôðîâûõ ñèãíàëîâ è ìåòîäîâ ôîðìèðîâàíèÿ
ìàñîê ïðè åãî ðåàëèçàöèè. Ïðåäëîæåí ìåòîä îïòèìèçèðîâàííîãî ôîðìèðîâàíèÿ ìàñîê ïðè
ÏÈ ïðåîáðàçîâàíèè äëÿ êîäèðîâàíèÿ èíôîðìàöèè è ðàçðàáîòàí ïðîãðàììíûé êîìïëåêñ, â
êîòîðîì ïîâûøåíî áûñòðîäåéñòâèå ïðÿìîãî è îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ èíôîðìàöèè
áåç åå ïîòåðü.
Âèêîíàíî àíàë³ç îñîáëèâîñòåé ñòðóêòóðíî-ôóíêö³îíàëüíî¿ îðãàí³çàö³¿ ñ³ò÷àñòî¿ àðõ³òåêòóðè
ïàðàëåëüíî-³ºðàðõ³÷íîãî (ϲ) ïåðåòâîðåííÿ öèôðîâèõ ñèãíàë³â ³ ìåòîä³â ôîðìóâàííÿ ìàñîê
ïðè éîãî ðåàë³çàö³¿. Çàïðîïîíîâàíî ìåòîä îïòèì³çîâàíîãî ôîðìóâàííÿ ìàñîê ïðè ϲ ïå-
ðåòâîðåíí³ äëÿ êîäóâàííÿ ³íôîðìàö³¿ òà ðîçðîáëåíî ïðîãðàìíèé êîìïëåêñ, â ÿêîìó ï³ä-
âèùåíî øâèäê³ñòü ïðÿìîãî òà çâîðîòíüîãî ϲ ïåðåòâîðåííÿ ³íôîðìàö³¿ áåç ¿¿ âòðàò.
Ê ë þ ÷ å â û å ñ ë î â à: ïàðàëëåëüíûå âû÷èñëåíèÿ, ïàðàëëåëüíî-èåðàðõè÷åñêîå ïðåîáðàçî-
âàíèå, îáðàáîòêà èçîáðàæåíèé, êîäèðîâàíèå èíôîðìàöèè.
Ðåøåíèå ïðîáëåìû áûñòðîãî ïðåîáðàçîâàíèÿ áîëüøèõ ìàññèâîâ èíôîð-
ìàöèè — èçîáðàæåíèé äëÿ ýôôåêòèâíîãî îáåñïå÷åíèÿ åå çàïèñè, ñîõðàíå-
íèÿ, îáðàáîòêè è ñ÷èòûâàíèÿ — ñâÿçàíû ñ ñîçäàíèåì áûñòðîäåéñòâóþùèõ
óñòðîéñòâ êîäèðîâàíèÿ è äåêîäèðîâàíèÿ. Áûñòðîäåéñòâèå ïðîöåññà êîäè-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 35
* Äàííûå èññëåäîâàíèÿ âûïîëíåíû â ðàìêàõ ÍÈÐ ¹ GP/F44/051 «Ìåòîäû è ñðåäñòâà
îðãàíèçàöèè âûñîêîïðîèçâîäèòåëüíûõ ïàðàëëåëüíî-èåðàðõè÷åñêèõ âû÷èñëèòåëüíûõ
ïðîöåññîâ â èíòåëëåêòóàëüíûõ ñèñòåìàõ», êîòîðàÿ îñóùåñòâëÿåòñÿ çà ñ÷åò áþäæåòíûõ
ñðåäñòâ ÌÎÍÌÑ Óêðàèíû, ïðåäîñòàâëåííûõ êàê ãðàíò Ïðåçèäåíòà Óêðàèíû äëÿ ïîä-
äåðæêè íàó÷íûõ èññëåäîâàíèé ìîëîäûõ ó÷åíûõ.
� Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ, 2013
ÈÍÔÎÐÌÀÖÈÎÍÍÛÅ
ÒÅÕÍÎËÎÃÈÈ
ðîâàíèÿ-äåêîäèðîâàíèÿ ìàññèâîâ öèôðîâûõ äàííûõ çàâèñèò, ïðåæäå âñåãî,
îò ðåàëèçóåìîãî àëãîðèòìà öèôðîâîé îáðàáîòêè. Ñîâðåìåííûé óðîâåíü ðàç-
âèòèÿ ñõåìîòåõíèêè ìíîãîêàíàëüíûõ öèôðîâûõ óñòðîéñòâ êîäèðîâàíèÿ- äå-
êîäèðîâàíèÿ áîëüøèõ ìàññèâîâ èíôîðìàöèè âñå åùå õàðàêòåðèçóåòñÿ ïðå-
èìóùåñòâåííî ïîñëåäîâàòåëüíûìè àëãîðèòìàìè öèôðîâîé îáðàáîòêè ñ
ñóùåñòâåííûìè âðåìåííûìè çàòðàòàìè, êîòîðûå ñâÿçàíû ñ ïîñëåäîâàòåëü-
íûì âî âðåìåíè ïðîöåññîì êîäèðîâàíèÿ-äåêîäèðîâàíèÿ [1—4].
Óêàçàííàÿ ïðîáëåìà ñòàíîâèòñÿ íàèáîëåå àêòóàëüíîé â îáëàñòè êîäè-
ðîâàíèÿ èçîáðàæåíèé, ãäå öåëåñîîáðàçíî èñïîëüçîâàòü ïàðàëëåëüíóþ îáðà-
áîòêó.  îòëè÷èå îò øèðîêî ðàñïðîñòðàíåííûõ òèïîâ êîäèðîâàíèÿ âèäåî-
èíôîðìàöèè, íàïðèìåð ðàçíîñòíîé, êîäîâî-èìïóëüñíîé, äåëüòà-ìîäóëÿöèè,
â îñíîâó êîòîðûõ ïîëîæåí ïðèíöèï ïîñëåäîâàòåëüíîãî êîäèðîâàíèÿ ðàç-
íîñòíîé èíôîðìàöèè, ïðåäëàãàåòñÿ èñïîëüçîâàòü ïàðàëëåëüíî-ïèðàìèäàëü-
íûé ïðèíöèï îáðàáîòêè ðàñïðåäåëåííûõ â ïðîñòðàíñòâåííî-âðåìåííîé
îáëàñòè ðåçóëüòàòîâ êîäèðîâàíèÿ ìàññèâà äàííûõ, ÷òî ïðèâîäèò ê ñóùåñò-
âåííîìó ïîâûøåíèþ àëãîðèòìè÷åñêîãî áûñòðîäåéñòâèÿ, óïëîòíåíèþ ìàññè-
âîâ äàííûõ è îáåñïå÷åíèþ ïàðàëëåëüíî-èåðàðõè÷åñêîé (ÏÈ) ôîðìû îïèñà-
íèÿ ñèãíàëîâ (èçîáðàæåíèé) [5].
Ïîñòàíîâêà çàäà÷è.  ðàáîòàõ [6—9] ðàññìîòðåíû ïðèìåðû ìàòåìà-
òè÷åñêèõ ìîäåëåé ñåòåâîãî ìåòîäà ÏÈ ïðåîáðàçîâàíèÿ öèôðîâûõ ñèãíà-
ëîâ, à òàêæå íåêîòîðûå âîïðîñû èõ ïðèìåíåíèÿ. Äëÿ ðåøåíèÿ ïîñòàâëåí-
íîé çàäà÷è ïîâûøåíèÿ áûñòðîäåéñòâèÿ ïðÿìîãî è îáðàòíîãî ÏÈ ïðå-
îáðàçîâàíèÿ ñèãíàëîâ è îïòèìèçàöèè èçáûòî÷íîñòè ïðåäñòàâëåíèÿ ìàñîê
îïðåäåëèì àáñòðàêòíóþ ìîäåëü ñåòåâîé ñòðóêòóðû, ñïîñîáû ïðåäñòàâ-
ëåíèÿ ìàñîê äëÿ åå ðåàëèçàöèè è âûïîëíèì ýêñïåðèìåíòàëüíûå èññëåäî-
âàíèÿ ìíîãîóðîâíåâîãî ïðåîáðàçîâàíèÿ ìàñêèðîâàííûõ ñèãíàëîâ. Â êà-
÷åñòâå öèôðîâûõ ñèãíàëîâ èñïîëüçóåì ìàññèâû ÷èñëîâîé èíôîðìàöèè è
îòñ÷åòû ïîëóòîíîâûõ èçîáðàæåíèé.
Äëÿ îáîñíîâàíèÿ öåëåñîîáðàçíîñòè ïðèìåíåíèÿ â ïðèêëàäíûõ çàäà-
÷àõ êîäèðîâàíèÿ, îáðàáîòêè è ñðàâíåíèÿ èçîáðàæåíèé â õîäå ýêñïåðè-
ìåíòàëüíûõ èññëåäîâàíèé âûïîëíåíî êîìïüþòåðíîå ìîäåëèðîâàíèå, ðàç-
ðàáîòàí íàáîð äåìîíñòðàöèîííûõ ïðèëîæåíèé, êîòîðûå äàþò âîçìîæ-
íîñòü îöåíèòü äîñòîâåðíîñòü ðàáîòû ïðåäëîæåííîé ñåòåâîé ìîäåëè.
Îñíîâíûå ïîíÿòèÿ, îïðåäåëåíèÿ è àëãîðèòìû ñåòåâîé ìîäåëè ÏÈ
ìíîãîóðîâíåâîãî ïðåîáðàçîâàíèÿ ìàñêèðîâàííûõ ñèãíàëîâ. Èñïîëü-
çóåìûå â òåîðèè èíôîðìàöèîííûõ ñòðóêòóð è òåîðèè ãðàôîâ ëèíåéíûå
ñïèñêè è äåðåâüÿ [10] ÿâëÿþòñÿ ñòðóêòóðàìè ñ óïîðÿäî÷åííûìè ñâÿçÿìè.
Ïîýòîìó èíôîðìàöèÿ î ñòðóêòóðå ïðè èõ îïèñàíèè îïðåäåëÿåòñÿ òèïîì
ñâÿçåé ìåæäó ýëåìåíòàìè äàííûõ è ÿâëÿåòñÿ ñòðóêòóðîé ñ ãèáêîé èåðàð-
õèåé. Îäíèì èç ïóòåé ðåàëèçàöèè ïàðàëëåëèçìà ïðè ðàáîòå ñ ìíîãîñâÿç-
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
36 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
íûìè ñòðóêòóðàìè ÿâëÿåòñÿ ðåãóëÿðèçàöèÿ, îáåñïå÷èâàþùàÿ îïèñàíèå èõ
ñ ïîìîùüþ ðåãóëÿðíîé ñåòåâîé ñòðóêòóðû ïðåîáðàçîâàíèÿ. Ïðè ýòîì èí-
ôîðìàöèÿ î ñâÿçÿõ âêëþ÷àåòñÿ â ñåòåâóþ ñòðóêòóðó ïðåîáðàçîâàíèÿ â
ÿâíîì âèäå, ò.å. ïðåäñòàâëÿåòñÿ â âèäå ýëåìåíòîâ äàííûõ.
Ââåäåì íåêîòîðûå ïîíÿòèÿ, îòíîñÿùèåñÿ ê äðåâîâèäíîé ìîäåëè ñå-
òåâîé ñòðóêòóðû ÏÈ ïðåîáðàçîâàíèÿ ñ ðåãóëÿðíûìè ñâÿçÿìè [5]. Ïóñòü
ãðàô G V E� ( , ) — ñòðóêòóðà îáðàáîòêè äàííûõ, ñîñòîÿùàÿ èç ìíîæåñòâà
óçëîâ V è ìíîæåñòâà ðåáåð E. Ãðàô ÿâëÿåòñÿ íàïðàâëåííûì, åñëè ðåáðà
ïðåäñòàâëåíû â âèäå óïîðÿäî÷åííûõ ïàð óçëîâ. Äåðåâî ïðåîáðàçîâàíèÿ
îïðåäåëÿåòñÿ íàïðàâëåííûì ãðàôîì, îáëàäàþùèì ñëåäóþùèìè ñâîéñò-
âàìè: òîëüêî êîðíåâûå óçëû íå èìåþò âõîäÿùèõ â íèõ äóã, â êàæäûé
ïîñëåäóþùèé óçåë âõîäèò ìíîæåñòâî äóã, ÷èñëî êîòîðûõ îïðåäåëÿåòñÿ
ñòðóêòóðîé îáðàáàòûâàåìûõ äàííûõ.
Ñòðóêòóðà îáðàáîòêè äàííûõ îòîæäåñòâëÿåòñÿ ñ íàïðàâëåííûì ãðà-
ôîì, â êîòîðîì óçëàì ñîîòâåòñòâóþò ýëåìåíòû äàííûõ, à íàïðàâëåííûå
äóãè, ñâÿçûâàþùèå óçëû, îïèñûâàþò ðàçëè÷íûå çàâèñèìîñòè ìåæäó ýëå-
ìåíòàìè è ìàðêèðóþòñÿ ñîîòâåòñòâóþùèì îáðàçîì.
Ñòðóêòóðà îáðàáîòêè äàííûõ ìîäåëè ÏÈ ïðåîáðàçîâàíèÿ D K�{ , }�
îïðåäåëÿåòñÿ ìíîæåñòâîì K óçëîâ è ìíîæåñòâîì � �{ , ,...}f f1 2 ôóíêöèé
f Ki :
�1 è 1� K, êîòîðûå îòîáðàæàþò ìíîæåñòâî óçëîâ â îäèí óçåë è
íàîáîðîò. Äâà óçëà, K è �K , ñâÿçàíû äóãîé f i , åñëè � �K f Ki ( ).
Ñòðóêòóðà îáðàáîòêè äàííûõ D K�{ , }� , ïðè êîòîðîé ìíîæåñòâî óç-
ëîâ îòîáðàæàåòñÿ â îäèí óçåë, ò.å. K �1, à ôóíêöèÿ � îïðåäåëÿåòñÿ F*-
êðèòåðèåì, îáðàçóåò êîíâåðãåíòíóþ ñòðóêòóðó ïîääåðåâà.
Ñòðóêòóðà îáðàáîòêè äàííûõ D K* *{ , }� � , ïðè êîòîðîé îäèí óçåë
îòîáðàæàåòñÿ â ìíîæåñòâî óçëîâ K, ò.å. 1� K, à ôóíêöèÿ �* îïðåäåëÿåòñÿ
Q*-ôóíêöèåé ïðåîáðàçîâàíèÿ, îáðàçóåò äèâåðãåíòíóþ ñòðóêòóðó ïîä-
äåðåâà.
Èç ðàáîòû [5] ñëåäóåò, ÷òî èñïîëüçîâàíèå ÏÈ ïðåîáðàçîâàíèÿ äëÿ
ðàçëè÷íûõ çàäà÷ çàâèñèò îò âèäà êðèòåðèÿ, âûáîðà îáùåé ÷àñòè F * è
ñîîòâåòñòâóþùåãî åìó òèïà Q*-ïðåîáðàçîâàíèÿ.  îáùåì ñëó÷àå êðèòå-
ðèé âûáîðà îáùåé ÷àñòè ìîæåò èìåòü äèñêðèìèíàíòíûé (÷èñëîâîé), ðàñ-
ñìàòðèâàåìûé çäåñü, à òàêæå ñòðóêòóðíûé, ôèçè÷åñêèé è èíòåëëåêòóàëüíûé
ñìûñë. Áóäåì èññëåäîâàòü ðàçíîâèäíîñòè äèñêðèìèíàíòíîãî Q*-ïðåîáðà-
çîâàíèÿ, îñíîâû òåîðèè êîòîðîãî ÿâëÿþòñÿ îïðåäåëÿþùèìè äëÿ ñòðóêòóð-
íîãî, ôèçè÷åñêîãî è èíòåëëåêòóàëüíîãî Q*-ïðåîáðàçîâàíèé. Èç ïîëó÷åí-
íûõ ìàññèâîâ íà îñíîâå F *-êðèòåðèÿ è Q*-ïðåîáðàçîâàíèÿ ñôîðìèðóåì
íîâûé ìàññèâ.
Ïîëó÷åííûé ìàññèâ íàçîâåì ìàññèâîì âòîðîãî ïîðÿäêà è ïðåîáðà-
çóåì ïî òàêîìó æå àëãîðèòìó. Ýòîò ïðîöåññ ïðåîáðàçîâàíèÿ îïðåäåëèì
êàê ïðåîáðàçîâàíèå ïî âåðòèêàëè. Åñëè äëÿ ýòèõ ìàññèâîâ ïðèìåíèòü òîò
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 37
æå àëãîðèòì, òî ýòîò ïðîöåññ ïðåîáðàçîâàíèÿ ìàññèâîâ ìîæíî íàçâàòü
ïðåîáðàçîâàíèåì ïî ãîðèçîíòàëè. Ïîýòîìó âñå ïîëó÷åííûå òàêèì îáðàçîì
ìàññèâû ÿâëÿþòñÿ ìàññèâàìè ïåðâîãî ïîðÿäêà. Ìàññèâû ïåðâîãî ïîðÿäêà
ïðåîáðàçóþòñÿ äî òåõ ïîð, ïîêà ïîñëåäíèå íå ñòàíóò íóëåâûìè, îáðàçóÿ
ïðè ýòîì ìàññèâû âòîðîãî ïîðÿäêà.
Ìàññèâû âòîðîãî ïîðÿäêà òàêæå ïðåîáðàçóþòñÿ ïî êðèòåðèþ îáùåé
÷àñòè F * .  ðåçóëüòàòå îáðàáîòêè ìàññèâîâ âòîðîãî ïîðÿäêà ïîëó÷àåòñÿ
ìàññèâ òðåòüåãî ïîðÿäêà, êîòîðûé ïðåîáðàçóåòñÿ ïî îïèñàííîìó âûøå
àëãîðèòìó äëÿ ìàññèâà ïåðâîãî ïîðÿäêà. Òàêèì îáðàçîì, ìàññèâû êàæäîãî
ïîðÿäêà ïðåîáðàçóþòñÿ òàêæå ïî ãîðèçîíòàëè äî ïîëó÷åíèÿ íóëåâîãî
ìàññèâà. Ýòîò ïðîöåññ ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íå îáðàçóþòñÿ
íóëåâûå ìàññèâû ïî ãîðèçîíòàëè è íå ñôîðìèðóåòñÿ èñõîäíàÿ èíôîð-
ìàöèÿ äëÿ ïîñòðîåíèÿ íîâûõ ìàññèâîâ ïî âåðòèêàëè. Ìàññèâû, íàõîäÿ-
ùèåñÿ íà ðàçíûõ óðîâíÿõ, ñ òå÷åíèåì âðåìåíè ñàìè ïðåîáðàçóþòñÿ ïî
ãîðèçîíòàëè. Ýòîò ïðîöåññ íàçîâåì ýâîëþöèåé ìàññèâà, à ïðåîáðàçîâàíèå
Q* — îïåðàòîðîì ýâîëþöèè ìàññèâà.
Ñâîéñòâî 1. Ïîñëåäîâàòåëüíîå âî âðåìåíè ôîðìèðîâàíèå êîíâåð-
ãåíòíûõ K è äèâåðãåíòíûõ D ïîääåðåâüåâ îáðàçóåò K – D äåðåâî.
Ñâîéñòâî 2. Ñîñåäíèå K – D äåðåâüÿ îäíîãî óðîâíÿ ôèçè÷åñêè âî âðå-
ìåíè ñäâèíóòû îòíîñèòåëüíî äðóã äðóãà íà îäíî K è îäíî D ïîääåðåâüÿ.
Íåëèíåéíàÿ ñòðóêòóðà K – D äåðåâüåâ îáðàçóåò îáîáùåííîå äåðåâî ñåòè.
Ñå÷åíèÿìè îáîáùåííîãî äåðåâà ÿâëÿþòñÿ îäíîèìåííûå óçëû K è D
ïîääåðåâüåâ, èìåþùèõ îäèíàêîâûå ïóòè ê êîðíåâûì óçëàì.
Õâîñòîâûìè (ðåçóëüòèðóþùèìè) óçëàìè ÿâëÿþòñÿ îäèíî÷íûå óçëû K
ïîääåðåâüåâ îáîáùåííîãî äåðåâà ñåòåâîãî ïðåîáðàçîâàíèÿ, â ñå÷åíèÿõ
êîòîðîãî íàõîäèòñÿ îäèí óçåë K ïîääåðåâüåâ.
Ñåòåâîå äåðåâî — ýòî êîíå÷íîå ìíîæåñòâî K – D äåðåâüåâ, èç êîòîðûõ
ñîñåäíèå ïîääåðåâüÿ îäíîãî óðîâíÿ ñäâèíóòû âî âðåìåíè îäíî îòíîñè-
òåëüíî äðóãîãî íà K – D äåðåâî, à ÷èñëî ñå÷åíèé îïðåäåëÿåòñÿ ÷èñëîì
õâîñòîâûõ óçëîâ, ïîëîæåíèå êîòîðûõ â ïîñëåäîâàòåëüíîñòè ñå÷åíèé
èìååò âèä ( )2 3c � , ãäå c — íîìåð ñå÷åíèÿ, c �0 1, ,... .
Âåòâüþ ñåòåâîãî äåðåâà ÿâëÿåòñÿ ëþáîå ïðîèçâîëüíî ñôîðìèðîâàííîå
â ñîîòâåòñòâèè ñ ïðåäûäóùèì îïðåäåëåíèåì K – D äåðåâî.
Ñâîéñòâî 3. ×èñëî óðîâíåé ñåòåâîãî äåðåâà îïðåäåëÿåòñÿ ÷èñëîì åãî
õâîñòîâûõ óçëîâ, óâåëè÷åííûì íà åäèíèöó.
Óðîâíè îïðåäåëÿþòñÿ ïðîöåññàìè ýâîëþöèè ìàññèâîâ ïî ãîðèçîí-
òàëè è ïåðåõîäîì ê ýâîëþöèè ìàññèâîâ ïî âåðòèêàëè.
Ïðåäëàãàåìûé ñïîñîá ïàðàëëåëüíîãî ïðåîáðàçîâàíèÿ ñèãíàëîâ ðàñ-
ñìîòðèì ñ ïîìîùüþ ñåòåâîãî àëãîðèòìà [5, 7, 11], îñíîâíûå ñâîéñòâà
êîòîðîãî — ïàðàëëåëèçì è èåðàðõèÿ, ñèíõðîííîñòü è äåòåðìèíèðîâàí-
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
38 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
íîñòü. Ñåòü ñîñòîèò èç ìíîæåñòâà êîíå÷íûõ ìíîæåñòâ �, ìíîæåñòâà ýëå-
ìåíòîâ A è óñëîâíî ðàçáèòà íà ðÿä óðîâíåé.
Ñåòü ÏÈ ïðåîáðàçîâàíèÿ âêëþ÷àåò ñîâîêóïíîñòü ñëåäóþùèõ õàðàêòå-
ðèñòèê:
êîíå÷íîå ÷èñëî Ì ìíîæåñòâ íà u èåðàðõè÷åñêèõ óðîâíÿõ,
C A Q F M t M t M t M th ( , , , ) { ( ), ( ),..., ( ), ( )* *� 1
1
0 2
1
0
1
0 1
2
1 ,..., ( )}M tn
u
s ,
ãäå h — ÷èñëî èñõîäíûõ ìíîæåñòâ Ì, h
2; u — ïîðÿäêîâûé íîìåð óðîâíÿ,
u
2; n — ïîðÿäêîâûé íîìåð u-ãî óðîâíÿ, n
2; ts — òàêò èëè øàã, íà
êîòîðîì ñôîðìèðîâàëîñü ñîîòâåòñòâóþùåå ìíîæåñòâî íà u-ì óðîâíå, s
1;
t0 — ïåðâûé èëè íà÷àëüíûé òàêò, ãäå ôîðìèðóþòñÿ èñõîäíûå ìíîæåñòâà
ïåðâîãî óðîâíÿ;
êîíå÷íîå ìíîæåñòâî ýëåìåíòîâ
A a t a t a t a t a th n
u� �
�{ ( ), ( ), ..., ( ), ( ), ..., (1
1
1 2
1
1
1
1 1
1
3 s )},
ãäå �
u 2 — ïîðÿäêîâûé íîìåð óðîâíÿ; �
n 1 — ïîðÿäêîâûé íîìåð ìíî-
æåñòâà, êîòîðîìó ïðèíàäëåæèò ýëåìåíò; �ts — òàêò, íà êîòîðîì ôîðìè-
ðóåòñÿ ñîîòâåòñòâóþùèé ýëåìåíò.
Ìíîæåñòâà êîíå÷íûõ ìíîæåñòâ � è ìíîæåñòâà ýëåìåíòîâ A ïåðå-
ñåêàþòñÿ:
� � �� �
A M t a t a t a ti
j
s
j
s
j
s k
j
s, ( ) { ( ), ( ), ..., ( )}
1
1
2
1 1 ,
ãäå M ti
j
s( ) — èñõîäíîå ìíîæåñòâî äëÿ j-ãî óðîâíÿ.
Îáîçíà÷èì F* êðèòåðèé âûáîðà ýëåìåíòà èç ìíîæåñòâà a ti
j
s( ) �
�
F M ti
j
s
* [ ( )]1 (ïåðåõîä îò ìíîæåñòâà M ti
j
s( )
1 ê ýëåìåíòó a ti
j
s( )) è Q* —
ôóíêöèþ ïðåîáðàçîâàíèÿ ìíîæåñòâà, Q M t M t
a t i
j
s s
i
j
s( )
* [ ( )] ( )
��1 1 (ïåðåõîä
îò ýëåìåíòà a ti
j
s( ) ê ìíîæåñòâó M ts( )�1 ).
Ìîùíîñòü èñõîäíûõ ìíîæåñòâ M ti
1
0( )îáîçíà÷èì m, à èõ ÷èñëî — H:
M t a a a m1
1
0 11 12 1( ) { , , ..., }� ;
M t a a a m2
1
0 21 22 2( ) { , , ..., }� , ..., M t a a ah h h hm
1
0 1 2( ) { , ,..., }� .
Êàæäîå èç ýòèõ ìíîæåñòâ ïðåîáðàçóåòñÿ ïî åäèíîìó ñåòåâîìó àëãîðèòìó,
à âñå ìíîæåñòâà îòðàáàòûâàþòñÿ ïàðàëëåëüíî. Èç ìíîæåñòâà ̳ âûáèðàåò-
ñÿ îäèí ýëåìåíò ài è ýëåìåíò a t ai i
1
1( ) � ÿâëÿåòñÿ ýëåìåíòîì ñåòè C.
Ýëåìåíò ai èç ìíîæåñòâà Ì âûáèðàåòñÿ ïî F*-êðèòåðèþ, ò.å. a F Mi � * ( ),
a Mi . Ñ ó÷åòîì ýòîãî âûáðàííîãî ýëåìåíòà âûïîëíÿåòñÿ ïðåîáðàçîâàíèå
äàííîãî ìíîæåñòâà, â ðåçóëüòàòå ÷åãî ôîðìèðóåòñÿ íîâîå ìíîæåñòâî òîé
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 39
æå ìîùíîñòè, â êîòîðîì âñå ýëåìåíòû, ðàâíûå âûáðàííîìó (åñëè òàêèå
èìåþòñÿ), îïðåäåëåííûì îáðàçîì îòìå÷åíû, íàïðèìåð îáíóëåíû. Eñëè
ñôîðìèðóåòñÿ ìíîæåñòâî a a a a ai i i i im1 2 4 70 0 0 0, , , , , , , ..., , , òî ïîÿâèòñÿ ýëå-
ìåíò a t a a a a ai i i i ij im
1
1 3 5 6 1( ) � � � � �
. Òàêàÿ îïåðàöèÿ íàçûâàåòñÿ Q*-ïðå-
îáðàçîâàíèåì. Q*-ïðåîáðàçîâàíèå ìíîæåñòâà M ai�{ }, ñ ó÷åòîì âûáðàííîãî
ýëåìåíòà a Mi , îïðåäåëèì êàê ïðåîáðàçîâàíèå, â ðåçóëüòàòå êîòîðîãî
ôîðìèðóåòñÿ íîâîå ìíîæåñòâî òîé æå ìîùíîñòè, âñå ýëåìåíòû êîòîðîãî,
ðàâíûå ai , è ñàì ýòîò ýëåìåíò èìååò âèä Q M Mai
* ( ) � �.
Äàëåå, èç âíîâü ïîëó÷åííîãî ìíîæåñòâà âûáèðàåòñÿ ïî F*-êðèòåðèþ
ñëåäóþùèé ýëåìåíò, aij1
, a t aj ij
1
3 1
( ) � (a aij ij1
� ), è âûïîëíÿåòñÿ Q*-ïðåîá-
ðàçîâàíèå. Â ðåçóëüòàòå ôîðìèðóåòñÿ ìíîæåñòâî, â êîòîðîì âñå ýëåìåíòû,
ðàâíûå aij1
, îòìå÷åíû. Èòåðàöèîííîå ïðåîáðàçîâàíèå âûïîëíÿåòñÿ äî òåõ
ïîð, ïîêà âñå ýëåìåíòû èñõîäíîãî ìíîæåñòâà íå áóäóò îòìå÷åíû. Òàêîå
ìíîæåñòâî îïðåäåëÿåòñÿ êàê íóëåâîå, è äàëüíåéøåå åãî ïðåîáðàçîâàíèå
íå âûïîëíÿåòñÿ.
Íóëåâûì ìíîæåñòâîì íàçûâàåòñÿ òàêîå ìíîæåñòâî, âñå ýëåìåíòû êî-
òîðîãî â ðåçóëüòàòå Q*-ïðåîáðàçîâàíèÿ îòìå÷åíû.
Ïðîöåññ ïðåîáðàçîâàíèÿ â íóëåâîå ìíîæåñòâî íàçîâåì ïðîöåññîì
ñõîäèìîñòè. Î÷åâèäíî, ÷åì ìåíüøå òàêòîâ âûáîðêè íåîáõîäèìî îñóùåñò-
âèòü äî ôîðìèðîâàíèÿ íóëåâîãî ìíîæåñòâà, òåì ëó÷øå ñõîäèìîñòü äàí-
íîãî ïðîöåññà. Òàêîé âèä ïðåîáðàçîâàíèÿ íàçîâåì ãîðèçîíòàëüíûì, èëè
ïðåîáðàçîâàíèåì âåòâè.
Ïîñëåäîâàòåëüíîñòü øàãîâ ïðåîáðàçîâàíèÿ èñõîäíîãî ìíîæåñòâà ñ
ó÷åòîì ïðîìåæóòî÷íûõ ðåçóëüòàòîâ äî ïîëó÷åíèÿ íóëåâîãî ìíîæåñòâà
íàçûâàåòñÿ âåòâüþ.
Ðàññìàòðèâàÿ âñå Í èñõîäíûõ ìíîæåñòâ ïåðâîãî óðîâíÿ, ïðè âûáîðå
ýëåìåíòà a tj j
1 ( ), i h�{ , ,..., }1 2 , j �{ , , ,...}1 3 5 , èç êàæäîãî ìíîæåñòâà ôîðìèðóåì
íîâûå ìíîæåñòâà, ãäå ³ — ïîðÿäêîâûé íîìåð èñõîäíîãî ìíîæåñòâà; tj —
òàêò, â êîòîðîì âûáðàí ýëåìåíò. Ïðè ïåðâîì âûáîðå ýëåìåíòîâ èç H
âõîäíûõ ìíîæåñòâ â òàêòå t1 ôîðìèðóåòñÿ íîâîå ìíîæåñòâî
M t a t a t a t a th1
2
1 1
1
1 2
1
1 3
1
1
1
1( ) { ( ), ( ), ( ), ..., ( )}� .
Íà âòîðîì øàãå ïðåîáðàçîâàíèÿ t3 èç èñõîäíûõ ìíîæåñòâ ôîðìèðóåòñÿ
åùå îäíî ìíîæåñòâî èç H ýëåìåíòîâ:
M t a t a t a th2
2
3 1
1
3 2
1
3
1
3( ) { ( ), ( ),..., ( )}� .
Òàêîå ïðåîáðàçîâàíèå âûïîëíÿåòñÿ äî òåõ ïîð, ïîêà âñå èñõîäíûå ìíî-
æåñòâà íå ñòàíóò íóëåâûìè.
Ìíîæåñòâà M t M t M ti j1
2
1 2
2
3
2( ), ( ),..., ( ) ÿâëÿþòñÿ èñõîäíûìè ìíîæåñò-
âàìè âòîðîãî óðîâíÿ. Èõ òàêæå áóäåì ïðåîáðàçîâûâàòü ïî ñåòåâîìó àëãî-
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
40 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
ðèòìó äî ïîëíîé ñõîäèìîñòè. Òîãäà ïðåîáðàçîâàíèå, âûïîëíÿåìîå íà
ïåðâîì óðîâíå H èñõîäíûõ ìíîæåñòâ, ýëåìåíòàìè êîòîðûõ ÿâëÿþòñÿ ýëå-
ìåíòû ïåðâîãî óðîâíÿ, áóäåì ñ÷èòàòü âòîðûì óðîâíåì.
Ïðè ïðåîáðàçîâàíèè ìíîæåñòâ âòîðîãî óðîâíÿ ôîðìèðóþòñÿ ýëåìåí-
òû, ñîçäàþùèå èñõîäíûå ìíîæåñòâà äëÿ òðåòüåãî óðîâíÿ è òàê äàëåå, äî
k-ãî óðîâíÿ, íà êîòîðîì ýëåìåíòû óæå íå ñîçäàþò íîâîå ìíîæåñòâî. Âñå
ïðåîáðàçîâàíèÿ ïðîèñõîäÿò ïî òàêòàì t³, ³ = 1, 2, 3, ... . Â êàæäîì òàêòå
äëÿ ëþáîãî óðîâíÿ ïðîèñõîäèò âûáîð ýëåìåíòîâ èç ìíîæåñòâ ïî
F*-êðèòåðèþ èëè Q*-ïðåîáðàçîâàíèå ìíîæåñòâ â ñîîòâåòñòâèè ñ ðàíåå
âûáðàííûìè ýëåìåíòàìè, ÷òî ñâèäåòåëüñòâóåò î ñâîéñòâå ñèíõðîííîñ-
òè äàííîé ñåòè.
Ñòðóêòóðà ñåòåâîãî àëãîðèòìà, ïðåäñòàâëÿþùàÿ ñîáîé ñîâîêóïíîñòü
ìíîæåñòâ M tj
i
k( ) è ýëåìåíòîâ a tj
i
k( )�1 , ïðèâåäåíà íà ðèñ. 1. Îðèåíòè-
ðîâàííûå äóãè ñîåäèíÿþò ìíîæåñòâà è ýëåìåíòû, ïðè ýòîì íåêîòîðûå
äóãè íàïðàâëåíû îò ìíîæåñòâ M tj
i
k( ) ê ýëåìåíòàì a tj
i
k( )�1 , à äðóãèå — îò
ýëåìåíòîâ ê ìíîæåñòâàì. Äóãà, íàïðàâëåííàÿ îò ìíîæåñòâà M tj
i
k( ) ê ýëå-
ìåíòó a tj
i
k( )�1 , îïðåäåëÿåò F*-êðèòåðèé âûáîðà ýëåìåíòà, à äóãà, íàïðàâ-
ëåííàÿ îò ýëåìåíòà a tj
i
k( )�1 ê ìíîæåñòâó M tj
i
k( )�2 , óêàçûâàåò íà Q*-ïðå-
îáðàçîâàíèå ìíîæåñòâà. Äóãè ÿâëÿþòñÿ íàïðàâëåííûìè, ñëåäîâàòåëüíî,
ýòî îðèåíòèðîâàííûé ãðàô ñ íóëåâûì ìíîæåñòâîì M ts2
1( ).
Êàæäûé ýëåìåíò, îáîçíà÷åííûé íà ðèñ.1 çíàêîì �� íå âõîäèò íè â
îäíî ìíîæåñòâî, òàê êàê â äàííîì òàêòå äëÿ ñâîåãî óðîâíÿ âûáðàí åäèíñò-
âåííûì, íå ó÷àñòâóåò â äàëüíåéøåé îáðàáîòêå ìàññèâîâ è ÿâëÿåòñÿ åå
ðåçóëüòàòîì. Òàêèå ýëåìåíòû íàçîâåì õâîñòîâûìè, èëè ýëåìåíòàìè, ôîð-
ìèðóþùèìè ðåçóëüòàò.
Ïðè Q*-ïðåîáðàçîâàíèè ìíîæåñòâ, ìîãóò áûòü îòìå÷åíû, íàïðèìåð,
ðàâíûå ýëåìåíòû. Âûäåëèì èíôîðìàöèþ îáî âñåõ ðàâíûõ ýëåìåíòàõ è èõ
ðàñïîëîæåíèè âî ìíîæåñòâå. Äëÿ ýòîãî êàæäîìó Q*-ïðåîáðàçîâàíèþ ìíî-
æåñòâà íåîáõîäèìî ïîñòàâèòü â ñîîòâåòñòâèå äâîè÷íûé êîä, â êîòîðîì
åäèíèöû íàõîäÿòñÿ â ðàçðÿäàõ, ñîîòâåòñòâóþùèõ ïîçèöèÿì ðàâíûõ ýëå-
ìåíòîâ â ìíîæåñòâå. Âñå îñòàëüíûå ðàçðÿäû êîäà, ñîîòâåòñòâóþùèå äðó-
ãèì ýëåìåíòàì ìíîæåñòâà, çàïîëíÿþòñÿ íóëÿìè.
Ïîä òåíåâîé ìàñêîé (äàëåå ïðîñòî ìàñêà) Q*-ïðåîáðàçîâàíèÿ ìíî-
æåñòâà áóäåì ïîíèìàòü äâîè÷íûé êîä, ðàçðÿäíîñòü êîòîðîãî ðàâíà ìîù-
íîñòè ìíîæåñòâà, à åäèíèöû íàõîäÿòñÿ â ðàçðÿäàõ êîäà, ñîîòâåòñòâóþùèõ
ìåñòîíàõîæäåíèþ îòìå÷åííûõ íà äàííîì øàãå ýëåìåíòîâ ìíîæåñòâà.
Òàêèå ìàñêè ôîðìèðóþòñÿ äëÿ âñåõ ïðîìåæóòî÷íûõ è íóëåâûõ ìíîæåñòâ
âî âñåõ âåòâÿõ è íà âñåõ óðîâíÿõ.
Áëîê-ñõåìû ðåàëèçóåìûõ àëãîðèòìîâ öèôðîâîé îáðàáîòêè ñèãíàëîâ,
ñîîòâåòñòâóþùèå ïðÿìîìó è îáðàòíîìó ÏÈ ïðåîáðàçîâàíèÿì, ïðåäñòàâ-
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 41
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
42 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
a1
3 (t7)
4
a2
3(t7)
a
2
a2
1
(t7 )
a h
1
(t7)
a
2
a2
1
(t5 )
a h
1
(t5)
a
2
a2
1
(t3 )
a h
1
(t3)
a
2
a2
1
(t1 )
ah
1
(t1)
t0
1
M2
1
(t
0
)
1
M
1
Mh
1
(t)
M2
1
(t2)
Mh
1
(t2)
t1 t2
M M
M2
1
(t4)
M h
1
(t4)
t3 t4
M M
M2
1
(t6)
Mh
1
(t6)
t5 t6
M M
M2
1
(t8)
Mh
1
(t8)
t7 t8
M M
ts
0
M2
1
(ts)a2
1
(t s1)
a
1
2(t4)
3
a2
2
(t4 )
M1
2
(t5)
M2
2
(t5)
a
1
2
(t6)
3
a2
2
(t6 )
a3
2
(t6)
M2
2
(t
6
) M1
2
(t7)
M 2
2
(t7)
M3
2
(t7)
a1
2
(t8)
3
a2
2
(t8)
a3
2
(t8 )
a4
2
(t8 )
a1
2
(t2)
M1
2
(t3) M1
2
(t4)
0
M1
3
(t6)
M3
2
(t8)
Âåòâü 3
Âåòâü 4
Ì
Ì
Ì
Ì
ÌÌ
Âåòâü 1
Âåòâü 1
Âåòâü 2
Âåòâü 2
a1
3
(t5)
a1
4
(t8)
Óðîâåíü 1
Óðîâåíü 2
Óðîâåíü 3
Óðîâåíü 4
Óðîâåíü 5
�
�
�
�
Ðèñ. 1. Ñòðóêòóðíàÿ ñõåìà îðãàíèçàöèè ÏÈ ñåòè: 1—4 â âåðòèêàëüíûõ ïðÿìîóãîëüíèêàõ —
èñõîäíûå ìíîæåñòâà G-ïðåîáðàçîâàíèÿ äëÿ ôîðìèðîâàíèÿ âåòâåé ÏÈ ñåòè; ãîðèçîí-
òàëüíûå ïðÿìîóãîëüíèêè — ïðîìåæóòî÷íûå ìíîæåñòâà (ðåçóëüòàò Q*-ïðåîáðàçîâà-
íèÿ); — ýëåìåíòû; � — ýëåìåíòû a t a t a t1
2
2 1
3
5 1
4
8( ), ( ), ( ) ; 0 — íóëåâîå ìíîæåñòâî
ëåíû íà ðèñ. 2, à è á. Êàê âèäíî èç ðèñ. 2, á, â áëîêàõ 2 è 3 ïðåîáðàçîâàíèÿ
ïðîèñõîäÿò ïàðàëëåëüíî ïî âñåì óðîâíÿì. Åñëè âî âñåõ ÷åòíûõ óðîâíÿõ
âûïîëíÿåòñÿ îïåðàöèÿ âûáîðà ïî F *-êðèòåðèþ, òî âî âñåõ íå÷åòíûõ óðîâ-
íÿõ îñóùåñòâëÿåòñÿ Q*-ïðåîáðàçîâàíèå, è íàîáîðîò. Â áëîêå 4 àíàëèçèðóåòñÿ
íàëè÷èå îäèíàêîâûõ ýëåìåíòîâ, èëè ýëåìåíòîâ ïîñëåäóþùèõ óðîâíåé íà
âñåõ óðîâíÿõ. Íà îäíèõ óðîâíÿõ íà äàííîì øàãå àëãîðèòìà òàêèå ýëåìåíòû
ìîãóò áûòü, à íà äðóãèõ óðîâíÿõ — îòñóòñòâîâàòü. Ïîýòîìó èç áëîêà 4
âîçìîæåí âûõîä ïî äâóì íàïðàâëåíèÿì îäíîâðåìåííî, ÷òî ñëåäóåò îáÿçà-
òåëüíî ó÷èòûâàòü ïðè èñïîëüçîâàíèè äàííîãî àëãîðèòìà.
Äëÿ àëãîðèòìîâ öèôðîâîé îáðàáîòêè ñèãíàëîâ ïðèâåäåííàÿ àáñòðàêò-
íàÿ ÏÈ ìîäåëü ÿâëÿåòñÿ óíèâåðñàëüíîé. Äîêàçàòåëüñòâîì ýòîãî óòâåðæ-
äåíèÿ ìîãóò áûòü ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé ïàðàë-
ëåëüíîé îáðàáîòêè äëÿ ÏÈ ïðåîáðàçîâàíèÿ íå òîëüêî ñèãíàëîâ, íî è
èçîáðàæåíèé ïðè ðåàëèçàöèè íà ðàçëè÷íûõ íàáîðàõ äàííûõ: â âèäå äâó-
ìåðíîé ìàòðèöû äàííûõ ðàçíîé ðàçìåðíîñòè, à òàêæå ïÿòíîïîäîáíûõ
èçîáðàæåíèé ïðîôèëÿ ëàçåðíîãî ëó÷à ðàçíîé ðàçìåðíîñòè [5—9].
Òàêèì îáðàçîì, ñóòü ÏÈ ìåòîäà çàêëþ÷àåòñÿ â îäíîâðåìåííîì èñïîëü-
çîâàíèè ïîñëåäîâàòåëüíîñòè ìíîæåñòâ ìàññèâîâ èíôîðìàöèè, îáðàçóþùèõ
ìíîæåñòâà èíôîðìàöèîííûõ ïîëåé íà ðàçëè÷íûõ óðîâíÿõ èåðàðõèè, è ðå-
êóðñèâíîì ôîðìèðîâàíèè íîâûõ ïîñëåäîâàòåëüíîñòåé èíôîðìàöèîííûõ ïî-
òîêîâ íà ðàçëè÷íûõ óðîâíÿõ èåðàðõèè, ÷òî ïîçâîëÿåò ðåàëèçîâàòü ñòðàòåãèþ
ìíîãîóðîâíåâîãî âçàèìîäåéñòâèÿ îò îáùåãî ê ÷àñòíîìó.
Ïðåäëîæåííûé ïðîöåññ îáðàáîòêè ÿâëÿåòñÿ ïèðàìèäàëüíûì. Äåéñò-
âèòåëüíî, â ïðîöåññå îáðàáîòêè ÷èñëîâîé èíôîðìàöèè ñ êàæäûì øàãîì
G-ïðåîáðàçîâàíèÿ, ðåàëèçóåìîãî â êàæäîé âåòâè [5], êîëè÷åñòâî ÷èñåë
óìåíüøàåòñÿ. Åñëè ìíîæåñòâà, ïîëó÷àåìûå ïîñëå êàæäîãî øàãà, ïîñòà-
âèòü ïîñëåäîâàòåëüíî îäíî íà äðóãîå, òî îáðàçóåìûé èìè òðåõìåðíûé
êîíòóð áóäåò èìåòü ôîðìó ïèðàìèäû.
Ðàññìîòðèì ïðèìåð ïèðàìèäàëüíîãî ïðîöåññà îáðàáîòêè èíôîðìà-
öèè â êàæäîé âåòâè íà îñíîâå G-ïðåîáðàçîâàíèÿ (òàáë. 1). Ïóñòü âõîäíîå
ìíîæåñòâî åñòü M = {2, 3, 5, 7, 4, 5, 4, 4}. Ñóììà âõîäíîé ÷èñëîâîé
èíôîðìàöèè ai
i�
� �
1
8
34 . Íà êàæäîì øàãå (ñòóïåíè ïèðàìèäû) íàõîäèòñÿ
ìèíèìàëüíîå ÷èñëî. Âû÷èòàåì åãî èç êàæäîãî ÷èñëà âõîäíîãî ìîæåñòâà
÷èñåë, îïðåäåëÿÿ ïðîìåæóòî÷íûå ðåçóëüòàòû: a a N1 � �min , ãäå N — ÷èñëî
íåíóëåâûõ ýëåìåíòîâ.
Ïèðàìèäàëüíàÿ âû÷èñëèòåëüíàÿ ñòðóêòóðà íà îñíîâå ÏÈ ïðåîáðàçî-
âàíèÿ îáðàçóåò ñåòü â âèäå ÏÈ ïèðàìèäû (ðèñ. 3). Äëÿ êàæäîé ïèðàìèäû
èñïîëüçóåòñÿ ñâîé ïðîöåññîðíûé ýëåìåíò (ÏÝ), à ÷èñëî ÏÝ îïðåäåëÿåòñÿ
ñóììàðíûì ÷èñëîì âåòâåé ÏÈ ñåòè.
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 43
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
44 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
Í
à÷
àë
î
Ô
î
ð
ì
è
ð
î
â
àí
è
å
ï
àê
åò
à
è
ñõ
î
ä
í
û
õ
ì
àñ
ñè
â
î
â
Â
û
á
î
ð
ï
î
ýë
åì
åí
òî
â
â
ñ
åõ
ì
àñ
ñè
â
î
â
ñî
î
òâ
åò
ñò
âó
þ
ù
è
õ
ó
ð
î
â
í
åé
F
* -
ê
ð
è
òå
ð
è
þ
Â
û
á
î
ð
ï
î
â
ñ
åõ
ì
àñ
ñè
â
î
â
ñî
î
òâ
åò
ñò
âó
þ
ù
è
õ
ó
ð
î
â
í
åé
Q
*
ê
ð
è
òå
ð
è
þ
-
Ï
î
â
ñ
åì
ó
ð
î
â
í
ÿ
ì
.
Â
û
á
ð
àí
í
û
õ
ýë
åì
åí
òî
â
á
î
ë
ü
ø
å
î
ä
í
î
ãî
?
Ô
î
ð
ì
è
ð
î
â
àí
è
å
â
ð
å
çó
ë
üò
àò
ì
àñ
î
ê
è
è
õ
â
û
â
î
ä
Ô
î
ð
ì
è
ð
î
â
àí
è
å
ì
àñ
ñè
â
î
â
ä
ë
ÿ
ñë
åä
ó
þ
ù
è
õ
ó
ð
î
â
í
åé Å
ñò
ü
í
å
-
ó
ð
î
â
í
å?
í
ó
ë
åâ
î
é
ì
àñ
ñè
â
í
à
ê
àê
î
ì
ë
è
á
î
Ï
î
â
ñ
åì
ó
ð
î
â
í
ÿ
ì
Ï
åð
â
û
é
ýë
åì
åí
ò
ï
åð
â
î
é
â
åò
â
è
?
.
Ï
åð
åí
î
ñ
î
ä
è
í
î
÷
í
û
õ
ýë
åì
åí
òî
â
í
à
ñë
åä
ó
þ
ù
è
å
ó
ð
î
â
í
è
Â
û
â
î
ä
î
ä
è
í
î
÷
í
î
ãî
ýë
åì
åí
òà
â
ð
å
çó
ë
üò
àò
Ê
î
í
åö
0
0
0
1
1
1
Í
à÷
àë
î
Â
û
á
î
ð
ýë
åì
åí
òî
â
ï
î
â
ñ
åì
ó
ð
î
â
í
ÿ
ì
Â
û
á
î
ð
ì
àñ
î
ê
ýë
åì
åí
òî
â
ï
î
â
ñ
åì
ó
ð
î
â
í
ÿ
ì
Q
*
ï
î
â
ñ
åì
ó
ð
î
â
í
ÿ
ì
ì
àñ
ñè
â
î
â
-ï
ð
åî
á
ð
àç
î
â
àí
è
å
Å
ñò
ü òû
è
ë
è
ýë
åì
åí
òû
ñ
ï
î
ñë
åä
ó
þ
ù
è
õ
ó
ð
î
â
í
åé
?
ýë
åì
åí
î
ä
è
í
î
÷
í
û
å
Ï
åð
åí
î
ñ
ì
àñ
ñè
â
î
â
í
à
ï
ð
åä
û
ä
ó
ù
è
å
ó
ð
î
â
í
è
Â
û
â
î
ä
ð
å
çó
ë
üò
àò
à
Ê
î
í
åö
0
1
Â
åò
â
è
ó
ð
î
â
í
ÿ
?
ï
åð
â
î
ãî
1
0
à
á
1 2 3 4
5
6
7
Ð
èñ
.2
.Ñ
õ
åì
û
àë
ãî
ð
è
òì
î
â
ï
ð
ÿ
ì
î
ãî
(à
)
è
î
á
ð
àò
í
î
ãî
(á
)
Ï
È
ï
ð
åî
á
ð
àç
î
â
àí
è
é
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 45
×èñëîâàÿ èíôîðìàöèÿ
Ïðîìåæóòî÷íûé
ðåçóëüòàò
2 3 5 7 4 5 4 4 2 � 8 = 16
0 1 3 5 2 3 2 2 1 � 7 = 7
x 0 2 4 1 2 1 1 1 � 6 = 6
x x 1 3 0 1 0 0 1 � 3 = 3
x x 0 2 x 0 x x 2 � 1 = 2
x x x 0 x x x x 16 + 7 + 6 + 3 + 2 = 34
Òàáëèöà 1
f( 1)1k
(t 0)
f
k1
(t0 )
f11(t0)
f21(t0)
f( 1)2k
(t2 )
f
k2
(t
2
)
f 12(t2)
f22(t2)
f 11 (t1)
f
12
(t 3)
f
11
(t3)
f( 1)3k
(t4)
f
k 3
(t4)
f13(t4 )
f23(t4 )
ÏÝ
ÏÝ
ÏÝ
ÏÝ
ÏÝ
ÏÝ
ÏÝ
ÏÝ
f 11 (t4)
f 11(t
5
)
x1
x
2
x ( 1)n
x
n
11
11
12
13
21
Ðèñ. 3. Ñòðóêòóðíàÿ ñõåìà âçàèìîäåéñòâèÿ èíôîðìàöèîííûõ ïîòîêîâ â ñåòè
Ìîäåëü ñåòåâîãî ìåòîäà ìîæíî ïðåäñòàâèòü â ôîðìàëèçîâàííîì âèäå
èñõîäÿ èç ñëåäóþùèõ ïîëîæåíèé. Ïóñòü èìååòñÿ ìíîæåñòâî ïîòîêîâ
âõîäíûõ äàííûõ. Âîçíèêàåò ñëåäóþùèé âîïðîñ. Êàê â ðåàëüíîì âðåìåíè
îðãàíèçîâàòü ïàðàëëåëüíûé âû÷èñëèòåëüíûé ïðîöåññ, ÷òîáû ïîëó÷èòü
ñòðîãî ðàñïðåäåëåííóþ âî âðåìåíè è èåðàðõèè âû÷èñëèòåëüíóþ ñåòü?
Îòâåòîì íà ýòîò âîïðîñ ìîæåò áûòü ïðèíöèï ïîñòðîåíèÿ ñëåäóþùåé
ñåòåâîé ìîäåëè. Áóäåì îáðàáàòûâàòü èëè ïðåîáðàçîâûâàòü ìíîæåñòâî âõîä-
íûõ ïîòîêîâ äàííûõ íà ðàçëè÷íûõ k èåðàðõè÷åñêèõ óðîâíÿõ. Êàæäûé óðî-
âåíü ïðåäñòàâëÿåò ñîáîé ñîâîêóïíîñòü ÏÝ, ôóíêöèîíèðóþùèõ â ñòðîãî ôèê-
ñèðîâàííûå ìîìåíòû âðåìåíè t j .
Ïóñòü çàäàíû n1 ôóíêöèé f t f t f tn1 2 1
( ), ( ),..., ( ). Äàííûå ôóíêöèè îïè-
øåì íà ðàçëè÷íûõ óðîâíÿõ èåðàðõèè èõ ïðåäñòàâëåíèÿ îò 1-ãî äî j-ãî
( j l�2 , l �1 2, ,... è j l� �2 3, l �0 1 2, , ,...):
j
n
i
n
j
j
n
i
n
j
i
j j
f t i f t ij
� � � � �
� � � �
�
�
1 1
1
1 1
2
1 1 2 2
2( ) ( )� �
1
13
13
2 3
n
f t i�
� �( ( ) )�
�
� �
� � �
� �
� �
i
n
i
n
i
f t i f t i
2
23
3
33
23 33
2 3 2 3( ( ) ) ( ( ) ) ...� �
�
�
� �
n
n
n
n
f t i
3
3 2 3( ( ) )�
�
� �
� � �
� �
� �
i
n
i
n
i
f t i f t i
1
14
2
24
14 24
2 6 2 6( ( ) ) ( ( ) ) ...� �
�
�
� �
n
n
n
n
f t i
1
1 4
1 4
2 6
( )
( ) ( ( ) )�
�
� � �
�
� �
� �
i n
n
n
i
n
l
n l
f t i f t i l
4 12
4
1
122 6 2 6( ( ) ) ... ( ( )� �) ( ( ) ) ...�
� � �
�
�
i
n
l
l
f t i l
2
22
22
2 6 �
�
� �
�
�
� �
i n
n
n l
i n
n
n l
n l n l
f t i l f t
1
1 2 2
1 2 2
2 6
( )
( ) ( ( ) ) (�
� �( ) )2 6i l �
�
� � �
�
�
�
� �
� �
i
n
l
i n
n
n
l n l
f t i l f
1
1 2 3
1 2 3 2 3
2 6 3
( ) ( )
( ) ( ( ) )� ( ) ( ( ) )2 3 2 6 3l t i l�
� � � , (1)
ãäå � — çàäåðæêà ôîðìèðîâàíèÿ ïîñëåäóþùåé ôóíêöèè îòíîñèòåëüíî
ïðåäûäóùåé; n jk — ÷èñëî ôóíêöèé j-ãî ðàçëîæåíèÿ k-ãî ôóíêöèîíàëüíîãî
óðîâíÿ.
Àíàëèçèðóÿ ìîäåëü ñåòåâîãî ìåòîäà (1), ìîæíî ñäåëàòü âûâîä î òîì,
÷òî â ïðîöåññå îáðàçîâàíèÿ êàæäîãî óðîâíÿ â åãî âåòâÿõ ôîðìèðóåòñÿ
âðåìåííîé ñäâèã �, íàëè÷èå êîòîðîãî ïðèâîäèò ê ïîëó÷åíèþ õâîñòîâûõ
ôóíêöèé.
Ïàðàëëåëèçì ÏÈ ïðåîáðàçîâàíèÿ ðåàëèçîâàí â âåòâÿõ êàæäîãî óðîâíÿ
â ñîîòâåòñòâèè ñ âðåìåííîé êîîðäèíàòîé ïî ãîðèçîíòàëè, à èåðàðõèÿ — ïî
âðåìåííîé êîîðäèíàòå ñî ñäâèãîì íà îäèí òàêò � ïî âåðòèêàëè.
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
46 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
Íà ïåðâîì óðîâíå ïàðàëëåëüíûì ñïîñîáîì â íåçàâèñèìûõ âåòâÿõ âû-
ïîëíÿåòñÿ èñõîäíîå (çàäàííîå äëÿ êîíêðåòíîé çàäà÷è) ïðåîáðàçîâàíèå è
òåì ñàìûì ôîðìèðóþòñÿ èíôîðìàöèîííûå ïîòîêè äàííûõ äëÿ ïðåîáðà-
çîâàíèÿ íà ïîñëåäóþùèõ óðîâíÿõ. Íà êàæäîì ïîñëåäóþùåì óðîâíå âû-
ïîëíÿåòñÿ ôîðìèðîâàíèå õâîñòîâîãî ýëåìåíòà.
Ýòî ïðåîáðàçîâàíèå âêëþ÷àåò ñîâìåñòíîå ðàçâèòèå èäåé ïàðàëëåëèç-
ìà, èåðàðõèè è ñìåøèâàíèÿ ïðè îáðàáîòêå èíôîðìàöèîííûõ ïîòîêîâ
äàííûõ, êîòîðûå çàòåì ðàñïðîñòðàíÿþòñÿ ïî ãîðèçîíòàëè íà îñòàëüíûå
ýëåìåíòû, à ïî âåðòèêàëè èëè â îáùåì ñëó÷àå ïî ïðîèçâîëüíîìó ìàðø-
ðóòó — íà ýëåìåíòû äðóãèõ èåðàðõè÷åñêèõ óðîâíåé. Îáåñïå÷åíèå ìàêñè-
ìàëüíîé êîððåëÿöèè ýëåìåíòîâ ÏÈ ïðåîáðàçîâàíèÿ äîñòèãàåòñÿ â ðåçóëü-
òàòå îðãàíèçàöèè ñåòåâîé ñòðóêòóðû è ìíîãîêðàòíîãî ñìåøèâàíèÿ èíôîð-
ìàöèîííûõ ïîòîêîâ äàííûõ íà ðàçëè÷íûõ óðîâíÿõ èåðàðõèè.
Ñïîñîáû ïðåäñòàâëåíèÿ ìàñîê äëÿ ðåàëèçàöèè ìíîãîóðîâíåâîãî
ïðåîáðàçîâàíèÿ. Ðàññìîòðèì íåñêîëüêî ñïîñîáîâ ïðåäñòàâëåíèÿ ìàñîê è
èõ ñâîéñòâà ïðè ðåàëèçàöèè ÏÈ ïðåîáðàçîâàíèÿ, âëèÿþùèå íà åãî õàðàê-
òåðèñòèêè [12].
Äëÿ âîññòàíîâëåíèÿ èñõîäíîé èíôîðìàöèè, ïðåîáðàçîâàííîé â ñîîò-
âåòñòâèè ñ ÷àñòíîé ìåòîäèêîé ÏÈ ïðåîáðàçîâàíèÿ, â ïðîöåññå îáðàáîòêè
ìàññèâîâ íåîáõîäèìî íà êàæäîì øàãå ïðåîáðàçîâàíèÿ ti çàïîìèíàòü, íà
êàêèõ ïîçèöèÿõ â ìàññèâå A tj i
� ( ) (ãäå j — íîìåð ìàññèâà, � — íîìåð
óðîâíÿ) íàõîäÿòñÿ ýëåìåíòû, ðàâíûå ýëåìåíòó a tj i
� ( )
1 .
Ñôîðìèðóåì äëÿ ýòîãî äâîè÷íîå ñëîâî, ðàçðÿäíîñòü êîòîðîãî ðàâíà
ðàçìåðíîñòè ìàññèâà A tj i
� ( )
2 , à åäèíèöû ñòîÿò â òåõ ïîçèöèÿõ êîäà, â
êàêèõ ïîçèöèÿõ ìàññèâà íàõîäèòñÿ ýëåìåíò, ðàâíûé âûáðàííîìó. Âñå
îñòàëüíûå ïîçèöèè äâîè÷íîãî êîäà çàïîëíÿþòñÿ íóëÿìè. Ýòîò äâîè÷íûé
êîä, ôîðìèðóåìûé íà êàæäîì øàãå Q*-ïðåîáðàçîâàíèÿ ìàññèâà, íàçîâåì
ìàñêîé: F t F tj i j i
� �( )( ( )) — ìàñêà ìàññèâà A tj i
� ( ) ïî ýëåìåíòó a tj i
� ( )
1 . Ìàñ-
êè ôîðìèðóþòñÿ â ïðîöåññå âñåãî ïðåîáðàçîâàíèÿ ìàññèâà äî åãî ïîëíîé
ñõîäèìîñòè íà âñåõ óðîâíÿõ è äëÿ âñåõ âåòâåé. Ìàñêè íåîáõîäèìû äëÿ
ïðîöåññà äåêîäèðîâàíèÿ è ñîäåðæàò èíôîðìàöèþ î òîì, íà êàêîé ïîçèöèè
(ïîçèöèÿõ) â ìàññèâå äîëæåí íàõîäèòüñÿ âûáðàííûé ýëåìåíò.
Ïåðâûé ñïîñîá ïðåäñòàâëåíèÿ ìàñîê — äâîè÷íûå ñëîâà, ðàçìåðíîñòü
êîòîðûõ ðàâíà ðàçìåðíîñòè ìàññèâà. Ýòîò ñïîñîá ôîðìèðîâàíèÿ ìàñîê
ìîæíî èñïîëüçîâàòü â ëþáûõ àëãîðèòìàõ ÏÈ ïðåîáðàçîâàíèÿ. Íåäîñòàò-
êîì òàêîãî ñïîñîáà ÿâëÿåòñÿ ãðîìîçäêîñòü ïðåäñòàâëåíèÿ ìàñîê, íî àëãî-
ðèòì èõ ôîðìèðîâàíèÿ ïðè ýòîì î÷åíü ïðîñò.
Âòîðîé ñïîñîá ïðåäñòàâëåíèÿ ìàñîê — ñòåêîâûé. Îí çàêëþ÷àåòñÿ â
òîì, ÷òî ìàñêàìè ÿâëÿþòñÿ íà÷àëüíûå àäðåñà (íîìåðà ïîçèöèé) ïîäìíî-
æåñòâ ñ îäèíàêîâûìè ýëåìåíòàìè èëè íåïîñðåäñòâåííî àäðåñ ýëåìåíòà,
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 47
äëÿ êîòîðîãî ôîðìèðóåòñÿ ìàñêà. Ýòîò ñïîñîá ïîçâîëÿåò ñîêðàòèòü îáúåì
ïðåäñòàâëåíèÿ ìàñîê, íî òðåáóåò äîïîëíèòåëüíûõ ïðåîáðàçîâàíèé ïðè
êîäèðîâàíèè è äåêîäèðîâàíèè ìàññèâà.
Ñòåêîâûì ýòîò ñïîñîá íàçûâàåòñÿ ïîòîìó, ÷òî ïðè êîäèðîâàíèè ìàñ-
ñèâà ôîðìèðóåìûå àäðåñà âûáðàííûõ ýëåìåíòîâ çàïèñûâàþòñÿ ïî ñòåêî-
âîìó ïðèíöèïó, øèðîêî ðàñïðîñòðàíåííîìó â óñòðîéñòâàõ ïàìÿòè [13,
14]. Äåêîäèðîâàíèå ìàññèâà ñî ñòåêîâûìè ìàñêàìè ïðåäïîëàãàåò ïîýòàï-
íîå ïðåîáðàçîâàíèå ìàññèâà ïî ñëåäóþùåìó ïðàâèëó: èç ñòåêà âûáèðàåòñÿ
âåðõíèé àäðåñ è çíà÷åíèÿ ýòîãî àäðåñà, ìàññèâ çàïîëíÿåòñÿ ýëåìåíòàìè,
ðàâíûìè ýëåìåíòó ñ äàííûì àäðåñîì. Çàïîëíåíèå èíôîðìàöèè îñóùåñòâ-
ëÿåòñÿ äî òîé ïîçèöèè, àäðåñ êîòîðîé âûáðàí èç ñòåêà íà ïðåäûäóùèõ
øàãàõ äåêîäèðîâàíèÿ. Åñëè òàêîé àäðåñ îòñóòñòâóåò, òî çàïîëíåíèå âû-
ïîëíÿåòñÿ äî ïîñëåäíåãî ýëåìåíòà ìàññèâà. Ïîñëå òîãî êàê èç ñòåêà âûá-
ðàí ïîñëåäíèé àäðåñ, ïðîöåññ äåêîäèðîâàíèÿ çàêàí÷èâàåòñÿ.
Ïðîöåññîì çàïîëíåíèÿ ìàññèâà ýëåìåíòàìè ìîæíî óïðàâëÿòü, àíàëè-
çèðóÿ çíà÷åíèÿ ñëåäóþùåãî è çàìåíÿåìîãî ýëåìåíòîâ. Åñëè ýòè çíà÷åíèÿ
ðàâíû, òî çàïîëíÿåòñÿ ñëåäóþùàÿ ïîçèöèÿ.  ïðîòèâíîì ñëó÷àå, êîãäà
ðàíåå çàïîëíåííûå ýëåìåíòû â ìàññèâå åäèíè÷íûå èëè ñîñòàâëÿþò îäè-
íî÷íóþ ãðóïïó, ñëåäóþùàÿ ïîçèöèÿ íå çàïîëíÿåòñÿ .
Òðåòèé ñïîñîá ïðåäñòàâëåíèÿ ìàñîê îñíîâàí íà îïòèìèçàöèè ÿâíî
èçáûòî÷íîãî ïåðâîãî ñïîñîáà. Èçáûòî÷íîñòü ïðåäñòàâëåíèÿ ìàñîê, ðàç-
ðÿäíîñòü êîòîðûõ ðàâíà ðàçìåðíîñòè ìàññèâà, ñîñòîèò â òîì, ÷òî òå ðàç-
ðÿäû ìàñîê, â êîòîðûõ ñîäåðæèòñÿ åäèíèöà, âî âñåõ ñëåäóþùèõ ìàñêàõ
çàïîëíÿþòñÿ íóëÿìè. Òàêèå ðàçðÿäû èç ñëåäóþùèõ ìàñîê ìîæíî èñêëþ-
÷èòü, ÷òî è ÿâëÿåòñÿ îñíîâîé ýòîãî ñïîñîáà. Ïðè êîäèðîâàíèè ìàññèâà â
ýòîì ñëó÷àå êàæäàÿ ïîñëåäóþùàÿ ìàñêà èìååò ðàçìåðíîñòü ìåíüøå ïðå-
äûäóùåé íà ÷èñëî åäèíèö â ïðåäûäóùåé ìàñêå.
Ðàññìîòðèì ïðèìåð êîäèðîâàíèÿ ìàññèâà, ñîñòîÿùåãî èç âîñüìè ýëå-
ìåíòîâ (òàáë. 2). Â äàííîì ïðèìåðå äëÿ õðàíåíèÿ ìàñîê íåîáõîäèìà ïà-
ìÿòü îáúåìîì 18 áèò, â òî âðåìÿ êàê äëÿ õðàíåíèÿ ïîëíûõ ìàñîê òðåáóåòñÿ
5 � 8 = 40 áèò. Ïðè ýòîì ïîñëåäíþþ ìàñêó ìîæíî íå õðàíèòü, òàê êàê îíà
ñîñòîèò òîëüêî èç åäèíèö. Ïðè äåêîäèðîâàíèè â ïðåäïîñëåäíåé ìàñêå íà
ìåñòå åäèíèö íåîáõîäèìî óñòàíàâëèâàòü ïðåäïîñëåäíèé âûáðàííûé ýëå-
ìåíò, à íà ìåñòå íóëåé — ïîñëåäíèå âûáðàííûå ýëåìåíòû.
×åòâåðòûé ñïîñîá — ïðåäñòàâëåíèå ìàñîê ëîãèêî-âðåìåííûì êîäîì
(ËÂÊ) [5, 15].  ýòîì ñëó÷àå êàæäîìó ýëåìåíòó ñîîòâåòñòâóåò îïðåäåëåí-
íûé îòðåçîê âðåìåíè (êâàíò âðåìåíè) — ËÂÊ. Åñëè ïðè êîäèðîâàíèè
ìàññèâà âñòðå÷àåòñÿ ýëåìåíò, ðàâíûé âûáðàííîìó, òî ñîîòâåòñòâóþùèé
êâàíò âðåìåíè çàïîëíÿåòñÿ èìïóëüñîì, â ïðîòèâíîì ñëó÷àå èìïóëüñ
îòñóòñòâóåò. Ïðîöåññ êîäèðîâàíèÿ ìàñîê âûïîëíÿåòñÿ ïàðàëëåëüíî äëÿ
âñåõ ðàçëè÷íûõ ýëåìåíòîâ ìàññèâà. Ìàñêè ËÂÊ äëÿ ìàññèâà èç òàáë. 2
ïðåäñòàâëåíû íà ðèñ. 4.
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
48 ISSN 0204—3572. Electronic Modeling. 2012. V. 35. ¹ 1
Êðîìå ÷åòûðåõ îñíîâíûõ ñïîñîáîâ ïðåäñòàâëåíèÿ ìàñîê, âîçìîæíû
÷àñòíûå ñëó÷àè, êîòîðûå îïðåäåëÿþòñÿ àëãîðèòìàìè ÏÈ ïðåîáðàçîâàíèÿ.
Òàê, ïðè âûáîðå ýëåìåíòîâ èç ìàññèâà ïî ïîðÿäêîâîìó íîìåðó â ñëó÷àå èñ-
ïîëüçîâàíèÿ òðåòüåãî ñïîñîáà ïðåäñòàâëåíèÿ ìàñîê â ïåðâîì ðàçðÿäå âñåõ
ìàñîê âñåãäà áóäåò ñòîÿòü åäèíèöà. Ðåçóëüòàò ðàçëîæåíèÿ ìàññèâà ïî
òàêîìó àëãîðèòìó ïðåäñòàâëåí â ëåâîé ÷àñòè òàáë. 3.  êà÷åñòâå èñõîäíîãî
âûáðàí ìàññèâ, ïðåäñòàâëåííûé â òàáë. 2.
Èç òàáë. 3 âèäíî, ÷òî ïåðâûå ðàçðÿäû ìàñîê ñîäåðæàò åäèíèöû. Åñëè
âûáðàííûé ýëåìåíò — åäèíñòâåííûé â ìàññèâå, òî âî âñåõ îñòàëüíûõ
ðàçðÿäàõ ìàñêè áóäóò íóëè, ÷òî ìàëîèíôîðìàòèâíî, è òàêóþ èíôîðìàöèþ
ïðè êîäèðîâàíèè ìîæíî íå èñïîëüçîâàòü.  ïðàâîé ÷àñòè òàáë. 3 ïðåäñòàâëåí
ðåçóëüòàò ðàçëîæåíèÿ ìàññèâà ñ ó÷åòîì èçëîæåííîãî âûøå. Êàê âèäèì, ìàñ-
êè òàêîãî ìàññèâà ñîêðàùàþòñÿ äî îäíîé âîñüìèðàçðÿäíîé ìàñêè.
Âîçìîæíà ñèòóàöèÿ, êîãäà âåñü ìàññèâ ñîñòîèò èç îäèíàêîâûõ ýëå-
ìåíòîâ. Ýòî îçíà÷àåò, ÷òî ìàñêà òàêîãî ìàññèâà òîëüêî îäíà è ñîäåðæèò
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 49
Ðèñ. 4. Ïðåäñòàâëåíèå ìàñîê â âèäå ËÂÊ
Íîìåð ýëåìåíòà Ìàññèâ Ìàñêà
1 3 1 0 0 1 1
2 3 1 1 0 0
3 10 0 0 1
4 3 1 0
5 3 1
6 4 0
7 12 0
8 7 0
Âûáðàííûå ýëåìåíòû 3 4 7 10 12
Òàáëèöà 2
åäèíèöû âî âñåõ ðàçðÿäàõ. Òàêóþ ìàñêó ìîæíî íå çàïîìèíàòü, à çàïîì-
íèòü ëèøü ðàçìåðíîñòü ìàññèâà è ýëåìåíò, èç êîòîðîãî ñîñòîèò äàííûé
ìàññèâ. Ïðè äåêîäèðîâàíèè ìàññèâà íåîáõîäèìî ó÷èòûâàòü, ÷òî åñëè
ìàñêà îòñóòñòâóåò, òî âåñü ìàññèâ ñîñòîèò èç îäèíàêîâûõ ýëåìåíòîâ.
Ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé ìåòîäà ìíîãîóðîâ-
íåâîãî ïðåîáðàçîâàíèÿ ìàñêèðîâàííûõ ñèãíàëîâ. Â ýêñïåðèìåíòàëü-
íûõ èññëåäîâàíèÿõ èñïîëüçîâàí ðàçðàáîòàííûé ïðîãðàììíûé êîìïëåêñ
äëÿ ðåàëèçàöèè ïðÿìîãî è îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ, êîòîðûé ñîäåð-
æèò äâà ïðîãðàììíûõ ïðîäóêòà [16, 17].
1. Ïðîãðàììó ðåàëèçàöèè ïðÿìîãî ÏÈ ïðåîáðàçîâàíèÿ öèôðîâûõ ñèã-
íàëîâ ñ îïòèìèçàöèåé ïðîöåäóðû ôîðìèðîâàíèÿ ìàñîê. Ïðèìåíåíèå îï-
òèìèçèðîâàííîãî àëãîðèòìà ôîðìèðîâàíèÿ ìàñîê, êîòîðûé ïîçâîëÿåò
óìåíüøèòü îáúåì ïàìÿòè, íåîáõîäèìûé äëÿ èõ ñîõðàíåíèÿ, ïî ñðàâíåíèþ
ñ íåîïòèìèçèðîâàííûì àëãîðèòìîì. Ïðè ýòîì îäíèì èç ýòàïîâ ÏÈ ïðå-
îáðàçîâàíèÿ ÿâëÿåòñÿ óìíîæåíèå ìèíèìàëüíîãî ýëåìåíòà íà ìîùíîñòü â
îïåðàòîðå ïðåîáðàçîâàíèÿ G (ðèñ. 5, à).
2. Ïðîãðàììó ðåàëèçàöèè îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ íà îñíîâå
îïòèìèçèðîâàííîãî ìåòîäà ôîðìèðîâàíèÿ ìàñîê äëÿ âîññòàíîâëåíèÿ ïðå-
îáðàçîâàííûõ ìåòîäîì ïðÿìîãî ÏÈ ïðåîáðàçîâàíèÿ ñ îïòèìèçàöèåé ïðî-
öåäóðû ôîðìèðîâàíèÿ ìàñîê èíôîðìàöèîííûõ ñðåä, ïðåäñòàâëåííûõ â
âèäå äâóìåðíîé ìàòðèöû äàííûõ èëè èçîáðàæåíèÿ. Îñîáåííîñòüþ ðåàëè-
çîâàííîãî àëãîðèòìà ÿâëÿåòñÿ ìîäèôèêàöèÿ ïðîöåññà äåêîäèðîâàíèÿ íà
îñíîâå îïòèìèçèðîâàííîãî àëãîðèòìà ðàáîòû ñ ìàñêàìè, êîòîðàÿ ïîâû-
øàåò áûñòðîäåéñòâèå äåêîäèðîâàíèÿ (ðèñ. 5, á).
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
50 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
Íîìåð
ýëåìåíòà
Ìàññèâ Ìàñêà
Íîìåð
ýëåìåíòà
Ìàññèâ Ìàñêà
1 3 1 1 1 1 1 1 3 1
2 3 1 0 0 0 2 3 1
3 10 0 0 0 3 10 0
4 3 1 0 4 3 1
5 3 1 5 3 1
6 4 0 6 4 0
7 12 0 7 12 0
8 7 0 8 7 0
Âûáðàííûå
ýëåìåíòû 3 4 7 10 12
Âûáðàííûå
ýëåìåíòû 3 10 4 12 7
Òàáëèöà 3
ßçûê ðåàëèçàöèè ïðîãðàììíîãî êîìïëåêñà — C++. Ôóíêöèè ïðîãðàìì-
íîé áèáëèîòåêè, ïîñëå ïåðåêîìïèëÿöèè, êîððåêòíî ðàáîòàþò ñ ðàçëè÷íûìè
îïåðàöèîííûìè ñèñòåìàìè: MS Windows, GNU/Linux, Mac OS.
Îñíîâíûå ýòàïû ðåàëèçàöèè ïðÿìîãî ÏÈ ïðåîáðàçîâàíèÿ ñ îïòèìè-
çàöèåé ïðîöåäóðû ôîðìèðîâàíèÿ ìàñîê ñëåäóþùèå.
1. Çàãðóçêà èíôîðìàöèîííîãî ìàññèâà (â âèäå èçîáðàæåíèÿ èëè äâó-
ìåðíîé ìàòðèöû äàííûõ, çàäàííîé ïîëüçîâàòåëåì ðàçìåðíîñòè). Ôîðìè-
ðîâàíèå ìíîæåñòâ { ( ), ( ),..., ( )}M t M t M th1
1
0 2
1
0
1
0 (ñì. ðèñ. 1).
2. Âûïîëíåíèå ïðÿìîãî ÏÈ ïðåîáðàçîâàíèÿ ñ îïòèìèçàöèåé ïðîöåäó-
ðû ôîðìèðîâàíèÿ ìàñîê íàä äàííûìè (èçîáðàæåíèåì). Ïîñëåäîâàòåëüíîå
ïðèìåíåíèå òðåõ îïåðàòîðîâ � ( ) [ ( ( ))]M T S G M� (ñì. ðèñ. 5, à).
2.1. Òðàíñïîíèðîâàíèå (ñì. ðèñ. 5, à, ìåòîä Ò ). Ïåðåõîä îò ýâîëþöèè
ìàññèâîâ ïî âåðòèêàëè ê ýâîëþöèè ìàññèâîâ ïî ãîðèçîíòàëè (ñì. ðèñ. 1).
2.2. G-ïðåîáðàçîâàíèå (ñì. ðèñ. 5, à, ìåòîä G). Ýâîëþöèÿ ìàññèâîâ ïî
ãîðèçîíòàëè (ñì. ðèñ. 1).
2.3. Ñäâèã (ðèñ. 5, à, ìåòîä S); çàïîìèíàíèå îäíîìåðíîé ìàòðèöû
õâîñòîâûõ ýëåìåíòîâ ïðåîáðàçîâàííîãî èíôîðìàöèîííîãî ìàññèâà (ñì.
ðèñ. 5, à, ìåòîä getHash). Â ïðåäåëàõ îäíîãî óðîâíÿ âåòâè ñäâèíóòû âî
âðåìåíè îäíà îòíîñèòåëüíî äðóãîé íà îäèí òàêò (ñì. ðèñ. 1).
3. Ôîðìèðîâàíèå îäíîìåðíîé ìàòðèöû îïòèìèçèðîâàííûõ ìàñîê (ñì.
ðèñ. 5, à, ìåòîä getMasks).
4. Âåäåíèå ôàéëà-ïðîòîêîëà.
Îñíîâíûå ýòàïû ðåàëèçàöèè îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ íà îñíîâå
îïòèìèçèðîâàííîãî ìàñî÷íîãî ìåòîäà ñëåäóþùèå.
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 51
Ðèñ. 5. Ôðàãìåíòû äèàãðàììû êëàññîâ ïðîãðàììû äëÿ ðåàëèçàöèè ïðÿìîãî (à) è îáðàò-
íîãî (á) ÏÈ ïðåîáðàçîâàíèÿ íà îñíîâå îïòèìèçèðîâàííîãî ìåòîäà ôîðìèðîâàíèÿ ìàñîê
1. Çàãðóçêà ìàññèâà õâîñòîâûõ ýëåìåíòîâ (â âèäå îäíîìåðíîãî íàáîðà
äàííûõ, ïîëó÷åííûõ ïðè êîäèðîâàíèè ìåòîäîì ïðÿìîãî ÏÈ ïðåîáðàçî-
âàíèÿ ñ îïòèìèçàöèåé ïðîöåäóðû ôîðìèðîâàíèÿ ìàñîê).
2. Çàãðóçêà ìàññèâà îïòèìèçèðîâàííûõ ìàñîê (â âèäå îäíîìåðíîãî
íàáîðà äàííûõ (ñîñòîÿùåãî èç 0 è 1), ïîëó÷åííûõ ïðè êîäèðîâàíèè ìåòî-
äîì ïðÿìîãî ÏÈ ïðåîáðàçîâàíèÿ ñ îïòèìèçàöèåé ïðîöåäóðû ôîðìèðî-
âàíèÿ ìàñîê).
3. Âûïîëíåíèå îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ íà îñíîâå îïòèìè-
çèðîâàííîãî ìåòîäà ìàñîê íàä çàäàííûìè äàííûìè (ñì. ðèñ. 5, á, ìåòîä
ReversePI).
4. Âîññòàíîâëåíèå íà÷àëüíîãî ìàññèâà äàííûõ (â âèäå äâóìåðíîé
ìàòðèöû äàííûõ èëè èçîáðàæåíèÿ (ñì. ðèñ. 5, á, ìåòîä getMatrix)).
Ðàçðàáîòàííûå ïðîãðàììû ïîçâîëÿþò çàãðóçèòü èçîáðàæåíèå, èëè
çàäàòü ðàçìåðû ìàòðèöû äëÿ ïðÿìîãî è îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ, è
çàïîëíèòü çàäàííóþ ìàòðèöó ñîáñòâåííîðó÷íî èëè ñ ïîìîùüþ ãåíåðàòîðà
ïñåâäîñëó÷àéíûõ ÷èñåë. Ïîñëå ýòîãî äëÿ çàäàííîãî ìàññèâà äàííûõ âû-
ïîëíÿåòñÿ ÏÈ ïðåîáðàçîâàíèå, âûâîäÿòñÿ çíà÷åíèÿ õâîñòîâûõ ýëåìåíòîâ,
èõ ñóììà è ñóììà âõîäíîé ìàòðèöû (óêàçàííûå ñóììû, ñîãëàñíî òåîðèè
ÏÈ ïðåîáðàçîâàíèÿ, äîëæíû ñîâïàäàòü), à òàêæå âðåìÿ îáðàáîòêè è îáîá-
ùåííûé ðàçìåð ìàñîê.
Ðàçðàáîòàííûé ïðîãðàììíûé êîìïëåêñ äëÿ ðåàëèçàöèè ïðÿìîãî è
îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ ñèãíàëîâ ïðîòåñòèðîâàí íà ðàçëè÷íûõ íà-
áîðàõ äàííûõ: â âèäå äâóìåðíîé ìàòðèöû äàííûõ ðàçíîé ðàçìåðíîñòè, à
òàêæå ïÿòíîïîäîáíûõ èçîáðàæåíèé ïðîôèëÿ ëàçåðíîãî ëó÷à ðàçíîé ðàç-
ìåðíîñòè. Â òåñòîâîì ïðèìåðå îñóùåñòâëåíà ðåàëèçàöèÿ ïðÿìîãî ÏÈ
ïðåîáðàçîâàíèÿ ñ îïòèìèçàöèåé ôîðìèðîâàíèÿ ìàñîê íàä öâåòíûì ïÿòíî-
ïîäîáíûì èçîáðàæåíèåì ïðîôèëÿ ëàçåðíîãî ëó÷à (â ôîðìàòå RGB ðàçìåð-
íîñòüþ 128 � 128 ïèêñåëåé) è âûïîëíåíî îáðàòíîå ÏÈ ïðåîáðàçîâàíèå íà
îñíîâå îïòèìèçèðîâàííîãî ìåòîäà ìàñîê äëÿ åãî âîññòàíîâëåíèÿ.
Ïîëó÷åííûå ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé (è òåñòî-
âîãî ïðèìåðà) ñâèäåòåëüñòâóþò î ïîâûøåíèè áûñòðîäåéñòâèÿ ÏÈ ïðå-
îáðàçîâàíèÿ ïî ñëåäóþùèì êðèòåðèÿì:
áûñòðîäåéñòâèå îáðàáîòêè ïðÿìûì ÏÈ ïðåîáðàçîâàíèåì íåîïòèìè-
çèðîâàííûì ìåòîäîì — 984 ìñ, îïòèìèçèðîâàííûì ìåòîäîì —782 ìñ;
áûñòðîäåéñòâèå îáðàáîòêè îáðàòíûì ÏÈ ïðåîáðàçîâàíèåì íåîïòèìè-
çèðîâàííûì ìåòîäîì — 1250 ìñ, îïòèìèçèðîâàííûì ìåòîäîì — 422 ìñ;
óìåíüøåíèå èçáûòî÷íîñòè îáúåìîâ ïàìÿòè ïðè ôîðìèðîâàíèè ìàññè-
âîâ ìàñîê íåîïòèìèçèðîâàííûì ìåòîäîì — 25 057 800 áèò, îïòèìèçè-
ðîâàííûì ìåòîäîì — 10 187 072 áèòà.
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
52 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
Âûâîäû
Ïðåäëîæåííûé ìåòîä ïîçâîëÿåò ïîâûñèòü áûñòðîäåéñòâèå ïðÿìîãî è îá-
ðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ, à òàêæå îïòèìèçèðîâàòü èçáûòî÷íîñòü ïðåä-
ñòàâëåíèÿ ìàñîê, ðàçðÿäíîñòü êîòîðûõ ðàâíÿåòñÿ ðàçìåðíîñòè îáðàáàòû-
âàåìûõ öèôðîâûõ ñèãíàëîâ.
Âûáðàííûé â ðåçóëüòàòå ñðàâíèòåëüíîãî àíàëèçà ìåòîä ïðåäñòàâëåíèÿ
ìàñîê äëÿ îïòèìèçàöèè îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ èçîáðàæåíèé ïðèâî-
äèò ê ñóùåñòâåííîìó óìåíüøåíèþ îáúåìîâ ïàìÿòè, íåîáõîäèìîé äëÿ ñîõðà-
íåíèÿ ìàñîê, à òàêæå èìååò ñâîéñòâà âûÿâëåíèÿ îøèáîê êîäèðîâàíèÿ.
Ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé ïîäòâåðäèëè ýôôåêòèâ-
íîñòü ïðåäëîæåííûõ àëãîðèòìîâ ïðÿìîãî è îáðàòíîãî ÏÈ ïðåîáðàçîâàíèÿ
öèôðîâûõ ñèãíàëîâ è âîçìîæíîñòü ïðèìåíåíèÿ èõ â ïðèêëàäíûõ çàäà÷àõ
êîäèðîâàíèÿ, îáðàáîòêè è ñðàâíåíèÿ èçîáðàæåíèé. Ïîëó÷åííûå ðåçóëüòàòû
ìîãóò íàéòè ïðèìåíåíèå â äàëüíåéøèõ èññëåäîâàíèÿõ ïî ðàçðàáîòêå âûñî-
êîïðîèçâîäèòåëüíûõ ìíîãîóðîâíåâûõ ïàðàëëåëüíî-èåðàðõè÷åñêèõ ñåòåé íà
îñíîâå îïòîýëåêòðîííîé è îïòè÷åñêîé ýëåìåíòíîé áàçû.
An analysis of structural-functional organization of the network architecture of parallel-hierar-
hical transformation and mask generation methods has been performed. The method of optimized
forming of masks by encoding information in parallel-hierarchical transformation is proposed.
The software package with high speed performance of lossless direct and reversal parallel-hierar-
hical transformation of information has been developed.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ïðýòò Ó. Öèôðîâàÿ îáðàáîòêà èçîáðàæåíèé. Â 2-õ òîìàõ. — Ì. : Ìèð, 1982. — Ò. 1. —
310 ñ., Ò. 2. — 790 ñ.
2. Ãðåíàíäåð Ó. Ëåêöèè ïî òåîðèè îáðàçîâ. Àíàëèç îáðàçîâ. — Ì. : Ìèð, 1981. — 448 ñ.
3. Ñêëÿð Á. Öèôðîâàÿ ñâÿçü. Òåîðåòè÷åñêèå îñíîâû è ïðàêòè÷åñêîå ïðèìåíåíèå. Èçä. 2-å
èñïð. : Ïåð. ñ àíãë. — Ì. : ÈÄ «Âèëüÿìñ», 2003. — 1104 ñ.
4. Ñåðãèåíêî À.Á. Öèôðîâàÿ îáðàáîòêà ñèãíàëîâ: Ó÷åá. ïîñîáèå. Âòîðîå èçä. — ÑÏá. :
Ïèòåð, 2006. — 752 ñ.
5. Êîæåì’ÿêî Â.Ï., Êóòàºâ Þ.Ô., Ñâº÷í³êîâ Ñ.Â. òà ³í. Ïàðàëåëüíî-³ºðàðõ³÷íå ïåðåòâî-
ðåííÿ ÿê ñèñòåìíà ìîäåëü îïòèêî-åëåêòðîííèõ çàñîá³â øòó÷íîãî ³íòåëåêòó. — ³ííèöÿ :
ÓͲÂÅÐÑÓÌ-³ííèöÿ, 2003. — 324 ñ.
6. Yarovyy A.A. Applied Realization of Neural Network and Neurolike Parallel-Hierarchical
System Based on GPGPU. Development and application systems// Proc. of the 10th Intern.
Conf. on DAS-2010. May 27—29, 2010, Suceava.— Romania: Suceava, Universitatea
Stefan cel Mare Suceava, 2010. — Ð. 351—356.
7. Kozhemyako V., Timchenko L., Yarovyy A. Methodological Principles of Pyramidal and Paral-
lel-Hierarchical Image Processing on the Base of Neural-Like Network Systems // Advances in
Electrical and Computer Engineering. — 2008. — Vol. 8 (15), ¹ 2 (30). — Ð. 54—60.
8. Kozhemyako V.P., Timchenko L.I., Yarovyy A.A. Software Support of Accurately Measure-
ment and Prediction of Laser Beam Profile Characteristics// Proc. of the 10th Intern. Conf.
«Swiat³owody i ich zastosowania», October 4—7, 2006, Krasnobród, Poland. Tom 2 —
Lublin, Wydawnictwo-Drukarnia Liber Duo s.c., 2006. — Ð. 675—684.
Òåîðåòè÷åñêèå è ïðèêëàäíûå àñïåêòû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 2 53
9. Timchenko L., Kutaev Yu., Kozhemyako V. et al. Method for Processing of Extended Laser
Paths Images // Advances in Electrical and Computer Engineering. — 2003. — Vol. 3 (10),
¹ 2 (20). — P. 66—78.
10. Êíóò Ä. Èñêóññòâî ïðîãðàììèðîâàíèÿ äëÿ ÝÂÌ. Â 3-x ò. — Ì. : Ìèð, 1978.
11. Timchenko L., Kutaev Yu., Kozhemyako V. et al. Method for Training of a Parallel-Hierarchi-
cal Network, Based on Population Coding for Processing of Extended Laser Paths Images //
Proc. of SPIE. — 2002. —Vol. 4790. — P. 465—479.
12. ßðîâèé À.À. Ìåòîä îïòèì³çîâàíîãî ôîðìóâàííÿ ìàñîê ïðè êîäóâàíí³ ³íôîðìàö³¿ â
ïàðàëåëüíî-³ºðàðõ³÷íîìó ïåðåòâîðåíí³ // ³ñíèê Âϲ. — 2011. — ¹ 6 (99). — Ñ. 216—
223.
13. Áðþõîâè÷ Å.À. Àâòîìàòè÷åñêèé êîíòðîëü è ïðîèçâîäèòåëüíîñòü ÝÂÌ. // ÓÑÈÌ. —
1979. — ¹ 4. — C. 83—86.
14. Ìåòëèöêèé Å.À., Êàâåðçíåâ Â.Â. Ñèñòåìû ïàðàëëåëüíîé ïàìÿòè: òåîðèÿ, ïðîåêòèðîâà-
íèå, ïðèìåíåíèå. Ïîä ðåä. Â.È. Òèìîõèíà. — Ë. : Èçä. Ëåíèãðàäñêîãî óíèâåðñèòåòà,
1989. — 240 ñ.
15. Êîæåìÿêî Â.Ï., Òèì÷åíêî Ë.È., ßðîâîé À.À. Ìîäåëè ïàðàëëåëüíî-èåðàðõè÷åñêîé
îáðàáîòêè èíôîðìàöèè íà îñíîâå àïïàðàòà ëîãèêî-âðåìåííûõ ôóíêöèé// Òåçèñû
äîêë. Ìåæäóíàð. íàó÷. êîíô. «Èíôîðìàöèîííûå è êîìïüþòåðíûå òåõíîëîãèè, ìîäå-
ëèðîâàíèå, óïðàâëåíèå». Ãðóçèÿ, Òáèëèñè: 1—4 íîÿáðÿ 2010 ã. — Òáèëèñè : Èçä-âî
ÃÒÓ, 2010. — Ñ. 231—232.
16. Ñâ³äîöòâî ïðî ðåºñòðàö³þ àâòîðñüêîãî ïðàâà íà òâ³ð ¹ 39490. Êîìï’þòåðíà ïðîãðàìà
ïðÿìîãî ïàðàëåëüíî-³ºðàðõ³÷íîãî ïåðåòâîðåííÿ ç îïòèì³çàö³ºþ ôîðìóâàííÿ ìàñîê (³ç
ìíîæåííÿì ì³í³ìàëüíîãî åëåìåíòà íà ïîòóæí³ñòü â îïåðàòîð³ ïåðåòâîðåííÿ G). /
À.À ßðîâèé, ².Ì. Ñóãàê — Çàðåºñòðîâàíî ÄIJ Óêðà¿íè 04.08.2011.
17. Ñâ³äîöòâî ïðî ðåºñòðàö³þ àâòîðñüêîãî ïðàâà íà òâ³ð ¹ 39489. Êîìï’þòåðíà ïðîãðàìà
çâîðîòíîãî ïàðàëåëüíî-³ºðàðõ³÷íîãî ïåðåòâîðåííÿ íà îñíîâ³ îïòèì³çîâàíîãî ìàñêî-
âîãî ìåòîäó (³ç ìíîæåííÿì ì³í³ìàëüíîãî åëåìåíòà íà ïîòóæí³ñòü â îïåðàòîð³ ïåðåòâî-
ðåííÿ G). / À.À.ßðîâèé, ².Ì. Ñóãàê — Çàðåºñòðîâàíî ÄIJ Óêðà¿íè 04.08.2011.
Ïîñòóïèëà 21.06.12;
ïîñëå äîðàáîòêè 12.11.12
ÒÈÌ×ÅÍÊÎ Ëåîíèä Èâàíîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð, çàâ. êàôåäðîé òåëåêîììóíèêà-
öèîííûõ òåõíîëîãèé è àâòîìàòèêè Ãîñóäàðñòâåííîãî ýêîíîìèêî-òåõíîëîãè÷åñêîãî óíèâåðñè-
òåòa òðàíñïîðòà.  1979 ã. îêîí÷èë Âèííèöêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ
èññëåäîâàíèé — ñèñòåìû èñêóññòâåííîãî èíòåëëåêòà.
ßÐÎÂÎÉ Àíäðåé Àíàòîëüåâè÷, êàíä. òåõí. íàóê, äîêòîðàíò, äîöåíò êàôåäðû êîìïüþòåðíûõ
íàóê Âèííèöêîãî íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà, êîòîðûé îêîí÷èë â 2001 ã. Îá-
ëàñòü íàó÷íûõ èññëåäîâàíèé — ïàðàëëåëüíûå âû÷èñëåíèÿ, íåéðîïîäîáíûå èíòåëëåêòóàëüíûå
ñèñòåìû, ðàñïîçíàâàíèå îáðàçîâ è îáðàáîòêà èçîáðàæåíèé.
ÊÎÊÐßÖÊÀß Íàòàëüÿ Èâàíîâíà, êàíä. òåõí. íàóê, äîöåíò êàôåäðû òåëåêîììóíèêàöèîííûõ
òåõíîëîãèé è àâòîìàòèêè Ãîñóäàðñòâåííîãî ýêîíîìèêî-òåõíîëîãè÷åñêîãî óíèâåðñèòåòà
òðàíñïîðòà.  1973 ã. îêîí÷èëà Âèííèöêèé ïåäàãîãè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëå-
äîâàíèé — ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå ïàðàëëåëüíûõ ïðîöåññîâ.
Ë.È. Òèì÷åíêî, À.À. ßðîâîé, Í.È. Êîêðÿöêàÿ
54 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-100837 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-11-27T13:58:32Z |
| publishDate | 2013 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Тимченко, Л.И. Яровой, А.А. Кокряцкая, Н.И. 2016-05-27T14:45:08Z 2016-05-27T14:45:08Z 2013 Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов / Л.И. Тимченко, А.А. Яровой, Н.И. Кокряцкая // Электронное моделирование. — 2013. — Т. 35, № 2. — С. 35-54 . — Бібліогр.: 17 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/100837 681.3:004.272 Выполнен анализ структурно-функциональной организации сетевой архитектуры параллельно-иерархического (ПИ) преобразования цифровых сигналов и методов формирования масок при его реализации. Предложен метод оптимизированного формирования масок при ПИ преобразовании для кодирования информации и разработан программный комплекс, в котором повышено быстродействие прямого и обратного ПИ преобразования информации без ее потерь. Виконано аналіз особливостей структурно-функціональної організації сітчастої архітектури паралельно-ієрархічного (ПІ) перетворення цифрових сигналів і методів формування масок при його реалізації. Запропоновано метод оптимізованого формування масок при ПІ перетворенні для кодування інформації та розроблено програмний комплекс, в якому підвищено швидкість прямого та зворотнього ПІ перетворення інформації без її втрат. An analysis of structural-functional organization of the network architecture of parallel-hierarhical transformation and mask generation methods has been performed. The method of optimized forming of masks by encoding information in parallel-hierarchical transformation is proposed. The software package with high speed performance of lossless direct and reversal parallel-hierarhical transformation of information has been developed. Данные исследования выполнены в рамках НИР № GP/F44/051 «Методы и средства организации высокопроизводительных параллельно-иерархических вычислительных процессов в интеллектуальных системах», которая осуществляется за счет бюджетных средств МОНМС Украины, предоставленных как грант Президента Украины для поддержки научных исследований молодых ученых. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Информационные технологии Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов Article published earlier |
| spellingShingle | Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов Тимченко, Л.И. Яровой, А.А. Кокряцкая, Н.И. Информационные технологии |
| title | Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов |
| title_full | Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов |
| title_fullStr | Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов |
| title_full_unstemmed | Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов |
| title_short | Теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов |
| title_sort | теоретические и прикладные аспекты параллельноиерархического многоуровневого преобразования цифровых сигналов |
| topic | Информационные технологии |
| topic_facet | Информационные технологии |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/100837 |
| work_keys_str_mv | AT timčenkoli teoretičeskieiprikladnyeaspektyparallelʹnoierarhičeskogomnogourovnevogopreobrazovaniâcifrovyhsignalov AT ârovoiaa teoretičeskieiprikladnyeaspektyparallelʹnoierarhičeskogomnogourovnevogopreobrazovaniâcifrovyhsignalov AT kokrâckaâni teoretičeskieiprikladnyeaspektyparallelʹnoierarhičeskogomnogourovnevogopreobrazovaniâcifrovyhsignalov |