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

Корисна модель відноситься до автоматики і обчислювальної техніки і може бути використана в операційних схемах аналогових процесорів. Відомий спосіб паралельного додавання тривалостей групи часових інтервалів [а.с. СРСР 388269, кл. G06G7/14, 1971p.], який базується на накопиченні кратних тривалостей і полягає в тому, що для кожного часового інтервалу групи виділяють шляхом диференціювання моменти часу його початку і кінця, за виділеними моментами часу визначають поточне значення різниці між сумою моментів часу закінчення інтервалів групи, тривалість найбільшого часового інтервалу групи перетворюють в послідовність кратних тривалостей шляхом множення її на це значення різниці, а отримані кратні тривалості накопичують. Недоліком цього способу є обмежені функціональні можливості, оскільки в ньому не реалізується сортування тривалостей первісної групи часових інтервалів. Найбільш близьким за технічною суттю є спосіб паралельного додавання тривалостей групи часових інтервалів [а.с. 1119035 СРСР, кл. G06G7/14, 1984p.], оснований на накопиченні кратних тривалостей, причому порівнюють між собою тривалості часових інтервалів гр упи і виділяють часовий інтервал найменшої тривалості, формують тривалість, кратну цій найменшій тривалості шляхом множення її на кількість часових інтервалів в групі, формують нову гр упу часови х інтервалів шля хом віднімання цієї найменшої тривалості від тривалості кожного часового інтервалу попередньої групи, далі вказані дії повторюють для кожної нової групи часових інтервалів до виділення інтервалу найменшої тривалості, що дорівнює нулю, а отримані кратні тривалості послідовно підсумовують. Недоліком цього способу є обмеження функціональних можливостей через те, що він не забезпечує одночасно з додаванням відсортування тривалостей первісної групи часових інтервалів. В основу корисної моделі поставлена задача вдосконалення способу паралельного додавання тривалостей групи часових інтервалів, в якому в результаті введення нових дій досягається розширення функціональних можливостей за рахунок відсортування тривалостей первісної групи часових інтервалів. Поставлена задача вирішується тим, що у способі паралельного додавання і сортування тривалостей групи часових інтервалів, основаному на накопиченні кратних тривалостей, причому порівнюють між собою тривалості часових інтервалів групи і виділяють часовий інтервал найменшої тривалості, формують тривалість, кратну цій найменшій тривалості шляхом множення її на кількість часових інтервалів в гр упі, формують нову гр уп у часових інтервалів шляхом віднімання цієї найменшої тривалості від тривалості кожного часового інтервалу попередньої групи, далі вказані дії повторюють для кожної нової групи часових інтервалів до виділення інтервалу найменшої тривалості, що дорівнює нулю, а отримані кратні тривалості послідовно підсумовують, згідно з корисною моделлю, послідовно підсумовують найменші тривалості, значення сум яких на кожному кроці оброблення представляють собою відповідні тривалості відсортованої групи часових інтервалів. На Фіг.1 подана блок-схема пристрою для додавання і сортування тривалостей групи часових інтервалів, на Фіг.2 схематично представлено приклад паралельного додавання і сортування тривалостей групи часових інтервалів. Паралельне додавання і сортування тривалостей групи часових інтервалів здійснюється таким чином. На першому кроці для первісної (першої) групи часових інтервалів порівнюють між собою тривалості цих інтервалів і виділяють часовий інтервал найменшої тривалості. Цю найменшу тривалість перетворюють в кратну їй тривалість шляхом множення отриманої найменшої тривалості на кількість часових інтервалів у первісній групі, а також формують нову (другу) гр упу часових інтервалів шляхом віднімання отриманої найменшої тривалості від кожного часового інтервалу попередньої групи. Визначена найменша тривалість є першим часовим інтервалом відсортованої групи часових інтервалів. Для другої гр упи часових інтервалів вказані дії повторюють, а саме, порівнюють між собою тривалості інтервалів другої групи і виділяють новий часовий інтервал найменшої тривалості. Потім формують тривалість, кратну поточній найменшій тривалості шляхом множення цієї найменшої тривалості на кількість часових інтервалів у другій групі, а також формують третю групу часових інтервалів шля хом віднімання поточної найменшої тривалості від тривалості кожного часового інтервалу другої групи.Підсумовують поточну і попередню найменші тривалості і формують поточний (другий) часовий інтервал відсортованої групи часових інтервалів. Далі послідовність дій повторюють для кожної нової групи часових інтервалів до виділення інтервалу найменшої тривалості, що дорівнює нулю. Отримані для кожної групи часових інтервалів кратні тривалості накопичують шляхом їх послідовного підсумовування. Пристрій, що реалізує спосіб (Фіг.1), містить входи 1 1, 12, ..., 1n (де n - максимальна кількість часових інтервалів в гр упі), на які подають тривалості часових інтервалів первісної (першої) гр упи, блоки 21, 22, …, 2n порівняння, з допомогою яких виділяють різниці між тривалостями окремих інтервалів групи та інтервалами найменшої тривалості, блок 4 послідовного підсумовування (накопичення) кратних тривалостей, в якому також виконують множення найменших тривалостей на кількість часових інтервалів у поточній групі, блок 5 накопичення інтервалів найменшої тривалості, вихід 6 результату додавання і вихід 7 результату сортування тривалостей групи часових інтервалів. Розглянемо приклад паралельного додавання тривалостей групи з п'яти часових інтервалів. Додають інтервали з тривалостями, які дорівнюють (11, 3, 5, 8, 15). П'ять тривалостей подають відповідно на входи 11, …, 15 задаючи вхідну гр упу для додавання. Оскільки у початковому стані на виході блока 3 присутній нульовий сигнал, то на першому кроці додавання від кожної тривалості первісної групи віднімають нуль з блока 3 і на виходах блоків 21, …, 2 5 формують різниці, що утворюють першу групу і фактично дорівнюють тривалостям часових інтервалів первісної групи (11,3, 5, 8, 15). Ці тривалості паралельно подають по п'яти входах на блок 3, де формують інтервал мінімальної ненульової тривалості, що дорівнює 3. Цю тривалість подають на блок 4, де відбувається утворення поточної часткової тривалості 15, кратність якої визначають кількістю додатних ненульових тривалостей першої групи, і одночасно на блок 5, звідки подають на вихід 7 результату сортування тривалостей групи часових інтервалів як першу тривалість відсортованої групи часових інтервалів. На другому кроці у блоках 21, …, 25 формують різниці між тривалостями часових інтервалів (11, 3, 5, 8, 15) першої групи і мінімальною тривалістю першої групи, що дорівнює 3. Формують значущі різниці (8, 2, 5, 12), що утворюють другу груп у. Мінімальну ненульову тривалість часових інтервалів другої групи, що дорівнює 2, формують у блоці 3 і подають на блок 4, де формують поточну часткову тривалість в чотирикратному розмірі, тобто 8, кратність якої визначають кількістю додатних ненульових тривалостей другої групи. Цю тривалість підсумовують в блоці 4 з частковою тривалістю першої групи, в даному випадку з 15, і формують накопичену часткову тривалість 23. У блоці 5 поточну мінімальну тривалість 2 додають до мінімальної ненульової тривалості першої групи, що дорівнює 3, а сум у, що дорівнює 5, подають на вихід 7 результату сортування тривалостей групи часових інтервалів як другу тривалість відсортованої групи часових інтервалів. На третьому кроці у блоках 21, …, 2 5 формують різниці між тривалостями часових інтервалів (8, 2, 5, 12) другої групи і мінімальною тривалістю другої групи, що дорівнює 2. Формують значущі різниці (6, 3, 10), що утворюють третю групу. Мінімальну ненульову тривалість часових інтервалів третьої групи, що дорівнює 3, формують у блоці 3 і подають на блок 4, де формують поточну часткову тривалість в трикратному розмірі, тобто 9, кратність якої визначають кількістю додатних ненульових тривалостей третьої групи. Цю тривалість підсумовують в блоці 4 з отриманою на попередньому кроці сумою поточних часткових тривалостей, що дорівнює 23, і формують накопичену часткову тривалість 32. У блоці 5 поточну мінімальну тривалість 3 додають до отриманої на попередньому кроці суми мінімальних ненульових тривалостей, що дорівнює 5, а результат, що дорівнює 8, подають на вихід 7 результату сортування тривалостей групи часових інтервалів як третю тривалість відсортованої групи часових інтервалів. На четвертому кроці у блоках 21, …, 25 формують різниці між тривалостями часових інтервалів (6, 3, 10) третьої групи і мінімальною ненульовою тривалістю третьої групи, що дорівнює 3. Формують значущі різниці (3, 7), що утворюють четверту гр упу. Мінімальну ненульову тривалість часових інтервалів четвертої групи, що дорівнює 3, формують у блоці 3 і подають на блок 4, де формують поточну часткову тривалість у двократному розмірі, що дорівнює 6, кратність якої визначають кількістю додатних ненульових тривалостей четвертої групи. Цю тривалість підсумовують в блоці 4 з отриманою на попередньому кроці сумою поточних часткових тривалостей, що дорівнює 32, і формують накопичену часткову тривалість 38. У блоці 5 поточну мінімальну тривалість 3 додають до отриманої на попередньому кроці суми мінімальних ненульових тривалостей, що дорівнює 8, а результат, що дорівнює 11, подаються на вихід 7 результату сортування тривалостей групи часових інтервалів як четверту тривалість відсортованої групи часових інтервалів. На п'ятому кроці у блоках 21, …, 25 формують різниці між тривалостями часових інтервалів (3, 7) четвертої групи і мінімальною ненульовою тривалістю четвертої групи, що дорівнює 3. Формують значущу різницю (4), що утворює п'яту гр уп у. Мінімальну ненульову тривалість часового інтервалу п'ятої групи, що дорівнює 4, формують у блоці 3 і подають на блок 4, де формують поточну часткову тривалість в однократному розмірі, що дорівнює 4, кратність якої визначається кількістю додатних ненульових тривалостей п'ятої групи. Цю тривалість підсумовують в блоці 4 з отриманою на попередньому кроці сумою поточних часткових тривалостей, що дорівнює 38, і формують накопичену часткову тривалість 42. У блоці 5 поточну мінімальну тривалість 3 додають до отриманої на попередньому кроці суми мінімальних ненульових тривалостей, що дорівнює 11, а результат, що дорівнює 15, подають на вихід 7 результату сортування тривалостей групи часових інтервалів як п'яту тривалість відсортованої групи часових інтервалів. На шостому кроці у блоках 21, …, 25 формують нульову різницю, внаслідок чого процес оброблення припиняють, оскільки блоком 3 формують нульову мінімальну тривалість. Отже, сформована на п'ятому кроці накопичена часткова тривалість 42 є остаточною сумою тривалостей первісної групи часових інтервалів. Запропонований спосіб сортування тривалостей групи часових інтервалів можна представити таким чином: i ai,0 = å q j, i = 1 n , (1) j=1 де ai,0 - і-та тривалість первісної групи А0 часових інтервалів; n - кількість часових інтервалів первісної групи; qj - мінімальна тривалість на j-му кроці оброблення. Доведемо слушність виразу (1) за умови, що тривалості часових інтервалів первісної групи А0 різні за значенням, додатні і впорядковані за величиною, тобто (2) a i,0 < a 2, 0 < ... < a i, 0 < ... < a n,0 . За визначенням { }n=1, i n n A j = { i, j } = { i, j -1 - q j } . a a i =1 i =1 q j = min A j -1 = min ai, j -1 (3) (4) Використовуючи метод математичної індукції, можна довести, що (5) q 1 = a j, 0 - a j -1,0 . Тоді, приймаючи до уваги співвідношення (3)-(5), отримаємо å q j = å (a j,0 - a j-1,0 ) = (a1,0 - a 0,0 ) + (a 2,0 - a1,0 ) + ... + (ai -1,0 - ai - 2,0 ) + (ai,0 - ai -1,0 ) = ai,0 - a0,0 = ai,0 , i i j =1 j -1 оскільки a0,0=0 через те, що ця тривалість відсутня у первісній групі А0 часови х інтервалів (2). Отже, справедливість використання виразу (1) аналітично доведена.