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

 

УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ДВОЙНЫХ И ОБНАРУЖЕНИЯ МНОГОКРАТНЫХ ОШИБОК ЦИКЛИЧЕСКИМИ КОДАМИ, содержащее входной регистр, к первой группе входов которого подсоединены выходы первого блока ключей, последовательно соединенные первьй динамический триггер, первый счетчик и дешифратор, а также второй, третий и четвертый блоки ключей, триггер, первый делитель, элемент ИЛИ, блок поразрядного суммирования по модулю два и второй динамический триггер,; при этом информационный вход входного регистра является первым входом устройства, вторым входом которого является вход второго динамического триггера, отличающееся тем, что, с целью расптрения функциональньк возможностей путем исправления двойных ошибок и уменьшения времени исправления и обнаружения ошибок, введены два блока определения весовых коэффициентов , второй делитель, второй.счетчик , регистр сдвига, вьпсодной регистр , элемент И и блок элементов ИЛИ, выходы которого подключены к второй группе входов входного регистра , выход которого подключен к информационному входу выходного регистра , к входу стирания которого через элемент И подключен выход триггера, к входу сброса которого, а также к входам сброса первого счетчика , первого делителя и первого динамического триггера подключен первый выход дешифратора, остальные выходы которого через элемент ИЛИ подключены к разрешающему входу третьего блока ключей и первому разрешающему входу первого блока ключей, ко входам которого подклюi чены выХодьГ регистра сдвига, к информационному входу которого, а также к входу сброса второго счетчика , входу второго динамического триггера и информационному входу второго делителя подключен первый выход первого блока определения весовых коэффициентов, второй выход которого подключен к разрешающему 00 входу второго блока ключей, ко входам ел которого, а также к первым соответо ствующим входам блока поразрядного суммирования по модулю два и входам третьего блока ключей подсоединены выходы первого делителя, информационный вход которого объединен с информационным входом входного регистра , к тактовому входу которого, а также к тактовому входу первого делителя подключен выход первого динамического триггера, при этом выходь блока поразрядного суммирования по модулю два подключены ко входам второго блока определения весовых коэффициентов непосредственно и через четвертый блок ключей к первым соот

(21) 3613688/24-09 (22) 22.06.83 (46) 15.10.85. Бюл. Н 38 (72) С. А. Скотарь, Н. И. Науменко, M.Ì.Ãîëóá÷èê и В.Ю.Шакирзянов (53) 621.394.14(088.8) (56) Авторское свидетельство СССР

У 556375, кл . Н 04 Ь 1/10, 1975.

Авторское свидетельство СССР

У 1061275, кл. Н 04 L 1/10, 1982. (54) (57) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ

ДВОЙНЫХ И ОБНАРУЖЕНИЯ МНОГОКРАТНЫХ

ОШИБОК ЦИКЛИЧЕСКИМИ КОДАМИ, содержащее входной регистр, к первой группе входов кс.тoporo подсоединены выходы первого блока ключей, послеДовательно соединенные первый динамический триггер, первый счетчик и дешифратор, а также второй, третий и четвертый блоки ключей, триггер, первый делитель, элемент ИЛИ, блок поразрядного суммирования по модулю два и второй динамический триггер,, при этом информационный вход входного регистра является первым входом устройства, вторым входом которого является вход второго динамического триггера, о т л и ч а ю— щ е е с я тем, что, с целью расши- рения функциональных возможностей путем исправления двойных ошибок и уменьшения времени исправления и обнаружения ошибок, введены два блока определения весовых коэффициентов, второй делитель, второй. счетчик, регистр сдвига, выходной регистр, элемент И и блок элементов

ИЛИ, выходы которого подключены к второй группе входов входного регистра, выход которого подключен к информационному входу .выходного регистра, к входу стирания которого через элемент И подключен выход триггера, к входу сброса которого, а также к входам сброса первого счетчика, первого делителя и первого динамического триггера подключен первый выход дешифратора, остальные выходы которого через элемент ИЛИ подключены к разрешающему входу третьего блока ключей и первому разрешающему входу первого блока ключей, ко входам которого подключены выходы регистра сдвига, к информационному входу которого, а также к входу сброса второго счетчика, входу второго динамического триггера и информационному входу второго делителя подключен первый выход первого блока определения весовых коэффициентов, второй выход которого подключен к разрешающему входу второго блока ключей, ко входам которого, а также к первым соответствующим входам блока поразрядного суммирования по модулю два и входам третьего блока ключей подсоединены выходы первого делителя, информационный вход которого объединен с информационным входом входного регистра, к тактовому входу которого, а также к тактовому входу первого делителя подключен выход первого динамического триггера, при этом выходы блока поразрядного суммирования по модулю два подключены ко входам второго блока определения весовых коэффициентов непосредственно и через четвертый блок ключей к первым соот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 ошибок в кодовой комбинации во время передвижения информации по регистру.

