Самокорректирующееся дискретное устройство Советский патент 1992 года по МПК G06F11/14 G06F11/18 

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

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

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

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

с

СХ

ел ю

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

Недостатком устройства является низ- кая надежность в работе при осуществлении коррекции ошибок большей кратности (вследствие резкого увеличения сложности резервного оборудования).

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

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

На фиг. 1 представлена схема устройства; на фиг. 2 - схема корректора.

Устройство содержит (фиг. 1): исходный комбинационный логический блок 1, избыточный комбинационный логический блок 2, дешифратор 3 ошибки, корректор 4, элемент ИЛИ 5. Корректор 4 (фиг. 2) содержит элементы 16-21 неравнозначности.

Входы устройства соединены с входами исходного комбинационного логического блока 1 и входами избыточного комбинационного логического блока 2, информационные выходы которого подключены к входам дешифратора 3 ошибки, выходы которого соединены с управляющими первыми вхо- дами корректора 4, информационные входы которого подключены к выходам исходного комбинационного логического блока 1, а выходы являются выходами устройства. Входы логического элемента ИЛИ 5 соединены с

соответствующими контрольными выходами избыточного комбинационного логического блока 2, выход подключен к второму управляющему входу корректора 4, информационные выходы исходного комбинационного логического блока 1 соединены с входами дешифратора 3 ошибки.

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

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

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

Рассмотрим функциональную модель комбинационного дискретного устройства, содержащую гп-входов и k-выходов.

На вход дискретного устройства может быть подано /Х/-возможных xi-входных воздействий.

Комбинация значений выходных сигналов дискретного устройства образует выходной набор V Ј- f Kyi, У2,..., yk). На выходе дискретного устройства может быть получено множество/Yfc 2 -всех возможных выходных наборов.

Определение .1. Два выходных набора i(yi. и,..., yk) и (yi, у2,..., yk) будем считать прямым и обратным, если одноименные выходные сигналы в данных наборах имеют противоположные значения. Например, для прямого выходного набора 101 трехвыходного дискретного устройства, обратным выходным набором является комбинация 010.

Определение 2. Функцию f 0(yi, У2ytc); описывающую взаимное отношение между выходными сигналами прямого и обратного выходных наборов, будем называть определяющей функцией. Для рассмотренных комбинаций прямого и обратного выходных наборов определяющая функция имеет вид Y у2, уз).

Анализ выбранной математической модели позволил выявить следующие ее свойства:

Свойство 1. Множество выходных наборов У может быть описано определяющими функциями.

Свойство 2. Множество выходных воздействий X включает подмножеств входных воздействий iXil, IXal,....-)Хм1, каждое из которых обеспечивает истинность соответствующей определяющей функции.

Так как аргументы определяющих функций между собой находятся в строгом соответствии, to зная истинное значение (соответствующее логической единице или логическому нулю) одного из аргументов, можно определить значения всех других выходных сигналов для данного выходного набора. Для того, чтобы иметь такую возможность, разобьем множество |х| на два подмножества |XiJ и|Хц| таких, что: (Xt)(Xn)0.

Свойство 3. Любой выходкой набор дискретного устройства может быть представ лен в виде:

Yf f (Xi,Xfl,(1) где Xf6 N, , X2XN};

Xje M, , Xn}.

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

©Y| ,

где Y| - выходной набор, имеющий ошибку.

Так как значение выходного набора У Ј определяется в соответствии с выражением (1), то формально вектор ошибки можно представить в виде

Ek f(Xi, Xj, Yf ).

Из полученного выражения следует, что коррекция выходного набора может быть выполнена, если осуществить кодирование выходного набора по |Х|) и |Xj| подмножеством входных наборов.

Утверждение 1. Минимальное количество дополнительных разрядов, необходимых для формирования вектора ошибки Ek, исправляющего К-кратную ошибку, определяется выражением г К, где г - число дополнительных разрядов.

Действительно, для задания выходного набора Y| f(Xi, Xj) необходимо использовать два подключателя входных наборов .

Тогда минимальное число символов, с помощью которых можно осуществить передачу N+M сообщений, равно Hog22K 1+log22 K. Таким образом, любая К-кратная ошиб- ка На выходе дискретного устройства может быть скорректирована при условии отсутствия ошибки в проверочных разрядах.

