Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

где 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:

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

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

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

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

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

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

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