Проблема синтеза надёжных схем из ненадёжных элементов

Рассмотренные ранее методы синтеза схем ЦА исходят из задачи наиболее экономного расходования элементов, как ЗЭ так и ЛЭ. По самому определению наиболее экономной схемы она должна обладать тем свойством, что выход из строя любого её элемента вызывает выход из строя всей схемы в целом, потому что, если в схеме есть элементы, которые могут исключить, не нарушая работы схемы, то такая схема не будет минимальной по числу элементов, использованных при её построении.

Различают 2 вида неисправностей ЦА. Неисправность первого вида – отказ, состоит в том, что начиная с некоторого момента времени и во все последующие моменты времени элемент перестаёт функционировать или функционирует неверно. Второй вид неисправности – это мгновенная самоустраняющаяся неисправность, называемая сбоем. наступление сбоя означает, что элемент не сработал или неправильно сработал в течение одного такта работы автомата, но возникшая таким образом неисправность вовсе не должна сохраняться на протяжении последующих тактов.

Современные сложные электронные ЦА состоят из многих тысяч ЛЭ и ЗЭ, требования к надёжности их работы очень высоки (вероятность сбоя ЦА должно быть ), вероятность сбоя отдельных элементов . В ряде случаев требования к надежности элементов оказываются практически невыполнимыми, и тогда возникает проблема построения высоконадёжных схем из относительно ненадёжных элементов.

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

Наиболее распространёнными является дублирование. Способ дублирования ЦА сводится к замене одного автомата двумя одинаковыми автоматами, выходы которых в процессе функционирования дублируемых автоматов постоянно сравниваются с помощью специальной схемы сравнения. Дублирование не учитывает внутреннюю структуру ЦА; с его помощью обнаруживаются ошибки любой кратности, возникающие на выходах одного из дублируемых устройств, а также ошибок, возникающие на выходах двух устройств одновременно, приводящие к появлению неодинаковых векторов выходов дублируемых устройств.

Недостатки дублирования:

- большая структурная избыточность требующая усвоения оборудования.

Пример: Продублировать ЦА А, имеющий три выходных канала .

Состояние выходов продублированного устройства можно представить в виде матрицы G при контроле:

,линейный групповой код

а так называемая функция декодирования имеет вид:

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

Другой распространённый метод – мажорирование. Мажорирование позволяет вырабатывать правильный выходной сигнал при наличии неисправностей в ЦА и определять место их появления с точностью до указания номеров неправильно работающих устройств. Мажорирование требует для своей организации использования нечётного числа устройств, работающих параллельно. Выработка правильного выходного сигнала устройства осуществляется мажоритарным ЛЭ. Для определения номеров неправильно работающих устройств необходимо дополнительно иметь специальный элемент анализа (ЭА).

Пример: Выполнить мажорирование для ЦА с одним выходом .

			f

f – выход устройства, - выходы элемента анализа.

для ЭА:

Недостаток метода – большая структурная избыточность.

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

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

Различают избыточные коды с обнаружением ошибок и избыточные коды с исправлением ошибок (самокорректирующиеся коды).

Простейший избыточный код – код с проверкой на чётность. Такой код получают путём добавления к слову одного контрольного разряда, в который записывают 0 или 1 с тем, чтобы число 1 в полученной кодовой комбинации было нечётным. Если, например, исходное слово А=10101100, то в коде с проверкой на чётность оно будет представлено как A`=101011001. Если А=10101101, то A`=101011010.

Таким образом любая ошибка нечётной кратности обнаруживается этим кодом.

К кодам с исправлением ошибок относятся коды Хэмминга, предназначенные для исправления одной ошибки или обнаружения двух и исправления одной ошибки. (см. К.Г.Самофалов ЭЦВМ стр.466).

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

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

Такие коды имеют несколько контрольных разрядов (КР), каждый из которых контролирует по чётности свою группу разрядов в слове. Эти группы формируются так, чтобы исследовательный опрос КР указал место сбоя. В КР записывается такая цифра, чтобы количество “1” в контролируемых разрядах было нечётным.

Представим кодовую комбинацию с числом разрядов n=15. Тогда схема формирования КР в коде Хэмминга имеет вид:

