Реферат: Программа дисциплины по кафедре Вычислительная техника математические основы кодирования информации

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

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

Тихоокеанский государственный университет



Утверждаю

Проректор по учебной работе

______________ С.В. Шалобанов

“_____” ________________2007_ г.



Программа дисциплины

по кафедре Вычислительная техника


математические основы кодирования информации


Утверждена научно-методическим советом университета для направлений подготовки (специальностей) в области техники и технологии


Хабаровск 2007 г.


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


Программу составил (и)








































Ф.И.О. автора (ов)
Ученая степень, звание, кафедра






Программа рассмотрена и утверждена на заседании кафедры

протокол № ______ от «____»__________________ 200_г

Завкафедрой__________«__»______ 200_г

________________

Подпись дата

Ф.И.О.







Программа рассмотрена и утверждена на заседании УМК и рекомендована к изданию

протокол № ______ от «____»_____________ 200_г

Председатель  УМК  _______«__»_______ 200_г

_________________

Подпись дата

Ф.И.О.




Директор  института  _______«__»_______ 200_г

__________________

(декан факультета) Подпись дата

Ф.И.О.




^ Цели и задачи изучаемой дисциплины

.

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


^ 2. Требования к уровню освоения содержания дисциплины


В результате изучения дисциплины студент должен:

-знать основы кодирования информации при передаче ее по различным каналам;

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

-осуществляющее различные типы кодирования.

Дисциплина связана с предшествующими дисциплинами: ”Высшая математика”, "Теория вероятностей и математическая статистика", ”Программирование”.


объем дисциплины и виды учебной работы


Наименование

По учебным планам основной траектории обучения1

с максимальной трудоёмкостью

с минимальной трудоёмкостью

^ Общая трудоёмкость дисциплины







по ГОС

170




по УП






Изучается в семестрах
67

67

^ Вид итогового контроля по семестрам







зачет

67

67

экзамен







Курсовой проект (КП)







Курсовая работа (КР)







^ Вид итогового контроля самостоятельной работы без отчетностей

расчетно-графические работы (РГР)







Реферат (РФ)







Домашние задания (ДЗ)







^ Аудиторные занятия:







всего

85




В том числе: лекции (Л)

51




Лабораторные работы (ЛР)

34




Практические занятия (ПЗ)







^ Самостоятельная работа







общий объем часов (С2)







В том числе на подготовку к лекциям







на подготовку к лабораторным работам







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







на выполнение КП







на выполнение КР







на выполнение РГР







на написание РФ







на выполнение ДЗ







на экзаменационную сессию









^ Разделы дисциплины и виды занятий и работ


№
Раздел дисциплины Л
ЛР

ПЗ

КП

(КР)
РГР
ДЗ

РФ

С2

1

2

3

4

5

6

7

8

9

10



Введение.



*
























Математические модели сигналов

*

*
















*



Количественная оценка информации

*

*
















*



Информационные характеристики источника сообщений и канала связи.


*

*
















*



Кодирование при передаче по дискретному каналу без помех.


*

*
















*



Эффективное кодирование


*

*
















*



Кодирование по дискретному каналу с помехами

*

*
















*



тематический план лекционных занятий


№ темы
Раздел (тема) дисциплины Число часов по специальности ВМ
1

Введение.

Предмет и задачи дисциплины. Связь другими дисциплинами учебного плана. Понятие информации. Этапы обращения информации. информационные системы. системы передачи информации. Теория информации.

2

2

Математические модели сигналов.

Понятие сигнала и его модели. Формы представления сигналов. Преобразования непрерывных сигналов в дискретные. постановка задач дискретизации. Способы восстановления сигналов. Теорема Котельникова.

4

3

Количественная оценка информации.

^ Энтропия. Свойства энтропии. Количество информации. Основные свойства количества информации.

4

4

Информационные характеристики источника сообщений и канала связи.

^ Определения. Эргодичный источник. Избыточность. Модель дискретного канала. Модель непрерывного канала связи.

4

5

Кодирование при передаче по дискретному каналу без помех.

