Контроль и защита информации
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-группу Е
.
| Номера Рекомендуемые материалыFREE РК2 по инфе РК3. Вариант №11 -50% Ознакомительная Практика (ОП1) Вариант Н26 Практика ООП Берчун РК6 Ответы на Аттестацию официального партнера amoCRM 2023 Вариант 11 - Отчёт по практике №2 разрядов слова | S | Проверочные группы по Хэммингу. | |||||||||||||||||
| 4 | 3 | 2 | 1 | 0 | |||||||||||||||
| 1 | 0 | 0 | 0 | 0 | 1 |
19,21,23,25.…
18,19,22,23,26,27...
20,21,22,23,28...
24,25,26,27,28…
Е | |||||||||||||
| 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-й биты чётности будут неправильными.
Если происходит одиночная ошибка, то код Хэмминга позволяет её обнаружить и исправить, т.е. проинвертировать содержимое бита в котором произошла ошибка. Если изменение информации произойдет в двух разрядах, то код Хэмминга позволит только обнаружить ошибку, но исправить её нельзя. Однако вероятности появления в одном слове данных двух и более ошибок значительно меньше, чем вероятность одной ошибки.
Существуют специальные электронные устройства, которые осуществляют кодирование и декодирование в коде Хэмминга.
