Как уже указывалось, функции контроля можно осуществить при информационной избыточности. Такая возможность появляется при использовании специальных методов кодирования информации. В самом деле, некоторые методы кодирования информации допускают наличие разрешенных и запрещенных комбинаций. В качестве примера можно привести двоично-десятичные системы представления числовой информации (Д-коды). Появление запрещенных комбинаций для подобного представления свидетельствует об ошибке в результатах решения задачи. Такой метод можно использовать для контроля десятичных операций. Однако он является частным примером и не решает общей задачи.
Задача кодирования информации представляется как некоторое преобразование числовых данных в заданной программе счисления. В частном случае эта операция может быть сведена к группированию символов (представление в виде триад и тетрад) или представлению в виде символов позиционной системы счисления. Так как любая позиционная система счисления не несет в себе избыточности информации, и все кодовые комбинации являются разрешенными, то использовать такие системы для контроля не представляется возможным.
Систематический код —код, содержащий в себе кроме информационных контрольные разряды.
В контрольные разряды записывается некоторая информация об исходном числе. Поэтому можно говорить, что систематический код обладает избыточностью. При этом абсолютная избыточность будет выражаться количеством контрольных разрядов k, а относительная избыточность — отношением k/n, где n=m+k — общее количество разрядов в кодовом слове (m — количество информационных разрядов).
Понятие корректирующей способности кода обычно связывают с возможностью с возможностью обнаружения и исправления ошибки. Количественно корректирующая способность кода определяется вероятностью обнаружения или исправления ошибки. Если имеем n- разрядный код и вероятность искажения одного символа будет P, то вероятность того, что искажены k символов, а остальные n-k символов не искажены, по теореме умножения вероятностей будет
W=Pk(1-P)n-k.
Число кодовых комбинаций, каждая из которых содержит k искаженных элементов, равна числу сочетаний из n по k:
Тогда вероятность искажения
Так как на практике P=10-3÷10-4, наибольший вес в сумме вероятностей имеет вероятность искажения одного символа. Следовательно, основное внимание нужно обратить на обнаружение и исправление одиночной ошибки.
Корректирующая способность кода связана также с понятием кодового расстояния.
Кодовое расстояниеd(A,B) кодовых комбинацийА и В определяется как вес такой третьей кодовой комбинации, которая получается сложением исходных комбинаций по модулю 2.
Вес кодовой комбинацииV(A) — количество единиц, содержащихся в кодовой комбинации.
Коды можно рассматривать и как некоторые геометрические (пространственные) фигуры. Например, триаду можно представить в виде единичного куба, имеющего координаты вершин, которые отвечают двоичным символам (рис. 4.1) в этом случае кодовое расстояние воспринимается как сумма длин ребер между соответствующими вершинами куба (принято, что длина одного ребра равна 1). Оказывается, что любая позиционная система отличается тем свойством, что минимальное кодовое расстояние равно 1.
В теории кодирования показано, что систематический код обладает способностью обнаружить ошибки только тогда, когда минимальное кодовое расстояние для него больше или равно 2t, т.е. , где t — кратность обнаруживаемых ошибок t=1 (в случае обнаружения одиночных ошибок t=1). Это означает, что между соседними кодовыми комбинациями должна существовать по крайней мере одна кодовая комбинация (рис. 4.2).
001 011
а) d=1 d=1
Информационные основы контроля работы цифрового автомата.
Алгоритмы выполнения арифметических операций обеспечат правильный результат только в случае, если машина работает без нарушений. При возникновении какого-либо нарушения нормального функционирования результат будет неверным, однако пользователь об этом не узнает, если не будут предусмотрены меты для создания системы обнаружения возможной ошибки, а с другой стороны, должны быть проработаны меры, позволяющие исправить ошибки. Эти функции следует возложить на систему контроля работы цифрового автомата.
Система контроля - совокупность методов и средств, обеспечивающих определение правильности работы автомата в целом или его отдельных узлов, а также автоматическое исправление ошибки. Ошибки в работе цифрового автомата могут быть вызваны либо выходом из строя какой-то детали, либо отклонением от нормы параметров (например, изменение напряжения питания) или воздействием внешних помех. Вызванные этими нарушениями ошибки могут принять постоянный или случайный характер. Постоянные ошибки легче обнаружить и выявить. Случайные ошибки, обусловленные кратковременными изменениями параметров, наиболее опасны и их труднее обнаружить. Поэтому система контроля должна строится с таким расчетом, чтобы она позволяла обнаружить и по возможности исправить любые нарушения. При этом надо различать следующие виды ошибок результата:
1. возникающие из-за погрешностей в исходных данных;
обусловленные методическими погрешностями;
появляющиеся из-за возникновения неисправностей в работе машины.
Первые два вида ошибок не являются объектом для работы системы контроля. Конечно, погрешности перевода или представления числовой информации в разрядной сетки автомата приведут к возникновению погрешности в результате решения задачи. Эту погрешность можно заранее рассчитать и, зная её максимальную величину, правильно выбрать длину разрядной сетки машины. Методические погрешности также учитываются предварительно. Проверка правильности функционирования отдельных устройств машины и выявление неисправностей может осуществляться по двум направлениям: - профилактический контроль, задача которого - предупреждение появления ошибок в работе; - оперативный контроль, задача которого - проверка правильности выполнения машиной всех операций. Решение всех задач контроля становится возможным только при наличии определенной избыточности. Избыточность может быть либо аппаратными (схемными) средствами, либо логическими или информационными средствами. К методам логического контроля можно отнести следующие приемы. В ЭВМ первого и второго поколений отсутствие системы оперативного контроля приводило к необходимости осуществления "двойного счета", когда каждая задача решалась дважды, и в случае совпадения ответов принималось решение о правильности функционирования ЭВМ. Если в процессе решения какой-то задачи вычисляются тригонометрические функции, то для контроля можно использовать известные соотношения между этими функциями, например, если это соотношение выполняется заданной точностью на каждом шаге вычислений, то можно с уверенностью читать, что ЭВМ работает правильно. Вычисление определенного интеграла с заданным шагом интегрирования можно контролировать сравнением полученных при этом результатов с теми результатами, которые соответствуют более крупному шагу. Такой "сокращенный" алгоритм даст, видимо, более грубые оценки и по существу требует дополнительных затрат машинного времени. Все рассмотренные примеры свидетельствуют о том, что такие методы контроля позволяют лишь зафиксировать факт появления ошибки, но не оп-ределяют место, где произошла эта ошибка. Для оперативного контроля ра-боты ЭВМ определение места, где произошла ошибка, т.е. решение задачи поиска неисправности, является весьма существенным вопросом. Как уже указывалось, функции контроля можно осуществить при инфор-мационной избыточности. Такая возможность появляется при использовании специальных методов кодирования информации. В самом деле, некоторые методы кодирования информации допускают наличие разрешенных и запре-щенных комбинаций. В качестве примера можно привести двоично-десятичные системы представления числовой информации (Д-коды). Появ-ление запрещенных комбинаций для подобного представления свидетельст-вует об ошибке в результатах решения задачи. Такой метод можно использо-вать для контроля десятичных операций. Однако он является частным при-мером и не решает общей задачи. Задача кодирования информации представляется как некоторое преобра-зование числовых данных в заданной программе счисления. В частном слу-чае эта операция может быть сведена к группированию символов (представ-ление в виде триад и тетрад) или представлению в виде символов позиционной системы счисления. Так как любая позиционная система счисления не несет в себе избыточности информации, и все кодовые комбинации являются разрешенными, то использовать такие системы для контроля не представляется возможным.
Систематические коды.
Систематический код - код, содержащий в себе кроме информационных контрольные разряды. В контрольные разряды записывается некоторая информация об исходном числе. Поэтому можно говорить, что систематический код обладает избы-точностью. При этом абсолютная избыточность будет выражаться количеством контрольных разрядов k, а относительная избыточность - отношением k/n, где n=m+k - общее количество разрядов в кодовом слове (m - количество информационных разрядов). Кодовое расстояние d(A,B) кодовых комбинаций А и В определяется как вес такой третьей кодовой комбинации, которая получается сложением исходных комбинаций по модулю 2. Вес кодовой комбинации V(A) - количество единиц, содержащихся в ко-довой комбинации. Коды можно рассматривать и как некоторые геометрические (пространственные) фигуры. Например, триаду можно представить в виде единичного куба, имеющего координаты вершин, которые отвечают двоичным символам (рис. 4.1) в этом случае кодовое расстояние воспринимается как сумма длин ребер между соответствующими вершинами куба (принято, что длина одного ребра равна 1). Оказывается, что любая позиционная система отличается тем свойством, что минимальное кодовое расстояние равно 1. В теории кодирования показано, что систематический код обладает способностью обнаружить ошибки только тогда, когда минимальное кодовое расстояние для него больше или равно 2t, т.е. , где t - кратность обнаруживаемых ошибок t=1 (в случае обнаружения одиночных ошибок t=1). Это означает, что между соседними кодовыми комбинациями должна существо-вать по крайней мере одна кодовая комбинация.
Кодирование по методу четности-нечетности.
Если в математическом коде выделен один контрольный разряд (k=1), то к каждому двоичному числу добавляется один избыточный разряд и в него за-писывается 1 или 0 с таким условием, чтобы сумма цифр в каждом числе бы-ла по модулю 2 равна 0 для случая нечетности. Появление ошибки в кодиро-вании обнаружится по нарушению четности (нечетности). При этом допуска-ется, что может возникнуть только одна ошибка. В самом деле, для случая четности правильным будет только половина возможных комбинаций. Чтобы одна допустимая комбинация превратилась в другую, должно возникнуть, по крайней мере, два нарушения или четное число нарушений. Можно представить и несколько видоизмененный способ контроля по ме-тоду четности - нечетности. Длинное число разбивается на группы. Кон-трольные разряды выделяются всем группам по строкам и по столбцам. Увеличение избыточности информации приводит к тому, что появляется возможность не только обнаружить ошибку, но и исправить её. Контроль по методу четности-нечетности широко используют в ЭВМ для контроля записи, считывания информации в запоминающих устройствах на магнитных носителях.
Коды Хэмминга.
Коды, предложенные американским ученым Р. Хэммингом, обладают способностью не только обнаружить, но и исправить одиночные ошибки. Эти коды - систематические. Предложим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было произведено k проверок. Если результат проверки свидетельствует об ошибке, запишем 0, если ошибка - запишем 1. Запись полученной последо-вательности символов образует двоичное число. Свойство кодов Хэмминга таково, что контрольное число указывает номер позиции, где произошла ошибка. При отсутствии ошибок в данной позиции последовательность будет содержать только нули. Полученное число таким образом описывает n=(m+k+1) событий. (4.1.) В таблице, ниже, представлены примеры кодирования информации по ме-тоду Хэмминга для семизарядного кода.
Разряды двоичного кода
Кодируемая
десятичная
k1
k2
m1
k3
m2
m3
m4
информация
Как видно из таблицы в этом случае n=7, m=4, k=3 и контрольными будут разряды 1,2,4. По методу Хэмминга могут быть построены коды разной длины. При этом чем больше длина кода, тем меньше относительная избыточность. Например, для контроля числа, имеющего 48 двоичных разрядов. Коды Хэмминга используют в основном для контроля передачи информации по каналам связи, что имеет место в вычислительных системах с телеобработкой данных или в системах коллективного пользования.
Тест.
1.Система контроля - это А) Система контроля за центральным процессором Б) Контроль родителя над ребенком В) Совокупность методов и средств, обеспечивающих определение правильности работы автомата в целом или его отдельных узлов, а также автоматическое исправление ошибки.* Г) Специальное устройство находящиеся в процессоре 2. Какой вид ошибок является объектом для работы система контроля А) Возникающие из-за погрешностей в исходных данных Б) Обусловленные методическими погрешностями В) Появляющиеся из-за возникновения неисправностей в работе машины.* Г) Возникающие из-за погрешностей в выводных данных 3. Задача профилактического контроля А) Предупреждение появления ошибок в работе* Б) Поверка правильности выполнения машиной всех операций В) Проверка ошибок в тексте Г) Устранение ошибок 4. Задача оперативного контроля А) Предупреждение появления ошибок в работе Б) Поверка правильности выполнения машиной всех операций* В) Оперативная проверка ошибок Г) Контроль за всем 5. Определение систематического кода А) Код, состоящий из одних цифр Б) Код, служащий для решения различных математических задач В) Код, содержащий в себе кроме информационных контрольные разряды. Систематический код обладает избыточностью* Г) Код, содержащий в себе только контрольные разряды 6. Кодовое расстояние d(A,B) кодовых комбинаций А) Определяется как вес такой третьей кодовой комбинации, которая получается сложением исходных комбинаций по модулю 2.* Б) Определяется как вес такой третьей кодовой комбинации, которая получается сложением исходных комбинаций по модулю 3. В) Определяется как вес такой пятой кодовой комбинации, которая получается сложением исходных комбинаций по модулю 2. Г) определяется как вес такой четвертой кодовой комбинации, которая получается сложением исходных комбинаций по модулю 2. 7. Вес кодовой комбинации V(A)-это А) Количество нулей, содержащихся в кодовой комбинации. Б) Количество пятерок, содержащихся в кодовой комбинации. В) Все количество цифр Г) Количество единиц, содержащихся в кодовой комбинации. * 8. Коды Хэмминга А) систематические * Б) Информационные В) Профилактические Г) Десятеричные
Цифровая оперативная печать
Оборудование Konica Minolta bizhub PRO C6000L, максимальный формат - SRA3 (450х320 мм.)
Цветность/Тираж
При любом тираже
Черно-белая односторонняя
1+0
6,00
Черно-белая двусторонняя
1+1
12,00
Полноцветная односторонняя
4+0
16,00
Полноцветная двусторонняя
4+4
32,00
Полноцветная+черно-белая
4+1
22,00
Цена в рублях без стоимости материала, до- и послепечатной обработки. Срок изготовления от 1 часа.
