 |
Обнаружение и исправление ошибок. Корректирующие коды. Примеры.
|
|
|
|
Система контроля - совокупность методов и средств, обеспечивающих определение правильности работы автомата в целом или его отдельных узлов, а также автоматическое исправление ошибки. Ошибки в работе цифрового автомата могут быть вызваны либо выходом из строя какой-то детали, либо отклонением от нормы параметров (например, изменение напряжения питания) или воздействием внешних помех. Вызванные этими нарушениями ошибки могут принять постоянный или случайный характер. Постоянные ошибки легче обнаружить и выявить. Случайные ошибки, обусловленные кратковременными изменениями параметров, наиболее опасны и их труднее обнаружить.
Поэтому система контроля должна строится с таким расчетом, чтобы она позволяла обнаружить и по возможности исправить любые нарушения. При этом надо различать следующие виды ошибок результата:
- возникающие из-за погрешностей в исходных данных;
- обусловленные методическими погрешностями;
- появляющиеся из-за возникновения неисправностей в работе машины.
Первые два вида ошибок не являются объектом для работы системы контроля. Конечно, погрешности перевода или представления числовой информации в разрядной сетки автомата приведут к возникновению погрешности в результате решения задачи. Эту погрешность можно заранее рассчитать и, зная её максимальную величину, правильно выбрать длину разрядной сетки машины. Методические погрешности также учитываются предварительно.
Проверка правильности функционирования отдельных устройств машины и выявление неисправностей может осуществляться по двум направлениям:
- профилактический контроль, задача которого - предупреждение появления ошибок в работе;
- оперативный контроль, задача которого - проверка правильности выполнения машиной всех операций.
Решение всех задач контроля становится возможным только при наличии определенной избыточности. Избыточность может быть либо аппаратными (схемными) средствами, либо логическими или информационными средствами. К методам логического контроля можно отнести следующие приемы. В ЭВМ первого и второго поколений отсутствие системы оперативного контроля приводило к необходимости осуществления "двойного счета", когда каждая задача решалась дважды, и в случае совпадения ответов принималось решение о правильности функционирования ЭВМ.
Если в процессе решения какой-то задачи вычисляются тригонометрические функции, то для контроля можно использовать известные соотношения между этими функциями, например, если это соотношение выполняется заданной точностью на каждом шаге вычислений, то можно с уверенностью читать, что ЭВМ работает правильно.
Вычисление определенного интеграла с заданным шагом интегрирования можно контролировать сравнением полученных при этом результатов с теми результатами, которые соответствуют более крупному шагу. Такой "сокращенный" алгоритм даст, видимо, более грубые оценки и по существу требует дополнительных затрат машинного времени.
Все рассмотренные примеры свидетельствуют о том, что такие методы контроля позволяют лишь зафиксировать факт появления ошибки, но не оп-ределяют место, где произошла эта ошибка. Для оперативного контроля ра-боты ЭВМ определение места, где произошла ошибка, т.е. решение задачи поиска неисправности, является весьма существенным вопросом.
Как уже указывалось, функции контроля можно осуществить при инфор-мационной избыточности. Такая возможность появляется при использовании специальных методов кодирования информации. В самом деле, некоторые методы кодирования информации допускают наличие разрешенных и запре-щенных комбинаций. В качестве примера можно привести двоично-десятичные системы представления числовой информации (Д-коды). Появ-ление запрещенных комбинаций для подобного представления свидетельст-вует об ошибке в результатах решения задачи. Такой метод можно использо-вать для контроля десятичных операций. Однако он является частным при-мером и не решает общей задачи.
Задача кодирования информации представляется как некоторое преобра-зование числовых данных в заданной программе счисления. В частном слу-чае эта операция может быть сведена к группированию символов (представ-ление в виде триад и тетрад) или представлению в виде символов позиционной системы счисления. Так как любая позиционная система счисления не несет в себе избыточности информации, и все кодовые комбинации являются разрешенными, то использовать такие системы для контроля не представляется возможным.
|
|
|
|
|
|
Код Хэмминга. Примеры.
Коды, предложенные американским ученым Р. Хэммингом, обладают способностью не только обнаружить, но и исправить одиночные ошибки. Эти коды - систематические.
Предложим, что имеется код, содержащий 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 двоичных разрядов. Коды Хэмминга используют в основном для контроля передачи информации по каналам связи, что имеет место в вычислительных системах с телеобработкой данных или в системах коллективного пользования.
|
|
|
Асинхронный RS-триггер на элементах ИЛИ-НЕ (с прямыми входами), И-НЕ(с инверсными входами). Условное графическое обозначение. Электрическая схема. Таблицы функционирования, учитывающая и не учитывающая состязания сигналов.
Асинхронный RS-триггер
Имеет два входа “R” и “S” и два выхода, как правило это “Q” и “не Q” (т.е. инверсный). Лично я запомнил, какой вход для чего, после того, когда узнал, что R – это “RESET” (что означает “сброс”) и “S” – это “SET” (что означает установка). Принимая во внимание изложенную информацию можно указать, что при подаче сигнала (единица) на вход “S” на выходе “Q” устанавливается единица, а при подаче сигнала (единица) на вход “R” приводит к сбросу единицы на выходе “Q” и установки на нем нуля. Рассмотрим работу на базе элементов “2ИЛИ-НЕ” и “2И-НЕ”. Для этого используем графическое изображение этих элементов.
Итак, разберем принцип работы на базе элементов “2ИЛИ-НЕ”. В начальном положении, когда на входах R и S отсутствуют сигналы (логический “0”), на выходе “Q” присутствует также “0” или “1” – это исходное состояние. Выглядит это так:
Далее подадим на “S” логическуюединицу и получим на выходе “Q” также единицу. Будет выглядеть это так.
|
|
|
Следующим шагом подадим логическую единицу на “R” и уже на выходе “Q” получим “0”. Изобразим это на рисунке.
Более наглядную работу RS-триггера на элементах 2ИЛИ-НЕ можно продемонстрировать, изобразив таблицу истинности. Вот так она выглядит.
Сейчас рассмотрим работу на элементах 2И-НЕ. Выглядит она аналогично, как и на элементах 2ИЛИ-НЕ с той лишь разницей, что активным уровнем является не “1”как в предыдущем случае, а “0”. Убедимся в этом, используя рисунок и таблицу истинности.
Асинхронным триггерам свойственно такое явление как присутствие “гонок”, что это? Это не одновременное или даже не согласованное по времени поступление сигналов на входы. Это приводит к наложению одного сигнала на другой. Чем это вызвано? А вызвано это разным временем быстродействия элементов, через которые проходит сигнал прежде чем попасть на вход триггера, в данном случае на вход “R” или “S”. Покажем это явление на диаграмме.
Чтобы избавиться от этого явления, был придуман вариант подачи синхросигнала и асинхронный RS–триггер превратился в синхронный.
|
|
|