КР А контролирует по чётности все нечётные разряды кода. В КРА записывается такая цифра, чтобы количество “1” в нечётных разрядах было нечётным. Таким образом КРА контролирует по чётности все разряды в номерах которых есть “1” в первом разряде (в двоичном представлении).

КР В контролирует по чётности разряды в номерах которых есть “1” во втором разряде.

КР С контролирует по чётности разряды в номерах которых есть в третьем разряде.

КР Д контролирует по чётности разряды в номерах которых есть в четвёртом разряде.

Контрольные разряды могут быть размещены среди информационных различными способами. Наиболее удобно их размещать на 1,2,4,… позициях, так как в этом случае каждый КР принадлежит только одной, соответствующей ему группе разрядов.

Если число КР=К, то длина кодовой комбинации n определяется таким образом:

,

при k=4 . Отсюда можно найти k , так как при работе кода возможны n+1 результатов: ошибки нет, ошибка в 1-м разряде, во 2-м разряде и так долее.

Пример 1. сформируем КР для слова х=01110100101. Длина слова m=11, k=4, n=15. следовательно код Хэмминга должен иметь вид:

АВ0С111D0100101

Для определения значений А, В, С, D решим уравнения:

А+0+1+1+0+0+1+1=1 (mod 2)=1 А=1

В+0+1+1+1+0+0+1=1 (mod 2)=1 В=1

С+1+1+1+0+1+0+1=1 (mod 2)=1 С=0

D+0+1+0+0+1+0+1=1 (mod 2)=1 D=0

Таким образом, слово х в коде Хэмминга примет вид: 110011100100101.

Пример 2. найти ошибку в слове х=110011100101101. для этого сформируем суммы по mod 2 разрядов, контролируемых разрядами А, В, С,D.

A=1+0+1+1+0+0+1+1 (mod 2)=1

B=1+0+1+1+1+0+0+1 (mod 2)=1

C=0+1+1+1+1+1+0+1 (mod 2)=0

D=0+0+1+0+1+1+0+1 (mod 2)=0

Следовательно, ошибка в разряде с номером 1100. Если ошибки нет, то проверка по всем КР даёт номер разряда 0000, которой нет.

Пример 3. Сформируем при наличии ошибок во 2-м и 5-м разрядах слова х=1110001, то есть принято слово x`=1010101.

A=1+1+1+1 (mod 2)=0

B=0+1+0+1 (mod 2)=0

C=0+1+0+1 (mod 2)=0

Таким образом, при двукратной ошибке декодирование даёт номер разряда 111, что неверно.

Незначительное увеличение избыточности кода путём введения дополнительного КР1, осуществляющего проверку на чётность всего кода, позволяет обнаружить все двукратные ошибки. Располагает КР1 на месте “0”–го разряда кода. Признаком наличия двукратной ошибки является равенство нулю функции x` при проверке всех разрядов кода на нечётность и равенство “1” хотя бы одной функции .

Пример 4. Найдём КР1 для слова х=1110001.

A=1+1+0+1=1

B=1+1+0+1=1

C=0+0+0+1=1

I+1+0+0+1 (mod 2)=1 I=1

Таким образом, слово примет вид 11110001.

Пусть принято слово x`=11010101 ошибки во 2-м и 5-м разрядам. Сформируем функции .

A=1+1+1+1 (mod 2)=0

B=0+1+0+1 (mod 2)=0

C=0+1+0+1 (mod 2)=0

I=1+1+0+1+0+1+0+1=1 x`=0

Таким образом, в коде присутствуют 2 ошибки.

Общий недостаток избыточных кодов – они не приспособлены для выполнения арифметической операции.

Глава 14

Микропрограммные автоматы

Задачей УА является выработка распределенной во времени последовательности выходных (управляющих) сигналов, под воздействием которых в ОУ осуществляется некоторая операция.

Элементарный неделимый такт обработки информации в ОА, происходящий в течение одного момента автоматного времени (одного такта работы ЦА), называется микрооперацией. Примеры микроопераций: сдвиг информации, инкремент, декремент, установка «0» или «1», инверсия переменной и т.д.

Если в ОА одновременно реализуется несколько микроопераций, то такое множество называется микрокомандой.

Микрооперации возбуждаются выходными сигналами УА, а их последовательность во времени определяется функциями перехода УА.

