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

московский государственный инст/пп РАдиотвзшики. электроники Г 8 Ой АВТОМАТИКИ /ТЕХНИШЛШЙ ТНШЕРСИТЕЕ/

Ли

На. правах рукашса

1СХЯ03 Геннадий Яйансаиг

КОМБИНАТОРНАЯ ТНЗРЖ ШЮРМАШН

/ИНФОРЫАШОННАЯ: ХВОРГО ДЕТЕРМШИРСаАШЫХ ПРОЦВССОВ/

Специальность 05.13.01. Управление а. технических системах

АВТСРВЗсРАТ

диссертация, на соискание учено! степени дсгасра технических науа

Москва. 1994

/

Работа выполнена £ Московском государственном институте радиотехники, алеэтзюники в автоматики /техническом университете/. '

Официальные оппонента: доктор технических наук, профессор В.Г Лазарев.,

доктор технических наук, профессор Г.К-Храыешин,

доктор'технических наук, профессор Б-Е-Ддычеев

Ведуиая организация - Цосковскй анергетическиг институт /твхыяческиЕ университет/'.

Защита состоится ~ "_1994 г. в час.

ыяв. на заседании диссертационного совета Л (£2.54.01 в Еосковсксш государственном институте радиотехники, электроники и автомашин /техническом университете/ ло адресу: 117454, Кос-ква, проспект Вернадского, 7В.

С днссертяпиеЯ можно оанвкпмиться в библиотеке Московского-государственного института радиотехники, электроники.и автоматики /технического университета/.

Автореферат разослан ">¿0' (И^ С ^ 1994 г.

УченыЛ секретарь ^

диссертационного совета Хозрюв Г.К.

/ /

- 3 -

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

Актуальность проблемы. Теоретическим базисом различных информационных устройств я систем является теория информации, изучающая процессы появления, преобразования, передачи, переработки, хранения а отображения информации. В настоящее время теория информации представляет собой совокупность отдельны! частных теорий, описывающих разные формы существования информации с учетом или без учета критериев оценки её получателем. Центральное место среди: частных теорий информации занимает формальная вероятностная теория К.Шеннона, исследующая информацию в виде случайных событий, значений случайных величин и реализаций случайных функций. Математическим аппаратом этой теории служи! теория вероятностей.

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

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

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

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

Отсутствие таков теории существенно сдерживает общее гармоничное развитие теории информации. Некоторые застой, который наблюдается в 8той области знания, 'объясняется ещё и отсутствием новых идей, которые, как и в любой другой области, являх>тся источником её саморазвития. Выходящая же изредка в стране литература по теории информации посвящена в основном изложении давно -полученных результатов шенноновской теория или их незначительному обобщение. Поэтому проблема разработки информационной теории детерминированных процессов, которая но кру17 рассматриваемых вопросов была Он хоть в какой-то степени соразмерна с вероятностной теорией информации Шеннона, является актуальной.

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

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

Задачи исследования. I. Установить меру количества информации- в элемента конечного множества,.исследовать её свойства.

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

3. Рассмотреть каналы, обеспечивающие передачу элементов конечного множества, выявить и. проанализировать их основные Характеристики. Исследовать процесс передачи информации по таким каналам.

4. Установить меру количества информации в числе множества

действительных. чисел ограниченного интервала, исследовать её свойства.

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

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

7. Установить меру количества информации в функции множества детерминированных функций, исследовать её свойства.

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

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

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

Научная новизна результатов. Все результаты диссертационной работы, за исключением приведенных в гл. I и а.п. 2.1. 2.2, 2.6, 2.7, S.I, являются новыми. К наиболее существенным новым научным результатам относятся:

L. Пера относительной определенности элемента одного конечного множества в элементе другого конечного множества при всюду определенном, сюръективном и функциональном отображении первого множества во второе.

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

3. riepu относительной определенности элемента декартова про-

изведешш конечного числа конечных множеств и относительной определенности элемента конечного множества в последовательности элементов нескольких конечных множеств.

4. Кера относительного количества информация в элементе конечного множества.

5. Доказательство утверждения, что развиваемая в настоящей работе комбинаторная теория информации не является частным случаем вероятностной теории К.Шеннона.

6. Девять типов детерминированных дискретных источников /ДЕК/.

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

8. Основная теорема эффективного кодирования для ДДИ.

Э. Восемь типов детерминированных дискретных каналов /ДДК/.

Ю. Основная теорема помехоустойчивого кодирования для ДИК.

11. Кера определенности числа множества действительных чисел ограниченного интервала, её свойства.

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

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

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

15. Пера относительного количества информации в числе множества; действительных чисел ограниченного интервала о числе другого аналогичного множества.

16. Девять типов детерминированных дискретно-непрерывных источников /ДДНИ/.

17. Математическое понятие "дискретно-непрерывный автомат с ограниченными алфавитами"

18. Числовое эффективное кодирование как способ уменьшения избыточности информации, выдаваемой ДЩШ.

19. Основная теорема числового эффективного кодирования для дда.

20. Восемь типов детерминированных дискретно-непрерывных каналов /ШШ/.

21. Математическое описание детерминированных независимых и зависимых аддитивных и мультипликативных помех, действующих в

ддак.

22. Класс числовых линейных блоковых корректирующих кодов, в которых элементами комбинаций являются конечные десятичные дробя.

23. 'Деры определенности функций, принадлежащих множествам периодических и непериодических функций как с ограниченными, так и неограниченными спектрами.

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

25. Меры относительной определенности периодической и. непериодической детерминированных функций с ограниченными и неограниченными спектрами, принадлежащих соответствующим множествам функций. ■

26. Меры количества информации в функциях множеств различных детерминированных функций.

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

28. Девять типов детерминированных непрерывных источников /ДНИ/.

29. Математическое понятие "непрерывный автомат с ограниченными непериодическими алфавитами".

30. функциональное эффективное кодирование как способ уменьшения избыточности информации, выдаваемой ДНИ.

31. Восемь типов детерминированных непрерывных каналов /ДЯК/.

32. Математическое описание детерминированных независимых и зависимых аддитивных и мультипликативных помех, действующих в ДНК.

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

- в -

34. Функциональное помехоустойчивое кодирование как. способ увеличения избыточности информации, выдаваемой ДНК.

Все перечисленные результаты получены лично автором.

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

1. Керы относительной определенности и количества информации в элементе конечного множества, их свойства.

2. Доказательство принципиального различия комбинаторной к вероятностной /К.Шеннона/ теорий информации..

3. Типы ДНИ и их математические модели.

4. Постановка задачи и теоремы об информационной способности ДЛИ.

5. Типы ДЕК и их математические модели.

Б. Основные теоремы эффективного и помехоустойчивого кодирования комбинаторной теории информации.

7. Меру определенности и количества информации в числе множества действительных чисел ограниченного интервала, их свойства.

8. Меры относительной определенности и количества информации в числе множества действительных чисел ограниченного интервала, их свойства.

9. Тили ДДВИ и их математические модели. Понятие дискретно-непрерывного автомата,

10. Числовое аффективное и помехоустойчивое кодирование -как способы изменения избыточности информации, выдаваемой ДДНИ.

11. Типы ДШК и их математические- модели.

12. Результаты анализа числовых детерминированных помех в ДДЕК.

13. Класс числовых линейных блоковых корректирующих кодов с конечными десятичными дробями в качестве элементов комбинаций.

14. Меры определенности и количества информации в функции множеств лериодических и непериодических функций с ограниченными и неограниченными спектрами, кх свойства. •

• 15. Меры относительной определенности и количества информации .».-функции множеств периодических и непериодических функций с. .ограниченными и неограниченными спектрами, их свойства.

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

17. Типы ДЦИ и их математические модели. Понятие непрерывного автомата.

- а -

18. Функциональное эффективное, я помехоустойчивое кодирование последовательности непериодических функций как способы изменения избыточности информация, выдаваемой ДНИ.

19. Типы ШК и их математические подели.

20. Результаты анализа функциональных детерминированных помех в ДНК.

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

Реализация результатов исследования. Результаты разработанной в диссертации комбинаторной теории информации использованы в различных курсах лекций в ряде ВУЗов России и ближнего зарубежья: в Уральском, политехническом институте в курсе лекций по дисциплине "Телемеханика"; в Московском горном институте^ курсах "Телемеханика" и "Телемеханика и связь"; в Новосибирском электротехническом институте в курсе "Телемеханика"; в Московском институте радиотехники, электроники а автоматики /ИИРЭА/ в курсах "Теория передачи информации", "Теория передачи цифровой информации", "Прикладная теория информации", "Телемеханика"; в

- 1С -

Куййыиевском политехническом институте в курсе "Телемеханика"; в Каунасском политехническом институте в курсе лекций "Прикладная теория информации'; в Львовском политехническом институте в курсах "Основы кибернетики" и "Основы теории систем"; в Киевском политехническом институте в курсе "Теория сигналов"; в Севастопольском приборостроительном институте в курсе "Телемеханика"; в Севанском политехническом институте в курсе лекций "Телемеханика; в Азербайджанским институте нефти и химии в курсе "Телемеханика"; в Казахском политехническом институте в курсе "Телемеханика". Работы по создании программных кодеров и декодеров числовых линейных корректирующих кодов ведутся на кафедре Автоматических систем КИРЭА.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на ежегодных Научно-техшческдх конференциях 1ИРЭА 1986-1991 г. и на научно-методических семинарах кафедры Автоматических систем ¡¿ИРЗА в лергсд 1984-1992 г.

Публикации. По результатам выполненных исследований автором опубликовано 22 работы, в том числе учебное пособие Гораинов О.А., Хохлов Г.И. Элементы теории информации и кодирования. -К.: МИРЗА, 19Б5.

Объем а структура диссертации. Диссертация состоит из введения, десяти глав, заключения, двух приложений и списка литературы из 48 наименований. Она содержит 479 с. машинописного текста, 44 рисунка и 10 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении обосновывается актуальность темы исследования и дается обшая характеристика диссертационной работы.

' В главе I проведен анализ основных теорий информации и сформулирована постановка задачи.

. Для установления философских взглядов и концепций, которые были положены автором в основу развиваемой в диссертации комбинаторной теории информации, дано определение информации. Это определение является развитием сформулированного в ряде работ определения А«Д.Урсуда к основывается на понятии множества и принципе отражения: информация - это отраженное в различии элементов одного множества различие элементов другого множества. Вид полу-

чаемой информации определяется тем видом различия элементов отразившего, множества, в котором запечатлелось различие элементов отраженного, множества.

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

Отмечено, что основных информационных процессов - шесть. Это - появление, преобразование, передача, переработка, хранение и отображение информации. Бели отбросить некоторые специфические особенности, то все шесть информационных процессов можно свести всего к двум принципиально различным - появлению и передаче. Появление информации всегда связано с наличием или действием некоторого объекта, который называют источником, передача обусловлена свойствами другого объекта /физической среды/, который называют каналом. Таким образом, источник и канал - это два основных информационных объекта, которые должны рассматриваться а любой теории информации.

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

Проведена классификация теорий информации. Сяя разделены на полные - неполные, формальные - неформальные, невероятностные - вероятностные. 3 свою очередь, в неформальных теориях выделены семантические, ценностные и прагматические теории.

Проведен краткий анализ формальных теорий информации: комбинаторной Р.Хартли, вероятностной К.Шеннона, алгоритмической А.Н.Колмогорова; установлены особенности, введенных в этих теориях мер количества информации для изучаемых в них форм её существования. Определена степень полноты каждой из этих теорий.

Выполнен краткий анализ неформальных теорий информации: семантических - Бар-Хиллела-Карнапа и В.А..трейдера, прагматических - А.А.Харкевяча и Р.Л.Стратоновича.

Отмечено, что окружающий нас мир состоит аз двух миров: случайных и детерминированных явлений. Эти явления переплетены и часто идут параллельно, взаимодействуя и изменяя друг друга.

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

Излагаемая теория информации, названная комбинаторной, является развитием и обобщением меры Р.Хартли. £ основу теории положен постулат, что информация есть отраженное различие, запечатленное в одной из форы и имеющее, определенный вид. При это;»: ке икегт существенного значения, как получен этот вид - детерми-нировннно или случайным образом. Главное, что информация представляет собой зафиксированную в различии элементов некоторого множества определенность элементов другого множества, и как определенность и должна исследоваться.

За общую, меру количества информации3 в комбинаторной теории принята величина

У =3) -Л)„ . А/

