Декодер линейных кодов, исправляющий стирания

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК В 1 )ЮЧ 1,1 Ц ИБ ИСАНИЕ ИЗОБРЕТЕНИТОРСКОМУ СВИДЕТЕЛЬСТВУ К ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ"Связь", 1968, с, 105-109.2, Авторское свидетельство СССРР 651479, кл. Н 0 3 К 13/32, 01,04.77.(54)(57) 1, ДЕКОДЕР ЛИНЕЙНЫХ КОДОВ, ИСПРАВЛЯ 01 ИЙ СТИРАНИЯ, содержащий регистр, регистр стираний, регистр информации, кодер, дополнительный регистр, пять элементов И, три триггера, датчик разрешающего импульса, блок задержки, блок суммирования по модулю два, выход первого триггера соединен с первым входом первого элемента И, выход которого соединен с входом блока задержки и входом второго триггера, выход которого соединен с первым входом второго элемента И и с входом, датчика разрешающего импульса, выход которого соединен с первым входом третьего элемента И, второй вход которого подключен к первому входу четвертого элемента И, второй вход которого соединен с выходом дополнительного регистра, вход которого соединен с выходом второго элемента И, выходы третьего и четвертого элементов И подключены соответственно к первому и второму выходам декодера, вход регистра информации и вход регистра стираний соединены соответственно с первым и вторым .входами декодера, о т л и ч а ю щ и й с я тем, что, с целью, повышения его быстродействия, в него введены матрица, блок сумматоров по модулю два, блок элементов ИЛИ, регистр преобразований, блок двухвходовых сумматоров по модулю два, элемент ИЛИ, шестой элемент И, мультиплексор, генератор проверок, логический блок, при. чем вход регистра информации соединен с входом кодера, выходы которого соединены с первыми входами мультиплексора выходы которого соединены с первыми входами матрицы, первые выходы которой соединены с входами блока сумматоров по модулю два, выходы которого соединены с первыми входами регистра и первыми входами логического блока, первые выходы которого соединены с вторыми входамилатрицы, вторые выходй которой соединены с входами блока элементов ИЛИ, выходы которогб соединены с первыми входами блока двухвходовых сумматоров по модулю два, ф и с первыми входами регистра преобразований, выходы которого соединены с вторыми входами блока двухвходовых сумматоров по модулю цва,выходы которого соединены с третьими входами матрицы, а четвертые входы матрицы Я соединены с вторыми выходами логического блока, второй вход которого соединен с входом регистра стираний, а третий выход логического блока соединен с вторым входомрегистра пре- образований, четвертый выход логичес кого блока соединен с входом первого триггера, при этом выход регистра информации соединен с первым входом блока суммирования по модулю два, выход которого соединен с вторым входом второго элемента И, второй вход блока суммирования по модулю два соединен с выходом пятого элемента И, первый вход которого и второй вход регистра. соединены с выходом регистр стираний, а второй вход пятого элемента И соединен с первым выходом регистра, вторые выходы которого соединены с Входами элемента ИЛИ, выход которого соединен с первым входом шестого элемента И, второй вход которого соединен с выходом блока задержки, а выход шестого элемента И1112554 соединен с входом третьего триггера, выход которого соединен с вторым входом четвертого элемента И, кроме того, выходы генератора. проверок соединены с вторыми входами мультиплексора.2. Декодер по п. 1, о т л и ч а ющ и й с я тем, что матрица состоит из ячеек, каждая из которых содержитпервый и второй элементы И и триггер,1Изобретение относится к импульсной технике и может быть использовано в системах передачи информациилинейными кодами по каналам со стираниями. 5Известен декодер линейных кодов,исправляющий стирания, содержащийрегистр информации, регистр стираний, сумматор по модулю два, элементы Й, входы которых соединены с выходами регистра стираний, выходырегистра информации соединены с входами сумматора по модулю два 13.Однако для такого устройства харак-терно недостаточно высокое быстродействие.Наиболее близким по техническойсущности к изобретению является декодер линейных кодовл исправляющийстирания, содержащий регистр, регистрстираний, регистр информации, кодер, 20дополнительный регистр, пять элементов И, три триггера, датчик разрешающего импульса, блок задержки, блоксуммирования по модулю два выходпервого триггера соединен с первымвходом первого элемента И, выходкоторого соединен с входом блока задержки и входом второго триггера, выход которого соединен с первым входомвторого элемента И и с входом датчика разрешающего импульса, выход которого соединен с первым входом третьего элемента И, второй вход которого соединен с первым входом четвертого элемента И, второй вход 35которого соединен с выходом дополнительного регистра, вход которого соединен с выходом второго элемента И,выходы третьего и четвертого элементов И подключены соответственно к 40первому и второму выходам декодера,вход регистра информации и вход регистра стираний соединены соответственно с первым и вторым входами .декодера ,"23.4Недостатком известного устройстваявляется низкое быстродействие.Цель изобретения - повышение быстродействия декодера,выход которого соединен с первымивходами элементов И, вторые входыпервого и второго элементов И подключены соответственно к первым ивторым входам матрицы, а выходы элементов И-соответственно к первым ивторым выходам матрицы, при этомпервый и второй входы триггера соедийены соответственно с третьими ичетвертыми входами матрицы. 2Поставленная цель достигается тем; что в декодер линейных кодов. исправляющий стирания, содержащий регистр регистр стираний, регистр информации, кодер, дополнительный регистр, пять элементов Ч,три триггера, датчик разрешающего импульса, блок задержки, , блок суммирования по модулю два, 1выход первого триггера соединен с первым входом первого элемента И, выход которого соединен с входом блока задержки и входом второго триггера, выход которого соединен с первым входом второго элемента И и с входом датчика разрешающего импульса, выход которого соединен с первым входом третьего элемента И, второй вход которого подключен к первому входу четвертого элемента И, второй вход которого соединен с выходом дополнительного регистра, вход которого соединен с выходом второго элемента И, выходы третьего и четвертого элементов И подключены соответственно к первому и второму выходам декодера, вход регистра информации и вход регистра стираний соединены соответственно с первым и вторым входами декодера, введены матрица, блок сумматоров по модулю два, блок элементов ИЛИ, регистр. преобразований, блок двухвходовых сумматоров по модулю два, элемент ИЛИ, шестой элемент И, мультиплексор, генератор проверок, логический блок, причем вход регистра информации соединен с входом кодера, выходы которого соединены с первыми входами мультиплексора, выходы которого соединены с первыми входами матрицы, первые выходы которой соединеяы с входами блока сумматоров по модулю два, выходы которого соединены с первыми входами регистра и первыми входами логического блока, первые выходы которого соединены с вторыми входами латрицы, вторые выходы которой соединены с входами блока элементов ИЛИ, выходы которого соединены с первыми входами блока двухвходовых сумматоров по модулюдва и с первыми входами регистра преобразований, выходы которого соединены с вторыми входами блока двухвходовых сумматоров по модулю два, выходы которого соединены с третьими вхо" дами матрицы, а четвертые входы матри цы соединены с вторыми выходами логического блока, второй вход которого соединен с входом регистра стираний, а третий выход логического блока соединен с вторым входом регистра преобразований, четвертый выход логического блока соединен с входом первого триггера, при этом выход регистра информации соединен с первым входом блока суммирования по модулю два, выход которого соединен с вторым входомвторого элемента И, второй вход блоа суммирования по модулю два соединен с выходом пятого элемента И, первый вход которого и второй вход регистра соединены с выходом регистра стираний, а второй вход пятого элемента И соединен с первым выходом регистра, вторые выходы которого соединены с входами элемента ИЛИ, выход которого соединен с первым входом шестого элемента И, второй вход которого соединен с выходом блока задержки, а выход шестого элемента И соединен с входом третьего триггера, выход которого соединен с вторым входом четвертого элемента И, кроме того, выходы генератора проверок соединены с вторыми входами мультиплексора.Лри этом матрица состоит из ячеек, каждая иэ которых содержит первый и второй элементы И и триггер, выход которого соединен с первыми входами элементов И, вторые входы .первого и второго элементов И подключены соответственно к первым и вторым входам матрицы, а выходы элементов И - соответственно к первым и вторым выходам матрицы, при этом ,первый и второй входы триггера соединены соответственно с третьими и четвертыми входами матрицы.На фиг. 1 представлена блок-схема предлагаемого устройства; на фиг.2 - блок-схема ячейки матрицы, на фиг. 3 - временные диаграммы, поясняющие принцип работы декодера,Устройство содержит регистр 1, регистр 2 стираний, регистр 3 информации, кодер 4, дополнительный регистр 5, пять элементов И 6-10, триггеры 11-13, датчик 14 раэрешающе .го импульса, блок 15 задержки, блок 16 суммирования по модулю "2", матрицу 17, состоящую из ячеек 18, блок 19 сумматоров по модулю "2", блок 20 элементов ИЛИ, регистр 21 преобразований, блок 22 двухвходовых сумматоров по модулю "2", элемент ИЛИ 23, шестой элемент И 24, мультиплексор 25, генератор 26 проверок,логический блок 27, первый 28 и второй 29 выходы декодера, первый 30 ивторой 31 его входы, каждая ячейка 18матрицы 17 состоит из элементов И 5 32 и 33 и триггера 34. Входной сигнал поступает на регистр 3 информации и на кодер 4,выходы которого через мультиплексор 10 25 соединены с первыми входами матри,цы 17, Другие входы мультиплексора 25соединены с выходами генератора 26проверок, а первые выходы матрицы17 - с входами блока 19 сумматоров по 5 модулю два, выходы которого соединены с входами регистра 1 и входамилогического блока 27, первые и вторые выходы которого соединены с вторыми и третьими входами матрицы 17,вторые выходы которой подключены квходам блока 20 элементов ИЛИ, выходы которого соединены с первымивходами блока 22 двухвходовых сумматоров по модулю два, а также с первыми входами регистра 21 преобразований, выходы которого соединены свторыми входами блока 22 двухвходовых сумматоров по модулю два, выходыкоторого соединены с четвертыми входами матрицы 17; третий выход логиЗ 0 ческого блока 27 подключен к второмувходу регистра 21 преобразований, четвертый выход блока 27 через первыйтриггер 11 и первый элемент И 6 подключен к входам блока 15 задержки и 35 второго триггера 12, выход которогосоединен с датчиком 1 Ф разрешающегоимпульса и первым входом второго элемента И 7, выход которого соединен свходом дополнительного регистра 5, 40 выход которого соединен с первым входом четвертого элемента И 9, второйвход которого подключен к выходу третьего триггера 13 и второму входутретьего элемента И 8 первый вход 45 которого соединен с выходом датчика14 разрешающего импульса, а выход -с первым выходом 28, вход триггера13 соединен с выходом шестого элемента И 24, первый вход которого соединен с выходом блока 15 задержки, авторой вход - с выходом элемента ИЛИ23, входы которого соединены с выходами регистра 1, другой выход которого соединен с первым входом пятого элемента И 10, выход которого сое динен с первым входом блока 16 суммирования по модулю два, выход которого соединен с вторым входом. второго элемента И 7, а другой вход блока 16 суммирования по модулю два 60 соединен с выходом регистра 3 информации, выход регистра 2 стираний соединен с входом регистра 1 и вторымвходом пятого элемента И 10, а входрегистра 2 стираний - с входом логического блока 27.1112554 Сущность изобретения заключается в последовательном, одновременно со скоростью поступления входной информации, решении линейных уравнений путем нахождения обратной матрицыНс 15 Б = ( Н 1 Е где 11 Н 11 - матрица, образованная изматрицы проверок методом,10указанным ниже,Ес - вектор ошибок на стертыхпозициях,Я - вектор синдрома ошибок.Покажем, что решение данного уравнения исправляет стирания. Действительно, известно, что если имеется входной вектор Ь и проверочная матрица (Н 8 , для линейных кодов вектор синдрома Б = ь (Н 1 = Е ( Н 1, знак Т - транспонирование матрицы. Так как 20 предлагаемый декодер исправляет только стирания, ошибка возможна только на тех позициях (разрядах) входного слова, где происходит стирание. Следовательно, можно записать25+ Мг 1 Я = Е 1 Нс 11 30 Ес = 1( с 11(Ь, = 1,Информация, записанная встроке матрицы 17 М 1, через блок 20 элементов ИЛИ поступает на входы регистра 21 преобразований и по заднему фронту сигналов (а,1 поступление импульса записи Сг иэ логического блока 27 на тактовый вход) записывается в регистр 21 преобразований,где 1 Нс( - матрица, получающаяся иэматрицы Н( выбором техстолбцов, номера которыхсовпадают с номером тогоразряда входного слова, гдепроисходит стирание.Из последнего выражения следует Устройство работает следующим образом.В исходном состоянии в ячейках 18 матрицы 17 (обозначаемой в дальнейшем М 1, соответствующих главной диагонали, записаны "1", а в остальных ячейках 18 - "О"; в триггерах 13 45 и 11 - "1", а в триггере 12 - "О". Принятое входное слово, в котором символы, соответствующие стертым позициям, заменены на "О", последовательно записывается в регистр 3 информации и одновременно поступает на кодер 4, на выход которого после приема выдается вектор синдрома ошибок Я (при отсутствии ошибок вектор синдрома равен нули).Вектор стираний С, в котором "1" расположены на позициях, соответствующих стираниям, а на остальных позициях - "О", записывается в регистр 2 стираний и одновременно поступает в логический блок 27. В генераторе 60 26 проверок последовательно формируются и векторов-столбцов проверочной глатрицы Н 1( (очередной вектор- столбец соответствует номеру позиции во входном кодовом слове 1, Во 65 время приема входного кодового словамультиплексор 25 обеспечивает соединение выхода генератора 2 б проверок с входами ячеек 18 матрицы 17, апосле приема входного слова на входматрицы 17 поступает синдром с выхода кодера 4. Вектор-столбец проверочной матрицы (Н 1 параллельно поступает на все строки матрицы 17 ( навторые входЫ первого элемента И 32ячейки 18 матрицы 171 и логическиперемножается с векторами-строками.Сигналы с выходов первого элемента И32 ячеек матрицы 17 с каждой строкипоступают на вход блока 19 сумматоров по модулю два. Следовательно, навыходе блока 19 получается преобразованный вектор-столбец, который поступает в логический блок 27. Такимобразом, производится умножение век-.тор-столбца Г проверочной матрицы11 Н 11 справа на матрицу М(1 М(%,= 1,Ь.й М, й(г++ 1. Н- 1 Л Ь;М, Н + .,+ М, Ь Пока в принятом кодовом слове отсутствуют стирания, в матрице (1 М 11 записана единичная матрица 1(1 и, следовательно, при умножении на единичнуи матрицу вектор-столбца последний не изменяется, т.е. При поступлении стертой позиции во входном слове ,в векторе стираний с на данной позиции присутствует "1") подается сигнал (а;) на второй вход второго элеглента И 33 тех ячеек 18 матрицы 17 (М(, номера строк которых совпадают с порядковым номером стирания, на время, равное половине первого периода поступления позиций входного слова, т.е, определяется длительностью тактовых импульсов Т логического блока 27 (фиг.31. Сигналы (а ) имеют вид а; ==,лс 1 чс,л,л 1, л йл лй 1, л и;ч чс,лЬ;л.д И(-1 лИ;ч,ч;.,лфи.л 4менно запускается датчик 14 разрешающего импульса, а также сигнал с выхода элемента И б поступает на блок 15 задержки.После записи всего слова в дополнительный регистр 5 в регистре 1 5 преобразованного вектора сидрома должны быть записаны все нули, еслив принятом слове нет обнаруживаемых кодом ошибок, приводящих к переходу элементов входного слова из "1 ф в 10 "0" или из "0" .в "1 ф. Наличие хотя бы одной единицы в регистре 1 говоРит Об обнаружении ошибки и об отказе от декодирования. В этом случае будет "1" на выходе элемента ИЛИ 23. 5 Этот сигнал разрешает задержанномуГ в блоке 15 задержки сигналу с выхода элемента И б установить триггер 13 в нулевое состояние, Следовательно исправленное слово из дополнительно го регистра 5 и импульс разрешения с датчика 14 разрешающего импульса через элементы И 9 и И 8 не проходят на выходы 29 и 28 соответственно.Если при декодировании нет сигнала "Отказа от декодирования по стираниям" и нет обнаруживаемой ошибки во входном слове, исправленное слово из дополнительного регистра 5 и импульс разрешения с датчика 14 разрешающего импульса через элемент 9 и 8 И проходят на выходы 29 и 28 соответственно. Таким образом, введение матрицы, блока сумматоров по модулю два, бло-. ка элементов ИЛИ, регистра преобразований, блока двухвходовых сумматоров по модулю два, элементов ИЛИ и И, мультиплексора, генератора проверок и логического блока позволяет . повысить быстродействие предлагаемого устройства, особенно для кодов, имеющих большую длину информационных символов.1112554 Сщир,с Ус фиг.8 фиг. 3 аэ б 467/43 Тираж 8 б 1 Подпи ВНИИПИ Государственного комитета СССР по делам иэобретений и открытий 113035, Москва, Ж, Раушская наб., д