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

 

Изобретение относится к вычислительной технике и технике связи. Его использование в ппаратурр передачи данных позволяет повысить быстродействие . Устройство содержит буферный иегистр 1, блок 2 счета стираний, генератор 3 испытательных сигналов , распределитель 4 импульсов, вычислитель 5 синдромпя и блок 6 замещения символов, Благод1,эя введению блока 7 коррекции синдрома и блока 8 сравнения комбинаты в устройстве вместо вычисления синдрома для каждой (кроме первой)комбинации ошибок осуществляется сложение по модулю два ранее вычисленного синдрома с требуемым столбцом проверочной матрицы . 4 з.п. 4-лы, 4 ил Ј

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (5))5 Н 03 М 13/0?

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И OTHPbtTHRM

ПРИ ГКНТ СССР (2I) 4661614/24 (22) 13.03.89 (46) 07.03,91 Бюл. II 9 (71) Минский радиотехнический институт (72) O.Ä. Карякин, В.А. Вишневский, В.В. Киреев и А.С. Кузьмук (53) 671,394.14:681.32(088.8) (56) Берлекэмп Э. Алгебраическая теория кодирования. — М.: Мир, 1971, с. 145-147.

Блейхут Р, Теория и практика кодов, контролирующих ошибки, — 11.:

Мир, 1986, с. 165-179.

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

9 786030, кл. Н 03 М 13/02, 1978. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ СТИРАНИЙ.SU» 1633498 А1

{5/) Изобретение относится к вычислительной технике и технике связи. Его использование в аппаратуре передачи данных позволяет повысить быстродействие. Ус ройство содержит буферный регистр 1, блок 2 счета стираний, генератор 3 испытательных сигналов, распределитель 4 импульсов, вычислитель 5 синдро.. в и блок 6 замещения символов. Благодаря введению блока 7 коррекции синдр ма и блока

8 сравнения комбинаций в устройстве вместо ьь числения синдрома для каждой (кроме первой)комбинации ошибок осуществляется сложение по модулю два ранее вычисленного синдрома с требуемым столбцом проверочной матрицы. 4 з.и. й-лы, 4 ил.

1633498

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

1

Вычислитель 5 синдромов содержит лиг.4) блок 32 постоянной памяти, демультиплексор 33, блок 34 сумматоров по модулю два, буферный регистр

35, формирователь 36 адреса, регистр

37 сдвига, формирователь 38.импульсов

55 сдвига и формирователь 39 импульсов синхронизации. На *иг.4 обозначены первый 40, второй 41 и третьи 4? передачи данных.

Цель изобретения — повышение быстродействия устройства, На фиг.l изображена блок-схема устройства; на фиг.2-4 — блок счета стираний, генератор испытательных сигналов и вычислитель синдромов. соответственно..

Устройство для исправления стираний содержит буферный регистр I, блок 2 счета стираний, генератор 3 испытательных сигналов, распределитель 4 импульсов, вычислитель 5 синдромов, блок 6 замещения символов, блок 7 коррекции синдрома и блок 8 сравнения кобинаций, На фиг, 1 обо- 20 значены информационный вход 9, вход

10 стираний, тактовый вход l l u выход 12 устройства.

Блок 2 счета стираний выполнен (Фиг.2) на первом 13 и втором 14 25 двоичных счетчиках, дешифроторе 15 и ключевом элементе 16, На фиг.2 обозначены управляющий вход 17, так1товый вход 18, первые 19 и второй 20 и третьи 21 выходы блока 2, 30

Генератор 3 испытательных сигналов включает в себя фиг,3) первый 22 и второй 23 элементы AJIH, элемент

И 24, элемент НЕ 25, двоичный счетчик 26 и элементы ИСКЛЧЧАЩЕЕ ИЛИ 27.

На Лиг.3 обозначены первый 28, вторые 29 и третий 30 входы и выходы 31 генератора 3, Генератор 3 представляет собой генератор кода Грея, где каждая следующая выходная комбинация 40 отличается от предыдущей ровно в одном элементе. На фиг.3 обозначено кодовое расстояние d используемого (принимаемого) кода.

Распределитель 4 импульсов пред 45 ставляет собой фактически демультиплексор, устанавливающий уровень логической единицы на выходе в соответствии с входным кодом, входы, первые 43 и второй 44 выходы вычислителя 5.

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

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

Формирователь 36 адреса выполнен (фиг.4 ) на мультиплексоре 45, элементе ИЛИ 46, ключевом элементе 47 и двоичном счетчике 48, Сущность изобретения заключается в отказе от громоздкого вычисления синдрома для каждой, кроме первой, комбинации ошибок, заключающегося в делении многочлена принятого кодового слова на проверочный полином или в умножении era на проверочную матрицу, Вместо этой процедуры в блоке 7 коррекции синдрома используется операция сложения по модулю два ранее вычисленного синдрома с требуемым столбцом проверочной матрицы, местоположение которого определяется блоком 8 сравнения комбинаций (предыдущей и последуюшей ) генератора 3 испытательных сигналов.

