Устройства хранения информации Кэш - память Основная память Магнитный (жесткий) диск Регистры Оптические носителиМагнитные носители

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

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

бит 12 бит 16 бит 1 ячейка Адреса Пример: три способа организации 96-битной памяти

Машинное слово Ячейка - минимальная единица к которой можно обращаться. Большинство современных машин оперирует с 8-битными ячейками памяти. 8 бит = 1 байт. Байты формируют слова. Слово - максимальная единица памяти с которой оперирует большинство команд машины. Например, 32-битная машина содержит 32- битные регистры и манипулирует с машинными словами из 4 байт, 64-битная соответственно содержит 64-битные регистры и манипулирует со словами из 8 байт.

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

локш0 она4 рем школ 4ано 8мер Нумерация справа налево Нумерация слева направо (прямой порядок) Попробуем представить как будет храниться фраза школа номер 495 в памяти. При этом пусть число 495 представлено в виде int: ( )

Проблема Если мы попробуем скопировать такие данные по одному байту с одной машины на другую, то вместо номера 495 получится номер ( ). Простого решения у этой проблемы не существует!

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

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

Смысл интервала Хэмминга Если интервал Хэмминга для двух слов равен d, это значит, что достаточно d битовых ошибок, чтобы превратить одно слово в другое. Пример: XOR = => d = 3

Интервал Хэмминга полного кода Для памяти из m-битных слов существует 2 m вариантов сочетания битов. Кодированные слова состоят из n битов, но из-за способа подсчета контрольных разрядов допустимы только 2 m из 2 n комбинаций. Если получилось значение с недопустимой комбинацией контрольных разрядов, то сразу известно, что произошла ошибка. Зная алгоритм подсчета контрольных разрядов, мы можем найти все возможные комбинации кодированных слов и вычислить для них минимальный интервал Хэмминга. Т.е. выбрать минимум из всех интервалов Хэмминга для каждой пары кодированных слов. Этот интервал назовем интервалом Хэмминга полного кода.

Смысл интервала Хэмминга полного кода От этой величины зависят свойства проверки и исправления ошибок кода. Чтобы обнаружить d ошибок в битах необходим код с интервалом Хэмминга d + 1 (так как d ошибок не смогут изменить одно допустимое слово на другое). Соответственно, чтобы исправить d ошибок надо чтобы интервал Хэмминга кода был 2d + 1 (так как даже при d изменениях кодированное слово будет ближе к изначальному, чем к какому-либо другому слову).

Примеры Пример 1: код с битом четности. Пример 2: код с четырьмя возможными значениями d = 2 => можем обнаружить одиночную ошибку d = 5 => можем обнаружить до 4-х ошибок и исправить две.

Алгоритм для обнаружения и исправления одиночной ошибки Попробуем придумать алгоритм для обнаружения и исправления одиночной ошибки в произвольном коде при параметрах n = m + r. Для каждого из 2 m допустимых значений кода есть n возможных одиночных ошибок => n + 1 сочетание на слово. (n + 1)*2 m должно быть 2 n (чтобы каждая ошибка была уникальной комбинацией и мы могли бы разгадать ее изначальное представление) => (m+r+1) 2 r. Таким образом мы получаем нижний предел числа контрольных разрядов.

Значения нижнего предела Размер слова Количество контрольных разрядов Общий размер %-ное увеличение длины слова

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