Устройство для исправления ошибок Советский патент 1987 года по МПК H03M13/51 

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

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

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

Устройство для исправления ошибок содержит приемный регистр I, блок 2 суммирования, блок 3 деления, блок 4 декодирования, первый, второй и третий буферные регистры 5-7, первый и

to

i5

по модулю неприводимог о полинома степени П| на П|-разрядную псевдослучайную последовательность и сложения по модулю два результата у -1ножения с дру гой п,-разрядной псевдослучайной последовательностью. Послед.С ;5.::тельность полученную после псевдостохастического преобразования длины а N,- , разделяют на N , отрезков длины Ti. каждый и производят кодирование второй ступени, в соответствии с которым одноименные символь полученных отрез™ ков складыв;ж т по модулю два, в ре-, зультате чего получают проверочный от резок длины 7. двоичгшх символов (фиг. 3), которые добавляют к ичным символам. В результате общая длина передаваемой кодовой последовательности делается равной п N

второй генераторы 8, 9 псевдослучай- (N + 1) Ti двоичных символов, а об- ной последовательности, коммута- число проверочных символов равным тор 10 и блок 11 пробного исправле- i-mrf ошибок. На фиг. 1 также обозначены информационный вход 2, вход 13 работает следующим образом. цикловой синхронизации, первый и вто- Принятая п-разрядная кодовая после рой выходы 14 и 15,

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

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

Коммутатор 10 служит для поочеред

п л Ч псевдослучайных последовательностей кого прдключения генераторов о и 9 к - - f .

буферному регистру 6,

Блок 11 исправления ошибок (фиг.2) включает в себя кольцевой сдвигающий регистр 16, генератор 17 тактовых имг г ,, + А .

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

довательность со входа i 2 записывается в первый буферный регистр 5, а п, К + г, ее символов, подвергнутых на передающем конце псевдостохас- 30 тическому преобразованию,, заносятся в приемный регистр 1, Одновременно по сигналу цикловой синхронизации со входа 1 3 генераторы 8 и 9 форг-шруют очередные значения двух отрезков

пульсовJ элементы 18 НЕ, первые, вторые и третий элементы 19, 20, 21 И сумматоры 22 по модулю два

Генетзатор 17 тактовых импульсов вьтолнен на генераторе ртпульсов и распределителе импульсов.

дошны п, к + г, двоичных символов каждый, которые через коммутатор 10 заносятся и запоминаются в регистрах 6 и 7. По тому же сигналу со вхо- 40 да 13 в блоке 11 пробного исправления ошибок первые элементов кольцевого сдвигающего регистра 6 устанавливаются в положение 1 а остальные

в положение

45

считывается преобразованный на передаче отрезок кодоПо Завершению приема п-разрядной Кодовая последовательность, посту-кодовой последовательности с прием- пающая на вход 12 устройства, форми-ного регистра руется следующим образом. К К двоичным информационным символам, по,цл еж а-50 последовательности длины п щим передаче, добавляют TJ двоичных К + г, в блок 2 cyм v иpoвaпия, где проверочных символов, полученных впроизводится ei o сложение по модулю соответствии с используемым (п,,К)-два с первым п -разрядным отрезком кодом, при этом выполняется равенствопсевдослучайной последовательности, f N,, -л , где N, и - целые числа. 55 находящимся в регистре 6, а после

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

этого - давление по модулю неприводимого полинома степени п результата суммирования в блоке 3 на значение п -разрядногч отрезка псеЕдослу-

5

по модулю неприводимог о полинома степени П| на П|-разрядную псевдослучайную последовательность и сложения по модулю два результата у -1ножения с другой п,-разрядной псевдослучайной последовательностью. Послед.С ;5.::тельность , полученную после псевдостохастического преобразования длины а N,- , разделяют на N , отрезков длины Ti. каждый и производят кодирование второй ступени, в соответствии с которым одноименные символь полученных отрез™ ков складыв;ж т по модулю два, в ре-, зультате чего получают проверочный отрезок длины 7. двоичгшх символов (фиг. 3), которые добавляют к ичным символам. В результате общая длина передаваемой кодовой последовательности делается равной п N