^ Код Грея. Криптографическое закрытие информации. Шифр простой подстановки. Код Вижинера. Гаммирование. Современные алгоритмы шифрования..

8

6

Эффективное кодирование.

^ Кодирование Шенона-Фано, Хаффмана. Современные алгоритмы сжатия информации.

16

7

Кодирование по дискретному каналу с помехами.

^ Теорема Шеннона. Помехоустойчивые коды. Блоковые коды. Групповые коды. Циклические коды. Коды БЧХ. Итеративные коды. Сверточные коды.

13

Итого

51



^ Лабораторный практикум и его взаимосвязь с содержанием лекционного курса



№ п/п

№ раздела по варианту

содержания
^ Наименование лабораторной работы
1

2
Математические модели сигналов
2

3
^ Измерение количества информации в дискретном и непрерывном сообщении
3

4
Информационные характеристики источника непрерывных сообщений и каналов
4

5
^ Кодирование информации по дискретному каналу без помех
5

7

ПРОЕКТИРОВАНИЕ КОДЕРА И ДЕКОДЕРА КОДА ХЭММИНГА на базе W-HDL исправляющего ошибки


6

7

ПРОЕКТИРОВАНИЕ КОДЕРА И ДЕКОДЕРА КОДА ХЭММИНГА на базе ^ W-HDL исправляющего и корректирующего ошибки


3

7

ПРОЕКТИРОВАНИЕ КОДЕРА И ДЕКОДЕРА КОДА С ЧЕТНЫМ ЧИСЛОМ ЕДИНИЦ на базе W-HDL


4

7

ПРОЕКТИРОВАНИЕ КОДЕРА И ДЕКОДЕРА ГРУППОВОГО КОДА на базе W-HDL




^ Перечень лабораторных работ

краткие характеристики ряда лабораторных работ по МОКИ


Лабораторная работа N 1

ПРОЕКТИРОВАНИЕ КОДЕРА И ДЕКОДЕРА КОДА С ЧЕТНЫМ ЧИСЛОМ ЕДИНИЦ на базе ^ W-HDL

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

^ Варианты задания:

k - количество информационных символов;

n - длина кода;

p - количество проверочных символов.

k=4, n=5

 

Порядок выполнения работы

Разработать логическую схему кодера и декодера кода с четным числом единиц, обнаружи­вающего ошибки нечетной кратности (k=4, n=5)..

В Схемном Редакторе W-HDL выполнить чертеж принципиальной схемы кодера и декодера кода с четным числом единиц, обнаружи­вающего ошибки нечетной кратности (k=4, n=5)..

Проверить принципиальную схему на наличие синтаксических и схемотехнических ошибок. Исправить обнаруженные ошибки.

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

^ Содержание отчета

Логическая схема кодера и декодера кода с четным числом единиц, обнаружи­вающего ошибки нечетной кратности (k=4, n=5)..

Принципиальные схемы кодера и декодера кода с четным числом единиц, обнаружи­вающего ошибки нечетной кратности (k=4, n=5) с возможностью имитации ошибок (демонстрируется на ЭВМ).

Временные диаграммы моделирования кодера и декодера кода с четным числом единиц, обнаружи­вающего ошибки нечетной кратности (k=4, n=5) в Редакторе Временных Диаграмм (демонстрируются на ЭВМ).

Контрольные вопросы

1. На какие типы разделяют помехоустойчивые коды? В чем заключается отличие между ними?

2. Что понимается под значностью и весом кодовой комбинации?

3. Как определяется расстояние между кодовыми комбинациями?

4. Какова связь корректирующей способности кода с кодовым расстоянием?

5. Что такое двоичный симметричный канал?

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

Лабораторная работа N 2

ПРОЕКТИРОВАНИЕ КОДЕРА И ДЕКОДЕРА ГРУППОВОГО КОДА на базе W-HDL

Задание : на базе средств W-HDL разработать модель кодера и декодера для группового кода, исправляющего одиночную ошибку, и выполнить их моделирование.

Варианты задания:

1. Количество k информационных разрядов P(n, k) кода: k = [(N+5) / 2],
где N - номер по журналу.