где 2) - исходная определенность элемента некоторого множества;

Э„ - определенность, потерянная в результате искажения исходных элементов множества.

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

В главе 2 вводятся меры количества информации в элементе конечного множества, исследуются их свойства.

Дня конечного множествах мощности 1X1 =К установлена мера определенности его элемента

• где а>1, /2/

совпадающая с .мерой количества информации Р.Хартли, указаны её свойства, /Основание логарифма й задает единицы, а которых исчисляется определенность./

Для конечного множествах"1^ последовательностей элементов

из П конечных множеств .....X« введена мера определенности

последовательности

ВОТ^Р . гдеа>1. Р ИХ""!. /3/

Отмечено, что свойства мера /3/ совпадают со свойствами меры количества информации в ограниченной последовательности, введенной Р.Хартли.

Для отображения £ :Х—У . задаваемого соответствием между конечными множествами X. и У . которое всюду определено, объективно и функционально, установлена мера 1){У]Х) относительной определенности, содержащейся в среднем а элементе множества У об элемент® множества X :

ОДС) = еодам /4/

где N =1X1 . М =М , ;

X; - подмножество множествах , являющееся прообразом элемента /] = 1,2,...,М /. Второй член в /4/ выражает потерю определенности 1)(5С)п элемента множествах в элементе множества У, вызванную не взаимно однозначным соответствием между элементами этих множеств. Показано, что 1ПГ,Х) зависит от М , М и отображения | •

Доказаны теоремы о минимальных и максимальных потерях определенности элемента множествах в элементе множестваУ , позволяющие найти границы интервала возможных значений. Кроме того, доказана теорема об оценке максимальных потерь определенности элемента множества X . дающая возможность оценить нижнюю границу интервала значений 1){УД) • В соответствии с указанными теоремами при условия, что N>14 >1, получим:, при N /М - нецелом

%М < ЖХЦ /5/

при /V /М - целом

Установлена

мера относительной определенности элемента декартова произведения П конечных множеств /I = 1,2,/

л/

где (^...Ып); —мощность прообраза (Х,х...*ХЯ); элемента 1/,-бУ

//-1.2.....М/. ' . V

Введена мера относительной определенности элемента конечного множествах в последовательности У11*' элементов П? конечных множеств Гг /1С = 1,2,... ,/П / при известных отображениях :Х~*"Ук » задаваемых соответствиями, которые всюду определены, сюръективны и функциональны, и /... £ :

ш I J

/е/

где Мх=|Ук1 1.2,...,Ш/; -

мощность подмножества ХдСХ , каждому из элементов которого отображение ставит в соответствие элемент

У;бУг //г= 1.2,...,Яг /. Найдены свойства ЭДУ^.Х] .

Доказана теорема, устанавливающая относительную определенность значений П переменных в значении логической функции "сложение по модулю 2", имеющая существенное значение для двоичных линейных кодов, в которых проверочные символы находятся как суммы по модулю 2 определенных информационных. Установлены меры: количества информации в элементе конечного множестваX

31Х) = 5(Х) = ; /9/

количества информации в последовательности элементов II конечных множеств Х< . • • • ,Х„

Ш'% Ш'"1) = /ю/

относительного количества информации в элементе конечного множестваУ об элементе конечнога множества X

ад = ых)-им, -ь^н /а/

относительного количества информации в элементе конечного множества Т об элементе декартова произведения X/. • .*ХП конечных множеств

где _ потери определенности элемента декартова »

произведения X/ • • .хХп в результате отображения его в множество У ;

относительного количества информации в последовательности Т^'элементов М конечных множеств^ /К= 1,2,...,/Л/ ш т 1 Мг

где ВЭДцк ~ потери определенности элемента множества X при отображении ^к:Х-*У|с /К = 1,2,...,ГП /.

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

Установлено различие развиваемой в настоящей диссертации комбинаторной и вероятностной /К.Шеннона/ теорий информации. На базе доказанной теоремы о непересечениа интервалов значений!1сог личеств информации в указанных теориях показано, что комбинаторная теория не является частным случаем вероятностной.

В главе 3 рассмотрены источники, выдающие информацию в виде элементов конечных множеств, установлены и исследованы их основные характеристики.

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

кого характера. .Источника с неслучайным характером выдачи аже-ментов названы детерминированными дискретными источниками /ДДИ/.

