ПР4_Отчёт_ЗаболотниковМЕ_9373

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра информационных систем

отчет

по практической работе №4

по дисциплине «Теория информации, данные, знания»

Тема: Основы теории кодирования. Код Хемминга

Студент(ка) гр. 9373		Заболотников М.Е
Преподаватель		Писарев И. А.

Санкт-Петербург

2020

Цель работы

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

Вопросы по теме 4:

1. Сформулируйте задачу надёжной передачи сообщений.

2. Объясните, почему кодирование с контрольной суммой позволяет обнаружить в процессе передачи только нечётное число ошибок

3. Дайте определение расстояния Хэмминга между двоичными словами

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

5. Решить задачу:

Для слов длины в алфавите используются кодовые слова длины (3, 4 – коды). Порождающая матрица имеет вид:

Какую по кратности ошибку может обнаружить этот код?

a) Определите кодовое слово b для слова исходного сообщения a= 001.

b) Какое кодовое слово b соответствует слову исходного сообщения a= 100.

c) Какое кодовое слово b соответствует слову исходного сообщения a= 111.

Выполнение работы

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

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

3. Пусть имеются два слова и длины и состоящие из символов алфавита . Расстоянием Хемминга между словами и – – называется количество несовпадений в одних и тех же позициях чисел и .

4. Обнаруживающая способность кода связана с минимальным расстоянием Хэмминга через теорему об обнаруживающем коде:

«Для того, чтобы код являлся обнаруживающим, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами удовлетворяло неравенству: .»

5. Итак, порождающая матрица . Возьмём первые два слова – и . Вычислим коды этих слов:

А) ;

Б) .

Минимальное расстояние между словами (кодами) и равно . Следовательно, обнаруживающая способность кода равна ( при ).

1. (см. пункт Б выше);

2. ;

3. .

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. https://yadi.sk/i/g387TDYOrKwdUw