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

 

Изобретение относится к вычислительной технике. Его использование в системах передачи цифровой информации обеспечивает повьшение достоверности принимаемой информации. Устройство для исправления ошибок содержит блок 2 суммирования, блок 3 деления, блок 4 декодирования и генераторы 8, 9 псевдослучайной, последовательности . Введение приемного регистра 1, буферных регистров 5-7, коммутатора 10 и блока II пробного исправления ошибок позволяет исправлять в п-разрядной кодовой последовательности любые одиночные пакеты ошибок длиной А с вероятностью Рцсп --vfob - - + 1, N,- п, К + г, К и Г( - количество информационных и проверочных символов исходного (п,, К)-кода; { N , X - целые числа) при общем числе исправляемых конфигураций ошибок М и, кроме того, обеспечивает гарантированное значение вероятности необнаруживаемой ошибки (в каналах с .произвольным распределением ошибок) Р (2 ° -1). 1 з.п. ф-лы, , (Л

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

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

РЕСПУБЛИК (!9) 8 0 ()!) А1 (gg 4 Н 03 И 13/02

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3853240/24-24 (22) 25.12.84 (46) 30.01.87. Бюл. ¹ 4 (72) Г.Н. Устинов (53) 621.391.15(088.8) (56) Техника средств связи. Сер. Техника проводной связи, 1977, вып. 6 (16), с. 81 — 85.

Коржик В.И., Финк Л.M. Помехоустойчивое кодирование дискретных сообщений в каналах со случайной структурой (Статистическая теория связи, вып. 4) 9 М.: "Связь", 1975, с. 195196, рис. 4.1.. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ OIIIHБОК (57) Изобретение относится к вычис— лительной технике. Его использование в системах передачи цифровой информации обеспечивает повышение до— стоверности принимаемой информации.

Устройство для исправления ошибок содержит блок 2 суммирования, блок 3 деления, блок 4 декодирования и ге,нераторы 8, 9 псевдослучайной. после— довательности. Введение приемного регистра 1, буферных регистров 5-7, коммутатора !О и блока 11 пробного исправления ошибок позволяет исправлять в п †разрядн кодовой последовательности любые одиночные пакеты ошибок длиной с вероятностью Р„ „=

+ 1, N,9 =n< =К+ r,, Киг! — количество информационных и проверочных символов исходного (n,, К)-кода; (,, с

N, ф — целые числа) при общем числе исправляемых конфигураций ошибок М =

2 и и, кроме того, обеспечивает гарантированное значение вероятности необнаруживаемой ошибки (в каналах с произвольным распределением ошибок)

Р„ (2 * — 1) . 1 з.п. ф-лы, 3 ил.

Т,- оф,9) - !

1? 87? 96 ков складывают по модулю два, в результате чего получают проверочный ат— резок длины двоичных символов (фиг ° 3) 1 Ko7 Îpûe дооавляют к пу дво ичным символам. Б рез>льт ате абшая длина передаваемой кодовой последовательности делается равной и = N 1; (N + 1) !1 двоичных символов, а об— щее число проверочных символов равным

v = r, +),.

Устройство для ис.правления ошибок работает следуюшим образом.

Принятая п — разрядная кодовая после— довательнасть са входа 12 записывается в первый буферный регистр 5, а

n = K + r, ее символов, подвергнув

-.blõ ка передающем ко,;е псевцастохас тическому преобразованию, заносятся в приемный регис.тр . Одновременна па сигналу циклавай синхронизации со входа 13 генераторы 8 и 9 формчруют очередные значения двух отрезков псевдослучайных последовательностей длины п, = К + г, двоичных символов каждый, которые через коммутатор 10 заносятся и запомикаются в регист— рах 6 и 7. По таму же сигкалу со входа !3 в блоке 11 пробного исправле— ния ошибок гервые ф элементов кольцевого сдвигающего регистра 16 ус11 танавливаются в полажекче 1 . à остальные — в положение 0

11

Кодовая последовательность, пасту— пающая на вход 12 устройства, формируется следующим образом. К К двоичным информационным символам,. подлежа — 50 шим передаче, добавляют r, двоичных проверочных символов, полученных в соответствии с чспользуемым (n,К)— кодом, при этом выполняе".ñÿ равенства

n = N, |1, где N, и % — целые числа, Над полученной последовательностью длины и двоичных символов производят о операцию псевдостохастическага преобт7азования, заключающуюся в умножении

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

Целью изобретения является повышение достоверности принимаемой информации.

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

Устройство для исправления ошибок содержит приемный регистр 1, блок 2 суммирования, блок 3 деления, блок ч декодирования, первый, второй и третий буферные регистры 5-7, первый и второй генераторы 8, 9 псевдослучайной последоватеЛьности, коммутатор 10 и блок 11 пробного исправления ошибок. На фиг. 1 также обозначены информационный вход 12, вход 13 цикловой синхронизации, первый и вто— рой выходы 14 и 15.

