По и. Прикладнаятеорияинформации
 Скачать 377.21 Kb.
|
|
2 МИНИСТЕРСТВООБРАЗОВАНИЯИНАУКИРОССИЙСКОЙ ФЕДЕРАЦИИ САНКТ-ПЕТЕРБУРГСКИЙНАЦИОНАЛЬНЫЙИССЛЕДОВАТЕЛЬСКИЙУНИВЕРСИТЕТ ИНФОРМАЦИОННЫХТЕХНОЛОГИЙ, МЕХАНИКИИОПТИКИ А.В.Ушаков ПРИКЛАДНАЯТЕОРИЯИНФОРМАЦИИ: элементытеорииипрактикум Учебное пособие Санкт-Петербург 2012 3 УДК [517.938 + 519.713 / .718]:62.52: 621.398 Ушаков А.В. Прикладная теория информации: элементы теории и практикум: Учебное пособие для вузов. – СПБ.: СПбНИУИТМО, 2010.–325с.: ил. 36. В пособии изложены в сжатой форме основные положения учебной дисциплины «Прикладная теория информации» цикла специальных дисциплин образовательного стандарта направления 220200 – «Автоматизация и управление» подготовки бакалавров и магистров и специальности 220201 – «Управление и информатика в технических системах» подготовки специалистов – инженеров, достаточные для освоения теоретического материала дисциплины и проведения практикума по ней. Учебное пособие предназначено для студентов, однако оно может быть рекомендовано также аспирантам и молодым специалистам, которым по роду своей деятельности приходится иметь дело с проблемами канализации информации, обеспечения её помехозащиты при передаче и хранении, а также разработки устройств дискретной автоматики и функционального преобразования кодов. Рецензенты: д.т.н., профессор В.Н.Дроздов; д.т.н., профессор А.А.Шалыто. Рекомендовано к печати Ученым советом факультета компъютерных технологий и управления, протокол № 6 от 14.02.2012 В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования «Санкт- Петербургский государственный университет информационных технологий, механики и оптики» на 2009–2018 годы. Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2012 Ушаков А.В.2012 4 СОДЕРЖАНИЕ Предисловие 7 Используемые обозначения и сокращения 10 Введение. Прикладная информатика в общей проблематике управления 14 0. Основные понятия и определения 21 1. Количественные меры информации. Характеристики источника информации 28 1.1 Структурные меры количества информации 29 1.2 Вероятностная мера количества информации К.Шеннона 33 2. Передача информации по каналам связи 48 2.1 Передача информации по каналам связи без помех 51 2.2 Передача информации по каналам связи с помехами 54 3. Основные задачи кодирования информации 61 4. Эффективное кодирование 69 4.1 Объем сигнала и емкость канала связи, условия их согласования 69 4.2 Алгоритм эффективного кодирования К.Шеннона – Р.Фэно 71 4.3 Алгоритм эффективного кодирования Д.Хаффмена 78 5. Помехозащитное кодирование 85 5.1 Формирование базовых параметров систематического помехозащищенного кода 85 5.2 Матричное представление помехозащитного преобразования кодов. Конструирование матриц систематических помехозащищенных кодов 91 5.3 Представление помехозащитного преобразования кодов на основе действий с модулярными многочленами. Выбор образующего модулярного многочлена кода 107 5.4 Связь корректирующей способности кода с кодовым расстоянием, экспресс – оценки корректирующей способности помехозащищенного кода 120 Преобразование кодов с помощью линейных двоичных динамических систем (ЛДДС) 129 6. 6.1 Аппарат передаточных функций в задаче модельного представления линейных двоичных динамических систем 129 5 6.2 Векторно - матричное модельное представление линейных двоичных динамических систем, свойства квадратных матриц над двоичным конечным полем Галуа 139 6.3 Линейные двоичные динамические системы в задачах рекуррентного помехозащитного кодирования и декодирования 152 Концепция подобия в теории линейных двоичных динамических систем 168 6.4.1 Концепция подобия в задаче двоичного динамического наблюдения состояния ЛДДС 170 6.4.2 Процесс помехозащитного декодирования как процесс двоичного динамического наблюдения состояния двоичного канала связи 176 6.4 6.4.3 Синтез двоичных динамических систем в логике произвольных линейных триггеров на базе концепции подобия 180 Преобразование кодов с помощью нелинейных двоичных динамических систем (конечных автоматов) 188 7.1 Канонический алгоритм синтеза конечного автомата (КА). Автоматные логики Мура и Мили 188 7.2 Аналитические описание комбинационных схем КА. Булевы функции и их свойства, базисы представления, дизъюнктивные совершенные нормальные формы (ДСНФ) и конъюнктивные совершенные нормальные формы (КСНФ), проблема редуцирования аналитического представления переключательных функций. Булевы производные булевых функций, области применения 198 7.3 Триггеры: функции перехода и функции возбуждения входов триггеров 221 7. 7.4 Реализация рекуррентных устройств помехозащитного кодирования и декодирования в логике произвольных триггеров 225 7.5 Синтез конечных автоматов на основе граф – схем алгоритмов функционирования устройств дискретной автоматики 230 8. Конечные цепи А. Маркова в моделировании двоичных каналов связи 242 8.1 Элементы теории конечных цепей Маркова 243 8.2 Моделирование двоичных каналов связи с помощью конечных цепей Маркова 254 6 9. Спектры передаваемых по каналам связи непрерывных сигналов 261 9.1 Спектры немодулированных одиночных сигналов и импульсных (кодовых) последовательностей 261 9.2 Спектры модулированных и демодулированных сигналов 266 10. Дискретное представление непрерывных сигналов. Базисные функции. Теорема В.Котельникова – К.Шеннона. 275 10.1 Прямая задача дискретного представления непрерывных сигналов. Матрица Грама. Базисные функции 275 10.2 Обратная задача дискретного представления непрерывных сигналов. Теорема В.Котельникова – К.Шеннона 279 Заключение 287 Литература 288 Приложения 1: Таблица неприводимых модулярных мно- гочленов 292 Приложения 2: D -преобразование двоичных последователь– ностей 298 Приложение 3: Коды, используемые в современных телекоммуникационных системах 304 Приложения 4: Выдержки из ГОСТ 26.205 – 88 Комплексы и устройства телемеханики 305 Из истории лаборатории технической информатики и телемеханики кафедры СУИ 318 Об авторе 325 7 Посвящается Лидии Тимофеевне Никифоровой, вовлекшей автора в прикладную теорию информации ПРЕДИСЛОВИЕ Дисциплина «Прикладная теория информации (ПТИ)» к настоящему моменту имеет следующую предысторию. Первоначально в учебных планах подготовки инженеров – электриков по специальности 0606 – «автоматика и телемеханика» в 70-е годы XX-го века появилась дисциплина «Математические основы кибернетики (МОК)», составным компонентом в которую входили вопросы, связанные с прикладной теорией информации и проблемами ее канализации в каналах передачи и хранения. К концу 70-х годов XX-го века название дисциплины претерпевает первое изменение, в результате чего она стала называться «Теоретическими основами кибернетики (ТОК)», при этом информационный и канальный модуль был сохранен в новой дисциплине как составной компонент. Введенная в учебный план специальности 0606 дисциплина как в версии МОК, так и в версии ТОК в основном решала задачи математического обеспечения модельных представлений процессов управления и информационных процессов в канальных средах. В конце 80-х годов XX-го века дисциплина претерпевает очередное изменение названия, в результате чего она начинает называться «Математическими основами исследования процессов управления (МОИПУ)». Из программы дисциплины МОИПУ изымаются положения, связанные с информационными процессами в канальных средах, которые переносятся в программу появившейся в учебном плане специальности дисциплины «Прикладная теория информации (ПТИ)». С этого момента дисциплина «Прикладная теория информации » в учебном плане подготовки инженеров – электриков по специальности «автоматика и телемеханика» живет и развивается самостоятельно по естественным законам диалектики. Последняя модификация учебного процесса произошла в начале 90- х годов XX-го века, которая сопровождалась одновременными изменениями номера и названия специальности инженерной подготовки так, что выпускники вузов по данной специальности стали получать квалификацию инженера по специальности 210100 (ныне 220201) – «управление и информатика в технических системах». С середины 90-х годов XX-го века дисциплина ПТИ вошла также в структуру учебного плана по разделу специальных дисциплин 8 образовательного стандарта направления 651900 (ныне 220201) – «Автоматизация и управление» подготовки бакалавров и магистров. Таким образом, предлагаемое учебное пособие подготовлено на основе опыта преподавания дисциплин МОК, ТОК и «Прикладная теория информации (ПТИ)», накопленного на кафедре Систем управления и информатики (до 2001-го года кафедре автоматики и телемеханики) Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики. До 2002 – го года дисциплина «Прикладная теория информации» составляла с дисциплиной «Телемеханика» единый методологический и проблемный образовательный модуль, на который возлагалась подготовка выпускников кафедры по вопросам дистанционного управления техническими объектами и технологическими ресурсами на основе использования возможностей агрегативных средств систем телемеханики (АССТ), представлявших собой телемеханическую технику четвертого поколения. С 2002 – го года в учебных планах подготовки специалистов по специальности 220201 и подготовки бакалавров и магистров направления 220200 дисциплина «Телемеханика» заменена на дисциплину «Информационные сети и телекоммуникации (в задачах дистанционного управления техническими объектами)». Учитывая стековую структуру протоколов построения современных сетевых технологий, на дисциплину «Прикладная теория информации» в основном возлагаются задачи погружения студентов в проблематику сетевых технологий, представленную физическим и канальным уровнями стеков протоколов. При подготовке учебного пособия использованы материалы ранее опубликованных научных и учебно-методических публикаций, содержательно коррелирующих с проблематикой дисциплины «Прикладная теория информации»: Никифорова Л. Т., Рогинский И. Ю., Ушаков А. В. Алгебраический синтез дискретных систем. Учебное пособие. Л.:ЛИТМО, 1978.; Болтунов И.П., Никифорова Л. Т., Ушаков А. В. Расчет систем телемеханики. Учебное пособие. Л.:ЛИТМО, 1978.; Никифорова Л. Т., Болтунов Г.И., Ушаков А. В. Расчет телемеханических узлов и систем с применением ЭВМ. Учебное пособие. Л.:ЛИТМО, 1980.; Никифорова Л.Т., Ушаков А.В., Хабалов В.В. Теоретические основы кибернетики. Учебное пособие. Л.: ЛИТМО, 1984; Кирюшин А. А., Рассветалова Л. А., Ушаков А. В. Модальное управление в задаче синтеза двоичных динамических систем в логике линейных триггеров //Автоматика и телемеханика, 1993, №8.; Рассветалова Л. А., Ушаков А. В. Двоичное динамическое наблюдение в задаче помехоустойчивого кодирования //Автоматика и 9 телемеханика, 1993, №6.; Матричные уравнения в исследовании дискретных процессов над бесконечными и конечными полями / Т.А. Акунов, С. Алишеров, Р.О. Оморов, А.В. Ушаков / Под ред. А.В. Ушакова. – Бишкек: Илим, 1993.; Ушаков А. В. Синтез циклических кодирующих и декодирующих устройств в логике произвольных триггеров //Автоматика и телемеханика, 1997, №11.; Алгебраические методы в теории устройств дискретной автоматики и телемеханики: Труды лаборатории телемеханики СПбГИТМО(ТУ). / Под ред. А.В.Ушакова. – СПб: СПбГИТМО (ТУ), 2001; Мельников А.А., Ушаков А.В. Двоичные динамические системы дискретной автоматики / Под ред. А.В. Ушакова. СПб: СПбГУ ИТМО, теории систем: элементы теории и практикум./ Под ред. Ушакова А.В. – СПб: СПбГУИТМО, 2007.; Боженкова Н.Ю., Осипцева О.С., Ушаков А.В. Фактор канальной среды в задаче синтеза цифрового дистанционного управления непрерывным объектом // Изв.вузов. Приборостроение.2008.Т.51,№3;Дударенко Н.А., Нуйя – Осипцева О.С., Ушаков А.В., Филиппов М.И. Проблемы организации управления объектом типа «многомерный вход – многомерный выход» с помощью скалярного двоичного канала связи // Изв.вузов. Приборостроение.2009.Т.52,№11; Ушаков А.В., Яицкая Е.С. Двоичное наблюдение и задача помехозащитного декодирования систематических кодов // Изв.вузов. Приборостроение.2009.Т.52,№11; Ушаков А.В., Яицкая Е.С. Рекуррентное систематическое помехозащитное преобразование кодов: возможности аппарата линейных двоичных динамических систем //Изв. Вузов. Приборостроение. 2011.т.54.№3. В написании разделов 5, 6 и 7 приняла участие аспирант кафедры систем управления и информатики СПбНИУ ИТМО Яицкая Елена Сергеевна. Особую благодарность автор хотел бы выразить рецензентам доктору технических наук, профессору Дроздову Валентину Ниловичу и доктору технических наук, профессору Шалыто Анатолию Абрамовичу, чьи указания и советы заметно улучшили качество учебного пособия. Конструктивную критику по существу содержания учебного пособия следует направлять автору по: почтовому адресу 195267 до востребования, телефонам 5954128, 2900744 и электронной почте ushakov-AVG@yandex.ru. 10 Используемыеобозначенияисокращения S , X- множество элементов произвольной природы; ) p ( GF ), p ( GF , F , G , G n 0 - алгебраические структуры соответственно группа, подгруппа, поле, простое поле Галуа с характеристикой (модулем) p,расширенное поле Галуа; { } − d X , d , X метрическое пространство с метрикой ) y , x ( d d = ; A , A - соответственно линейный оператор (ЛО) и матрица ЛО; X n - n -мерное линейное пространство над полем F ; Rn - линейное вещественное пространство; - единичная матрица; - нулевой скаляр, вектор, матрица; j i A A A , , – матрица , i - я строка , j - й столбец матрицы A ; столбце ; A T - матрица , транспонированная к матрице A ; A* - матрица , сопряженная к матрице A ; A-1 - матрица , обратная к матрице A ; A+ - матрица , псевдообратная к матрице A ; { } n i diag , 1 , λ i = - диагональная матрица с элементами i λ на диагонали; { } n i row , 1 , α i = - строчная матричная структура с элементами i α в строке; { } n i col , 1 , α i = - столбцовая матричная структура с элементами i α в столбце; ( ) ο - норма элемента ( ) ο ; ( ) P ο - норма элемента ( ) ο с весом Р; { } y x ang , - угол между векторами x и y ; ∆ = - равенство по определению; ∀ - для всех; ∃ - существует; ∈ - принадлежит; ∉ - не принадлежит; max i - максимум на множестве элементов с индексом i ; 11 Ι Υ, - символы объединения и пересечения множеств; ( ) { } γ β arg γ = - значениe γ , удовлетворяющее условию ( ) γ β ; ( ) ( ) ( ) ( ) { } ο ο ο ο rang rank , tr , det - соответственно определитель, след, ранг матрицы ( ) ο ; ( ) ο dim -размерность элемента ( ) ο ; ( ) ο deg - степень полинома ( ) ο ; ( ) ο Jm - образ ( ) ο ЛО; Ker ( ) ο - ядро ( ) ο ЛО; ⊗ - символ кронекеровского произведения; ( ) { } B , A contr - предикат наличия свойства управляемости пары матриц ( ) B A , ); ( ) { } C , A observ - предикат наличия свойства наблюдаемости пары матриц ( А , С ) ; ∨ - логическое "или"; & - логическое "и"; ( ) ο : η ; ( ) ο | η - предикат наличия характеристического свойства η у элемента ( ) ο ; ( ) { } ο ∗ rem rest - остаток от деления ο ∗ ; АА – абстрактный автомат БП – блок памяти БФ – булева функция ВА – время «аппаратурное» ВВ – модель « вход - выход » ВК – время «канальное» ВМП – векторно-матричное представление ВНН – вектор невязки наблюдения ВПС – векторный показатель сложности ВС – модель « вход - состояние » ВСВ – векторно-матричное линейное описание « вход - состояние - выход » ГДДС – гибридная двоичная динамическая система ГСА – граф-схема алгоритма ДА – дискретная автоматика ДДС – двоичная динамическая система ДКП – двоичная кодовая последовательность ДКС - двоичный канал связи 12 ДКУ – декодирующее устройство ДНУ – двоичное наблюдающее устройство ДПВ – диаграмма переходов и выхода ДСНФ – дизъюнктивная совершенная нормальная форма ДУПК – дивидендное устройство помехозащитного кодопреобразования ИВП – источник входной последовательности ИДИ - источник дискретной информации ИМ - информационный массив ИЧК – информационная часть кода КА – конечный автомат КИ - квант информации КПР – кодовое пространство КС – канал связи КУ – кодирующее устройство ЛДДС – линейная двоичная динамическая система ЛУ – линейное устройство ММ – модулярный многочлен МС – модельная среда НДДС – нелинейная двоичная динамическая система ОПВ – оценка приведенной востребованности ОСВ – оценка степени востребованности ПЗК – помехозащищенный код ПЗКА – помехозащищенный конечный автомат ПНЗК – помехонезащищенный код ПТИ - прикладная теория информации РПКС – Регистр помехи в канале связи СД – «синдромный» дешифратор СДБФ – селлерсовское дифференцирование булевых функций СО - синдром ошибки ТИ - теория информации Т - триггер (примитивный автомат памяти первого порядка) УДA – устройство дискретной автоматики УДММ – устройство деления модулярных многочленов УК – устройство коммутации УКК – устройство коррекции кода УПЗК – укороченный помехозащищенный код УС – уравнение Сильвестра УУММ - устройство умножения модулярных многочленов УФКС - Устройство формирования кода сообщения УФСК – устройство формирования сигнала коррекции ХММ – характеристический модулярный многочлен 13 ХП – характеристический полином ЦДУ – циклическое декодирующее устройство ЦКУ – циклическое кодирующее устройство ЦПЗК – циклический помехозащищенный код ЧПС – частная производная Селлерса ЭЗ – элемент задержки ЭП – элемент памяти ■ – знак завершения доказательства утверждения, решения примера, завершения алгоритма; □ – знак завершения высказывания (утверждения, определения, примечания, следствия, свойства, постулата, гипотезы); ( )( ) { } k D • – прямое D – преобразование кодовой последовательности ( ) • над простым полем Галуа; ( ) { } • E – оператор округления величины ( ) • до ближайшего большего целого; ( ) ( ) { } k f D d F = – D – образ последовательности ( ) k f ; ( ) ( ) { } d f D k f 1 − = – оригинал D–образа последовательности ( ) k f ; ( ) { } N p p p GF ∈ − = , 1 ..., , 2 , 1 , 0 – простое поле Галуа; ( ) N n p p GF n ∈ , , – расширенное поле Галуа; k – дискретное время ( Κ , 2 , 1 , 0 = k ), выраженное в числе тактов длительностью t ∆ процессов передачи и преобразования кодов; { } n i row , 1 , α i = – строчная матричная структура с элементами i α в строке; ( ) k u – входная кодовая последовательность ДДС; ( ) k x – вектор исходного состояния ДДС; ( ) 1 k x + – вектор состояния перехода ДДС; ( ) k y – выходная кодовая последовательность ДДС; & – союз «И» предикатов; ∨ – союз «ИЛИ» предикатов. 14 ВВЕДЕНИЕ |