Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Задачи, решаемые при разработке цифровых логических устройств, можно разделить на две категории:
1. Синтеза.
2. Анализа.
Синтез - это процесс построения схемы цифрового устройства по заданию.
Анализ - процесс обратный синтезу.
дискретного устройства, отражающая только его свойства по переработке сигналов, называется дискретным (цифровым) автоматом.
В общем случае, модель представляет собой многополюсный черный ящик с m входами и n выходами (рис.1.3). Состояние автомата определяется состояниями сигналов на его входах и выходах. Совокупность входных и выходных переменных Х и Z образуют входное и выходное слово автомата, соответственно.
Различные значения входных переменных образуют алфавит (т.к. алфавит входных и выходных переменных един, в дальнейшем будет рассматриваться только один алфавит). В цифровой технике алфавит входного (выходного) слова содержит два значения (две буквы) "1" и "0".
Каждое слово - набор переменных на входе или на выходе автомата, отличается от другого слова хотя бы одной буквой. Каждая буква слова поставлена в соответствие с номером входа (выхода) автомата.
Функционально полная система логических функций представляет собой набор логических функций, с помощью которых можно записать любую, сколь угодно сложную функцию. В этом случае говорят, что этот набор образует базис. Функционально полными являются 3 базиса:
1) "И-ИЛИ-НЕ" (базис конъюнкции, дизъюнкции, инверсии)
2) "И-НЕ" (базис Шеффера)
3) "ИЛИ-НЕ" (базис Пирса или функция Вебба).
Элементы, реализующие операцию "И-НЕ", “ИЛИ-НЕ” и “Исключающее ИЛИ” на принципиальных и структурных схемах изображаются так:
Полусумматор находит сумму двух двоичных чисел 0 и 1 согласно таблице сложения:
+ | ||
Пусть p и q обозначают числа, которые требуется сложить, d0 – младший разряд суммы, d1 – старший (разряд переноса). Тогда приходим к следующим таблицам истинности:
Табл. 1
p | q | d0 | d1 |
Следовательно, , где черта сверху обозначает отрицание, а знак конъюнкции для краткости опущен. Это выражение можно преобразовать в . Бит d1 выражается ещё проще, d1=p&q.
Если обозначить логические элементы следующим образом:
то полусумматор можно представить в виде следующей простой схемы:
Рис.1 Схема полусумматора на элементах «НЕ-ИЛИ-И».
Если теперь использовать полусумматор как отдельный логический элемент с двумя входами и двумя выходами, обозначим его значком
Полный сумматор складывает три одноразрядных двоичных числа. Следовательно, он может сложить два двоичных числа с тем числом, которое «переносится». Обозначим два складываемых числа через p и q, а бит переноса – r. На выходе будем иметь два бита суммы – младший D0 и старший –D1, который будет являться битом переноса для следующего разряда. Имеем следующие таблицы истинности:
Табл. 2
p | q | r | D0 | D1 |
Можно видеть, что D0 есть результат сложения d0, полученного в полусумматоре, c r, а D1 можно получить из таблицы истинности в виде формулы
Это выражение можно сократить, воспользовавшись картой Карно:
q ~q
x | x | x | |
x |
p
~p
r ~r r
В итоге получим
поэтому сумматор может быть представлен в виде следующей схемы:
Рис. 2. Схема сумматора.
Процессы контроля и восстановления информации в ЭВМ. Коды Хемминга: исправление одиночных ошибок, обнаружение двойных ошибок.
В ЭВМ, снабженной системой автоматического контроля, возникновение ошибок в каком-либо устройстве порождает сигнал ошибки, с появлением которого приостанавливается выполнение программы целиком или только рабочей процедуры в неисправном устройстве. При этом 1 в соответствующем разряде регистра ошибок, высвечиваемом на сигнальном табло на пульте оператора, указывает укрупненно место, где обнаружена ошибка (устройство, узел, регистр, группа разрядов регистра и т. д.). Сигнал ошибки инициирует работу системы восстановления.
Система автоматического восстановления во взаимодействии с системой автоматического контроля обычно выполняет следующие функции:
1) распознавание характера обнаруженной ошибки, т. е. выяснение, вызвана ошибка случайным сбоем, перемежающимся или устойчивым отказом;
2) организация «рестарта», т. е. продолжения выполнения программы путем устранения возникающей ошибки в информации повторением ошибочно выполненной микрооперации, команды или сегмента программы (при обнаружении, что ошибка
вызвана сбоем);
3) запись в память информации о сбое;
4) инициирование (при обнаружении отказа) работы системы автоматического диагностирования (САД).
На САД в данном случае возлагается:
1) локализация места отказа с заданной степенью подробности, например до уровня сменной платы, и, если возможна реконфигурация, т. е. отключение неисправного узла
Или устройства с передачей его функции другому соответствующе
узлу или устройству; У
2) запись в память информации об отказе для последующей обработки.
Общая логика взаимодействия систем автоматического контроля, восстановления и диагностирования показана н рис. 12.4. Первой выполняется процедура обработки сигнала прерывания. от системы контроля, начинающаяся записью состояний регистров процессора и старого слова состояния программы (ССП) в соответствующие ячейки памяти и выборкой нового ССП системы восстановления. Далее производится запись в специальные регистры или ячейки памяти ситуации в ЭВМ в момент обнаружения ошибки (записывается состояние запоминающих элементов и шин передачи данных неисправного устройства) '.
Для распознавания характера ошибки (сбой или отказ) необходимо повторить, может быть, даже несколько раз, операцию, в которой обнаружилась ошибка. Однако желательно это сделать с минимальными потерями времени. С этой точки зрения лучше всего, если процессор и система контроля выполнены таким образом, что проверяется правильность каждой микрооперации и вычислительный процесс останавливается на ошибочно выполнившейся микрооперации, которая может быть повторена. Микрооперация (команда) может быть повторена, если не исказилась используемая в операции информация (операнды, адреса и т. д.), т. е. если не пройден «порог повторения». Это проверяет входящая в систему программа обработки ошибок, которая по записанной ситуации, соответствующей появлению ошибки, определяет, пройден или нет порог повторения микрооперации или команды 2. Если соответствующий порог пройден, то вместо микрооперации повторяется команда, а вместо команды — сегмент программы. Последнее возможно, если программист предусмотрел в программе «контрольные точки», сохраняющие промежуточные данные, позволяющие повторить программу с данного места.
Если при повторении микрокоманды (команды, сегмента, программы) ошибка не повторяется, событие распознается как сбой и происходит возврат к точке прерывания программы, но перед этим в память записывается дополнительная информация состоянии в момент сбоя вычислительной системы (какие в это реМя выполнялись операции в периферийных и других устрой-| ствах, название программы, адрес команды, операнды, время). I мнформация о ситуациях при сбоях и об отказах накапливается (во внешнем ЗУ и в последующем обрабатывается специальной программой, вырабатывающей определенные рекомендации обслуживающему персоналу, выполняющему профилактические работы.
Если при определенном числе повторений (например, восемь) ошибка сохраняется, событие распознается как отказ и автоматически приводится в действие САД для определения места неисправности. Диагностические процедуры также могут включаться вручную с пульта, например при пуске машины.
После выявления места отказа проверяется возможность -реконфигурации путем автоматического отключения неисправного устройства и передачи его функций другому устройству. Если это возможно, то производится реконфигурация системы. Затем после сообщения оператору об отказе и произведенной реконфигурации происходит возврат к контрольной точке программы. Если реконфигурация невозможна, САД инициирует на пульте код неисправности. Оператор, пользуясь справочником неисправностей, находит неисправный блок, ремонтирует или заменяет его, затем с пульта включает диагностические процедуры. Если отказ устранен, производится возврат к контрольной точке программы.
КОДЫ ХЕММИНГА
Коды Хемминга для исправления одиночных ошибок являются классической схемой, применяемой для контроля и исправления информации в оперативной памяти. Для обычной практики достаточным является умение находить и корректировать одиночные ошибки и обнаруживать двойные ошибки без исправления.
В основе метода лежит принцип проверки некоторого подмножества бит на четность, то есть рассматривается число двоичных единиц в рассматриваемом подмножестве, которое (число) должно быть четным (или, если по-другому договориться, нечетным; принципиально здесь разницы нет, но дополнение до нечета несколько лучше электротехнически, так как здесь обнаруживается разница между нулем и отсутствием сигнала). Любое контролируемое подмножество бит при этом должно содержать контрольные разряды.
Проверки должны быть построены так, чтобы в совокупности давать максимум информации о наличии и положении ошибки. Для этого они должны быть независимы. Это означает, что никакая сумма одних проверок не совпадает ни с какой другой проверкой. Например, три проверки на четность в позициях
1: 1,2, 5, 7
2: 5, 7,8,9
3: 1,2, 8,9
являются зависимыми, поскольку сумма любых двух строк покрывает третью строку.
Пусть нам дано m контрольных разрядов. С их помощью можно различить не более 2m событий. Одно из них состоит в том, что все символы сообщения правильны, а остальные должны давать местоположение одной из n возможных одиночных ошибок. Это приводит к неравенству
или
Если имеет место точное равенство, то код называется совершенным. В совершенном коде Хемминга имеется 2m-1 разрядов, из которых 2m-m-1 информационных.
Существует понятие избыточности кода, определяемое как отношение общего числа бит в сообщении к числу полезных бит. Для кода Хемминга избыточность быстро уменьшается с ростом размера информационного блока, и в пределе равна 1+log2n.
Контрольные разряды сообщения ставятся в позиции, соответствующие целым неотрицательным степеням числа 2, то есть в позиции 1,2, 4,8,16,… и т.д. Для того, чтобы определить номера разрядов, входящих в соответствующую проверку, выпишем двоичное представление номеров позиций:
№ | |||||||||||||||
Двоич. |
В первую проверку включим те разряды, двоичные номера которых содержат единицу в младшем разряде, во вторую – те, у которых 1 стоит во 2-м справа разряде номера и т.д. Получатся следующие последовательности проверок:
1: 1,3,5,7,9,11,13,15,…
2: 2,3,6,7,10,11,14,15,…
3: 4,5,6,7,12,13,14,15,…
4: 8,9,10,11,12,13,14,15,…
……………………………
Синдромом называется двоичное число, состояшее из m бит, которое получается, если написать символ 0 для каждой выполненной проверки, и 1 – для каждой невыполненной. Нулевой синдром означает отсутствие ошибки, в противном случае он будет указывать позицию ошибки. Поскольку информационные и проверочные символы принимают равное участие в кодовом слове, код является равномерно защищенным.
Для иллюстрации сказанного приведем следующий простой пример на 15-разрядной сетке. Через Kr обозначим контрольные разряды сообщения, а через Is – информационные. Пусть требуется передать следующие 11 бит информации: 01101111010. Примем методику дополнения до нечета. Сначала заполним информационные позиции, а затем построим соответствующие контрольные:
№ разр. | |||||||||||||||
K/I | K1 | K2 | I1 | K3 | I2 | I3 | I4 | K4 | I5 | I6 | I7 | I8 | I9 | I10 | I11 |
ЗНАЧ. |
Пусть при передаче сообщения ошибка появилась в одном из разрядов, например, в 10-м. Внесем в разрядную сетку «испорченное» сообщение и найдем синдром S.
№ разр. | |||||||||||||||
K/I | K1 | K2 | I1 | K3 | I2 | I3 | I4 | K4 | I5 | I6 | I7 | I8 | I9 | I10 | I11 |
ЗНАЧ. | 0* |
Разряды первой проверки дают нечетное (3) число единиц, значит, она выполняется и мы пишем 0. Вторая проверка дает 6 единиц, значит, она не выполнена, и мы пишем 1. Аналогично выполнив оставшиеся проверки, получим синдром S=1010, что соответствует числу 10. Следовательно, в принятом сообщении следует исправить 10-й разряд.
Что произойдет в случае двойной ошибки? Система вычислит ненулевой синдром, но теперь он уже не будет правильно указывать позицию ошибки. Следовательно, вместо двух ошибок мы будем иметь три. Для получения кода с дополнительным обнаружением двойных ошибок (без возможности исправления) добавим ещё одну проверку на четность и еще один разряд, охватив проверкой всё сообщение. Тогда каждая одиночная ошибка по-прежнему будет давать правильный синдром, а дополнительная проверка – 1. Обзор возможных случаев приводится в следующей таблице:
Первоначальный синдром | Новая проверка на четность | Смысл |
Правильно | ||
Ошибка в дополнительной позиции | ||
Любой | Одиночная ошибка | |
Любой | Двойная ошибка |
Ошибки более высокой кратности достаточно редки, и необходимость их корректировки может возникнуть при создании систем повышенной надежности, например, в авиационной, военной или космической технике. Вероятность появления k – кратной ошибки в блоке из n бит при вероятности ошибки в отдельном бите, равном p, и независимом возникновении ошибок в разных разрядах, выражается формулой
и при малых p быстро уменьшается с ростом k.
Дата публикования: 2015-02-18; Прочитано: 1254 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!