автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Сверточные коды и широкополосные системы связи

РГ6 од

„, „ .РОССИЙСКАЯ АКАДЕМИЯ НАУК ~ о }\сл

ИНСТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ

На правах рукописи

ЗИГАНГИРОВ Дмитрий Камильевич

УДК 621. 391. 15

СВЕРТОЧНЫЕ КОДЫ И ШИРОКОПОЛОСНЫЕ СИСТЕМЫ СВЯЗИ

Специальности:

05. 13.01 Управление в технических; системах 05. 13. 17 Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва — 1993

УДК 62!. 391. 15

Работа выполнена в Институте проблем передачи информации Российской Академии Наук

Научный руководитель:

Официальные оппоненты:

доктор технических наук, профессор Э. М. Габпдулин

доктор технических паук, Ю. Л. Сагалович

кандидат технических наук, О. Д. Скопинцев

Ведущая организация: Академия авиа-космического приборостроения (г. Санкт-Петербург)

Защита диссертации состоится « »-199 г.

в__.час. на заседания специализированного совета

Д. 003. 29.01 в Институте проблем передачи информации РАН по адресу: 101447, Москва, ГСП-4, ул. Ермоловой, 19.

С диссертацией можно ознакомиться в библиотеке ИППИ РАН.

Автореферат разослан « »--- 1993 г.

Ученый секретарь специализированного совета, доктор технических наук

С. Н. СТЕПАНОВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность тени

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

Применение широкополосных сигналов в системах передачи дискретной информации позволяет:

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

-нейтрализовать влияние негативных факторов, определяемых физической структурой радиоканала, таких, как различного ' вида замирания, мног'олучевость, переотражшшя;

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

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

мощность.

Общий принцип формирования широкополосного сообщения (ИПС) состоит в умножении дискретного информационного сигнала со сравнительно низкой скоростью передачи на псевдослучайный гаирокополосный сигнал.

Методы расширения спектра включают 4М-расширение (кодирование по фазе), ЧМ-расг. трение (кодирование по частоте), АН-расширение (кодирование по амплитуде), а также гибридные методы. В работе будут рассматриваться только системы с псевдослучайной перестройкой рабочей частоты (¡ШРЧ).

Для борьбы с организованной помехой Используется помехоустойчивое кодирование. Предполагается, что постановщику помехи ничего не известно о характере сигналов, за исключением типа используемой модуляции (ФМ, ЧМ и др. ) и полосы частот. Кодирование делает передаваемые сигналы бесструктурными, однако постановщик помехи может просто генерировать сигналы,- аналогичные используемым, и тем самым срывать передачу. Для предотвращения этой возможности в передачу вносится дополнительный элемент псевдослучайности.

Аналогичная проблема возникает при использовании несколькими пользователями общей полосы частот. В каждый момент времени

пользователи системы одновременно переласт информацию. ' Кодирован« позволяет улучшить характеристики систем связи без увеличен» мощности передаваемых сигналов, а дополнительное введение для кахдо пары пользователей (передатчик-приемник) определенной псевдослучайно последовательности, разделяет сигналы различных пользователей.

Наряду с блоковыми широко, используются сверточные коды Сверточное кодирование, применяемое вместе с декодированием Витерби стало в последнее время одним из наиболее используемых методо исправления ошибок, что объясняется более простим по сравнению блоковыми кодами декодированием а также возможностью просто реализации декодеров с мягким решением. Практически алгоритм Витерб применяется для двоичных кодов с малой длиной кодового ограничения Недвоичные сверточные коды изучены слабее, хотя при передаче п каналам связи часто используется недвоичная (д- ичная) модуляция.

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

• рассматривается целесообразность использования д-ичных сверточных кодов в системах с псевдослучайной перестройкой рабочих частот;

• изучается метод построения хороших д-ичных сверточных кодов, проводится анализ их характеристик;

исследуются различные методы последовательного декодирования;

• рассматривается применение ранговой метрики в . системах с импульсной помехой;

