Тюрин С.Ф., Алексеев Н.А., Гревцев А.М., Белых А.А.,
г. Пермь

УДК 681.142

МЕТОДИКА АДАПТАЦИИ К ФУНКЦИОНАЛЬНЫМ ОТКАЗАМ
ПОСЛЕДОВАТЕЛЬНОСТНЫХ ЦИФРОВЫХ УЗЛОВ

В отличие от рассматривавшейся ранее адаптации к отказам комбинационных автоматов [1 – 7] предложен подход к адаптации последовательностных устройств на основе адаптации к отказам блока памяти помимо комбинационной части, построенной на функционально-полных толерантных элементах (ФПТ). Предложена методика такой адаптации, зависящая от вида отказа блока памяти.

В связи с широким распространением универсальных программируемых логических устройств (ПЛУ), которые могут реконфигурироваться в процессе эксплуатации, возникают новые возможности для построения отказосбоеустойчивых цифровых автоматов. Предлагается сохранять не исходные логические функции, а базисные функции, позволяющие вычислить исходные за большее время при заданной модели отказов[1 – 4]. Это позволяет восстановить вычислительный процесс при некотором снижении производительности. При этом возникает задача реализации логических функций на массивах элементов с различной разрядностью слов.

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

Матричные преобразования функций можно описать выражением PLA( ,A)= , где , – входной и выходной векторы соответственно, А – начальный адрес массива данных. Реализация последовательного автомата представляется выражением PLA( | | , PAM,A) =  | | , где , – текущее и последующее состояние автомата, PAM – адрес ячейки памяти хранения текущего состояния, А – начальный адрес массива данных.

Для вычисления одной булевой функции достаточно задать матрицы Q, D и вектор , а для вычисления одной конъюнкции – три вектора , , .

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

1. Вычисление многоразрядной конъюнкции.

В этом случае разрядность входных переменных n > r Поэтому необходимо анализировать int n/r или μ подконъюнкций (int – ближайшее целое число, μ –число агрегатов, т.е. групп переменных). Для каждой из подконъюнкций задаются вектора

: { . . . }

: { . . . }

: { . . . }

Так как конъюнкция одна, то вектора имеют единицы в одних и тех же фиксированных позициях, т.е. по существу вектор один для всех подконъюнкций.

Вектора группируются в μ подмассивов с начальными адресами А_J ,j= в каждом подмассиве по одному вектору Q, D, V.

Процесс вычисления можно описать следующим образом:

PLA( , A₁)=V₁,

PLA( , A₂)=V₂,

.

.

.

PLA( , A_μ)=V_μ,

, где Z – результат вычислений. В принципе вычисления заканчиваются при обнаружении нулевого вектора V_j . В общем виде вычисление многоразрядной конъюнкции записывается следующим образом:

PLA( , A_j)=V_j,

, j = 1, μ (1)

Здесь x_j – j–й вектор входных переменных с j-го агрегата, либо с j-й группы переменных, количество которых превышает r.

2. Вычисление многоразрядной булевой функции.

Пусть булева функция имеет k конъюнкций, причем некоторые из них – многоразрядные или зависят от переменных, принадлежащих различным узлам. Многоразрядная булева функция характеризуется параметрами h, k, μ=int h/r, S, где h – разрядность вектора , k – количество многоразрядных конъюнкций (для простоты будем считать, что все конъюнкции – многоразрядные, остальные можно вычислить отдельно и тривиально), μ=int h/r – количество подвекторов , S – количество подконъюнкций, которое может не совпадать с k* μ (S ≤ k* μ). Аналогично вычислению многоразрядной конъюнкции задаются вектора:

: { . . . }

: { . . . }

: { . . . }, j= ,

которые группируются в μ массивов с начальными адресами Ai (i=1, μ).

а) случай k ≤ r. Тогда вектора Vj содержат единицы в позициях, соответствующих номерам конъюнкций, в которые входит данная подконъюнкция.

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

 Таким образом:

PLA( , A₁)=V₁,

PLA( , A₂)=V₂, (2)

PLA( , A_μ)=V_μ,

[ (M/M₁) ] [ (M/M₂) ] …. [ (M/M_μ)]=

Здесь М - полное множество конъюнкций, где каждой соответствует разряд , Mi (i= ) – множество индексов вхождений подконъюнкции для i-го входного подвектора . Причем в массивы Аj в отличии от вычисления одной конъюнкции могут входить более одного вектора Q, D, V.

Операции маскирования можно реализовать в самой процедуре PLA за счет включения в массивы Aj векторов Q,D,V, имитирующих включение фиктивной подфункции

. Вектора, например, имеют вид

: {0, 0, … 1, 0, … 0}

: {0, 0, … 1, 0, … 0}

: {0, 0, … 1, 0, … 0}

: {0, 0, … 0, 0, … 1}

: {1, 0, … 0, 0, … 1}

: {1, 0, … 0, 0, … 1}

Здесь независимо от значения переменной x_i к результатам PLA добавляются маски, содержащие в первом и последнем битах единицы. Таким образом, организуется своего рода "смещение" результатов PLA.

Тогда выражение (2) можно записать так:

(3)

Функция равна единице, если Z≠0. Вектор Z несет информацию о единичных конъюнкциях исходной функции.

