Практическая работа 1_4 Теория информации

Теоретическая подготовка Подготовьте ответы на вопросы: В чём заключается сущность помехоустойчивого кодирования? Какие задачи решают помехоустойчивые коды? Какой код называется кодом с проверкой по паритету? В чём заключается сложность выбора корректирующего кода для реальных каналов связи? Какие коды называются блочными? Перечислите основные характеристики корректирующих кодов. Что такое минимальное кодовое расстояние? Укажите количественную связь между минимальным кодовым расстоянием и корректирующей способностью кода. Что определяет верхние границы для кодового расстояния? Что определяет нижние границы для кодового расстояния? Опредение границы Плоткина и Хемминга. Определите границу Варшамова-Гильберта. Дайте определение синдрома ошибок. Дайте определение шумового вектора. Чему равны скорость и избыточность кода.

Кодовые слова Кодовым словом называют любой ряд допустимых знаков. Например, двоичное число 1100 можно считать двоичным 4- разрядным кодовым словом.

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

Расстояние по Хэммингу Блоковые коды характеризуются так называемым минимальным кодовым расстоянием. Расстоянием по Хэммингу между двумя кодовыми словами называется число разрядов, в которых они различны. При этом в качестве минимального кодового расстояния (d min ) выбирается наименьшее из всех расстояний по Хэммингу для любых пар различных кодовых слов, образующих код.

Пример Пусть мы используем только трехразрядные двоичные слова. Всего таких кодовых слов может быть восемь. Те кодовые слова, которые отличаются только на одну единицу, называются соседними. Например, кодовые слова 101 и 111 – соседние, так как отличаются только средним разрядом, а слова 101 и 110 – не соседние, так как у них отличаются два последних разряда.

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

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

Одиночные ошибки Минимальное расстояние между допустимыми словами кода с контролем по четности равно двум (из рисунка на предыдущем слайде видно, что никакие два кодовых слова в рамочках не соединены линиями, то есть не являются соседними). Именно по этой причине одиночная ошибка в кодовом слове превращает это слово в недопустимое.

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

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

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

код Хэмминга. Кодовое слово длиной n содержит k информационных и m контрольных разрядов. Коррекция искаженного i-го разряда заключается в сложении (по модулю 2) принятого кодового слова с вектором вида 0…010…0, содержащем единицу в i-ом разряде. Для n-разрядного кодового слова существует n таких векторов, соответствующих однократным ошибкам, и один нулевой вектор, соответствующий случаю приема слова без ошибок. Таким образом, m контрольных разрядов должны обеспечивать формирование n + 1 вектора ошибки, то есть должно выполняться неравенство. В результате получается (2 m -1, 2 m -1-m) код, называемый кодом Хэмминга.

Код Хэмминга (7,4) Простейший нетривиальный случай, соответствующий m=3, образует (7,4)-код, который можно синтезировать следующим образом. Сопоставим каждому вектору ошибки порядковый номер – синдром (след.слайд). При этом нулевому вектору ошибки соответствует нулевой синдром.

Векторы ошибок и соответствующие им синдромы a6a6 a5a5 a4a4 a3a3 a2a2 a1a1 a0a0 s2s2 s1s1 s0s

Функция S Рассматривая функции s i как свертку по модулю 2 разрядов кодовых слов, получим:

Информационные разряды Функции s i должны обращаться в единицу при наличии ошибки в одном из образующих их разрядов, и в ноль – при отсутствии ошибок. Обеспечение этого требования возможно лишь при условии, что часть разрядов формируется специальным образом. В частности, разряды a 0, a 1, a 2 можно рассматривать как свертку по модулю 2 остальных разрядов, участвующих в соответствующих уравнениях:

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

Пример Допустим, исходное информационное слово равно 1101, то есть a6=1, a5=1, a4=1, a3=1. Для преобразования его в допустимое кодовое слово помехоустойчивого (7,4) -кода Хэмминга рассчитаем контрольные разряды по найденным выше зависимостям. В частности, Таким образом, с учетом контрольных разрядов кодовое слово будет равно

Пример Если в процессе передачи или хранения слово осталось неискаженным, то его синдром s0…s2 будет соответственно равен: Синдром, состоящий из одних нулей, указывает на отсутствие ошибки и соответствует нулевому вектору ошибки.

Пример Предположим, что в процессе передачи или хранения в результате воздействия внешних факторов оказался искаженным отдельный разряд кодового слова. Например, вместо слова было принято слово В этом случае синдром окажется отличным от нуля: s0…s2 будет соответственно равен: Синдром 101 соответствует вектору ошибки , при этом единица указывает на разряд, в котором эта ошибка произошла. Для ее коррекции достаточно сложить по модулю 2 принятое искаженное кодовое слово с вектором ошибки.

Решение задач 1. Определите границы Плоткина и Хемминга для кодов (6,3) и (7,4), имеющих d min = Определите границу Варшамова-Гильберта для этих же кодов. 3. Рассчитать избыточность -кода Хэмминга (7,4). 4. Вычислить минимальную и максимальную оценки количества дополнительных разрядов для кодовых слов длины n,если требуется чтобы минимальное расстояние между ними было d. Варианты: a)n = 32, d = 3 б) n = 23, d = Закодируйте целые числа от 5 до 8 кодом Хемминга (7,4), пользуясь уравнениями для проверок. 6. Чему равны скорость и избыточность кода (9,5)? 7. Сколько всего синдромов ошибок может содержать таблица декодирования кода (9,5)? Постройте таблицу кода (9,5). 8. Определите шумовой вектор для конфигурации из одной ошибки в пятой позиции кода (9,5). Для справки см. rekurrentnyh-kodov.html

Конец Если вы решили все задачи получите 10 баллов.