Для того, чтобы повысить вероятность безотказной работы дискретного устройства, резервированного предлагаемым методом, необходимо кодовые слова, подаваемые с проверочных разрядов, разнести на расстояние d 1зар+ 1, где 1эад - кратность ошибки, обнаруживаемой в проверочных разрядах. С целью уменьшения числа проверочных разрядов, вводимых для обеспечения данного условия, целесообразно ограничиться обнаружением одиночной ошибки.

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

Исходный комбинационный логический блок 1 представляет собой комбинационное трехвыходное дискретное устройство, реализованное в известном устройстве, и вы- полняющее на каждом выходе логические функции соответственно:

yiHh 32§з V3i§2a3vaia2a 3V 313232 V313233V va 1агаз;

y2 ai3233vaia2a3V3i32a3V §13233; уз-31а2азуа v зтагаз у 313233. Истинность для рассматриваемого исходного комбинационного логического блока представлена в табл. 1.

В соответствии со свойством 2 множе- ство |Х1 ьключает четыре подмножества входных воздействий |Xi|, 1X2), Хз|, РЦ, каждое из которых порождает соответствующую определяющую функцию:

v(xieXi)(yi.y2.y3);

v(xieX2) -э-т2(у1,у2,уз);

V(xieX3)(yi,y2,y3),

V(XieX4) (yi,y2iy3).

Из анализа табл. 1 следует, что каждое

подмножество включает следующие входные воздействия: Xi {xi}; Х2(х5.хб,х7};

,ХЗ,Х4}: Х4(Х8К

Кроме того, множество Х| включает два подмножества Х|-{х1,х2,хз,хб,х7,х8} и Xir- {x4,xs}, для которых у 1 f i(Xi)1 и у i(Xn)0.

Избыточный комбинационный логический блок 2 предназначен для формирования логических сигналов в проверочных разрядах относительно имеющихся подмножеств входных воздействий.

В общем случае подмножества Xi, X2, Хз, Х4 могут быть закодированы на двух контрольных разрядах п и пг, но для того, чтобы выполнить условие обнаружения одиночной ошибки добавим третий контрольный раз- ряд гз. Результаты кодирования занесем в табл. 2, из которой следует, что:

VXo; Г2 Хз VX гз Х2 V Хз.

Используя табл. 1, находим, что Vaia233. аХ,а1Э2аз.

В этом случае в первом контрольном разряде реализуется логическая функция уаз(а1а2У ai32), которая может быть выполнена на базе двухвходовых логических элементов И, ИЛИ. НЕ.

Аналогичным образом построены логические функции, реализуемые на втором и третьем контрольных разрядах избыточного комбинационного логического блока, ко- торые имеют вид:

V v а2§з;

У V 3132 V 313233 V 313233.

Формировэние логического сигнэла в четвертом контрольном рэзряде гз осущест- вляется с помощью логического элементэ ИЛИ 5. В этом случзе (Xii) f(x4 Vxs)

Дешифратор 3 ошибки предназначен для формирования сигналов в разрядах zi, 22, 23 вектора ошибки относительно выход- ных сигналов yi, y2, уз исходного комбинационного логического блока 1 и выходных сигналов в контрольных разрядах п, Г2, гз избыточного комбинационного логического блокэ2.

Для дискретного устройстве, содержэ- щего К-выходов, кэждому xi-входному воздействию соответствует смежный клзсс 2 -векторов, содержэщий 2 -ошибочных векторов.

Так как вектор ошибки Ек(Х|)Ёк(Хц). то количество ошибочных векторов может быть ограничено числом 2к-1/2.

В табл. 3-6 представлены четыре смежных класса выходных векторов рассмзтри- ваемого устройства для xi бХь

Учитывая единичные значения сигналов в рэзрядах вектора ошибки для всех возможных Ys и xi, принадлежащих Xi, X2. Хз, подмножеством входных воздействий (см. табл. 3-6).. проведя аналитические преобразования, получим логические функции, реализуемые на выходах дешифратора 3 ошибки (в разрядах вектора ошибки);

(пгз v пгз) vyir2(rV3 спгЗ);

(Г2ГЗ V Г2ГЗ) V У2П(Г2ГЗ V Г2Гз); (П ГЗ V П ГЗ) V узГ2(г1 гЗ V П Гз).(2)

Корректор 4 (фиг. 2) предназначен для окончательного формирования ошибки и осуществления коррекции ошибки на выходах исходного логического блока.

Формирование значения логического сигнала в каждом разряде вектора ошибки осуществляется с помощью элементов 16- 18 неравнозначности соответственно.

В этом случае значение сигнала в разряде вектора ошибки, определяется выражением: 2| 2| @Г4.

На элементах 19-21 неравнозначности происходит коррекция ошибки выходных сигналов исходного комбинационного логического блока 1.

Устройство работает следующим образом.

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

Рассмотрим работу устройства в режиме коррекции, например, при подаче вход-: ного набора xi, порождающего выходной набор . Пусть, в результате возникновения дефекта для данного входного воздействия, получен выходной набор , имеющий ошибку. В этом случае в проверочных разрядах п, га. гз, Г4 присутствуют сигналы, соответствующие логическому нулю. Используя систему уравнений (2) находим, что (так как ггушгз) порождает логическую единицу). (так как 1у2Г2 з) порождают логическую единицу). 23 0 (так как 2узг1Гз- -0, так как уз 0).