Введено в рассиотреняе девять типов ДЦИ: I/ нерегулярный с неограниченной /бесконечной/ памятью; 2/ нерегулярный с конечной памятью; Э/ невырожденный регулярный с. конечной памятью; 4/ вырожденный регулярный с конечной памятью; 5/ нерегулярный без памяти; £/ нерегулярный без памяти с регулярными входом и выходом; 7/ периодический; 8/ невырожденный регулярный без памяти; 9/ вырожденный регулярный без памяти. Показано, что их математическими моделями являются различные автоматы. Установлено, что к важнейшим типам ДНИ относятся: невырожденный регулярный с конечной памятью, периодический и невырожденный регулярный без памяти. Работа источников рассмотрена на примере функционирования конечного автомата, являющегося моделью невырожденного регулярного дди с конечно® памятью, с привлечением понятия "частное отображение". Частным отображением названо отображение входного алфавита в выходной при конкретном состоянии памяти автомата.

Доказана теорема о числе состояний памяти регулярного ДДК с конечной памятью.

Определено понятие "информационная способность ДНИ". Еад информационной способностью ДДИ понижается его способность выдавать разные выходные последовательности. Информационная способность ДДИ характеризуется функцией

дайны I элементов, которые могут появиться на выходе ДДИ.

Доказаны три теоремы, среди которых одна - основная, определяющие информационную способность невырожденного регулярного ДДИ с конечной памятью. В формулировки этих теорем входят поня-йя тривиального и нетривиального отображений: отображение д : ., в котором соответствие между конечными множествами А и & всюду определено ж 1АГ> I, а |В| = I, названо тривиальным; отображение, не являющееся тривиальным, названо"нетривиальным. Б формулировке и доказательстве основной теоремы использовано также понятие "граф переходов автомата".

Основная теорема для Д№

Для того чтобы при (-*-00 число выходных последовательностей

где

регулярного Щ с памятью ßt-*00 , необходимо, и'достаточно, чтобы в графе переходов автомата, представляющего данный источник: I/ содержался хотя бы один цикл длины L > 2;

2/ хотя бы одно из частных отображений х' • соответствующих вершинам цикла, была нетривиальным;

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

При доказательстве теоремы использованы три предварительно доказанные лешлы.

Приведены теоремы об информационной способности периодического ДШ и. невырожденного регулярного ДДИ без памяти.

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

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

Определено понятие избыточности информации, выдаваемой ДДЯ. Показано,, что у любого невырожденного регулярного !тта без памяти избыточность информации равна нулю. Понятие избыточности распространено на случай конечного отрезка последовательности, следующего после элемента с любкм номером. • i

Показано, что применяя различные способы кодирования отрезков последовательности невырожденного регулярного ДДИ с конечной памятью и периодического ДШ, избыточность выдаваемой 4ШИ~вдфор-мации может быть уменьшена или увеличена. Избыточность информации невырожденного регулярного ДЛИ без памяти может быть только увеличена. :

Доказана основная теорема, определяющая предельные возможности эффективного кодирования последовательности элементов ДЕК при использовании равномерных блоковых кодов.

Обозначим через количество информации, которое со-

держит отрезок длины Аб последовательности ДДИ, начинающийся с (1+ 1)~го элемента.

Основная теорема эффективного иодирования доя ДЮ Среди равномерных, блоковых кодов с основанием 0 , которыми кожио закодировать отрезок последовательности ДПК из элементов, начинающийся с (2+1)-го элемента, всегда существует такой, длина которого удовлетворяет неравенствам:

Для оценки степени уменьшения длины последовательности ДДК в результате эффективного кодирования предложено использовать понятие "коэффициент сжатия".

В главе 4 рассмотрены каналы, обеспечивающие передачу элементов конечных множеств, и их основные характеристики.

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

В рассмотрение введено восемь типов ДДК: I/ нерегулярный с неограниченной /бесконечной пакятью; 2/ нерегулярный с конечной памятью; 3/ регулярный с конечной памятью; 4/ нерегулярный без памяти; 5/ нерегулярный без памяти с регулярными входом и выходом; 6/ периодический; 7/ регулярный без памяти; 8/ регулярный С переменными состояниями. Установлено, что их математическими моделями являются различные автоматы. К важнейшим типа« ДДК отнесены: регулярный с конечной памятью,, периодический и регулярный без памяти, функционирование каналов показано на примере ра-.-йоты конечного автомата, представляющего регулярный ДДК с конечной памятью.

Определено понятие "количество информации в выходном символе ДДК". Показано, что количество информации в выходном символе зависит как от средней определенности символа входной последовательности канала, которая в конечном счете определяется свойствами источника, так и от потерь определенности символа в канале, которые определяются свойствами как источника, так и канала. Приведены два способа вычисления количества информации

в выходном символе. Наедено понятие максимального среднего количества информаши в выходном символе ДЩС.

, Установлена важнейшая характеристики ДЖ - скорость передачи информация:. Определение скорости передачи, выполнено дзумя способам® - на баз& понятия, "количество информации, в выходном символе: ДНК™ и на основа множегста виодных и выходных последовательностей, ДЩ. имеющих, доитатачна большую, но одинаковую длительность. ■: I

■Дано, определение пропускной способности ДШ£ как предельно достижимой а нем скороста передачи информации. Показано, что если: информация на входе ДДК представлена в безызбыточной форме, та вей она не может быть получена на его выходе.

Доказана основная в;. 0"р е * а. помехоустойчивого кодирования для ДЩС '

Вели производительность ДЖ С Д НК* где - пропу-

скная способность ДДК, то существует, такой способ кодирования, при котором вся информация* выдаваемая, источник см, будет передана па каналу со сколь угодно малыми потерями.

Если Сдщ> существует такой способ кодирования,

при котором потери информации, выдаваемой источником, будут меньше Удщ - С_щщ +£ . где £ сколь, угодно мало.

Не существует способа кодирования, при которем потеря информации, выдаваемой источником, меньше Здги ~Сщг-

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

Для множества действительных чиселХ ={ЗС} ограниченного интервала при максимальной абсолютной погрешности их ок-

ругления $ > О установлена, мера определенности числа данного множества:

])|(Х) =*0£„М /а>1/. ■ /16/

гдег N - количество чисел, различимых на интервале [0,6] . Округление чисел множества.^.с максимальной абсолютной погрешностью $ разбивает множество X на N непересекающихся подмножеств /I = 1,2,представляющих собой ^-окрестности чисел I; , образующих конечное множество чиселХ мощности |Х} = N •

Еыделенк три типичных расположения ^-окрестностей чисел 1£на отрезке 10-,6]. Мера /16/ названа ¿-определенностью числа множества X . определены свойства, этой меры..

Введена мера определенносхи последовательности чисел из Г? множеств . •.. действительных чисел ограничений интервалов при максимальных абсолютных погрешностях их округления соответственно ^>0.....Кц^-О:

/а>1/. /IV/

где Х1» - множество всех допустимых упорядоченных последовательностей чисел множествX,.•••X /З1 £лД..*Хй /; Рп - число последовательностей, различимых в множестве последовательностей Х'"^ после округления их чисел соответственно с погрешностями

___. Указаны свойства меры /17/.

Для отображения ■ задаваемого соответствием между

множествамиX и У действительных чисел ограниченных интервалов, которое всюду^определено, сюрьективно и функционально, установ- . /лена мера ) относительной определенности числа множества

X. содержащейся в числе множестваУ при максимальных абсолютных погрешностях округления чисел множеств соответственно £ и Л :

где N иМ - количество чисел, различимых в множествах X к V , соответственно;

Ц: - число (¡-окрестностей, покрывающих все отрезки действительных чисел, составляющих прообраз А -окрестности числа /^ =

= 1.2.....М /.

' _ Второй член в /18/^харакгеризует потерю определенности

числа множествах в числе множества ^ . Выявлены свойст-"2а меры /18/ в зависимости от количества чисел, различимых в указанных множествах, и характера отображения первого множества во второе.

Доказаны теоремы о максимальных и минимальных потерях определенности числа ыножестваХ в числе, множества1? , вызываемых не взаимно однозначным соответствием между этими множествами,^позволяющие найти границы интервала возможных значений Ь^4(У,Х) .

Помимо аюга, доказана теорема ой оцетде низшей границы интервала значазшй I)- (У,Х). На основании указанных теорем имеем; при Г<М<М

/19/

при к!^М

/20/

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

Установлена, мера относительной определенности элемента декартова произведения Л множествХ'\,/1 = 1,2,...,Г? / действитель- ' ных чисел ограниченных интервалов, содержащейся в числе ограниченного мнохест&а-Д чисел, для достаточно произвольного детерминированного отображения :

;: л /21/

где - число -окрестностей, покрывающих интервал действительных чисел множествах^//' = 1,2,...,/1 /;

- число . окрестностей, покрывающих все подобласти И -мерных действительных векторов, составляющих прообраз А -окрестности: числа ^бУ" / ] = 1,2.....М/. Введенная мера является

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