2. Вариант А -групповой код P(n, k) оптимальный с точки зрения минимума корректирующих разрядов и максимума информационных (N - нечетное). Вариант В -групповой код P(n, k) оптимальный с точки зрения минимума аппаратных затрат реализации кодера и декодера (N - четное) k - количество информационных символов;

Порядок выполнения работы

1. Определить минимальное количество контрольных разрядов. Построить производящую матрицу группового кода по варианту А или В.

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

3. Синтезировать кодер и декодер. Для исправления одиночной ошибки в декодере синтезировать дешифратор.

4. Разработать функциональные и принципиальные схемы кодера и декодера.

5. Составить и отладить программную модель.

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

Содержание отчета

1. Исходные данные.

2. Производящая матрица группового кода.

3. Проверочная матрица группового кода.

4. Синтез декодера.

5. Функциональная схема кодера и декодера.

6. Принципиальные схемы кодера и декодера группового кода с возможностью имитации ошибок. (демонстрируется на ЭВМ).

7. Временные диаграммы моделирования кодера и декодера группового кода в Редакторе Временных Диаграмм (демонстрируются на ЭВМ).

Контрольные вопросы

1. В чем заключается отличие между блочными и непрерывными кодами?

2. Что понимается под значностью и весом кодовой комбинации?

3. Как определяется расстояние между кодовыми комбинациями?

4. Какова связь корректирующей способности с кодовым расстоянием?

5. Как строится производящая матрица группового кода?

6. Каковы условия построения проверочной подматрицы?

7. Каков алгоритм определения проверочных символов по информационным с помощью проверочной матрицы?

8. Как определяется состав контрольных равенств с помощью проверочной матрицы?


^ Лабораторная работа N 3
ПРОЕКТИРОВАНИЕ КОДЕРА И ДЕКОДЕРА КОДА ХЭММИНГА на базе W-HDL

Задание : на базе средств W-HDL разработать модель кодера и декодера для кодов Хэмминга, исправляющих одиночную ошибку и исправляющих одиночную и обнаруживающих двукратные ошибки, и выполнить их моделирование..

Варианты задания:

1. Длина кодового слова n кода Хэмминга

n = [ ( 35 - N ) / 2 ],
где N - номер по журналу.

2. Вариант А - код Хэмминга с исправлением одиночной ошибки и обнаружением двукратной (N - четное). Вариант В - код Хэмминга с исправлением одиночной ошибки (N - нечетное).

Порядок выполнения работы

1. Определить минимальное количество контрольных разрядов. Построить производящую матрицу кода Хэмминга по варианту А или В.

2. Построить проверочную матрицу кода Хэмминга. Определить равенства для проверочных разрядов и равенства для определения разрядов синдрома.

3. Синтезировать кодер и декодер. Для исправления одиночной ошибки в декодере использовать стандартный дешифратор.

4. Разработать функциональные и принципиальные схемы кодера и декодера.

5. Составить и отладить программную модель.

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

Содержание отчета

1. Исходные данные.

2. Производящая матрица кода Хэмминга.

3. Проверочная матрица кода Хэмминга. .

4. Функциональная схема кодера и декодера.

5. Принципиальные схемы кодера и декодера группового кода с возможностью имитации ошибок. (демонстрируется на ЭВМ).

6. Временные диаграммы моделирования кодера и декодера группового кода в Редакторе Временных Диаграмм (демонстрируются на ЭВМ).

Контрольные вопросы

1. Что обусловило широкое распространение двоичных кодов?

2. Каков принцип построения кодов Хэмминга?

3. Каким образом составляются проверочные равенства кода Хэмминга?

4. Как строится проверочная матрица для кода Хэмминга с исправлением одиночной и обнаружением двукратной ошибок?

5. Как определяется коэффициент избыточности кода?

6. Какие коды называются плотноупакованными (совершенными)?

7. Как определяются номера позиций контрольных разрядов в коде Хэмминга?

8. Какие существуют разновидности кодов Хэмминга? В чем их отличие?

 

Лабораторная работа N 4