Устройство работает следующим образом.

Кодовая комбинация поступает в регистр 1 и вычислитель 5 синдромов, Работа буферного регистра 1 и блока 2 счета стираний синхронизируется импульсами с тактового входа 11 устройства. В исходном состоянии блок 2 обнулен. Одновременно с выдачей очередного символа кодовой комбинации на блок 2 поступает с входа 10 стираний

/ устройства сигнал стирания 1 вектор стираний), содержащий единицу, если в отношении этого символа в демодуляторе (не показан) ие принято определенного решения. С блока 2 в блок 6 поступает сигнал, соответствующий номеру (по порядку поступления) соответствующего стирания, а на распределитель 4 — номер разряда, в котором произошло стирание. По этому сигналу и соответствующему сигналу с рас3498 6

5 163 пределителя 4 в блоке 6 записывается номер стертого разряда кодовой комбинации. Кроме того, блок 6 подключает к входам разрядов регистра 1, соответствующим стертым символам, выходы разрядов генератора 3.

Причем к одному разряду регистра 1 подключается выход одного разряда генератора 3. После записи в региг.тр

1 всей принятой кодовой комбинации начинает работать генератор 3, который запускается ио входу 28 сигнаll 11 лом Пуск, формируемым на втором выходе 20 блока 2 этим же сигналом запускается Формирователь 38 импульсов сдвига, входящий в состав вьг ислитепя 5 синдромов (Ъ.сг. с},Таким образом, вместо стертых символов в регистр 1 записываются испытательные комбинации, Первая испытательная комбинация имеет вид 00...0. 0на поступает с генератора 3 в блок 8 сравнения комбинаций, регистр которого перед началом работы был обнулен, а также записывается в нужные разряды регистра 1. По (d-1)-разрядному сигналу сравнения вида 00...0 с выходов бло.ка 8 вычислитель 5 вычисляет I-ðàçрядный синдром записанной в регистре 1 комбинации, Полученный первый синдром поступает в блок 7 корс акции синдрома, где запоминается, а затем без изменений проходит иа r-входы 29 генератора 3, Если синдром окажется нулевым, то генератор 3 останавливается и вырабатывается сигнал об окончании декодирования. Если синдром не равен нулю во всех разрядах, то на выходе генератора 3 появляется новая испштательная комбинация, отличающаяся от предыдущей ровно в одном элементе (генератор 3 генерирует последовательность кода Грен). Новая испытательная комбинация формируется генератором 3 по приходу на вход 30 импусьса синхронизации иэ вычислителя 5 синдромов и поступает в блок 6 замещения символов и блок 8 сравнения, в котором сравнивается с записанной там предыдущей комбинацией. Номер разряда с единицей, соответствующей различающимся элементам двух соседних комбинаций, однозначно связан с номером столбца проверочной матрицы, хранящейся в вычислителе 5, Найденный столбец поступает в блок 7 коррекции, где складывается с предыдущим

55 синдромом, Внс>вь полученный синдром запоминается н блоке 7, а затем поступает в генератор 3. При этом вычислитель 5 больше для данной принятой комбинации синдром не вычисляет, Синдром вычисляется путем перемножения принятого вектора (транспонированиого) на проверочную матрицу для первой (нулевой) пробной комбинации. Проверочная матрица кода записана в блоке 32 постоянной памяти. По с.игналу запуска с входа 41, которым одиовременн:. обнуляются счетчик 48 формирователя 36 адреса и регистр 35, запускается формирователь 38 импульсов сдвига, управляющий ре|истром 37 сдвига, в котором записана кодовая комбинация. Формирователь 36 адреса, тактируемый аорлировасгелем 38 импульсов сдвига, ьыбирает иэ блока 32 требуем |й столсс ц (сигнал нулевого разряда кодоьой комбинации регистра 37 сдвига разрешает поступление кода адреса стоэбиа проверочной матрицы иэ счетчика 48 через мультиплексор 45 в блок 32), который поразрядно суммируется по модулю два в блоке

34 с содержимым рег .тра 3-, результат остается в регисс,le 35. По сигналу Чтение" реэупьз а, умно кения вектора иа матрицу вьп,ается по выходам

43 на блок 7 коррекции синдрома. Дпя пîcледующих пробных комбинаций из блока 32 извлекается с помощью формирователя 36 адреса требуемый стобец без вычисления очередного синдрома (ненулевой код от блока 8 с помощью элемента 1ПИ 46 переключает мультиплексор 45 и поступает в блок 32 как адрес столбца), а затем вектор-столбец поступает через демультиплексор