Введена мера относительной определенности числа множества действительных чидел X в последовательности У(Гп1 чисел из ¡7) ограниченных множеств?« /К = 1.2.....действительных чисел при.

разных отображениях :Х"*Ук : м

. где М^ - количество чисел, различимых, в множествеУк/К =1,2,-.ПУ, число ?-окрестнс£тей, -покрывающих все отрезки действительных. чисел, составляющих прообраз 4(-окрестности числа^- = = 1.2,..., М|с /. Установлены свойства, меры /22/.. ^

Введены меры:. ...___

количества информации в числе, множества действительных чисел ограниченного интервала: " • , -

ЗД)=])8(Х) «Ц'М : /23/

„ количества информации в последовательности чисел из П множеств действительных чисел ограниченных интервалов

......гЮ-ЩЛ-' ^4/

относительного количества информации1 в числе множества^" действительных чисел ограниченного интервала о числе йгобрагаемсга в него ограниченного множества, действительных чисел X

уудиД) •• /25/

отнссительнога количества информации в числе множества У действительных чисел огоаниченного интервала об элементе декартова • произведения ограниченных множеств, чисел

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

-пЦ^-Й^ХЦаЯ,;. к»

Понятия "избыточность цредставления" и "избыточность отображения информации, введенные для случая представления информации элементами конечных множеств, распространяются на случай,

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

В главе 6 рассмотрены источники, выдающие информацию в виде чисел множеств, действительных чисел ограниченных, интервалов, выявлены и исследованы их основные характеристики.

В излагаемой теории информации изучаются источники с неслучайным характером выдачи действительных чисел. Такие источники названы детерминированными дйскретао-негоерывнкми источниками. /ШШИ/. Величина интервала времени, через который источник выдз-ев очередное число, при общем рассмотрении несущественна; интерес представляют само- число и его номер в выдаваемой источнико.'/ последовательности.

Предложено девять тялоа ДЩШ: I/ нерегулярный с неограниченной /бесконечной/ памятью; 2/ нерегулярный с конечной памятью; 3/ невырожденный регулярный с конечной памятью; 4/ вырождении? регулярный с конечной памятью; 5/ нерегулярный без памяти; 6/ нерегулярный без памяти с регулярными входом и выходом; 7/ периодический; 8/ невырожденный'регулярный без памяти; 9/ вырожденный регулярный без памяти. Введено новое математическое понятие -дискретно-непрерывный автомат с ограниченными алфавитами. Показано, что адекватными математическими моделями ДПНИ являются различные дискретно-непрерывные автоматы с ограниченным континуальным входным алфавитом и конечными алфавитами: выходным и состояний. Установлено, что важнейшими типами ДШИ являются: неви-ровденный регулярный с конечной памятью, периодический и невырожденный регулярный без памяти. Действие источников показано на примере работы дискретно-непрерывного автомата, представляющего невырожденный регулярный ДШИ с конечной памятью.

Определено понятие "информационная способность ДДНК". Доказаны три теоремы, из которых одна - основная, устанавливающие информационную способность невырожденного регулярного ДШИ с конечной памятью. Доказательство основной теоремы базируется на трех предварительно сформулированных леммах.

Доказаны теоремы ой информационной способности' периодического ДДНИ иг невырожденного регулярного ДДВИ без памяти.:

Для всех типов ДДНИ получены выражения, определяющие количество информации в числе выдаваемых ими. последовательностей.

Дано определение производительности - основной характеристики ДДНИ. Производительность источника установлена двумя способами: с использованием количества информации в выходном числе' ДПШ и на основе; множества его выходных последовательностей, имеющих большую, но одинаковую длительность. Определена максимальная производительность ДЩШ. Найдено, что максимальная производительность периодического, и. невырожденного регулярного xnftff без. памяти совпадает с. ах производительностью.

Установлена ещё одна характеристика ДДНИ - избыточность выдаваемой ш информации. Формулы расчета избыточности получены для всех важнейших типов. ДПШ.

Показано, что адекватным приемом изменения избыточности информации, выдаваемой ДЩИ, является числовое кодирование. Суть числового блокового кодирования состоит в установлении взаимно однозначного соответствия между отрезками выходной последовательности ДДНИ .и некоторыми другими- ограниченными по длине последовательностями чисел. Установлена, что избыточность информация, выдаваемой всеми источниками, кроме невырожденного регулярного без памяти, может быть как уменьшена, так и увеличена. Избыточ- ' нооть информации последнего источника, может быть талыаа увеличена

Доказана теорема, определяющая предельные возможности, числового эффективного кодирования выходной последовательности чисел ДПШ при использовании равномерных числовых блоковых кодов /основная теорема числового эффективного кодирования/. В качестве показателя эффективности числового кодирования последовательности ДДЩ длины I при делении её на отрезки по it чисел предложено использовать коэффициент сжатия.

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

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

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

В результате проведенной классификации выявлено восемь типов ДДНК: I/ нерегулярный с неограниченной /бесконечной/ памятью; '2/ нерегулярный с конечной памятью; 3/ регулярный с конечной памятью; 4/ нерегулярный без памяти; 5/ нерегулярный без памяти'с регулярными входом и выходом; 6/ периодический; 7/ регулярный без памяти; Б/ регулярный с переменными состояниями. Показано, что их математическими моделями служат различные автоматы. Установлено, что важнейшими типами ДЩЖ являются: регулярный с конечной памятью, периодический, регулярный без памяти.

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

Установлено понятие "количество информации в выходном числе ДДНК". Найдено, что. количество информации в выходном числе зависит как от средней определенности числа последовательности на входе канала, которая в конечном счете определяется свойствами источника, так и от потерь определенности в канале при передаче одного числа, которые; определяются свойствами как источника, так и канала.. Даны два способа нахождения.количества информации в выходном числе. Установлена понятие максимального среднего количества информации в выходном числе ДДНК.

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

Установлена пропускная способность ДШК как предельно достижимая в нем скорость передачи информации.

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

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

К детерминированным функциям отнесены периодические и как-неограниченные, так и ограниченные во времени непериодические функции. На базе преобразования Фурье дано их частотное представление. В качестве основных форм представления выбраны:

для периодической действительной функции, времени |л(£) с периодом Т ряд Фурье в виде.

ю

Ш = с„ , /26/

где С0 - постоянная составляющая;

С^- амплитуда <Г-ой косинусоядальной функции;

2Й/Т - угловая частота повторения представляемой периодической функции;

начальная фазаК-ой косинусоядальной функции; для непериодической действительной функции времени ^{ЭД обратное преобразование. Фурье в вещественной форме

У«=Гс(и))С05[шЬ^)]аш, /29/

о

где СИ =-^с1(ы);

£|(и))и-у|Ц))- соответственно модуль и аргумент спектральной алотнсста ¿¡.(¿)) фу нкшш :

-¿ни) 00 —шЬ

= сЦи)е =]уь}е ¿ь. /го/

■-ее

И периодические, и непериодические функции разделены на два класса: с ограниченным и неограниченным спектром.

Дня бесконечного множества1^ ={|л!$} периодических функций с олнда. и тем же иериодомТ . удовлетворяющих условиям Дирихле и обладающих ограниченным спектром, при максимальных абсолютных погрешностях £<,> 0, £*> 0, б»> 0 округления соответственно постоянной составляющей, амплитуды я начальной фазы К-ой гармоники /К = 1,2,...,П ; П -номер высшей гармоники спектра/ установлена мера определенности периодической функции данного мнохе-ства: х-.

ДДе Ргпн - число функций с различающимися спектрами в множестве Рп п°сле округления с максимальными абсолютными погрешностями £« . С* .бк /К = 1,2,....Г? / постоянной составляющей, амплитуд и начальных фаз гармоник в представляютх их рядах Фурье.

Показано, что при конечных ЕоДк,5* А = 1,2,...,П / определенность периодической функции с ограниченным спектром, принадлежащей множеству рп , всегда конечна.

Для бесконечного множества Гц периодических функций

с одинаковым периодомТ , удовлетворяющих условиям Дирихле и обладающих неограниченным спектром, определенность функции определена так:

= V- ' /32/

где Роо - число функций о различающимися спектрами в множестве

, получаемых после округления с максимальными абсолютными' погрешностями £, /1С = 1,2,.../ постоянной составляющей, амп-лятуд и начальных фаз гармоник в рядах Фурьепредставляющих все функции множества Гп . ^_^ —,