ПРОЕКТИРОВАНИЕ КОДЕРА И ДЕКОДЕРА КОДА ХЭММИНГА на базе W-HDL

Задание : на базе средств W-HDL разработать модель кодера и декодера для циклических кодов Хэмминга исправляющих одиночную ошибку и выполнить их моделирование..

Варианты задания:

1. Количество k информационных разрядов кода Хэмминга

k = [ ( N + 1 ) / 4 ],


где N - номер по журналу, N < 34.

2.




0 - вариант A,




1 - вариант B,

N mod 4 =

2 - вариант C,




3 - вариант D.

Для вариантов A и B выбирается образующий полином K(X) из таблицы; для вариантов C и D - полином K'(X), двойственный полиному K(X) из таблицы.

Для вариантов A и C реализовать 1-й способ построения циклических кодов (систематический код); для вариантов B и D - 2-й способ (несистематический код).

Для вариантов A, B, C, D - кодер на основе (n-k) -разрядного регистра сдвига.

3. Вариант E : N > 33, n=2(N-31) - 1, кодер на основе k-разрядного регистра сдвига.

Таблица пpимитивных полиномов



Степень полинома

Полином в 8-ричной с/с

1

1

2

7

3

13

4

23

5

45

6

103

Пример определения полинома для 6-й степени:
полином в 8-ричной с/с: 103 ;
полином в 2-ичной с/с: 001 000 011 ;
полиномиальная форма представления: X6 + X + 1.

Порядок выполнения работы

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

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

3. Синтезировать кодер и декодер на основе линейных переключательных схем.

4. Разработать функциональные и принципиальные схемы кодера и декодера.

5. Составить и отладить программную модель.

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

Содержание отчета

1. Исходные данные.

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

3. Выбор образующего полинома.

4. Образующая матрица циклического кода.

5. Функциональная схема кодера и декодера.

6. Принципиальные схемы кодера и декодера циклического кода с возможностью имитации ошибок. (демонстрируется на ЭВМ).

7. Временные диаграммы моделирования кодера и декодера циклического кода в Редакторе Временных Диаграмм (демонстрируются на ЭВМ).

Контрольные вопросы

1. Чем обусловлено название циклических кодов?

2. Какие известны способы построения циклических кодов?

3. Каким образом выбирается образующий полином циклического кода?

4. Как строится проверочная матрица для циклического кода с исправлением одиночной ошибок?

5. Какова процедура обнаружения и исправления ошибки в циклических кодах с d=3?

6. Что такое "декодер Меггитта"?

7. Что такое "укороченный циклический код"?

8. Как реализуется операция деления на полином с помощью линейной переключательной схемы?

9. Как выполняется умножение полиномов с помощью линейной переключательной схемы?

10. Как определить полином, двойственный заданному?

11. Что такое неприводимый полином?



^ 2.1 Вопросы входного контроля

Знание основ теории вероятностей и математической статистики, основ программирования.

2.2 Текущий контроль

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

2.3 Вопросы выходного контроля

Понятие информации.

Этапы обращения информации, информационные системы, системы передачи информации.

Математические модели сигналов.

Понятие сигнала и его модели.

Формы представления сигналов.

Преобразования непрерывных сигналов в дискретные.

Постановка задач дискретизации.

Способы восстановления сигналов.

Теорема Котельникова.

Количественная оценка информации.

Энтропия. Свойства энтропии.

Количество информации. Основные свойства количества информации.

Информационные характеристики источника сообщений и канала связи.

Эргодичный источник.

Избыточность.

Модель дискретного канала.

Модель непрерывного канала связи.

Кодирование припередаче по дискретному каналу без помех.

Код Грея.

Криптографическое закрытие информации.

Шифр простой подстановки.

Код Вижинера.

Гаммирование.

Современные алгоритмы шифрования..

Эффективное кодирование.

Кодирование Шенона-Фано, Хаффмана.

Современные алгоритмы сжатия информации.

Кодирование по дискретному каналу с помехами.

Теорема Шеннона для дискретного канала с помехами.

Помехоустойчивые коды.

Блоковые коды.

Групповые коды.