33 сразу в регистр 35. Формирователь

39 импульсов синхронизации выдает на выход 44 счетные импульсы для генератора 3 испытательных сигналов, при этом учитывается задержка для вычиспения первого синдрома. Счетные импульсы генерируются на основе сигнала формирователя 38 импульсов сдвиг», сигнал разрешения на работу которого выдает блок 2 счета стираний на своем втором выходе 20 по окончании поступления входной кодовой комбинации, В известном устройстве вычислитель

5 осуществляет " û÷èñëåíèå синдрома для каждой комбинации ошибок, а в предлагаемом устройстве если каждая

1633498

3gj °

S S

1 ! где S; и

1О

r

G= 001 001 10 I 0 I 1 1 1 0

000100 I 101011 I 1

000011101100101

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

1 0 0 О 0 0 0 0

0 1 0 0 0 О 0 О

О 0 1 0 0 О 0 0

0 О 0 1 0 0 0 0

0 0 0 О i 0 0 0

0 0 0 0 0 1 О 0

0 0 0 0 0 0 1 0

0 0 О 0 0 0 0 1

В известном устройстве для вычисления одного синдрома при умножении принятой кодовой комбинации на матрицу Н требуется n-r операций сложения, а всего для исправления d-I ошибок потребуется W =(n г ) Ч опе11 раций сложения, 40 Б предлагаемом устройстве при модификации синдрома требуется r операций сложения, а всего их потребуется

W =(n r) +(V-I)r, 45

Выигрыш составляет

W«nd ,! z

W = = раз.

W «1-2 (n- l )+2

Для рассмотренного примера с короткой длиной кодового слова (n=l5)

W =I0,4 раза, При вычислении синдрома путем деления многочленов выигрыш по количеству тактов составляет по аналогии

55 Wz! и 2"

"("- )

При этом считается, что сложение в блоке 7 происходит эа один такт.

S -= 1 О 1 1 1 I 0 О О I

Из рассмотренного примера видно, что результаты вычислений предлагаемого и извес ного устройств аналогичны, причем Ь обоих случаях иэ исправления Й-1 ошибок в принятой кодовой комбинации требуется лроанали2",,Ь-< зовать в среднем V- =— — --" пробных

2 комбинаций. новая пробная комбинация ошибок отличается от предыдущей только в одном разряде, то новый синдром равен старый синдром; столбец проверочной матрицы (J -- номер элемента кодовой последовательности, в котором она отличается от предыдущей), Проверочная матрица кода

1010 l I 0

I 1 I I 1 О 1

1 О 1 О О О

0 1 1 0 1 О 0

0 1 1 I О 0 О

О О 1 1 1 0 О

1 0 1 I О О 0

1 0 1 1 О 0

Пусть кодовое слово с ошибками имеет вид

b = О 0 О 0 О О 1 0 1 О О 0 0 I 1.

Fro синдром S =H.Ь

О I О 1 О О О О 1 I, Изменив в кодовом слове один элемент на противоположный, например первый, получаем другое слово

b l О О О 0 I I I О 0 О 0 1 I.

Его синдром т

S =H b = 1 О 1 1 1 l О О О 1Или иэ старого синдрома получаем новый сложением его с первым столбцом проверочной матрицы

О 1 О 1 0 0 0 О I

1 1 1 О 1 I 0 0 1 0 !ля иллюстрации данного свойства возьмем, например, систематический код с параметрами n=l5, k=5, r=l0, 1-ва 6э где n — длина кодового слова, <1 — кодовое расстояние, максимальное количество лшиmax бок (исправляемых кодом), k=n-r — длина информационной части, порождающая матрица которой имеет вид

I< 33498

