Допустим, что слово состоит из m бит данных, к которым мы добавляем r бит контрольных разрядов. Тогда единицу размером n бит (n = m + r), содержащую m бит данных и r бит контрольных разрядов, будем называть кодированным словом.
Для любых двух слов можно определить, сколько соответствующих битов в них различается. Для этого применяется операция XOR и считается кол-во единиц в результате.
Число битовых позиций по которым различаются два слова называется интервалом Хэмминга.
Смысл интервала Хэмминга
Если интервал Хэмминга для двух слов равен d, это значит, что достаточно d битовых ошибок, чтобы превратить одно слово в другое.
Пример:
11110001 XOR
00110000 = 11000001 => d = 3
Интервал Хэмминга полного кода
Для памяти из m-битных слов существует 2m вариантов сочетания битов. Кодированные слова состоят из n битов, но из-за способа подсчета контрольных разрядов допустимы только 2m из 2n комбинаций. Если получилось значение с недопустимой комбинацией контрольных разрядов, то сразу известно, что произошла ошибка.
Зная алгоритм подсчета контрольных разрядов, мы можем найти все возможные комбинации кодированных слов и вычислить для них минимальный интервал Хэмминга. Т.е. выбрать минимум из всех интервалов Хэмминга для каждой пары кодированных слов. Этот интервал назовем интервалом Хэмминга полного кода.
Смысл интервала Хэмминга полного кода
От этой величины зависят свойства проверки и исправления ошибок кода.
Чтобы обнаружить d ошибок в битах необходим код с интервалом Хэмминга d + 1 (так как d ошибок не смогут изменить одно допустимое слово на другое).
Соответственно, чтобы исправить d ошибок надо чтобы интервал Хэмминга кода был 2d + 1 (так как даже при d изменениях кодированное слово будет ближе к изначальному, чем к какому-либо другому слову).
Примеры
Пример 1: код с битом четности.
d = 2 => можем обнаружить одиночную ошибку
Пример 2: код с четырьмя возможными значениями.
0000000000
0000011111
1111100000
1111111111
d = 5 => можем обнаружить до 4-х ошибок и исправить две.
Алгоритм для обнаружения и исправления одиночной ошибки
Попробуем придумать алгоритм для обнаружения и исправления одиночной ошибки в произвольном коде при параметрах n = m + r.
Для каждого из 2m допустимых значений кода есть n возможных одиночных ошибок => n + 1 сочетание на слово.
(n + 1)*2m должно быть ≤ 2n (чтобы каждая ошибка была уникальной комбинацией и мы могли бы разгадать ее изначальное представление)
=>
(m+r+1) ≤ 2r.
Таким образом мы получаем нижний предел числа контрольных разрядов.
Значения нижнего предела
Размер слова |
Количество |
Общий |
%-ное |
|
контрольных |
размер |
увеличение |
|
разрядов |
|
длины слова |
8 |
4 |
12 |
50 |
16 |
5 |
21 |
31 |
32 |
6 |
38 |
19 |
64 |
7 |
71 |
11 |
128 |
8 |
136 |
6 |
256 |
9 |
265 |
4 |
512 |
10 |
522 |
2 |
Метод Ричарда Хэмминга
Диаграмма Вена
|
0 |
0 |
1 |
|
|
|
|
1
1 0
1
Виртуальная память – воображаемая память, по объёму равная максимально адресуемой памяти.
•Главная идея виртуальной памяти – использовать внешнюю память как продолжение основной.
Далее…
•Диск
•Страничная организация памяти
•Анализ страничной организации
•Буфер быстрого преобразования адреса
•Сегментная организация
•Выводы