Устройство для исправления двойных и обнаружения многократных ошибок циклическими кодами Советский патент 1985 года по МПК H03M13/15 

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

5611

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

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

1

Изобретение относится к технике передачи данных и может использоваться в устройствах повышения достоверности информации.

Цель изобретения - расширение функциональных возможностей путём исправления двойных ошибок и ут-геньшения времени исправления и обнаружения ошибок.

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

Устройство для исправления двойны и обнаружения многократных ошибок циклическими кодами содержит входной 1 и выходной 2 регистры, регистр 3 сдвига, первый 4 и второй 5 делители первый 6 и второй 7 блоки определения весовых коэффициентов, блок 8 поразрядного с т мирования по модулю два, первый 9 и второй 10 динамические триггеры, триггер 11, первый 12 и второй 13 счетчики, дешифратор 14,, элемент. ИЛИ 15, блок элементов ИЛИ 16, первый 17, второй 18, третий 19 и четвертый 20 блоки ключей, элемент И 21.

Входной регистр 1 представляет собой и ячеек памяти, выполненных на двухступенчатых триггерных структурах. Продвижение информации по регистру осуществляется тактовыми импульсами ТИ1. Сумматоры по модулю два, стоящие перед каждым разрядом регистра, служат для исправления

ошибок в кодовой комбинации во врем передвижения информации по регистру

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

Первый делитель 4 осуществляет деление принимаемой кодовой комбинации G (х) на образующий полином Р (х). Скорость его работы соответствует скорости продвижения информации по входному регистру 1.

Второй делитель 5 представляет собой схему деления одночлена вида х степени S : п - k на Р (х), т.е. это датчик первичных остатков R(х) - R(x). Скорость работы делителя 5 в k раз превьппает скорость первого делитепя 4(ТИ2 kTHI), который содержит схему выделения переднего фронта (СВПФ), вырабатывающую короткий импульс из сигнала, поступающего с первого блока 6 определения весовых коэффициентов.

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

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

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

Принимаемая с первого входа устройства кодовая комбинация под воздействием тактовых импульсов, вырабатываемых первым динамическим триггером 9, который запускается управляющим сигналом, поступающим на второй, вход устройства, последовательно записывается во входной регистр 1 и делится в первом делителе t на образующий полином Р(х) . Первьй счетчик 12 осуществляет подсчет чкслз( импульсов, поступивших с выхода первого динамического триггера 9, а дешифратор 14 выдает сигналы, соответствующие , (п + г)-му, (п + + 2г)-му и т,д, тактовым импульсам.

На п-м такте принимаемая комбинация . полностью записывается во входной регистр 1. К тому времени в первом делителе 4 содержится остаток, соответствующий последнему Кр(х)-му остатку полного цикла остатков R(x)-R(x) . При этом сигналом с дешифратора 14, соответствующим п-му тактовому импульсу, вьфаботанному первым динагчическим триггером 9, через элемент Mini 15 открьюается третий блок 19 ключей, чем г эеспечивается перепись остатка R.(x) на первый блок 6 определения весовых коэффициентов. Если весовой коэффициент данного остатка W . 2, то это означает, что в принятой кодовой комбинации не более двух ошибок и полином этой ощибки сосредоточен в первых элементах комб-инадии и тождественен остатку Rf(x), т.е. Е(х) R(x). Поэтому выходным сигналом (W 4 2) с первого блока 6 определения весовых коэффициентов открывается второй 18 блок, ключей и R(x) остаток через блок 16 элементов ИЛИ поступает на один из соответствующих входов сумматоров по модулю два, стоящих перед первыми г ячейками входного регистра 1. Таким образом, происходит исправление тех элементов кодовой комбинации, которым соответствуют единицы в Е(х).

Получение весового коэффициента ifl (х) 7 2 свидетельствует о том, что в кодовой комбинации имеется либо многократная ошибка, либо хотя бы од611

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

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

во втором делителе 5 на полином Р(х). Фактически второй делитель 5 осуществляет деление одночлена х степени S 7 п - k на Р(х), т.е. он является .датчиком остатков с весом -1

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

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

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

прихода п + 1 (п + г + 1, п + 2г + + 1, ...) тактового импульса второй делитель 5 сумел выдать Я линейнонезависимых остатков в области dmin - 1 с весом W 7/ drain - 1.

Второй счетчик 13, подсчитав к

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

Блок 8 поразрядного суммирования

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

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

V/ 1 через блок 16 элементов ИЛИ обеспечивает истфавлёние одной из двух ошибок, HMeFomHxcH в кодовой комбинации .

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

Как уже отмечалось, вторая ошибка соответствует номеру остатка из области 1 остатков с W Ь который в сумме с К(х)-м остатком для разультрфующий остаток с единичным весовым коэффициентом, т.е. если на первом тахте работы второго динамического триггера 10 полу шлся остаток с весовым коэффициентом W ,1, то вторьм искаженным элементом является п-й элемент, если на втором такте - то п + 1 элемент, . если же на К такте - то г + 1 элемент.

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

Если же на п-м такте не было зафиксировано результата суммирования с весом W 1, то это означает, что в первых элементах кодовой комбинацки ошибок нет. Для осуществления такого же анализа последующих t элементов комбинагдии (г + 1, г + 2, ..., 2г) производится уже с остатком R г(х) процедура, аналогичная 0 татку R(x), так как в этом случае входная информация на первый делитель 4 не поступает. Тогда если остатку Rp,(x) соответствует расположение элементов кодовой комбинации:. то R (х)-му остатку соответствуе

его 1Д1клический сдвиг на (. разрядов вправо. Это позволяет описанным способом исправить имеющиеся ошибки и 5 для этого случая.

Таким образом, последовательно анализируя остатки на п-гп, (п + г)-м,

(п + 2г)-м, . , ., (п ( + 1)г)-м

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

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

(5 1)г, соответствующем случаю,

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

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

5 tjTQ триггер 11 находится в состоянии О. Тогда 2п-м тактовым импульсом с дешифратора 14 откроется элемент И 21 и сигнал с инверсного выхода триггера 11 поступает на второй выход устройства в качестве команды

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

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

Установка второго счетчика 13 в нулевое состояние осуществляется сигналом с выхода (W 2) первого

блока 6 определения весовых коэффициентов, после чего устройство готово к приему очередной кодовой комбинации. .-rK;jL-y F Г