Совокупность микрокоманд и функций перехода образует микропрограмму, которая является связующим звеном между командой (кодом операции) и ОА (аппаратными средствами).

Чтобы построить схему УА, нужно задать микропрограмму работы ОА. Микропрограмма может быть задана в виде граф-схемы алгоритма (ГСА).

Граф-схемы алгоритмов

ГСА называется ориентированный граф, содержащий одну начальную вершину (Начало), одну конечную вершину (Конец) и произвольное конечное множество условных и операторных вершин. Любая вершина ГСА, кроме вершины «Начало» имеет по одному входу. Вершина «Начало» входов не имеет. Вершина «Начало» и любая операторная вершина имеют по одному выходу. Вершина «Конец» выходов не имеет. Любая условная вершина имеет два выхода, помеченных символами «Да» и «Нет», либо «1» и «0» соответственно.

ГСА должен удовлетворять следующим условиям:

1. Входы и выходы вершин соединяются друг с другом с помощью дуг, направленных от выхода к входу.

2. Каждый выход соединен только с одним входом.

3. Любой вход соединяется, по крайней мере, с одним выходом.

4. Любая вершина ГСА лежит хотя бы на одном пути от «Начало» в «Конец».

5. Один из выходов условной вершины может соединяться с ее входом, что недопустимо для операторной вершины.

6. Разрешается в различных условных вершинах записывать одинаковые логические условия.

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

Будем называть микропрограммнымавтоматом конечный автомат Мили или Мура, построенный по граф-схеме алгоритма. При построении микропрограммного автомата считают, что его входной алфавит совпадает с множеством сигналов логических условий, выходной алфавит – с множеством сигналов выполнения отдельных микроопераций, а алфавит состояний и функций переходов задается графом автомата. Работа такого автомата тактируется генератором синхросигналов, причем период следования этих сигналов , где - время, необходимое для выполнения i-й микрооперации.

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

Пример. Построить содержательную ГСА УА по размену металлических денег. При этом будем считать, что можно разменивать монеты достоинством 10, 25, 50 коп. на соответствующее число 5 коп. монет. Будем полагать, что в качестве операционных автоматов используются:

блок анализа стоимости размениваемых монет;

блок выдачи монет;

блок анализа наличия монет;

счетчик монет.

Чтобы на основе содержательной ГСА получить необходимый набор состояний микропрограммного автомата прибегают к так называемой отметке ГСА.

Правила построения отмеченной ГСА различны для автоматов Мили и Мура.

Если необходимо построить микропрограммный автомат Мили, то содержательная ГСА УА размечается в соответствии такими правилами:

1) символом отмечают вход первой вершины, следующей за вершиной «Начало». А также вход вершины «Конец»;

2) входы вершин (операторных или условных), следующих за операторными вершинами, отмечают символами , …

3) входы двух различных вершин, за исключением вершины «Конец», отмечаются различными символами;

4) вход вершины может отмечаться только одним символом;

5) содержательные термины микроопераций и логических условий заменяются их условными обозначениями.

После разметки ГСА УА по размену денег примет вид:

Если необходимо построить автомат Мура, то разметку делают т.о.:

1) символом отмечают вершины «Начало» и «Конец»;

2) различные операторные вершины отмечаются различными символами , …

3) все операторные вершины должны быть отмечены.

Вид отмеченной ГСА для УА по размену денег представлен на рис. 3.

После полученной отмеченной ГСА строится граф автомата Мили или Мура. Он имеет столько различных вершин, сколько различных букв с индексами имеется в отмеченной ГСА. Между двумя вершинами графа имеется дуга, если на отмеченной ГСА между этими вершинами есть путь. Над дугой ставится входной сигнал, равный конъюнкции логических условий (и синхросигнала) соответствующего пути. Если путей несколько, то входной сигнал представляет из себя дизъюнкцию конъюнкций. Если строится граф автомата Мура, то символы микроопераций (т.е. выходные сигналы управляющего автомата) записываются около соответствующих вершин. Если в отмеченной ГСА имеется безусловный переход между операторными вершинами, то на графе автомата ставится входной сигнал «1», показывающий, что данный переход происходит при поступлении очередного синхросигнала.