• предлагается метод алгебро-послеяователышго декодирования д-ичны; сверточных кодов и строится система криптозащиты на основе сверточны: кодов.

1

Цель работы заключается в развитии теории д-ичных сверточных кодо1 и в пх пркмепепии в системах связи с псевдослучайной перестройка рабочей частоты.

Досттаение этой цели предполагает решение следующей совокупносп задач:

-построение д-кчных сверточных кодов и исследование их характеристик; -разработка эффективного метода декодирования д-ичных сверточш» кодов;

-сравнит од ышЯ анализ различных алгоритмов кодирования I гакоявровакжя в систоипх связи с псевдослучайной перестройкой рабоче! частоты.

-з-

1аучная новизна

работе получены следующие результаты:

, Вычислено среднее отношения сигнал/шум в системах ППРЧ. . Для системы ППРЧ с многими пользователями проводится сравнение азличных методов кодирования.

. Построены сверточные МДР коды, найден строчный спектр кодов. . Разработана программная реализация алгоритмов последовательного екодирования и предложен алгоритм алгебро-последовательного екодирования сверточных кодов над большими алфавитами.

Для системы ППРЧ с активной 'помехой предложен алгоритм ;екодирования сверточных кодов с использованием порядковых статистик. ¡. Строится криптосистема на базе д-ичних сверточных кодов.

Положения, выносимые на защиту

I. Вычисление среднего отношения сигнал/шум в системах ППРЧ при согласованном дружественном выборе псевдослучайных

тоследовательностей.

Построение д-ичних МДР сверточных кодов, вычисление строчного • спектра этих кодов.

I Алгебро-последователытй алгоритм декодирования сверточных кодов. 1. Алгоритм почти мягкого декодирования сверточных кодов для . .

систем ППРЧ с использованием порядковых статистик. '.5. Криптосистема на основе, д-ичных сверточных кодов,

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

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

Практическая значимость работы подтверждена актами о внедрении.

Апробация работ

Результаты работы докладывались на Х-ом Всесоюзном симпозиуме по проблемам избыточности в информационных системах (Ленинград-1989), на

II международном семинаре "Алгебраическая и комбинаторная теория кодирования" (Ленинград-1990), на VI международном семинаре "Сперточныо коды; Связь с многими пользователями" (Москва -1990), на научных семинарах в ШИН! РАН и в Лундском университете (Швеция-1992).

Публикации

По теме диссертации опубликовано 6 печатных работ.

Структура диссертации

Диссертационная работа состоит из Введения, четырех глав. Заключения, списка литературы и Приложения.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава носит обзорный и постановочный характер. В ней дается описание структуры системы . связи с псевдослучайной перестройкой рабочей частоты. Особое внимание уделяется использовании помехоустойчивого кодирования.

Кодеры реальных систем ППРЧ строятся по двум стандартным схемам: с использованием каскадных и итеративных конструкций. Например, система .глсб использует трехступенчатое каскадное кодирование.

В приемном устройстве после временного деперемехения- и приведения сигнала с ППРЧ к узкополосному виду осуществляется демодуляция и декодирование. Демодулятор мохот выносить репенио о стирании символа. Вневннй декодер исправляет ошибки -и стирания, причем, число исправляемых овибок и стираний ^, такое что гtl*tl< с1а-1, где <33 - минимальное расстояние внеинего кода.

В системе мобильней телефонной связи сбм используются итеративная конструкция, в которой часть блока информационных символов длиной 50 бит кодируется блоковым кодом, а вось блок длиной 260 бит, кроне последних 78 бит, кодируется сверточным кодом со скоростью 1/2 и памятью 5. Кроме этого, в системе предусмотрена зааита от несанкционированного доступа.

В практических системах применяются также некаскаднш схемы с использованием только сворточных кодов. Для каналов с двоичной или чотворпчной ФЦ и когерентной демодуляцией возможно примоиенио двоичных сворточннх кодов. В таких конструкциях в обаем случае используются ДВОПЧКиа КОДЫ, В которых С ВЫХОД1ШИ символам ставятся в соответствие 2°- ортогональных сигналов. Однако, в ряде приложений цод©сообразным оказывается применение д-пчной ФЦ и некогерентной «оконуляцап. В этих случаях недвоичные кодовые символы ставятся в