Первый и второй делители 4 и 5 представляют собой регистры с обратными связями, содержащие сумматоры по модулю два. Делители обеспечивают выдачу остатков R(x), т.е. уже на первом тахте получаем первый остаток R (х), на втором — R, {х) и

10 т.д.

Первый делитель 4 осуществляет деление принимаемой кодовой комбина-ции С (х) на образующий полином

Р (х) . Скорость его работы соответ15 ствует скорости продвижения информации по входному регистру 1.

Второй делитель 5 представляет собой схему деления одночлена вида

xS степени Я 3 n — k íà P (х), т.е. уо это датчик первичных остатков

R. (х) — R„(x) . Скорость работы дели— теля 5 в k раз превышает скорость первого делителя 4(ТИ2 = ЕТИ1), который содержит схему выделения пе25 реднего фронта (СВПФ), вырабатывающую короткий импульс из сигнала, поступающего с первого блока 6 определения весовых коэффициентов.

Блоки 6 и 7 определения весовых коэффициентов реализованы на различных устройствах, выделяющих кодовые комбинации с заданным весовым коэффициентом. В предлагаемом устройстве они выполнены на базе устройства выбора из и при этом первое осуществляет выбор комбинации с ве1185611

4 совым коэффициентом W 2, а второе с W = 1.

УстрОФСтво для исправления двой— ных и обнаружения многократных оши— бок циклическими кодами, работает следующим образом.

Принимаемая с первого входа устройства кодовая комбинация под воздействием тактовых импульсов, вырабатываемых первым динамическим 1О триггерам 9, который запускается управляющим сигналом, поступающим на второй. вход устройства, последовательно записывается во входной регистр 1 и делится в первом делителе 15

4 на образующий полином Р(х). Первый счетчик 12 осуществляет подсчет числа, импульсов, поступивших с выхо- да первого динамического триггера 9, а дешифратор 14 выдает сигналы, соот- 20 ветствующие п-му, (n + r) ìó, (п +

+ 2r)-му и т.д. тактовым импульсам.

На и-м такте принимаемая комбинация.полностью записывается во входной регистр 1. К тому времени в пер- 25 вом делителе 4 содержится остаток, соответствующий последнему Rл(х)-му остатку полного цикла остатков R„(x)-R (х). При этом сигналом с дешифрал .тора 14, соответствующим и-му такто- ЗО вому импульсу, выработанному первым динамическим триггером 9, через эле— мент ИЛИ 15 открывается третий блок

19 ключей, чем . 1еспечивается перепись остатка R (х) на первый блок 6

Ь определения весовых коэффициентов.

Если весовой коэффициент данного остатка W < 2, то это означает, что в принятой кодовой комбинации не более двух ошибок и полином этой ошибки сосредоточен в первых элементах комбинации и тождественен остатку

R „(х), т. е. Е „(х) = R(x) . Поэтому выходным сигналом (W 4 2) с первого блока 6 определения весовых коэффициентов открывается второй 18 блок ключей и R„(x) остаток через блок

16 элементов ИЛИ поступает на один из соответствующих входов сумматоров по модулю два, стоящих перед первыми у е ячейками входного регистра 1. Таким образом, происходит исправление тех элементов кодовой комбинации, которым соответствуют единицы в Е(х).

Получение весового коэффициента 55

WО (х) ) 2 свидетельствует о том, что

"й в кодовой комбинации имеется либо многократная ошибка, либо хотя бы одна из двух ошибок находится за пределами первых r элементов комбинации, либо присутствует одиночная ошибка, находящаяся не в первых элементах.

Для исключения последних случаев сигнал с выхода первого блока 6 определения весовых коэффициентов (W 7 2) поступает на информационные входы регистра 3 сдвига и второго делителя

5, а также запускает второй информа ционный динамический триггер 10, 1 тактовые импульсы которого служат для продвижения сигнала, записанного в регистр 3 сдвига и для. его деления во втором делителе 5 на полином Р(х) .

Фактически второй делитель 5 осуществляет деление одночлена х степени

S ) n — k íà P(x), т.е. он является датчиком остатков с весом W 7 dm;Ä -1

Таким образом, под действием первого импульса с второго динамического триггера 10 в регистре 3 сдвига

"1" записана в первую ячейку, а второйй делитель 5 выдает первый остаток

Б.„(х) матрицы Н „, . С каждйм последующим тактовым импульсом второго динамического триггера 10 вырабатывается следующий остаток и осуществляется продвижение "1" в регистре

