Кодирование хемминга с подсчетом единичных бит

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

Факультет технической кибернетики

—————————

Кафедра информационной безопасности компьютерных систем

ОТЧЕТ

по лабораторной работе №4

«Контроль и восстановление целостности информации»

По курсу «Основы информационной безопасности»

Студент:	Виноградова М.М.
	гр. 1088/4
Преподаватель:	Калинин М.О.

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

1. Цель:

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

Теоретические сведения

Помехоустойчивое кодирование

Среда, no которой передается информация, He может быть абсолютно надежной. В беспроводных системах связи и телекоммуникационных системах уровень помех бывает очень высоким, Наиболее простой способ проверки целостности передаваемых данных — использование контрольных cyмм. Однако такой подход позволяет только обнаруживать влияние среды. Ha передаваемую информацию. В том случае, если необходимо исправлять ошибки в Переданных данных без их повторной передачи, применяется помехоустойчивое кодирование.

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

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

В результате влияния пoмex в сообщении возникают ошибки. Ошибки в сообщении однобитными или групповыми. У групповых ошибок есть свои позитивные и негативные свойства. Положительное свойство групповой ошибки заключаются в следующем. Пусть данные передаются блоками no 1000 бит, a вероятность ошибки

составляет 0,001 Ha бит. Если ошибки изолированные и независимые, то 63% блоков (0,63~2:1-0,999^(1000)) будут содержать ошибки. Если же они возникают группами по 100 сразу, то ошибки будут содержать 1% блоков (0,01~1-0,999^(10)). Зато, если ошибки нe группируются, То в каждом кадре они невелики, и есть возможность их исправить. Негативное свойство групповых ошибок заключается в том, что они портят кадр безвозвратно. В результате требуется повторная пересылка сообщения, что в некоторых системах невозможно (например, в телефонных сетях).

Кодирование Хемминга

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

Обнаружив ошибку, декодер последовательно сравнивает искаженный символ co всеми разрешенными символами, стремясь найти символ, наиболее схожий с искаженным (т.е. символ с наименьшим числом различий, a именно нe более чем в d-1 позициях, где d— расстояние Хемминга).

B общем случае, если количество сбойных бит меньше расстояния Хемминга хотя 6ы наполовину, то декодер может гарантированно восстановить исходный символ.

Таким образом, условие обнаружения ошибок: d=r, где r —

количество ошибок; условие успешного восстановления информации:

d2r. Поэтому простейшая реализации кодирования Хемминга дополнительно к информационным разрядам вводит L=log2К избыточных контролирующих разрядов, где К — число информационных разрядов. Число L округляется до ближайшего большего целого значения. L? разрядный контролирующий код есть инвертированный результат

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

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

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

Биты, номера которых являются степенью 2, являются контрольными, остальные биты — информационными. Каждый контрольный бит отвечает за четность суммы связанной c ним группы бит, расположенных справа. Если сумма соответствующих информационных

битов четная, то контрольный бит равен нулю, и наоборот.

Такие коды Хемминга способны исправлять лишь одиночные ошибки. C ростом размеров обрабатываемых слов увеличивается и вероятность ошибок. Выбор оптимальной размерности кодируемых слов является нетривиальной задачей, требующей знания характера и частоты возникновения ошибок в используемых каналах передачи информации.

Результаты работы

Кодирование Хемминга с подсчетом единичных бит

Создадим файл, на котором будем проверять работоспособность программ