Для бесконечного множества ^ ={|ц(Ь)} непериодических функций, каждая из которых удовлетворяет условиям Дирихле и имеет ограниченный .спектр, установлена следующая мера определенности функции:

где - число непериодических функций с различающимися спектрами в множестве:Тн после округления с погрешностями £ , С* и бц /К= 1,2,...,П / соответственно частот и удельных, весов амплитуд и начальных фаз гармонических составляющих спектров функций УцЮбТн /Г) - номер высшей различимой частотной составляющей спектра функции /.

Установлено, что при конечных Б ,£ю<5к /К = 1,2.....П / определенность непериодической функции с ограниченным спектром, принадлежащей множеству Гн , всегда конечна.

Для бесконечного множества Гц непериодических фун-

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

А,*.....(Ь) = ' /34/

■ - га-

где Рво - число функций а различающимися спектрами в множестве 1"н, получаемых после округления с максимальными абсолютными пог-рапностями 8 ,6к ибр /Ю= 1,2,.../ соответственно частот, удельных. весов амплитуд и начальных фаз гармонических, составляющих спектров функций §и(Ь)£Ри • Приведены свойства мер /31/-/34/.

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

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

Введена мера определенности последовательности функций из I множеств= 1,2.....1 / непериодических функций, существующих на интервалах длительности. Т< ,Тг,...,Те при условии, что

Т4 =Т2= ••• =Т[ =Т:

/35/

где Х(" - множество последовательностей из I непериодических функций множеств 5Сцд ;

=|Х<0| ; X?'' - конечное множество последовательностей, представляющих последовательности множества Х^'. при округлении частотных составляющих, входящих в них функций с. максимальными абсолютными погрешностями ,<3« .• • .6«> • • • "^М •

Найдены свойства меры /35/.

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

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

Так, например, еслиТп =\ЫЩ и1?п = {f„(t)} - бесконечные множества периодических функций с одним и тем же перводомТ, обладающих ограниченными и одинаково распложенными на оси частот спектрами, H!J:F„-*-(jn - отображение множества1^ в множество^, то средняя относительная оцределенность периодической функции |n(t). содержащаяся в периодической функции ^(t), определена так:

г-. ■]

где £о ,U ,...,£n i^n; tj,Tf,j)j ,...,tn,/>ц - максимальные абсолютные погрешности округления постоянной составляющей, амплитуд и начальньос.фаз гармоник рядов Фурье, представляющих все функции множеств Fn и£п соответственно;

и Q^ - числа функций с различающимися спектрами /после округления информационных параметров/ в множествах Fn и "Сц ;

Дгпнт ~ М?15Н0СТ:Ь прообраза ffl-ой /№= / функции

из конечного множества функций, получаемого из множества G„ в результате онругления информационных параметров. Найдены свойства всех введенных мер.

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

Определены меры количества информации: в функциях множеств периодических и непериодических функций с ограниченными и неог- . раниченными спектрами; в последовательности функций из{ множеств непериодических функций.

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

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

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

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

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

Непрерывным источником назван любой объект, действие которого приводит к.появлению последовательности функций от одной действительной переменной. В комбинаторной теории информации изучаются источники с неслучайным характером выдачи функций.. Такие источники названы детерминированными непрерывными источниками/ДНИ/.

Введено в рассмотрение девять типов ДОИ: I/ нерегулярный с неограниченной /бесконечной/ памятью; 2/ нерегулярный с конечной памятью; 2/ невырожденный ре1улярннй с конечной памятью; 4/ вырожденный регулярный с конечной памятью; о/ нерегулярный без памяти; 6/ нерегулярный без памяти с регулярными входом и выходок,-7/ периодический; 8/ невырожденный регулярный без памяти; 9/ вырожденный ре1улярный без памяти. При определении регулярных ДЩ было использовано понятие "трансляция множества функций на время',' означающее перенос множества функций на некоторый временной ян-

- ох -

тервал.

Установлено новое математическое понятие -'непрерывный автомат с ограниченными непериодическими алфавитами. Показано, что адекватными математическими моделями ДНИ служат различные непрерывные автоматы с ограниченным бесконечным входным алфавитов и конечными алфавитами: выходным и состояний. Отмечено, что в&-жнейшими типами ДНИ являются: невырожденный регулярный с конечной памятью, периодический и невырожденный регулярный без памяти. Принцип функционирования ЩИ проиллюстрирован работой непрерывного автомата, представляющего_невырожденный регулярный источник с конечной памятью.

Дано определение понятия "информационная способность ДНИ"." Приведены три теоремы, определяющие информационную способность невырожденного регулярного ЩИ с конечной памятью.

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

Получены выражения, определяющие для всех типов ДНИ количество информации, содержащееся в функции их выходных последовательностей.

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

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

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

мации, выдаваемой любым ДЭЙ, кроме невырожденного регулярного без памяти. У этого источника избыточность информации может быть только увеличена.

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

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

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

Считается, что любой ДВК характеризуется:

1. полосой пропускания [Ц, .(ад с шириной полосы (%-Шц ;

2. диапазонами значений входных функций 12 пня ,2тох] и выходных функций [Над Мтвж] ;

3. комплексным коэффициентом передачи

Ш =шеда /шекш,]/,

модуль которого 1С1и))=)Х1Ш)1 - амплитудно-частотная, а аргумент

- фазачастотная характеристики канала.

Исследовано восемь типов ДЗК: I/ нерегулярный с неограниченной /бесконечной/ памятью; 2/ нерегулярный с конечной памятью; 3/ регулярный с конечной памятью; 4/ нерегулярный без памяти; 5/ нерегулярный без памяти с регулярными входом и выходом; 6/ периодический; 7/ регулярный без памяти; 8/ регулярный с переменными состояниями. Установлено, что их математическими моделями являются различные конечные непрерывные автоматы с ограниченными непериодическими алфавитами. Выявлены важнейшие типы ЛНК - регулярный с конечной памятью, периодический и регулярный йез памяти.

Показано, что комплексный коэффициент передачи ДВК можно

рассматривать как сложную детерминированную помеху, приЕОдяиую к нелинейным искажениям передаваемых по каналу функций и вследствие этого к потере части информации в канале.

Дано описание детерминированных независимых и зависимых аддитивных и мультипликативных помех, характерных для ДНК. Установлено, что в общем случае действие названных помех не может Скть устранено^ приводит к потере в каналах части передаваемой по ним информации.

Определенно понятие "количество информации в выходной функции ДНК". Показано, что количество информации в выходной функции зависит от среднего количества информации во входной функции канала, которое в конечном счете определяется свойствами источнйкз,'

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

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

Дано определение пропускной способности ДНК как предельно достижимой в нем скорости передачи информации.

Доказана основная теорема функционального помехоустойчивого кодирования для ДЕК, устанавливающая величину потерь информации в канале при выдаче её детерминированным непрерывным источником.

В заключении сформулированы основные результаты работы.

В приложении I предложен класс числовых линейных, блоковых корректирующих кодов, элементами комбинаций которых являются, действительные числа, имеющие вид конечных десятичных дробей. Так;;е коды являются одним из способов числового кодирования, приводящим к увеличению избыточности информации, выдаваемой ДДЕК.

В приложении 2 приведено 12 актов об использованиеразрасо- . тайной комбинаторной теории информации.

ОСНОВНЫЕ РЕЗШЬТАТЫ РАБОТЫ.

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

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

в. среднем в событии одного из них о событии другого.

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

4. Как и в вероятностной теории, в информационной теории детерминированных процессов исследуются три формы представления информации: дискретная - виде элементов конечного множества, дискретно-непрерывная - в виде чисел множества действительных чисел ограниченного интервала и непрерывная - в:-виде функций множества детерминированных функций, но с неслучайным характером отношения элементов этих множеств..

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

-Зоны свойства всех введенных мер.

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

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

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

ДО ТВ® ДИССЕРТАЦИИ ОПУБДИКОВАНЫ СИЩСЩИЕ РАБОТЫ

Г. Горяинов: О.А. Дохлов Г.И. Элементы теории информации и кодирования. -М.: МИРЭА, 1985.

2. Хохлов Г.И. Относительная определенность и количество информации в элементе конечного множества./Методы моделирования, и управления в гибких автоматизированных производствах и системах автоматического управления: Межвуз. сб. науч. тр. -М.: МИРЭА, 1989.

3. Хохлов Г.И. Относительная определенность и количество информации об элементе декартова произведения конечных множеств. /Моделирование и экспертные системы: Межвуз. сб. нзуч. тр. -М.: МИРЭА, 1989.

4. Хохлов Г.И. Понятие избыточности в комбинаторной теории информации.. /Моделирование и управление в гибких автоматизиро-

