uzluga.ru
добавить свой файл


Устройства хранения информации


Двоичная система

  • Память - это часть компьютера, где хранятся программы и данные.

  • Основной единицей памяти является двоичный разряд - бит.

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



Адреса

  • Память состоит из ячеек, каждая из которых может хранить некоторую порцию информации.

  • Каждая ячейка имеет номер, который называется адресом.

  • Все ячейки памяти содержат одинаковое число битов. Адреса также представляют из себя двоичное число. Количество битов в адресе определяет максимальное число адресованных ячеек, что в совокупность с размером ячейки определяет максимальный объем адресуемой памяти.





Машинное слово

  • Ячейка - минимальная единица к которой можно обращаться.

  • Большинство современных машин оперирует с 8-битными ячейками памяти. 8 бит = 1 байт.

  • Байты формируют слова. Слово - максимальная единица памяти с которой оперирует большинство команд машины.

  • Например, 32-битная машина содержит 32-битные регистры и манипулирует с машинными словами из 4 байт, 64-битная соответственно содержит 64-битные регистры и манипулирует со словами из 8 байт.



Порядок байт

  • Байты в словах могут нумероваться слева направо или справа налево. Кажется, что никакой разницы в это нет, но на самом деле это не так!





Проблема

  • Если мы попробуем скопировать такие данные по одному байту с одной машины на другую, то вместо номера 495 получится номер 4009820160

  • (11101111 00000001 00000000 00000000). Простого решения у этой проблемы не существует!



Ошибки

  • Память компьютера время от времени может делать ошибки из-за всплесков напряжения на линии электропередачи или по другим причинам. Для борьбы с такими ошибками используются коды с обнаружением и исправлением ошибок. При этом к каждому слову в памяти особым образом добавляются дополнительные биты. Когда слово считывается из памяти, эти биты проверяются на наличие ошибок.



Допустим, что слово состоит из m бит данных, к которым мы добавляем r бит контрольных разрядов. Тогда единицу размером n бит (n = m + r), содержащую m бит данных и r бит контрольных разрядов, будем называть кодированным словом.

  • Допустим, что слово состоит из 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 изменениях кодированное слово будет ближе к изначальному, чем к какому-либо другому слову).



Примеры



Алгоритм для обнаружения и исправления одиночной ошибки

  • Попробуем придумать алгоритм для обнаружения и исправления одиночной ошибки в произвольном коде при параметрах n = m + r.

  • Для каждого из 2m допустимых значений кода есть n возможных одиночных ошибок => n + 1 сочетание на слово.

  • (n + 1)*2m должно быть ≤ 2n (чтобы каждая ошибка была уникальной комбинацией и мы могли бы разгадать ее изначальное представление)

  • =>

  • (m+r+1) ≤ 2r.

  • Таким образом мы получаем нижний предел числа контрольных разрядов.



Значения нижнего предела



Метод Ричарда Хэмминга Диаграмма Вена