б) случай k>r , т.е. количество конъюнкций больше оставшейся разрядности. Тогда возможен случай, когда для определения значения некоторых конъюнкций недостаточно поразрядной конъюнкции (2), (3). Поэтому для идентификации значения конъюнкций необходимо int k/r векторов разрядностью r и, если некоторая подконъюнкция входит в конъюнкции, номера которых принадлежат различным векторам идентификации, количество которых γ, то необходимо γ раз вычислять подконъюнкции с различными векторами V. Для вычисления многоразрядных конъюнкций в общем случае необходимо int k/r подмассивов, в каждом из которых необходимы, в свою очередь, подмассивы по различным входным векторам (i= ). Пусть Мк – множество номеров многоразрядных конъюнкций, j=1, int k/r, Aji – начальный адрес подмассива M_Aji – множество номеров многоразрядных конъюнкций соответствующего подмассива. Для вычисления значений конъюнкции необходима операция пересечения множеств. Ее можно организовать поразрядной конъюнкцией Vji (результатов) с учетом маскирования битов, соответствующих номерам дополнений Mk/ M_Aji (в принципе, Mk- вектор с r единицами).

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

Процесс вычислений выглядит следующим образом:

PLA( , A_1i)= ,

.

. 

.

PLA( int k/r i, Aint k/r i)= int K/r i , (4)

Zj = Z, где (4) учитывает маскирование для псевдопересечения в массивах Аi.

В том случае, если используется отдельная команда, то вычисления имеют вид:

PLA( , A₁₁) (M₁/M₁₁) =

.

.

.

PLA( , A_1µ) (M₁/M_1µ) =

.

.

.

PLA( int k/r 1, Aint k/r 1) (Mint k/r / Mint k/r 1) = int k/r 1

PLA( int k/r µ, Aint k/r µ) (Mint k/r / Mint k/r µ) = int k/r µ

Zj = Z.

Вычисления могут заканчиваться при обнаружении нулевого вектора

3. Вычисление систем многоразрядных булевых функций (СМБФ)

СМБФ характеризуется параметрами n, k,µ=int n/r, S, m, где m – количество выходных
функций.

Вычисление системы функций производится с использованием вариантов 2а, 2б:

а) количество подконъюнкций в СМБФ k ≤ r, n>r, m ≤ r. Используются выражения (2) или (3)

	PLA( , Ai)= ,
	(6)

PLA( , Az)=

(здесь использовано выражение (3)).

Аналогично можно использовать выражение (2)

PLA( , Ai)= ,

(7)

PLA( , Az)= ,

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

Следует отметить, что при задании СМБФ в СНДФ индексы вхождения подконъюнкций в конъюнкции на различных подвекторах содержат полное множество многоразрядных конъюнкций, поэтому необходимость в маскировании дополнения до этого множества отпадает.

Поэтому процесс вычисления по выражениям (6), (7) упрощается, что является справедливым и для вычисления одной функции.

б) Количество подконъюнкций k>r, n>r,m ≤ r.

В этом случае используются выражения (4) и (5).

Псевдовыходной вектор будет иметь разрядность r*int k/r, тогда для получения Z необходимо int k/r краткое вычисление с последующей дизъюнкцией.

Процесс вычисления имеет вид:

	PLA( , Aji)= ,
	PLA( , Azj)= , (8)

 _{int k/r}

  =

 ^j=1 

или

 PLA( , Aji) (Mj/Mij)=

 PLA( , Az_j)=   (9)

 _{int k/r}

  = , i= ,

 ^j=1 

в) n<=r, m>r, k –любое, т.е. многоразрядным является только выходной сигнал. В этом случае необходимо int m/r подмассивов для определения r*int m/r разрядов выходного вектора, причем входной вектор единственный.

Вычисления имеют вид:

 PLA( , A_i)= , (10)

Для подготовки исходных данных необходимо провести декомпозицию СМБФ на int m/r подсистем.

г) n>r, k<=r, m>r

В таком случае определяются значения конъюнкций, количество которых меньше или равно разрядности r , т.е. вектор по выражениям (6) или (7). Для получения собственно выходных векторов, количество которых равно int m/r, необходимы вычисления вида (10). Таким образом, вычисляем по формулам:

PLA( , Ai)=

 _μ

  = (11)

 ⁱ⁼¹

 PLA( , Az_j)= , i= ,

PLA( , Ai)=

 _μ

 [ (M/Mi)]=   (12)

 ⁱ⁼¹

 PLA( , Az_j)=   , i= ,

д) n>r, k>r, m>r

В этом случае после получения псевдовыходных векторов по выражениям (8) или (9) получают Ε=int m/r собственно выходных векторов

 PLA( , Aji) =

 PLA( , Az_jE)=   (13)

 _{int k/r}

  = , i= , ,

 ^j=1

 PLA( , Aji) (Mj/Mij) =

 PLA( , Az_jE)=   (14)

 _{int k/r}

  = , i= , ,

 ^j=1

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

Литература

1.       Тюрин С.Ф. Синтез адаптируемой к отказам цифровой аппаратуры с резервированием базисных функций //Приборостроение. – 1999. – № 1. – С.36-39.

2.       Тюрин С.Ф. Адаптация к отказам одновыходных схем на генераторах функций с функционально-полными толерантными элементами //Приборостроение. – 1999. – № 7. – С.32 – 34.

3.       Тюрин С.Ф. Проблема сохранения функциональной полноты булевых функций при «отказах» аргументов //Автоматика и телемеханика. – 1999. – № 9. – С.176 –186.

4.       Тюрин С.Ф., Несмелов В.А., Харитонов В.А. и другие. Программируемое логическое устройство. Патент РФ № 2146840. Опубл. БИ № 8, 2000 г.

5.       Тюрин С.Ф. и другие. Система для программирования технологическим оборудованием. Патент РФ №2189623. Опубл. БИ №26, 2002 г.