ванных производствах и. системах автоматического управления: Нежвуз. сб. науч. тр. -М.: МИРЭЛ, 1990.

5. Хохлов Г.И. О различии комбинаторной я вероятностной Д. -Шеннона/ теорий информации./Электронная техника, сер. 10. Микроэлектронике устройства. 1991, вып. I.

6.. Хохлов Г.И. Детерминированные дискретные источники и их математические модели./Вопросы кибернетики. Устройства и системы: Межвуз. сб. науч. тр. -М.: МЙРЭА, 1989.

7. Хохлов Г.И. Информационная способность детерминированных, дискретных источников.Дульттшкропроцессорные информаци-онна-управляющие системы: Межауз. ей.науч. тр. -М.: ШРЭА, Г990.

8. Хохлов Г.И. Производительность а- максимальная производительность детерминированного дискретного источника./Вопросы кибернетики. Устройства и системы: Ке«шуз. сб. науч. тр. -И.: МНЕЗА, 1990. .

9. Хохлсв-Е.И. Основные теоремы кодирования комбинааорной теории информации./Электронная техника- сер. 10..Микроэлектронике устройства. 1991, вып. 2.

10. Хохлов-Г.И. Детерминированные дискретные каналы и их .математические; модели./Модели- к системы представления знаний: Межвуз. сб. науч.'тр. -М.: МЙРЭА, 1990.

11. Хохлов Г.И. Скорость передачи информации: ш детерминированному дискретному каналу и его пропускная способность./Электронная техника, сер. 10. Микроэлектронные устройства. 1991, вып. 2.

12. Хохлов Г.И. Определенность и количества информации в числе множества действительных чисел ограниченного интервала. /Электронная техника, сер. 10. Микроэлектронные устройства. 1991, вып. 4.

13. Хохлов Г.И. Относительная определенность и количество информации в числе множества действительных чисел ограниченного интервала./Электронная техника, сер. 10. Микроэлектронные устройства. 1991, внп. 4.

14. Хохлов Г.И. Относительная определенность аргумента в значении детерминированной функции./Электронная техника, сер. 10. Микроэлектронные устройства. 1991, вып. 5.

15. Хохлов Г.И. Относительная определенность и количество информации об элементе декартова произведения множеств дей-

ствителышх чисел ограниченных интервалов./Электронная техника, сер.10. Микроэлектронные устройства. 1991,вып.6.

16. Хохлов Г.И. Детерминированные дискретно-непрерывные источники и их математические модели./Многопозишояные радисси-сгемы: Межвуз. сб. науч. тр. -М.: МИРЭА, 1991.

17. Хохлов Г.И. Информационная способность детерминированных дискретно-непрерывных источников./Вопросы кибернетики. Устройства и системы: Межвуз. со. науч. тр.-М.:МИРЗА,1991.

18. Хохлов Г.И. Производительность и максимальная производительность 'детерминированных дискретно-непрерывных источников. /Вопросы кибернетики. Устройства и системы: Межвуз.-сб. науч. тр. -М.: МИРЭА, 1991.

19. Хохлов Г.И. Детерминированные дискретно-непрерывные каналы и их математические модели./Электронная техника, сер. 10. Микроэлектронные устройства. 1991, вып. 5.

20. Хохлов ГЛ. Помехи в детерминированных дискретно-непрерывных. каналах./Электронная техника, сер. 10. Ыикроэлектрон-ные устройства. 1992, вып. 1,2.

21. Хохлов Г.И. Числовые линейные блоковые корректирующие коды. /Электронная техника, сер. 10. Микроэлектронные устройства. 1991,- вып. 2.

22. Хохлов Г.И. Определенность и количество информации в функции множества детерминированных функций./Вопросы управления в сложных технических системах: Межвуз. сб. науч. тр. -К.: МИРЭА, 1992.

Лицензия * 020456 от 04.03.92.

Подписано в печать 15.04.94. Формат 60 х 84 1/16. Бумага писчая. Печать офсетная. Усл.сеч.л. 2,32. Усд.кр.-отт. 9,28. Уч.-изд.л. 2,5. Тираж 75 экз. Заказ 226. Бесплатно.

Московский Государственный институт радиотехники, электроники и автоматики ^технический университет) 117454 Москва, просп.Вернадского, 78

Введение

ГЛАВА I. АНАЛИЗ ТЕОРИЙ ИНФОРМАЦИИ И ПОСТАНОВКА ЗАДАЧИ

1.1. Определение информации

1.2. Формальные и неформальные теории информации

1.3. Анализ формальных теорий информации.

1.4. Анализ неформальных теарий информации

1.5. Постановка задачи

Выв о, д ы по I главе

ГЛАВА 2. ОПРЕДЕЛЕННОСТЬ И КОЛИЧЕСТВО ИНФОРМАЦИИ В ЭЛЕМЕНТЕ КОНЕЧНОГО МНОЖЕСТВА

2.1. Определенность элемента конечного множества

2.2. Определенность последовательности элементов П конечных множеств

2.3. Относительная определенность элемента, конечного множества:.

2.4. Относительная определенность элемента декартова произведения конечных множеств-.

2.5. Относительная определенность элемента конечного множества в. последовательности элементов ГП конечных множеств

2.6. Количество информации в элементе конечного множества.

2.7. Количество информации в последовательности элементов. П конечных множеств

2.8. Относительное количество информации в элементе конечного множества. 862.9. Относительное количество информации в последовательности элементов ГП конечных множеств

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

2.II. О различии комбинаторной и вероятностной /К.

Шеннона/ теорий информации

Выводы по 2 главе . ЮЗ

ГЛАВА 3. ДЕТЕРМИНИРОВАННЫЕ ДИСКРЕТНЫЕ ИСТОЧНИКИ.

3.1. Детерминированные дискретные источники и их математические модели

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

3.3. Количество информации в выходном элементе: детерминированного дискретного источника

3.4. Производительность и максимальная прожзвсдите>-льность детерминированного дискретного источника

3.5. Избыточность информации детерминированного: дискретного источника.

3.6. Кодирование последовательности элементов детерминированного дискретного источника

3.7. Эффективное кодирование последовательности элементов детерминированного дискретного источника

В ы В: о д ы по 3 главе

ГЛАВА 4. ДЕТЕРМИНИРОВАННЫЕ ДИСКРЕТНЫЕ КАНАЛЫ.

4.1. Детерминированные дискретные каналы и их математические модели

4.2. Количество информации в выходном символе детерминированного дискретного канала

4.3. Скорость передачи информации по детерминированному дискретному каналу

4.4. Пропускная способность детерминированного дискретного канала

4.5. Помехоустойчивое кодирование последовательности элементов детерминированного дискретного источника

Выводы по 4 главе

ГЛАВА 5. О НЕ ЩШ ЕМКОСТЬ И КОЛИЧЕСТВО ИНФОРМАЦИИ В ЧИСЛЕ МНОЖЕСТВА ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ ОГРАНИЧЕННОГО ИНТЕРВАЛА

5.1. Определенность числа множества действительных ;яисел ограниченного интервала

5.2. Определенность последовательности чисел из П множеств действительных чисел ограниченных интервалов

5.3. Относительная определенность числа множества действительных чисел ограниченного интервала

5.4. Относительная определенность элемента декартова произведения множеств: действительных чисел ограниченных интервалов

5.5. Относительная определенность числа множества де> йствительных чисел в последовательности элементов из 1П множеств действительных чисел ограниченных интервалов

5.6. Количество информации! в числе множества действительных чисел ограниченного интервала

5.7. Количество информации в последовательности чисел из Г) множеств действительных чисел ограниченных интефвалов

5.8. Относительное количество информации в числе мног-жества действительных чисел ограниченного интервала

5.9. Относительное: количество информации в последовательности чисел из 177 множеств действительных чисел ограниченных интервалов

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

В ы в о. д ы по 5 главе.

ГЛАВА 6. ДЕТЕРМИНИРОВАННЫЕ ДИСКРЕТНО-НЕПРЕРЫВНЫЕ ИСТОЧНИКИ

6.1. Детерминированные дискретно-непрерывные источники и их математические модели

6.2. Информационная способность детерминированных дискретно-непрерывных источников

6.3. Количество информации в выходном числе детерминированного дискретно-непрерывного источника

6.4. Пр ои зв о ди т.ел ьн о с ть и максимальная производительность детерминированного, дискретно-непрерывного источника.

6.5. Избыточность информации детерминированного дискретно-непрерывного источника.

6.6. Числовое- эффективное кодирование последовательности чисел детерминированного дискретно-непрерывного источника.