Блок 2 суммирования осуществляет поразрядное сложение по модулю два.

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

Коммутатор 10 служит для поочередного прдключения генераторов 8 и 9 к буферному регистру 6.

Блок 11 исправления ошибок (фиг.2) включает в себя кольцевой сдвигающий регистр 16, генератор !7 тактовых им— пульсов элементы 18 НЕ, первые, вторые и третий элементы 19, 20, 21 И, сумматоры 22 по модулю два.

Генет7атор 17 тактовых импульсов выполнен на генераторе импульсов и распределителе импульсов, па модулю ттепривоиимого паликама степени п, на n! — раз!7ядттун псевдослучай— кую последовательность и сложения па модулю два резуль —,àòà,:.nþæeíèÿ с друт ОЙ и разрядкОЙ (7 севдаслз1iтайкай JIc7 сл е д а в а т е. т ь и а с т ь ю . H 0 c Jl é., l 17::". - p JI I H o c T h 1 полученную:тосле псевдастохастическа— го преобразования длины и, = М1 разделяют на М 1 отрезков длинь1 каж-. дый и производят кодирование второй ступени, в соответствии с которым одноименные символы полученных отрезПо завершению приема и-разрядкой кодовой последовательности с приемнога регистра 1 с.итывае .ся преобразованный на передаче отрезок кодо— вой последовательности длины ng

К + r, в блок 2 суммирава ия, rqe производится ега слажеттие па модулю два с первым п,— разрядным отрезком псевдослучайной последовательности, находящимся в регистре 6, а после этага — давление па ."1алулю n=llðèâo— димаго паликома степени и, результата суммирования в б токе Э ка зкачекие тт. -разрядка- i а. рез;а псе lnocëó1287296 чайной последовательности, хранящимся в регистре 7. Результат деления в виде отрезка длины К r, двоичных символов поступает в блок 4 декоди— рования, где в соответствии с введенными при кодировании г< проверочны— ми символами производится проверка этого отрезка на наличие ошибок.

При необнаружении ошибок К-разрядное сообщение поступает на первый 10 выход К устройства, При обнаружении ошибок блок 4 декодированггя по своему третьему выхо— ду вырабатывает сигнал, который поступает в блок 11 на генератор 17 тактовых импульсов, который в свою очередь формирует серию тактовых импульсов, осуществляющих управление работой блока 11.

Первая серия из N импульсов осуществляет считывание п-разрядной коДовой последовательности, хранящейся в первом буферном регистре 5, через элементы 19 — 19 И в сумматоры 22 25

< М

I 9 по модулю два, где осуществляется суммирование одноименных символов N отрезков длины Ъ двоичных символов каждый (сложение по столбцам), и в приемный регистр 1 с первых выходов 30 блока 11 пробного исправления ошибок записываются и< двоичных символов.

При этом считывание через элемент !9 И разрешается с помощью элементов 18 НЕ для тех разрядов кодовой последова— тельности, которые соответствуют элементам кольцевого сдвигающего регистра 16, находящимся в положении "0" (в начале работы этому положению сов ответствуют все элементы кольцевого сдвигающего регистра 16, кроме перI вых ф элементов, которые были ранее установлены в положение "!") . В результате в приемном регистре 1 будет записана п-разрядная последователь- 45 ность, !< первых символов которой стерты, а в сумматорах 22 по модулю два — результат суммирования одноименных нестертых символов, который записывается в приемный регистр 1 на место стертых символов через злементы 20 И с помощью второй серии из N импульсов (N<+1,...,2N-i) генерато— ра 17 тактовых импульсов. Следующим импульсом с генератора 17 осуществля- 5 ется сдвиг содержимого кольцевого сдвигающего регистра 16 на один разряд вправо, а последним импульсом осуществляют с помощью третьего элемента 21 И проверку наличия всех noðвых g элементов кольцевого сдвигаю— щего регистра 16 в положении "!", что является признаком окончания npo— цесса декодирования.

Полученная в результате пробного стирания двоичных символов и последующего ее восстановления п,-разрядная двоичная последовательность снова подвергается обратному псевдостохастическому преобразованию в блоках 2 и 3, а оттуда поступает в блок 4 декодирования. При необнаружении ошибок К вЂ разрядн сообщение поступает получателю, а при обнаружении ошибки вновь вырабатывается сигнал по тре.— тьему выходу блока 11 обнаружения ошибок на запуск генератора !7 такто— вых импульсов, в соответствии с которым осуществляется стирание с последующим восстановлением уже дру— гой комбинации двоичных символов, определяемой элементами кольцевого сдвигающего регистра 16, находящимися в положении 1", и повторение цикла декодирования.

В случае обнаружения ошибок во всех предусмотренных Х циклах декодирования блок 11 пробного < справле— ния о<иибок вырабатывает сигнал по второму выходу (именно в этот момент первые Ъ элементов кольцевого сдвигающего регистра 16 будут находиться в состоянии 1"), который является вторым выходом 15 устройства, о наличии неисправляемой комбинации ошибок.

Значение I — максимально необходимое число цик-.ов де<одирования при заданных значениях n r< — определяется минимальным числом комбинаций стираемых символов, включающих в себя остальные комбинации стираний, которые могут быть исправлены используемым кодом при условии отсутствия ошибок в остальных символах кодовой последовательности.

Очевидно, что значение Х, которое может быть реализовано, удовлетворяет неравенство I I . В рассматрн << ваемом варианте устройства для ис— правления ошибок Х = n +1 число ис— правляемых сочетаний стираний M =

2 и. lli

Таким образом, устройство для исправления ошибок за сче- введения в передаваемую информацию г = r + Я проверочных символов позволяет с ве<,- Ео) g5 -< роятностью Р„„, = 1 — п (2 — 1) !

287296 исправить в п-разрядной последовательности любые одиночные пакеты оши бок длины Ь > (при общем числе исправляемых конфигураций ошибок М =

2 п) и, кроме того, обеспечивает

A гарантированное значение вероятностк необнаруживаемой ошибки (в каналах с произвольным распределением ошибок), определяемое неравенством

Y — M)gB 10

