Устройство для контроля ошибок в избыточном модулярном коде

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1) 4 Н 03 М 13/О И О ЕНИЯ ОП ИДЕТ ЕЛЬСТВ ВТОРСК ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство СССР 1 Ф 744583, кл. О 06 Р 11/08, 1977.Авторское свидетельство СССР М 377780, кл. О 06 У 11/10, 1970. (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ ОШИБОК , В ИЗБЫТОЧНОМ МОДУЛЯРНОМ КОДЕ (57) Изобретение относится к вычислительной технике, может быть использовано в системах связи и обработки инФормации, оперирующих с модулярными кодами (кодами в системе остаточных классов), позволяет расширить 1363484 функЦиональные воэможности устройства за счет обеспечения исправленияошибок любой заданной кратности, Устройство содержит входной преобразователь 1 кода (из модулярного в позиционный), блок 3 вычисления поправоки блок 5 анализа. Введение блока 2преобразования числа в цепную дробь,вычитателя 4 и выходного преобразователя 6 кода (из позиционного в модулярный) обеспечивает при соответствующей избыточности исходного кодаобнаружение и исправление ошибок.Всевычисления производятся в позиционномкоде, чем достигается еще и некоторое упрощение устройства. 4 з.п. лы, 5 ил.- избыточные основания, Р =66,Р=38798760, а произведение оснований, остатки по которым можно исправить, должно быть меньше 177. Такимобразом, искажение любого одного остатка всегда исправимо, а также ис -правимы искажения в любых двух остатках по основаниям( (,а также по основаниям 1, )Р, 3 Р1"6 Рт х. 1 ь (1611 20РРР РПусть задано число Х=51.1-(0,7,5,4,1,1,17), в результате искажения которого получйлось число Х =2645881-(0,,7,4,1,1,17),252645881Раскладываем число в в вв цеп 38798760ную дробь38798760=14 в 2645881+1756426 а,=14;2 Ь 45881=1:1756426+889455, а =1;1756426=1889455+866971 а:,=1;889455=1 866971+22484 а,=1;86 Ь 971=38 22484+12579, а =38 и т,д,Соответственно для цепной дроби014, 1, 1, 1, 38.Р,ц 12645881-2771340=-125459О так как получилось отрицательноечисло, то продолжаем вычислять подходящие дроби;,Ия 152645881-2586584=59297618 полученное значение не удовлетворяет условию и, следовательно, переходим к следующему шагу; 45Р, 2 Р- так как - не является2929целым числом, то процесс вычисленияподходящих дробей продолжаем (приэтом также 2645881-267577,6=298995,5);5 о2645881-2645370=511616,Цоследовательно, исходное значение числа Х равно 511,На фиг. 1 приведена функциональная схема устройства для контроляошибок в избыточном модулярном коде;на фиг. 2 - пример выполнения блокапреобразования числа в цепную дробь; на фиг. 3 -. пример выполнения блокаанализа; на фиг. 4 - пример выполнения блока вычисления поправки; нафиг. 5 - пример выполнения блокапреобразования цепной дроби.Устройство для контроля ошибок визбыточном модулярном коде содержитвходной преобразователь 1 кода блок2 преобразования числа в цепную дробь,блок 3 вьчисления поправки, вычитатель 4, блок 5 анализа и выходнойпреобразователь б кода. На фиг. 1обозначены информационные входы 7,,.ервые 8, вторые 9 и третьи 1 С установочные гходы, контролнные ьыходы11, первые 12 и вто;и з 13 информационные выходы.Бходнои преобразователькодаооеспечивает преобразования кода вIостатка,модулярного кода ) в позиционный кот., например, двоичный.Он может быть выполнен как в видекомбинационного устройства, не требующего синхронизации, так и в видемноготактного устройства (необходимые при этом цепи синхронизации награфических материалах не показаны,но их наличие для этого случая подразумевается),Блок 2 преобразования числа в цепную дробь (фиг. 2) выполнен на регистре 14 сдвига, состоящем из трехячеек 14.1-14.3, каждая из котсрыхимеет разрядность не менееор Г.вычитателе 15 делителе 16 и перемножителе 17, На фиг. 2 обозначеныинформационные входы 18, управляющиевходь. 19 и выходы 20 блока. Бхоцыпредварительной записи в ячейку 14.3не показаны. При появлении импульсана входе 19,1 происходит запись вячейку 14.3 кода числа с выходов бло ка 16,этом содержимое остальныхячеек регистра 14 остается неизменным. При появлении импульса на входе19.2 содержимое регистра 14 передвигается на одну ячейку влево. Блоки15-7 могут быть выполнены как в комбинационном, так и регистровых вариа;. тах.Блок 5 анализа (фиг. 3) выполнен на первом 21 и втором 22 элементах сравнения, генераторе 23 импульсов и элементе И 24. На фиг. 3 обозначены первые 25 и вторые 26 информационные входы и управляющие выходы 27 блока, Если код на входах 26 меньше кода на входах 9, то на выходе элемента 223484 45 50 5 136 сравнения будет уровень "1", запирающий генератор 23 импульсов, Если код на входах 25 меньше кода Р на входах 10, то на прямом выходе элемента 21 будет уровень "0". Генератор 23 генерирует двухфазную последовательность импульсов на выходах 27,1 и 27.2.Блок 3 вычисления поправок (фиг. 4) выполнен на первом 28 и втором 29 преобразователях кода, делителе 30 и перемножителе 31. На фиг. 4 обозначены информационные входы 32, управляющие входы 33, первые 34 и вторые 35 выходы блока. Делитель ЗО и перемножитель 31 могут быть выполнены известным способом, при этом перемножитель 31 имеет шину блокировку (не показана), посредством которой на его выходе можно обеспечить появление кода числа О независимо от значений переменных на его ьходах.Преобразователи 28 и 29 кода выполнены каждый (фиг. 5) на регистре Зб сдвига, аналогичном регистру 14 блока 2, перемножителе 37 и сумматоре 38. На фиг. 5 обозначены информационные входы 39 и выходы 40 преобразователя. Выходной преобразователь 6 кода служит для преобразования позиционного кода (например, двоичного), в котором функционируют блоки 2-5, в исправленный модулярный код, аналогичный входному коду. Этот преобразователь, как и входной преобразователь 1, может быть выполнен в комбинационном или регистровом виде.Устройство для контроля ошибок в избыточном модулярном коде работает следующим образом. В исходном состоянии на входах 7установлены коды остатков х х1соответственно, которые определяютчисло Х . Число Х =Х, если ни один(из остатков не искажен, либо Х ФХ,если искажен один или несколько остатков н представлении числа Х . Задачей работы устройства является коррекция искаженных остатков с цельюпреобразования Х в Х. Через время,определяемое переходными процессамив преобразователе 1, на его выходахустановится значение числа Х в позиционном (дноичном) коде,Далее необходимо проверить правильность числа Х . Критерием его 5 10 15 20 25 30 35 40 правильности является выполнение условия Х Р.ФТак как в исходный момент времени перемножитель 31 и генератор 23Iзаблокированы, то число Х через вычитатель 4 в неизменном виде поступает на входы элемента 22 сравнения,который сравнивает его с кодом числаР со входов 9. Если Х Р, то навйходах элемента 22 сравнения будетуровень "1", который поступает навыход 11.1 устройства и свидетельствует о том, что нет необходимостив процедуре исправления ошибки. Вэтом случае число Х может сниматьсякак с выходов 12 и 13, так и со входов 7. Если окажется, что Х ) Р, тоустройство приступает к первому такту коррекции ошибок.В первом такте работы устройствав ячейки 14.1, 14.2 и 14.3 регистра14 записываются коды чисел Р, Х и0 соответственно, в ячейки 36,1, 36.2и 36,3 регистра 36 блока 28 - значения О, ) и 0 соответственно, а в ячейки 36,1, 36.2 и 36.3 регистра Зб блока 29 значения 1, 0 и 0 соответственно, При этом снимается блокировкас блоков 23 и 31,Делитель 16 вычисляет отношениеРбеэ восстановления остатка, т.е,ХРвеличину в ", , которая блоком 17 ум 1ножается на Х и полученная, величинавычитается из Р вычитателем 15. Таким образом с выходов 20 блока 2 разрядная цифра а, цепной дроби а,а, поступает на входы 33 блока.При этом блок 28 вычисляет знаменатель Ц,=аподходящей дроби, а блок29 ее числитель Р =1. В этот моментвремени на выходах блоков 28 и 29получим значения а, и 1 соответственно.На выходах блока 3 вычисления поправок после окончания переходныхпроцессов н блоках 30 и 31 имеемРвзначение -"- , которое вычитается иза,числа Х вычитателем 4,(Если окажется, что Ц )Р, то напрямом выходе элемента 2 сравненияи соответственно на выходе 11.3 появится уровень "1", означающий, что необходимо отказаться от дальнейшего декодирования вниду невозможностиисправить число Х , и работа устройства на этом прекращается.,".ами устройства,55 Если окажется, что Ц с Р и Х -Р- -"-Р , то на выходе элемента 22а к фсравнения и на инверсном выходе эле-.мента 22 сравнения появятся уровни."1",вследствие чего на выходе 11.2также появится уровень "1", означаюРщий что Х=Х - в " , Исправленное знаФа,чение числа Х в позиционном или моду"лярном коде снимается с выходов 12или 13 соответственно.Если окажется, что Д, Р , а Х -3 т- в " .Р , то через некоторое время,а,которое необходимо для окончания переходньгх процессов в выш помянутыхблоках, на выходе 27,1 генератора 23появится импульс, под действием которого в ячейки 14.3 и 36,3 будут записаны коды чисел г, =Р-а,Х , а, 1 соответственно (заметим, что ячеек36.3 две: одна в блоке 2 б, вторая вблоке 29). А через некоторое время,когда закончатся переходные процессыв регистрах 4 и 36, появится импульсна выходе 27.2, при этом содержимоерегистров 14 и 36 сдвинется на однуячейку влево,Соответственно после этого наГХ 1выходах блока 2 имеем а =, аРг Йгна выходах блока 3 Р - =Р -- - - ,и ц и ага,+1РгПри этом, если Х -РР и Ц Рц к гРто соответственно Х=Х -Р -г и генеи цратор 23 блокируется уровнем "1" свыхода элемента 23 сравнения, а навыходе 11,2 появляется уровень "1",означающий окончание процесса коррекции,ЕслиР , то происходит отказот дальнейшего декодирования, а еслиРгЦ сР и Х -Р - ) Р , то устроиствоЗи О - кфпродолжит свою работу вьппеописаннымобразом,Таким образом, предлагаемое устройство позволяет контролироватьошибки любой кратности (при соответствующей величине избыточности). Кроме того, отсутствует ПЗУ и все операции выполняются в двоичном коде,соответственно аппаратурная сложностьустройства пропорциональна 1 оягР ипри росте мощности кода она будет расти медленнее, чем для известныхустройств. Формула и з о б р е т е н и я 1, Устройство для контроля ошибокв избыточном модулярнэм капе, содержащее входной преобразователь кода, 10 входы которого являются соответствующими информационными входами устройства, блок вычисления поправок,первые выходы которого подключены кпервым информационным входам блокаанализа, контрольные выходы которогоявляются контрольными выходами устройства, отличающеесятем, что, с целью расширения функциональных возможностей за счет обеспечения исправления ошибок любой заданной кратности, в устройство введеныблок преобразования числа в цепнуюдробь, вычитатель и выходнои преобразователь кода, выходы входного преобразователя кода подключены к соответствующим первым входам вычитателяи информационным входам блока преоб.разования числа в цепную дробь, выхо-ды которого соединены с информационными входами блока вычисления поправок, выходы которого соединены с вторыми входами вычитателя, вь.ходы кото".рого подключены к соответствующимвторым иншормационным входам блокаанализа, входам выходного преобразователя кода и являются первьп".и информационными выходами устройства, управляющие выходы блока анализа соединены с соответствующими управляющими входам;.блока вычисления поправоки блока преобразования числа в цепную дробь, установочные входы которыхсоответственно объединены и являются первыми установочными входами устройства, первые и вторые установочные входы блока анализа являются соответственно вторыми и третьими установочными входами у стройства, выхо"ды выходного преобразователя кода яв"ляются вторыми инФормационными выхо 2, Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок преобразования числа в цепную дробь выполнен на вычитателе делителе, пере- множителе и регистре сдвига, выходы первой ячейки которого подключены к первым входам вычитателя и делителя, выходы которого подключены к первымвходам перемножителя и являются выходами блока, выходы второй ячейки регистра сдвига подключены к вторым входам делителя и перемножителя вы 5 ходы которого соединены с вторыми входами вычитателя, выходы которого подключены к информационным входам третьей ячейки регистра сдвига, информационные входы первой и второй ячеек регистра сдвига являются соответственно установочными и информационными входами блока, входы записи и сдвига регистра сдвига являются соответственно первым и вторым управ ляющими входами блока. 3. Устройство по и. 1, о т л ич а ю щ е е с я тем, что блок анализа выполнен на элементах сравнения,20 элементе И и генераторе импульсов, инверсный выход первого элемента срав. нения соединен с первым входом элемента И, выход второго элемента сравнения подключен к входу генератора импульсов, второму входу элемен та И и является первым контрольным выходом блока, первые входы первого и второго элементов сравнения являются соответственно первыми и вторыми инЛормационными входами блока, вторые входы второго и первого элементов сравнения являются соответственно первыми и вторыми установочными входами блока, выход элемента И и прямой выход первого элемента сравнения являются соответственно вторым и третьим контрольными выходами блока, первый и второй выходы генератора импульсов являются одноименными управляющими выходами блока. 4. Устройство по и, 1, о т л и ч а ю щ е е с я тем, что блок вычисления поправок выполнен на преобразователях кода, делителе и перемножителе, выходы первого преобразователя кода соединены с первыми входами делителя и являются первыми выходами блока, выходы второго преобразователя кода соединены с первыми входами перемножителя, выходы делителя подклю. чены к вторым вХодам перемножителя, информационные входы преобразователей кода соответственно объединены и являются информационными входами блока, первые и вторые управляющие входы преобразователей кода соответственно объединены и являются одноименными управляющими входами блока, вторые входы делителя являются установочными входами блока, выходы перемножителя являются вторыми выходами блока.5. Устройство по и, 4, о т л и - ч а ю щ е е с я тем, что преобразователь кода выполнен на сумматоре, перемножителе и регистре сдвига, выходы первой и второй ячеек которого подключены к первым входам соответст. венно сумматора и перемножителя, выходы которого соединены с вторыми входами сумматора, выходы которого подключены к информационным входам третьей ячейки регистра сдвига и являются выходами преобразователя, вторые входы перемножителя являются информационными входами преобразователя, входы записи и сдвига регистра сдвига являются соответственно первым и вторымуправляющими входами преобразователя.1363484 Составитель О.РевинскийРедактор Т,Лазоренко Техред Л.Сердюкова Корректор И,Муска Заказ 6380/ исное ного коми ии и отк аушская Проектная,оизводственно-полиграфическое предприятие, г. Ужгород,Тираж 900 ВНИИПИ Государств по делам изобрет 13035, Москва, Жета СССРтийаб д, 4/