Алгоритмические вопросы построения оптимальных кодов для многих приемников тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

российская лклдения наук вычнс/мтелыши центр

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

алиев иамкп иагонедович

УДК 519.725

алгоритмические вопросы построения оптиналышх кодов для многих приемников

01.01.09 - математическая кибернетика

' АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата Физико-математических наук

Носква 1993

Работа выполнена в Вычислительном центре РАН

Научный руководитель: доктор Физико-натенатических нал«, профессор В. К. Леонтьев

Официальные оппоненты: доктор Физкко-математических наук, профессор Э. И. Гордеев кандидат Физико-математических наук, Н. Н. Кузорин

Ведущая организация: научны: совет комплексной проб-лекы "Кибернетика"

1993г. вА^^час

Зашита состоится ______ 1993г. a часов на

заседании Специализированного совета К 002. 32. 02 в Вычислительном центре ран по адресу: Носква. ГСИ-1, ул. Вавилова, д. Ю.

С диссертацией ног.но о .¡накопиться в библиотеке Математического института РАН.

Ли

Автореферат разослал "___"__'_______1993г.

Учений секретарь Специализированного Совета К 002. 32. 02 при ВЦ АН России,

доктор Физ. -мат. наук к. В. Рудаков

0БГ1ЛЯ ХАРАКТЕРИСТИКА РАБОТЫ

-Актуальность тени.. При передаче информации по реальны» каналам связи из-за помех, которые могут иметь саную различную физическую природу, неизбежны овшбки. история кодирования, контролирушего ошибки.началась в 1948г. публикацией знаменитой статьи Клода Шеннона, в которой била показана возможность передачи информации по каналу связи с иунами со скорость» меньшей пропускной способности канала и произвольной малой оиибкой декодирования.

Пусть Е(Н) - «позестсо всех двоичных слов длины Н. Любое нно-зостбо из Е(Н)> каждое слово которого при данном типе ошибок допускает однозначное восстановление по полученный на приемном конце словам, называется кодом с исправлением опивок. На практике часто встречается капали, отлкчаюншеся асимметрическим характером ошибок, например, такие, в которых преобладают замещения вида 0->1 и 1-Х). Другим типом ошибок являются так назыпаеные выпадения и вставки символов.

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

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

_Цель работы .. Целью диссертации является: -разработка эффективных алгоритмов построения оптанальных кодов в случае многих приемников;

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

_Иетоды исследования .. В ^астояшёй работе использованы ком-

- г -

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

„Научная новизна ..

-найдены необходимые и достаточные условия, при которых оити-нальный код совпадает со всем пространством двоичных слов Е(Н);

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

„Апробация работы .. Результаты исследования докладывались на семинарах Вычислительного центра РАН.

.структура диссертации .. диссертация состоит из введения, девяти параграфов, приложения и списка литературы.

.Публикации .. Основные результаты диссертации опубликованы в 4 статьях, список которых приводится в конце автореферата.

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

Во введении сформулирована задача исследования, кратко описано содержание параграфов.

В $1 вводятся основные определения и обозначения. Пусть Е(Ю-

- множество всех слов длины N. и пусть а-(а(1).а(2).....а(Н)) -

!

произвольное слово из Е1Н>. Если слова 1X1. хг.... хи, 1<1<Н. из Е(Н-1) могут быть получены из слова а множества Е(н> в результате выпадения разноиндексных символов.то набор (х1, х2,.... хи, будем называть потомствен слова а. а слово а -родителем для этого потомства.

Слово из Е1Н-1). полученное в результате выпадения символа из Е(Н), буден называть проекцией этого слова. Для проекций слова а введен обозначение:

аш = (а(1)... )а(1*1)... а(Н)).

Два :лова из Е(Н-1) называются зависимыми, если они обладает хотя бы одним общих потомством в еи-11, в противном случае слова называется независимыми. Кодон в Е1К) будем называть любое множество независимых слов в Е(Ы). Код Н из Е(Н) будем называть полным, если он не содержится ни в каком другой коде из к(Н). и максимальным.если в е(н) не содержится код большей нощности.

Полсловом слова а будем называть любую последовательность под-

ряд расположенных символов слова а. Подслово некоторого слова из Е(Н), содержащее не менее двух символов, будем называть отрезкой, если лу>5ые два соседние символа этого полслова различил. Обратный для данного отрезка называется отрезок. полученный из исходного за-непой кагдого двоюшого синвола на обратный, т. е. О на I я наоборот. Серией слова а будем называть подслово из одинаковых символов, не содержащееся ни в каком другом иодслосе этого те типа. Расг-.грением (сухениен) серии слова а будем называть результат добавлеь (соответственно удаления) одного из ее синволои.

Обозначим:

К1(а,Ь) - значение истинности высказывания "одно из слов а и Ъ может быть получено из другого заменой некоторого отрезка на обратный":

К2(а, Ь, э) - значение истинности высказывания "одно из слов а и Ь нохет быть получено из другого сужением некоторой серии длины нрасширением некоторой другой серии длшш >(з-1)". 'А и А' - соответственно первый и последний символы слова А.

