Устройство для исправления двойных и обнаружения многократных ошибок циклическими кодами

(56) Авторское свидетельство СССРОф 556375, кл. Н 04 Ь 1/10, 1975.Авторское свидетельство СССРУ 1061275, кл. Н 04 Ь 1/10, 1982 сши-(54) (57) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯДВОЙНЫХ И ОБНАРУЖЕНИЯ МНОГОКРАТНЫХОШИБОК ЦИКЛИЧЕСКИМИ КОДАМИ, содержащее входной регистр, к первойгруппе входов которого подсоединенывыходы первого блока ключей, последовательно соединенные первый динамический триггер, первый счетчик идешифратор, а также второй, третийи четвертый блоки ключей, триггер,первый делитель, элемент ИЛИ, блокпоразрядного суммирования по модулюдва и второй динамический триггерпри этом информационный вход входного регистра является первым входом устройства, вторым входом которого является вход второго динамического триггера, о т л и ч а ю -щ е е с я тем, что, с целью рарения функциональных возможностейпутем исправления двойных ошибок иуменьшения времени исправления иобнаружения ошибок, введены дваблока определения весовых коэффициентов, второй делитель, второй. счетчик, регистр сдвига, выходной регистр, элемент И и блок элементовИЛИ, выходы которого подключены квторой группе входов входного регистра, выход которого подключеинформационному входу .выходного регистра, к входу стирания которого через элемент И подключен выход триггера, к входу сброса которого, а также к входам сброса первого счетчика, первого делителя и первого динамического триггера подключен первый выход дешифратора, остальные выходы которого через элемент ИЛИ подключены к разрешающему входу третьего блока ключей и первому разрешающему входу первого блока ключей, ко входам которого подключены выходы регистра сдвига, к информационному входу которого, а также к входу сброса второго счетчика, входу второго динамического триггера и информационному входу второго делителя подключен первый выход первого блока определения весовых коэффициентов, второй выход которого подключен к разрешающему входу второго блока ключей, ко входам которого, а также к первым соответствующим входам блока поразрядного суммирования по модулю два и входам третьего блока ключей подсоединены выходы первого делителя, информационный вход которого объединен с информационным входом входного регист ра, к тактовому входу которого, а также к тактовому входу первого делителя подключен выход первого динамического триггера, при этом выходы блока поразрядного суммирования по модулю два подключены ко входам второго блока определения весовых коэффициентов непосредственно и через четвертый блок ключей к первым соот1185611 ветствующим входам блока элементовИЛИ, к вторым соответствующим входамкоторого подлкючены выходы второгоблока ключей, а выходы третьего блока ключей подсоединены ко входам первого блока определения весовых коэфФициентов, причем выход второго динамического триггера подключен ковходу второго счетчика и тактовымвходам регистра сдвига и второго делителя, первый выход которого подключен к первому разрешающему входу четвертого блока ключей, к второму разрешающему входу которого, а также 1Изобретение относится к технике передачи данных и может использовать. ся в устройствах повышения достоверности информации.Цель изобретения - расширение Функциональных возможностей путем исправления двойных ошибок и уменьшения времени исправления и обнаружения ошибок.На чертеже представлено устройстао для исправления двойных и обнаружения многократных ошибок циклическими кодами.Устройство для исправления двойных и обнаружения многократных ошибок циклическйми кодами содержит входнойи выходной 2 регистры, регистр 3 сдвига, первый 4 и второй 5 делители, первый 6 и второй 7 блоки определения весовых коэффициентов, блок 8 поразрядного суммирования по модулю два, первый 9 и второй 10 динамические триггеры, триггер 11, первый 2 и второй 13 счетчики, дешифратор 14, элемент ИЛИ 15, блок элементов ИПИ 16, первый 17, второй 18, третий 19 и четвертый 20 блокй ключей, элемент И 21.Входной регистр 1 представляет собой и ячеек памяти, выполненных на двухступенчатых триггерных структурах, Продвижение информации по регистру осуществляется тактовыми импульсами ТИ 1, Сумматоры по модулю два, стоящие перед каждым разрядом регистра, служат для исправления к второму разрешающему входу первогоблока ключей и входу триггера подключен выход второго блока определения весовых коэффициентов, а выходвторого счетчика поцключен к входамсброса второго динамического триггера и второго делителя, выходы которого подключены к вторым соответствующим входам блока поразрядного суммирования по модулю два, причем выходвыходного регистра и выход элементаИ являются соответственно первым и вторым выходами устройства,2ошибок в кодовой комбинации во времяпередвижения информации по регистру.Первый и второй делители ч и 5представляют собой регистры с обратными связями, содержащие сумматорыпо модулю два, Делители обеспечивают выдачу остатков Е(х), т.е, ужена первом тахте получаем первый остаток Кь(х), на втором - К,(х) и 10 т.д.Первый делитель ч осуществляетделение принимаемой кодовой комбина ции С (х) на образующий полиномР (х). Скорость его работы соответ ствует скорости продвижения информации по входному регистру 1.Второй делитель 5 представляетсобой схему деления одночлена видахз степени Я 3 и - к на Р (х), т,е.20 это датчик первичных остатковК,(х) - Й(х). Скорость работы дели -теля 5 в 1 раз превьппает скоростьпервого делителя ч(ТИ 2 = ЕТИ 1), который содержит схему выделения пе реднего фронта (СВПФ), вырабатывающую короткий импульс из сигнала,поступающего с первого блока б определения весовых коэффициентов.Блоки 6 и 7 определения весовыхкоэффициентов реализованы на различных устройствах, выделяющих кодовыекомбинации с заданным весовым коэффициентом. В предлагаемом устройстве они выполнены на базе устройства выбораиз и, при этом первоеосуществляет выбор комбинации с весовым коэффициентом У2, а второе с И = 1.Устройство для исправления двой - ных и обнаружения многократных ошибок циклическими кодами, работает следующим образом.Принимаемая с первого входа устройства кодовая комбинация под воздействием тактовых импульсов, вырабатываемых первым динамическим 1 О триггером 9, который запускается управляющим сигналом, поступающим на второй. вход устройства, последовательно записывается во входной регистр 1 и делится в первом делителе 15 4 на образующий полином Р(х). Первый счетчик 12 осуществляет подсчет числа, импульсов, поступивших с выхо- да первого динамического триггера 9, а дешифратор 14 выдает сигналы, соот ветствующие п-му, (и + г)-му, (п + + 2 г)-му и т.д. тактовым импульсам.На и-м такте принимаемая комбинация.полностью записывается во входной регистр 1. К тому времени в пер вом делителе 4 содержится остаток, соответствующий последнему Кл(х)-му остатку полного цикла остатков Е(х)- -К (х). При этом сигналом с дешифрал.тора 14, соответствующим и-му такто- ЗО вому импульсу, выработанному первым динамическим триггером 9, через эле - мент ИЛИ 15 открывается третий блок 19 ключей, чем1 еспечивается перепись остатка К (х) на первый блок 6Ьопределения весовых коэффициентов. Если весовой коэффициент данного остатка Ч с 2, то это означает, что в принятой кодовой комбинации не более двух ошибок и полином этой ошибки сосредоточен в первых элементах комбинации и тождественен остатку К,(х), т.е. Е (х) = К(х). Поэтому выходным сигналом (М с 2) с первого блока 6 определения весовых коэффи циентов открывается второй 18 блок ключей и К(х) остаток через блок 16 элементов ИЛИ поступает на один из соответствующих входов сумматоров по модулю два, стоящих перед первыми 5 О е ячейками входного регистра 1. Таким образом, происходит исправление тех элементов кодовой комбинации, которым соответствуют единицы в Е(х).Получение весового коэффициента 55 И (х) ) 2 свидетельствует о том, что"йв кодовой комбинации имеется либо многократная ошибка, либо хотя бы одна из двух ошибок находится за пределами первых г элементов комбинации, либо присутствует одиночная ошибка, находящаяся не в первых Г элементах. Для исключения последних случаев сигнал с выхода первого блока 6 определения весовых коэффициентов (У2) поступает на информационные входы регистра 3 сдвига и второго делителя 5, а также запускает второй информационный динамический триггер 10, тактовые импульсы которого служат для продвижения сигнала, записанного в регистр 3 сдвига и для. его деления во втором делителе 5 на полином Р(х) . Фактически второй делитель 5 осуществляет деление одночлена х степени5Б ), и - 1 с на Р(х), т.е. он является датчиком остатков с весом М 7 й ; -1Таким образом, под действием первого импульса с второго динамического триггера 10 в регистре 3 сдвига "1" записана в первую ячейку, а второй делитель 5 выдает первый остаток Б.(х) матрицы Н , . С кажцйм последующим тактовым импульсом второго динамического триггера 10 вырабатывается следующий остаток и осуществляется продвижение "1" в регистре 3 сдвига на один разряд вправо. При этом скорость работы второго динамического триггера 10 в Е раз больше скорости первого динамического триггера 9, Это связано тем, чтобы до прихода и + 1 (и + г + 1, и + 2 г + + 1, ) тактового импульса второй делитель 5 сумел выдать М линейнонезависимых остатков в областис 1 шдп - 1 с весом Ы ) сЫп - 1.Второй счетчик 13, подсчитав кимпульсов второго динамического триггера 10, осуществляет его остановку и сброс второго делителя 5.Блок 8 поразрядного суммирования по модулю два последовательно выполняет операцию суммирования остатка К(х) с 1 с остатками, выдаваемыми вторым делителем 5, Результаты суммирования поступают на второй блок7 определения весовых коэффициентов, сигнал на выходе которого появляется лишь в случае, когда весовой коэффициент хотя бы одного результирующего остатка будет единичным. Выходной сигнал второго блока 7 определения весовых коэффициентов открывает четвертый блок 20 ключейи остаток с весовым коэффициентомИ = 1 через блок 16 элементов ИЛИ обеспечивает исправление одной из двухошибок, имеющихся в кодовой комбина.ции,Следует заметить, что четвертыйблок 2 О закрыт при отсутствии деления во втором делителе 5, чтообеспечивает устранение ложного появления сигнала с второго блока 7определения весовых коэффициентов.1(ак уже отмечалось, вторая ошибка соответствует номеру остатка иэобласти 1 остатков с У 7 с 1 , - 1,который в сумме с К(х)-м остаткомдля результирующий остаток с единичным весовым коэффициентом, т.е.если на первом такте работы второгодинамического триггера 10 получился остаток с весовым коэффициентомЫ = 1, то вторым искаженным элементом является и-й элемент, если навтором такте - то и + 1 элемент,. если же на К такте - то г + 1 элемент.Так как процесс продвижения 1 в регистре 3 сдвига и выдача остатков вторым делителем 5 осуществляются одними и теми тактовыми импульсами, то содержимое регистра 3 сдвига соответствующее полиному второй ошибки, через первый блок 17 ключей, открываемый сигналами с элемента ИЛИ 15 и второго блока 7 определения весовых коэффициентов, обеспечивает аналогичным образом через сумматоры по модулю два исправление второго искаженного элемента.Если же на и-м такте не было зафиксировано результата суммирования с весом И = 1, то это означает, что в первых элементах кодовой комбинации ошибок нет, Для осуществления такого же анализа последующих элементов комбинации (г + 1, г + 2,2 г) производится уже с остатком К + г(х) процедура, аналогичная остатку Е(х), так как в этом случае входная информация на первый делитель 4 не поступает, Тогда, если остатку В(х) соответствует расположение элементов кодовой комбинации то Р. 2 (х)-му остатку соответствует,его циклический сдвиг на 8. разрядоввправо. Зто позволяет описанным способом исправить имеющиеся ошибки идля этого случая,Таким образом, последовательноанализируя остатки на и-в, (и + г)-м,и(и + 2 г)-м, , (и + ( - + 1)г)-м10 тактах устройство обеспечивает исправление различного сочетания двухошибок, а также любую одиночнуюошибку.Если же и на последнем такте и +15 и+ ( + 1)г соответствующем случаю,когда последние элементы принимаемойкодовой комбинации займут правые г -ячеек входного регистра 1, ни разу 20 не появится сигнал на выходе второгоблока 7 определения весовых коэффициентов, то зто означает, что в кодовой комбинации присутствует ошибка высокой кратности. Отсюда следует,что триггер 11 находится в состоянии"О". Тогда 2 и-м тактовым импульсом сдешифратора 14 откроется элементИ 21 и сигнал с инверсного выходатриггера 11 поступает на второй вы ход устройства в качестве команды"Запрос на повторную передачу принятой комбинации, одновременно стираяв выходном регистре 2 кодовую комбинацию с обнаруженной ошибкой. З 5 В случае отсутствия ошибок в принятой кодовой комбинации информацияс входного регистра 1 переписываетсяв выходной регистр 2 и поступает напервый выход устройства потребителю.40Задним фронтом тактового импульсаосуществляется сброс всех последовательностных узлов устройства: первого делителя 4, первого динамического триггера 9, триггера 11, первого счетчика 12.Установка второго счетчика 13 внулевое состояние осуществляется сигналом с выхода (Ч2) первого блока б определения весовых коэффициентов, после чего устройство готово к приему очередной кодовой комбинации.ец лиал ППП "Патент", г. Ужгород, ул. Проектная, 4 каз 6438/59 Тираж 871 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, РаушсПодписноекомитета СССРи открытийая наб., д. 4/5