Избыточное кодирование информации. Код Хэмминга.

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

Если длина кода n разрядов, то таким двоичным кодом можно представить максимум 2^n различных слов. Если все разряды слова служат для представления информации, код называется простым (неизбыточным). Коды, в которых лишь часть кодовых слов используется для представления информации, называются избыточными. Часть слов в избыточных кодах является запрещенной, и появление таких слов при передаче информации свидетельствует о наличии ошибки.

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

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

Способность кода обнаруживать или исправлять “ошибки” определяется так называемым минимальным кодовым расстоянием. Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова п, то кодовое расстояние может принимать значения от 1 до n. Минимальным кодовым расстоянием данного кода называется минимальное расстояние между двумя любыми словами в этом коде. Если имеется хотя бы одна пара слов, отличающихся друг от друга только в одном разряде, то минимальное расстояние данного кода равно 1.

Простой (не избыточный) код имеет минимальное расстояние dmin — 1. Для избыточных кодов dmin > 1. Если dmin > 2, то любые два слова в данном коде отличаются не менее чем в двух разрядах, следовательно, любая одиночная ошибка приведет к появлению запрещенного слова и может быть обнаружена. Если dmin = 3, то любая одиночная ошибка создает запрещенное слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова — в двух разрядах. Заменяя запрещенное слово ближайшим к нему (в смысле кодового расстояния) разрешенным словом, можно исправить одиночную ошибку.

В общем случае, чтобы избыточный код позволял обнаруживать ошибки кратностью r, должно выполняться условие:

dmin>r+1

Код Хэмминга.

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

d + p + 1 ≤ 2 ^p,

где d - размер блока данных в битах, p - количество необходимых контрольных бит. Обычно для характеристики кода Хэмминга используют пару (c, d), где с - длина передавемого блока данных с контрольными битами, а d - чистая длина данных. Например, (11, 7) означает, что передаваемая длина данных - 7 бит, количество контрольных бит равно 4, что составляет общую длину блока 11 бит. В отличае от других методов коррекции ошибки, где контрольные биты дописываются в конец или начало блока данных (либо вообще в другом пакете данных), биты кода Хэмминга записываются вместе с данными в строго определённых позициях. Здесь и делее мы будем нумеровать биты не с нуля, а с единицы. Тогда позиции в которых записываются контрольные биты соответствуют степеням двойки (2^k, k = 0, 1, 2,...), то есть 1, 2, 4, 8 и т.д.
Рассмотрим механизм работы кода Хэмминга на примере передачи 7-битового кода 1110011. Для контроля целостности блока данных такой длины, нам необходимо 4 бита кода Хэмминга, которые записываются в позициях 1, 2, 4, 8:

Позиция бита                       Значение бита       *       *   * * Таблица 1 - Расположение битов кода Хэмминга (отмечены '*')

Контрольная сумма формируется путем выполнения операции "исключающее ИЛИ" над кодами позиций ненулевых битов. В данном случае это 11, 10, 9, 5 и 3.

сумма   Таблица 2 - Нахождение контрольной суммы

Полученная контрольная сумма записывается в соответствующие разряды блока данных - младший бит в младший разряд. Таким образом формируется следующий блок данных:

Позиция бита                       Значение бита                       Таблица 3 - Результирующий блок данных

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

сумма   Таблица 4 - Проверка корректности блока данных

Теперь рассмотрим два случая ошибки: 1) ошибка в бите 7 - бит 0 заменён на бит 1 и 2) ошибка в бите 5 - бит 1 заменён на бит 0. Просуммируем коды позиций с ненулевыми битами:

сумма     сумма   Таблица 5 - Контрольная сумма в блоках данных содержащих ошибку

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

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

Задача поиска подстроки в строке заключается в нахождении в оригинальной строке, точного вхождения (соответствие всех символов) подстроки. В результате программа должна выдать номера символов всех вхождений подстроки…

Метод Грубой силы.

Этот алгоритм заключается в проверке всех позиций текста с 0 по n – m (n-длина строки, m-длина подстроки) на предмет совпадения с началом образца. Если совпадает - смотрим следующую букву и т.д.

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

Оптимизацией метода грубой силы является алгоритм хэш функции…

Хэш-функции

Хэш-функция - это преобразование, получающее из данных произвольной длины некое значение фиксированной длины. Простейшими примерами являются контрольные суммы. Бывают криптографические и программистские хэши. Криптографический хэш отличается от программистского следующими двумя свойствами: необратимостью и свободностью от коллизий. Обозначим m - исходные данные, h(m) - хэш от них. Необратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0. Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1!= m2, но h(m1) = h(m2).
Криптографические хэш-функции разделяются на два класса:
- хэш-функции без ключа
- хэш-функции с ключом.

Хэш-функции без ключа разделяются на два подкласса:
- слабые хэш-функции,
- сильные хэш-функции.
Слабой хэш-функцией называется односторонняя функция H(x), удовлетворяющая следующим условиям:
1) аргумент х может быть строкой бит произвольной длины;
2) значение H(x) должно быть строкой бит фиксированной длины;
3) значение H(x) легко вычислить;
4) для любого фиксированного x вычислительно невозможно найти другой x'!= x, такой что H(x')=H(x).
Пара x'!= x, когда H(x')=H(x) называется коллизией хэш-функции. Сильной хэш-функцией называется односторонняя функция H(x), удовлетворяющая условиям 1-3 для слабой хэш-функции и свойству 4':
4') вычислительно невозможно найти любую пару x'!= x, такой что H(x')=H(x).
Поскольку из свойств 1-2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 4' говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.

Хэш-функцией с ключом называется функция H(k,x) удовлетворяющая свойствами:
1) аргумент х функции H(k,x) может быть строкой бит произвольной длины;
2) значение H(k,x) должно быть строкой бит фиксированной длины;
3) при любых k и x легко вычислить H(k,x);
4) для любого х должно быть трудно вычислить H(k,x) не зная k;
5) должно быть трудно определить k даже при большом числе неизвестных пар {x, H(k,x)} при выбранном наборе х или вычислить по этой информации H(k,x') для x'!= x.

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

Вот некоторые алгоритмы хэш-функций:
MD2
Автор: FIXME!
Размер: 128 бит.

MD4
Автор: Р.Райвест (R. Rivest).
Размер: 128 бит.

MD5. Капитально переделанный MD4.
Автор: Р.Райвест (R. Rivest).
Размер: 128 бит.

SHA.
Один из (относительно) новых алгоритмов свертки.
Автор: FIXME!
Размер: 160 бит.

ГОСТ Р34.11-94
Российский алгоритм. Размерность получаемого значения очень удобна для формирования по паролю ключа для ГОСТ 28147-89.
Автор: FIXME!
Размер: 256 бит.

Рассмотрим поиск подстроки в строке с помощью хэш-функции. Каждый символ имеет свой уникальный код от 0 до 255. Суть метода заключается в том, чтобы для подстроки подсчитать некоторую хэш-функцию (например, сумму кодов всех символов в строке), затем посчитать ту же самую хэш-функцию для части строки, равной по длине подстроке, и, в случае совпадения хэш-функции, полностью сравнить его. Ускорение работы алгоритма связано с тем, что мы каждый раз не пересчитываем каждый раз хэш-функцию, а только отнимаем значение функции от самого "старого" символа и добавляем значение функции от следующего символа.