В *2 для случая двух приенников получены условия независимости двух произвольных слов из Е(Н) или.что то хе, условия существования кода, включавшего два заданных слова.

Доказана следующая теорема.

.Теорема .. множество н из Е(Н) при г = 2 является кодон тогда и только тогда, когда для кахдой пары слов а и Ь из Н нарушены условия К1 (а, Ь), К2(а,Ь,2).

В »3 для случая двух приемников сфорнулироваиы алгоритмы проверки независимости слов из Е(Н), построения лексикографически первого полного кода в Е(Н). декодирования и оценена их слол гость.

В 94 показано, что задача построения максимального кода в ЕШ) является задачей построения независимого множества в графах специального вида, построены матрицы смезшости этих графов для некото-рык частныя случаев, сформулированы алгоритны вычисления максимальных независимых множеств в графах.

В $5 установлен ряд Фактов о независимых словах из Е(Н).

В $6 найдены максимальные коды при малых н в случае двук приемников. С поиотьо ЭВМ для мощностей максимального кода при налых Н получены следующие результаты.

! н :з:ч:5 :б :г :в :9 :ю :н : 1а из ¡14 :15 :

ношность : 5:в: 11: гз:41; 60:114 189! 347:596:1 юо: 1952:36ю; :макс.кода: :::::: : : : : : :

В »7 доказана следующая ленка.

_/!екна ..Любое слово а из Е(Н) однозначно определяется своими треня произвольными попарно различными проекциями.

Пусть для слов а и Ь ия ЕШ) выполнено условие К1(а. Ы.т. е. существует такой отрезок Т. что а=(5Т0), Ъг(БТ'О), где 5. Т, О - некоторые подслойа. Т"- отрезок, обратный отрезку Т.

Введен обозначения:

ез. 1 (а. ь> =К1 (а. ы а (Б' = 'Т) а (ст~>' = 'О).

КЗ. 2(а. Ы =К1(а,ЬН!Б'=' (Т">) МТ' = 'О).

Доказана следующая теорема.

.Теорема .. Мновество К из Е(Ы) при г = 3 является кодон тогда и только тогда, когда для кахдои аагы слов а и Ь из И нарушены условия К2(а. Ь. 3), КЗ. 1 (а. Ь), КЗ. 2 (а, Ь).

В »в рассмотрен случай, когда количество приемников превышает 3. Получены необходимые и достаточные условия независимости слов и сформулирован линейный алгоритм проверки этих условий.

Доказана сдедуюаяя теорена.

„Теорема .. иловество к из еш> при (.>2 является кодон тогда и только тогда, когда для каждой пары слов а и Ь кз Н, разлнчашншея лишь взаикнообратныкн отрезками: а=(ЭТО), Ь- (ЭТ'О). выполняется неравенство:

(Б.т>, к(т*.о)) ♦ пппслз,т~).и(т».01 где через !,(».«) обозначена длина последней серии полслова », сос-

- ь -

тавлегаюй из первого синвола V. через »(V. V) обозначена длина первой серии полслова V. составленной из последнего символа полслова V. V.V - последовательные подслсва.

Приведены результаты вычисления мощностей наксималышх кодов для различных значений I и Я:

:\ н: з: 4: 5! в: 7: в: 9: ю: и:

• • •

: з : а: 14: ге: 4в: ов: 1бч: 307: 57в:1096:

: 4 : а: 16! з?.: егмго: гзо: 442: 649:1637:

: 5 : а: 1в: зг: 64:12в: гм: ^oi: 99в:197ь:

: 6 ! в: 16: зг: et:1гв: 256! 512!1022:2040:

: 7 : в: 16! зг: 64!128! 256: 512:1024:2043:

В »9 получено соотношение поеду длиной двоичного сигнала К и количествен приемников t, необходимое и достаточное для однозначного определения произвольного слова из Е(Н) по его проекяияп.

-Теорема.. Любое слово а из Е(Н) однозначно определяется своими разьоиндексными проекциями тогда и только тогда, когда t>n/2+l.

В приложении приведет максимальные коды для значений п -3, 4,... .... 15 в случае двуе приемников.

По теме диссертации опубликованы следующие работы:

I. Алиев и. И. Восстановление произвольного сигнала в каналах с помехами типа "выпадение символа", 8 с// деп. в ВИНИТИ 270-В93.

?.. Алиев И. И. Максимальные коды при передаче двоичных слов небольшой длины по двум каналам с выпадением одного символа, п с // //деп. в ВГЧИТК 271-В93.

- ь -

3. Алиев Ш. Н. Лилейный алгоритм проверки различимости сигналов . ори помехах тина "выпадение символа" (тезисы). - в сб. статей лгу.

выв. 2, Махачкала. 1992.

4. Алиев Ш. Н. Рекуррентный метод построения натршш смежности графа сигналов (тезисы) - в сб. статей ЛГУ. вып. 2. Махачкала. 199а.