Декодер линейных кодов,исправляющий стирания Советский патент 1984 года по МПК H03M13/13 

соединен с входом третьего триггера, выход которого соединен с вторым входом четвертого элемента И, кроме того, выходы генератора проверок соединены с вторыми входами мультиплексора.

2, Декодер по п. 1, отличающийся тем, что матрица состоит из ячеек, каждая из которых содержит первый и второй элементы И и триггер.

выход которого соединен с входами элементов И, вторые входы первого и второго элементов И подключены соответственно к первым и вторым входам матрицы, а выходы элементов И-соответственно к первым и вторым выходам матрицы, при этом первый и второй входы триггера соединены соответственно с третьими и четвертыми входами матрицы.

1. ДЕКОДЕР ЛИНЕЙНЫХ КОДОВ, ИСПРАВЛЯЮЩИЙ СТИРАНИЯ, содержащий регистр, регистр стираний, регистр информации, кодер, дополнительный регистр, пять элементов И, три триггера, датчик разрешающего импульса, блок задержки, блок сумглирования по модулю два, выход первого триггера соединен с первым входом первого элемента И, выход которого соединен с входом блока задержки и входом второго триггера, выход которого соединен с первым входом второго элемента И и с входом .датчика разрешающего импульса, выход которого соединен с первьпч входом третьего элемента И, второй вход которого подключен к первому входу четвертого элемента И, второй вход которого соединен с выходом дополнительного регистра, вход которого соединен с выходом второго элемента И, выходы третьего и четвертого элементов И подключены соответственно к первому и второму выходам декодера, вход регистра информации и вход регистра стираний соединены соответственно с первым и вторым .входами декодера, отличающийс я тем, что, с целью.повышения его быстродействия, в Него введены матрица, блок cy 1мaтopoв по модулю два, блок элементов ИЛИ, регистр преобразований, блок двухвходовых сумматоров по модулю два, элемент ИЛИ, шестой элемент И, мультиплексор, генератор проверок, логический блок, причем вход регистра информации соединен с входом кодера, выходы которого соединены с первыми входами мультиплексора, выходы которого соединены с первыми входами матрицы, первые выходы которой соединены с входами блока сумглаторов по модулю два, выходы которого соединены с первыми входами регистра и первыми входами логического блока, первые выходы которого соединены с входами матрицы, вторые выходы которой соединены с входами блока элементов ИЛИ, выходы которого соединены с первыми входами блока двух- входовых сумматоров по модулю два. § и с первыми входами регистра преоб(Л разований , выходы которого соединены с вторыми входами блока двухвходовых сумматоров по модулю два, выходы которого соединены с третьими входами матрицы, а четвертые входы матрицы g соединены с вторыми выходс1ми логического блока, второй вход которого соединен с входом регистра стираний, а третий выход логического блока соединен с вторым входом регистра преобразЪваний, четвертый выход логического блока соединен с входом перво:л :д го триггера, при этом выход регистра информации соединен с первым входом блока суммирования по модулю два, 42 выход которого соединен с вторым входом второго элемента И, второй вход блока суммирования по модулю два соединен с выходом пятого элемента И, первый вход которого и второй вход регистра соединены с выходом регистра стираний, а второй вход пятого элемента И соединен с первым выходом регистра, вторые выходы которого соединены с входами элемента ИЛИ, выход которого соединен с первым входом шестого элемента И, второй вход которого соединен с выходом блока задержки, а выход шестого элемента И

Изобретение относится к импульсной технике и может быть использова но в системах передачи информации линейными кодами по каналам со стираниями. Известен декодер линейных кодов, исправлякядий стирания, содержащий регистр информации, регистр стираний, сумматор по модулю два, элемен ты И, входы которых соединены с выходами регистра стираний, выходы регистра информации соединены с вхо дами сумматора по модулю два L11. Однако для такого устройства харак терно недостаточно высокое быстродействие. Наиболее близким по технической сущности к изобретению является декодер линейных кодову исправлянягдий стирания содержащий регистр, регис стираний, регистр информации, кодер дополнительный регистр, пять элемен тов И, три триггера датчик разрешаю щего импульса, блок задержки блок суммирования по модулю два, выход первого триггера соединен с первым входом первого элемента И, выход которого соединен с входом блока за держки и входом второго триггера, вы ход которого соединен с первым входо второго элемента И и с входом датчика разрешающего импульса, выход которого соединен с первым входом третьего элемента И, второй вход которого соединен с первым входом че вертого элемента И, второй вход которого соединен с выходом дополни тельного регистра, вход которого сое динен с выходом второго элемента И, выходы третьего и четвертого элементов И подключены соответственно к первому и второму выходам декодера, вход регистра информации и вход регистра стираний соединены соответственно с первым и вторым входами декодера Г23 . Недостатком известного устройства является низкое быстродействие. Цель изобретения - повышение быст родействия декодера. Поставленная цель достигается тем; что в декодер линейных кодов, исправ,ляющий стирания, содержащий региструрегистр стираний, регистр информации, кодер, дополнительный регистр, пять элементов И, три триггера, датчик разрешающего импульса, блок задержки, блок сугпиирования по модулю два, выход первого триггера соединен с первым входом первого элемента И, выход которого соединен с входом блока задержки и входом второго триггера, выход которого соединен с первым входом второго элемента И и с входом датчика разрешающего импульса, выход которого соединен с первым входом третьего элемента И, второй вход которого подключен к первому входу четвертого элемента И, второй вход которого соединен с выходом дополнительного регистра, вход которого соединен с выходом второго элемента И, выходы третьего и четвертого элементов И подключены соответственно к первому и второму выходам декодера, вход регистра информации и вход регистра стираний соединены соответственно с первым и вторым входами декодера, введены матрица, блок сугФ1аторов по модулю два, блок элементов ИЛИ, регистр, преобразований, блок двухвходовых суг/ маторов по модулю два, элемент ИЛИ, шестой элемент И, мультиплексор, генератор проверок, логический блок, причем вход регистра информации соединен с входом кодера, выходы которого соединены с первьц и входами мультиплексора, выходы которого соединены с первыми входами матрицы, первые выходы которой соедине-ны с входами блока сумматоров по модулю два, выходы которого соединены с первыми входами регистра и первыми входами логического блока, первые выходы которого соединены с вторыми входами матрицы, вторые выходы которой соединены с входами блока элементов ИЛИ, выходы которого соединены с первыми входами блока двухвходовых сумматоров по модулю

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

При этом матрица состоит из ячеек, каждая из которых содержит первый и второй элементы И и триггер, выход которого соединен с первыми входами элементов И, вторые входы .первого и второго элементов И подключены соответственно к первым и вторым входам матрицы, а выходы элементов И - соответственно к первым и вторым выходам матрицы, при этом .первый и второй входы триггера соединены соответственно с третьими и четвертыми входами матрицы.

На фиг. 1 представлена блок-схема предлагаемого устройства; на фиг 2 - блок-схема ячейки матрицы, на фиг. 3 - временные диаграммы, поясняющие принцип работы декодера.

Устройство содержит регистр 1, регистр 2 стираний, регистр 3 информации, кодер 4, дополнительный ре.гистр 5. пять элементов И 6-10, триггеры 11-13, датчик 14 разрешающе-го импульса, блок 15 задержки, блок 16 сумглирования по модулю 2, матрицу 17, состоящую из ячеек 18, блок

19суг/1маторов по модулю 2, блок

20элементов ИЛИ, регистр 21 преобразований, блок 22 двухвходовых сумматоров по модулю 2, элемент ИЛИ 23, шестой элемент И 24, мультиплексор 25, генератор 26 проверок, логический блок 27, первый 28 и второй 29 выходы декодера, первый 5о и второй 31 его входы, каждая ячейка 18 матрицы 17 состоит из элементов И 32 и 33 и триггера 34. .

Входной сигнал поступает на регистр 3 информации и на кодер 4, выходы которого через мультиплексор 25 соединены с первыми входами матри0цы 17. Другие входы мультиплексора 25 соединены с выходами генератора 26 проверок, а первые выходы матрицы 17 - с входами блока 19 сумматоров по модулю два, выходы которого соедине5ны с входами регистра 1 и входами логического блока 27, первые и вторые выходы которого соединены с вторыг и и третьими входами матрицы 17, вторые выходы которой подключены к

0 входам блока 20 элементов ИЛИ, выходы которого соединены с первыми входами блока 22 двухвходовых сумматоров по модулю два, а также с-первь 1И входами регистра 21 преобразо5ваний, выходы которого соединены с вторыми входами блока 22 двухвходовых сумматоров по модулю два, выходы которого соединены с четвертыми входами матрицы 17-, третий выход логи0ческого блока 27 подключен к второму входу регистра 21 преобразований, четвертый выход блока 27 через первый триггер 11 и первый элемент И 6 подключен к входам блока 15 задержки и

5 второго триггера 12, выход которого соединен с датчиком 1 разрешакмцего импульса и первьп входом второго элемента И 7, выход которого соединен с входом дополнительного регистра 5, выход которого соединен с первым вхо0дом четвертого элемента И 9, второй вход которого подключен к выходу третьего триггера 13 и второму входу третьего элемента И 8 первый вход которого соединен с выходом датчика

5 14 разрешающего импульса, а выход с первым выходом 28. вход триггера 13 соединен с выходом шестого элемента И 24, первый вход которого соединен с выходом блока 15 задержки, а

0 второй вход - с выходом элемента ИЛИ 23, входы которого соединены с выходами регистра 1, другой выход которого соединен с первым входом пятого элемента И 10, выход которого сое5динен с первым входом блока 16 суммирования по модулю два, выход которого соединен с вторым входом.второго элемента И 7, а другой вход блока 16 суммирования по модулю два соединен с выходом регистра 3 инфор0мации, выход регистра 2 стираний соединен с входом регистра 1 и вторым ; входом пятого элемента И 10, а вход регистра 2 стираний - с входом логического блока 27.

5 Сущность изобретения заключается в последовательном, одновременно со скоростью поступления входной инфор мации, решении линейных уравнений путем нахождения обратнойматрицы 1Н.Г s (1 ,. , . где ИНН - матрица, образованная и матрицы проверок методо указанным ниже, Е(. - вектор ошибок на стерты позициях; S - вектор синдрома ошибок. Покажем, что решение данного ура нения исправляет стирания. Действительно; известно, что если имеется входной вектор Ъ и проверочная матр ца ИНН , для линейных кодов вектор синдрома s S (НГ Е н Н 1 , знак Т - транспонирование матрицы. Так к предлагаемый декодер исправляет тЪл ко стирания, ошибка возможна только на тех позициях (разрядах) входного слова, где происходит стирание Следовательно, можно записать S ЕС Н Hell , где матрица, получающаяся из матрицы 1Н| выбором тех столбцов, номера которых совпадают с номером того разряда входного слова, г происходит стирание. Из последнего выражения следует Е; н , Устройство работает следующим образом. В исходном состоянии в ячейках 18 матрицы 17 (обозначаемой в даль нейшем М), соответствующих главной диагонали, записаны 1, а в осталь ных ячейках 18 - в триггерах 1 и 11 - 1, а в триггере 12 - О. Принятое входное слово, в котором символы, соответствующие стертым по зициям, заменены на О, последовательно записывается в регистр 3 ийформации и одновременно поступает на кодер 4, на выход которого после Приема выдается вектор синдрома оши бок s (при отсутствии ошибок вектор синдрома равен нулю. Вектор стираний С, в котором 1 расположены на позициях, соответствующих стираниям, а на остальных по зициях - О, записывается в регистр 2 стираний и одновременно поступает в логический блок 27. В генераторе 26 проверок последовательно формируются п векторов-столбцов проверочной матрицы ННц (очередной векторстолбец соответствует номеру позиции во входном кодовом слове 1. Во время приема входного кодового слова мультиплексор 25 обеспечивает соединение выхода генератора 26 проверок с входами ячеек 18 матрицы 17, а после приема входного слова на вход матрицы 17 поступает синдром с выхода кодера 4. Вектор-столбец проверочной матрицы 1Н| параллельно поступает на все строки матрицы 17 ( на вторые входы первого элемента И 32 ячейки 18 матрицы 17) и логически перемножается с векторами-строками. Сигналы с выходов первого элемента И 32 ячеек матрицы 17 с каждой строки поступают на вход блока 19 сумматоров по модулю два. Следовательно, на выходе блока 19 получается преобразованный вектор-столбец, который поступает в логический блок 27. Таким образом, производится умножение век-, тор-столбца 1Г проверочной матрицы (1Н1( справа на матрицу М 11М11Л hj , ht, -ffi fV Ц-2 + -,r 12 bli MII ht, ® Мгг . . . + Mr, hi, Ф U,h. + . :. + , . Пока в принятом кодовом слове отсутствуют стирания,.в матрице IIMii записана единичная матрица llli и, следовательно, при умножении на единичную матрицу вектор-столбца последний не изменяется, т.е. ll I (I h Ь . При поступлении стертой позиции во входном слове (в векторе стираний с на данной позиции присутствует I) подается сигнал (QJ.) на второй вход второго элементл И 33 тех ячеек 18 матрицы 17 1М|, номера, строк которых совпадают с порядковым номером стирания, на время, равное половине первого периода поступления позиций входного слова, т.е. определяется длительностью тактовых импульсов Т логического блока 27 (фиг. 31 . Информация, записанная в j строке матрицы 17 М|, через блок 20 элементов ИЛИ поступает на входы регистра 21 преобразований и по заднему фронту сигналов (о) поступление импульса записи Cj из логического блока 27 на тактовый вход) записывается в регистр 21 преобразований. Сигналы ;Q) имеют вид а o,,cj, vCIЛ(.лh;лh л ...лК., л IniV v л hi л... А Hl-i Л 4ii V ...V qi-fAitH А Hi

В лог1 ческом блоке; 27 производится анализ преобразованного векторастолбца h на равенство I содержимого о ячейки матрицы, т.е. элe 1eнта вектор-столбца ТГ , номер которого равен порядковому номеру стирани

При равенстве 1 в конце периода позиции со стиранием (по заднему фронту на тактовые входы триггеров 34 элементов матрицы 17 1М)тех строчек, номера которых соответствуют номерам элементов преобразованного вектора-столбца h- , содержащих 1 ( за исключением строчки с номером л) подаются из логического блока 27 перепады напряжений - сигналы

fi --с,,/ (-h-t V qii), где cr-(qoAh;vc54AhiV...vc5iAh v...V(i.,

обеспечивающие суммирование по модулю два содержимого этих строчек с содержимым регистра 21 преобразований Это связано с тем, что информация с выхода регистра 21 преобразований, пройдя без изменения через блок 22 двухвходовых суг1маторов по модулю два, на вторые входы которых поданы О, подается на первые входы триггеров 34 ячеек 18 матрицы 17 Ш1. Су1/5мирование по модулю два обеспечивается использованием JK-триггеро в качестве триггеров 34 ячеек 18 матрицы 17 МI.

При равенстве 0 J-ro элемента вектора-столбца h: в логическом блоке 27 отыскивается (с помощью сигналов ) элемент преобразованного ветор-столбца h-i , номер которого ,V является бли; .айишм больщим Л с содержимым I. При этом подается сигнал на второй вход вторых элементов И 33 ячеек 18 матрицы 17 im на время, равное второй половине периода поступления позиции входного слова со стиранием (а) . Информация, записанная в строке У матрицы 17 Itll, через блок 20 элементов ИЛИ поступает на первые входы блока 22 двухвходовых сумматоров по модулю 2. Сигналы с выходов блока 22 двухвходовых сумматоров по модулю 2 поступают на первые входы триггеров 34 ячеек 18 матрицы 17, В конце периода позиции со стиранием (по заднему фронту) на тактовые входы триггеров 34 ячеек 18 матрицы 17 тех строчек, номера которых соответствуют номерам элементов преобразованного вектор-столбца Ь . содержащих 1, и строчке .с номером .1, подаются из логического блока 27 перепады напряжений (f), обеспечивающие суммирование по модулю два содержимого этих строчек с информацией на выходе блока 2 двухвходовых сумматоров по модулю два.

После приема всего входного слова в матрице 17 iMi записана матрица, обратная матрице

il Mil Ч Нс1Г

Если при приеме входного слова оказывается,, что число стираний больиме г, или при анализе какоголибо преобразованного вектора-столб0 Ца h{, у которого содержимое элемента с номером ,1 равноJO, не найдется в вектор-столбце h , содержащего 1, элемента с номером J J , т.е. обратная матрица не сущест5 вует, данная комбинация стираний исправлена быть не может и логический блок вырабатывает сигнал Отказ от декодирования по стираниям Ц1УС „л1лоЛИ,л ,..л Wr.1VC5,лh...hr.,v..v(л«.;),

Q устанавливающий первый триггер 11 в состояние О. Вектор синдрома ошибок S после приема входного кодового слова, пройдя с выхода кодера 4 через мультиплексор 25, умножается.

5 справа на матрицуiMi и преобразованный вектор синдрома ошибок с выхода блока 19 сумматоров записывается в регистр 1

Е Ц Mll-S . S

В преобразованном векторе синдрома ошибок О соответствует правильной замене позиции со стиранием во входном слове, а 1 - ошибочной,

Далее производится п последовательных сдвигов содержимого регистра 3 информации и регистра 2 стираний. Содержимое регистра 1 преобразованного вектора синдрома ошибок сдвигается только при наличии I на выходе регистра 2 стираний, поступающей на управляющий вход регистра 1. Исправление ошибочной замены позиций со стиранием во входном слове осуществляется в блоке 16 суммирования по модулю два, на один вход которого поступает последовательно информация из регистра 3, а на второй - информация из регистра 1, стробируемая на элементе И 10 сигналами из регистра 2 стираний.

Исправленное слово с выхода блока 16 суммирования по модулю два записывается в дополнительный регистр 5, если на вход элемента И 7 подается 1 с выхода триггера 12. Если за время приема входного слова не образовывается сигнал Отказ от декодирования по стираниям и

триггер 11 остается в состоянии 1, управляющий сигнал проходит через элемент И б, устанавливает триггер 12 в состояние 1, при этом происходит запись исправленного слова в

дополнительный регистр 5 и одновре

менно запускается датчик 14 разрешающего импульса, а также сигнал с выхода элемента И 6 поступает на блок 15 задержки.

После записи всего слова в дополнительный регистр 5 в регистре 1 преобразованного вектора сидрома должны быть записаны все нули, если в принятом слове нет обнаруживаемых кодом ошибок, приводящих к переходу элементов входного слова из 1 в О или из О .в 1. Наличие хотя бы одной единицы в регистре 1 говорит об обнаружении ошибки и об отказе от декодирования. В этом случае будет 1 на выходе элемента ИЛИ 23 Этот сигнал разрешает задержанному в блоке 15 задержки сигналу с выхода элемента И б установить триггер 13 в нулевое состояние, Следовательно исправленное слово из дополнительного регистра 5 и импульс разрешения с датчика 14 разрешающего импульса

К

через элементы И 9 и И 8 не проходят на выходы 29 и 28 соответственно.

Если при декодировании нет сигнала Отказа от декодирования по стираниям и нет обнаруживаемой ошибки во входном слове, исправленное слово из дополнительного регистра 5 и импульс разрешения с датчика 14 разрешающего импульса через элемент 9 и 8 И проходят на выходы 29 и 28 соответственно.

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

ь

r-1 r-i m r-L ГП r