3 сдвига на один разряд вправо. При этом скорость работы второго динамического триггера 10 в k раз больше скорости первого динамического триггера 9. Это связано тем, чтобы до прихода n + 1 (n + r + 1, n + 2r +

+ 1, ...) тактового импульса второй делитель 5 сумел выдать fc линейнонезависимых остатков в области

dmin — 1 с весом М ) dmin — 1.

Второй счетчик 13, подсчитав к импульсов второго динамического триггера 10, осуществляет его остановку и сброс второго делителя 5.

Блок 8 поразрядного суммирования по модулю два последовательно выполняет операцию суммирования остатка

R„(x) с % остатками, выдаваемыми вторым делителем 5. Результаты суммирования поступают на второй блок

7 определения весовых коэффициентов, сигнал на выходе которого появляется лишь в случае, когда весовой коэффициент хотя бы одного результирующего остатка будет единичным. Выходной сигнал второго блока

7 определения весовых коэффициентов открывает четвертый блок 20 ключей и остаток с весовым коэффициентом

1185611

И = 1 через блок 16 элементов ИЛИ обеспечивает исправление одной из двух ошибок, имеющихся в кодовой комбинации, Следует заметить, что четвертый блок 20 закрыт при отсутствии деления во втором делителе 5, что обеспечивает устранение ложного появления сигнала с второго блока 7 определения весовых коэффициентов.

1(ак уже отмечалось, вторая ошибка соответствует номеру остатка иэ области 1 остатков с M > с1 „, „ — 1, который в сумме с R„(x) ì остатком для результирующий остаток с единичным весовым коэффициентом, т.е. если на первом такте работы второго динамического триггера 10 получился остаток с весовым коэффициентом

Ы = 1, та вторым искаженным элементом является и-й элемент, если на втором такте — то п + 1 элемент, . если же íà g такте — то г + t элемент.

Так как процесс продвижения 1 в регистре 3 сдвига и выдача остатков вторым делителем 5 осуществляются одними и теми тактовыми импульсами, то содержимое регистра 3 сдвига,, соответствующее полиному второй ошибки, через первый блок 17 ключей, открываемый сигналами с элемента

ИЛИ 15 и второго блока 7 определения весовых коэффициентов, обеспечивает аналогичным образом через сумматоры по модулю два исправление второго искаженного элемента.

Если же на и-м такте не было зафиксировано результата суммирования с весом И = 1, то это Означает, что в первых элементах кодовой комбинации ошибок нет. Для осуществления такого же анализа последующих элементов комбинации (r + 1, r + 2, 2r) производится уже с остатком

R„ + r(x) процедура, аналогичная остатку R„(x), так как в этом случае входная информация на первый делитель 4 не поступает. Тогда, если остатку R„(x) соответствует расположение элементов кодовой комбинации::, то Р. >g (х) — му остатку соответствует.

его циклический сдвиг на 8. разрядов вправо. Зто позволяет описанным способом исправить имеющиеся ошибки и для этОГО случая.

Таким образом, последовательно анализируя остатки на n-m, (n + r)-м, п (n + 2r) ì, ..., (n + (— + 1)r)™

10 тактах устройство обеспечивает исправление различного сочетания двух ошибок, а также любую одиночную ошибку.

Если же и на последнем такте n +

15 и

+ (- + 1)г, соответствующем случаю, когда последние элементы принимаемой кодовой комбинации займут правые r— ячеек входного регистра 1, ни paзу

2б не появится сигнал на выходе второго блока 7 определения весовых коэффициентов, то это означает, что в кодовой комбинации присутствует ошибка высокой кратности. Отсюда следует, что триггер 11 находится в состоянии

"0". Тогда 2п-м тактовым импульсом с дешифратора 14 откроется элемент

И 21 и сигнал с инверсного вьгхода триггера 11 поступает на второй выЗ0 ход устройства в качестве команды

"Запрос на повторную передачу принятой комбинации, одновременно стирая в выходном регистре 2 кодовую комбинацию с обнаруженной ошибкой.

З5 В случае отсутствия ошибок в принятой кодовой комбинации информация с входного регистра 1 переписывается в выходной регистр 2 и поступает на первый .выход устройства потребителю. ф)

Задним фронтом тактового импульса осуществляется сброс всех последовательностных узлов устройства: первого делителя 4, первого динамического триггера 9, триггера 11, первого счетчика 12.

Установка второго счетчика 13 в нулевое состояние осуществляется сигналом с выхода (Ч > 2) первого блока б определения весовых коэффициентов, после чего устройство готово к приему очередной кодовой комбинации.

1185611

Составитель С.Осмоловский

Редактор Т.Митейко Техред М.Кузьма Корректор М.Максимишинец

Заказ 6438/59 Тираж 871 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4