<<
>>

Надежность кодирования данных

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

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

Память объемом 1 Мбайт содержит 8 388 608 бит, таким образом, среднее время появления ошибки для этого объема составляет примерно 1/8 года, или 45 дней. Если учесть, что в стандартной комплектации современных компьютеров объем оперативной памяти не менее 128 Мбайт, то этот фактор приводит к искажению в среднем трех битов в день. Такая высокая вероятность появления ошибки в кодах данных уже не является допустимой. На сегодняшний день не существует экономически оправданных технических способов защиты памяти от ос-излучения. Неустранимые проблемы искажения информации возникают и при хранении данных на магнитных и оп- тических дисках с высокой плотностью, а также при их передаче по линиям свя- зи с высокими посторонними шумами.

Вместе с тем, применяя специальные методы кодирования, можно обеспечить контроль за появлением ошибки и даже восстановление исходного кода после ее обнаружения. Применение этих методов позволяет понизить вероятность появ- ления ошибки до 1О^9 и ниже.

Общим методом обеспечения надежности хранения и передачи данных в компью- тере и по линиям связи является включение в код дополнительных контрольных разрядов (битов). Существует много различных вариантов этого метода. Под- робное их рассмотрение в рамках данного учебника невозможно, поэтому далее обсуждаются только наиболее распространенные способы.

Во многих компьютерах одним из уровней контроля за появлением ошибок является включение в байт дополнительного, контрольного девятого разряда, который формируется аппаратурой автоматически. А те восемь битов, из кото- рых, как мы до сих пор считали, состоит байт, в дальнейшем будем называть информационными. Значение контрольного разряда определяется так, чтобы об- щее количество разрядов байта (всех информационных и контрольного), которые содержат 1, было нечетным. Рассмотрим, например, байт с информационными битами 1001 11102. Количество единиц в нем нечетно, следовательно, аппаратура сформирует значение контрольного бита, равное 0. При этом общее количество единиц в девяти битах байта останется нечетным. А, например, для байта с ин- формационными битами 1001 01102, количество единиц в котором четное, кон- трольный бит окажется равным 1 — в результате образуется нужное нечетное количество единиц.

На рис. 2.15 приведены примеры байтов с отмеченным буквой К контрольным битом. Байты на рис. 2.15, а не содержат ошибок. Контрольный бит содержит О или 1, так что общее количество единиц нечетное. В то же время байты на рис. 2.15, б содержат ошибочные коды.

Рис. 2.15. Байты с контрольными битами: а — без ошибок; 6 — содержащие ошибку

Процессор во время выполнения любых действий контролирует общее количе- ство единиц в байте по всем девяти битам и в случае нарушения требования его нечетности либо блокирует дальнейшую работу, либо принимает специальные меры по восстановлению верного значения кода, выполняя, например, повтор- ную передачу или организуя повторное выполнение действия, приведшего к по- явлению ошибки.

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

Теоретические соображения показывают, что ошибки могут быть не только оди- ночными. Существует ненулевая вероятность появления кратных ошибок, когда одновременно появляется два и больше сбойных битов в одном байте. В связи с этим следует уточнить возможности одиночного контрольного разряда. Если суммарное количество единиц в байте при использовании одного контрольного разряда оказалось четным, то можно утверждать только, что имеется нечетное (1,3, 5 или 7) количество одновременно появившихся в байте ошибочных битов. Поскольку вероятность одновременного появления трех (а тем более пяти или семи) ошибочных битов в одном и том же байте ничтожно мала, на практике считают, что имеется только один сбойный бит.

Кроме введения контрольного разряда существуют и более развитые способы кодирования, которые не только позволяют установить факт появления ошибок большой кратности, но и обеспечивают их исправление. К таким способам отно- сятся коды, принцип построения которых в 1948 г. предложил Р. Хемминг.

Проиллюстрируем общую идею построения кодов Хемминга на простом приме- ре. Пусть имеется исходный 4-битный код 11002. Чтобы не только обнаружить, но и исправить вероятную одиночную ошибку, предлагается каждую тройку би- тов снабдить одним контрольным разрядом. Количество различных троек, кото- рые могут быть выбраны из четырех битов, равно числу сочетаний из четырех по три: С4=4 Однако теоретический анализ показывает, что можно ограничиться любыми тремя тройками. Количество единиц в каждой группе (тройка битов вместе с контрольным разрядом) должно быть нечетным. На рис. 2.16, а изо- бражены исходный код и значения контрольных битов А, В и С в каждой вы- бранной тройке.

Рис. 2:16. Исправление ошибочного бита: а — код без ошибки; б — с единичной ошибкой

Если во время выполнения действий один из битов окажется искаженным, то во всех группах, в которые входит ошибочный бит, контроль нечетности покажет наличие ошибки. Следовательно, для определения положения ошибочного бита в коде достаточно выбрать разряд, входящий во все группы, в которых наруше- на нечетность. В примере на рис. 2.16 только в группе, контролируемой битом А, общее количество единиц нечетное, в то время как значения контрольных битов В и С (на рисунке эти биты подчеркнуты) сигнализируют о наличии ошибки в их группах. Ошибочный бит должен принадлежать одновременно двум послед- ним группам. Такой бит всего один — это третий по счету бит, отмеченный на рис. 2.16 кружком. После определения положения сбойного бита исправление кода осуществляется его инвертированием.