Граф автомата Мили приведен на рис. 4, граф автомата Мура на рис. 5. Дальнейший синтез производится с помощью метода структурного синтеза.

Для построения функциональной схемы автомата Мили составим таблицу переходов-выходов (табл. 1). Кодирование входных сигналов, состояний и выходных сигналов осуществим по таблицам 2, 3, 4 соответственно.

Каждому логическому условию ГСА можно поставить в соответствие физическую одноразрядную шину, считая, что логическое условие есть выходной сигнал определенного ОА. Так «1» на шине будет означать, что монета поступила в блок анализа наличия монет, и он информирует об этом УА. Т.о. двоичный вектор будет представлять совокупный входной сигнал УА, а сигналы , , , , могут быть получены с помощью специальной КС формирования входных сигналов.

Для выходных сигналов автомата , , , чаще удобней использовать также отдельные физические шины. Такая организация выходных каналов автомата целесообразна, если операционные автоматы, которыми управляет синтезируемый автомат, физически разнесены. Кодирование выходных сигналов в соответствии с табл. 4 требует их дешифрации в блоке ОА.

Структурная таблица переходов-выходов УА представлена в табл. 5. В качестве элементов памяти выберем Т-триггеры. Таблица функций возбуждения синтезируемого автомата имеет вид табл. 6, а функции возбуждения и представлены в ДНФ. Функции выходов могут быть получены по табл. 5 или табл. 7.

Микропрограмма, отражающая алгоритм функционирования автомата, может быть записана в ЗУ, чаще всего ПЗУ. При этом могут иметь место некоторые особенности при адресации и кодировании микрокоманд.

Таблица 1

Состояния автомата	Входные сигналы

Таблица 2

Входные сигналы автомата	Код входных сигналов

Таблица 3

Состояния автомата	Код состояний

Таблица 4

Выходные сигналы автомата	Код выходных сигналов

Таблица 5

Состояния автомата	Входные сигналы

Таблица 6

Состояния автомата	Входные сигналы

для Т-триггера.

Таблица 7

Состояния автомата

Входные сигналы

Порядок выполнения микрокоманд определяется логическими условиями, поступающими извне, в частности от ОА. Для того, чтобы реализовать процедуру выбора адреса следующей микрокоманды (в зависимости от значений переменных, отражающих условия) к ПЗУ добавляется схема выбора адреса, суть работы которой в следующем.

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

, , , двоичные адреса, разрядность которых определяется емкостью ПЗУ. После выполнения микрокоманды управление передается микрокоманде с адресом или в зависимости от значения анализируемой переменной .

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

Автоматы, реализованные т.о., называют автоматами с программируемой (гибкой) логикой в отличие от автоматов, схемы которых строятся на основе дискретных элементов – автоматов с жесткой логикой.

В первом случае структура УА включает в себя ЗУ и схему выбора адреса следующей команды (иногда еще схему формирования выходных сигналов микроопераций); во втором – схему их дискретных компонентов, состоящую из элементов памяти и комбинационных элементов.

Оба способа реализации получили дальнейшее развитие на основе программируемых БИС, МП и однородных сред.

ЛИТЕРАТУРА

1. Глушков В.М. Синтез цифровых автоматов. М.: 1967

2. Самофалов К.Г. и др. Прикладная теория цифровых автоматов. К.: 1987

3. Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Цифровые электронные вычислительные машины. - К.: Выща шк., 1983

4. Савельев А.Я. Прикладная теория цифровых автоматов. М.: 1987

5. Справочник по интегральным микросхемам /Под ред. Б.В. Тарабрина. - М.: Энергия, 1980.

6. Каган Б.М., Сташин В.В. Основы проектирования микропроцессорных устройств автоматики. М.: 1987

7. Руденко В.С., Сенько В.И., Чиженко И.М. Основы преобразовательной техники: Учебник для вузов. – 2-е изд., перераб. и доп. – М.: Высш. школа, 1980. – 424с.

8. Шило В.Л. Популярные цифровые микросхемы: Справочник. – М.: Радио и связь, 1988. – 352с.

9. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. – М.: Радио и связь, 1990. – 304с.

10. Зубчук В.И., Сигорский В.П., Шкуро А.Н. Справочник по цифровой схемотехнике. – К.: Тэхника, 1990. – 448с.