Так как значение , то сигналы ZL 22, 23 на элементах 16-18 не инвертируются.

Сигнэлы 21 и Z2, поступающие на элементы 19 и 20 неравнозначности, обеспечивают коррекцию сигналов У1 и у2.На выходе устройства получаем скорректированное значение выходного набора Y 111. .

Аналогичным образом устройство рэ- ботзет при подэче других входных воздействий и наличии ошибок другой кратности.

Возникновение одниночной ошибки в проверочных разрядах п, Г2, гз не приводит формированию единичных значений в рзз- ряде векторэ ошибки.

Для сзмокорректирующегося дискретного устройства, реализующего метод вычисления синдрома, сложность декодирующего устройства составляет

(),ii Ск +(п-К) +4К 121Лэ.

При использовании предлагаемого метода сложность декодирующего устройства составляет

Цек.п (п-1) Ј Ск + п +

1 1. .

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

Рс РкодРс Ј Сз|Рб3 |(1-Рб) - 1 0

РкодРС Рб3+ЗРб2(1-Рб)+

+ ЗРб(1-Рб)2+ (1-Рб)3. (3) где Ре - вероятность безотказной работы по одному информационному выходу дискретного устройства;

Рс - вероятность безотказной работы декодирующего устройства;

Ркод - вероятность безотказной работы кодирующего устройства.:

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

Если принять интенсивность отказа одного двухвходового элемента А 0,1-КГ5

--, то его вероятность безотказной работы час-f

равна .

Тогда вероятность безотказной работы по одному выходу составляет .

Соответственно Рс Рлэ121. Минимизированную сложность кодирующего устройства определяем, используя выражение (2)

1.код(Ш-п). где , общее число разрядов.

В этом случае Ркод Рлэ36.

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

Подставляя полученные значения в выражение (3), определяем вероятность отказа Qc,

,5907M(T4.

Для предлагаемого устройства вероятность безотказной работы оценивается выражением.п(Рб3+ЗРб2(1-Рб)+ЗРб(1-Рб) +

+ (1-РбГрЛ4Рк3(1-Рк),(4)

где РК вероятность безотказной работы по одному выходу кодирующего устройства. Средняя сложность кодирующего устройст- 0 ва по одному выходу составляет семь двух- входовых элементов, т.е. .

Pr-D 66

Подставляя полученные значения выражение (4). определяем вероятность отказа 5 для предлагаемого способа ,6875-1(Г5.

Формула изобретения

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

5 корректор, входы устройства соединены с входами исходного комбинационного логического блока и входами избыточного комбинационного логического блока, информационные выходы которого подключе0 ны к входам блока вычисления синдрома,

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

5 информационные выходы исходного комбинационного логического блока соединены с входами эталонных сигналов дешифратора ошибки.

fll&fat tta

/По.&л.и-цл &

Изобретение относится к вычислительной технике и может быть использовано для повышения надежности комбинационных дискретных устройств. Цель изобретения - повышение надежности устройства. Устройство содержит исходный комбинационный логический блок, избыточный комбинационный логический блок, дешифратор ошибки, корректор, элемент ИЛИ. Повышение надежности достигается за счет использования метода информационного резервирования. 2 ил. 6 табл.

/ПаЈл.ъе,чА 3

/ПаЛица Ј

/71еь1Гли#а. &

/rtafauttA 6

а г

IB

17

71k.

10

11

П

3 - fa

19

e

20

Щ &2

ft з

21