Аналізатор сигнатур паралельного потоку даних

Аналізатор сигнатур паралельного потоку даних, який містить групу інформаційних входів, перший n-розрядний регістр (де n - ступінь утворюючого полінома або кількість розрядів сигнатурного аналізатора), першу групу n суматорів за модулем два, при цьому входи відповідного суматора за модулем два першої групи з'єднано з тими номерами інформаційних входів, які дорівнюють ненульовим елементам відповідного рядка матриці станів одноканального сигнатурного аналізатора, який відрізняється тим, що в нього введені n груп по n схем AND, дві групи по n суматорів за модулем два, блок пам'яті, другий та третій регістри, блок віднімання, мультиплексор, блок множення, лічильник, дві групи входів початкового встановлення приладу, вихід сигналу закінчення тестування, при цьому виходи кожного і-го суматора за модулем два першої групи підключені до перших U 2 (19) 1 3 буде дорівнювати sig (t)=1101. Якщо пристрій [2] має п'ять входів, то згортка тієї ж послідовності (t)=101011 буде мати наступне значення sig (t)=1111. Така ж послідовність на класичному одноканальному сигнатурному аналізаторі з тим же поліномом буде дорівнювати sig (t)=1100. Не рівність сигнатур свідчить про те, що цей пристрій отримує не вірні результати стиску вхідних даних. Ця помилка виникає вслід того що пристрій [2] на кожному такті обробляє чотири біта (або п'ять біт, якщо використовується пристрій з п'ятьма входами) і послідовність (t)=101011 змінюється на наступну (t)=01010011 (t)=0010100011), яка містить не шість, а вісім (десять) розрядів. В основу корисної моделі поставлено задачу підвищення достовірності контролю, з одержанням сигнатури, яка дорівнює сигнатурі одноканального сигнатурного аналізатора при використанні одного й того утворюючого поліному та однакової вхідної послідовності. Такого результату можна досягти, якщо в аналізатор сигнатур паралельного потоку даних, який містить групу інформаційних входів, перший прозрядний регістр (де n - ступінь утворюючого полінома або кількість розрядів сигнатурного аналізатора), першу групу n суматорів за модулем два, додатково введеш n груп по n схем AND, дві групи по n суматорів за модулем два, блок пам'яті, другий та третій регістри, блок віднімання, мультиплексор, блок множення, лічильник, дві групи входів початкового встановлення приладу, вихід сигналу закінчення тестування, при цьому входи відповідного суматора за модулем два першої групи з'єднано з тими номерами інформаційних входів, які дорівнюють ненульовим елементам відповідного рядка матриці станів одноканального сигнатурного аналізатора, виходи кожного і-го суматора за модулем два першої групи підключені до перших входів елементів AND і-ї групи, другі входи яких з'єднано з відповідними виходами блоку пам'яті, адресні входи якого з'єднано з другою групою інформаційних входів мультиплексора та виходами другого регістру, входи якого підключені до відповідних виходів блоку віднімання, перші входи якого з'єднано з виходами мультиплексора, перша група інформаційних входів якого підключена до відповідних виходів блоку множення, перша група входів якого з'єднано з виходами лічильника, інверсний вихід якого є виходом сигналу закінчення тестування, інформаційні входи лічильника підключені до першої групи входів початкового встановлення приладу, друга група входів початкового встановлення приладу з'єднано з інформаційними входами третього регістра, виходи якого підключені до другої групи відповідних входів блоку множення та другої групи входів блоку віднімання, вихід і-ї схеми AND кожної групи з'єднано з відповідним входом і-го суматора за модулем два другої групи суматорів за модулем два, виходи яких підключені до перших входів відповідних суматорів за модулем два третьої групи, виходи яких з'єднано з відповідними входами першого регістру, виходи якого підключені до другої групи відповідних входів суматорів за модулем два третьої групи. 64692 4 Позитивним технічним результатом є те, що пристрій дозволяє отримувати сигнатуру паралельного потоку даних, яка дорівнює результату, отриманому на одноканальному сигнатурному аналізаторі. Пристрій може виконувати паралельну обробку інформаційної послідовності, яка передається по групах, при цьому довжина групи розрядів може бути будь-якою, тільки не більше кількості інформаційних входів пристрою. Це дає змогу значно підвищити достовірність контролю з використанням аналізатора сигнатур паралельного потоку даних. При пошуку в патентній та науково-технічній літературі не виявлено об'єктів з ознаками, подібними до відмінних ознак технічного рішення, що заявляється, на підставі чого можна зробити висновок про відповідність його критерію "суттєві відмінності". На Фіг.1 наведена структурна схема пристрою в загальному виді. Пристрій включає: групу інформаційних входів 1; першу групу суматорів за модулем два 21-2n (де n - ступінь утворюючого полінома або кількість розрядів сигнатурного аналізатора); n груп по n схем AND 311-3nn; другу групу суматорів за модулем два 41-4n; третю групу 51-5n суматорів за модулем два; перший регістр 6; блок пам'яті 7; другий 9 та третій 13 регістри; блок віднімання 9; мультиплексор 10; блок множення 11; лічильник 12; дві групи входів початкового встановлення приладу 14, 15; вихід сигналу закінчення тестування 16. Розглянемо принцип функціонування пристрою [2]. Матриця станів сигнатурного аналізатора, може бути побудована на підставі характеристичного полінома над полем Галуа GF(2). При цьому кожний стовбець цієї матриці можна визначити відповідно виразу [1]: i hi=S ·h0, i=0,1,…z, (1) де hi - і-й стовбець матриці станів Н; z - кільT кість стовбців матриці станів; h0=||10…0|| - нульовий стовбець матриці станів; S - супроводжуюча матриця, яка однозначно описує характеристичний поліном [3]: a11 a12 a13 a1i a1n 1 0 0 ... 0 ... 0 S 0 1 0 ... 0 ... 0 0 0 1 ... 0 ... 0 , (2) ... ... ... ... ... ... ... .. 0 0 0 ... 0 1 0 де a1j{0, 1, 2} - коефіцієнти характеристичного поліному. n n-1 i Р(х)=а1nх а1nх …a1ix … а12ха11 Наприклад, для характеристичного полінома 4 3 Р(х)=х 3х 3,1 супроводжуюча матриця має вигляд: 0 0 1 1 S 1 0 0 0 0 1 0 0 0 1 1 0 . (3) 5 64692 Відповідно (1) матриця станів для характерис4 3 тичного поліному Р(х)=х 3х 31 має вигляд, який 6 наведений в табл.1. Таблиця 1 Номер рядка 1 2 3 4 1 1 0 0 0 2 0 1 0 0 3 0 0 1 0 4 1 0 0 1 5 1 1 0 0 6 0 1 1 0 Номер стовбця 7 8 9 1 0 1 0 1 0 1 0 1 1 1 0 Процес отримання сигнатури для вхідної послідовності (t) можна представити з допомогою виразу: ............................................................ S 0 1 14 0 0 1 1 15 0 0 0 1 (5) (S K (r 2 )  S  (K 1)(r 2)   S 0 13 0 1 1 1  SK 1 2K 1 )  SK (S 0  K  S1 K 1  K (r 1) 12 1 1 1 1  SK 1 K 1 )  sig ( t )  [S 0 (S 0  0  S11  S 11 1 1 1 0 ної послідовності. Хай вхідна послідовність вводиться в сигнатурний аналізатор по групах, по К розрядів в кожній. Тоді формулу (4) можна перетворити до виразу, який наведений нижче: (4) sig (t)   Si ihi , i  0  z , де  - сума за модулем два; i - і-й елемент вхідної послідовності; z - кількість елементів вхід K (r 2 ) 10 1 1 0 1 1 (S K (r 1 )  S  (K 1)(r 1)   S де r кількість тактів роботи приладу при перевірці вхідної послідовності. На першому такті прилад обробляє групу розрядів K(r 1) , (K 1)(r 1) ,.........Kr 1 , а на останньому такті наступну групу розрядів 0, 1,…, K-1. Для того, щоб результат відповідав виразу (5), необхідно сигнатуру першої групи розK(r-1) рядів умножати на матрицю S , а результат складати по модулю два з сигнатурою другої групи розрядів вхідної послідовності, яку необхідно K(r-2) умножати на матрицю S . Такі дії повторюються доки не закінчується перевірка даних і буде введена остання група розрядів. Для виконання цих функцій до приладу [2] в додано n груп по n схем AND 311-3nn, другу групу суматорів за модулем два 41-4n, третю групу 51-5n суматорів за модулем два, блок пам'яті 7, другий 9 та третій 13 регістри, блок віднімання 9, мультиплексор 10, блок множення 11, лічильник 12, дві групи входів початкового встановлення приладу 14,15, вихід сигналу закінчення тестування 16. Пристрій (Фіг.1) працює наступним чином. В початковому стані в регістрах 6 і 8 записано код 0…0, в лічильник 12 з першої групи входів початкового встановлення приладу 14 записується кільsig( t 0 )  (S 0 K(r 1)  S1 (K 1)(r 1)  K 1  K(r 1)1)  K 1  Kr 1 )]h 0 , кість тактів перевірки вхідних даних r, а в регістр 13, з другої групи входів початкового встановлення приладу 15, записується кількість входів К, які контролюються сигнатурним аналізатором (ланцюги встановлення в початковий стан не наведені). Блок множення 11 визначає загальну кількість розрядів вхідної послідовності z=К*r. Число і подається на першу групу інформаційних входів мультиплексора 10, яка, на час встановлення в початковий стан пристрою, з'єднана з виходами мультиплексора 10. Блок 9 виконує віднімання. z-K=K*r-K=K*(r-1) (6) Результат віднімання (6) записується в регістр K(r-1) 8 є адресою матриці S (5), яка зберігається в блоці пам'яті 7. На цьому встановлення в початковий стан пристрою закінчено. В процесі перевірці даних на входи 1 аналізатора паралельно подається перша група з К розрядів інформаційної послідовності з виходу об'єкта контролю, яка є реакцією на вхідні тестові дії. При цьому, перша група суматорів за модулем два 21-2n виконує згортку даних відповідно матриці станів сигнатурного аналізатора або формулі:  SK 1Kr 1 )h0 , Згортка, яка отримана на виходах блоків 21-2n K(r-1) умножається на матрицю S , що зафіксована на виходах блоку пам'яті 7 в процесі встановлення в початковий стан пристрою. Ця дія виконується з допомогою n груп по n схем AND 311-3nn та другої (7) групи суматорів за модулем два 41-4n. Результат фіксується в регістрі 6 по сигналу синхронізації (ланцюги синхронізації на Фіг.1 не наведені). Таким чином, в регістрі 6 зафіксовано сигнатуру, яка визначається по формулі: 7 64692 sig ( t 1 )  SK(r 1) (S 0  K(r 1 )  S1 (K 1)(r 1)  8  SK 1 Kr 1 )h 0 . В момент сигналу синхронізації і запису сигнатури в регістр 6 виконується підготовка адреси для K(r-2) отримання матриці S з блоку пам'яті 7. При цьому адреса, що зберігається в регістрі 8, подається на другу групу інформаційних входів мультиплексора 10, яка, в робочому режимі приладу постійно з'єднана з виходами мультиплексора. Блок 9 виконує віднімання аналогічно виразу (6): К*(r-1)-К=К*(r-2) (9) Результат віднімання, відповідно виразу (9), K(r-2) записується в регістр 8 є адресою матриці S (5), яка формується на виходах блоку пам'яті 7. Коли на входи 1 сигнатурного аналізатора пода (8) ється друга група з К розрядів інформаційної послідовності з виходу об'єкта контролю перша група суматорів за модулем два 21-2n виконує згортку даних відповідно виразу (7). Ця згортка, з допомогою n груп по n схем AND 311-3nn та другої групи суматорів за модулем два 41-4n, умножається на K(r-2) матрицю S , що вже зафіксована на виходах блоку пам'яті 7. Результат множення підсумовується (з допомогою третьої групи суматорів за модулем два 51-5n) з сигнатурою, яка зберігається в регістрі 6 і фіксується в тому ж регістрі по сигналу синхронізації. Таким чином, в регістрі 6 зафіксовано сигнатуру, яка визначається по формулі: sig( t 2 )  [ SK(r 2) (S 0 K (r 2 )  S1 (K 1)(r 2)   SK 1 K(r 1)1)  (10)  SK(r 1) (S 0 K (r 1 )  S1 (K 1)(r 1)   SK 1 Kr 1 )]h0 , Ці дії повторюються до завершення тестування об'єкту контролю. Сигнал про завершення тестування формується на інверсному виході 16 лічильника 12, який підраховує кількість тактів перевірки вхідних даних, віднімаючи одиницю від числа r при надходженні чергової групи розрядів. В регістрі 6 зберігається результат згортки вхідного паралельного потоку даних, який оброблявся в пристрої по групах з К розрядів. Для порівняння з схемою прототипу на Фіг.2 наведена функціональна схема аналізатора, яка 4 3 відповідає утворюючому поліному Р(х)=х x 1 для випадку K=4. При цьому покажемо процес отримання однакових сигнатур на одноканальному та багатоканальному аналізаторах на наступному прикладі. Припустимо сигнатурний аналізатор обробляє послідовність (t)=101011 по три розряди (старший розряд вводиться першим), на першому такті вводиться послідовність (t=1)=101, а на другому - (t=2)=011. Процес отримання сигнатури для цієї послідовності на одно канальному наведений в табл.2. Таблиця 2 Виходи регістра зсуву 1 2 3 4 (t) Матриця станів реСигнатура гістра зсуву 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 1 0 1 Обробка даних з допомогою пропонованого приладу виконується наступним чином. На першому такті сигнатурний аналізатор приймає послідовність 101 (K=3), при цьому на виходах першої групи суматорів за модулем два буде сформована тимчасова сигнатура sig (0)=1010, яка умножа3 ється на матрицю S (довжина групи розрядів K=3) відповідно наступному виразу: 1 1 0 0 1 0 1   . 0 0 1 1 1 1 1 0 0 0 0 1 На другому такті роботи приладу на входи 1 сигнатурного аналізатора подається послідовність 011, сигнатура якої (0011) умножається на матри0 цю S (яка зафіксована на виходах блоку пам'яті 7) з допомогою блоків 311-3nn і 41-4n, та додається до сигнатури sig (1) з допомогою суматорів за модулем три 51-54. При цьому в регістрі 6 буде зафіксовано результат sig (2)=1100 (00111111=1100). Таким чином, аналізатор сигнатур паралельного потоку даних здатний достовірно обробляти інформацію, яка може передаватись по групах довжиною менше кількості інформаційних входів пристрою та одержувати сигнатуру, яка дорівнює сигнатурі одноканального аналізатора при використанні одного й того утворюючого поліному. Отримана сигнатура пристрою для обробки паралельного потоку даних, який пропонується, завжди буде дорівнювати сигнатурі з одноканального аналізатора, тому, що матриця станів, а також супроводжуюча матриця залежать тільки від вигляду утворюючого поліному. Рівність сигнатур одноканального пристрою і аналізатора сигнатур паралельного потоку даних, при однакових вхідній послідовності та утворюючого поліному, свідчить про правильність отриманих результатів. Джерела інформації: 1. Гордон Г., Надич X. Локализация несправностей в микропроцессорных системах при помощи шестнадцатиричных ключевых кодов // Электроника. 1977, №5, с. 23-33. 2. Авторское свидетельство СССР №1403065, кл. G06F 11/00, 1988. (прототип). sig (1)  S 3 sig (0)  0 1 1 0 1 9 64692 10 11 Комп’ютерна верстка А. Рябко 64692 Підписне 12 Тираж 23 прим. Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601