Устройство для декодирования с коррекцией ошибок

СОка совЕтснихСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 98 1)5 НОЗМ 13 АНИЕ ИЗОБРЕТЕНИЯ ой ковский 5 я к .обработс исправлеГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ П 1 НТ СССР ВТОРСКОМУСВИДЕТЕЛЬ(71) Киевский политехнический инстут им. 50-летия Великой Октябрьссоциалистической революции(56) Авторское свидетельство СССРУ 794728, кл, Н 03 М 13/00, 1981.Авторское свидетельство СССРВ 1446695, кл. Н 03 М 13/00, 29.1(54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯС КОРРЕКЦИЕЙ ОШИБОК(57) Изобретение относитске дискретной информациинием ошибок данных путем контроля избыточности. Устройство может приме-.няться для обнаружения и исправления,ошибок при сборе, хранении и передаче,цифровой информации недвоичным кодомс применением многопозиционных сигналов. Каждый элемент кодовой комбинации, проверочной матрицы и синдромаформируют, хранят и пересылают меяЩублоками в виде набора двоичных цифровых сигналов (многопозиционного сигнала). Целью изобретения являетсяупрощение устройства. Устройство содержит регистры 1, 4, 12 и 13, блок 2сумматоров, блок 3 элементов И, счетчики 5 и 7 импульсов, умножители 9 и10, элемент И 8, блок 6 деления, сум-.маторы 11 и 14, тактовый,.информационные входы и выходы устройства соответственно 15, 16 и 17. 2 ил., 2 табл.4 5 6 7 О О О О 4 5 6 7 3 1 7 5 7 4 1 2 5 2 5,1 2 7 3 6 53 2 46 4 3 О 1 1 2 3 О О О О О О 1 1 2 3 О 2 2 4 6 О 3 3 6 5 О 4 4 3 7 О 5 5 1 4 О 6 6 7 1 О 7 7 5 2 50 55 Изобретение относится к обработке дискретной информации с исправлением ошибок данных путем контроля избыточности и может применяться для обнаружения и исправления одиночных ошибок5 при сборе, хранении и передаче цифровой информации.Целью изобретения является упрощение устройства.ОНа фиг. 1 представлена структурная схема предлагаемого устройства; на ,фиг. 2 - пространственно-временная :диаграмма работы устройстваУстройство содержит регистр 1, "блок 2 сумматоров, блок 3 элементов И, регистр 4, счетчик 5 импульсов,блок 6 деления, счетчик 7 импульсов,элемент И 8, умножители 9 и 10, сумматор 11, регистры 12 и 13, сумматор14, тактовый, информационные входы и выходы устройства соответственно15, 16 и 17. Регистр 1 представляетсобой регистр длиной в и ячеек по шпараллельных двоичных разрядов, каждая 25 из которых принимает одно ш-разрядное двоичное слово. Блок 2 сумматоров представляет собой ш элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и выполняет логическую .функцию поразрядного суммирования30 по шой 2 двух ш-разрядных двоичных чисел, где ш-разрядность кодового символа в декодируемом коде, Блок 3 элементов И представляет собой ш параллельно работающих элементов И с (ш+1) входами, причем (ш+1)-й вход каждого35 элемента подключен к своему разряду выхода регистра 4, а остальные ш входов каждогоэлемента И подключены к соответствующим разрядам выхода счет 40 чика 5, Умножитель 10 может быть организован на основе ПЗУ на (2 ш+1) адресных входах и ш выходах, хранящего таблицу умножения, представленную втабл. 1.Таблица 1.Элементы Элементы второй строки прокода. Й верочной матрицы кода Н Умножитель 9 может быть организован на основе ПЗУ; хранящего таблицу умножения в конечном поле СГ(8) сок ласно табл. 2,Элементы Элементы первой строки прохода Й верочной матрицы кода Н Особенностью. умножителей 10 и 9 является то,.что с их помощью выполняют умножение в конечном поле, например СР(8), элементов кода на элементы одной строки проверочной матрицы систематического кода Н (для умно- жителя 9) и на элементы другой строки матрицы Н (для умножителя 10). Работа предлагаемого устройства основана на выполнении следующего алгоритма декодирования с коррекцией ошибки,Формируют две группы разрядов синдрома Б и Б из элементов кодовой комбинации, поступающей на входы первого и второго умножителей 9 Еу, Ь;,Ойус 1сумма в СР(Ч);элементы проверочной матрицы Н;элементы принятой кодовойкомбинации вида у 9 уЗ у 1 уубу Фу Зу 2 у 11-Б столбца, 3-И строкиматрицы Н, а уи уевпроверочные элементы кодового блока и у- У 1информационные элементыкодового блока.Так, например, для систематического кода с основанием Ч = 2 = 8 матрица Н выглядит следующим образом;5 158410 1 1 2 3 4 5 6.7При этом, если в одном из и элементов кодовой комбинации произошла любая 5 ошибка, то первая группа разрядов Б синдрома представляет собой величину ошибки Р, а вторая Б впроизведение величины ошибки Е на йомер Ь искаженной информационной позиции в кодовой комбинации,Б е 1 1 Б = е 1(4)гЗатем "делят" величину Б г, представленную второй группой разрядов синдрома, на величину ошибки Б = е и определяет номер Ь искаженной информационной позиции.(5)Корректируют искаженную группу информационных разрядов у р отыскивая ее по найденному номеру 1, и прибавляя 5 к ней величину ошибки В . При этом получают истинное значение 1.-й группы данных у , которая была искажена,Ь,ИСт 130Каждый элемент кодовой комбинации и матрицы Н формируют, хранят и пересылают из блока в блок устройства в виде группы, содержащей ш двоичных35 разрядов, и ставят в соответствие одному элементу конечного поля порядкац=2.Исходное состояние устройства характеризуется следующими признаками (фиг. 2): состояния регистра 1 (позиции 18-26), регистра 4 (позиция 29) и счетчика 5 (позиция 30) произвольны; состояния второго счетчика 7, пер". вого 12 и второго 13 регистров нулевые,Пусть для примера ш = 3, когда и = 9. На вход 16 устройства (фиг.1) потактно подают и = 9 групп по ш = 3 двоичных разрядов. Под действием тактовых импульсов, например, по заднему их фронту в регистре 1 эти группы сдвигают и = 9 раз в течение и = 9 тактовр до заполнения региСтра 1 кодовой комбинацией. Процесс продвижения кодового вектора в ячейках регистра 1 данных иллюстрирован на фиг 2 позициями 18-26. 08Одновременно с продвижением групп данных в регистре 1 элементы кодовой комбинации с входа декодера поэлементно подают на первый умножитель 10, в котором происходит умножение на элементы второй строки матрицы Н, и на второй умножитель 9, посредством которого элементы принятого кодового вектора умножаются на элементы первой строки матрицы Н. Произведения этих элементов подают на первый 11 и второй 14 сумматоры, суммируя их с содержимым, хранящимся в регистрах 12 и 13 соответственно., и вновь помещаются для промежуточного хранения в регистры 12 и 13. Так реализуют выполнение в соответствии с выражениями (1) обработки сигналов кода. При этом в регистрах 12 и 13 запоминают сигналы данных по переднему фронту тактового импульса Две группы разрядов проверочного синдрома Б и Бг, сформированные по указанному правилу, подают на блок 6 деления, где определяют номер позиции 1. искаженного элемента посредством деления второй группы разрядов проверочного синдрома, хранящегося в регистре 12,Б г = е 1. на первую группу Б 1 = е, хранящуюся в регистре 3.Задним фронтом и=9-го тактового импульса счетчик 7 устанавливают в нулевое состояние. Его выходные сигналы при этом через элемент И 8 разрешают очередному тактовому импульсу. (фиг. 2, позиции 28 и 31) по переднему его фронту осуществить установку разрядов счетчика 5 и регистра 4 в соответствии с поступившими на их информационные входы сигналами, а именно - записывают в регистр 4 значение ошибкн Р, а в счетчик 5 - сигналы, представляющие собой номер позиции искаженной группы данных в кодовой комбинации, после чего происходит Обнуление первого 12 и второго 13 регистров по заднему фронту тактового .импульса. Момент обнуления регистров 12 и 13 выходным сигналом переноса (переполнения) с выхода счетчика 7 показан на фиг. 2, диаграмма 27.Пусть ошибка произошла на 7-й позиции в первой кодовой комбинации. На. фиг. 2 позициями 18-26 показано продвижение искаженного элемента 7.1 в составе новой кодовой комбинации. По окончании 9-го такта счетчик 7 уста". навливается в состояние "0", и очередным тактовым импульсом записывают в- регистр 4 величину ощибки е = е, а в счетчик 5 - номер Ь (фиг, 2, позиции 29 и 30). Выходными сигналами счетчика 5 в состоянии К = 7 отпирают блок 3 элементов И и разрешают величине ошибки суммироваться в блоке 2 сумматоров с искаженным элементом 7.1 с выхода регистра 1. Скорректированные данные в виде (ш = 3)-разрядного числа снимают с выхода блока 2 сумматоров в интервале от заднего фронта предыдущего тактового импульса и до переднего фронта следующего тактового импульса. Очередность появления данных на выходе устройства проиллюстрирована на фиг, 2, позиция 31, где скорректированный, элемент 7.1 изображен в незаштрихованной области.Коррекцию ошибки на другой позиции регистра 1 данных осуществляют аналогично. Пусть, например, искажен элемент кода на третьей позиции второй кодовой комбинации, обозначенный сим волом 3.2 (фиг, 2, позиции 18-26). После записикодовой комбинации в регистр 1 на выходе регистра 13 присутствует величина ошибки Е = е, а на выходе блока 6 деления - значение ло 30 катора Ь ошибки. По переднему фронту тактового импульса эту информацию записывают импульсом с выхода элемента в регистр 4 и в счетчик 5 (фиг. 2, позиции 29 и 30) соответственно. Съем информации с выхода устройства получателем происходит в середине тактового интервала. При этом посредством счетчика 5, установленного в состояние Ь = 3 = 011 подсчитывают чисю ф. 40 ло сдвигов групп данных в регистре 1 до состояния К = 7, когда на вход блока 2 сумматоров с выхода последней ячейки регистра 1 поступает искаженный элемент второй кодовой комбинации,45 обозначенный символом 3.2 (фиг. 2). После перевода счетчика 5 в состояниеК = 7, его выходными сигналами отпирают блок 3 элементов И и разрешают величине ошибки В суммироваться с искаженной группой данных 3.2 второй кодовой комбинации в блоке .2 суммато" ров. Скорректированный элемент присутствует на выходе блока 2 в интервале от заднего фронта текущего до переднего фронта следующего тактового им пульса. Скорректированная вторая кодовая комбинация показана на фиг. 2, позиция 31, где скорректированный элемент 3.2 изображен в незаштрихованной области. Другие группы разрядов по мере их поступления в блок 2 суммируются с "О", что никак их не из;, - няет.Если ошибка не происходит вовсе, то в регистр 4 величины ошибки записывается "0", и во время коррекции независимо от состояния счетчика 5 все группы разрядов данных, поступающие на вход блока 2, суммируются с нулем, что никак их не изменяет, Сигналы проверочных (избыточных) элементов кода устройство не корректирует, так как в их коррекции нет необходимости и получатель сигналов данных обычно их игнорирует, При этом, если ошибка искажает сигналы проверочного элемента у (выражение 2), которому0соответствует столбец матрицы Н (выражение 3), в регистр 4 запишутся сигналы "0, с которыми в дальнейшем суммируются сигналы данных у - у 7, никак не изменяясь. Если ошибка искажает сигналы проверочного элемента у 9 (выражение 2), которому соответствует1столбецматрицы Н (выражение 3); то сигналы величины ошибки е Ф О, записанные в регистр 4, впоследствии суммируют с сигналами проверочного элемента у 8, искажая его истинное значение. Однако в предлагаемом устройстве для указанного применения так же, как и в известном устройстве, это не является недостатком, так как сигналы данных устройство корректирует надежно (если произошла однократная ошибка), а проверочные сигналы получатель игнорирует.Формула изобретенийУстройство для декодирования с коррекцией ошибок, содержащее первый регистр, выходы которого подключены к первым входам блока сумматоров, тактовый вход первого регистра объединен с тактовыми входами второго и третьего регистров, первого и второго счетчиков импульсов и первым входом элемента И и подключен к тактовому входу устройства, информационные выходы первого счетчика импульсов подключены к вторым входам элемента И, выход которого подключен к установочным входам второго счетчика импульсов и чет-,.1 1 И . 21 и . 1212 2 .г Ф.г 271 гк 17 кг 151 1 2.111 11 1 7.2 6.2 524.2 И 7212 к 1 15.1 ии 211.1 11 1 гг бг 52 г 72 гг 1.гЗЗ 29 0123 7012345673 4 567 аг1 1 г йОННЫЕНЕОПрЕдЕяЕНЬ 6151 1 З. 211; к, 272 67 бг " 2.7 1 г Ц 7 иг.2 Составитель О, ТюринаТехред Л.Олийнык Корректор М, Самборская Редактор И. Горная Заказ 2264Тираж 661 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,10 вертого регистра, выходы которых подключены соответственно к первым и вторым входам блока элементов И, выходы которого подключены к вторым . входам блока сумматоров, выходы кото 5 рого являются выходами устройства, выходы второго и третьего регистров подключены к первым входам первого и второго сумматоров, выходы блока деления подключены к информационным входам второго счетчика импульсоВ, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введены первый и второй умножители, первые входы которых объединены с информационными входами первого регистра и являются информационными входами устройства, вторые входы умножителей объединены и подключены к информационйым выходам первого счетчикаимпульсов, выход переполнения которогоподключен к управляющим входам второго и третьего регистров, выходы первого и второго умножителей подключенысоответственно к вторым входам одноименных сумматоров, выходы которыхподключены к информационным входамсоответственно второго и третьего регистров, первые входы блока деленияподключены к выходам второго регистра, вторые выходы блока деления объединены с информационными входами четвертого регистра и подключены к выходам третьего регистра.