Корректирующие коды
Корректирующими называются коды, которые
позволяют обнаруживать ошибки и
исправлять их на приемной стороне, не
прибегая к повторной передаче ошибочных
кодовых комбинаций.
Исходя из основных параметров и способов
кодирования и декодирования, корректирующие
коды в первую очередь можно разделить
на блочные и непрерывные.
Блочные коды характеризуются тем, что
каждая кодовая комбинация состоит из
двух частей (блоков), первая состоит из
информационных символов, вторая – из
контрольных. Особенностью непрерывных
кодов является то, кодовая комбинация
не разделяется на блоки, а контрольные
символы размещаются по определенному
правилу между информационными.
Для корректирующих кодов справедливо
неравенство
N = Km
M,
где М– количество сообщений;N– количество кодовых комбинаций;К– основание кода;
m– длина кодовой
комбинации:m = n
+ k;n– число информационных разрядов,k– число контрольных разрядов,
обеспечивающих локализацию и исправление
искаженных элементов кодовой комбинации.
Число контрольных разрядов, необходимых
для обнаружения и исправления однократных
ошибок, определим путем следующих
рассуждений. При передаче любого из Мсообщений может быть искажен любой изmэлементов кодовой
комбинации или сообщение будет передано
верно. Следовательно, возможныm
+ 1исходов. Используяkконтрольных разрядов необходимо
различить все эти исходы. С помощьюkразрядов можно закодировать 2kисходов. Значит, должно выполняться
условие
Например, если М = 10, то в соответствии
с равенствомM = Knполучаем n
3,3 = 4. Чтобы иметь возможность
обнаруживать ошибочные кодовые комбинации
и исправлять их следует добавитьkконтрольных разрядов в соответствии с
выражением:
При выполнении равенства получим
.
Таким образом, чтобы проверить четыре
информационных разряда, требуется три
контрольных.
При этом избыточность кода составит
Коды обнаруживающие ошибки должны иметь
кодовое расстояние d
= 2. Определим, чему должно равняться
кодовое расстояние у корректирующих
кодов. При этом поставим условие, что в
одной кодовой комбинации не может
возникнуть более одной ошибки. Выражение
для определения кодового расстояния
будет иметь вид:
где α– кратность обнаруживаемых
ошибок,
β– кратность исправляемых ошибок,
1– кодовое расстояние для оптимального
кода;
Рассмотрим эту формулу на примере
равномерного трехразрядного кода.
При α = 0,β = 0 d = 1. Этот результат
соответствует равномерному оптимальному
коду. Его кодовые комбинации:000, 001,
010, 100, 110, 101, 011, 111.
При этом избыточность кода равна
При α = 1,β = 0 d
= 2. Этот результат соответствует
равномерному коду, обнаруживающему
однократную ошибку. Его кодовые
комбинации:001, 010, 101, 110.
При α = 1,β = 1 d
= 3. Этот результат соответствует
равномерному оптимальному коду. Его
кодовые комбинации:000, 111.
Общий алгоритм построения блочных кодов, корректирующих однократные ошибки
В зависимости от требуемой разрядности
кода записывается единичная матрица
(nn)
С помощью этой матрицы можно записать
все комбинации n-разрядного
оптимального кода.
Полученная матрица называется
производящей. Путем суммирования по
модулю 2 строк этой матрицы можно получить
равномерный избыточный код. В этом коде
выделены информационная и сервисная
части, поэтому такой код называется
систематическим.
К матрице Апредъявляются следующие
требования:
Передаваемые кодовые комбинации на
приемной стороне должны быть подвержены
контролю с целью выявления наличия или
отсутствия ошибки в любом месте кодовой
комбинации. Для этого на приемной стороне
используют проверочную матрицу, задача
которой состоит в обнаружении ошибки
и указании ее местоположения.
Проверочная матрица строится следующим
образом: к единичной матрице размером
kkслева приписывается матрица изnстолбцов иkстрок(nk). При этом строка приписываемой матрицы
является столбцом дополнительной
матрицы из матрицыA.
К матрице Ппредъявляется следующее
требование.
Пример: требуется построить систематический
код, позволяющий обнаружить ошибочное
отображение любого числа от 0до9на семисегментном индикаторе и исправить
его.
Согласно условию задачи количество
отображенных чисел (сообщений) М = 10.
Для представления этих чиселn
= 4, k = 3. Составим
производящую матрицу.
Выполняется условие: не менее (d-1)единиц. На основании этой матрицы можно
построить16кодовых комбинаций с
разрядностью
Первые четыре кодовые комбинации – это
строки матрицы А. Последние 6 кодовых
комбинаций являются суммами строк по
модулю 2, соответственно:
,,,,,.
Строим проверочную матрицу
Проверочная матрица показывает, что k0контролирует1,2,3разряды,k1
– 0,2,3разряды,k2 – 0,1,3разряды.
На основании проверочной матрицы можно
составить уравнения кодов-опознавателей
местоположения ошибки:
Последовательность f0
f1 f2– является кодом ошибочной или
безошибочной комбинации
Если кодовая комбинация не содержит
ошибок, то согласно (*) все позиции будут
содержать нули, следовательно, получится
код f0 f1
f2 =
0 0 0.
Рассмотрим подчеркнутую кодовую
комбинацию 1 0 1 0 1 0 1и начнем
последовательно вводить ошибки.
Вводим ошибку в разряд a0
и получаем код опознавателя ошибки
в этом разряде:
,f0 f1
f2 =
0 1 1.
Затем вводим ошибку в разряд а1и получаем код опознавателя ошибки в
этом разряде; затем в вводим ошибкуа2и получаем код опознавателя ошибки в
этом разряде и т.д.
Например, ошибка в разряде а3:
,f0 f1
f2 =
1 1 1
В итоге получаем таблицу кодов
опознавателей ошибок:
Проверим получившийся результат. Пусть
передали комбинацию 1000011, а получили1001011. Определяем код
опознавателя:
следовательно,
ошибка в разрядеа3.
Недостатком такого способа является
то, что коды опознавателей ошибок не
соответствуют десятичным числам.
Корректирующие коды. Начало новой теории кодирования
Время на прочтение
Проблемы информационной безопасности требуют изучения и решения ряда теоретических и практических задач при информационном взаимодействии абонентов систем. В нашей доктрине информационной безопасности формулируется триединая задача обеспечения целостности, конфиденциальности и доступности информации. Представляемые здесь статьи посвящаются рассмотрению конкретных вопросов ее решения в рамках разных государственных систем и подсистем. Ранее автором были рассмотрены в 5 статьях вопросы обеспечения конфиденциальности сообщений средствами государственных стандартов. Общая концепция системы кодирования также приводилась мной ранее.
Введение
По основному своему образованию я не математик, но в связи с читаемыми мной дисциплинами в ВУЗе пришлось в ней дотошно разбираться. Долго и упорно читал классические учебники ведущих наших Университетов, пятитомную математическую энциклопедию, множество тонких популярных брошюр по отдельным вопросам, но удовлетворения не возникало. Не возникало и глубокое понимание прочитанного.
Вся математическая классика ориентирована, как правило, на бесконечный теоретический случай, а специальные дисциплины опираются на случай конечных конструкций и математических структур. Отличие подходов колоссальное, отсутствие или недостаток хороших полных примеров — пожалуй главный минус и недостаток вузовских учебников. Очень редко существует задачник с решениями для начинающих (для первокурсников), а те, что имеются, грешат пропусками в объяснениях. В общем я полюбил букинистические магазины технической книги, благодаря чему пополнилась библиотека и в определенной мере багаж знаний. Читать довелось много, очень много, но «не заходило».
Этот путь привел меня к вопросу, а что я уже могу самостоятельно делать без книжных «костылей», имея перед собой только чистый лист бумаги и карандаш с ластиком? Оказалось совсем немного и не совсем то, что было нужно. Пройден был сложный путь бессистемного самообразования. Вопрос был такой. Могу ли я построить и объяснить, прежде всего себе, работу кода, обнаруживающего и исправляющего ошибки, например, код Хемминга, (7, 4)-код?
Известно, что код Хемминга широко используется во многих прикладных программах в области хранения и обмена данными, особенно в RAID; кроме того, в памяти типа ECC и позволяет «на лету» исправлять однократные и обнаруживать двукратные ошибки.
Информационная безопасность. Коды, шифры, стегосообщения
Информационное взаимодействие путем обмена сообщениями его участников должно обеспечиваться защитой на разных уровнях и разнообразными средствами как аппаратными так и программными. Эти средства разрабатываются, проектируются и создаются в рамках определенных теорий (см. рис. А) и технологий, принятых международными договоренностями об OSI/ISO моделях.
Защита информации в информационных телекоммуникационных системах (ИТКС) становится практически основной проблемой при решении задач управления, как в масштабе отдельной личности – пользователя, так и для фирм, объединений, ведомств и государства в целом. Из всех аспектов защиты ИТКС в этой статье будем рассматривать защиту информации при ее добывании, обработке, хранении и передаче в системах связи.
Уточняя далее предметную область, остановимся на двух возможных направлениях, в которых рассматриваются два различных подхода к защите, представлению и использованию информации: синтаксическом и семантическом. На рисунке используются сокращения: кодек–кодер-декодер; шидеш – шифратор-дешифратор; скриз – скрыватель – извлекатель.
Рисунок А – Схема основных направлений и взаимосвязи теорий, направленных на решение задач защиты информационного взаимодействия
Синтаксические особенности представления сообщений позволяют контролировать и обеспечивать правильность и точность (безошибочность, целостность) представления при хранении, обработке и особенно при передаче информации по каналам связи. Здесь главные задачи защиты решаются методами кодологии, ее большой части — теории корректирующих кодов.
Семантическая (смысловая) безопасность сообщений обеспечивается методами криптологии, которая средствами криптографии позволяет защитить от овладения содержанием информации потенциальным нарушителем. Нарушитель при этом может скопировать, похитить, изменить или подменить, или даже уничтожить сообщение и его носитель, но он не сможет получить сведений о содержании и смысле передаваемого сообщения. Содержание информации в сообщении останется для нарушителя недоступным. Таким образом, предметом дальнейшего рассмотрения будет синтаксическая и семантическая защита информации в ИТКС. В этой статье ограничимся рассмотрением только синтаксического подхода в простой, но весьма важной его реализации корректирующим кодом.
Сразу проведу разграничительную линию в решении задач информационной безопасности:
теория кодологии призвана защищать информацию (сообщения) от ошибок (защита и анализ синтаксиса сообщений) канала и среды, обнаруживать и исправлять ошибки;
теория криптологии призвана защищать информацию от несанкционированного доступа к ее семантике нарушителя (защита семантики, смысла сообщений);
теория стеганологии призвана защищать факт информационного обмена сообщениями, а также обеспечивать защиту авторского права, персональных данных (защита врачебной тайны).
В общем «поехали». По определению, а их довольно много, понять что есть код очень даже не просто. Авторы пишут, что код — это алгоритм, отображение и ещё что-то. О классификации кодов я не буду здесь писать, скажу только, что (7, 4)-код блоковый.
В какой-то момент до меня дошло, что код — это кодовые специальные слова, конечное их множество, которыми заменяют специальными алгоритмами исходный текст сообщения на передающей стороне канала связи и которые отправляются по каналу получателю. Замену осуществляет устройство-кодер, а на приемной стороне эти слова распознает устройство-декодер.
Алфавит и слова — это уже язык, известно, что естественные человеческие языки избыточны, но что это означает, где обитает избыточность языка трудно сказать, избыточность не очень хорошо организована, хаотична. При кодировании, хранении информации избыточность стремятся уменьшить, пример, архиваторы, код Морзе и др.
Ричард Хемминг, наверное, раньше других понял, что если избыточность не устранять, а разумно организовать, то ее можно использовать в системах связи для обнаружения ошибок и автоматического их исправления в кодовых словах передаваемого текста. Он понял, что все 128 семиразрядных двоичных слов могут использоваться для обнаружения ошибок в кодовых словах, которые образуют код — подмножество из 16 семиразрядных двоичных слов. Это была гениальная догадка.
До изобретения Хемминга ошибки приемной стороной тоже обнаруживались, когда декодированный текст не читался или получалось не совсем то, что нужно. При этом посылался запрос отправителю сообщения повторить блоки определенных слов, что, конечно, было весьма неудобно и тормозило сеансы связи. Это было большой не решаемой десятилетиями проблемой.
Построение (7, 4)-кода Хемминга
Вернемся к Хеммингу. Слова (7, 4)-кода образованы из 7 разрядов С j =
Линейные функциональные зависимости (правила (*)) вычислений значений символов
Исправление ошибки стало очень простой операцией — в ошибочном разряде определялся символ (ноль или единица) и заменялся другим противоположным 0 на 1 или 1 на 0.
Сколько же различных слов образуют код? Ответ на этот вопрос для (7, 4)-кода получается очень просто. Раз имеется лишь 4 информационных разряда, а их разнообразие при заполнении символами имеет
Информационные части этих 16 слов получают нумерованный вид №
(
0=0000; 4= 0100; 8=1000; 12=1100;
1=0001; 5= 0101; 9=1001; 13=1101;
2=0010; 6= 0110; 10=1010; 14=1110;
3=0011; 7= 0111; 11=1011; 15=1111.
Каждому из этих 4-разрядных слов необходимо вычислить и добавить справа по 3 проверочных разряда, которые вычисляются по правилам (*). Например, для информационного слова №6 равного 0110 имеем
Шестое кодовое слово при этом приобретает вид:
Таким же образом необходимо вычислить проверочные символы для всех 16-и кодовых слов. Подготовим для слов кода 16-строчную таблицу К и последовательно будем заполнять ее клетки (читателю рекомендую проделать это с карандашом в руках).
Таблица К – кодовые слова Сj, j = 0
15, (7, 4) – кода Хемминга
Описание таблицы: 16 строк — кодовые слова; 10 колонок: порядковый номер, десятичное представление кодового слова, 4 информационных символа, 3 проверочных символа, W-вес кодового слова равен числу ненулевых разрядов (≠ 0). Заливкой выделены 4 кодовых слова-строки — это базис векторного подпространства. Собственно, на этом все — код построен.
Таким образом, в таблице получены все слова (7, 4) — кода Хемминга. Как видите это было не очень сложно. Далее речь пойдет о том, какие идеи привели Хемминга к такому построению кода. Мы все знакомы с кодом Морзе, с флотским семафорным алфавитом и др. системами построенными на разных эвристических принципах, но здесь в (7, 4)-коде используются впервые строгие математические принципы и методы. Рассказ будет как раз о них.
Математические основы кода. Высшая алгебра
Подошло время рассказать какая Р. Хеммингу пришла идея открытия такого кода. Он не питал особых иллюзий о своем таланте и скромно формулировал перед собой задачу: создать код, который бы обнаруживал и исправлял в каждом слове одну ошибку (на деле обнаруживать удалось даже две ошибки, но исправлялась лишь одна из них). При качественных каналах даже одна ошибка — редкое событие. Поэтому замысел Хемминга все-таки в масштабах системы связи был грандиозным. В теории кодирования после его публикации произошла революция.
Это был 1950 год. Я привожу здесь свое простое (надеюсь доступное для понимания) описание, которого не встречал у других авторов, но как оказалось, все не так просто. Потребовались знания из многочисленных областей математики и время, чтобы все глубоко осознать и самому понять, почему это так сделано. Только после этого я смог оценить ту красивую и достаточно простую идею, которая реализована в этом корректирующем коде. Время я в основном, потратил на разбирательство с техникой вычислений и теоретическим обоснованием всех действий, о которых здесь пишу.
Создатели кодов, долго не могли додуматься до кода, обнаруживающего и исправляющего две ошибки. Идеи, использованные Хеммингом, там не срабатывали. Пришлось искать, и нашлись новые идеи. Очень интересно! Захватывает. Для поиска новых идей потребовалось около 10 лет и только после этого произошел прорыв. Коды, обнаруживающие произвольное число ошибок, были получены сравнительно быстро.
Векторные пространства, поля и группы. Полученный (7, 4)-код (Таблица К) представляет множество кодовых слов, являющихся элементами векторного подпространства (порядка 16, с размерностью 4), т.е. частью векторного пространства размерности 7 с порядком
Во-первых, они являются подпространством со всеми вытекающими отсюда свойствами и особенностями, во-вторых, кодовые слова являются подгруппой большой группы порядка 128, даже более того, аддитивной подгруппой конечного расширенного поля Галуа GF(
) степени расширения n = 7 и характеристики 2. Эта большая подгруппа раскладывается в смежные классы по меньшей подгруппе, что хорошо иллюстрируется следующей таблицей Г. Таблица разделена на две части: верхняя и нижняя, но читать следует как одну длинную. Каждый смежный класс (строка таблицы) — элемент факторгруппы по эквивалентности составляющих.
Таблица Г – Разложение аддитивной группы поля Галуа GF () в смежные классы (строки таблицы Г) по подгруппе 16 порядка.
Столбцы таблицы – это сферы радиуса 1. Левый столбец (повторяется) – синдром слова (7, 4)-кода Хемминга, следующий столбец — лидеры смежного класса. Раскроем двоичное представление одного из элементов (25-го выделен заливкой) факторгруппы и его десятичное представление:
Техника получение строк таблицы Г. Элемент из столбца лидеров класса суммируется с каждым элементом из заголовка столбца таблицы Г (суммирование выполняется для строки лидера в двоичном виде по mod2). Поскольку все лидеры классов имеют вес W=1, то все суммы отличаются от слова в заголовке столбца только в одной позиции (одной и той же для всей строки, но разных для столбца). Таблица Г имеет замечательную геометрическую интерпретацию. Все 16 кодовых слов представляются центрами сфер в 7-мерном векторном пространстве. Все слова в столбце от верхнего слова отличаются в одной позиции, т. е. лежат на поверхности сферы с радиусом r =1.
В этой интерпретации скрывается идея обнаружения одной ошибки в любом кодовом слове. Работа идет со сферами. Первое условие обнаружения ошибки — сферы радиуса 1 не должны касаться или пересекаться. Это означает, что центры сфер удалены друг от друга на расстояние 3 или более. При этом сферы не только не пересекаются, но и не касаются одна другой. Это требование для однозначности решения: какой сфере отнести полученное на приемной стороне декодером ошибочное (не кодовое одно из 128 -16 = 112) слово.
Второе — все множество 7-разрядных двоичных слов из 128 слов равномерно распределено по 16 сферам. Декодер может получить слово лишь из этого множества 128-ми известных слов с ошибкой или без нее. Третье — приемная сторона может получить слово без ошибки или с искажением, но всегда принадлежащее одной из 16-и сфер, которая легко определяется декодером. В последней ситуации принимается решение о том, что послано было кодовое слово — центр определенной декодером сферы, который нашел позицию (пересечение строки и столбца) слова в таблице Г, т. е номера столбца и строки.
Здесь возникает требование к словам кода и к коду в целом: расстояние между любыми двумя кодовыми словами должно быть не менее трех, т. е. разность для пары кодовых слов, например, Сi = 85=
=1010101; Сj = 25=
= 0011001 должна быть не менее 3; 85 — 25 = 1010101 — 0011001 =1001100 = 76, вес слова-разности W(76) = 3. (табл. Д заменяет вычисления разностей и сумм). Здесь под расстоянием между двоичными словами-векторами понимается количество не совпадающих позиций в двух словах. Это расстояние Хемминга, которое стало повсеместно использоваться в теории, и на практике, так как удовлетворяет всем аксиомам расстояния.
Замечание. (7, 4)-код не только линейный блоковый двоичный, но он еще и групповой, т. е. слова кода образуют алгебраическую группу по сложению. Это означает, что любые два кодовых слова при суммировании снова дают одно из кодовых слов. Только это не обычная операция суммирования, выполняется сложение по модулю два.
Таблица Д — Сумма элементов группы (кодовых слов), используемой для построения кода Хемминга
Сама операция суммирования слов ассоциативна, и для каждого элемента в множестве кодовых слов имеется противоположный ему, т. е. суммирование исходного слова с противоположным дает нулевое значение. Это нулевое кодовое слово является нейтральным элементом в группе. В таблице Д- это главная диагональ из нулей. Остальные клетки (пересечения строка/столбец) — это номера-десятичные представления кодовых слов, полученные суммированием элементов из строки и столбца. При перестановке слов местами (при суммировании) результат остается прежним, более того, вычитание и сложение слов имеют одинаковый результат. Дальше рассматривается система кодирования/декодирования, реализующая синдромный принцип.
Применение кода. Кодер
Кодер размещается на передающей стороне канала и им пользуется отправитель сообщения. Отправитель сообщения (автор) формирует сообщение в алфавите естественного языка и представляет его в цифровом виде. ( Имя символа в ASCII-соде и в двоичном виде).
Тексты удобно формировать в файлах для ПК с использованием стандартной клавиатуры (ASCII — кодов). Каждому символу (букве алфавита) соответствует в этой кодировке октет бит (восемь разрядов). Для (7, 4)- кода Хемминга, в словах которого только 4 информационных символа, при кодировании символа клавиатуры на букву требуется два кодовых слова, т.е. октет буквы разбивается на два информационных слова естественного языка (ЕЯ) вида
Пример 1. Необходимо передать слово «цифра» в ЕЯ. Входим в таблицу ASCII-кодов, буквам соответствуют: ц –11110110, и –11101000, ф – 11110100, р – 11110000, а – 11100000 октеты. Или иначе в ASCII — кодах слово «цифра» = 1111 0110 1110 1000 1111 0100 1111 0000 1110 0000
с разбивкой на тетрады (по 4 разряда). Таким образом, кодирование слова «цифра» ЕЯ требует 10 кодовых слов (7, 4)-кода Хемминга. Тетрады представляют информационные разряды слов сообщения. Эти информационные слова (тетрады) преобразуются в слова кода (по 7 разрядов) перед отправкой в канал сети связи. Выполняется это путем векторно-матричного умножения: информационного слова на порождающую матрицу. Плата за удобства получается весьма дорого и длинно, но все работает автоматически и главное — сообщение защищается от ошибок.
Порождающая матрица (7, 4)-кода Хемминга или генератор слов кода получается выписыванием базисных векторов кода и объединением их в матрицу. Это следует из теоремы линейной алгебры: любой вектор пространства (подпространства) является линейной комбинацией базисных векторов, т.е. линейно независимых в этом пространстве. Это как раз и требуется — порождать любые векторы (7-разрядные кодовые слова) из информационных 4-разрядных.
Порождающая матрица (7, 4, 3)-кода Хемминга или генератор слов кода имеет вид:
Справа указаны десятичные представления кодовых слов Базиса подпространства и их порядковые номера в таблице К
№ i строки матрицы — это слова кода, являющиеся базисом векторного подпространства.
Информационные слова сообщения имеют вид:
Это половины символа (ц). Для (7, 4)-кода, определенного ранее, требуется найти кодовые слова, соответствующее информационному слову-сообщению (ц) из 8-и символов в виде:
Получили два кодовых слова с порядковыми номерами 15 и 6.
Покажем детальное формирование нижнего результата №6 – кодового слова (умножение строки информационного слова на столбцы порождающей матрицы); суммирование по (mod2)
В результате перемножения получили 15 и 6 слова таблицы К кода.
Применение кода. Декодер
Декодер размещается на приемной стороне канала там, где находится получатель сообщения. Назначение декодера состоит в предоставлении получателю переданного сообщения в том виде, в котором оно существовало у отправителя в момент отправления, т.е. получатель может воспользоваться текстом и использовать сведения из него для своей дальнейшей работы.
Рассматриваемый код является систематическим, т. е. символы информационного слова размещаются подряд в старших разрядах кодового слова. Восстановление информационных слов выполняется простым отбрасыванием младших (проверочных) разрядов, число которых известно. Далее используется таблица ASCII-кодов в обратном порядке: входом являются информационные двоичные последовательности, а выходом – буквы алфавита естественного языка. Итак, (7, 4)-код систематический, групповой, линейный, блочный, двоичный.
Видим, что произведение порождающей матрицы на проверочную в результате дает нулевую матрицу.
В результате вычисленный синдром имеет нулевое значение, что подтверждает отсутствие ошибки в словах кода.
Пример 3. Обнаружение одной ошибки в слове, полученном на приемном конце канала (таблица К).
А) Пусть требуется передать 7 – е кодовое слово, т.е.
Установление факта искажения кодового слова выполняется умножением полученного искаженного слова на проверочную матрицу кода. Результатом такого умножения будет вектор, называемый синдромом кодового слова.
Выполним такое умножение для наших исходных (7-го вектора с ошибкой) данных.
Вот собственно и все, именно так устроен и работает классический (7, 4)-код Хемминга.
Здесь не рассматриваются многочисленные модификации и модернизации этого кода, так как важны не они, а те идеи и их реализации, которые в корне изменили теорию кодирования, и как следствие, системы связи, обмена информацией, автоматизированные системы управления.
Заключение
В работе рассмотрены основные положения и задачи информационной безопасности, названы теории, призванные решать эти задачи.
Задача защиты информационного взаимодействия субъектов и объектов от ошибок среды и от воздействий нарушителя относится к кодологии.
Рассмотрен в деталях (7, 4)-код Хемминга, положивший начало нового направлению в теории кодирования — синтеза корректирующих кодов.
Показано применение строгих математических методов, используемых при синтезе кода.
Приведены примеры иллюстрирующие работоспособность кода.
Литература
Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976, 594 c.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер.с англ. М.: Мир, 1986, 576 с.
Код коррекции ошибок
Коды коррекции
ошибок (Error
Correcting
Code
ECC)
позволяют не только обнаружить ошибку,
но и исправить ее в одном разряде. Поэтому
компьютер, в котором используются
подобные коды, в случае ошибки в одном
разряде может работать без прерывания,
причем данные не будут искажены. Коды
коррекции ошибок в большинстве
персональных компьютеров позволяют
только обнаруживать, но не исправлять
ошибки в двух разрядах. Но приблизительно
98% сбоев памяти вызвано именно ошибкой
в одном разряде, т.е. она успешно
исправляется с помощью данного типа
кодов. В кодах коррекции ошибок этого
типа для каждых 32 бит требуется
дополнительно семь контрольных разрядов
при 4-байтовой и восемь
при 8-байтовой организации. Реализация
кода коррекции ошибок при 4-байтовой
организации, очевидно, дороже реализации
проверки нечетности или четности, но
при 8-байтовой организации стоимость
реализации кода коррекции ошибок не
превышает стоимости реализации проверки
четности.
Для использования
кодов коррекции ошибок необходим
контроллер памяти, вычисляющий контрольные
разряды при операции записи в память.
При чтении из памяти такой контроллер
сравнивает прочитанные и вычисленные
значения контрольных разрядов и при
необходимости исправляет испорченный
бит (или биты). Стоимость дополнительных
логических схем для реализации кода
коррекции ошибок в контроллере памяти
не очень высока, но это может значительно
снизить быстродействие памяти при
операциях записи. Это происходит потому,
что при операциях записи и чтения
необходимо ждать, когда завершится
вычисление контрольных разрядов. При
записи части слова вначале следует
прочитать полное слово, затем перезаписать
изменяемые байты и только после этого
новые вычисленные контрольные разряды.
Большинство сбоев
памяти происходит в одном разряде, и
потому такие ошибки успешно исправляются
кодом коррекции ошибок. Использование
отказоустойчивой памяти обеспечивает
высокую надежность компьютера.
Контрольные вопросы
Соседние файлы в папке Сватов лабы