Циклические коды.

Коды БЧХ.

Итеративные коды.

Сверточные коды.



Учебно-методическое обеспечение.


В.И. Дмитриев Прикладная теория информации. М: Высшая школа, 1989 г., 320 с.

Орлов В.А. Теория информации в упражнениях и задачах. М: Высшая школа, 1976 г., 135 с.

В.Д. Колесник введение в теорию информации (кодирование источников). Л: Издательство Ленинградского университета. 1980 г., 162 с.

Р.Хемминг Теория кодирования и теория информации. М: Радио и связь, 1983

В.В. Золотарев, Г.В. Овечкин Помехоустойчивое кодирование. Методы и алгоритмы. М: Горячая линия - Телеком, 2004 г., 126с.

Р. Морелос – Сарагоса Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М. Техносфера, 2005 г., 320 с.

М. Вернер Основы кодирования М. Техносфера,2004 г., 288с.



^


Словарь терминов и персоналий

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

^ Знак – это реально различимые материальные объекты: буквы, цифры, предметы.

Сигнал – это динамический процесс, т.е. процесс, изменяющийся со временем, или колебания величины любой природы: напряжения, давления, электромагнитного поля и др.

^ Непрерывное сообщение – это сообщение, представляющее собой функцию времени, принимающая значения на всем континууме моментов времени.

Реализация непрерывного сообщения u(t), преобразо­ванного в электрическую форму первичного x(t), может быть преобразована в дискретный вид (последователь­ность чисел) с помощью процесса взятия выборок (от­счетов мгновенных значений) через интервалы Δt1, Δt2, Δt3, ....процесс взятия выборок u() называется дискретизацией или квантованием по времени.

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

Случайный процесс – случайная функция времени U(t), значение которой в каждый момент времени случайно.

^ Источник информации – это устройство, явление или причина, порождающая информацию.

Составной источник – это два и более источника одновременно посылающих информацию получателю.

Совокупность знаков u1,u2,u3,..un соответствующих всем N возможным состояниям источника называют его алфавитом, а количество состояний N объемом алфавита.

Источник информации – это устройство, явление или причина, порождающая информацию.

^ Типичные последовательности – это последовательности, которые при достаточном большом N отличаются тем, что вероятности их появления практически одинаковы.

^ Эргодический источник – это источник, для которого усреднение по реализациям совпадает с усреднением по времени.

Вероятность появления элементов сообщения характеризуется неопределенностью выбора.

Неопределенность выбора есть энтропия источника.

^ Источник информации – это устройство, явление или причина, порождающая информацию.

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

^ Количество информации – мера информации, сообщаемой появлением события определенной вероятности. Количеством информации также называют меру неопределенности источника.

^ Канал связи – совокупность устройств и физических сред, обеспечивающих передачу сообщений из одного места в другое (или от одного момента времени до другого).

^ Сигнал – это материальный носитель информации.

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

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

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

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

Если переходные вероятности постоянны, то канал имеет одно состояние и называется стационарным каналом без памяти.

^ Канал называется k – ичным, если у него k различных состояний на входе и на выходе.

Пропускная способность канала – максимально возможная скорость передачи информации, которую можно достичь выбором определенного метода кодирования:

Кодирование – процесс сопоставления элементов алфавита цифрам.

^ Код – правило сопоставления.

Кодовые слова – цифры, сопоставленные элементам алфавита.

Кодовое дерево – изображение совокупности кодовых комбинаций эффективного кода в виде графа.

^ Знак – это реально различимый материальный объект: буква, цифра, предмет.

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


^ график самостоятельной работы



^ План – график

Самостоятельной работы студентов

По дисциплине _МОКИ_________________________________________________

Институт (факультет) ИИТ__________ специальность ВМ____________________________

Семестр 6_____________________ часов в неделю (Л-ЛР-ПЗ / ФКТ - С2- РГР) 2-1-0/5______________

Распределение нормативного времени самостоятельной работы студентов по неделям семестра

17




3

2







5

лектор ___________________________________________

16




3

2







5

15




3

2







5

14




3

2







5

13




3

2







5