Пристрій для контролю помилок даних у комп’ютерних пристроях комутаційно-комунікаційного вузла інформаційно-телекомунікаційної системи, що функціонують у класі лишків

Реферат: Пристрій для контролю помилок даних у комп'ютерних пристроях комутаційно-комунікаційного вузла інформаційно-телекомунікаційної системи, що функціонують у класі залишків, належить до автоматики та обчислювальної техніки. У пристрій, що містить регістр числа, блок нулевізації, блок аналізу значення γ n+1 залишку за контрольним модулем mn+1 КЗ на нуль, введені перша та друга групи елементів АБО, група елементів І, група з К блоків (від 0 до К-1) констант нулевізації (К=[n/2], де: n - кількість інформаційних модулів (основ) КЗ; [n/2] - ціла частина числа n/2, його не менша). В основу винаходу поставлено задачу зменшити час контролю помилок даних. UA 105742 C2 (12) UA 105742 C2 UA 105742 C2 5 Винахід належить до області автоматики та обчислювальної техніки і може бути використано для контролю помилок даних у комп'ютерних пристроях (КП) комутаційнокомунікаційного вузла (ККВ) інформаційно-телекомунікаційній системі (ТКС), що функціонують у непозиційній системі числення класу залишків (КЗ). Розглянемо довільний КЗ, що задано інформаційними основами (модулями) m1, m2,,mi,,mn mi1  mi  для i  1, n . Основи МСЧ - це натуральні попарно прості числа (найбільший загальний дільник (НЗД) довільної пари основ m i і m j дорівнює одиниці, тобто n   НЗД mi , m j  1 , при i  j ). Числовий діапазон 0, M   mi  будемо називати інформаційним   i 1   діапазоном КЗ. Щоб мати змогу гарантовано виявити однократні помилки (тобто помилки у залишку числа за будь якої однією з інформаційних основ m i КЗ) введемо що одну (контрольну)  10    основу mn1  mi , що взаємно проста з інформаційними основами mi i  1 n . Числовий , діапазон 0,M  mn1  M1 будемо називати повним діапазоном КЗ. Існує теорема, що коли при обробці числа A  a1 a2  ai  an an 1 у КЗ ai  A  A / ai   mi  існує помилка в одній з основ ~ ~ m i числа A  a1 a2  ~i  ai  an an1 , то число A є спотвореним. В цьому випадку замість a  15 20    правильного числа A (що лежить в діапазоні 0,M ) одержуємо неправильне (спотворене) ~ ~ число A ( A знаходиться за межами діапазону 0,M ). Відомий пристрій (аналог), що дозволяє виявити помилки у системі обробки даних (див. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах.: М: Сов. радио, 1968. С. 33-39), що представлені у КЗ. Пристрій містить регістр числа A  a1 a2  ai  an an 1 у КЗ, схему перетворення числа A  a1 a2  ai  an an 1 з КЗ у     двійкову позиційну систему числення (ПСЧ) A , пристрій аналізу знаходження числа A у діапазоні 0,M . Суть роботи даного пристрою складається з послідовності наступних операцій.   Число A  a1 a2  ai  an an 1 з КЗ переводиться в ПСЧ, і далі робиться порівняння даного числа із робочим діапазоном 0,M . Якщо число A лежить у діапазоні 0,M , тоді робимо 25 висновок, що помилки нема, а якщо число A не лежить у діапазоні 0,M , тоді робимо висновок, що є помилки в одному з залишків числа A  a1 a2  ai  an an 1 . Недолік аналога - значний час процесу контролю помилок даних у КЗ. Недолік обумовлено тим, що необхідно проводити складну непозиційну операцію переводу числа A  a1 a2  an1    30  35  з КЗ У ПСЧ, що потребує значного часу. Найбільш близьким за технічною суттю до запропонованого винаходу є пристрій для контролю помилок даних у КЛ, що описано у монографії (Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М.: Сов. радио, 1968. С. 349-353). Пристрій для контролю даних у КЗ містить регістр числа A  a1 a2  ai  an an 1 , блок нулевізації (БН)   чисел у КЗ, групу блоків констант нулевізації (БКН) чисел, схему аналізу значення  n 1  ann1 на нуль. При цьому інформаційний вхід пристрою підключено до входу регістра числа A  a1 a2  ai  an an 1 , вихід якого підключено до першого входу БН. Вихід БН підключено    до входу схеми аналізу значення  n 1  ann1 на нуль, вихід якої є виходом пристрою БКН.  40  Виходи підрегістрів регістра числа A  a1 a2  ai  an an 1 підключено до відповідних входів БКН групи, виходи яких підключено другого входу БН. Прототип працює наступним чином. Вихідне число    0   що контролюється, A  a1 a2  ai  an an 1  A 0   a10  a0   ai0  ai1  an0  an0 1 , 2      заноситься в регістр. Далі це число поступає до БН, де послідовно за часом приводиться до виду A H  0 0  0 0  n 1  за допомогою такої послідовності операцій віднімання, що не 45 приведе до виходу числового значення числа A 0  за робочий діапазон 0,M . Ця операція у КЗ називається нулевізацією, та складається у послідовному відніманні за залишками a1, a2, a3 , , 1 UA 105742 C2  та an вихідного числа A  A 0    a0  a0 a0  a0   an0  a0   мінімальних чисел, так званих  1 2 i i 1 n 1    констант нулевізації (КН).   Продовжуємо віднімати n разів одержимо значення A H  0 0  0 a n  , або n 1  5   A H  0 0  0  n 1 , де  n 1  ann1 . Після знаходження на першому етапі значення  n1 , на другому етапі у схемі аналізу значення  n 1  a n  на нуль проводиться порівняння з нулем значення  n1 . Якщо n1  0 n 1 (число A знаходиться в діапазоні 0,M ), то робиться висновок, що число А не спотворено (правильне), тобто помилок нема. Якщо n1  0 (число А не знаходиться в діапазоні 0,M ), то число А спотворено (неправильне), тобто є помилка за однією з основ m i КЛ. 10 15 20 25 30 Для прототипу час нулевізації дорівнює значенню TН1  2n , де:  - час віднімання з числа A i константи нулевізації KH i ; n - кількість інформаційних основ КЛ. Загальний час T1 контролю помилок даних визначається як T1  TН1  TП1 , де TП1 - час порівняння значення  n1 з нулем. У КЛ час TП1 порівняння виконується за один такт, тоді можна вважати, що T1  TН1  2n 1 . Недолік прототипу - значний час процесу контролю помилок даних у КЛ. Це зумовлено великим часом TН1 проведення операції нулевізації, тобто великим часом визначення значення числа  n1 . В основу запропонованого винаходу поставлено задачу зменшити час контролю помилок даних у комп'ютерних пристроях комутаційно-комунікаційного вузла інформаційнотелекомунікаційній системі, що функціонують у класі лишків. Задача вирішується тим, що у пристрій для контролю помилок даних у комп'ютерних пристроях комутаційно-комунікаційного вузла інформаційно-телекомунікаційній системі, які функціонують у класі залишків (КЗ), що містить регістр числа, блок нулевізації (БН), блок аналізу значення  n1 залишку за контрольним модулем mn1 КЗ на нуль (БА), при цьому, до другого (керуючого) входу регістра числа підключено керуючий вхід пристрою, а вихід БА є виходом пристрою, додатково введено першу та другу групи елементів АБО, групу елементів І, групу з К блоків (від 0 до К-1) констант нулевізації (БКН) (К = [n/2], де: n - кількість інформаційних модулів (основ) КЛ; [n/2] - ціла частина числа n/2, його не менша: n/2≥[n/2]), при цьому інформаційний вхід пристрою підключено до перших входів елементів АБО першої групи, до других входів яких підключено вихід БН, а виходи елементів АБО першої групи підключено до першого (інформаційного) входу регістра числа, вихід якого підключено до першого входу БН, виходи підрегістрів залишків регістра числа попарно (а1, аn; а2, аn-1; а3, аn-2; … a n , a n ) підключено до 2 35 40 45 1 2 входів відповідних БКН, виходи яких через другу групу елементів АБО підключено до другого входу БН, вихід якого підключено до перших входів елементів І групи, до других входів яких підключено вихід К-1-го БКН, а виходи елементів І групи підключено до входу БА. Введення вказаних ознак дозволяє удвоє, у порівнянні з прототипом, зменшити час контролю помилок даних у КЛ. Для винаходу маємо, що час T2 контролю помилок дорівнює значенню T2  TН2  n 2 . На фіг. 1 у загальному випадку представлена блок-схема запропонованого винаходу. На фіг. 2 представлена блок-схема запропонованого пристрою для КЗ, що заданий основами m1=3, m2=4, m3=5, m4=7 і mk=mn+1=m5=11. В таблиці 1 дано константи парної нулевізації за основами m1=3 і m4=7 для КЗ, що задано основами m1=3, m2=4, m3=5, m4=7 і m5=11. В таблиці 2 дано константи парної нулевізації за основами m2=4 і m3=5, для КЗ, що задано основами m1=3, m2=4, m3=5, m4=7 і m5=11. 2 UA 105742 C2 Таблиця 1 Константи нулевізації БН 60 ПСЧ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 m1=3, m4=7 0||0||0||0||0 1||1||1||1||1 2||2||2||2||2 0||3||3||3||3 1||0||4||4||4 2||1||0||5||5 0||2||1||6||6 1||3||2||0||7 2||0||3||1||8 0||1||4||2||9 1||2||0||3||10 2||3||1||4||0 0||0||2||5||1 1||1||3||6||0 2||2||4||0||3 0||3||0||1||4 1||0||1||2||5 2||1||2||3||6 0||2||3||4||7 1||3||4||5||8 2||0||0||6||9 Таблиця 2 Константи нулевізації БН 61 ПСЧ 0 21 84 105 42 63 126 147 168 189 252 273 210 231 294 315 336 357 378 399 5 m2=4, m3=5 0||0||0||0||0 0||1||1||0||10 0||0||4||0|7 0||1||0||0||6 0||2||2||0||9 0||3||3||0||8 0||2||1||0||5 0||3||2||0||4 0||0||3||0||3 0||1||4||0||2 0||0||2||0||10 0||1||3||0||9 0||2||0|0||1 0||3||1||0||0 0||2||4||0||8 0||3||0||0||7 0||0||1||0||6 0||1||2||0||5 0||2||3||0||4 0||3||4||0||3 На фіг. 1 представлена загальна блок-схема винаходу, де: 1 - інформаційний вхід пристрою; 2 - перша група елементів АБО; 3 - блок нулевізації (БН); 4 - регістр числа A у КЛ; 5 - керуючий вхід пристрою; 60  6K 1 - група блоків констант нулевізації (БКН); 7 - друга група елементів 3 UA 105742 C2 5 10 АБО; 8 - група елементів І; 9 - блок аналізу значення  n1 залишку за контрольним модулем mn1 на нуль (БА); 10 - вихід пристрою. Інформаційний 1 вхід пристрою підключено до перших входів елементів АБО першої 2 групи до других входів яких підключено вихід БН 3. Виходи елементів АБО першої 2 групи підключено до входу регістра 4 числа, до другого входу якого підключено керуючий 5 вхід пристрою. Вихід регістра 4 підключено до першого входу БН 3. Виходи підрегістрів залишків регістра 4 числа попарно (а1, аn; а2, аn-1; а3, аn-2; і т.д.) підключено до входів відповідних БКН 60  6K 1 , виходи яких через першу 7 групу елементів АБО підключено до другого входу БН 3, вихід якого підключено до перших входів елементів І 8 групи, до других входів яких підключено вихід (К-1)го БКН 6K 1 . Виходи елементів І 8 групи підключено до входу БА 9, вихід 10 якого є виходом пристрою. Пристрій для контролю даних у КЗ функціонує наступним чином (фіг. 1). За інформаційним входом 1 пристрою, через першу 2 групу елементів АБО до входу регістра 4 надходить число у КЗ (у загальному вигляді позначається як A  a1 a2  an an 1  15     A  A 0   a10  a0   an0  an0 1 ), що необхідно контролювати. Сигнал шини 5 запускає роботу 2       пристрою. З виходу регістра 4 число A 0   a0  a0   an0  a0   надходить до входу БН 3. З 2 n 1  1    виходу регістра 4 до входів БКН 60 надходять значення залишків a 0  і an0  , за якими у БКН 60 1  вибирається константа нулевізації KH 0    t 0  t 0   t n0  t 0   , де у загальному випадку 1 2 n 1    0   0, m  1; t 0   0, m  1 , а конкретно для даного числа A 0  - t 0   a 0  і t 0   a 0  . З виходу t1 1 n n n n 1 20 1 значення KH0 через елементи АБО другої 7 групи надходить до входу БН 3, де БКН 60 визначається значення  0 0 0   0 0 0 0 0 0 A 1  A 0   KH0   a10  a0  a3   ai1 ai0  ai1  an3 an2 an0 1 an  an1  t10  t 0  t 3   ti1 2  2       0 0 0 0 0 1 1 1 1 1 0 ti0 ti1  tn3 tn2 tn1 tn  t n1  0 a1 a3  a1  ai1 ai1 ai1  an3 an 2 an1 0 an1 .. 4 1 1   2    В загальному випадку у БКН 60  6K 1 формуються К констант нулевізації виду  0      KH 0    t10  t 0  t 3   t n0  t n0 1 , t10   0, m1  1; t n0   0, mn  1;  2    25 1 1 1  1 KH 1   0 t 1 t 3  t 1  t n 1 0 t n 1 , t 1  0, m2  1; t n 1  0, mn 1  1;  2 4   2       KH 2    0 0 t 32  t 2   t n2 2 0 0 t n2 1 , t 32   0, m3  1; t n2 2  0, mn  2  1;  4       i i i i i i KH i   0 0  0 t i1 t i 2  t n i 0  0 t n i , t i1  0, mi 1  1; t n 1  0, mn i  1;          30    ti  ai  ai1  t i1 mod m ,  i1 i 1 . i 1 i 1 i 1 i i  ai1  t i1 mod m . tn1  an i n i n i n i  Для n парного числа (К = n/2) маємо K K  KH K 1   0 0  0 t K 1 t K 1 0 0  0 t nK 1  .  1 1    Для n непарного числа (К = (n+1)/2) маємо K  KH K 1   0 0  0 t K 1 0  0 t nK 1  .  1    За допомогою вищеозначених констант .   KH i i  0,K  1 вихідне число контролюється, у БН 3 послідовно приводиться до виду A i  A i1  KHi1 , тобто 4 A 0  , що UA 105742 C2   0 0   A  A 0   a10  a 0   ai1 ai0  ai1  an0 1 an0  an0 1, 2       1 1 1 A 1  0 a 1 a3   ai1 ai1 ai11  an 1 0 an 1, 1   2       2 2 A 2   0 0 a32  a 2   ai1 ai2  ai1  an2 2 0 0 an2 1, 4       .    i i i i A i  0  0 ai1 ai 2  an i 1 an i 0  0 a(i) 1,   n       5  K A H  A K   A K 1  KH K 1  0 0  0 an 1  0 0  0  n 1 .     Вихідний сигнал БКН 6K 1 відкриває елементи І групи 8 і значення  n1 надходить до БА 9, де порівнюється з нулем. Якщо n1  0 , тоді сигнал шини 10 відсутній, що свідчить, що число A не спотворено. Якщо n1  0 , тоді на шині 10 присутній сигнал, що свідчить, що число A спотворено (неправильне). Наведемо приклади конкретної реалізації операції контролю даних у КЛ, що заданий основами m1=3, m2=4, m3=5, m4=7 і m5=11 (фіг. 2), табл. 1, 2). При цьому інформаційний 4 числовий інтервал 0,M правильних чисел A визначається через M   mi  3  4  5  7  420 , а робочий числовий інтервал 0,M визначається i 1 через значення 5 10 M0   mi  3  4  5  7  11  4620 . i 1 Приклад 1. За входом 1 через першу 2 групу елементів АБО число   A  A 0   1 0 0 1 4 , що контролюється, надходить до регістра 4. Сигнал шини 5 дає дозвіл на контроль числа A 0  .  Значення A 0  надходить до входу БН 3. За значеннями a10   1 і a 0   1 числа A 0  у БКН 60 4 15 (табл. 1) вибирається константа нулевізації KH 0   1 1 1 1 1 , що через елементи АБО другої 7 групи надходить до входу БН 3. Блок БН 3 визначає значення A 1  A 0  KH0 , тобто:   A 0   1 0 0 1 4  KH 0   1 1 1 1 1 . A 1  0 3 4 0 3  З виходу БН 3 число A 1 через першу 2 групу елементів АБО надходить до входу регістра 4. Таким чином, в даний момент часу у регістрі 4 знаходиться число A 1  0 3 4 0 3 . 20 1 Далі значення a 1  3 і a3   4 надходять до входів БКН 61 , де вибирається константа 2 нулевізації KH 1  0 3 4 0 3  (табл. 2). З виходу БКН 61 сигнал, що відповідає KH1 , надходить до других входів елементів І групи 8 та через другу 7 групу елементів АБО до БН 3. У БН 3 визначається значення A 2   A 1  KH 1  0 0 0 0 0  .  25  A 1  0 3 4 0 3  KH 1  0 3 4 0 3  . A 2   0 0 0 0 0  Нулевізоване A H число визначається як A H  A 2   A 1  KH 1  0 0 0 0 0 . Таким чином,  маємо, що  5  a52    n 1  0 . Так, як n1  0 , тоді сигнал шини 10 відсутній (вихідний сигнал   БА 9 відсутній), тобто число A  1 0 0 1 4 правильне. 5 UA 105742 C2 Перевірка: A  400  M  420. Приклад 2. За входом 1 через першу 2 групу елементів АБО число 5   A  A 0   1 1 0 1 4 , що контролюється, надходить до регістра 4. Сигнал шини 5 дає дозвіл на контроль числа A 0  . Значення A 0  надходить до входу БН 3. За значеннями a 0   1 і a 0   1 числа A 0  у БКН 60 4 1 (табл. 1) вибирається константа нулевізації KH 0   1 1 1 1 1 , що через елементи АБО другої 7 групи надходить до входу БН 3. Блок БН 3 визначає значення A 1  A 0  KH0 , тобто: A 0   1 1 0 1 4  0  KH  1 1 1 1 1  A 1  0 0 4 0 3 10  . З виходу БН 3 число A 1 через першу 2 групу елементів АБО надходить до входу регістра 4. Таким чином у регістрі 4 знаходиться число A 1  0 0 4 0 3 . . Далі значення a 1  0 і a 1  4 надходять до входів БКН 61 , де вибирається константа 2 3 нулевізації KH 1  0 0 4 0 7  (табл. 2). З виходу БКН 61 сигнал, що відповідає KH1 , надходить до других входів елементів І групи 8 та через другу 7 групу елементів АБО надходить до БН 3. У 2  1 1 БН 3 визначається значення A  A  KH  0 0 0 0 0  .  15  A 1  0 0 4 0 3  KH 1  0 0 4 0 7  . A 2   0 0 0 0 7  Нулевізоване A H число визначається як A H  A 2   A 1  KH 1  0 0 0 0 7 . Таким чином,  маємо, що  5  a52    n 1  7 . Так, як n1  0 , тоді сигнал шини 10 присутній (вихідний сигнал БА 9 присутній). Наявність сигналу шини 10 свідчить, що вихідне число A  1 1 0 1 4  20 25 30  спотворено. Перевірка: A  3865  M  420 . Таким чином запропонований винахід (пристрій для контролю помилок даних у комп'ютерних пристроях комутаційно-комунікаційного вузла інформаційно-телекомунікаційної системи, що функціонують у класі залишків) дозволяє у два рази зменшити час контролю даних, що підвищує оперативність процесу контролю. Це досягається шляхом суміщення у часі основних операцій обробки інформації у процесі нулевізації одночасно за двома m1, mn; m2, mn1; m 3, m n-2; і т.д. основами КЗ. Результати проведених розрахунків і порівняльного аналізу часу контролю даних запропонованого винаходу та прототипу показали, що використання винаходу для контролю помилок даних у комп'ютерних пристроях комутаційно-комунікаційного вузла інформаційнотелекомунікаційній системі, що функціонують у класі залишків, забезпечує менший час виявлення помилок, що підвищує загальну ефективність застосування кодів КЗ для обробки даних. 6 UA 105742 C2 ФОРМУЛА ВИНАХОДУ 5 10 15 Пристрій для контролю помилок даних у комп'ютерних пристроях комутаційно-комунікаційного вузла інформаційно-телекомунікаційної системи, що функціонують у класі залишків (КЗ), що містить регістр числа, блок нулевізації (БН), блок аналізу значення γ n+1 залишку за контрольним модулем mn+1 КЗ на нуль (БА), при цьому до керуючого входу регістра числа підключено керуючий вхід пристрою, а вихід БА є виходом пристрою, який відрізняється тим, що в пристрій введено першу та другу групи елементів АБО, групу елементів І, групу з К блоків констант нулевізації (БКН), де К=[n/2], n - кількість інформаційних модулів КЗ, [n/2] - ціла частина числа n/2, причому n/2≥[n/2], при цьому інформаційний вхід пристрою підключено до перших входів елементів АБО першої групи, до других входів яких підключено вихід БН, а виходи елементів АБО першої групи підключено до інформаційного входу регістра числа, вихід якого підключено до першого входу БН, виходи підрегістрів залишків регістра числа попарно а1, аn; а2, аn-1; а3, аn-2; … a n , a n 2 20 1 2 підключено до входів відповідних БКН, виходи яких через другу групу елементів АБО підключено до другого входу БН, вихід якого підключено до перших входів елементів І групи, до других входів яких підключено вихід К-1-го БКН, а виходи елементів І групи підключено до входу БА. 7 UA 105742 C2 Комп’ютерна верстка Л. Литвиненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 8