Рно

Формула изобретения

1. Устройство для исправления оши- 15 бок, содержащее генераторы псевдослучайной последовательности, блок суммирования„ выходы которого соединены с соответствующими первыми входами блока деления, выходы которого подключены к соответствующим входам бло— ка декодирования, первый к второй выходы которого являются соответствующими выходами устройства, о т л и— ч а ю щ е е с я тем, что, с целью 25 повышения достоверности информации, в него введены буферные регистры,коммутатор, блок пробного исправления ошибок и приемный регистр, первый вход которого объединен с входом пер- 30 вого буферного регистра и является информационным входом устройства, выходы приемного регистра подключены к соответствующим первым входам блока. суммирования, входы генераторов псевдослучайной последовательности, установочный вход блока пробного исправ— ления ошибок и управляющий вход коммутатора объединены и являются входом цикловой синхронизации устройства, выходы первого и второго генераторов псевдослучайной последовательности соединены с соответствующими информационными входами коммутатора, выход которого подключен к входу втс- г5 рого буферного регистра, последовательный выход которого соединен с входом третьего буферного регистра, параллельные выходы второго и третьего буферных регистров подключены к соответствующим вторым входам соот— ветственно блока суммирования и блока деления, выход первого буферного ре— гистра соединен с информационным ,входом блока пробного исправления ошибок, информационные выходы которого подключены к соответствующим вторым входам приемного регистра, контрольный выход блока пробного ксправления ошибок объединен с вторым выходом блока декодирования, третий выход которого соедкнен с управляю— щкм. входом блока пробного ксправле— нкя ошибок.

2. Устройство по п. 1,, о т л и ч а ю щ е е с я тем, что блок пробного ксправленкя ошибок выполнен на

»гервых элементах И, объединенных в

К групп по Я элементов в каждой (K = и — число символов входного кодового слова, вторых элементах И, объединенных в И; групп по ф элементов в каждой

N групп по 9 выходов в каждой, соединены через соответствующие элементы НЕ с первьпч» входами соответствующих первых элементов И и непосредcYâåHHî — с первыми входами соответствующих вторых элементов И, выход

i го первого элемента И )-й группы (i С 11,3 ",, j Е Pl,N)} подключен к

j ìó входу i-го сумматора по модулю цва, выход которого соединен с вторь:мк входами i-х вторых элементов И всех групп, выходы разрядов первой

» руппы кольцевого сдвигающего регистра подключены к соответствующим первым входам третьего элемента И, выходы генератора тактовых импульсов с первого по N-й и с (Ч+1)-го по (2N-1)-й соединены соответственно с вторыми входами первых элементов И соответствующих групп и с третьими входами вторых элементов И соответствующих групп, (2N} é и (2М+1)-й вы— ходы генератора тактовых импульсов подключены соответственно к входу сдвига кольцевого сцвкгающего регистра к второму входу третьего элемента И, выход которого является контрольным выходом блока пробного исправления ошибок, вь»ходы и» первых элементов И (n, = N< 9) объединены с выходамк соответствующих вторых элементов И к являются информационными выходами блока пробного исправления ош»бок, третьи входы первых элементов И объединены и являются информа— ционным входом блока пробного исправления ошибок, вход генератора такто- вых импульсов и установочный вход

129729б кольцевого сдвигающего регистра являются соответственно управляюшим и

,lстанововным вхолами олс1еа пробно1 о исправления ошиоок .

)287296

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

Редактор А. Долинич Техред Л.Сердюкова Корректор О. Луговая

Заказ 7730/59 Тираж 899 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная,4