:оответствиа сигналам м-ичной модуляции.

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

Вторая глава посвящена анализу помех в системах ППРЧ; ¡)лсснатрипаптся характеристики систем без кодирования, с использованием различных методов помехоустойчивого • кодирования; показывается целесообразность совместного использования д-ичного кодирования и многонозиционной модуляции. Для систем с согласованным выбором протокола ППРЧ выводится оценка на среднее отношение сигвал/иун. Этот параметр является основным при оценке характеристик систем связи с кодированием при работе в условиях помех естественного и искусственного происхождения.

Представлен сравнительный анализ систем ППРЧ без кодирования с использованием различных видов кодирования при воздействии помех различного происхогпвпрч и структуры, а так хв в системах с кодовым разделением при случайном выборе последовательностей перескоков. На •»;норо лиддит Л" мнется :>мпод о возможном эффективном использовании в '•1с:т«их ШП'Ч .;-И'МЮЙ модуляции совместно с д-ичным сверточным | пнироча!и,"м.

В рабою гчплиг.цругггч следующая модель системы с ППРЧ со многими пользотт^лячи.

Пусть каналом могу г одновременно пользоваться н пользователей. При этой <3уд'.>и иролиптгл Г!., что м-1 мешающий сигнал может случайным образом занимать ь частот. Известно, что при независимом выборе частот ср"пнрп отирчолпч сигнал/пун

Пусть пос»д.пчи!с с номером т-0 перелает сообщение длины к, амплитуды всех сигналов равны р- модность сигнала.

Сигнал па входе приемника при условии синхронизации по полезному сигналу при МТМ

N

(1)

Я- 1

