Пристрій для детального адаптивного порівняння символьних послідовностей

Пристрій для порівняння символьних послідовностей, що містить вхідний регістр для завантаження послідовності, що має групу виходів, які з'єднані із групою логічних схем, що згруповані у вигляді комірок матриці, і кожна з цих комірок містить елемент для завантаження бітового зразка (шаблона), схему для порівняння бітової послідовності із передвизначеним бітовим зразком (шаблоном), схему дозволу бітової маски, що містить елемент І, який відрізняється тим, що містить jрозрядну схему виділення суттєвих збігів, де j кількість символів в послідовності, j-розрядний регістр згортки просторового коду, схему згортки U 2 (19) 1 3 тики величини збігів вказаних послідовностей. Крім того, пристрій, який пропонується, дозволяє порівнювати не лише бітові послідовності, а і послідовності символів, де кожний символ може мати довжину від 1 до t біт (t = 2,3,…). Це дає змогу визначати збіги в текстових даних, музикальних творах, картинах і т. п. Поставлена задача вирішується ти, що конструктивний модуль містить що містить j- розрядну схему виділення суттєвих збігів, де j- кількість символів в послідовності, j- розрядний регістр згортки просторового коду, схему згортки просторового коду, яка має j входів та  виходів, де число  отримане шляхом округлення до найближчого більшого цілого числа значення log2j, регістр маски, блок завантаження оригінальної символьної послідовності, регістр маски, що має вхід для завантаження чергового символу оригінальної послідовності, який під'єднаний до блоку завантаження оригінальної послідовності та вхід для надходження сигналу зсуву з того ж блоку, блок завантаження оригінальної послідовності, що під'єднаний до регістру зсуву для передачі сигналу зсуву та має другу лінію зв'язку із регістром зсуву для завантаження символьної послідовності, виходи елементів "І" у кількості j, що поєднані із j відповідними однорозрядними входами логічної схеми виділення суттєвих збігів, а j однорозрядних виходів цієї схеми з'єднані із j- входами регістру згортки просторового коду що, має j однорозрядних виходів, які під'єднані до входів логічної схеми згортки просторового коду, що має  виходів на які подається результат. Корисна модель пояснюється на кресленні фіг., де зображено функціональну схему пристрою для адаптивного порівняння символьних послідовностей. Пристрій містить регістр зсуву 1, який має j груп виходів по t розрядів в групі, регістр 2, який має j груп виходів по t розрядів в групі, j блоків для порівняння символів 3, j-розрядну схему виділення суттєвих збігів 4, j- розрядний регістр згортки просторового коду 5, схему згортки просторового коду 6, яка має j входів та  виходів, регістр маски 7, блок завантаження оригінальної символьної послідовності 8, групу елементів "І". Кожна з j груп виходів регістра 1 підключена до першої групи із j виходів відповідного блоку 3. На другу групу із j входів кожної схеми 3 підключені виходи відповідної групи регістра 2. Регістр маски 7 має вхід завантаження чергового символу оригінальної послідовності, який під'єднаний до блоку завантаження оригінальної послідовності 8 та вхід для надходження сигналу зсуву з того ж блоку. Блок 8, також, під'єднаний до регістру зсуву 1 для передачі сигналу зсуву та має другу лінію зв'язку із регістром 1 для завантаження символьної послідовності. Блок схем 3 мають по одному виходу, які з'єднані із першими входами елементів "І". Елементи "І" також мають j других входів, на які подаються двійкові сигнали з відповідних розрядів регістру маски 7.j виходів елементів "І" поєднані із j відповідними однорозрядними входами логічної схеми виділення суттєвих збігів 4, a j однорозрядних виходів цієї схеми з'єднані із j- входами регістру зго 61653 4 ртки просторового коду 5 який, також, має j однорозрядних виходів, що під'єднані до входів логічної схеми згортки просторового коду 6. Ця схема має  виходів, на які подається двійковий код числа, який відображує кількісну характеристику співпадання піддослідної послідовності. Пристрій працює із символьними послідовностями, що мають вигляд вектора A[i]- оригінальна символьна послідовність (шаблон) та B[j]- піддослідна послідовність байт, де і та j- кількість символів в цих послідовностях. Пристрій виконує свою задачу як при i j, то перші символи оригінальної послідовності А виштовхуються із регістру 1. Після запису в регістр 1 останнього символу послідовності А виконується ще j - d додаткових тактів. В кожному з цих тактів відбувається зсув вмісту регістру 1 на один символ, а в регістр маски 7 шляхом зсуву записується 0. Значення, якими заповнюються звільнені розряди регістру 1 при додаткових тактах, не має значення. При і < j, регістр маски 7, який є регістром зсуву забезпечує ігнорування можливих випадкових збігів піддослідної послідовності з вмістом тих розрядів регістру 1, які не зайняті оригінальною послідовністю. В результаті на виході схеми згортки просторового коду 6 формується двійковий код числа, який відображує кількісну характеристику співпадання або кількісну характеристику оригінальності піддослідної послідовності В. Дійсно, якщо після обробки першої послідовності регістр згортки просторового коду 5 не обнуляти, а продовжувати обробку наступної послідовності із бази і т. д., то легко видно, що в результаті на виході пристрою буде сформована інтегральна оцінка співпадання. Розглянемо на прикладі роботу пристрою із відображенням вмісту регістрів потактово. Для при 5 61653 клада візьмемо і = 9, d = 2, j = 5 та значення послідовностей В =, A = . 6 10-й Таблиця Такти 1-й 2-й 3-й 4-й 5-й 6-й 7-й 8-й 9-й № блоку 2 1 7 5 2 1 7 5 2 1 7 5 2 1 7 5 2 1 7 5 2 1 7 5 2 1 7 5 2 1 7 5 2 1 7 5 Вміст регістру m o u s 0 0 m 0 0 o 0 0 u 0 0 m 0 0 o 0 0 m 0 0 o m 1 0 o u 1 0 o s 1 0 o 4 1 0 o m 1 0 o o 1 1 0 0 u m 1 0 u u 1 1 u s 1 1 u 4 1 1 u m 1 1 u o 1 1 u u 1 1 0 0 s m 1 0 s u 1 0 s s 1 1 s 4 1 1 s m 1 1 s o 1 1 s u 1 1 s 8 1 1 0 0 m m 1 0 m u 1 0 m s 1 0 m 4 1 0 m m 1 1 11-й e m 1 0 e u 1 0 e s 1 0 e 4 1 0 e m 1 0 e o 1 0 e u 1 0 e 8 1 0 e e 1 0 12-й 2 1 7 5 2 1 7 5 2 1 7 5 m o 1 1 m u 1 1 m 8 1 1 o u 1 1 o 8 1 1 o e 1 1 u 8 1 1 u e 0 1 u s e 1 1 s e 0 1 s 0 0 e 0 1 0 1 0 0 0 0 e Одним із найоптимальніших варіантів реалізації описаної конструкції пристрою для детального адаптивного порівняння символів є реалізація у вигляді функціонального блоку програмованого логічного пристрою (PLD), що може бути реконфігурованим в залежності від характеристик (розміру) інформаційних даних, які оброблюються та виконаного у вигляді параметричного модуля. Також, цей пристрій можна представити у вигляді блоку або IP- компоненти у складі вбудованої системи, що містить софт-процессорне ядро, із користувальницькою системою команд. Цей блок працює зі спеціальними інструкціями, які використовують регістри, що створені на основі програмованого логічного пристрою, пересилає дані між ними та виконує дії згідно описаного вище алгоритму. Прийнятність конструкції на програмованому логічному пристрої, також обумовлено тим, що з її допомогою можна реалізувати регістрові структури досить великої розрядності. Швидкодія даного пристрою залежить від значення i, та кількість звернень до пам'яті пропорційна і + j. Джерела інформації: 1. Патент US 6738794 В2 G06F17/15 2004 2. Тарасенко В. П. Оптимізація структур пристроїв згортки рівноважних однорозрядних операндів / В. П. Тарасенко, О. В. Тарасенко-Клятченко, О. К. Тесленко // Інформаційні технології та комп'ютерна інженерія.-2008, - № 3 (13). - С. 14-17. 7 Комп’ютерна верстка А. Крижанівський 61653 8 Підписне Тираж 23 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601