В ы в. о, д ы по 6: главе.

ГЛАВА 7. ДЕТЕРМИНИРОВАННЫЕ ДИСКРЕТНО-НЕПРЕРЫВНЫЕ КАНАЛЫ.

7.1. Детерминированные дискретно-непрерывные каналы и их математические модели

7.2. Помехи в детерминированных дискретно-непрерывных каналах

7.3. Количество информации в выходном числе детерминированного дискретно-непрерывного канала

7.4. Скорость передачи информации по детерминированному дискретно-непрерывному каналу

7.5. Пропускная способность детерминированного дискретно-непрерывного канала

7.6. Числовое помехоустойчивое кодирование последовательности чисел детерминированного дискретно-непрерывного источника

В ы ж о д ы по 7 главе

ГЛАВА 8. ОПРЕДЕЛЕННОСТЬ И КОЛИЧЕСТВО ИНФОРМАЦИИ В ФУНКЦИИ

МНОЖЕСТВА ДЕТЕРМИНИРОВАННЫХ ФУНКЦИЙ.

8.1. Детерминированные функции из их частотное представление;

8.2. Определенность функции множества детерминированных функций.

8.3. Определенность последовательности функций из t множеств непериодических функций

8.4. Относительная определенность функции множества детерминированных функций

8.5. Относительная определенность элемента декартова произведении множеств детерминированных функций

8.6'. Количество информации в функции множества детерминированных функций.

8.7. Количество информации в последовательности функций из I множеств непериодических функций . 396.

8.8. Относительное количество информации в функции множества детерминированных функций

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

8.10. Эффективное и, помехоустойчивое кодирование детерминированных функций.

В ИЕадн по 8 глав®.

ЕЛ ABA 9. ДЕТЕРМИНИРОВАННЫЕ НЕПРЕРЫВНЫЕ; ИСТОЧНИКИ.

9.1. Детерминированные непрерывные источники и их математические модели.

9.2. Информационная способность детерминированных непрерывных источников:.

9.3. Количество информации в. выходной функции детерминированного непрерывного источника.

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

9.5. Избыточность информации детерминированного непрерывного источника

9.6. Функциональное эффективное; кодирование последа-вательности функций детерминированного непрерывного источника.

В ы В: о д ы по 9 главе

ГЛАВА 10. ДЕТЕРМИНИРОВАННЫЕ НЕПРЕРЫВНЫЕ: КАНАЛЫ.

10.1. Детерминированные непрерывные каналы и их математические модели

10.2. Помехи в детерминированных непрерывных каналах

10.3. Количество информации в выходной функции детерминированного непрерывного канала

10.4. Скорость передачи информации: по детерминированному непрерывному каналу

10.5. Пропускная способность детерминированного непрерывного канала.

10.6. Функциональное помехоустойчивое: кодирование последовательности функций детерминированного непрерывного источника

Выводы по 10 главе:.

Актуальность проблемы. Теоретическим базисом различных информационных устройств и систем является теория информации, изучающая процессы появления, преобразования, передачи, переработки, хранения и отображения информации. В настоящее время теория информации представляет ©обой совокупность отдельных частных теорий, описывающих разные; формы существования информации с учетом или без учета критериев оценки её получателем. Центральное место среди частных теорий информации занимает формальная вероятностная теория К.Шеннона, исследующая информацию в виде случайных событий, значений случайных величин и реализаций случайных функций. Математическим аппаратом этой теории служит теория вероятностей.

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

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

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

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

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

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

Задачи исследования. I. Установить меру количества информации в элементе конечного множества, исследовать её свойства.

2. Рассмотреть источники, выдающие: информацию в виде элементов конечного множества, установить и проанализировать их основные: характеристики. Исследовать процесс генерации информации в данной форме.

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

4. Установить меру количества информации в числе множества действительных чисел ограниченного интервала, исследовать её свойства.

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

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

7. Установить меру количества информации в функции множества детерминированных функций, исследовать её свойства.

8. Рассмотреть источники, выдающие информацию в виде действительных функций множества детерминированных функций, установить и проанализировать их основные характеристики. Исследовать процесс генерации информации в указанной форме.

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

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

Научная новизна результатов. Все результаты диссертационной работы, за исключением приведенных в гл. I и п.п. 2.1, 2.2, 2.6, 2.7, являются новыми. К наиболее существенным новым научным результатам относятся:

1. Мера относительной определенности элемента одного конечного множества в элементе другого конечного множества при всюду определенном, сюръективном и функциональном отображении первого множества во второе.

2. Теоремы о минимальных и максимальных потерях определенности элемента одного множества в элементе другого множества, вызванных не взаимно однозначным соответствием между этими множествами, и теорема об оценке максимальных потерь определенности элемента отображаемого множества.

3. Меры относительной определенности элемента декартова произведения конечного числа конечных множеств и относительной определенности элемента конечного множества в последовательности элементов нескольких конечных множеств.

4. Мера относительного количества информации в элементе конечного множества.

5. Доказательство утверждения, что развиваемая в настоящей работа комбинаторная теория информации не является частным случаем вероятностной теории К.Шеннона.

6. Девять типов детерминированных дискретных истолников /ДДИ/.

7. Постановка задачи и теоремы об информационной способности невырожденного регулярного ДЦИ с конечной памятью, периодического ДЩ и невырожденного регулярного ДДИ без памяти.

8. Основная теорема эффективного кодирования для ДДИ.

9. Восемь типов детерминированных дискретных каналов /ДДК/.

10. Основная теорема помехоустойчивого кодирования для ДДК.

11. Мера определенности числа множества действительных чисел ограниченного интервала, её свойства.

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

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

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

15. Мера относительного количества информации в числе множества действительных чисел ограниченного интервала о числе; другого аналогичного множества.

16. Девять типов детерминированных дискретно-непрерывных источников /ДДНИ/.

17. Математическое понятие "дискретно-непрерывный автомат с ограниченными алфавитами".

18. Числовое эффективное кодирование как способ уменьшения избыточности информации!, выдаваемой ДЦЙ0.

19. Основная теорема числового эффективного, кодирования для ДДНЙ.

20. Восемь типов детерминированных дискретно-непрерывных каналов /ДЩК/.

21. Математическое описание детерминированных независимых и зависимых аддитивных и мультипликативных помех, действующих в дда.

22. Класс; числовых линежных блоковых корректирующих кодов, в которых элементами комбинаций являются конечные десятичные дроби.

23. Меры определенности функций, принадлежащих множествам периодических и непериодических функций как с ограниченными, так и неограниченными спектрами.

24. Теоремы о конечной определенности периодической и непериодической функции, принадлежащей соответственно множеству абсолютно интегрируемых на периоде периодических функций с неограниченным спектром и множеству абсолютно интегрируемых на всей временной оси непериодических функций с неограниченным спектром.

25. Меры относительной оцределенности периодической и непериодической детерминированных функций с ограниченными и неограниченными спектрами, принадлежащих соответствующим множествам функций.

26. Меры количества информации в функциях множеств различных детерминированных функций.

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

28. Девять типов детерминированных непрерывных источников /ДНИ/.

29. Математическое понятие "непрерывный автомат с ограниченными не периодическими алфавитами".

30. Функциональное эффективное: кодирование- как способ уменьшения избыточности информации:, выдаваемой ДНИ.

31. Восемь типов детерминированных непрерывных каналов /ДНК/.

32. Математическое описание детерминированных независимых и зависимых аддитивных и мультипликативных помех, действующих в ДНК.

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

34. Функциональное помехоустойчивое кодирование как способ увеличения избыточности информации, выдаваемой ДНИ.

Все перечисленные результаты получены лично автором.

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

1. Меры относительной олределенности и количества информации в элементе конечного множества, их свойства.

2. Доказательство принципиального различия комбинаторной и вероятностной /К.Шеннона/ теорий информации.

3. Типы ДДИ и их математические модели.

4. Постановка задачи и теоремы об информационной способности дци.

- 14

5. Типы ДЦК и их математические:модели.

6. Основные теоремы эффективного и помехоустойчивого кодирования комбинаторной теории информации.

7. Меры определенности и количества информации в числе множества дейстаительных чисел ограниченного интервала, их свойства.

8. Меры относительной определенности и количества информации в числе множества действительных чисел ограниченного интервала, их свойства.

9. Типы ДДНИ и их математические модели. Понятие:дискретно-непрерывного автомата.

10. Числовое эффективное и помехоу стойчивое кодирование как способы изменения избыточности информации, выдаваемой ДДНИ.

11. Типы ДДНК и их математические модели.

