Комбинаторная теория информации: Информ. теория детерминирован. процессов тема диссертации и автореферата по ВАК РФ 05.13.01, доктор технических наук Хохлов, Г. И.

• Хохлов, Г. И.
• доктор технических наук
• 1994

Оглавление диссертации доктор технических наук Хохлов, Г. И.

Введение

ГЛАВА 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

Список литературы диссертационного исследования доктор технических наук Хохлов, Г. И., 1994 год

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} выходной алфавит невырожденного регулярного ДП.и без памяти, а Л = - множество альтернативных