Теперь рассмотрим предложенный Р. Хеммингом общий порядок построения кодов, обеспечивающий однозначное обнаружение и исправление ошибок в ко- дах данных. Он включает в себя следующие действия.

1. Контрольные биты вставляются в исходный код и нумеруются совместно с ин- формационными битами слева направо начиная с 1.

2. Контрольные биты располагаются в позициях с номерами n = 2А, k = 0, 1,2, 3... объединенного кода, то есть в позициях с номерами n = 1, 2, 4, 8, 16...

3. Для каждого контрольного разряда с номером n весь код делится на группы, состоящие из 2n битов.

4. Контрольный бит с номером n контролирует в группе первые n подряд распо- ложенных битов кода (для первой группы, включая контрольный) с пропус- ком следующих n битов.

5. В каждой группе контрольный бит формируется так, чтобы общее количество единиц в ней было нечетным.

Рис.

2.17. Схема построения кода Хемминга

На рис. 2.17, а изображено 32-битное поле, для которого строится код Хемминга. Как показано далее, чтобы иметь возможность исправлять ошибки, в занимающий это поле код необходимо включить шесть контрольных разрядов. На рис. 2.17, б контрольные биты закрашены серым цветом, а внизу показана используемая в ко- дах Хемминга нумерация разрядов поля. В качестве примера формирования кон- тролируемой группы битов на рис. 2.17, в выделены разряды, которые контроли- руются четвертым контрольным битом. Группы битов, закрепленных за первыми четырьмя контрольными разрядами, представлены в табл. 2.8.

Таблица 2.8. Закрепление информационных битов за контрольными Контрольный бит Контролируемые биты

1 1, 3, 5, 7, 9, И, 13, 15, 17, 19, 21, 23, 25, 27, 29...

2 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27...

4 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31...

8 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31...

Для определения ошибочного бита важно знать не какие информационные биты относятся к данному контрольному, а какие контрольные биты закреплены за данным информационным. Анализ показывает, что в общем случае информаци- онный бит с номером b проверяется контрольными битами с номерами bь b2,..., bk такими, что b = bx + b2 + ... + bk. Это значит, что номер ошибочного бита равен сумме номеров контрольных битов, обнаруживших ошибку.

Рассмотрим пример построения кода Хемминга и исправления одиночной ошиб- ки для 16-битного кода. Из приведенных далее оценок следует, что для исправ- ления ошибки в таком коде необходимо пять контрольных разрядов. На рис. 2.18, я изображен исходный 16-битный код 1111 0111 1001 01112, а на рис. 2.18, б — по- строенный для него код Хемминга, состоящий из 21 бита. Определение значений контрольных битов проиллюстрировано в табл. 2.9: для каждого контрольного бита выписываются все информационные биты, за которые он отвечает, и в них подсчитывается общее количество единиц.

Если оно четно, то значение бита должно быть равно 1, в противном случае — 0.

Рис. 2.18. Определение номера ошибочного бита

Таблица 2.9. Формирование значения контрольного бита

Контрольный Контролируемые биты Количество Значение

бит единиц бита

Если в такой код в результате выполнения каких-либо действий попала ошибка, то для определения номера сбойного бита достаточно сложить номера кон- трольных битов, в группах которых отсутствует нужная четность. Например, на рис. 2.18, в ошибочна четность в группах первого и четвертого контрольных битов, — следовательно, ошибочен пятый бит кода.

Количество контрольных разрядов, которые должны быть включены в код, зависит от цели создания кода: предназначен он только для факта обнаружения ошибки или с его помощью должен быть восстановлен исходный код. Кроме того, необхо- димо принимать во внимание допустимую кратность ошибки. Определение мини- мально необходимого для заданных условий количества контрольных разрядов базируется на понятии интервала Хемминга, а он равен количеству битовых по- зиций, в которых два кода отличаются друг от друга. Возьмем, например, коды 1000 11012 и 0101 10012. Они различаются цифрами, находящимися во втором, чет- вертом, шестом и седьмом разрядах (использован стандартный для байта способ нумерации — слева направо, начиная с нуля). Таким образом, интервал Хемминга d для этих двух кодов равен 4. Интервал Хемминга двух кодов показывает, сколько требуется одновременных однобитовых ошибок, чтобы превратить один код в другой.

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

Если исходный код содержит т информационных разрядов и к нему добавляет- ся k контрольных, то полный код состоит из т + k разрядов. В полном коде из 2m+k возможных кодов допустимыми будут только 2m кодов, так как значения контрольных битов однозначно зависят от значений информационных. Таким об- разом, количество недопустимых кодов равно 2m+k - 2m.

