Пристрій для визначення екстремумів сигналу

1. Пристрій для визначення екстремумів сигналу, який містить аналого-цифровий перетворювач, схему порівняння, блок пам'яті, перша вихідна шина якого підключена до першої групи входів схеми порівняння, блок керування і блок формування номерів порівнюваних дискрет, перша група входів якого поєднана з першою групою виходів блока керування, який містить три послідовно з'єднані лічильники та елемент збігу, причому виходи першого, другого та третього лічильників утворюють, відповідно, першу, другу та третю групи виходів блоку, а вихід елемента збігу, підключеного входами до виходу перенесення першого лічильника та лінії синхронізації, зв'язаний з виходом відбору дискрет блоку керування, який відрізняється тим, що у пристрій введено блок формування номера екстремальної дискрети, інформаційний і дві групи керуючих входів якого підключені, відповідно, до виходу схеми порівняння та першої і другої груп виходів блоку керування, які, відповідно, є першою групою виходів усього пристрою і другою групою входів блоку формування номерів порівнюваних дискрет, крім того, вхід при A (54) ПРИСТРІЙ ДЛЯ ВИЗНАЧЕННЯ ЕКСТРЕМУМІВ СИГНАЛУ 38129 першим виходом блоку пам'яті, другий вихід блоку пам'яті та вихід перетворювача аналог-код за допомогою комутатора поєднані зі входом схеми порівняння, керуючий вихід якої підключено до входу блока керування, перший вихід блоку формування чисел Фібоначчі підключено до другого виходу пристрою, а другий вихід поєднано з керуючими входами блоку пам'яті й перетворювача аналогкод, вхід блоку формування чисел Фібоначчі підключено до пристрою, керуючий вхід регістра екстремумів, перший та другий керуючі входи схеми порівняння, перший та другий керуючі входи блоку формування чисел Фібоначчі поєднані з відповідними виходами блоку керування (Див.: авторське свідоцтво СРСР № 736111, кл. G06F 15/34, 1980). Головний недолік даного пристрою - це виключно послідовне зчитування з пам'яті порівнюваних між собою дискретних значень (дискрет) сигналу, причому із переміщенням носія дискрет тільки в одну з двох можливих сторін, що принципово робить неможливою організацію швидкого пошуку, особливо у реальному масштабові часу, з метою задовольняння сучасних вимог до систем контролю якості продукції й керування технологічними процесами на виробництві. До того ж, застаріла елементно-конструктивна база дозволяє здійснювати черговий крок пошуку лише протягом декількох тактів, що суттєво обмежує швидкодію. Задача винаходу - підвищення ефективності шляхом збільшення як швидкодії, так і коефіцієнта використання залученого обладнання. Ця задача досягається завдяки тому, що в пристрій, який містить аналого-цифровий перетворювач, схему порівняння, блок пам'яті, перша вихідна шина якого підключена до першої групи входів схеми порівняння, блок керування і блок формування номерів порівнюваних дискрет, перша група входів якого поєднана з першою групою виходів блоку керування, додатково введено блок формування номеру екстремальної дискрети, інформаційний і дві групи керуючих входів якого підключені, відповідно, до виходу схеми порівняння та першої і другої груп виходів блоку керування, які, відповідно, є першою групою виходів усього пристрою і другою групою входів блоку формування номерів порівнюваних дискрет, крім того, вхід пристрою через аналого-цифровий перетворювач підключено до інформаційних входів блоку пам'яті, перша та друга адресні шини якого підключені до відповідних груп виходів блоку формування номерів порівнюваних дискрет, третя адресна шина до другої групи виходів блоку керування, а друга інформаційна вихідна шина підключена до другої групи входів схеми порівняння, вихід відбору дискрет блоку керування підключено до керуючого входу аналого-цифрового перетворювача та до синхровходу блоку пам'яті, а вихід скидання блоку керування - до керуючого входу блока формування номера екстремальної дискрети, третя група виходів блоків керування служить другою групою виходів усього пристрою. Крім того, блок формування номеру екстремальної дискрети містить послідовно з'єднані дешифратор, регістр й постійний запам'ятовуючий пристрій, виходи якого утворюють першу групу виходів блоку, причому перша та друга групи керуючих входів блоку підключені до, відповідно, інформаційних та стробувальних входів дешифратора, виходи якого поєднані зі входами дозволу запису відповідних D-тригерів паралельного регістра, інформаційні входи яких пов'язані з інформаційним входом блоку, а інформаційні виходи - зі входами постійного запам'ятовуючого пристрою, до того ж інформаційні виходи всіх D-тригерів регістра, окрім найстаршого, утворюють другу групу виходів блоку, а їхній спільний вхід обнуління є керуючим входом блоку. На фіг. 1 наведена схема пристрою, на фіг. 2 всі можливі алгоритмічні реалізації m-крокового пошуку (m = 5) у межах 2n-компонентної вибірки (n = 4). Пристрій містить аналого-цифровий перетворювач 1, блок 2 формування номерів порівняльних дискрет, блок 3 пам'яті, схему 4 порівняння, блок 5 формування номеру екстремальної дискрети, який складається з дешифратора 6, паралельного регістра 7 і постійного запам'ятовуючого пристрою 8 та блок керування 9, до складу котрого входять лічильник 10 за модулем m числа кроків пошуку, nрозрядний двоїстий лічильник 11 обсягу 2n дискрет чергової вибірки та двоїстий лічильник 12 номеру вибірки. Блок 2 формування номерів порівнюваних дискрет реалізований за допомогою постійних запам'ятовуючих пристроїв ПЗП1 та ПЗП2 з (m-1)+d адресними входами, причому d=]log2m[, де ]х[ найбільше до х зверху ціле число, та n інформаційними виходами. У табл. 1 наведений приклад програмування вмісту ПЗП1 і ПЗП2 у випадку пошуку максимальної з 2n = 16 (n = 4) дискрет чергової вибірки, що реалізується із залученням m = 5 кроків, причому за допомогою (y)2 вказується значення у в двоїстій системі лічення. Блок 3 пам'яті являє собою регістровий файл (див. стор. 232 у книзі: Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных мікросхемах. Справ очник. - М.: Радио и связь, 1990. - 304 с.) з одним портом уведення даних DI1¸DIk та двома портами виведення даних DOA1¸DOAk і DOB1¸DOBk. Адресація регістрів пам'яті файлу при записуванні призводиться сигналами AW1...AWn, а при читанні порту DOA1DOAk (або DOB1-DOBk) - сигналами ARA1¸ARAn (або ARB1¸ARBn); запис даних до регістрового файлу синхронна (за встановленою попередньою адресою), а зчитування даних - асинхронне (при зміні адреси читання нові дані відразу ж з'являються на виході). Блок 5 формування номера екстремальної дискрети містить послідовно з'єднані дешифратор 6 із d інформаційними та n стробовими входами й m виходами, m-розрядний паралельний регістр 7 на D-тригерах зі входами Е дозволу доступу, постійний запам'ятовуючий пристрій 8 із m адресними входами та n інформаційними виходами, приклад програмування якого наведений у табл. 2 для n = 4 та m = 5. Блок 9 керування складається з послідовно з'єднаних: лічильника 10 за модулем m числа кроків пошуку, лічильника 11 дискрет чергової вибірки обсягом 2n, лічильника 12 номера поточної вибірки у діапазоні 0¸2r-1. Елемент збігу 13 призначений для формування сигналу відбору чергової дискре 2 38129 ти аналізованої вибірки. Запропонований пристрій реалізує модифікацію відомого алгоритму пошуку Фібоначчі, яка принципово відрізняється кількістю дискрет в складі аналізованих інтервалів невизначеності місцезнаходження екстремуму на кожному кроці, і передусім, на першому, де досліджується унімодальний сигнал, який зображений не Fk, а 2n своїми дискретами (відліками), причому Fk > 2n, (n - ціле число, a Fk - k-й член числової послідовності Фібоначчі 1, 2, 3, 5, 8, 13, 21, 34,...) Ступінь двійки являє собою типове значення багатьох конструктивних параметрів засобів цифрової обробки сигналів, визначаючи, зокрема, інформаційну місткість сегментів, сторінок, блоків та мікросхем пам'яті, а також ширину інтерфейсних шин, кількість входів у мультиплексорів та виходів у демультиплексорів і т.д. Тому обиране число дискрет в аналізованій вибірці вимірювального сигналу дозволяє, з одного боку, скоротити обсяг залученого обладнання, а відповідно, і його вартість практично вдвічі, а, з іншого боку, - досягти 100%го використання залученого обладнання, що особливо важливо у випадку портативних засобів контролю. Зменшення кількості відліків у складі аналізованої вибірки вимірювального сигналу, призводить до необхідності модифікувати, для кожного із послідовних кроків, кількість дискрет у складі залишкового інтервалу невизначеності локалізації максимуму унімодального сигналу. При цьому, число кроків пошуку зберігається і навіть скорочується на одиницю в декількох випадках. У таблиці 3 запропоновані рекомендовані значення для кількості дискрет у складі інтервалів невизначеності на кожному кроці пошуку у випадку найбільш типових довжин початкової вибірки. Для випадку 2n = 16 відліків у початковій вибірці на фіг. 2 надані всі можливі алгоритмічні реалізації процедури пошуку із залученням запропонованої модіфікації алгоритму Фібоначчі. На першому кроці вибірка, що аналізується (з урахуванням довільності її вигляду), зображена номерами відліків з 0-го до (2n-1)-й; порівнювальні між собою відліки показані жирними вертикальними стрілками. Якщо більшим виявляється лівий відлік, наприклад, з номером 6 на фіг. 2, то вибірка відтинається справа, починаючи з другого із порівнюваних відліків, наприклад, з номером 9, як на фіг. 2. Якщо більшим є правий відлік, наприклад, з номером 9 на фіг. 2, то вибірка відтинається зліва, включаючи перший відлік, наприклад, з номером 6, як на фіг. 2. На другому кроці ця усічена вибірка відліків може аналізуватися на одному з двох, отриманих вказаним вище способом, підінтервапів, маючи, наприклад, по 9 відліків на фіг. 2. При цьому, порівнюються між собою: залучений на попередньому кроці старий відлік (вказаний звичайною вертикальною стрілкою) та новий відлік (вказаний жирною вертикальною стрілкою), розташований симетрично у межах аналізованого підінтервалу. За результатами порівняння здійснюється відтинання аналізованого підінтервалу зліва чи справа, завдяки чому подвоюється число підінтервалів для наступного кроку. На третьому кроці аналізується один з чоти рьох, знов отриманих підінтервалів, що містять, наприклад, по 6 відліків, як на фіг. 2. Для кожного з підінтервалів використовується старий відлік і симетрично йому обирається новий відлік, потім вони порівнюються і, за результатами порівняння, підінтервал відтинається зліва чи справа. На четвертому кроці може аналізуватися вже один з восьми підінтервалів, що мають, наприклад, 3 відліки, як на фіг. 2. При відтинанні І-го та ІІІ-го підінтервалів зліва, а II-го та IV-го - справа, отримуємо по два однакових підінтервали, наприклад, [3,5] та [10,12], як на фіг. 2. Тому, незважаючи на подвоєння кількості інтервалів, оригінальних серед них на четвертому кроці буде тільки 6. Якщо позначити номер кроку через і (і = 1, ..., m), то загальна кількість отриманих підінтервалів на кожному кроці дорівнює 2i-1. З підвищенням номера кроку зростає і кількість підінтервалів, котрі формуються двічі: шляхом відтину зліва чи справа різних, але частково накладених початкових інтервалів. На останньому, m-му кроці (m = 5 для випадку початкової вибірки з 24 = 16 дискрет як на фіг. 2) кожний з потенційно можливих підінтервалів має лише два відліки, котрі й порівнюються між собою з метою вибору найбільшого. Функціонування пристрою на фіг. 1 здійснюється наступним чином. Перед початком чергового циклу роботи виконується скид у нуль усіх тригерів регістру 7, а також лічильника 10 за mod m та двоїстих лічильників 11 та 12. Функціонування запропонованого пристрою полягає у повторенні m-крокової процедури пошуку для послідовних вибірок вимірювального сигналу, які містять по 2n дискрет. Накопичення чергової вибірки в блоці пам'яті 3 здійснюється наступним чином. Після надходження (m-1) синхроімпульсів до лічильника 10 за модулем m на його виході перенесення Р з'являється логічна одиниця, котра дозволяє проходженню mго синхроімпульсу через елемент збігу 13 на керуючий вхід паралельного аналого-цифрового перетворювача (АЦП) 1 та на синхровхід С порту запису блоку пам'яті 3. При цьому АЦП 1 формує чергову к-розрядну дискрету вимірювального сигналу, котра й завантажується до відповідного з 2n регістрів блоку пам'яті 3 по завершенню m-го такту. Одночасно інкримінується вміст лічильника 11, який вказує номер записаної дискрети у вибірці. При досягненні лічильником 11 стану (11...1), котрий вказує на останню дискрету у вибірці, на його виході перенесення Р з'являється логічна одиниця, котра обнулює паралельний регістр 7, а також забезпечує інкримент вмісту лічильника 12, котрий містить номер аналізованої вибірки. Після занесення до блоку пам'яті 3 всієї вибірки з 2n дискрет, лічильник 11 опиняється у нульовому стані, в якому й перебуває протягом m періодів синхропослідовності, котрі використовуються з метою реалізації m-крокової процедури пошуку. Нульовий вміст лічильника 11, надходячи на входи стробування дешифратора 6, дозволяє роботу останнього, котрий на основі аналізу номера кроку пошуку, що зберігається в лічильнику 10, дозволяє запис до відповідного D-тригера паралельного ре 3 38129 гістру 7. У процесі m-крокової процедури пошуку номера екстремальної дискрети у межах вибірки з номером, що міститься у регістрі 12, виконуються такі дії. У першому такті, коли реалізується перший крок пошуку, нульовими є вміст паралельного регістру 7, котрий надходить на молодші адресні входи ПЗП1 та ПЗП2 блоку формування номерів порівнювальних дискрет 2, та вміст лічильника 10 за mod m, який подається на старші адресні входи ПЗП1 та ПЗП2. Тому прочитується вміст комірок ПЗП1 та ПЗП2 з нульовою адресою, які і є двоїстими номерами порівнювальних дискрет, наприклад, (6)2 та (9)2 як на фіг. 2, а також у нульовому рядку таблиці 1. Ці номери потрапляють на адресні входи ARA1 ... ARAn та ARB1 ... ARBn, відповідно, першого та другого портів виводу блока пам'яті 3, завдяки чому забезпечується читання з блоку 3 обраних к-розрядних двоїстих кодів відліків, та передача їх на входи схеми порівняння 4. Якщо логічна одиниця формується на виході "£" схеми порівняння 4, то вона потрапляє на інформаційний вхід D всіх тригерів регістра 7. Проте, завдяки надходженню на адресні входи дешифратора 6 нульового вмісту лічильника 10 за mod m, ця логічна одиниця заноситься по завершенні такту до першого тригера паралельного регістру 7. Якщо логічна одиниця формується на виході ">" схеми порівняння 4, то перший тригер регістру 7 зберігає свій нульовий стан. Вміст першого тригеру паралельного регістру 7 надходить на старший адресний вхід ПЗП3 8, обираючи при цьому нижню чи верхню половини таблиці програмування ПЗП3, яка наведена у таблиці 2. На другому такті лічильник 10 за mod m містить комбінацію 001, а паралельний регістр 7 комбінацію 0000 або 1000. У своїй сукупності ці комбінації утворюють 7-розрядну адресу для ПЗП1 та ПЗП2, наведену у другому чи в третьому рядках таблиці 1, де також вказані двоїсті номери дискрет, які будуть порівнюватися. Ці номери, надходячи на адресні входи ARA1 ... ARAn та ARB1 ... ARBn портів виводу регістрового файлу 3, забезпечують передавання відповідних відліків із блоку пам'яті 3 на входи схеми порівняння 4. Сформований за результатами порівняння біт надходить на входи D тригерів паралельного регістру 7. Завдяки присутності комбінації 001 у лічильнику 10, цей біт, по закінченні такту, фіксується у другому тригері паралельного регістра 7, зазначаючи, спільно із вмістом першого тригеру 7, одну з чотирьох чвертей таблиці програмування ПЗП3, наданої у таблиці 2. Протягом останнього, m-ro такту, на якому виконується m-й крок пошуку, лічильник 10 містить двоїсту комбінацію (m-1)2, а в (m-1) молодших тригерах паралельного регістра 7 зберігається певна комбінація з нулів та одиниць. Обидві ці двоїсті комбінації у своїй сукупності утворюють адресу конкретної комірки ПЗП1 та ПЗП2, яка знаходиться в останній частині таблиці програмування, напри клад, для і = 5 у таблиці 1. Адреси порівнювальних комірок ПЗП1 та ПЗП2 визначають: які з сусідніх відліків, котрі зберігаються в блоці 3 пам'яті, передаються на схему 4 порівняння. Сформований за результатами порівняння біт надходить до старшого, m-го тригеру паралельного регістра 7, де по закінченні такту, з'являється m-розрядна комбінація, яка вказує на адресу комірки ПЗП3, де й зберігається номер екстремальної дискрети. Вміст регістру 7 зберігається на виходах пристрою протягом m(2n-1) тактів синхропослідовності (протягом котрих у блоці 3 пам'яті накопичується наступна вибірка дискрет), тому надається достатній час для прочитування зовнішніми пристроями номеру екстремальної дискрети спільно з номером її вибірки з регістру 12. Аналогічним чином може бути організовано пошук і мінімального відліку унімодального вимірювального сигналу. Техніко-економічна ефективність від використовування винаходу, що пропонується, полягає у тому, що модифікація відомого алгоритму пошуку Фібоначчі зробила його дієздатним у відношенні до вибірок вимірювального сигналу, який має 2n дискрет, де 2n - найближча зверху до Fk ступінь двійки. Це дозволяє, з одного боку, зменшити обсяг використовуваного обладнання, а відповідно, і його вартість, практично вдвічі, а з іншого боку - досягти майже 100%-го використання залученого обладнання. Дійсно, оскільки ступінь числа два є типовим значенням багатьох конструктивних параметрів засобів цифрової обробки сигналів (наприклад, значення місткості пам'яті, кількості інформаційних входів у мультиплексорів, а також виходів у дешифраторів, тощо), то безпосередня реалізація відомого алгоритму пошуку Фібоначчі здійснювалась би із залученням обладнання з обсягом, пропорційним найближчому зверху до Fk ступіневі числа 2n+1, причому коефіцієнт використання залученого обладнання складав би, приблизно, Fk/2n+ +1 = 0,531 ... 0,964, у найкращому випадку. Застосування пропонованої модифікації алгоритму пошуку призводить до необхідності залучати обсяг обладнання, пропорційний 2n, тобто вдвічі менший, причому досягається практично 100% його використання, оскільки відсутні незадіяні (вільні) комірки пам'яті або розряди у цих комірках, використовуються всі розряди схеми порівняння, лічильників,ПЗП, майже всі виходи стандартного дешифратора тощо. Крім того, використання технічного рішення, що пропонується, надало можливість здійснювати черговий крок пошуку протягом лише одного такту, підвищуючи швидкодію до рівня, якого достатньо для пошуку в реальному масштабові часу екстремальної з дискрет, котрі надходять від, наприклад, механічно переміщуваного датчика, що сканує виріб, який контролюється на наявність дефектів (тріщин). 4 38129 Таблиця 1 Крок пошуку, і 1 2 3 4 5 (і-1)2 ТТ 1234 ПЗП1 Адреси 000 0000 001 0000 001 1000 010 0000 010 0100 010 1000 010 1100 011 0000 011 0010 011 0100 011 0110 011 1000 011 1010 011 1100 011 1110 100 0000 100 0001 100 0010 100 0011 100 0100 100 0101 100 0110 100 0111 100 1000 100 1001 100 1010 100 1011 100 1100 100 1101 100 1110 100 1111 Таблиця 2 ПЗП2 (6)2 (2)2 (9)2 (2)2 (5)2 (9)2 (12)2 (0)2 (3)2 (3)2 (6)2 (7)2 (10)2 (10)2 (13)2 (0)2 (1)2 (3)2 (3)2 (4)2 (4)2 (6)2 (7)2 (7)2 (8)2 (10)2 (10)2 (11)2 (11)2 (13)2 (14)2 ТТ 12345 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 (9)2 (6)2 (13)2 (3)2 (6)2 (10)2 (13)2 (2)2 (5)2 (5)2 (8)2 (9)2 (12)2 (12)2 (15)2 (1)2 (2)2 (4)2 (4)2 (5)2 (5)2 (7)2 (8)2 (8)2 (9)2 (11)2 (11)2 (12)2 (12)2 (14)2 (15)2 ПЗП3 (0)2 (1)2 (1)2 (2)2 (3)2 (4)2 (3)2 (4)2 (4)2 (5)2 (4)2 (5)2 (6)2 (7)2 (7)2 (8)2 (7)2 (8)2 (8)2 (9)2 (10)2 (11)2 (10)2 (11)2 (11)2 (12)2 (11)2 (12)2 (13)2 (14)2 (14)2 (15)2 Таблиця З Рекомендовані значення для кількості дискрет у складі інтервалів невизначеності Номер кроку пошуку Довжина Вибірки 1 24=16 25=32 26=64 27=128 28=256 29=512 210=1024 2 3 4 5 6 16 9 6 3 2 32 18 13 8 4 3 64 40 23 16 9 6 128 78 49 28 20 12 256 180 104 75 46 28 512 300 211 122 88 54 1024 721 418 302 186 115 7 8 9 10 11 12 13 2 3 7 17 33 70 2 4 10 20 44 2 6 12 25 3 7 18 2 4 11 2 8 4 5 Кількість кроків ал14 горитму Фібоначчі 6 7 9 10 12 13 2 15 38129 Фіг.1 6 38129 Фіг.2 __________________________________________________________ ДП "Український інститут промислової власності" (Укрпатент) Україна, 01133, Київ-133, бульв. Лесі Українки, 26 (044) 295-81-42, 295-61-97 __________________________________________________________ Підписано до друку ________ 2001 р. Формат 60х84 1/8. Обсяг ______ обл.-вид. арк. Тираж 50 прим. Зам._______ ____________________________________________________________ УкрІНТЕІ, 03680, Київ-39 МСП, вул. Горького, 180. (044) 268-25-22 ___________________________________________________________ 7