Слайд 1ИБ 5
Методы защиты информации в АСОД
Тема 5. Методы защиты информации
в АСОД
Алгоритмы обнаружения и исправления ошибок
Каналы передачи данных ненадежны
(шумы, наводки и т.д.), да и само оборудование обработки информации работает со сбоями.
Если ошибка обнаружена, можно осуществить повторную передачу данных и решить проблему. Если исходный код по своей длине равен полученному коду, обнаружить ошибку передачи не предоставляется возможным.
Слайд 2ИБ 5
Методы защиты информации в АСОД
Простейшим способом обнаружения ошибок является
контроль по четности. Обычно контролируется передача блока данных (М бит).
Этому блоку ставится в соответствие кодовое слово длиной N бит, причем N>M.
Избыточность кода характеризуется величиной 1-M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность).
Слайд 3ИБ 5
Методы защиты информации в АСОД
При передаче информации она кодируется
таким образом, чтобы с одной стороны характеризовать ее минимальным числом
символов, а с другой – минимизировать вероятность ошибки при декодировании получателем. Для выбора типа кодирования важную роль играет так называемое расстояние Хэмминга.
Пусть А и Б — две двоичные кодовые последовательности равной длины. Расстояние Хэмминга между двумя этими кодовыми последовательностями равно числу символов, которыми они отличаются. Например, расстояние Хэмминга между кодами 00111 и 10101 равно 2.
Слайд 4ИБ 5
Методы защиты информации в АСОД
Можно показать, что для детектирования
ошибок в N битах схема кодирования требует применения кодовых слов
с расстоянием Хэмминга не менее N + 1.
Можно также показать, что для исправления ошибок в N битах необходима схема кодирования с расстоянием Хэмминга между кодами не менее 2N + 1.
Таким образом, конструируя код, мы пытаемся обеспечить расстояние Хэмминга между возможными кодовыми последовательностями большее, чем оно может возникнуть из-за ошибок.
Слайд 5ИБ 5
Методы защиты информации в АСОД
Широко распространены коды с одиночным
битом четности. В этих кодах к каждым М бит добавляется
1 бит, значение которого определяется четностью (или нечетностью) суммы этих М бит.
Так, например, для двухбитовых кодов 00, 01, 10, 11 кодами с контролем четности будут 000, 011, 101 и 110. Если в процессе передачи один бит будет передан неверно, четность кода из М+1 бита изменится.
Слайд 6ИБ 5
Методы защиты информации в АСОД
Предположим, что частота ошибок (BER
– Bit Error Rate) равна р = 10-4. В этом
случае вероятность передачи 8 бит с ошибкой составит 1 – (1 – p)8 = 7,9 х 10-4.
Добавление бита четности позволяет детектировать любую ошибку в одном из переданных битах. Здесь вероятность ошибки в одном из 9 битов равна 9p(1 – p)8. Вероятность же реализации необнаруженной ошибки составит 1 – (1 – p)9 – 9p(1 – p)8 = 3,6 x 10-7.
Слайд 7ИБ 5
Методы защиты информации в АСОД
Таким образом, добавление бита четности
уменьшает вероятность необнаруженной ошибки почти в 1000 раз. Использование одного
бита четности типично для асинхронного метода передачи.
В синхронных каналах чаще используется вычисление и передача битов четности как для строк, так и для столбцов передаваемого массива данных. Такая схема позволяет не только регистрировать, но и исправлять ошибки в одном из битов переданного блока.
Слайд 8ИБ 5
Методы защиты информации в АСОД
Контроль по четности достаточно эффективен
для выявления одиночных и множественных ошибок в условиях, когда они
являются независимыми.
При возникновении ошибок в кластерах бит метод контроля четности неэффективен, и тогда предпочтительнее метод вычисления циклических сумм (CRC — Cyclic Redundancy Check).
В этом методе передаваемый кадр делится на специально подобранный образующий полином. Дополнение остатка от деления и является контрольной суммой.
Слайд 9ИБ 5
Методы защиты информации в АСОД
В Ethernet вычисление CRC производится
аппаратно. На рисунке показан пример реализации аппаратного расчета CRC для
образующего полинома R(x) = 1 + x2 + x3 + x5 + x7. В этой схеме входной код приходит слева.
Слайд 10ИБ 5
Методы защиты информации в АСОД
Слайд 11ИБ 5
Методы защиты информации в АСОД
Эффективность CRC для обнаружения ошибок
на многие порядки выше простого контроля четности. В настоящее время
стандартизовано несколько типов образующих полиномов.
Для оценочных целей можно считать, что вероятность невыявления ошибки в случае использования CRC, если ошибка на самом деле имеет место, равна (1/2)r, где r — степень образующего полинома.
Слайд 12ИБ 5
Методы защиты информации в АСОД
В наземных каналах связи, где
вероятность ошибки невелика, обычно используется метод детектирования ошибок и повторной
пересылки фрагмента, содержащего дефект.
Для спутниковых каналов с типичными для них большими задержками системы коррекции ошибок становятся привлекательными. Здесь используют коды Хэмминга или коды свертки.
Слайд 13ИБ 5
Методы защиты информации в АСОД
Рассмотрим, например, следующий 4-битный код:
Это
обыкновенный двоичный код, который можно встретить в некоторых однокристаллках, вмещающий
в свои 4 бита 16 символов (т.е. с его помощью можно закодировать 16 букв алфавита).
Как нетрудно убедиться, два любых символа отличаются по меньшей мере на один бит, следовательно, расстояние Хемминга для такого кода равно единице (что условно обозначает как d = 1).
Слайд 14ИБ 5
Методы защиты информации в АСОД
А вот другой 4-битный код:
На
этот раз два произвольных символа отличаются как минимум в двух
позициях, за счет чего информационная емкость такого кода сократилась с 16 до 8 символов. При этом комбинации 0001 или 0010, например, отсутствуют.
Указанных комбинаций (и ещё шести) бит в данном коде действительно нет, точнее, они есть, но объявлены запрещенными.
Слайд 15ИБ 5
Методы защиты информации в АСОД
Благодаря этому обстоятельству наш подопечный
код способен обнаруживать любые одиночные ошибки.
Возьмем, например, символ «1010» и
исказим в нем произвольный бит (но только один!). Пусть это будет второй слева бит, тогда искаженный символ станет выглядеть так: «1110».
Поскольку комбинация «1110» является запрещенной, декодер может засвидетельствовать наличие ошибки.
Только засвидетельствовать, но не исправить, т.к. для исправления даже одного-единственного сбойного байта требуется увеличить расстояние Хемминга как минимум до трех.
Слайд 16ИБ 5
Методы защиты информации в АСОД
Поскольку 4-битный код с d
= 3 способен вмещать в себя лишь два различных символа,
то он крайне ненагляден и потому нам лучше выбрать код с большей разрядностью. Пусть это будет 10-битный код с d = 5.
Слайд 17ИБ 5
Методы защиты информации в АСОД
Возьмем, к примеру, символ «0000011111»
и исказим два любых бита, получив в итоге что-то наподобие:
«0100110111».
Поскольку такая комбинация является запрещенной, декодер понимает, что произошла ошибка. Достаточно очевидно, что если количество сбойных бит меньше расстояния Хемминга хотя бы наполовину, то декодер может гарантированно восстановить исходный символ.
Слайд 18ИБ 5
Методы защиты информации в АСОД
Действительно, если между двумя любыми
разрешенными символами существует не менее пяти различий, то искажение двух
бит всякого такого символа приведет к образованию нового символа (обозначим его k), причем расстояние Хемминга между k и оригинальным символом равно числу непосредственно искаженных бит (т.е. в нашем случае двум), а расстояние до ближайшего соседнего символа равно: d – k (т.е. в нашем случае трем).
Слайд 19ИБ 5
Методы защиты информации в АСОД
Другими словами, пока d–k>k декодер
может гарантированно восстановить искаженный символ. В тех случаях, когда d>k>d–k,
успешное восстановление уже не гарантируется, но при удачном стечении обстоятельств все-таки оказывается в принципе возможным.
Возвращаясь к нашему символу «0000011111», давайте на этот раз исказим не два бита, а четыре:
«0100110101»
и попробуем его восстановить. Изобразим процесс восстановления графически:
Слайд 20ИБ 5
Методы защиты информации в АСОД
Грубо говоря, обнаружив ошибку, декодер
последовательно сличает искаженный символ со всеми разрешенными символами алфавита, стремясь
найти символ наиболее «похожий» на искаженный. Точнее, символ с наименьшим числом различий, а еще точнее, символ, отличающийся от искаженного не более чем в (d – 1) позициях. Легко видеть, что в данном случае нам повезло, и восстановленный символ совпал с истинным.
Слайд 21ИБ 5
Методы защиты информации в АСОД
Однако если бы четыре искаженных
бита распределились бы так:
«0111111111», то декодер принял бы этот символ
за «1111111111» и восстановление оказалось бы неверным.
Таким образом, исправляющая способность кода определяется по следующей формуле:
для обнаружения r ошибок расстояние Хемминга должно быть больше или равно r;
для коррекции r ошибок расстояние Хемминга должно быть по крайней мере на единицу больше удвоенного количества r.
Слайд 22ИБ 5
Методы защиты информации в АСОД
Теоретически количество обнаруживаемых ошибок неограниченно,
практически же информационная емкость кодовых слов стремительно тает с ростом
d.
Допустим, у нас есть 24 байта данных, и мы хотели бы исправлять до двух ошибок на каждый такой блок. Тогда нам придется добавить к этому блоку еще 49 байт, в результате чего реальная информационная емкость блока сократится всего… до 30%!
Столь плачевный результат объясняется тем, что биты кодового слова изолированы друг от друга и изменение одного из них никак не сказывается на окружающих.
Как изменить существующее положение?
Слайд 23ИБ 5
Методы защиты информации в АСОД
Пусть все биты, номера которых
есть степень двойки, станут играть роль контрольных битов, а оставшиеся
и будут обычными («информационными») битами сообщения.
Каждый контрольный бит должен отвечать за четность суммы некоторой принадлежащей ему группы битов, причем один и тот же информационный бит может относиться к различным группам.
Тогда один информационный бит сможет влиять на несколько контрольных и потому информационная емкость слова значительно (можно даже сказать, чудовищно) возрастет.
Остается только выбрать наиболее оптимальное разделение сфер влияния.
Слайд 24ИБ 5
Методы защиты информации в АСОД
Согласно методу помехозащитного кодирования, предложенного
Хеммингом, для того чтобы определить, какие контрольные биты контролируют информационный
бит, стоящий в позиции k, мы должны разложить k по степеням двойки:
Слайд 25ИБ 5
Методы защиты информации в АСОД
На первый взгляд кажется, что
коды Хемминга неэффективны, ведь на 4 информационных бита у нас
приходится 3 контрольных, однако поскольку номера контрольных бит представляют собой степень двойки, то с ростом разрядности кодового слова они начинают располагаться все реже и реже.
Так, ближайший к биту C контрольный бит D находится в позиции 8 (т.е. в трех шагах), зато контрольный бит E отделен от бита D уже на (24 - 23 - 1) = 7 «шагов», а контрольный бит F и вовсе на (25 - 24 - 1) = 15 «шагов».
Слайд 26ИБ 5
Методы защиты информации в АСОД
Таким образом, с увеличением разрядности
обрабатываемого блока, эффективность кодов Хемминга стремительно нарастает:
Слайд 27ИБ 5
Методы защиты информации в АСОД
Слайд 28ИБ 5
Методы защиты информации в АСОД
Слайд 29ИБ 5
Методы защиты информации в АСОД
Алгоритмы коррекции ошибок
Исправлять ошибки
труднее, чем их детектировать или предотвращать. Процедура коррекции ошибок предполагает
два совмещенных процесса:
обнаружение ошибки;
определение места (идентификации сообщения и позиции в сообщении).
После решения этих двух задач исправление тривиально — надо инвертировать значение ошибочного бита.
Слайд 30ИБ 5
Методы защиты информации в АСОД
Код Хэмминга представляет собой блочный
код, который позволяет выявить и исправить ошибочно переданный бит в
пределах переданного блока. Обычно код Хэмминга характеризуется двумя целыми числами, например, (11,7), используемыми при передаче 7-битных ASCII-кодов.
Такая запись говорит, что при передаче 7-битного кода используется 4 контрольных бита (7 + 4 = 11). При этом предполагается, что имела место ошибка в одном бите и что ошибка в двух или более битах существенно менее вероятна. С учетом этого исправление ошибки осуществляется с определенной вероятностью.
Слайд 31ИБ 5
Методы защиты информации в АСОД
Например, пусть возможны следующие правильные
коды (все они, кроме первого и последнего, отстоят друг от
друга на расстояние Хэмминга 4):
00000000
11110000
00001111
11111111
При получении кода 00000111 нетрудно предположить, что правильное значение полученного кода равно 00001111. Другие коды отстоят от полученного на большее расстояние Хэмминга.
Слайд 32ИБ 5
Методы защиты информации в АСОД
Рассмотрим пример передачи кода буквы
s = 0x073 = 1110011 с использованием кода Хэмминга (11,7)
Символами
(*) помечены четыре позиции, где должны размещаться контрольные биты. Эти позиции определяются целой степенью 2 (1, 2, 4, 8 и т.д.). Контрольная сумма формируется путем выполнения операции XОR (исключающее ИЛИ) над кодами позиций ненулевых битов. В данном случае это 11, 10, 9, 5 и 3.
Слайд 33ИБ 5
Методы защиты информации в АСОД
Вычислим контрольную сумму:
Таким образом,
приемник получит код
Слайд 34ИБ 5
Методы защиты информации в АСОД
Просуммируем снова коды позиций ненулевых
битов и получим нуль
Слайд 35ИБ 5
Методы защиты информации в АСОД
Ну а теперь рассмотрим два
случая ошибок в одном из битов посылки, например в бите
7 (1 вместо 0) и в бите 5 (0 вместо 1). Просуммируем коды позиций ненулевых битов еще раз:
В 5-ом бите вместо 1 принят 0, поэтому 5-ый бит не включен в таблицу
Слайд 36ИБ 5
Методы защиты информации в АСОД
В обоих случаях контрольная сумма
равна позиции бита, переданного с ошибкой. Теперь для исправления ошибки
достаточно инвертировать бит, номер которого указан в контрольной сумме.
Понятно, что если ошибка произойдет при передаче более чем одного бита, код Хэмминга при данной избыточности окажется бесполезен.
Слайд 37ИБ 5
Методы защиты информации в АСОД
В общем случае код имеет
N = M + C бит и предполагается, что не
более чем один бит в коде может иметь ошибку. Тогда возможно N+1 состояние кода (правильное состояние и n ошибочных). Пусть М = 4, а N = 7, тогда слово-сообщение будет иметь вид: M4, M3, M2, C3, M1, C2, C1. Теперь попытаемся вычислить значения С1, С2, С3. Для этого используются уравнения, где все операции представляют собой сложение по модулю 2:
С1 = М1 + М2 + М4
С2 = М1 + М3 + М4
С3 = М2 + М3 + М4
Слайд 38ИБ 5
Методы защиты информации в АСОД
Для определения того, доставлено ли
сообщение без ошибок, вычисляем следующие выражения (сложение по модулю 2):
С11 = С1 + М4 + М2 + М1
С12 = С2 + М4 + М3 + М1
С13 = С3 + М4 + М3 + М2
Слайд 39ИБ 5
Методы защиты информации в АСОД
Результат вычисления интерпретируется следующим образом:
Слайд 40ИБ 5
Методы защиты информации в АСОД
В обоих случаях контрольная сумма
равна позиции бита, переданного с ошибкой. Теперь для исправления ошибки
достаточно инвертировать бит, номер которого указан в контрольной сумме.
Понятно, что если ошибка произойдет при передаче более чем одного бита, код Хэмминга при данной избыточности окажется бесполезен.
Слайд 41ИБ 5
Методы защиты информации в АСОД
Одной из старейших схем коррекции
ошибок является двух- и трехмерная позиционная схема Для каждого байта
вычисляется бит четности (бит <Ч>, направление Х). Для каждого столбца также вычисляется бит четности (направление Y. Производится вычисление битов четности для комбинаций битов с координатами (X,Y) (направление Z, слои с 1 до N).
Слайд 42ИБ 5
Методы защиты информации в АСОД
Если при транспортировке будет искажен
один бит, он может быть найден и исправлен по неверным
битам четности X и Y. Если же произошло две ошибки в одной из плоскостей, битов четности данной плоскости недостаточно. Здесь поможет плоскость битов четности N+1. Таким образом, на 512 передаваемых байтов данных пересылается около 200 бит четности.
Слайд 43ИБ 5
Методы защиты информации в АСОД
Позиционная схема коррекции ошибок
Слайд 44ИБ 5
Методы защиты информации в АСОД
К сожалению, коды Хемминга способны
исправлять лишь одиночные ошибки, т.е. допускают искажение всего лишь одного
сбойного бита на весь обрабатываемый блок.
Естественно, с ростом размеров обрабатываемых блоков увеличивается и вероятность ошибок. Поэтому выбор оптимальной длины кодового слова является весьма нетривиальной задачей, как минимум требующей знания характера и частоты возникновения ошибок используемых каналов передачи информации.
В частности, для ленточных накопителей, лазерных дисков, винчестеров и тому подобных устройств коды Хемминга оказываются чрезвычайно неэффективными.
Слайд 45ИБ 5
Методы защиты информации в АСОД
Зачем же тогда мы их
рассматривали?
А затем, что понять прогрессивные системы кодирования (к которым в
том числе относятся и коды Рида-Соломона), ринувшись атаковать их «с нуля», практически невозможно, ибо они завязаны на сложной, действительно высшей математике,
Слайд 46ИБ 5
Методы защиты информации в АСОД
Коды Рида-Соломона
Коды Рида-Соломона были предложены
в 1960 году Ирвином Ридом (Irving S. Reed) и Густавом
Соломоном (Gustave Solomon), являвшимися сотрудниками Линкольнской лаборатории Массчусетского Технологического Института.
Коды Рида-Соломона также базируются на блочном принципе коррекции ошибок и используются в огромном числе приложений в сфере цифровых телекоммуникаций и при построении запоминающих устройств.
Коды Рида-Соломона применяются для исправления ошибок во многих системах:
Слайд 47ИБ 5
Методы защиты информации в АСОД
устройствах памяти (включая магнитные ленты,
CD, DVD, штриховые коды, и т.д.);
беспроводных или мобильных коммуникациях
(включая сотовые телефоны, микроволновые каналы и т.д.);
спутниковых коммуникациях;
цифровом телевидении / DVB (digital video broadcast);
скоростных модемах, таких как ADSL, xDSL и т.д.
Слайд 48ИБ 5
Методы защиты информации в АСОД
Что такое коды Рида-Соломона
Коды Рида-Соломона
– недвоичные совершенные систематические линейные блочные коды, относящиеся к классу
циклических кодов с числовым полем, отличным от GF(2), и являющиеся подмножеством кодов Боуза-Чоудхури-Хоквингема.
Корректирующие способности кодов Рида-Соломона напрямую зависят от количества контрольных байт.
Добавление r контрольных байт позволяет обнаруживать r произвольным образом искаженных байт, гарантированно восстанавливая r/2 байт из них.
Слайд 49ИБ 5
Методы защиты информации в АСОД
Схема коррекции ошибок Рида-Соломона
Слайд 50ИБ 5
Методы защиты информации в АСОД
Кодировщик Рида-Соломона берет блок цифровых
данных и добавляет дополнительные "избыточные" биты.
Ошибки происходят при передаче по
каналам связи или по разным причинам при запоминании (например, из-за шума или наводок, царапин на CD и т.д.).
Декодер Рида-Соломона обрабатывает каждый блок, пытается исправить ошибки и восстановить исходные данные.
Число и типы ошибок, которые могут быть исправлены, зависят от характеристик кода Рида-Соломона.
Слайд 51ИБ 5
Методы защиты информации в АСОД
Код Рида-Соломона специфицируются как RS(n,k)
s-битных символов.
Это означает, что кодировщик воспринимает k информационных символов
по s битов каждый и добавляет символы четности для формирования n символьного кодового слова. Имеется nk символов четности по s битов каждый.
Декодер Рида-Соломона может корректировать до t символов, которые содержат ошибки в кодовом слове, где 2t = n–k.
Слайд 52ИБ 5
Методы защиты информации в АСОД
Структура кодового слова R-S
Слайд 53ИБ 5
Методы защиты информации в АСОД
Пример. Популярным кодом Рида-Соломона является
RS(255, 223) с 8-битными символами. Каждое кодовое слово содержит 255
байт, из которых 223 являются информационными и 32 байтами четности. Для этого кода
n = 255, k = 223, s = 8
2t = 32, t = 16
Декодер может исправить любые 16 символов с ошибками в кодовом слове: то есть ошибки могут быть исправлены, если число искаженных байт не превышает 16.
При размере символа s, максимальная длина кодового слова (n) для кода Рида-Соломона равна
n = 2s – 1.
Например, максимальная длина кода с 8-битными символами (s = 8) равна 255 байтам.
Слайд 54ИБ 5
Методы защиты информации в АСОД
Если говорить упрощенно, то основная
идея помехозащитного кодирования Рида-Соломона заключается в умножении информационного слова, представленного
в виде полинома D, на неприводимый полином G3, известный обеим сторонам, в результате чего получается кодовое слово C, опять-таки представленное в виде полинома.
Слайд 55ИБ 5
Методы защиты информации в АСОД
Декодирование осуществляется с точностью до
наоборот: если при делении кодового слова C на полином G
декодер внезапно получает остаток, то он может рапортовать наверх об ошибке. Соответственно, если кодовое слово разделилось нацело, его передача завершилась успешно
Слайд 56ИБ 5
Методы защиты информации в АСОД
В отличие от кодов Хемминга,
коды Рида-Соломона могут исправлять любое разумное количество ошибок при вполне
приемлемом уровне избыточности. За счет чего это достигается?
В кодах Хемминга контрольные биты контролировали лишь те информационные биты, что находятся по правую сторону от них и игнорировали всех «левосторонних» товарищей. В кодах же Рида-Соломона контрольные биты распространяют свое влияние на все информационные биты и потому с увеличением количества контрольных бит увеличивается и количество распознаваемых/устраняемых ошибок.