На рис. 2.19 приведены примеры построения контрольных разрядов (цветом вы- делены 1-й, 2-й и 4-й разряды полного кода Хемминга) для исходных кодов 00002 и 10002. Первые семь полных кодов недопустимы, так как указанные в них значе- ния контрольных разрядов не обеспечивают нечетность количества единиц хотя бы в одной из групп (1-, 3-, 5- и 7-й; 2-, 3-, 6- и 7-й; 4-, 5-, 6- и 7-й разряды). Для кода 00002 допустим только один полный код 11010002, содержащий 1 во всех контрольных разрядах. Далее указано несколько построенных по точно такому же принципу допустимых и недопустимых полных кодов для исходного кода 10002.

Рис. 2.19. Допустимые коды Хемминга

Зная способ заполнения контрольных разрядов для любого набора информаци- онных битов, можно построить полный список допустимых кодов и найти в этом списке два кода с наименьшим интервалом Хемминга. Этот интервал называется интервалом Хемминга полного кода.

Анализ зависимости информационных битов для предыдущего примера (см. рис. 2.18 и табл. 2.9) m = 16, ⅛ = 5, /г = 21 показывает, что любой информацион- ный бит кода контролируется не менее чем двумя контрольными. Если возника- ет изменение в единственном информационном бите, то для допустимости ново- го полного кода должны измениться еще по крайней мере два контрольных бита. Другими словами, интервал Хемминга полного кода в данном примере равен 3.

Получим теперь нижнюю оценку количества контрольных битов, которые необ- ходимы для исправления одиночной ошибки у m-разрядного слова. Каждому из 2т допустимых кодов можно сопоставить ровно n недопустимых кодов, которые образуются из допустимого полного кода с ровно одним инвертированным битом (рассматриваются только одиночные ошибки). Умножая 2т на n + 1, получаем общее количество кодов, не содержащих ошибок вообще или же содержащих единственную ошибку. Очевидно, что могут быть полные коды с двумя и боль- шим количеством ошибок в k контрольных разрядах (см. рис. 2.18). Следова- тельно, число (п + 1) ∙ 2m должно быть меньше, чем общее количество полных ко- дов 2m+k: (п + 1) ∙ 2m < 2m+k. Преобразуя это неравенство, получим: т + k + 1 < 2k, откуда 2k - k > т + 1. Следовательно, минимальное количество контрольных разрядов ⅛, которые должны быть включены для исправления единичной ошибки в исходный код из т разрядов, должно удовлетворять неравенству 2k - k>m+ 1.

В табл. 2.10 приведены рассчитанные по этому неравенству количества контроль- ных битов k для исходного кода длиной т, чтобы полученный при этом полный код Хемминга мог исправлять одиночную ошибку. В этой же таблице приведены длина полного кода Хемминга /w + k и относительное увеличение длины исход- ного кода L = т/{т + k) за счет включения в него контрольных разрядов. Хоро- шо видно, что уже для кодов с исходной длиной т > 128 относительное увеличе- ние длины не превышает 6%, что можно считать вполне приемлемой платой за возможность автоматически исправлять ошибки.

Таблица 2.10. Разрядность кодов Хемминга для исправления одиночной ошибки

Более общий анализ показывает, что для обнаружения 5 ошибок необходим код с полным интервалом d = S + 1, а для исправления 5 ошибок необходим код с полным интервалом d = 25 + 1.

Методы построения кодов Хемминга и некоторых других, более мощных способов кодирования широко используются в различных устройствах памяти компьюте- ра. В частности, на этих методах основан аппаратный механизм контроля опера- тивной памяти ЕСС (Error Checking and Correcting — контроль и исправление ошибок), который является дополнительным средствам обеспечения высокой ее помехоустойчивости.

Дополнительный материал по обсуждавшимся в главе вопросам можно найти в из- даниях [3], [7], [10], [17], [29].

<< | >>
Источник: Степанов А. Н.. Архитектура вычислительных систем и компьютерных сетей. 2007

Еще по теме Надежность кодирования данных:

  1. 2.6. Правила кодирования
  2. Положительное кодирование.
  3. ПРИНЦИП КОДИРОВАНИЯ СПЕЦИФИЧЕСКОГО
  4. НАДЕЖНОСТЬ
  5. СХЕМЫ ВОЗДЕЙСТВИЯ ПРИ КОДИРОВАНИИ ЧЕЛОВЕКА
  6. 14. НАДЕЖНЫЙ ЧЕЛОВЕК
  7. 14. НАДЕЖНЫЙ ЧЕЛОВЕК
  8. ОПЕРАТОР: НАДЕЖНОСТЬ
  9. СИСТЕМА «ЧЕЛОВЕК - МАШИНА»: НАДЕЖНОСТЬ
  10. О том, как ненадежны надежные пути
  11. КОГДА ЖЕНЩИНА НЕ ЧУВСТВУЕТ СЕБЯ НАДЕЖНО В СВОЕМ КОЛОДЦЕ
  12. Прием избирательности и надежности психологического наблюдения.
  13. Григорьев Ю.А., Ревунков Г.И.. Банки данных, 2002