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

Пристрій для виявлення та виправлення помилок у модулярній системі числення (МСЧ), що містить вхідний регістр, суматор за модулем m1 2 47563 1 3 47563 Недоліком відомого пристрою є низькі функціональні можливості, які обумовлені неможливістю виправлення помилок. Найбільш близьким за технічною суттю є патент на корисну модель №42463, Бюл. №13, 2009р. Пристрій містить регістр, суматор за модулем m1 МСЧ, (n-1)-н суматорів та елемент АБО. Даний пристрій дозволяє виявити помилки у числі A = (a1, a 2 ,K, an ) , що представлено у МСЧ з попарно не простими основами (модулями) m1, m 2 ,K , mn та НЗД mi , m j ¹ 1 i ¹ j . При цьому , ( ) виявляються однократні (за однією з основ mi МСЧ), або [log2 (mi - 1)] + 1 двійкових розрядів. Недоліком відомого пристрою є низькі функціональні можливості корисної моделі, які обумовлені неможливістю виправлення помилок. Критерій, що дозволяє визначити та виправити помилки за однією із попарно не простих основ m1, m 2 ,K , mn МСЧ числа A = (a1, a 2 ,K, an ) наступний: по значенням лишків {ai }, i = 1 n , числа А в , МСЧ визначаємо всі можливі значення виду 4 (ai - ai +1 ) = ai(i +1)(mod di(i +1) ) , де i = 1, n - 1 , та значення (an - a1 ) = an1(mod dn1 ) . Позначимо di(i + 1) як НЗД основ di(i + 1= ) (mi , mi +1 ) . ( та mi ) МСЧ, mi +1 Якщо всі тобто значення ai(i +1) = mod di(i +1) одноразово дорівнюють нулю, тоді рахується, що помилки нема, або вона кратна кожному з дільників виду d (i -1)i та di(i + 1) (передба чається однократна помилка). Якщо a (i -1)i ¹ 0 та ai(i + 1) ¹ 0 , а інші значення aij = 0 (i ¹ j) , то однокра тна помилка присутня в лишку за модулем mi , тобто спотворений лишок за основою mi має наступний вигляд ~ = (a + Da ) mod m (0 < Da < m ) . a i i i i i i Далі за значеннями a (i -1)i та a i(i + 1) визначимо Dai = mi - Dai . Після цього, за допомогою суматора за модулем mi , виправляємо числа А в МСЧ ~ шляхом виправлення лишка a наступним чином: i ( ~i + Dai ) modmi = [(ai + Dai ) + (mi - Da i )]modmi = ai (modmi ) a де: ~i = (ai + Dai ) mod mi ; a Dai = (mi - Dai )mod mi . Мета корисної моделі - розширення функціональних можливостей пристрою за рахунок виправлення помилок у МСЧ. Поставлена мета вирішується за рахунок того, що пристрій містить вхідний та вихідний регістри, суматор за модулем m1 , МСЧ, першу (містить {(n1)-н суматорів за модулями m 2 K mn ), другу (n-н суматорів за модулями di(i +1), i = 1, n - 1 і d1n ) та , третю (містить n-н суматорів за модулем m1 K mn ) групи суматорів, групу з n шифраторів, групу з n елементів пам'яті, комутатор, елемент АБО. При цьому інформаційний вхід пристрою підключено до інформаційного входу вхідного регістра, а керуючий вхід пристрою підключено до керуючого входу регістра. Перший вихід вхідного регістра, відповідає значенню першого a1 лишка числа A = (a1, a 2 ,K, an ) у МСЧ, підключено до першого входу суматора за модулем m1 МСЧ ( m1 < m 2 < K < mn ) a n - кількість модулів МСЧ). Виходи розрядів a2 K an вхідного регістра підключено до перших входів відповідних суматорів за модулями m 2 K mn першої групи та до перших входів суматорів другої групи за модулем di(i +1)(i= 1, n - 1) і до першого входу суматора за модулем dn1 . До других входів суматорів першої групи підключено шини подачі значень модулів МСЧ mi (i = 2, n) . Вихід суматора за модулем mi та виходи суматорів першої групи підключено до других входів відповідних суматорів другої групи та до другого входу суматора за модулем dn1 di(i + 1) НЗД модулів mi та mi +1 МСЧ; dn1 - НЗД модулів mn та m1 ), виходи яких підключено до входів відповідних дешифраторів, виходи яких підключено до відповідних двовходових елементів пам'яті, виходи яких підключено до входів відповідних шифраторів, виходи яких підключено до перших відповідних суматорів за модулями m1 ¸ mn третьої групи та одноразово до входів елемента АБО. Виходи a1 ¸ an вхідного регістра підключено до других входів суматорів третьої групи та до входів комутатора. Вихід суматорів третьої групи та елемента АБО підключено до входів комутатора, вихід якого є виходом пристрою. На Фіг.1 приведена блок-схема пристрою для загального випадку, на Фіг. 2 - для МСЧ, що задана основами m1 = 4, m2 = 6, m 3 = 12 (n=3), де: 1 інформаційний вхід пристрою; 2 - вхідний регістр; 3 - керуючий вхід пристрою; 4 - суматор за модулем m1 МСЧ; 5 - шина подачі значення m1 ; 6 пе рша група суматорів за модулями m 2 , m3 ,K, mn ; 7 - шини подачі значень m 2 , m3 ,K, mn ; 8 - друга група суматорів за модулем di(i +1)(i = 1, n - 1) ; 9 - суматор за модулем dn1 ; 10 - група дешифраторів; 11 елементи пам'яті; 12 - група шифраторів; 13 - третя група суматорів за модулями m1, m 2 ,K , mn ; 14 елемент АБО; 15 - комутатор; 16 - вихідний регістр; 17 - вихід пристрою. 5 47563 Інформаційний 1 вхід пристрою підключено до інформаційного входу вхідного 2 регістра, а керуючий вхід 3 пристрою підключено до керуючого входу суматора 2. Перший вихід вхідного регістра 2 підключено до першого входу суматора 4 за модулем m1 , до другого входу якого підключена ши 6 Пристрів для виявлення та виправлення помилок у МСЧ функціонує наступним чином (Фіг.1). На вхід 1 пристрою поступає число A (a1, a 2 ,K, an ) у МСЧ. По сигналу шини 3 з ви= a2 K an регістра 2 підключені до перших входів відповідних суматорів першої 6 групи та до перших входів суматорів другої 8 групи за модулями ходу регістра 2 значення ai лишків у двійковому коді поступає на перші входи суматорів 4, 6, 8, 9, 13 та на першу групу входів комутатора 15. На другі входи суматорів 4, 6 поступає значення модуля m1 5, та значення модулів m 2 K mn 7. На другі входи суматорів 8 та суматора 9 поступають di(i +1)(i = 1, n - 1) і до першого входу суматора 9 за інвертовані значення модулем dn1 . До других входів суматорів першої 6 групи підключено шини 7 подачі значень модулів числа A = (a1, a 2 ,K, an ) . З виходу суматорів 8 зна на 5 подачі значення модуля m1 . Виходи розрядів mi (i = 2,n) . Вихід суматора 4 за модулем mi та виходи суматорів першої 6 групи підключені до других входів відповідних суматорів другої 8 групи та до другого входу суматора 9 за модулем dn1 . Виходи суматорів 8 та 9 підключені до входів відповідних дешифраторів 10 групи, виходи яких підключені до відповідних двовходових елементів 11 пам'яті, при цьому: до входів першого елемента 11 групи підключено вихід першого та n-го дешифраторів 10; до входів другого елемента 11 групи підключено вихід першого та другого дешифраторів 10 і т.д.; до входів n-го елемента 11 групи підключено вихід (n-1)-гo та n-го дешифраторів 10. Виходи елементів 11 підключено до входів відповідних шифраторів 12, виходи яких підключені до перших входів відповідних суматорів за модулями m1 K mn третьої 13 групи та до входів елемента 14 АБО. Виходи a1 K an вхідного 2 регістра підключені до других входів суматорів 13 та до входів комутатора 15. Вихід суматорів третьої 13 групи та елемента 14 АБО підключено до входів комутатора 15, вихід якого підключено до входу вихідного 16 регістра, вихід 17 є виходом пристрою. ( ( ) ai = mi - ai i = 1, n ) = (a лишків чення ai(i +1) = ai + ai +1 mod di(i +1) та з виходу сума ) тора 9 значення an1 n + a1 mod dn1 через відповідні дешифратори 10, в унітарному коді, поступають на відповідні елементи 11 пам'яті. Для кожної МСЧ елементи 11 кодуються окремим чином: по значенням a (i -1)i та a i(i + 1) елементи 11 визначають значення Dai . ~ Якщо число A = (a1, a2 ,K, ai ,K , an ) спотворено за модулем (основою) mi , тоді на виході тільки іто елемента 11 є сигнал, що відповідає значенню Dai , яке визначається числами a (i -1)i та a i(i + 1) . 3 виходу і-то шифратора 12 значення Dai у двійковому коді поступає на перші входи і-го суматора 13 за модулем mi та поступає на вхід елемента 14 АБО. На другі входи і-го суматора 13 за модулем mi , з виходу регістра 2, поступає значення ( ) ~ = a + Da mod m . На виході і-го суматора 13 за ai i i i модулем mi буде значення (~i + Dai )modmi = [(ai + Dai ) + (mi - Da i )]modmi = ai (modmi ) , a де: = Dai ( ) ~ = a + Da mod m ai i i i (mi - Dai )mod mi . 13 за модулем mk та На виході інших суматорів (k = 1,n;k ¹ i) отримаємо зна чення (ak + 0 )mod mk = ak (mod mk ) . Таким чином з виходів суматорів третьої 13 групи виправлений операнд A = (a1, a2 ,K, ai ,K , an ) через комутатор 15, який відчинений за другою групою входів вихідним сигналом елемента 14 АБО, поступає на вхід вихідного 16 регістра. Якщо число A = (a1, a 2 ,K, an ) не спотворено, то з виходів елементів 11 сигнали відсутні (нульові сигнали) і число А, через першу групу комутатора 15 з регістра 2, поступає на вхід регістра 16. Розглянемо приклад конкретного виконання операції виявлення та виправлення помилок у МСЧ, що задана основами m1 = 4, m2 = 6, m 3 = 12 . Кодові слова для даної МСЧ представлені в таб лиці 1. В таблицях 2 ¸ 4 представлені схеми комутаторів 11. При цьому d12 (4,6 ) 2 ; = = d23 = (6,12) = 6; d31 = (4,12) = 4. При цьому a1 m1 - a1 0100 - 0011 0001 , = = = a2 m 2 - a 2 0110 - 0100 0010 , = = = a3 m 3 - a3 1100 - 0111 0101 . = = = Нехай необхідно визначити та, якщо необхідно, виправити однократну (за однією основою ті МСЧ) помилку в числі А=(0011,0100,0111), (Фіг.2). На виході першого суматора 8 другої групи за модулем d12 формує на своєму виході значення ( ) a12 = a1 + a2 mod d12 = (0011 + 0010 )mod 2 = 0001 , тобто a12 = 1 . На виході другого суматора 8 за модулем a23 = d23 формує (a2 + a3 )modd23 = на виході значення (0100 + 0101)mod 6= 0011 . 7 47563 Суматор 9 за модулем d31 формує на виході значення ( ) a31 = a3 + a1 mod d31 = (0111 + 0001) mod 4 = 0 . Таким чином маємо a12 = 1 , a 23 = 3 , та a31 = 0 . Робимо висновок, що помилка міститься в лишку a2 за модулем m 2 числа А. Таким чином на входи другого 11 елемента (таблиця 3) в унітарному коді поступають значення a12 = 1 та a 23 = 3 . З виходу другого 11 елемента через другий шифратор 13 значення Da2 = 0011 (таблиця 3) в двійковому коді поступає на вхід елемента 14 АБО та на входи другого суматора 13 за модулем m 2 , на другі входи якого поступає з регістра 2 значення ~ a2 . На виході другого 13 суматора за модулем m2 ( ) формується 8 0 1 2 3 4 5 6 7 8 9 10 11 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 0000 0001 0010 0011 0000 0001 0010 0011 0000 0001 0010 0011 0000 0001 0010 0011 0100 0101 0000 0001 0010 0011 0100 0101 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 Таблиця 2 a31 1 2 = ~2 + D= (0100 + 0011)mod 6 0001 . a2 a a 2 modm2 = Таким чином, з виходів суматорів третьої групи виправлений операнд А=(0011,0001,0111) через комутатор 15, який відчинений за другою групою входів комутатора вихідним сигналом елемента 14 АБО, поступає на вхід вихідного 16 регістра (таблиця 1). Da1 = 1 3 значення a12 = 1 Da1 = 3 Таблиця 3 a23 a12 = 1 1 Da 2 = 5 2 Таблиця 1 3 4 Da 2 = 3 5 Число в позиційній системі чисЧисло у МСЧ лення А m1=0100 m2=0110 m3=01100 Da 2 = 1 Таблиця 4 a31 1 2 1 Da 3 = 7 2 3 Da3 = 1 a23 3 4 5 Da 3 = 3 Da3 = 11 Da 3 = 2 Da3 = 10 Da 3 = 9 Da 3 = 5 Таким чином запропонована корисна модель дозволяє не тільки виявляти помилки у числі A = (a1, a 2 ,K, an ) , що представлено у МСЧ за по парно не простими основами {mi } i = 1 n , але й , , виправляти помилки за однією з основ МСЧ. 9 Комп’ютерна верстка А. Рябко 47563 Підписне 10 Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601