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

 

О П и С А н И Е (1) 543!77

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 18.12.74 (21) 2088782/24 с присоединением заявки № (23) Приоритет

Опубликовано 15.01,77. Бюллетень ¹ 2

Дата опубликования описания 14.02.77 (51) М. Кл.з Н 04L 3/02

G 06F 11/08

Государственный комитет

Совета Министров СССР ло делам изобретений и открытий (53) УДК G81.326.7 (088.8) (72) Авторы изобретения

В. Н. Дынькин и В. М. Харламов

Ордена Ленина институт проблем управления (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ СООБЩЕНИЙ

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

Известны устройства для декодирования сообщений с исправлением симметрических ошибок типа замещения символов, содержащие блоки для деления входного слова на неприводимые делители порождающего многочлена, блок для выполнения операций в конечном поле и блоки для определения мест и величин ошибок (1). Однако во многих случаях применения устройств автоматики вероятности повреждения различных символов в каналах связи неодинаковы, т.е. имеют место несимметрические ошибки. В таких случаях применение указанных устройств неэффективно, ибо использование специализированных декодирующих устройств для несимметричных каналов приводит к увеличению быстродействия. Наиболее близким к изобретению техническим решением является устройство для декодирования сообщений с исправлением одиночных несимметрических ошибок, содержащее приемник аналогового сигнала, вход которого является входом устройства, а выход соединен с первым входом блока памяти, блок суммирования по модулю «два», первый вход которого соединен с выходом блока памяти, второй вход — с выходом вычислительного блока, а выход — с первым входом блока управления и выходом устройства, первый выход блока управления соединен с первым входом вычислительного блока (2). В этом устройстве избыточность, введенная в сообщение, локализуется в специально выделенных проверочных позициях. Дискретный сигнал из приемника поступает в блок памяти, где анализируются информационные позиции, которые, если они не искажены, проходят через блок суммирования по модулю

«два» сразу на выход. В случае искажения информационные символы по сигналу блока управления инвертируются в блоке суммирования по модулю «два» и направляются на выход, Зто устройство работает с кодами срав15 нительно малой мощности и способно исправлять только одиночные или две соседние несимметрические ошибки в кодовых словах фиксированной длины.

Целью изобретения является увеличение количества исправляемых ошибок путем обеспечения исправления многократных несимметрических ошибок и адаптации к кодовой длине. В описываемом устройстве это достигается тем, что в него введены блок коммутации и

25 блок q-x регистров, причем выход приемника аналогового сигнала соединен со входом блока q-x регистров, выходы которого соединены со вторыми входами вычислительного блока и блока управления, второй выход блока управ30 ления соединен со входом блока коммутации, 543177 —... + (— 1) (— о.): О, выход которого соединен со вторым входом ж блока памяти. х — (,—,) +(,—,)-

На чертеже представлена блок-схема описываемого устройства.

Оно содержит блок 1 д-х регистров, предназначенный для п ове ки словий кото ым нн и длЯ пРовеРки Условии, котоРым дол- если исправляются искажения нулевого симвожен удовлетворять кодовый вектор, вычислительный блок 2, где происходят поиски номеров искаженных символов, блок 3 коммутации, устанавливающий длину кодового вектора, Х (д Е) +(2 2) блок 4 памяти, где размещается принятое сообщение, представленное в виде двоичного —... + (— 1) (a — о) = О, вектора, блок 5 суммирования по модулю

«два», служащий для инвертирования искаженесли в канале искажаются символы «1». Решения это о уравнения представлены в виде степеней элемента а и показателем этих степеустройства стоит приемник б аналогового сигней — номера искаженных символов дискретного сигнала. Выход вычислительного блока

Вход пРиемника б аналогового сигнала ЯвлЯ- 2, воздейств я на один из входов блока 5 суммирования по модулю «два», меняет значение первым входом блока 4 памяти; первый вход соответствующего символа дискретного сигна 5 У ир ани ïî модУлю два соеди- ла поступающего на другой вход блока 5, нен с выходом блока 4 памЯти, втоРой вход — если этот символ искажен, и оставляет его без изменения, если символ правилен. На выходе блока 5 появляются истинные значения диски выходом устройства; первый выход блока 7 ретного сигнала.

УпРавлениЯ соединен с пеРвым входом вы- Переключение с одной длины кодового слова над другую происходит при поступлении и динен со вторым входом блока 4 памяти. Вход З0 на лок управления служе ной ин ормации из блока 5.

Блок 7 управления, воздействуя через блок приемника 6 аналогового сигнала, первый вы- коммутации на блок 4 памяти, устанавливаход — со втоР™ входом блока 7 УпРавлениЯ, ет необхо им ю лин кодового слова и второи выход — со вторым входом вычисли35 тельного блока 2. задержки, зависящую от количества корректируемых ошибок и быстродействия вычисли1, поступает в блок 4 памяти и одновременно

40 ходит в темпе 7 © сигнал и в блок 1 q-х регистров. В блоке 1 q-х регист- 40

Ров вычислЯютсЯ симметРические многочлены Э ктивность изоб етения обеспечивается

Эффективность изо ретения о еспечивается о. согласно уравнению возможностью исправления многократных .неи — 1 симметрических ошибок; адаптацией к кодо,,,Х

Е, Е, t а а ° .. а ГХе, Xi ° ° Хея вой длине и количеству исправляемых ошиlJ-Î, f«4« ... l бок; использованием в канале связи кодов с

a, (mod f (х)), большой мощностью.

При исправлении t несимметрических ошиЗдесь о, и а ЯвлЯютсЯ элементами полЯ 1 алУа бок для мощностей используемых двоичных

6Р(ее" ) образуемого неприводимым многочле- кодов справедлива оценка ном f (x) степени т, показателя и с коэффи- 50 циентами из поля GF(q), f(n) =0; s пробе- Л, > гает значения от 1 до t, где t — количество (n+ 1) несимметрических ошибок, которые исправляются кодом, применяющимся для передачи а при t 1 и и=р — 1, где р — простое число информации. Количество т ошибок, имеющих 55 и-+-1 место в канале связи т(1, определяется со- (М, (= (2" + п2 " ) (n + 1), гласно максимальному индексу симметрического многочлена о-,, значение которого от- что превышает мощности всех известных коСО дов. лично от значения о,, выбранного при кади- 60 ровании. Величины cr>, о2, ... o-. поступают Применение q-й логики при декодировании в вычислительный блок 2, а значение т — в двоичных сигналов позволяет использовать блок 7 управления. По значению т блок 7 классические способы решения квадратного управления выдает в вычислительный блок 2 уравнения, что и ведет к увеличению быстрокоманду на решение уравнения 65 действия устройства.

543177

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

Составитель В. Крылова

Редактор Л. Тюрина Техред А. Камышникова Корректор И. Позняковская

Заказ 105/16 Изд. № 112 Тираж 869 Подписное

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

113035, Москва, Раушская иаб., д. 4/5

Типография, пр. Сапунова, 2

Устройство для декодирования сообщений, содержащее приемник аналогового сигнала, вход которого является входом устройства, а ,выход соединен с первым входом блока памяти, блок суммирования по модулю «два», первый вход которого соединен с выходом блока памяти, второй вход — с выходом вычислительного блока, а выход — с первым входом блока управления и выходом устройства, первый выход блока управления соединен с первым входом вычислительного блока, о т л ич а ю щ ее с я тем, что, с целью увеличения количества исправляемых ошибок, в устройство введены блок коммутации и блок q-õ регистров, причем выход приемника аналогового сигнала соединен со входом блока q-х регистров, выходы которого соединены со вторыми входами вычислительного блока и блока управ5 ления, второй выход блока управления соединен со входом блока коммутации, выход которого соединен со вторым входом блока памяти.

10 Источники информации, принятые во внимание при экспертизе:

1. Берлекэмп Э. Алгебраическая теория кодирования. М., Мир, 1973, с. 146, рис. 5, 14.

2, Математические вопросы кибернетики и вычислительной техники. Ереван, изд-во

АН Армянской ССР, 1970, с. 76, рис. 4.