Презентация_ТЕХ.ДИАГНОСТИКА_2. Конспект лекций по курсу "техническая диагностика" Ю. В. Малышенко введение
 Скачать 0.81 Mb.
|
|
6.4. Анализ на состязания тестов последовательностных схем Анализ на состязания последовательностных схем выполняется в два этапа. На первом этапе (процедура А) изменившимся входным переменным приписывается значение “х” и выполняется троичное моделирование. Задача процедуры А - выявить элементы памяти (обратные связи), на состоянии которых могут влиять изменения входных переменных. На втором этапе (процедура В) определяются установившиеся состояния элементов памяти (обратных связей) схемы. Для этого назначаются входным переменным схемы их нормальные значения 1 или 0 и повторяется троичное моделирование, причем исходное состояние схемы при моделировании совпадает с состоянием схемы после выполнения процедуры А. Обозначим через Yk состояние k-го элемента памяти на данном наборе. Тогда справедливо следующее утверждение. Утверждение 6.2. Если Yk = 1(0) после применения процедур A и B, то Yk должно принять на данном наборе значение 1(0) независимо от задержек элементов схемы. Теперь становится очевидным, что состязания не оказывают влияния на установившееся состояние схемы, если после выполнения процедур А и В для любого k выполняется соотношение Yk x . Изложенный метод анализа тестов на состязания предполагает, что возможны любые задержки элементов схемы. Поэтому некоторые состязания, обнаруженные этим методом, могут отсутствовать в реальной схеме. Возможны различные модификации методов на основе троичного моделирования для обнаружения состязаний, в том числе, допускающие введение в модель схемы задержек. Например, в одном из алгоритмов анализ перехода (при изменении входного набора) предполагает выполнение четырех процедур: х-продвижение (x-PASS); v-продвижение (VALUE-PASS); D-x-продвижение (DELAYED-x-PASS); D-v-продвижение (DELAYED-VALUE-PASS). Первые две процедуры подобны процедурам А и В соответственно. Другие вступают в действие при наличии задержек в схеме. Анализ очередного набора начинается с операции х-продвижение. Изменившейся входной переменной приписывается значение “х” и вычисляются значения выходов элементов, на которые воздействует эта переменная. Просчет элементов некоторого пути, соединяющего данную входную переменную с выходом схемы, прекращается, если выполняется одно из условий: 1) вычисленное значение выхода элемента равно 0 или 1; 2) вычисленное значение выхода элемента совпадает с его прошлым значением; 3) встретилась задержка. Затем х-продвижение применяется к следующей изменившейся входной переменной и т.д., пока всем изменившимся входным переменным не будут приписаны значения “х”. Цель этой процедуры - выявить элементы,состояния которых зависят от изменившихся входных переменных. Процедура v-продвижение следует за х-продвижением. Изменившимся входным переменным поочередно приписываются их фактические значения и выполняются вычисления, подобные вычислениям в процедуре х-продвижение (при этом несколько изменяются условия прекращения просчета элементов пути, соединяющего рассматриваемую переменную с выходом схемы - нет первого условия). Цель процедуры v-продвижения - определить установившиеся значения элементов схемы. В ходе ее выполнения помечаются встреченные задержки. Если в схеме встречается задержка, то после v-продвижения применяются процедуры D-х и D-v-продвижений. Первый вступает в действие процедура D-x-продвижения. Выходу задержки приписывается значение ”х” которые "продвигается" к выходу схемы. При этом выполняются те же операции и соблюдаются те же условия, как и в процедуре х-продвижение. При выполнении D-v-продвижения выходу задержки присваивается значение ее входа и производятся вычисления, аналогичные вычислениями при v-продвижении. Число D-x и D-v-продвижений зависит от числа задержек и их места в схеме. Так, в случае пяти последовательно соединенных задержек потребуется выполнить пять раз D-x и D-v-продвижения. Проектирование сложных цифровых устройств, как правило, ведут с учетом проблемы состязаний. Для устранения состязаний используют следующие приемы: 1) введение специальных элементов для создания задержек в заданных частях схемы; 2) изменение структуры схемы с целью устранения состязаний логического типа; 3) анализ функционирования на рабочих и тестовых входных наборах и их изменение с целью устранения состязаний; 4) съем выходных сигналов с задержкой (для устранения влияния неопасных состязаний); 5) использование синхронизации при разработке схем с памятью. 7. ПРИМЕНЕНИЕ КОДИРОВАНИЯ ДЛЯ КОНТРОЛЯ ПЕРЕДАЧИ ИНФОРМАЦИИ При контроле передачи информации наибольшее распространение получили методы информационной избыточности, использующие коды с обнаружением и коррекцией ошибок. Если длина кода n разрядов, то таким двоичным кодом можно представить максимум 2n различных слов (т.е. различных комбинаций двоичных значений из n разрядов). Если все разряды слова служат для представления информации, код называется простым (неизбыточным). Коды, в которых только часть кодовых слов используется для представления информации, называются избыточными. Часть слов в избыточных кодах являются запрещенными, и их появление при передаче информации свидетельствует о наличии ошибки. Принадлежность слова к разрешенным или запрещенным словом определяется правилами кодирования и для различных кодов эти правила различны. Коды разделяются на равномерные и неравномерные. В равномерных кодах все слова содержат одинаковое число разрядов. В неравномерных кодах число разрядов в словах может быть различным. В вычислительных машинах применяются преимущественно равномерные коды. Равномерные избыточные коды делятся на разделимые и неразделимые. Разделимые коды всегда содержат постоянное число информационных (представляющих передаваемую информацию) и избыточных разрядов, причем избыточные разряды занимают одни и те позиции в кодовом слове. В неразделимых кодах разряды кодового слова невозможно разделить на информационные и избыточные. Ошибки приводят к искажению значений разрядов кода. Если искажается r разрядов, то говорят, что имеет место ошибка кратности r. Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова n, то кодовое расстояние может принимать значения от 1 до n . Способность кода обнаруживать или исправлять ошибки определяется так называемым минимальным кодовым расстоянием. Минимальным кодовым расстоянием данного кода называется минимальное расстояние между двумя любыми словами в этом коде. Если имеется хотя бы одна пара слов, отличающихся друг от друга только в одном разряде, то минимальное расстояние данного кода равно 1. Например, предположим передается четырехразрядный код и возможны четыре разных кодовых слова: 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 . Очевидно, минимальное кодовое расстояние, в данном случае, равно 2. Простой (неизбыточный) код имеет минимальное расстояние dmin=1 Для разделимых избыточных кодов dmin >1. Если dmin = 2, то любые два слова в данном коде отличаются не менее чем в двух разрядах. Следовательно, любая одиночная ошибка приведет к появлению запрещенного слова и может быть обнаружена. Если dmin = 3, то любая одиночная ошибка создает запрещенное слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова - не менее чем в двух разрядах. Заменяя запрещенное слово ближайшим к нему (в смысле кодового расстояния) разрешенным словом, можно исправить одиночную ошибку. Ошибки приводят к искажению значений разрядов кода. В общем случае, чтобы избыточный код позволял обнаруживать ошибки кратностью r, должно выполняться условие : dmin r+1 . Действительно, одновременная ошибка в r разрядах слова создает новое слово, отстоящее от первого на расстоянии r. Чтобы оно не совпало с каким-либо другим разрешенным словом, минимальное расстояние между двумя разрешенными словами должно быть хотя бы на единицу больше, чем r. Для исправления r-кратной ошибки необходимо, чтобы новое слово, полученное в результате ошибки, не только не совпадало с каким-либо разрешенным словом, но и оставалось ближе к правильному слову, чем к любому другому разрешенному слову. От одного правильного слова другое правильное слово отстоит на расстояние r. Следовательно, от любого другого разрешенного слова оно должно отстоять не менее чем на r+1, а минимальное кодовое расстояние должно быть не меньше суммы этих величин: dmin 2r + 1. При контроле передачи информации часто применяется код с проверкой по четности или нечетности. Такой код образуется путем добавления к группе информационных разрядов, представляющих собой простой (неизбыточный) код, одного избыточного (контрольного) разряда. При формировании слова в контрольный разряд записывается 0 или 1 таким образом, чтобы сумма единиц в слове, включая избыточный разряд, была четной (при контроле по четности) или нечетной (при контроле по нечетности). В дальнейшем при всех передачах (включая запись в память и считывание) слово передается вместе со своим контрольным разрядом. Если при передаче информации приемное устройство обнаруживает, что в принятом слове значение контрольного разряда не соответствует четности (нечетности) суммы единиц слова, то это воспринимается как признак ошибки. Минимальное расстояние кода с проверкой четности (нечетности) dmin = 2, поэтому он обнаруживает все одиночные ошибки, а кроме того, все случаи нечетного числа ошибок (3, 5 и т.д.). При одновременном возникновении двух или любого другого четного числа ошибок код с проверкой четности (нечетности) не обнаруживает ошибок. При контроле по нечетности контролируется полное пропадание информации, так как кодовое слово, состоящее из нулей, относится к запрещенным. Код с проверкой четности имеет небольшую избыточность и не требует больших затрат оборудования на реализацию контроля. Этот код широко применяется в вычислительных машинах для контроля передач информации между регистрами и для контроля считываемой информации в оперативной памяти. Легко установить связь кодирования при контроле по четности с выполнением сложения по модулю 2. Если число единиц в слове должно быть четным, то в контрольный разряд записывается прямой код суммы по модулю 2 всех информационных разрядов слова. При контроле на нечетность в контрольный разряд заносится обратный код указанной суммы. В ЭВМ, например, в оперативной памяти, в запоминающих устройствах на магнитных носителях применяют корректирующие коды, позволяющие не только обнаруживать, но и исправлять ошибки. К таким кодам относятся код Хэмминга, групповые корректирующие коды, циклические коды и другие. Код Хэмминга строится таким образом, что к имеющимся информационным разрядам слова добавляется определенное число контрольных разрядов, которые формируются перед передачей информации путем подсчета четности суммы единиц для определенных групп информационных разрядов. Контрольная аппаратура на приемном конце образует из принятых информационных и контрольных разрядов корректирующее число, которое равно 0 при отсутствии ошибки либо указывает место ошибки, например двоичный порядковый номер ошибочного разряда в слове. Ошибочный разряд автоматически корректируется путем изменения его состояния на противоположное. Требуемое число контрольных разрядов (разрядность корректирующего числа) определяется из следующих соображений. Пусть кодовое слово длиной n разрядов имеет m информационных и k = n - m контрольных разрядов. Корректирующее число длиной k разрядов описывает 2k состояний, соответствующих отсутствию ошибки и появлению ошибки в i-м разряде. Таким образом, должно соблюдаться соотношение: 2k n + 1 или 2k - k - 1 m. Из этого неравенства следует, например, что пять контрольных разрядов позволяют передавать в коде Хэмминга от 1 до 26 информационных разрядов и т.д. Таким образом, избыточность кода Хэмминга значительно выше избыточности кода с проверкой четности. Контроль по коду Хэмминга реализуется с помощью набора схем подсчета четности, которые при кодировании определяют контрольные разряды, а при декодировании формируют корректирующее число |