12. Результаты анализа числовых детерминированных помех в ДДНК.

13. Класс, числовых линейных блоковых корректирующих кодов с конечными десятичными дробями в качестве элементов комбинаций.

14. Меры определенности и количества информации в функции множеств/периодических и непериодических функций с ограниченными и неограниченными спектрами, их свойства.

15. Меры относительной определенности и количества информации в функции множеств периодических и непериодических функций с ограниченными; и неограниченными спектрами, их свойства.

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

17. Типы ДНИ и их математические модели. Понятие непрерывного, автомата.

Г8. Функциональное эффективное и помехоустойчивое кодирование

- is: последовательности непериодических функций как способы изменения избыточности информации, выдаваемой ДНИ.

19. Типы ДЕК и их математические модели.

20. Результаты анализа функциональных детерминированных помех в ДНК.

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

Реализация результатов исследования. Результаты разработанной в диссертации комбинаторной теории информации использованы в различных курсах лекций в ряде ВУЗов России и ближнего зарубежья: в Уральском политехническом институте в курсе лекций по дисциплине, "Телемеханика"; в. Московском горном институте в курсах "Телемеханика" и "Телемеханика и связь"; в Новосибирском электротехническом институте в курсе "Телемеханика"; в Московском институте радиотехники, электроники и автоматики /МИРЭА/ в курсах "Теория передачи информации", "Теория передачи цифровой информации'', "Прикладная теория информации", "Телемеханика"; в Куйбышевском политехническом институте в курсе "Телемеханика"; в Каунасском политехническом институте в курсе лекций "Прикладная теория информации"; в Львовском политехническом институте в курсах "Основы кибернетики" и "Основы теории систем"; в Киевском политехническом институте в курсе "Теория сигналов"; в Севастопольском приборостроительном институте в курсе "Телемеханика"; в Ереванском политехническом институте в курсе лекций "Телемеханика"; в Азербайджанском институте нефти и химии в курсе "Телемеханика"; в Казахском политехническом институте в курсе "Телемеханика". Работы по созданию программных кодеров и декодеров числовых линейных корректирующих кодов ведутся на кафедре Автоматических систем МИРЭА.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на ежегодных- Научно-технических конференциях МИРЭА I988-I99I г. и на научно-методических семинарах кафедры Автоматических систем МИРЭА в период 1984-1992 г.

Публикации. ПЬ результатам выполненных исследований автором опубликовано 22 работы, в том числе учебное пособие Горяинов 0.А.,Хохлов Г.И. Элементы теории информации и кодирования. -М.: МИРЭА, 1985.

Объем и структура диссертации. Диссертация состоит из введения, десяти глав, заключения, двух приложений и списка литературы из 48 наименований. Она содержит 479 с. машинописного текста, 44 рисунка и 10 таблиц.

Выводы по 2 главе

1. Для конечного множества установлена мера определенности его элемента, совпадающая с мерой количества информации Р.Хартли.

2. Для конечного множества последовательностей элементов из П конечных множеств введена мера определенности последовательности и указаны её. свойства. Эти свойства совпадают со свойствами меры количества информации в ограниченной последовательности, введенной Р.Хартли.

3. Для отображения f'X—Y , задаваемого соответствием между конечными множествамиX иY , которое всюду определено, сюръ-ективно и функционально, установлена MepaD(Y,X) относительной определенности, содержащейся в среднем в элементе множестваY об элементе множестваХ • Показано, 4to])(Y,X) зависит от мощностей множеств X иУ и отображения |'.X~*Y .

4. Доказаны теоремы о минимальных и максимальных потерях определенности элемента множестваХ в элементе множества Y » вызываемых не взаимно однозначным соответствием между элементами этих множеств, позволяющие найти границы интервала возможных значений D(Y,X) . Кроме того, доказана теорема об оценке максимальных потерь определенности элемента множестваХ t дающая возможность оценить нижнюю границу интервала значений I(Y,X) .

5. Установлена мера относительной определенности элемента декартова произведения конечных множеств.

6. Введена мера относительной определенности элемента конечного множества в последовательности элементов 17) конечных множеств и установлены её свойства.

7. Доказана теорема, устанавливающая относительную определенность значений П переменных в значении логической функции "сложение по модулю 2", имеющая существенное значение для линейных кодов, в которых проверочные символы находятся как суммы по модулю 2 определенных информационных.

8. Установлены меры количества информации в элементе конечного множества, в последовательности элементов П конечных множеств и меры относительного количества информации в элементе конечного множества, в последовательности элементов 17] конечных множеств.

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

10. Установлено различие развиваемой в настоящей работе комбинаторной и вероятностной /К.Шеннона/ теорий информации;. Доказано, что комбинаторная теория не является частным случаем вероятностной.

- 105

1. Если у ДДИ с конечной памятью VC == 1,2,. Х^=Х ={Xj/ii,2.H/,ArA /ft- i.2.1С/ и значение элемента

2. Из отображений /3.1/ и /3.3/ в качестве частных случаев могут быть получены отображения, описывающие более простые ДДИ. Так, если в отображении /3.3/ мощность множества альтернативных условийX = I, то оно вырождается в отображение:1. Х'-Х'^Х. /з.4/

3. При Х{ =Х и А^А VI = 1,2,. источник, задаваемый правой частью /3.5/, является нерегулярным ДЛИ без памяти с регулярными входом и выходом.

4. Если в отображении, стоящем в правой части /3.7/, множество условий А А. , где А - множество мощности |А| = I, т.е. если- 108 источник характеризуется отображением3.8/то такой источник назовем вырожденным регулярным ДШ без памяти.

5. Охарактеризуем подробнее автоматы, являющиеся математическими моделями ДЩ. Структурные особенности этих автоматов приведены на рис. 3.1.

6. FеЛ(Ы~Ч-^(е"н1) и ЕЫХ0Д0ЕаБТ0мата также нерегулярны.

7. Нерегулярный ДЩ. без памяти, с регулярными входом и выходом имеет своей математической моделью нерегулярный автомат без памяти И* ={Л,ХЛИ 1,2,./ /рис. 3.1,г/ с регулярными входным и выходным алфавитами, но нерегулярными функциями выходов

8. Математической моделью периодического ДДИ является автоматбез памяти И€ ЦЛД^Щ/g = 1,2,./ /рис. 3.1,д/ с периодическими /с периодом ^ / функциями выходов =где ГП * 1,2.- номер элемента в периоде. Числа I , ) и

9. ГО связаны равенством I И($-1)+ГП /5 = 1,2,. номер периода/.

10. Для невырожденного регулярного ДДИ без памяти математическая модель представляет собой автомат без памяти И = {A,X,Vj /рис. 3.1,з/ с регулярными входным, выходным алфавитами и неизменной функцией выходов У •

11. Поскольку в момент поступления на вход автомата условия^ его память находится в состоянии 0.00 , то при этом состоянии отображение Тп представляет собой по существу отображение1. X)/3'9/гдеХ^ 0 подмножество множества содержащее; только элемент 0 . .00 ;

12. Xj|0 ф выходной алфавит автомата при состоянии его памяти

13. Отображение^ <*Л~*Х назовем частным отображением отобра-женин^М ^

14. После выдачи П -го элемента вся память автомата будет заполнена, и значение каждого последующего элемента будет определяться подаваемым на вход автомата условием Л /1^= 1,2,.К;t>n / и состоянием его памяти / Xj .Xj,€X/«

15. Множество возможных состояний памяти XjX2'. .Х'п обозначим Х^ • Отображение, определяющее выходной элемент с номеромавтомата, является частным отображением вида:/3*12/vM vfn)гдел^ ji подмножество множества \ , содержащее только элемент 0С!|. Хр ;

16. Хп+1|х;. ^ выходной алфавит автомата при состоянии его памяти Х{.Х'П ,Х^фл j/pC и U{Xn+i|xJ эр^X • Таких част~ ных отображений у отображения IX^I^N^

17. Множество состояний памяти автомата вида ф . Х^. /d = 0,1,.,И / в общем случае обозначим Часть отображения *Уп , представляющую отображение X2U-X , обозначим ТМ :

18. Использование введенных понятий и обозначений рассмотрим на примерах.1. Пример 3.1

19. Пусть периодический ДЩ имеет период = 3 и задается табл. 3,1 отображений Н^ /ГП= 1,2,3; ^ =У3 /, графы которых приведены на рис:. 3.3,а. Построить граф последовательностей, которые может выдавать источник.

20. Пусть Xs {0,1} выходной алфавит невырожденного регулярного ДП.и без памяти, а Л = - множество альтернативных