Контроль и защита информации

5.3 Контроль и защита информации

       При хранении информации в БИС ЗУ возникают ошибки. Обычно причиной ошибки является альфа-частица - ядро атома гелия (состоящего из двух протонов и двух нейтронов), испущенное ядром тяжелого атома в результате радиоактивного распада. Альфа-частицы - отрицательный фактор, присущий устройствам памяти современных ЭВМ, поскольку радиоактивные ядра в небольших количествах присутствует почти во всех материалах. В частности атомы урана и тория содержатся в пластмассовых корпусах обычных микросхем памяти. Таким образом,  ячейки памяти (кристалл ЗУ) подвергаются постоянной бомбардировке. Поэтому случайные ошибки (сбои) нельзя предотвратить. Когда a-частица проникает через потенциальную яму, электроны покидают те места, которые они прежде занимали в кристаллической решетке кремния и попадают в близлежащие потенциальные ямы. Если яма была заполнена электронами (т.е. в запоминающем элементе хранится 0), то это не приводит не к каким последствием. Если же потенциальная яма первоначально была пустой (т.е. в запоминающем элементе хранилась 1), то может возникнуть ошибка: 1 может превратиться в 0. Часто ли возникают такие ошибки? Среднее время до возникновения сбоя для одного запоминающего элемента в БИС очень велико. Обычно значение этого показателя превосходит миллион лет. Однако память ЭВМ также состоит из миллионов ЗЭ. Это означает, что в целом для запоминающего устройства среднее время до возникновения сбоя не так уж и велико. Предположим, что среднее время до появления ошибки для одного ЗЭ составляет 1000000 лет. Тогда среднее время до появления ошибки в устройстве памяти в 1Мбайт будет равно миллиону лет, поделённому на 8388608 и составит приблизительно 43 дня.  1Мбайт=8388608 бит.  43 дня не так уж много. Эффективного способа защиты памяти от a-частиц не существует. Однако в некоторых ситуациях лучше исправить уже возникшие ошибки, чем пытаться их предотвратить.

       Контроль информации основан на  введении информационной избыточности. Если разрядность слова данных равна n и добавляется k контрольных разрядов, то полная длина кодовой комбинации равна n+k  разрядов. Для контроля информации широко используют код с проверкой на чётность. Этот код имеет небольшую избыточность, поскольку добавляется только один контрольный разряд - бит чётности. Содержимое этого бита подбирается таким образом, чтобы среди получившихся n+1 разрядов обязательно было четное число единиц. Контроль на чётность обнаруживает одиночные ошибки и нечётное количество ошибок.

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

                                                     .

       В коде Хэмминга биты n+k  - разрядного слова нумеруются слева направо, начиная с 1. Контрольные разряды, содержащие биты чётности имеют номера  2,где s=0,1,2,…,k-1.

       Каждый бит чётности используется для контроля только определённых разрядов расширенного слова данных.                                        

       Совокупности разрядов для каждого бита  чётности обозначают Е. Множества Е ещё называют проверочными группами. Номера разрядов составляющих проверочные группы Е(s=0,1,2…,k-1) имеют цифру 1 на s-м месте в своем двоичном представлении. Образование групп Е для n=16 и k=5 показано в таблице ниже. Разряд 1-й контролирует группу Е, 2-й разряд контролирует группу Е, 4-й разряд - группу Е, 8-й-группу Е, 16-группу Е.

Номера Рекомендуемые материалы 9 lab вариант 13 Программирование 500 руб. ЛР2- 22Р (граф Ашкинузе) Отчет + код Программирование графических приложений (ПГП) 500 руб. 6 lab вариант 13 Программирование 400 руб. объектно-ориентированное программирование Объектно-ориентированное программирование (ООП) 200 руб. FREE РК2 по инфе Информатика FREE Справочные материалы для выполнения лабораторных и контролируемых самостоятельных работ Метрология, стандартизация и сертификация (МСиС) разрядов слова	S	Проверочные группы по Хэммингу.
4	3	2	1	0
1	0	0	0	0	1	Е= 1,3,5,7,9,11,13,15,17,                 19,21,23,25.…                                Е=      2,3,6,7,10,11,14,15,                 18,19,22,23,26,27...      Е=     4,5,6,7,12,13,14,15,                  20,21,22,23,28...   Е=      8,9,10,11,12,13,14,15,                  24,25,26,27,28…  Е=      16,17,18,19,20,21…
2	0	0	0	1	0
3	0	0	0	1	1
4	0	0	1	0	0
5	0	0	1	0	1
6	0	0	1	1	0
7	0	0	1	1	1
8	0	1	0	0	0
9	0	1	0	0	1
10	0	1	0	1	0
11	0	1	0	1	1
12	0	1	1	0	0
13	0	1	1	0	1
14	0	1	1	1	0
15	0	1	1	1	1
16	1	0	0	0	0
17	1	0	0	0	1
18	1	0	0	1	0
19	1	0	0	1	1
20	1	0	1	0	0
21	1	0	1	0	1

       Сбой (искажение) состоит в инвертировании хотя бы одного бита исходных n-разрядных данных.

       Из закона формирования проверочных групп следует, что позиции 2={1,2,4, 8, …} встречаются только в одной из  k проверочных групп. Поэтому именно эти позиции берут в качестве контрольных. Позиции 1,2,4,8… являются первыми в проверочных группах и в них записывают биты чётности. В число проверяемых разрядов включается и тот разряд, где расположен сам бит чётности. При этом содержимое бита чётности устанавливается так, чтобы суммарное число единиц в проверяемых  им разрядах было чётным. При контроле с помощью кода Хэмминга формируют проверочное число содержащие  k разрядов. Код передан правильно, если соответствующее ему проверочное число равно нулю. При сбоях четность в некоторых проверочных группах Е нарушается. Тогда в разряды  проверочного числа, номера которых равны номерам нарушенных по чётности проверочных групп, ставятся единицы. В остальных разрядах проверочного числа  остаются нули. Ненулевое значение проверочного числа указывает на номер разряда расширенного кода данных, в котором произошла ошибка.

  Пример.                           n=16        k=5 

Информация в лекции "12 Реализация цифровых фрагментов" поможет Вам.

Нумерация битов кода Хэмминга для 16-разрядного слова данных.

Нумерация информационных битов 16-разрядного слова.

       Все проверочные группы содержат четное число единиц. Тогда проверочное число будет 00000. Допустим сбой в пятом разряде. Тогда чётность нарушается в группах, в которые этот разряд входит; Е и Е. При этом проверочное число 00101. Первый и четвертый биты четности будут неправильными.  Если ошибка в 20 разряде, то чётность нарушится в группах  Е и Е. Проверочное число  10100=20.Четвертый и 16-й биты чётности будут неправильными.

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

       Существуют специальные электронные устройства, которые  осуществляют кодирование и декодирование в коде Хэмминга.