Устройство для исправления стираний

СОЮЗ СОВЕТСНИХСОЦИАЛИСТ ПЕСКРЕСПУБЛИН 498 19) 111 3 М 13/02 ГОСУДАРСТВЕННЫПО ИЗОБРЕТЕНИЯМПРИ ГКНТ СССР НОМИТЕТОТНРЫТИЯМ ОПИСАНИЕ ИЗОБРЕТЕНИЯ(56) ский инст О. т рекции синдр макомбинаций в уссления синдромапервой)комбинаци ока 7 ко сраннени ло Б оис о место ьыч ой (кроме и ошибокмодулюрома снои матри МирА 9 78 54) РАНИЙсуществлява ранее тся сложение по ычисленного син требуемым цы. 4 з.и толбцоЙ-лы,ров еро ВТОРСНОМУ СВИДЕТЕЛЬСТВ Д. Карякин В,А. Вишневский, Киреев и А,С, Кузьмук 621,394,14:681.32(Ч 88.8) Берлекэмп Э. Алгебраическая я кодирования, - М,: Мир, 197 5-147.ейхут Р, Теория и практика коконтролирующих ошибки, - М.;1986, с. 165-179.торское свидетельство СССР 030, кл. Н 03 М 3/02, 978. УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ СХИ 5/) Изобретение относится к вычислительной технике и технике связи, Егоиспользование в аппаратуре передачиданных позволяет повысить быстродействие. Устройство содержит буферныйрегистр 1, блок 2 счета стираний,генератор 3 испытательных сигналов, распределитель 4 импульсов, вычислитель 5 синдров и блок 6 замещения символов, Благодаря введениюИзобретение относится к вычисли-:.тельной технике и технике связи иможет быть использовано в аппаратуре 1 О 50Вычислитель 5 синдромов содержит Фиг,4) блок 32 постоянной памяти, демультиплексор 33, блок 34 сумматоров по модулю два, буФерцый регистр 35, формирователь 36 адреса, регистр 37 сдвига, Формирователь 38 импульсов55 сдвига и формирователь 39 имцульсоц синхронизации, На Фиг,4 обозначены первый 40, второй 41 и третьи 4 передачи данных.Цель изобретения - повышение быстродействия устройства,На Фиг. изображена блок-схемаустройства; на фиг,2-4 - блок счетастираний, генератор испытательныхсигналов и вычислитель синдромов.соответственно,.Устройство для исправления стираний содержит буферный регистр 1,блок 2 счета стираний, генератор 3испытательных сигналов, распределитель 4 импульсов, вычислитель 5 синдромов, блок 6 замещения символов,блок 7 коррекции синдрома и блок 8сравнения кобинаций, На фиг, 1 обозначены информационный вход 9, вход10 стираний, тактовый вход 1 1 ивыход 12 устройства.Блок 2 счета стираний выполнен( Фиг.2) на первом 13 и втором 14 25двоичных счетчиках, дешифрГторе 15и ключевом элементе 16, На фиг,2обозначены управляющий вход 17, так 1 товый вход 18, первые 19 и второй 20и третьи 21 выходы блока 2,30Генератор 3 испытательных сигналов включает в себя Фиг,3) первый 22и второй 23 элементы ИЛИ, элементИ 24, элемент НЕ 25, двоичный счетчик 26 и элементы ИСКЛЧЧАЩЕЕ ИЛИ 27.На Фиг.3 обозначены первый 28, вторые 29 и третий 30 входы и выходы 31генератора 3, Генератор 3 представляет собой генератор кода Грея, гдекаждая следующая выходная комбинация 40отличается от предыдущей ровно в одном элементе. На фиг.3 обозначено кодовое расстояние с используемого(принимаемого) кода.Распределитель 4 импульсов представляет собой Фактически демультиплексор, устанавливающий уровеньлогической единицы на выходе в соответствии с входным кодом,входы, первые 43 и второй 44 выходывычислителя 5,Блок 6 замещения символов выполнентак же, как комбинационная логическая схема известного устройства,Блок 7 коррекции синдрома предназначен для заполнения синдрома и суммирования его с вектором-столбцом проверочной матрицы, реализуется в соответствии с выбранным кодом на регистрахи сумматорах по модулю два.Блок Я сравнения комбинаций служитдля выделения отличающихся разрядовв двух следующих друг за другом испытательных сигналах, реализуется на регистрах и сумматорах по модулю два.Формирователь 36 адреса выполнен(Фиг.4 ) на мультиплексоре 45, элементе ИЛИ 46, ключевом элементе 47 идвоичном счетчике 48,Сущность изобретения заключаетсяв отказе от громоздкого вычислениясиндрома для каждой, кроме первой,комбинации ошибок, заключающегося вделении многочлена принятого кодовогослова на проверочный полином или в умножении его ца проверочную матрицу,Вместо этой процедуры в блоке 7 коррекции синдрома используется операциясложения по модулю два ранее вычисленного синдрома с требуемым столбцом проверочной матрицы, местоположение которого определяется блоком 8сравнения комбинаций (предыдущей ипоследующей ) генератора 3 испытательных сигналов.Устройство работает следующим образом.Кодовая комбинация поступает в регистр 1 и вычислитель 5 синдромов,Работа буферного регистра 1 и блока 2счета стираний синхроцизируется импульсами с тактового входа 11 устройства, В исходном состоянии блок 2 обнулен. Одцонрсмецно с выдачей очередного символа кодовой комбинации наблок 2 поступает с входа 1 О стиранийустройства сигнал стирания векторстираний), содержащий единицу, еслив отношении этого символа в демодуляторе це показан) ие принято определенного решения. С блока 2 в блок 6поступает сигнал, соответствующийномеру (по порядку поступления) соот.ветствующего стирания, а ца распределитель 4 - номер разряда, в которомпроизошло стирание. По этому сигналу и соответствующему сигналу с рас3498 б 5 163пределителя 4 в блоке 6 записывается номер стертого разряда кодовойкомбинации, Кроме того, блок 6 подключает к входам разрядов регистра 1, соответствующим стертым символам, выходы разрядов генератора 3,Причем к одному разряду регистра 1подключается выход одного разрядагенератора 3. После записи в регистр1 всей принятой кодовой комбинацииначинает работать генератор 3, который запускает.я ио входу 28 сигна 11 11лом Пуск , формируемым на второмвыходе 20 блока 2, этим же сигналомзапускается ггормирователь 38 импульсов сдвига, входящигг в состав вьгислитепя 5 синдромов (ггггг.г),Таким образом, вместо стертых символов в регистр 1 записываются испытательныекомбинации,Первая испыт;гтепьная комбинацияимеет вид 000. 0 на поступает с генератора 3 в блок 8 сравнения комбинаций, регистр которого перед началом работы был обнулен, а также записывается в нужные разряды регистра 1. По (с 1-1)-разрядному сигналусравнения вида 000 с выходов блока 8 вычислитель 5 вычисляет г-разрядный синдром записанной в регистре 1 комбинации, Полученный первыйсиндром поступает в блок 7 кор; екциисиндрома, где запоминается, а затембез изменений проходит гга г-входы 29генератора 3, Если синдром окажетсянулевым, то генератор 3 останавливается и вырабатывается сигнал об окончании декодирования, Если синдром неравен нулю во всех разрядах, то навыходе генератора 3 появляется новаяиспьгтательная комбинация, отличающаяся от предыдущей ровно в одном элементе (генератор 3 генерирует последовательность кода Грен). Новая испытательная комбинация формируется генератором 3 по приходу на вход 30 импусьса синхронизации иэ вычислителя 5 синдромов и поступает в блок 6замещения символов и блок 8 сравнения,в котором сравнивается с записаннойтам предыдущей комбинацией, Номерразряда с единицей, соответствующейразличающимся элементам двух соседнихкомбинаций, однозначно связан с номером столбца проверочной матрицы,хранящейся в вычислителе 5, Найденный столбец поступает в блок 7 коррекции, где складывается с предыдущим 5 10 15 20 25 30 35 40 45 50 55 сиггг 1 ромом, Внсгвь полученный синдромзапоминается н блоке 7, а затем поступает в генератор 3. При этом вычислитель 5 больше для данной принятойкомбинации синдром не вычисляет,Синдром вычисляется путем перемножения принятого вектора (транспонироваггггого) иа проверочную матрицудля первой (нулевой) пробной комбинации, Проверочная матрица кода записана в блоке 32 постоянной памяти. Посигналу запуска с входа 41, которымодновременно обнуляются счетчик 48формирователя 36 адреса и регистр 35,эагг 1 скается формирователь 38 импульсов сдвига, управляющий регистром 37сдвига, в котором записана кодоваякомбинация. Формирователь 36 адреса,тактируемый гггорьгиров 1 асгеггем 38 импульсов сдвиг, ьыбирает иэ блока 32требуемьгй столсс ц г,сигнал нулевогоразряда кодовой комбинации регистра 37 сдвига разрешает поступлениекода адреса стоэбца проверочной матрицы иэ счетчика 48 через мультиплексор 45 в блок 32), который поразрядно суммируется по модулю два в блоке34 с содержимым 1 ег . тра 35, результат остается в регисгэе 35. По сигналу Чтение" реэуггьга умножения вектора гга матрицу выг,ается по выходам43 на блок 7 коррекции синдрома. Дпяпоследующих пробных комбинаций из блока 32 извлекается с помощью формирователя 36 адреса требуемый стобецбез вычисления очередного синдрома(ненулевой код от блока 8 с помощьюэлемента ПИ 46 переключает мультиплексор 45 и поступает в блок 32 какадрес столбца), а затем вектор-столбец поступает через демультиплексор33 сразу в регистр 35, Формирователь39 импульсов синхронизации выдает навыход 44 счетные импульсы для генератора 3 испытательных сигналов, приэтом учитывается задержка для вычиспения первого синдрома, Счетныеимпульсы генерируются на основе сигнала сггормирователя 38 импульсов сдвиг, сигнал разрешения на работу которого выдает блок 2 счета стираний насвоем втором выходе 20 по окончаниипоступления входной кодовой комбинации,В известном устройстве вычислитель5 осуществляет .ычисление синдромагля каждой комбинации ошибок, а впредлагаемом устройстве если каждая10 1000011101100100 1 0 0 О О 1 1 1 0 1 1 О 0С= 0010011010 111000010011010111100001110110010120 О О О О О О О О О О О 0 О 0 Э 0 1 О О О О 0 О О 00 0 О О 0 О О О 1 О 0 О О О О О О 1 О О 0 О О О О О 1 О О О 0 О О О ОО О 0 О О 0 О 0 1 О О О О О О О О 1 В известном устройстве для вычисления одного синдрома при умноже нии принятой кодовой комбинации наматрицу Н требуется и-г операций сложения, а всего для исправления Й ошибок потребуется Ы=(и г ) Ч опеираций сложения,40 В предлагаемом устройстве при модификации синдрома требуется г операций сложения, а всего их потребует- ся=(и ) +(Ч-) г,45 Выигрыш составляетЧи ийа . Раа,1 11 Ь-г(и)+2Лля рассмотренного примера с короткой длиной кодового слова (и=15)1=10,4 раза,При вычислении синдрома путем деления многочленов выигрыш по количеству тактов составляет по аналогии55 Я и 2"г и+(гЬ -)При этом считается, что сложениев блоке 7 происходит эа один такт. Б аа 1 О 11 О О О 1Из рассмотренного примера видно,что результаты вычислений предлагаемого и извесного устройств аналогичны, причем Ь обоих случаях иэ исправления Йошибок в принятой кодовой комбинации требуется лроанали 2" Ь зовать в среднем Ч= -- =" пробных2комбинаций,новая пробная комбинация ошибок отличается от предыдущей только в одномразряде, то новый синдром равен старый синдром;столбец проверочной матрицы ( номер элемента кодовой последовательности,в котором она отличаетсяот предыдущем),Проверочная матрица кода 10101101 1 1 1 О 1 1101000 0110100 100 100 1110000 0111000 0011100 1011000101100 Пусть кодовое слово с ошибками имеет видЬ,= О О О О О О0О О О ОЕго синдром Я,=Н Ь10101000011,Изменив в кодовом слове один элемент на противоположный, например первый, получаем другое слово о 1О О 0 0 1 0 1 О О О О 1 1.Его синдромтБ=Н Ь= 1 ОО О О 1.Или иэ старого синдрома получаем новый сложением его с первым столбцом проверочной матрицыО 1 О0 О О О 11 1 1 О 1 1 О 0 1 О ля иллюстрации данного свойства возьмем, например, систематическийкод с параметрами и=15, 1=5, г=10,С 1=7 в 1-шах 6 эгде и - длина кодового слова,,1 ля рассмотренного примера Я ==10,4 рдэд. формула изобретесич 1, Устройство для исправления стираний, содержащее буферный регистр, информационный вход и последовательный выход которого являются соответстО вецно информационным входом и выходом устройства, блок счета стирал, управляющий вход котсрого я сяе ся входом стираний устройства, рдспредепитель импульсов, генератор цспытательных сигналов, первые выходы блока счета стираний, выходы распределителя импульсов и генератора испытательных сигналов подключессы соответственно к первым - третьим входам блоО ка заменения символов, выходы которого соединены с установочными входами буФерного регистра, параллельные выходы которого подключены к первым входам вычисления синдромов, о т л и - 25 ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены блок коррекции синдрома и блок сравнения комбинаций, информационные входы которого подключены 3 О к выходам генератора испытательных сигналов, тактовые входы буфегцсосо регистра и блока счета стирании объединены и являются тактовым входам устройства, второй выход блока счета35 стираний подключен к перо су входу генератора испытательных сигналов ивторому входу вычислителя сццдромон,импульсов,2. Устройство по и, 1, о т л ич а ю щ е е с я тем, что блок счета стираний содержит первый и второй двоичные счетчики, дешифратор и ключевой элемент, управляющий вход которого объединен с входом первого двоичного счетчика и является управляющим .входом блока, вход второго двоичного счетчика является тактовым входом блока, выходы второго двоично 50 55 первые выходы которого соединены черезблок коррекции синдрома с вторыми 4 Овходами генератора испытательных сигналов, выходы блока сравнения комбинаций подключены к третьим входамвычислителя синдромов, второй выходкоторого соединен с третьим входом 45генератора испытательных сигналов,третьи выходы блока счета стиранийподключены к входам распределителя го гч тчика саединецы е хо, ц ленц фрдтора и ицсармапианцыси ц:;с;сцключевого с.мента, выходы первого двоичногс счетчика, выход деппсФрдтора и выходы ключевого элемента явля"ются соответственно первыми, вторым и третьими вьсходами блока3, Устройство по и, 1, а т цч а ю ие с я тем, чта гецер;стор испытательных сигналв садержигоичцый счетчик, э:семецты ИИ, элемент И, "не.ент 111, и эссмегсты ИСКГ 110 ЧАОЩЕ. ИЛИ, первый хоц пс рссого элемента 1 П 11, входы с,ро о з;семецта ИИ ц п:1 ый вход эле.с ц -д 11 яв.сяютсн с оотве гствецно перы с, цгорымц ц третьим входами генератора, снхоц торого лемецтд 1 с 1 И цепс средствегпсо и через элемецг 11 Е ;содкчючец к торым входам сооте гс гвеццо элементас цераго элемента И.П 1, выодь кото:; соединены соотвс тстнецца со счсссщс ходам и Входом сброса дваичцс)го счс.тсикапервый выход которого поключен к пераму входу г:ервого .с мента ИС 1(Ю- сАЯ.1: ИГИ ц яцссяется первым выходм генератора, 1-и г.:о с1=. с 1- ., с - кодовое расстаяни 1;ецчц го счетчика соединен с "ервым входом .-го и вторни входом с,з.-1)-га э:тементов ИС 1 сЧЮЧАЯЯЕЕ Иг 1 И, сс 1-1)-й выход двоичного счетчика подключен к второму входу (Й.)-го элементд ИСК.Г,1- ЧАИГЕЕ 1 ИИ, выход -го элементд 11 СКЛЮсЛЮТЕЕ 1 ЛИ является 1.-м выходомгенератора,с.строЙство па и, 1, а т л ч а ю щ е е с я тем, что вычислитель синдромов содержит блок постоянной памяти, демуль.иплексор, блок сумматоров по модулю двд, буферный регис.тр, Формирователь адреса, формирователь импульсов сдвига, формирователь импульсов синхрониздцсги и регистр сдвига, информационные входы которого являются первыми входами вычислителя, вход формирователя импульсов сдвига объединен с вхс,ами сброса буферного регистрд и Формирователя адреса и является вторым входом вычислителя, информационные входы формирователя адреса являются ,третьими входами вычислителя, первый выход формирователя импульсов сдвига подключен к тактовому входу формирователя адреса и регистра сдвигй, выход которого соединен с управляющим входом Формирователя адреса, 12первые выходы которого подключены к входам блока постоянной памяти, выходы которого соединены с информационными входами демультиплексора, второй вы 5 ход формирователя адреса подключен к управляющему входу демультиплексора, первые и вторые выходы которого соединены соответственно первыми входами блока сумматоров по модулю два и инормационными входами буферного регистра, выходы которого подключены к вторым входам блока сумматоров по модулю два и являются первыми выходами вычислителя, выходы блока сумматоров по модулю два соединены с установочными входами буферного регистра, второй выход формирователя импульсов сдвига подключен к входу формирователя импульсов синхронизации, первый выход которого соединен с входом разрешения чтения буферного регистра, второй выход формирователя импульсов синхронизации является вторым выходом вычислителя, 25 5, Устройство по п, 4, о т л ич а ю щ е е с я тем, что формирователь адреса содержит двоичный счетчик;ключевой элемент, элемент ИЛИ и мультиплексор, первые информационные входыкоторого и входы элемента ИЛИ соответственно объединены и являются информационными входами формирователя, управляющий вход ключевого элемента, счетный вход и вход сброса двоичного счетчика являются соответственно управляющим входом, тактовым входом и входомсброса формирователя, выходы двоичного счетчика соединены с информационными входами ключевого элемента, выходы которого подключены к вторым информационным входам мультиплексора,выходы которого являются первыми выходами.формирователя, выход элементаИЛИ соединен с управляющим входоммультиплексора и является вторым выходом формирователя,О. Лаз арен едактор Н,7. о.О НЫ дписное Заказ 62 ВБЖПИ Г дарственног 113035остави ехред Д ираж 4 комитета по изо Москва, Ж, Р енинскии Корректо тениям и открытиямская наб., д. 4/5 ри ГКНТ СС