Спосіб порогового паралельного додавання тривалостей групи часових інтервалів

Винахід відноситься до автоматики та обчислювальної техніки та може бути використаний в обчислювальних пристроях для процесу порогового оброблення масиву чисел, зокрема при моделюванні нейронних та нейроподібних мереж. Відомий спосіб паралельного додавання тривалостей групи часових інтервалів (а. с. СРСР № 388269, кл. G 06 G 7/14, 1971), який оснований на накопиченні кратних тривалостей і полягає в тому, що для кожного часового інтервалу групи виділяють шляхом диференціювання моменти часу його початку і кінця, за виділеними моментами часу визначають поточне значення різниці між сумою моментів часу початку часових інтервалів групи і сумою моментів часу закінчення інтервалів групи, тривалість найбільшого часового інтервалу групи перетворюють у послідовність кратних тривалостей шля хом її множення на отримане значення різниці, при цьому кратні тривалості накопичують. Недоліком даного способу є обмежені функціональні можливості через формування з малою точністю суми тривалостей початкової групи. Відомий спосіб паралельного додавання тривалостей групи часових інтервалів (а. с. СРСР № 1119035, кл. G 06 G 7/14, 1984), який оснований на накопиченні кратних тривалостей, причому порівнюють між собою тривалості часових інтервалів групи і виділяють часовий інтервал найменшої тривалості, формують тривалість, яка в подальшому позначається як поточна часткова тривалість і є кратною цій найменшій тривалості, шляхом її множення на кількість часових інтервалів у групі, формують нову групу часови х інтервалів шляхом віднімання цієї найменшої тривалості від тривалості кожного часового інтервалу попередньої групи, далі зазначені дії повторюють для кожної нової групи часових інтервалів до виділення інтервалу найменшої тривалості, який дорівнює нулю, а отримані кратні тривалості послідовно підсумовують. Недоліком даного способу є обмежені функціональні можливості, оскільки спосіб додавання тривалостей групи часових інтервалів використовується лише для формування суми тривалостей початкової групи. Найбільш близьким по технічний суті до способу, який пропонується, є спосіб порогового паралельного додавання тривалостей групи часових інтервалів (патент України 40228 А, кл. G 06 G 7/14, 2001), який оснований на накопиченні кратних тривалостей, в якому між собою порівнюють тривалості часових інтервалів групи та виділяють часовий інтервал найменшої тривалості, формують поточну часткову суму тривалостей, яка в подальшому позначається як поточна часткова тривалість, що кратна цій найменшій тривалості, шляхом множення її на кількість часових інтервалів в гр упі, формують нову гр упу часових інтервалів, яка в подальшому позначається як поточна група часових інтервалів, шляхом віднімання цієї найменшої тривалості із тривалості кожного часового інтервалу попередньої групи, далі вказані дії повторюються для кожної нової поточної групи часових інтервалів, а отримані кратні тривалості послідовно підсумовують, на кожному кроці обробки виконують порівняння суми поточних часткових тривалостей із порогом обробки і формують поточний підсумковий сигнал, який дорівнює одиниці, якщо сума поточних часткових тривалостей гр упи часових інтервалів більше або дорівнює порогу обробки, і дорівнює нулю у протилежному випадку, при цьому вказані дії повторюються до формування підсумкового сигналу, що дорівнює одиниці або, у протилежному випадку, до виділення інтервалу найменшої тривалості, який дорівнює нулю. Недоліком даного способу є те, що в ньому на кожному кроці обробки отримані кратні тривалості послідовно підсумовуються, тобто формується сума поточних часткових тривалостей, що в свою чергу, збільшує час оброблення. В основу винаходу поставлено задачу створення способу порогового паралельного додавання тривалостей групи часових інтервалів, в якому за рахунок введення нових дій досягається на кожному кроці оброблення можливість формування поточних часткових різниць тривалостей групи часових інтервалів, а також формування поточного порогу для наступного кроку оброблення шляхом послідовного віднімання від поточного порогу поточної мінімальної тривалості кількістю, що дорівнює кількості додатних ненульових тривалостей у поточній групі часових інтервалів, і формування підсумкового сигналу, що дорівнює одиниці тільки тоді, коли поточна часткова різниця менше або дорівнює нулю, що дозволяє завершити процес оброблення при наявності одиничного підсумкового сигналу без формування поточного порогу на цьому кроці оброблення, що призводить до прискорення способу за рахунок скорочення часу визначення від'ємної поточної часткової різниці. Поставлена задача вирішується тим, що у способі порогового паралельного додавання тривалостей групи часових інтервалів, в якому порівнюють між собою тривалості часових інтервалів групи і виділяють часовий інтервал найменшої тривалості, формують нову поточну груп у часових інтервалів шля хом віднімання цієї найменшої тривалості від тривалості кожного часового інтервалу попередньої групи, формують поточний підсумковий сигнал, далі зазначені дії повторюють для кожної нової поточної групи часових інтервалів до формування підсумкового сигналу, що дорівнює одиниці, або у протилежному випадку до виділення інтервалу найменшої тривалості, який дорівнює нулю, при цьому на кожному кроці оброблення визначають кількість додатних ненульових тривалостей у поточній групі часових інтервалів, а також виконують порівняння отриманої поточної мінімальної тривалості із поточним порогом і формують новий поточний поріг шляхом послідовного віднімання від поточного порогу поточної мінімальної тривалості кількістю, що дорівнює кількості додатних ненульових тривалостей у поточній групі часових інтервалів, при цьому послідовно отримують поточні часткові різниці тривалостей, а поточний підсумковий сигнал дорівнює одиниці, якщо отримана поточна часткова різниця є від'ємною або нульовою величиною, і дорівнює нулю, якщо отримана поточна часткова різниця є додатною величиною, причому на першому кроці порівняння виконують із заданим порогом шляхом послідовного віднімання від нього поточної мінімальної тривалості. На фіг.1 зображена блок-схема пристрою, який реалізує спосіб порогового паралельного додавання тривалостей групи часових інтервалів, на фіг. 2 схематично представлено варіант порогового паралельного додавання тривалостей групи часових інтервалів, які дорівнюють 11, 3, 5, 8, 15 і порогу, що дорівнює 28. Пристрій (фіг. 1), що реалізує даний спосіб порогового паралельного алгебраїчного додавання тривалостей групи часових інтервалів, містить: входи 11, ..., 1n тривалостей часових інтервалів первісної групи, схеми 21, ..., 2n віднімання (де n - максимальна кількість тривалостей в групі часови х інтервалів) для виділення різниці між тривалостями окремих інтервалів групи та інтервалом найменшої тривалості поточної групи, схему 3 порівняння для виділення інтервалу найменшої тривалості поточної групи, схему 4 формування поточних часткових різниць тривалостей. Перший вхід 5 схеми 4 є входом порогового значення пристрою, вихід 6 схеми 4 є виходом пристрою, другі входи схем 21, ..., 2n віднімання з'єднані з виходом 7 схеми 3 порівняння, який також підключений до другого входу схеми 4, а інформаційні виходи 81, ..., 8n схем 21,..., 2n віднімання з'єднані з входами схеми 3 порівняння і першою групою входів схем 21, ..., 2 n віднімання, які також підключені до входів 1 1, ..., 1n пристрою. Виходи групи ознак схем 21, ..., 2n віднімання з'єднані з групою входів 91,..., 9n схеми 4, вихід 10 якої підключений до входу 5 схеми 4. Порогове паралельне додавання тривалостей групи часових інтервалів виконується в такий спосіб. На першому кроці порівнюють між собою тривалості часових інтервалів групи і виділяють часовий інтервал найменшої тривалості. Формують поточні часткові різниці тривалостей шляхом послідовного віднімання від заданого порогу поточної мінімальної тривалості кількістю, що дорівнює кількості додатних ненульових тривалостей у поточній першій групі часових інтервалів. Якщо якась отримана поточна часткова різниця виявляється від'ємною або рівною нулю, то процес оброблення припиняється з формуванням одиничного підсумкового сигналу. У протилежному випадку формується нульовий підсумковий сигнал і процес оброблення продовжується. Остання отримана поточна часткова різниця буде використовуватись як поточний поріг на наступному кроці оброблення. На другому кроці у другій групі часових інтервалів, яка формується шляхом віднімання найменшої тривалості від тривалості кожного часового інтервалу попередньої (першої) групи, повторюють зазначені дії, а саме: порівнюють між собою тривалості часових інтервалів другої групи і виділяють часовий інтервал найменшої тривалості. Формують поточні часткові різниці тривалостей шляхом послідовного віднімання від поточного порогу поточної мінімальної тривалості кількістю, що дорівнює кількості додатних ненульових тривалостей у поточній другій гр упі часових інтервалів. Якщо якась отримана поточна часткова різниця виявляється від'ємною або рівною нулю, то процес оброблення припиняється з формуванням одиничного підсумкового сигналу. У протилежному випадку формується нульовий підсумковий сигнал і процес оброблення продовжується. Остання отримана поточна часткова різниця буде використовуватись як поточний поріг на наступному кроці оброблення. Зазначені дії повторюють на кожному кроці оброблення для кожної нової групи часових інтервалів до формування підсумкового сигналу, що дорівнює одиниці, або, у протилежному випадку, до виділення інтервалу найменшої тривалості, який дорівнює нулю. Отже, на першому кроці оброблення проводиться порівняння із заданим порогом, який задається на початку процесу додавання. При цьому, якщо значення поточної часткової різниці між поточним порогом та поточною мінімальною тривалістю від'ємне або дорівнює нулю, то процес оброблення припиняється. Починаючи з другого кроку поточне значення порогу буде приймати значення останньої поточної різниці між поточним порогом та поточною мінімальною тривалістю, отриманими на попередньому кроці. Розглянемо порогове паралельне додавання тривалостей групи, яка складається, наприклад, із п'яти часових інтервалів (фіг. 1). Додаються інтервали з тривалостями, які дорівнюють 11, 3, 5, 8, 15, а значення порогу дорівнює 28 (фіг. 2). Дані п'ять тривалостей подаються відповідно на входи 1 1, ..., 15, внаслідок чого створюється первісна група для додавання. Оскільки в початковому стані на виході 7 схеми 3 порівняння присутня нульова тривалість, то на першому кроці оброблення від кожної початкової тривалості віднімається нуль зі схеми 3 порівняння, і на виходах 81, ..., 85 схем 21, ..., 25 формуються різниці, які фактично дорівнюють початковим тривалостям часових інтервалів. Ці тривалості, які дорівнюють 11, 3, 5, 8, 15, паралельно подаються на п'ять входів схеми 3 порівняння, де відбувається виділення інтервалу найменшої ненульової тривалості з поданих п'яти інтервалів, тобто утворюється мінімальна тривалість, а саме 3. Ця тривалість подається з виходу 7 схеми 3 порівняння на вхід схеми 4 формування поточних часткових різниць тривалостей, де формується перша поточна часткова різниця тривалостей 25 (28-3 = 25) в результаті віднімання від заданого порогу найменшої тривалості поточної групи часових інтервалів. Кількість можливих поточних часткових різниць тривалостей визначається кількістю одиничних сигналів на входах 9 1, ..., 95 схеми 4 формування поточних часткових різниць тривалостей. Одиничні сигнали на цих входах формуються при наявності ненульових додатних тривалостей на вихода х 81 ,..., 85 відповідних схем 21,..., 25 віднімання. Отже, їх кількість на першому кроці оброблення дорівнює 5. На виході 6 пристрою присутній нульовий підсумковий сигнал, оскільки перша поточна часткова різниця додатня (25>0). Сформована перша поточна часткова різниця 25 з виходу 10 схеми 4 подається на її перший вхід 5 і формується друга поточна часткова різниця 22 (25-3=22). На виході 6 пристрою присутній нульовий підсумковий сигнал (22>0). Сформована друга поточна часткова різниця 22 з виходу 10 схеми 4 подається на її перший вхід 5 і формується третя поточна часткова різниця 19 (22-3=19). На виході 6 пристрою присутній нульовий підсумковий сигнал (19>0). І так дані дії повторюються до отримання останньої п'ятої поточної часткової різниці, якщо до цього не буде від'ємної або нульової поточної часткової різниці. Тобто, отримуємо четверту поточн у часткову різницю 16 (19-3=16>0) і п'яту поточну часткову різницю 13 (16-3=13>0), які є додатними. Остання поточна часткова різниця 13 є поточним порогом на другом кроці оброблення. На другому кроці у схемах 21,..., 25 формуються різниці між початковими тривалостями 11, 3, 5, 8, 15 та мінімальною тривалістю першої групи, яка дорівнює 3. Утворюються різниці 8, 0, 2, 5, 12 другої групи. Найменша ненульова тривалість часового інтервалу другої групи, яка дорівнює 2, формується в схемі 3 порівняння і подається з виходу 7 на схему 4 формування поточних часткових різниць тривалостей, де передбачається формування за кількістю одиничних сигналів на входах 91,..., 95 чотирьох поточних часткових різниць. Спочатку формується перша часткова різниця тривалостей 11 (13 -2 = 11). На виході 6 пристрою присутній нульовий підсумковий сигнал (11>0). Сформована перша поточна часткова різниця 11 з виходу 10 схеми 4 подається на її перший вхід 5 і формується друга поточна часткова різниця 9(11-2=9). На виході 6 пристрою присутній нульовий підсумковий сигнал (9>0). І так дані дії повторюються до отримання четвертої поточної часткової різниці, оскільки всі поточні часткові різниці на даному кроці також додатні: третя поточна часткова різниця 7 (9-2;=7>0), четверта поточна часткова різниця 5 (7-2=5>0). Остання поточна часткова різниця 5 є поточним порогом на третьому кроці оброблення. На третьому кроці у схемах 21, ..., 25 формуються різниці між тривалостями 8, 0, 2, 5, 12 та мінімальною тривалістю другої групи, яка дорівнює 2. Утворюються різниці 6, -, 0, 3, 10 третьої групи (знаком "-" позначається від'ємне значення тривалості). Найменша ненульова тривалість часового інтервалу третьої гр упи, яка дорівнює 3, формується в схемі З порівняння і подається з виходу 7 на схему 4 формування поточних часткових різниць тривалостей, де передбачається послідовне формування за кількістю одиничних сигналів на входах 91, ..., 95 трьох поточних часткових різниць тривалостей. Спочатку формується перша часткова різниця тривалостей 2 (53=2). На виході 6 пристрою присутній нульовий підсумковий сигнал (2>0). Сформована перша поточна часткова різниця 2 з виходу 10 схеми 4 подається на її перший вхід 5 і формується друга поточна часткова різниця -1 (2-3= -1). На виході 6 пристрою формується одиничний підсумковий сигнал (-1>0) і процес оброблення припиняється. Отже, замість формування передбачених трьох поточних часткових різниць на третьому кроці формується лише дві, що зменшує час цього кроку оброблення. Математичну модель запропонованого способу порогового паралельного оброблення можна представити таким чином: n ì , ï1 якщо å (ai ) ³ p y =í i= 1 (1) ï 0 в протилежно випадку, му î де у - підсумковий сигнал, р - поріг, aі - і-та тривалість часових інтервалів первісної групи, n - кількість тривалостей у гр упі часових інтервалів. Якщо суму S тривалостей часових інтервалів первісної групи можна представити у вигляді n S = å (ai ) = S1 + S 2 + ... + SN , i=1 де Sj - поточна часткова сума, сформована на j-му кроці оброблення, причому j = 1 N, то величину D = p - S , можна визначити таким чином D = p - S = p - (S1 + S 2 + ... + S N ) = p - S 1- - S 2 - ... - SN = (... ((p - S1 ) - S 2 ) - ... - S N ) £ 0. (2) Введемо позначення для поточного порогу D j = D j-1 - S j £ 0, j = 1 N (3) , де D 0 = p . В той же час величину Sj можна представити у такий спосіб S j = q j × d j, де qj - поточна мінімальна тривалість на j-му кроці, dj - кількість додатних ненульових тривалостей у поточній групі часових інтервалів. Тоді вираз (2) можна записати так: D = [...[[ p - (q1 + q1 + ... q1 ) ] - (q2 + q 2 + ... + q2 ) ] - ... - (qN + qN + ... + qN ) ] = 144 443 2 144424443 1444 444 2 3 d1 d2 dN é ù ê ú é ù êê ú ú ê é ú ù ú êêê ú - q ) - q ) - ... - q )ú - ... - q ) - q ) - ... - q )ú, (4) = ê ê (...(p - q1 ) - q1 ) - ... - q1 ) 2 2 2 N N N ú ê 14444 24444 3 ú 4 4 ú êêê ú d1 ú 1 4 û 4 ê ê ë 4444444444 24444444444 3 ú ú ê ú d2 ê ë 44444444444444444 244444444444444444 3 ú û 1 4 4 ê ú dN ë û або [ [ ( (( ) ) ] ] ] ( D = ... ... ... p - q11) - q( 2) - ...q( d1 ) - q(1) - q(22 ) - ... - q(d2 ) - ... - q(2 ) - q( dN ) (5) 1 1 2 2 N N Якщо вираз у круглих дужках позначити як (k ) dj (k -1) = dj (k ) 0 - q j , k = 1, d j , d1 = p, (6) то поточний поріг (3) буде мати такий вигляд (d ) j D j = d j-1 , d 0 = D j-1. j Отже, на кожному кроці оброблення можна перевіряти виконання умови d (jk ) £ 0, а не тільки D j =£ 0, що дозволяє прискорити процес порогового оброблення.