10. !>(я рассмотренного примера !! = .> 2

=10,4 раза. ф о р м у л а и з а б р е т е > и ч

1. YcTpottcT(»o дпя исправления стираний, содержащее буФерный регистр, инФормационный вход и поспедоватепьный выход которого являются саответст-Ip венно информационным >входом и (»ыходом устройства, бпак счета етирагп<й, управляющий вход кот<>рого я< (><ется входом стираний устройства, распредепитепь импульсов, генератор испытательных сигналов, первые выходы блока счета стираний, выходы распределителя импульсов и генератора испытательных сигнапов подключе><ы соответственно к первым — третьим входа<м 6((о-2п ка замен(ения символов, выходы которого соединены с установочными г»ходами

6УФерного регистра, параллельные выходы которого подключены к первым входам вычисления синдромов, о т л и — 25 ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены бпок коррекции синдрома и блок сравнения комбинаций, информационные входы которого подк tesettbt 3p к выходам генератора испытательных сигналов, тактовые входы буфег нагo регистра и блока счета стирани> объединены и являются тактовым входам устройства, второй выход блока счета

35 стираний подключен к пера.<у входу генератора испытательных сигналов и второму входу вычислителя синдромов, импульсов.

2. Устройство по п, 1, о т л ич а ю щ е е с я тем, что блок счета стираний содержит первый и второй двоичные счетчики, дешифратор и ключевой элемент, управляющий вход которого объединен с входом первого двоичного счетчика и является управляющим .входом блока, вход второго двоичного счетчика является тактовым входом блока, выходы второго двоично50

55 первые выходы которого соединены через блок коррекции синдрома с вторыми 4О входами генератора испытательных сигналов, выходы блока сравнения комбинаций подключены к третьим входам вычислителя синдромов, второй выход которого соединен с третьим t»õoäoì 45 генератора испытательных сигналов, третьи выходы блока счета стираний подключены к входам распределителя

ГО Гчетчика саецинеitbl Г вха-а !»<,>(е»н(фратлра и и((<(>армациан(<ыми н>« .(Ими кпючевого >.т< мс нта, t»btxA tbt первого дваичнаг<> счетчика, выход депп(Фратора и выходы ключевого элемента явпя-. ются соответственно первыми, вторым и третьими выходами блока °

3, Устройство па п, I o т н содержи г;(>»л(чиый счетч»<к, .:»еме(<ты 11!(!1, элемент !1, элем<-нт Ill: it -.» t! менты 11СК."110ЧАОЩЕ! . 1Л11, пернь и i»>» <,spot о з>пемента Il lll it п -, вши вход эпс- li ll-а 11 явпяютен с.ooTRc гствеино первы 1 вгарыми и третьим t»xo дами генератора, »» tint(r» t op»>ro пемента lt. 1И иенс средствегп<о и через эпемеиг IIF, подкчючен к >»тарым входам саот(»е гс гвеиио эпемента < первого элемента !ГП1, вы::одь(xnTO;> i:; coo;(tsиены соотвс тстненнл co cм и ВХодаМ СррОСВ ДВОИЧН<>1 О СЧ< Т <(>на > первый выхог(которого и .»ключен к пеp!»O«v t»io!ty г:ерваго -tc мента ИС!(ЧЮс!АЮ!»!!. ILI!II it ян<(яется пер(»ым вы.<ад<>м генератора, -и в.. .:»э ((1=."с,,1сl — кадагoe pace To>t ttti j;tt».-»<ч»<аt о счетчика соединен с "ервым входом

i-га и втарь(м входом (i"I) ãà эпементов ИС1<.ЧЮЧАЮЯЕЕ ИЧ11, (с1-l)-й выход двоичного счетчика подключен к второму входу (Й-7)-ro элемента ILCL«" >ЧАЮГ1ЕЕ 11Ч!1, выход i-ro элемента 1!С—

КЧЮ(ЕЕ 1ГП! являетсч i-м выходом генератора.

4, Устройство по п. 1, о т л и ч а ю н(е е с я тем, чта вычислитель синдромов содержит блок постоянной памяти, демуль .иппексор, блок сумматоров по модулю два, буферный регис.тр, Формирователь адреса, формирователь импульсов сдвига, формирователь импульсов синхронизац(ги и регистр сдвига, информационные входы которого являются первыми входами вычислителя, вход формирователя импульсов сдвига объединен с вхс .ами сброса буферного регистра и Формирователя адреса и является вторым входом вычислителя, информационные входы формирователя адреса являются .третьими входами вычислителя, первый выход формирователя импульсов сдвига подключен к тактовому входу формирователя адреса и регистра сдвига, выход которого соединен с управляющим входом Формирователя адреса, 12

1633498

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

5., Устройство по п, 4, о т л и ч а ю щ е е с я тем, что формирователь адреса содержит двоичный счетчик; ключевой элемент, элемент ИЛИ и мультиплексор, первые информационные входы которого и входы элемента ИЛИ соответственно объединены и являются информационными входами формирователя, управляющий вход ключевого элемента, счетный вход и вход сброса двоичного счетчика являются соответственно управляющим входом, тактовым входом и входом сброса формирователя, выходы двоичного счетчика соединены с информационными входами ключевого элемента, выходы которого подключены к вторым информационным входам мультиплексора, выходы которого являются первыми выходами, формирователя, выход элемента

ИЛИ соединен с управляющим входом мультиплексора и является вторым выходом формирователя, l 633498

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

Редактор Н. Лазаренко Техред Д.Олийнык Корректор М.йароши

Заказ 627 Тираж 458 Подписное

ВНИИПИ Государственного комитета по изобретениям и открьггиям при ГКНТ СССР

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

Производственно-издательский комбинг "Патент", г. Ужгород, ул. Гагарина, 101