Глава 7. Контроль работы цифрового автомата

7.1 Кодирование информации как средство обеспечения контроля работы автомата

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

Одним из самых известных методов кодирования (шифрования) является метод Цезаря, который римский император если и не изобрел, то, по крайней мере, активно им пользовался. Не имея доверия к своим посыльным, он шифровал письма элементарной заменой А на D, В на Е и так далее по латинскому алфавиту. К примеру, при таком кодировании последовательность ABC была бы записана как DEF. Известно, что еще древнегреческий историк Геродот в V в. до н. э., приводил примеры писем, понятных лишь адресату. Над созданием различных секретных шифров работали такие известные ученые средневековья, как Ф. Бэкон, Д. Кардано и др. Появлялись очень хитрые шифры и коды, которые, однако, с течением времени расшифровывались и переставали быть секретом. Первым кодом, предназначенным для передачи сообщений по каналам связи, был код С. Морзе, содержащий разное количество символов для кодирования букв и цифр. Затем появился код Ж. Бодо, используемый в телеграфии, в котором все буквы или цифры содержат одинаковое количество символов. В качестве символов может выступать наличие или отсутствие (пробел) импульса в электрической цепи в данный момент. Коды, использующие два различных элементарных сигнала, называются двоичными. Эти сигналы удобно обозначать символами 0 и 1. Тогда кодовое слово будет состоять из последовательностей нулей и единиц. Двоичное кодирование тесно связано с принципом дихотомии, который реализуется в графическом методе представления двоичной информации в виде графов. В предыдущих главах были рассмотрены общие и конкретные вопросы кодирования информации в цифровом автомате. Однако эти методы сами по себе еще не обеспечивают правильность выполнения того или иного алгоритма. Рассмотренные ранее алгоритмы выполнения арифметических операций обеспечат правильный результат только в случае, если машина работает без нарушений. При возникновении какого-либо нарушения нормального функционирования результат будет неверным, однако пользователь об этом не узнает, если не будут предусмотрены меры, сигнализирующие о появлении ошибки. Следовательно, с одной стороны, разработчиками машины должны быть предусмотрены меры для создания системы обнаружения возможной ошибки, а с другой стороны, должны быть проработаны меры, позволяющие исправить ошибки. Эти функции следует возложить на систему контроля работы цифрового автомата.

Введём следующее определение.

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

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

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

При этом надо различать следующие виды ошибок результата:

1) возникающие из-за погрешностей в исходных данных;

2) обусловленные методическими погрешностями;

3) появляющиеся из-за возникновения неисправностей в работе машины.

Первые два вида ошибок не являются объектом для работы системы контроля. Погрешности перевода или представления числовой информации в разрядной сетке автомата приведут к возникновению погрешности в результате решения задачи. Эту погрешность можно заранее рассчитать и, зная ее максимальную величину, правильно выбрать длину разрядной сетки машины. Методические погрешности также учитываются предварительно.

Проверка правильности функционирования отдельных устройств машины и выявление неисправностей может осуществляться по двум направлениям:

· профилактический контроль, задача которого — предупреждение появления возможных ошибок в работе;

· оперативный контроль, задача которого — проверка правильности выполнения машиной всех операций.

Решение всех задач контроля становится возможным только при наличии определенной избыточности информации. Избыточность может быть создана либо аппаратными (схемными) средствами, либо логическими или информационными средствами.

К методам логического контроля, например, можно отнести следующие приемы. В ЭВМ первого и второго поколения отсутствие системы оперативного контроля приводило к необходимости осуществления «двойного счета», когда каждая задача решалась дважды и в случае совпадения ответов, принималось решение о правильности функционирования ЭВМ.

Если в процессе решения какой-то задачи вычисляются тригонометрические функции, то для контроля можно использовать известные соотношения между этими функциями, например sin² α+ cos² α = 1. Если это соотношение выполняется с заданной точностью на каждом шаге вычислений, то можно с уверенностью считать, что ЭВМ работает правильно.

Вычисление определенного интеграла с заданным шагом интегрирования можно контролировать сравнением полученных при этом результатов с теми результатами, которые соответствуют более крупному шагу. Такой «сокращенный» алгоритм даст, видимо, более грубые оценки и по существу требует дополнительных затрат машинного времени.

Все рассмотренные примеры свидетельствуют о том, что такие методы контроля позволяют лишь зафиксировать факт появления ошибки, но не определяют место, где произошла эта ошибка. Для оперативного контроля работы ЭВМ определение места, где произошла ошибка, т. е. решение задачи поиска неисправности, является весьма существенным вопросом.

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