(N + 1) Ti двоичных символов, а об- число проверочных символов равным работает следующим образом. Принятая п-разрядная кодовая после

г г ,, + А .

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

(N + 1) Ti двоичных символов, а об- число проверочных символов равным работает следующим образом. Принятая п-разрядная кодовая после

довательность со входа i 2 записывается в первый буферный регистр 5, а п, К + г, ее символов, подвергнутых на передающем конце псевдостохас- тическому преобразованию,, заносятся в приемный регистр 1, Одновременно по сигналу цикловой синхронизации со входа 1 3 генераторы 8 и 9 форг-шруют очередные значения двух отрезков

псевдослучайных последовательностей f .

дошны п, к + г, двоичных символов каждый, которые через коммутатор 10 заносятся и запоминаются в регистрах 6 и 7. По тому же сигналу со вхо- да 13 в блоке 11 пробного исправления ошибок первые элементов кольцевого сдвигающего регистра 6 устанавливаются в положение 1 а остальные

в положение

считывается преобразованный на передаче отрезок кодоПо Завершению приема п-разрядной кодовой последовательности с прием- ного регистра последовательности длины п К + г, в блок 2 cyм v иpoвaпия, где производится ei o сложение по модулю два с первым п -разрядным отрезком псевдослучайной последовательности, находящимся в регистре 6, а после

этого - давление по модулю неприводимого полинома степени п результата суммирования в блоке 3 на значение п -разрядногч отрезка псеЕдослу-