у( Ь)~А У уго,(Ь-кТ) ехр (Цо(0) (Ь-кТ)*Ъ(°' (Ь))) +

J - о о

J - о о

га-о, 1,... ,Н-1

где н-т/то, т -длительность одного передаваемого' сигнала, Р„

1, 0<«то. о 1 О,в противно

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

нимать значения из некоторого конечного мнохества (ввз, ..., в }, (<tJt|} ~ последовательность независимых случайных фаз в интервале (-я,я), вносимых во время перескока с одной частоты на другую, постоянных в интервале работы на одной частоте,

псевдослучайная с периодом н последовательность рабочих частот {о.....о ).

1 К

Второе слагаемое суммы является помехой от остальных

_С») гт) («I («) О - О X ,

а третье л(и-собственный пум приемника с односторонней спектральной плотностью N .

о

Корреляционный приемник, настроенный на полезный сигнал для оценки к - ого символа, выполняет операцию вида

(Н*1)Т

¡У(Ы (Ь-кТ)" ехр(-1а<°' (Ь-кТ)) <?<:-

*г V »

•А/з\т ехр(1ч<°')+ Т (И (V (г""))х

I к и М , О И м . О

«■»♦».»г

х | ехр (1(а'~' (Ь-кТ)+ч(-' ))ехр(-Н*'мс" (Ь-кт)) сЗе]+ (3)

лг

* | «(Цг^"' а-кТ)"ехр(-1а^°} (Ь-кТ)) йЬ, иг

где периодические корреляционные функции двух последовательностей 'о. '

*о .^о^" I у'°'(Ь-Х )у'1} (Ь)'бЬ

О / \ О« J А и*-«

(1)

' X ^ < » »

о|

Пусть го| но равно целому кратному го> а, например, 0<1т <г < (1*1 )т <г,

о о» о

а в^ число периодов г, на которое сдвинуты полезный и мешающий сигнал. Заметим, что отновение сигнал/иум вычисляется при усреднении по с-азовоиу сдвигу, временной задержке и несувей частоте.

Дисперсия иуновой компоненты * вычисляется следуюцим образом.

о*

г

М-1

Ё ]<\*т.о<\>\'*\К.о(Хт>\'>* *«оТ'4"

я - о

""'т° (5)

ТТ Г<я * >><** /4■

4 ТЫ и и J т. О Щ т, О я О

и« ОА■О

I Т

о

Вычислив интеграл, получаем

б(г Т*/ЗиуКу (<? (1+1-К)+<? 1Х-К) + <? <1+1)+С? (1))*ЫТ /4,

ОЪ о I* и щ, I м,( т.( т.! О

"Я- о I * О

где с ( ("I)-апериодическая взаимно-корреляционная функция.

Отношение сигнал/шум определяется как отношение рт/2 к Уо(« .) и

произведя суммирование по т и 1 имеем:

* " (6)

Гакии образом, доказано, что при фиксированном значении отношения сигнал/пум и согласованном выборе последовательности перескока, можно включить в систему примерно в три раза большее число абонентов.

Третья глава посвящена построению и анализу д-ичных сверточннх кодов памяти ш. В параграфах 3.2, 3.3 дается описание сверточннх кодов с максимальным достижимым расстоянием (НДР), метод построения таких кодов, вычисляется спектр кодов для д-4, для кодов над большими алфавитами, найден алгоритм для приближенной оценки спектра.

Определенно 1. Сперточннй код над полем д) со скоростью г=ь/с, определяемый норотдающей матрицей в, является МДР кодом, если для п-0, 1, . . ., п, дистанционный профиль кода с?п удовлетворяет ооо]поступит

<3 - (п+1 )(с-Ь)*1,

п

го ость грпшшл • Синглтона-Плоткина достигается,, для любого укороченного кола. Поэтому минимальное расстояние кода <з с! . .-(т+1) (с-Ь) + 1.

Кпаяратнио матрицы порядка л с неотрицательными элементами, ••одержали« иупопую рчд подматрицу, где будем называть

кйпигопскпми, а гсо остальные - некённговокими,

Ллл пэхоткчнш МЛР сверточннх кодов использовалась следующая юор'чп, на к ладил чушал ограничения на вид несистематической части цоротл-тцой матрицы С - патрицы О-

Теорема 1. СперточныЛ год с порождаемой матрнцой в. является ЫДРкодом тогда и только тогда, когда все некбниговские подматрицы матрицы О любых порядков непнрохдпнн.

Перебором всох таких матриц для скорости 1/2 найдены все НДР коды для <7<13, для <7-2К н некоторые коды для д-25. Результаты сведены п Таблицу 1 . Следует отнотить, что некоторые коды из полученных сомойстп кодов были найдены Сстессеном без использования свойств теоремы 1.

Предложенные коды и их укорочения оптимальны в смысле свободного расстояния. По найденным кодам для скорости 1/2 можно построить коды для любой скорости, применяя вычеркивание столбцов и строк в порождающей матрица исходного кода. Ниже приведены характеристики найденных кодов. Здесь (^-свободное расстояние, я-чнсло различных' кодов с задании сI . Полный перебор -показал, что для данных д не сувествует НДР сверточных кодов с большим <3 .

я а / N

2 5 1

4 7 6

5 9 16

7 I 1 18

8 1 1 84

9 I 1 336

16 13 18 180

32 15 ---

Нахождение спектра сверточных кодов для д*2 является трудной задачей, т.к. число состояний его репетчатой диаграммы равно <Г*<Г • однако для ИДР кодов с д-4 удается уыеньвить размеры матрицы и найти полный спектр кода.

Если исправление оиибок происходит на длине кода, основной характеристикой кода является набор ого строчных расстояний. Для НДР сверточных кодов аналитическое описание распределения строчных весов может быть найдено с использованием тождества Нак-Бильямс, свлзываюдего распределение весов AJ(к) кода с распределением весов дуального кода (к), где ¿-те'куцая длина кода

Ко Ьа

£ сГ4 к.1.....И, 1-0.....кс. (7)

1 - О > 0-о

При к'1 и скорости 1/2 очевидно, что а (\)-1, А1(\)-0,

и ¡>о(\)-1, Вг(\)-0, в При увеличении к число слов с весом но

больниц к. не изменяется, а остальные веса находятся из (7).

Пая других скоростей спектр можно пересчитать, исходя из указанного соотношения при других начальных условиях. Найдем спектр НДР сверточкого кода для скоростей 1/3 и 2/3 получаемых вычеркиванием нечетных строк кз поромакзэй патрицу кода со скорость» 1/2.

Пра к'1 инеем д (\>-1, а Г1 )-о, А (и*0, л (1)-д-i и в

О 1 9 Э О

В (\)~0, ва (}}-3(д-1). При увеличении к число слов с весом, не Оольвка 3(&-1), в коле со скоростью 1/2 не изменяется, а в дуальном ®ау кодо во изменяется число слов с весом, не Оольвим к. Далео расврэя&воннэ в< находится из (7).

Строчннм спектром сверточного кода называется число слов веса 1 с ненулевым первым символом

5 (к)*А1(к)-А1(к-1), 1-0,...,2к. Вычислен строчный спектр НДР сверточных кодов для д-зг и следующих скоростей

X 1/2 1/3 2/3

л 1302

5 65206

6 1808044

7 372 28168956

8 13299 5208 236617853

9 487625 26164 806031801

10 1098048

И 16222315

12 1555248046

13 8838626338

14 22718386046

В параграфах 3. А и 3. 5 для различных алгоритмов последовательного декодирования сверточных кодов изучается зависимость сроДнего числа ветвлений от вероятности ошибки в канале, и предлагается алгебро-последователышй алгоритм декодирования g-ичных сверточных кодов.

Одним из эффективных методов декодирования сверточных кодов являются алгоритмы последовательного декодирования, в частности алгоритм Фано, стек-алгоритм и получивший в последнее время иирокоо развитие крипер- алгоритм. В диссертации разработаны эти алгоритмы применительно к 7-ичнсну алфавиту. На основе этого подхода создан про-граишшй комплекс [1], давний возможность изучить сложность алгоритмов, то есть количество операций, необходимых для декодирования одного символа. Под операцией понимается посещение^ одного узла кодового дерева. • Так как сложность каждого из этих алгоритмов определяется количеством посещенных узлов, и для кода со скоростью п-ь/с за каждый узлом непосредственно следуют <jb узлов, для больших q сложности этих алгоритмов становится очень большой. Поэтому при больпих q для декодирования таких кодов предлагается алгебро-последопательный алгоритм.

Процесс декодирования состоит из двух этапов [6]. lia первой этапе декодер определяет положения овибочных символов. т.о. координаты ненулевых символов шумовой последовательности п. На второй этапе декодер определяет переданную информационную последовательность по принятой последовательности г, используя информацию о положении ошибочных символов. Болое подробное описание декодирования начнем со второго этапа.

Введем в рассмотрение последовательность п - последовательность

хэмнинговых ошибочных символов. Она состоит из символов алфавита 1с,е) и имеет символ с ("correct") в тех позициях, где принятый символ совпадает с переданным и символ e("erroneous") - в остальных позициях. Знание декодером положений ошибочных символов и означает знание последовательности пн.

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

J|n-'G|"-'= г|"-\ (8)

1 о 1 о 1 о -

относительно и. Полученное решение и объявляется декодированной последовательностью.

Очевидно, что если положения ошибок определены правильно, т.е. последовательность п истинная, то:

н

1) невычеркнутые символы последовательности г совпадают с соответствующими символами последовательности v ;

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

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

а) либо система (8) не имеет решения, что является признаком того, что п неистинная;

н

б) либо система (8 ) имеет решонио и тогда декодер максимального правдоподобия также не сможет принять однозначного правильного решения.

Отметим, чго условно существования решения системы (8 ) состойi

в том, что ранг матрицы G равен рангу расширенной матрицы G ~ системы (0): '

rank G|n" '' rank С - I"/ (9)

1 о г1 о

Перейдем к описанию первого этапа декодирования - нахождения последовательности п^ . При нахождении пя используются принципы последовательного декодирования. Мы остановимся на описании

модификации, основанной на стек-алгоритме.

Совокупность последовательностей пн может быть представлена как совокупность путей дерева положений ошибок. в котором последовательные узлы соединены ветвями длины единица (из одного символа), из каждого узла выходит две ветви: одна - из символа ■ "с", другая - из символа "е". Каждому узлу дерева пя|^"'на глубине л поставим в соответствие метрику

мспх-';. [п- а(пнГо-')и ♦ где dfn Г"') означает вес последовательности n I""' . Оптимальннми

я 1 о я 1 о

является выбор величин

- 1 од —I Е , 3 - log —— , 7-z ' *qz

где

г - (1-г) log((j1)q.

Узел п называется живым, если соответствующая ему система (8) имеет решение (т.е. выполняется условие (9)) и мертвым в противном случае.

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

Суцественное изменение состоит в том, что в стек заносятся лишь живые узлы дерева положений ошибок. Определение живости узла производится с использоваштем (9). Исследуется случай, когда передача производится блоками информационных символов, за которыми следует "хвост" из нулевых подблоков, а декодирование завершается, когда декодер впервые достигает концевых узлов дерева.

Рассмотренные в этой глава <т-ич1ше сверточные коды обладают рядом свойств, которые позволяют переборно найти все коды с данными параметрами и найти строчный спектр этих кодав. Для декодирования ртнх кодов предлагается использовать алгейро-последовательноо декодирование.

В четвертой главе рассматривается эффективность применения 7-пчннх сверточннх кодов в системах с ППРЧ.

В системах передачи информации с ППРЧ возможно применение сворточного кодирования для исправления ошибок, возникших в результате различного рода помех. В параграфе 4.1 изучается использование g-ичного сверточного кодирования для увеличения числа пользователей при согласованном дружественном выборе псевдослучайных последовательностей.

Оценка помехоустойчивости системы с ППРЧ и д-ичныи сгерточиым кодом проводится по формулаи

в„ РЫ), (10)

Г

где Р(б)- вероятность ошибки декодирования при передаче двух кодовых слов на расстоянии <3, в -число кодовых слов веса <3. Выигрыш от

с!

применения МДР сверточных кодов по сравнению с к-дуалышмп сверточными кодами при рь < 10'® составляет около 1 Дб.

Использование кодирования в системах ППРЧ с активными помехами в классическом виде в некоторых случаях не дает существенных результатов.

В параграфе 4.2 предлагается алгоритм, использующий при декодировании в каналах с активной помехой статистику выходов корреляторов.

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

В диссертации предложено "почти мягкое" декодирование, использующее статистические ранги порядковых статистик, образованных выходами корреляторов, то есть упорядоченные в порядке убывания величины значения выходов корреляторов (вариационный ряд). Необходим-) знать распределение выхода - ранг содержащего сигнал коррелятора г вариационном ряду. Обозначим р (капк условную вероятность того, что ранг j-oгo коррелятора равен 1 при условии, что сигнал согласован с ^-ым коррелятором. Очевидно что р (Папк j=i) не зависит от ] и б<м ограничения общности можно считать Вероятность р (папк

равна вероятности собшия, что выходы 1-1 корреляторов больше, выходы первого коррелятора, а выходы 1-го остальных д-1 корреляюрс-н - меньше

{Г,Ч.....г,<5 1 и 1<г<>5 .....с,>5 »•

' I - т 1*1 д

где j * 1 - номера любых корреляторов но содержащих полезного сигнала. Так как величины г г , г , ...,г независимы, и не

зависят от г , то вероятность того, что первый коррелятор будет иметь номер 1 равна (для одного моваюцего сигнала)

со

Р(Папк(г1,)-1)-(1-(Т-^ (х))1-* (1-Рг(х))Г1 (х)я~'<?1 (х)с!х*

СО

*1/я- С1" [ (1-Р (х)сЗх(11)

+ (1~1/я) с г п-г (х)Г~ р (х)г (х)ах, где

<з-гЗ 1 г 1 1

\ ехр[- -

* -/Тле -<ь I 2а > 'нкцня распределения выхода коррелятора с метающим сигналом.

г (х)--1— Г ехр\--*—\<Зу -

' Угле -А I 2аг> гнкция распределения выходов корреляторов, не содержащих сигнал,

(х) - плотность распределения выхода коррелятора, содержащего по-

;зный сигнал и но содержащего мешающего сигнала,

» / > ' [ (х-(з*1)и)')

Ф (х)--ехр - -,

г УТсто I 20* > ютность распределения коррелятора с сигналом и помехой.

Здесь первое слагаемое соответствует случаю, когда мепающий 1гнал имеется в каком-нибудь корреляторе га, п*\, но ж" ■

Второе слагаемое - когда мешающий сигнал в первом >рреляторв.

Третье - когда мешающий сигнал в т-ом корреляторе га* 1, и. г^г^.

Распределение вероятностей ранга коррелятора, содержащего снг-1Л, можот быть найдено либо по формуле (10), либо методом Нонте-

фЛО.

Процесс декодирования при использовании ранговой метрики состоит слелугием. Упорядочим выходы корреляторов в порядке убивания их гачений. Пусть ранг коррелятора, содержащего переданный сигнал равен В качество весовой Функции метрики будем использовать вероятность >го, что истпшшЯ коррелятор в вариационном ряду, имеет ранг 1. Тогда щраконие метрики вдоль данного пути равно

р'1од qV(Rank г (1]-*1)-К. я

Качество работы декодера можно оценить по къличеству посещенных 1лов. Известно, что первый момент числа операций на декодированный [мвол при последовательном декодировании ограничен величиной, но висящей от длины кодового ограничения и ограничения на обратный тек декодера, если скорость передачи я <

Пропгрыя от применения ранговой метрики увеличивается при увели-'нин отношения сигнал/шум, увеличении мощности мешающих сигналов, ■реходе к меньшим алфавитам. Так для проигрыз при <т-32 - 0.7» 1.0 5 при ^-16 - 1+3.5 дБ (при изменении помехи от -<» до 0 дБ).

В параграфе 4.3 в качество одного пз применений д-пчного «споротого кодирования совместно с алгебро-послелопателышм докодирова-[ои рассматривается криптосистема типа криптосистемы Цакэлиса.

Порождающая натрии д-ичного сверточного кода со скоростью Ь/с

и памятью и является порождающей матрицей сверточного кода с единичной памятью и скоростью (Ьт)/(ст),

(12)

Умножим матрицы й'1'".^" слева на случайную матрицу Б размера (Ьт)х(Ьт), а справа на перестановочную матрицу т размера (ст)х(ст).

Матрицы <зг'' Операция

V" ( V , V ,

Б-в т и С - Б в т являются открытым ключей, цифрования состоит в кодировании сообщения .V } длины п сверточным кодом

п - 1

■

(13)

Ъ"> Ъ(3>й 0

0 0

0 о Ъ"} с'

вг1>сгг'о

|П- 1 I п- 1 — I " - 1

V "И в

• О ' О 1 о

После этого к последовательности добавляется шумовая ■

последовательность п, содержащая е ненулевых символов из ггСд). и полученная последовательность г|1'1.

г Г'1- (г , г , г.....г ), где

г - (г , г ,..., г ), г есгСд), 1-0, п-1 ,с, ( ( ( I г ' (с (Л '1'I

передается в канал.

При дешифровании, каждый подблок г( принятой последовательности г умножаются справа на т'. К полученной последовательности г1 применяется процедура декодирования сверточного кода с памятью ет и скоростью Ь/с, исправляются Ь ошибок. После этого декодированная последовательность у' умножается на б"', получаем V.

Для улучшения параметров системы будем использовать и параллельно работающих сверточных кодов, выходные символы которых перемежаются. Шумовая последовательность в этом случае должна формироваться на основе ¿-кратных пакетов длины N. Таким образом открытым ключей является порождающая матрица д-ичного сверточного КОДа со скоростью ИЬт/Мст.

Далее в работе рассматриваются различные алгоритмы раскрытия ванной криптосистемы. Наименее трудоемкий для нелегального пользователя - исправление пакетов стираний на длине сит. При этом производятся попытки декодирования всех возможных конфигураций пакетов стираний длины < N и кратности ь. Число возможных конфигураций положений пакетов для послаловатольности длины л находится из выражения

и . (14)

' 'л- г 1 - 1 ) с Н- I >

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

Для я-256 мы имеем т-86. г-1/2 и <^-7 72 и пусть N-5. Таким образом мы получили сверточный код с Ь-5, с-10, <За равным <За первоначального сверточного кода, исправляющий пакеты ошибок длины 5 и кратности 55. Открытым ключви являются два матрицы размера 430x860 из д-ичных элементов <2гв"'двоичных элементов), поле в котором проводятся вычисления и длина пакета ошибок.

Преимущество предложенной системы по сравнению с классической системой Макэлиса состоит в том что, сложность декодирования определяется сложностью декодера сверточных кодов, допускающих простую аппаратную реализацию. Кроне этого возможна параллельная обработка каждой из N последовательностей, когда правильное обнаружение стирания в одной последовательности определяет положенно стирания в к-1 последовательностях, что значительно сокращает числ" операций. При передаче криптограмм по реальной линии связи со многими пользователями и шумом возможно применение мягкого решения.

Заключение

В диссертационной работе разработана теория д-ичных сверточных кодов и исследовано их применение в системах связи с псевдослучайной перестройкой рабочей частоты.

К наиболее существенным результатам относятся следующие:

1. Вычислено сроднее отношение сигнал/шум п системах ППРЧ при согласованном дружественном выборе псевдослучайных последовательностей.

2. Рассмотрены сверточные ЦДР коды, найден строчный спектр кодов.

3. Разработана программная реализация алгоритмов последовательного декодирования и предложен алгоритм алгебро-последователыюго декодирования' сверточных кодов над большими алфавитами.

4. Предложен алгоритм почти мягкого декодирования сверточных кодов для систем ППРЧ с использованием порядковых статистик.

5. В качестве другого приложения строится криптосистема па оснопгт д-ичкнх сверточных кодов.

Основные результаты диссертации опубликованы в слелугяих публикациях: '

1. Л. А. Безрук, Д. К. Зигангиров, С.А.Попов. Последовательное декодирование сверточных кодов// Алгоритмы и программ. Информационный бюллетень. -Цосква. -1989 №4, с.

-162. А. А. Безрук, Д. К. Зигангиров, С.А.Попов. Сравнительный анали: алгоритмов последовательного декодирования//Труды X симпозиума пс проблемам избыточности в информационных системах. -Ленинград, -19Э£ г.. Ч 1.. с. 115-118.

3. А. А. Безрук, Д. К. Зигангиров, С. А. Попов. Сравнительный анали: алгоритмов последовательного декодирования.// Проблемы передач! информации. -М. -1991. № 2 . -с. 100-106.

4. Д. К. Зигангиров, К. Ш. Зигангиров. Последовательное синлромнос декодирование сверточных кодов над большими алфавитами// Проблемь передачи информации. -М. -1991. 1(2 . -с. эг-96.

5. D.K.Zigangirov, К.Sh.Zigangirov. Algebiaic-trellis decoding ol convolutional codes// Тезисы докладов VI Советско-Шведского семинара: Сверточные коды; Связь с многими пользователями, -Москва -1990

6. D.K.Zigangirov, К.Sh.Zigangirov. Syndrome sequential decoding ol convolutional codes over large alphabet// Тезисы докладови Совотско-Болгарского симпозиума "Алгебраическая и комбинаторная твори; кодирования", -Ленинград, -1990