Систематический код — код, содержащий в себе кроме информационных контрольные разряды.

В контрольные разряды записывается некоторая информация об исходном числе. Поэтому можно говорить, что систематический код обладает избыточностью. При этом абсолютная избыточность будет выражаться количеством контрольных разрядовk, а относительная избыточность — отношением k/n, где n = m + k — общее количество разрядов в кодовом слове (m — количество информационных разрядов).

Понятие корректирующей способности кода обычно связывают с возможностью обнаружения и исправления ошибки. Количественно корректирующая способность кода определяется вероятностью обнаружения или исправления ошибки.

Корректирующая способность кода связана также с понятием кодового расстояния.

Кодовое расстояние d(A, В) для кодовых комбинаций А и В определяется как вес третьей кодовой комбинации, которая получается поразрядным сложением исходных комбинаций по модулю 2.

Вес кодовой комбинации V(A) — количество единиц, содержащихся в кодовой комбинации.

Пример 7.1. Найти вес и кодовое расстояние для комбинаций A = 011011100,

B = 100111001

Решение. Вес для кодовых комбинаций V(A) = = 5; V(B) = = 5.

Находим кодовую комбинацию С= A ⊕ B = 111100101, для которой определяется вес,

равный кодовому расстоянию для A и В: V(C) = d(A,B) = = 6

Ответ d(A.B) = 6.

Коды можно рассматривать и как некоторые геометрические (пространственные) фигуры. Например, триаду можно представить в виде единичного куба, имеющего координаты вершин, которые отвечают двоичным символам (рис. 8.1). В этом случае кодовое расстояние воспринимается как сумма длин ребер между соответствующими вершинами куба (принято, что длина одного ребра равна 1). Оказывается, что любая позиционная система отличается тем свойством, что минимальное кодовое расстояние равно 1 (рис. 8.2, а).

Рис. 7.1. Геометрическое представление кодов

Рис. 7.2. Кодовые расстояния

В теории кодирования показано, что систематический код способен обнаружить ошибки только тогда, когда минимальное кодовое расстояние для него больше или равно 2t, т.е.

где t — кратность обнаруживаемых ошибок (в случае одиночных ошибок t = 1 и т. д.).

Это означает, что между соседними разрешенными кодовыми словами должно существовать по крайней мере одно кодовое слово (рис. 8.2, б, в).

В тех случаях, когда необходимо не только обнаружить ошибку, но и исправить ее (т.е. указать место ошибки), минимальное кодовое расстояние должно быть

Существуют коды, в которых невозможно выделить абсолютную избыточность. Пример таких кодов — Д-коды, где количество разрешенных комбинаций меньше количества возможных комбинаций. Неявная избыточность характерна также для кодов типа «k из n». Примером является код «2 из 5», который часто используется для представления информации. Суть его в том, что в слове из пяти разрядов только два разряда имеют единичное значение.

7.2 Методы эффективного кодирования информации

Информационную избыточность можно ввести разными путями. Рассмотрим один из путей эффективного кодирования.

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

Такое эффективное кодирование базируется на основной теореме Шеннона для каналов без шума, в которой доказано, что сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов на букву будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины.

Теорема не указывает конкретного способа кодирования, но из нее следует, что при выборе каждого символа кодовой комбинации необходимо стараться, чтобы он нес максимальную информацию. Следовательно, каждый символ должен принимать значения 0 и 1 по возможности с равными вероятностями и каждый выбор должен быть независим от значений предыдущих символов.

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

Следует отметить, что вторая теорема Шеннона относится к реальным каналам связи и гласит следующее:

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

7.3 Кодирование по методу четности-нечетности

Если в математическом коде выделен один контрольный разряд (k = 1), то к каждому двоичному числу добавляется один избыточный разряд и в него записывается 1 или 0 с таким условием, чтобы сумма цифр в каждом числе была по модулю 2 равна 0 для случая четности или 1 для случая нечетности. Появление ошибки в кодировании обнаружится по нарушению четности (нечетности). При таком кодировании допускается, что может возникнуть только одна ошибка. В самом деле, для случая четности правильной будет только половина возможных комбинаций. Чтобы одна допустимая комбинация превратилась в другую, должно возникнуть по крайней мере два нарушения или четное число нарушений. Пример реализации метода четности представлен в таблице 7.1.

Таблица 7.1

Число	Контрол.ьный разряд	Проверка



		1 - нарушение

Такое кодирование имеет минимальное кодовое расстояние, равное 2.

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