чайной последовательности, хранящимся в регистре 7. Результат деления в виде отрезка длины К + Г( двоичных символов поступает в блок А декоди- роваш1я, где в соответствии с введенными при кодировании г, проверочными символами проиаводится проверка этйго отрезка на наличие ошибок.

При необнаружении ошибок К-разряд ное сообщение поступает на первый выход К устройства.

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

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

элементы 19 - 191 Ив сумматоры 2

I л по модулю два, где осуществляется

суммирование одноименных символов N отрезков длины Л двоичнУх символов каждый (сложение по столбцам), и в приемный регистр I с первых выходов блока 1 пробного исправления ошибок записываются п, двоичных символов. При этом считывание через элемент 19 разрешается с помощью элементов 18 НЕ для тех разрядов кодовой последова- тельности, которые соответствуют элементам кольцевого сдвигающего регистра 16, находящимся в положении О (в начале работы этому положению со- ответствуют все элементы кольцевого сдвигающего регистра 16, кроме пер- Bbix элементов, которые были ранее установлены в положение 1). В результате в приемном регистре будет записана п-разрядная последовательность, ; первых символов которой стерты, а в сумматорах 22 по модулю два - результат суммирова шя одно- именньпх нестертых символов, который записывается в приемный регистр 1 на место стертых символов через элементы 20 И с помощью второй серии из Nf импульсов (N(+,...,2N-1) генератора 17 тактовых импульсов. Следующим импульсом с генератора 17 осуществля ется сдвиг содержимого кольцевого сдвигающего регистра 16 на один разряд вправо, а последним импульсом осуществляют с помощью третьего эле

o

.5

0

5

0 5

0

5

0

мента 21 И проверку наличия всех первых }, элементов кольцевох о сдвигающего регистра 6 в положении 1, что является признаком окончания процесса декодирования.

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

В случае обнаружения ошибок во всех предусмотренных I циклах декодирования блок 11 пробного исправления ошибок вырабатывает сигнал по второму выходу (именно в этот момент первые , элементов кольцевого сдвигающего регистра 1 б будут находиться в состоянии 1), который является вторым выходом 1J устройства, о наличии неисправляемой комбинации ошибок. Значение I - максимально необходимое число циклов декодирования при заданных значениях п, г, - определяется минимальным числом комбинаций стираемых символов, включающих в себя остальные .комбинации стираний, которые могут быть исправлены используемым кодом при условии отсутствия ошибок в остальных символах кодовой последовательности.

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

Таким образом, устройство для исправления ошибок за счет введения в передаваемую информацию г г, + /

проверочных символов позволяет

г,-

РОЯТНОСТЬЮ Pj г, 1- П (2

-

исправить в п-разрядной последовательности любые одиночные пакеты ошибок длины b , (при общем числе исправляемых конфигураций ошибок М 2 п) и, кроме того, обеспечивает гарантированное значение вероятности необнаруживаемой ошибки (в каналах с произвольным распределением ошибок) 5 определяемое неравенством ,г . г,еоз,п ..1

1287296 6

правления ошибок объединен с вторым выходом блока декодирования, третий выход которого соединен с управляю- входом блока пробного исправления ошибок.

2, Устройство по п. 1, о т л и - чающееся тем, что блок пробного исправления ошибок выполнен на JO первых элементах И, объединеннл гх в N групп по / элементов в каждой (N п - число символов входного кодового слова, вторых элементах И, объединенных в N групп по fl элемен- Устройство для исправления оши- /5 тов в каждой (,Ni N - 1), третьем

По (2

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

I

бок, содержащее генераторы псевдослучайной последовательности, блок суммирования, выходы которого соединены с соответствующими первыми входами блока деления, выходы которого подключены к соотвеч ствующим входам блока декодирования, первый и второй выходы которого являются соответствующими выходами устройства, отличающееся тем, что, с целью повышения достоверности информации, в него введены буферные регистры,коммутатор, блок пробного исправления ошибок и приемный регистр, первый вход которого объединен с входом первого буферного регистра и является информационным входом устройства, выходы приемного регистра подключены к соответствующим первым входам блока

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

выход которого подключен к входу ВТО- 45 подключены соответственно к входу

рого буферного регистра, последовательный выход которого соединен с входом третьего буферного регистра, параллельные выходы второго и третьего буферных регистров подключены к соответствующим вторым входам соответственно блока суммирования и блок делё ния, выход первого буферного регистра соединен с информационным /входом блока пробного исправления ойшбок, информационные выходы которого подключены к соответствую1цим вторым входам приемного регистра, контрольный выход блока пробного исэлементе И, элементах НЕ, объединенных в N групп по А элементов в каждой, сумматорах по модулю два, генераторе тактовых импульсов и кольцевом сдви1 ающем регистре, выходы разрядов которого, объединенные в N групп по 71 выходов в каждой, соединены через соответствующие элементы НЕ с первыми входами соответствующих первых элементов И и непосредственно - с первыми входами соответствующих вторых элементов И, выход i-ro первого элемента И j-й группы (i е C l , J6 ) подключен к

. входу i-ro cyMt-iaTopa по модулю два, выход которого соединен с вто- рь:ми входами i-x вторьсх элементов И всех групп, выходы разрядов первой группь; кольцевого сдвигающего регистДР генератора тактовых импульсов с первого по N-й и с (N+l)-ro по - (2К-1)-й соединены соответственно с 40 вторыми входами первых элементов И соответствующих групп и с третьими входами вторых элементов И соответствующих групп, (2Ы)-й и (2N+l)-й выходы генератора тактовых импульсов

сдвига кольцевого сдвигающего регистра и второму входу третье1 о элемента И, выход которого является контрольным выходом блока пробного исп50 равления ошибок, выходы nj первых элементов И (п ) объединены с выходами соответствующих вторых элементов И и являются информационными выходами блока пробного исправления

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

ляются соответственно управляющим и

исправления ошибок.

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

1 J| 1 111

i /5/ i- /ff i- I...4 /tf;, L.

...

«

Фиг. 5

« в в