A₁	A₂	A₃	A₄	A₅	K₁
A₆	A₇	A₈	A₉	A₁₀	K₂
A₁₁	A₁₂	A₁₃	A₁₄	A₁₅	K₃
A₁₆	A₁₇	A₁₈	A₁₉	A₂₀	K₄
A₂₁	A₂₂	A₂₃	A₂₄	A₂₅	K₅
K₆	K₇	K₈	K₉	K₁₀

Увеличение избыточности информации приводит к тому, что появляется возможность не только обнаружить ошибку, но и исправить ее. Пусть произошла неисправность в каком-то из разрядов этого числа (представим, что разряд a₁₈ изменил состояние, т. е. a₁₈ = 1). Это приведет к тому, что при проверке на четность сумма по соответствующим строкам и столбцам изменится для значений, которые содержат элемент a₁₈, т. е. это будет четвертая сверху строка и третий слева столбец. Следовательно, нарушение четности по этой строке и столбцу можно зафиксировать, что в конечном счете означает обнаружение не только самой ошибки, но и места, где возникла ошибка. Изменив содержимое отмеченного разряда (в данном случае a₁₈) на противоположное, можно исправить ошибку.

Контроль по методу чётности – нечётности широко используют в ЭВМ для контроля записи, считывания информации в запоминающих устройствах на магнитных носителях, а также при выполнении арифметических операций.

7.3 Коды Хэминга

Коды, предложенные американским ученым Р. Хэмингом, способны не только обнаружить, но и исправить одиночные ошибки. Эти коды — систематические.

Основная идея состоит в добавлении к информационным битам несколько битов чётности, каждый из которых контролирует определённые информационные биты. Если пронумеровать все передаваемые биты, начиная с первого слева направо (напомним, что информационные биты нумеруются с нуля и справа налево), то контрольными оказываются биты, номера которых равны степеням числа 2, а все остальные являются информационными. Например, для 8 – разрядного информационного кода контрольными окажутся разряды с номерами 1,2,4,8.

Номера контролируемых битов для каждого проверочного приведены в табл. 7.2.

Таблица 7.2.

Проверочные биты	Контролируемые биты
	1,3,5,7,9,11,13,15, 17, 19, 21,…
	2,3,6,7,10,11,14,15,18,19,22,…
	4,5,6,7,12,13,14,15,20,21,22, 23,…
	8,9,10,11,12,13,14,15,24,25, 26,…
	16, 17, 18, 19,20, 21, 22, 23, 24, 25, 26,…
	32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, …

Легко усматривается принцип выделения контролируемых разрядов: для любого номера проверочного разряда (n), начиная с него, n разрядов подряд оказываются проверяемыми, затем группа n непроверяемых разрядов,далее происходит чередование групп.

Пример 7.2. Пусть вместо последовательности 0 0 0 1 1 1 0 1 1 1 0 1 пришла следующая:

0 0 0 1 0 1 0 1 1 1 0 1

1 2 3 4 5 6 7 8 9 10 11 12

Анализируем состояния контрольных битов в соответствии с табл. 7.2.

Бит 1 – неверно, т.е. ошибка находится в каком – либо бите с нечётным номером.

Бит 2 – верно, следовательно, биты с нечётными номерами 3, 7, 11 – верны (т.е. – ошибка в 5 или 9).

Бит 4 – неверно, значит ошибка может содержаться только в 5- м бите.

Таким образом, однозначно устанавливается, что ошибочным является 5 –й разряд, остаётся исправить его значение на противоположное и, тем самым, восстановить правильную последовательность.

На основании сказанного можно сформулировать простой алгоритм проверки и исправления передаваемой последовательности бит в представлении Хемминга:

1. произвести проверку всех битов чётности;

2. если все биты чётности верны, то перейти к п.5;

3. вычислить сумму номеров всех неправильных битов чётности;

4. инвертировать содержимое бита, номер которого равен сумме, найденной в п.3;

5. исключить биты чётности, передать правильный информационный код.

Избыточность кодов Хемминга для различных длин передаваемых последовательностей приведена в табл. 7.3.

Таблица 7.3.

Число информационных битов	Число контрольных битов	Избыточность
		1.50
		1.31
		1.06

Из сопоставления видно, что выгоднее передавать и хранить более длинные последовательности битов. Безусловно, данный способ кодирования требует увеличения объёма памяти компьютера приблизительно на одну треть при 16 – битной длине машинного слова, однако, использование кодов Хемминга позволяет автоматически исправлять одиночные ошибки.