О длинах путей самотестируемых детекторов, построенных в базе ПЛБ | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/11

О длинах путей самотестируемых детекторов, построенных в базе ПЛБ

При проектировании самопроверяемых схем используются самотестируемые детекторы кодов, в частности детекторы равновесных кодов ((m, п)-кодов). Для представления всевозможных кодовых слов (m, п)-кодов используется специальная формула разложения. В работе сравниваются два самотестируемых детектора (m, п)-кодов, построенные на многократном использовании этой формулы разложения и реализации полученной в результате формулы программируемыми логическими блоками (ПЛБ). Конкретный вид формулы определяется множеством представляемых ею кодовых слов (параметрами m, n), числом k входов в ПЛБ и способом разбиения переменных на подмножества. В работе анализируется влияние способа разбиения переменных на подмножества на максимальную длину пути в схеме детектора и на количество ПЛБ в детекторе.

On the lengths of the paths in self-testing checkers based on CLB.pdf В самопроверяемых схемах используются детекторы кодов. Как правило, детектор строится на той же элементной базе, что и схема. Метод построения детектора обычно состоит в подсчете веса входного кодового слова. Для этой цели используются схемы, основанные либо на пороговых элементах, либо на параллельных счетчиках [1-7]. В данной работе предлагается синтез детектора на ПЛБ. В [8] был предложен метод проектирования самопроверяемого конечного автомата. В случае исправного функционирования схемы на выходе комбинационной составляющей реализуются кодовые слова некоторого неупорядоченного кода, например равновесного. Там же предлагается метод синтеза самотестируемого детектора равновесного кода (детектора (m, п)-кодов), основанный на многократном использовании специальной формулы разложения множества кодовых слов равновесного кода и реализации полученной в результате формулы программируемыми логическими блоками в предположении, что среди программируемых блоков обязательно присутствуют блоки с двумя выходами. К реализации формулы предъявляется специальное требование: соответствующая реализации схема детектора (m, п)-кодов должна быть самотестируемой для заданного множества V неисправностей. Предлагаемый для сравнения подход [9] основан на многократном использовании той же формулы разложения, применяемой к иному, по сравнению с работой [8], разбиению подмножества переменных кодовых слов. Это разбиение ориентировано на сокращение максимальной длины путей в схеме, являющейся реализацией полученной в результате формулы, и минимизацию разброса длин путей. В предложенном в работе [9] методе синтеза самотестируемых детекторов наличие двух выходных ПЛБ не обязательно. Это значит, что данный метод позволяет строить самотестируемые детекторы, используя любые существующие на текущий момент программируемые логические матрицы (Field Programmable Gate Arrays (FPGA), производители Xilinx, Altera, Achronix, Actel, Atmel, Lattice semiconductor и др.), в то время как метод, предложенный в [8], ориентирован только на FPGA фирмы Xilinx. 92 О длинах путей самотестируемых детекторов, построенных в базе ПЛБ Рассматривается множество V неисправностей детектора, которое включает в себя все кратные константные неисправности на входах и выходах ПЛБ. При этом в схеме детектора неисправным может быть только один ПЛБ. Предполагается, что в системе, состоящей из самопроверяемой схемы и детектора (m, п)-кодов, неисправными могут быть либо схема, либо детектор, но не оба вместе. К самотестируемому детектору предъявляются следующие требования: 1) при появлении на выходе схемы (или на входе детектора) в некоторый момент времени t некодового слова детектор должен выдать соответствующий сигнал; 2) в самом детекторе может произойти неисправность из рассматриваемого множества неисправностей V, которая должна быть обнаружима в рабочей области функционирования детектора, т.е. на множестве всех его кодовых слов. Это означает, что должен существовать кодовый набор (кодовое слово (m, n)-кода), на котором эта неисправность проявляется на выходах детектора. Самотестируемый детектор имеет два выхода, причем комбинации значений сигналов имеют следующие интерпретации: а) (01) или (10) означает, что входной набор является кодовым словом ((m, n)-кода) и детектор исправен; б) (00) или (11) означает, что либо входной набор не является кодовым словом, либо детектор неисправен. Детектор строится по формуле, представляющей множество всех кодовых слов (m, n)-кода, являясь реализацией этой формулы. 1. Метод разложения множества кодовых слов (m, n)-κoga Заметим, что число всевозможных кодовых слов (m, n)-кода равно Cm , т.е. числу сочетаний из n по m. Кодовые слова могут быть представлены дизъюнкцией элементарных конъюнкций (ДНФ) ранга n. Обозначим эту дизъюнкцию Dm(X), где X = {xι, .^, Xn} - множество переменных. Уже при n = 10, m = 5 ДНФ D5(X) состоит из C'∣5∣ = 252 конъюнкций ранга 10 и содержит 2 520 букв. Поскольку любые две конъюнкции из Dm(X) ортогональны по крайней мере по двум переменным, то ДНФ Dm(X) является совершенной и сокращенной одновременно и, следовательно, не может быть сокращена в результате минимизации ДНФ. Для представления всевозможных (m, п)-кодов в [8] предложена специальная формула, включающая скобки, символы л, V и ДНФ Dp (X'') . Выражение Dp (X'') - это дизъюнкция конъюнкций, соответствующих всем (q, p)-кодовым словам, p ≤ n, q ≤p, X' ⊂X, X = {xι, .^, Xn}. Построим формулу следующим образом. Разделим множествоXна два подмножестваX1,X2, гдеX1 = {xι, x⅛},X2= {xk+ι, Xn}. Все множество кодовых слов равновесного кода может быть представлено формулой (1) Dm (X)=∑ "0 D', (X")Dm--i (X ^), где символ л между Di(X∣) и Dm-i(X2) опущен. Назовем k основой разложения (k - число входов в ПЛБ), Dki , Dm-i - функциями разложения. Если n - k > к, то формула (1) снова используется для соответствующей функции разложения Dm-i, i = 0, m , и т.д. В результате многократного применения формулы (1) получаем представление для всех кодовых слов (m, n)-кода в виде формулы, содержащей скобки, операции V и л и Dq (X') . В этой формуле для любой ДНФ Dq(X') выполняется условие p ≤ k. Представления такого вида в дальнейшем будем называть формулами А. 93 Н.Б. Буторина, Е.Г. Пахомова Например, получим формулу A для D84 , k = 2 при помощи формулы (1). В соответствии с приведенным алгоритмом на первом шаге: X1 ={x1, x2}, X2 ={x3, x4, x5, x6, x7, x8}. D84(X)=D20(X1)D64(X2)VD21(X1)D63(X2)VD22(X1)D62(X2). Далее, X21 = {x3, x4}, X22 = {x5, x6, x7, x8}. Выполнив следующий шаг разложения по формуле (1) для D62(X2) , D63(X 2), D64(X2) получим D62(X2) = D20(X21)D42(X22)V D12(X21)D41(X22)V D22(X21)D40(X22), D63(X2) = D20(X21)D43(X22)V D12(X21)D42(X22)V D22(X21)D41(X22), D64(X2) = D20(X21)D44(X22)V D21(X21)D43(X22)V D22(X21)D42(X22) . Далее, X221 = {x5, x6}, X222 = {x7, x8}. Выполнив следующий шаг разложения по формуле (1) для D40(X22) , D41(X 22) , D42(X22) , D43(X 22) , D44(X22) получим D40(X22) = D20(X221)D20(X222), D41(X22) = D20(X221)D21(X222)V D21(X221)D20(X222), D42(X22) = D20(X221)D22(X222)V D21(X221)D21(X222)V D22(X221)D20(X222), D43(X22) = D21(X221)D22(X222) V D22(X221)D21(X222) , D44(X22) = D22(X221)D22(X222). Подставляя полученные выражения в формулу (1) получаем формулу А. Структура этой формулы может быть представлена деревом (рис. 1). л л d4( X ) V D1(X1) d0(.X 1) ^'^d6(X 2) л χf∖ D22 D21(X 21) D2(X 21) Х®4(х22) v H'. (.V-I yD4(x^2ι V d∖(^x^'2) л d'0(x22) ^^ДD4( X '2) ЛЛ Л Л Л Л Л ЛЛ'лЛл D∖X^22^ D0X^") ∣d!(x-22)∣D4(x^^^) ^ к ∣∖ ∣d2(x2^∣d4(x^22)\\ 1\\ ∣Dx2^2)I'D0(x222) D12(X221) D22(X221) D20(X221) D21(X221) D22(X221) D21(X221) D22(X221) D20(X221) D21(X221) D22(X221) D20(X221) D21(X221) D0(X221) D1(X221) D2(X221)D0(X221) D1(X221) D22(X222) D21(X222) D20(X222) D22(X222) D21(X222) D20(X222) D2(X222) D1(X222)D0(X222) Рис. 1. Дерево разложения для D 4 , k = 2 (способ 1) Fig. 1. Tree decomposition for D 4 , k = 2 (technique 1) В [9] был предложен другой способ разбиения множества переменных на подмножества. Разделим множество X на два подмножества X1, X^, где X1 = {Х1, .^, Xg}, X^= {xg+1, .^, Xn}. Все множество кодовых слов равновесного кода может быть представлено формулой (2) Dnm(X) = ∑im=0Dgi (X1)Dnm--gi(X2) , где символ л между Di (X1) и Dm-i(X2) опущен. Здесь Dgi (X1), Dnm--gi(X 2) - функции разложения, основа разложения k - максимальная мощность подмножества переменных при последнем применении формулы (2). 94 О длинах путей самотестируемых детекторов, построенных в базе ПЛБ В статье [9] предлагается следующий способ выбора g: g - наименьшее целое, большее или равное числа П2 или, в другой записи, g = ∖n∣2^. Если g > k и / или n - g > k, то формула (2) снова используется для каждой функции разложения Dg (1), Dm∑g (X2) , i = 0, m , и т.д. В результате мы имеем формулу для всех кодовых слов (m, n)-кода, в которой для любой Dq(Xr) выполняется условие p ≤ k. Это значит, что во втором способе многократное разложение применяется как к первому, так и ко второму множителю формулы (2). Например, получим формулу A для D84 , k = 2 вторым способом. На первом шаге X1 ={x1, x2, x3, x4}, X2 = {x5, x6, x7, x8}. Результат разложения представляется в виде: d4( X)=d0( X 1)d4( X2) V d4(X^)d3( X2) v d2( x ^)d2( x2) V d3( X1)d4( x2) v d4( x 1)d40( x2) . На втором шаге имеем подмножества X11 = {x1, x2}, X12 = {x3, x4}, X21 = {x5, x6 }, X22 = {x7, x8}. Применим формулу (2) еще раз ко всем функция разложения: D40(X1)=D20(X11)D20(X12), D41(X1)= D20(X11)D21(X12)VD21(X11)D20(X12), D42(X1)= D20(X11)D22(X12)VD12(X11)D21(X12)VD22(X11)D20(X12), D43(X1)= D12(X11)D22(X12)VD22(X11)D21(X12), D44(X1)= D22(X11)D22(X12), D40(X2)= D20(X21)D20(X22), D41(X2) = D20(X21)D21(X22)V D21(X21)D20(X22), D42(X2) = D20(X21)D22(X22) V D21 (X21)D21 (X22) V D22(X21)D20(X22) , D43(X2)= D12(X21)D22(X22)VD22(X21)D21(X22), D44(X2)= D22(X21)D22(X22). Подставляя полученные выражения в формулу (2) получаем формулу А. Можно сказать, что формула (1) есть частный случай формулы (2) при g = k. Структура формулы (2) может быть представлена деревом (рис. 2). Рис. 2. Дерево разложения для D 4 , k = 2 (способ 2) Fig. 2. Tree decomposition for D 4 , k = 2 (technique 2) Дадим определение шага разложения. 1. При первом применении формулы (2) множество переменных X разбивается на два подмножества: X1 и X2. При этом мощность одного из этих подмножеств или обоих подмножеств может оказаться больше k. Это первый шаг разложения. 95 Н.Б. Буторина, Е.Г. Пахомова 2. На втором шаге разложения формула (2) применяется ко всем функциям разложения предыдущего шага, определенным на подмножестве переменных, мощность которого больше k. В результате применения формулы (2) подмножество X1 и / или X2 разбивается на два подмножества, мощность каждого из которых меньше мощности X1 или X2 соответственно, но при этом снова может быть больше k. 3. Таким образом, і-й шаг разложения - это применение формулы (2) ко всем функциям разложения предыдущего (і - 1)-го шага, определенным на подмножестве переменных, мощность которого больше k. Итак, конкретный вид формулы определяется множеством представляемых ею кодовых слов (параметрами m, n), значением k и способом разбиения переменных на подмножества. В дальнейшем будем сравнивать рассмотренные выше способы разбиения множеств переменных на два подмножества. По сути, формула (1) есть частный случай формулы (2). Действительно, в первом способе разложения g = k на каждом шаге разложения, и формула (1) используется только для функции разложения Dnm--ki , i = O,m , и т.д. Во втором способе выбирается g, кратное k. При этом возможны следующие две ситуации. 1. Пусть n кратно k, т.е. n = kq = k(q^ + q2), где kq1 - ближайшее к ∖n∕2^ число, кратное k, q2 = q - q1. Итак, на первом шаге множество X, |X| = n, разбивается на два подмножества X1 и X2, где = kq^ = g, IJ2I = kq^ = n - g. Если |X1| > k и (или) |X2| > k, то применяем формулу (2) к соответствующему сомножителю Dgi (X1), Dnm--gi(X2) , выполняя разбиение множеств J1, J2 в соответствии с правилами пункта 1, и т.д. 2. Пусть n не кратно k. Тогда при использовании формулы (2) на первом шаге разложения предлагается выбирать g - ближайшее к ∖n∕2^ число, кратное k. В этом случае n - g не кратно k. Итак, на первом шаге множество J, |J| = n, разбивается на два подмножества J1 и J2, причем |J1| = kq1 = g, |J2| = kq2 +r = n - g, где r < k. Если |J1| > k и (или) |J2| > k, то применяем формулу (2) к соответствующему сомножителю Dgi (X1), Dnm--gi(X2) , выполняя разбиение множеств J1, J2 в соответствии с правилами пункта 2, и т.д. Приведем пример нахождения конкретных значений g и n - g при k = 6 для n = 18, 21, 30 двумя способами (рис. 3, 4). Рис.3. Деревья выбора при k = 6 для n = 18, 21, 30 (способ 1) Fig. 3. Trees of choice with k = 6 for n = 18, 21, 30 (technique 1) Рис.4. Деревья выбора при k = 6 для n = 18, 21, 30 (способ 2) Fig. 4. Trees of choice with k = 6 for n = 18, 21, 30 (technique 2) В обоих способах концевым вершинам дерева разложения сопоставляются ДНФ вида Dki , где 0 ≤ і ≤ k. Под синтезом детектора будем понимать реализацию формулы А композицией программируемых логических блоков, основанную на анализе дерева разложения формулы А. Подход к синтезу самотестируемого детектора для обоих способов остается одинаковым: вершины дерева разложения формулы А покрываются программируемыми логическими блоками снизу вверх [8]. Заметим, что кодовые слова, представляемые формулой А, при синтезе детектора необходимо разбивать на два подмножества: каждое из подмножеств сопоставляется одному из выходов детектора. 96 О длинах путей самотестируемых детекторов, построенных в базе ПЛБ 2. Сравнение двух детекторов Проведем оценку детекторов по двум параметрам: количеству ПЛБ и длине пути. Последовательность ПЛБ, такую что выход предыдущего блока является входом в последующий блок, назовем путем в детекторе. Входы первого блока являются входами детектора, а выход последнего блока - один из выходов детектора. Длиной пути назовем число ПЛБ, образующих путь. Нас будут интересовать пути максимальной длины, поскольку они влияют на быстродействие само-проверяемой системы, состоящей из самопроверяемой схемы и контролирующего ее самотестируе-мого детектора. Договоримся детектор, построенный по формуле (1) называть детектор 1, а детектор, построенный по формуле (2) - Детектор 2. При n ≤ 3k значения g и n - g для обоих способов разложения одинаковы, следовательно, одинаковы формулы А и представляющие их деревья разложения. Различия появляются при n > 3k. Проведем оценку детекторов по максимальной длине пути Lmax. Она зависит от числа μ шагов разложения и максимальной длины пути λ в подсхемах, реализующих формулу (1) или (2) на очередном шаге разложения. Число μ шагов разложения зависит от выбранного способа разбиения переменных на подмножества. Максимальная длина пути λ в подсхеме, реализующей формулу на очередном шаге разложения, зависит от количества слагаемых в этой формуле. Покажем это на примере. Применим формулу (2) к D7 при k = 7 с целью получения реализующей D7 подсхемы: D174 = D70(X1)D77(X2)v D71(X1)D76(X2)v D72(X1)D75(X2)v D73(X1)D74(X2)v (3) v D4(X1)D3(X2)v D5(X1)D2(X2)v D6(X1)D1(X2)v D7(X1)D0(X2). Обозначения выходов ПЛБ приведены в табл. 1. Таблица 1 Обозначения выходов ПЛБ, реализующих множители формулы (3) Реализуемая функция Обозначение выхода Реализуемая функция Обозначение выхода Dθ( X1) yi D0 {X2) yi6 d7( X 1) уз d7( X 2) yi4 D72( X1) y5 d7(x X 2) yi2 D3(. X1) У7 d7(.X 2) yιo D74( X1) У9 D74( X2) У8 d5(. X 1) yιι d7(. X 2) У6 d7(. X 1) yi3 D76( X2) У4 D7 (x X 1) yi5 d7(x X 2) У2 Имеем 8 слагаемых, состоящих из двух множителей. Каждый множитель сопоставляется входу ПЛБ, который реализует дизъюнкцию нескольких слагаемых. Так как в данном примере количество входов ПЛБ равно 7, то для реализации всех слагаемых потребуется ^2 • 8/7^ = 3 ПЛБ. Обозначим выходы этих ПЛБ через z1, z2, z3. Таким образом, ПЛБ1 реализует функцию jιj2 v узу4 v убу7, выход этого ПЛБ обозначен через zι, ПЛБ2 реализует функцию у7у8 v y9y10 v y11y12, выход этого ПЛБ обозначен через z2, ПЛБ3 реализует функцию у13у14 v у15у16, выход этого ПЛБ обозначен через z3. Пусть выходы подсхемы, реализующей формулу (3), являются выходами детектора (их два). Выходы z1 и z2 делаем входами ПЛБ, реализующий функцию D1 . Выход этого ПЛБ является одним из выходов детектора, второй выход - z3. Максимальная длина пути λmax в подсхеме, реализующей формулу (3), равна 2. Эта подсхема приведена на рис. 5. 97 Н.Б. Буторина, Е.Г. Пахомова y7 y8 y9y10y11y12 y13 y14y15y16 y1y2 y3 y4 y5 y6 Рис. 5. Подсхема, реализующая формулу (3) Fig. 5. A subcircuit realizing formula (3) В общем случае, если на реализацию формулы (1) или (2) требуется два и более ПЛБ и выходы этих ПЛБ не являются выходами детектора, то максимальная длина пути λmax в подсхеме, реализующей формулу, больше 1. Пусть Lmax - максимальная длина пути в схеме, реализующей детектор, λi - максимальная длина пути среди всех подсхем, реализующих i-й шаг разложения с использованием формулы (1) или (2). Тогда по построению λ+1, т.е. Lmax - сумма всех максимальных длин путей на каж дом шаге разложения + 1 (для реализации листьев дерева разложения). Чтобы найти длину пути λ в подсхеме, реализующей формулу (2) или (1) на очередном шаге разложения, необходимо знать количество слагаемых sum в этой формуле. Утверждение 1. Количество слагаемых sum в формуле (2) зависит от m, n - m, g и n - g, а именно sum = min{m + 1, g +1, n - g +1, n - m + 1}. Доказательство. Формула (2) имеет вид Dnm(X) = Yim=0 Dgi (X1)Dnm--gi(X2) . Разберем всевозможные случаи и приведем примеры. 1. Пусть m > g, m < n - g. Так как в разложении Di индекс i начинается с 0 и не может быть больше g, то получаем в формуле (2) (g + 1)-е слагаемое. Рассматривая связь чисел m, g и n - g, получаем, что в этом случае g +1 = min{g +1, m + 1, n - g +1, n - m + 1}. Действительно, условия m > g и m < n - g можно переписать в виде двойного неравенства g < m < n - g. Откуда находим g + 1 < m + 1 < n - g + 1. Иначе говоря, g +1 = min{g +1, m + 1, n - g +1}. Кроме того, из m < n - g следует, что n - m > g, следовательно, n - m + 1 > g +1. Таким образом, g +1 = min{g +1, m + 1, n - g +1, n - m + 1}. Например, пусть g = 4, m = 5 и n = 10. Тогда формула (2) имеет вид: D5o = D0( X 1)D∣( X ^) V D1( X 1)D4( X ^) v D^(^ X 1)d6( X 2) v D3(, X 1)DK, X 2) V D^(^ X 1)d6( X ^) То есть количество слагаемых sum = 5 = g + 1. 2. Пусть m < g, m > n - g. В этом случае слагаемых n - g +1. Поскольку из неравенств m < g, m > n - g следует, что n - g + 1< m + 1 < g + 1, то n - g + 1 = = min{ n - g + 1, m + 1, g+1}. Кроме того, из m < g находим: -m > -g, следовательно n - m + 1 > n - g + 1. Таким образом, n - g + 1= min{g +1, m + 1, n - g +1, n - m + 1}. Например, пусть g = 6, m = 4 и n = 9. Тогда формула (2) имеет вид: D94 = D61(X1)D33(X2)vD62(X1)D32(X2)vD63(X1)D31(X2)vD64(X1)D30(X2). То есть количество слагаемых sum = 4 = n - g + 1. 98 О длинах путей самотестируемых детекторов, построенных в базе ПЛБ 3. Пусть m < g, m < n - g. В этом случае слагаемых m + 1 = min{m + 1, g +1, n - g +1}. Кроме того, из m < g, m < n - g, получаем: m < g < n - m ⇒ m < n - m, а значит m + 1 < n - m + 1. Следовательно, m + 1 = min{m + 1, g +1, n - g +1, n - m + 1}. Например, пусть g = 4, m = 2 и n = 8. Тогда формула (2) имеет вид: D82 = dO(x1)d2(x2) V d4(x1)d4(x2) V d2 (X1)D4oJX2) . То есть количество слагаемых sum = 3 = m + 1. 4. Пусть m > g, m > n - g. В этом случае i в формуле (2) должно удовлетворять условиям i ≤ g и m - i ≤ n - g. Откуда находим, что m - n + g ≤ i ≤ g. Это неравенство имеет g - (m - n + g) + 1 = = n - m + 1 целых решений. При этом из m > g, m > n - g, получаем: n - m < g < m, из чего следует n - m +1 < g + 1 < m + 1. Иначе говоря, n - m +1 = min{m + 1, g + 1, n - m + 1}. Кроме того, из условия m > g получаем: -m < -g ⇒ n - m +1 < n - g + 1. Следовательно, n - m +1 = min{m + 1, g +1, n - g +1, n - m + 1}. Например, пусть g = 4, m = 6 и n = 8. Тогда формула (2) имеет вид d6 = d2(X^)D44(X^) V d3(X^)D3(X^) V D4(X^)D2(X^) . То есть количество слагаемых sum = 3 = n - m + 1. Итак, во всех случаях получаем, что sum = min{m + 1, g +1, n - g +1, n - m + 1}. Утверждение доказано. Следствие 1. Количество слагаемых sum в формуле (1) зависит от m, n - m, k и n - k, а именно sum = min{m + 1, k +1, n - k +1, n - m + 1}. Доказательство. Так как формула (1) является частным случаем формулы (2), а именно получается из формулы (2) при g = k, то с = min{m + 1, k +1, n - k +1, n - m + 1}. Следствие доказано. Каждое из слагаемых текущего шага разложения реализуется некоторой подсхемой. Выясним, какая их них даст наибольшую длину пути. В силу того, что Cm достигает максимума при m = J2, таким слагаемым будет слагаемое, у которого i наиболее близкое к g/2 или m - i, наиболее близкое к (n - g)/2. Приведем алгоритм нахождения максимальной длины пути L в детекторе 1 для D m , где 0° 1, то до тех пор, пока количество необходимых для реализации формулы ПЛБ CountCLB = PCountCLB / kP больше 1, увеличиваем λ. 100 О длинах путей самотестируемых детекторов, построенных в базе ПЛБ 6. Если первый шаг разложения и CountCLB > 2, то до тех пор, пока количество необходимых для реализации формулы ПЛБ CountCLB = ∖CountCLB / k больше 2, увеличиваем λ. 7. L = L + λ. 8. Если g ≤ k и p - g ≤ k, то нахождение L закончено. Иначе p = g, q - число, наиболее близкое к p/2 и идем на шаг 3. Сравним сложность детектора 1 и детектора 2. Будем считать, что при четных k используются двухвыходные ПЛБ (табл. 2). Таблица 2 Сравнение сложности детектора 1 и детектора 2 m n k Оценка максимальной длин^і пути Количество ПЛБ Детектор 1 Детектор 2 Детектор 1 Детектор 2 6 12 4 5 5 31 31 8 16 4 7 5 55 60 3 16 4 6 4 32 32 10 20 4 9 7 85 82 3 20 4 8 6 43 43 3 64 4 30 8 164 164 10 64 4 31 11 448 471 20 64 4 31 12 703 728 32 64 4 31 12 811 840 Количество ПЛБ, сопоставляемых листьям дерева разложения (все ПЛБ реализуют функции вида Dq , где 0 ≤ q ≤ k) одинаково при любом из рассматриваемых способах разбиения (так как в обоих случаях при разбиении идет ориентация на число k входов в ПЛБ). Разница в количестве ПЛБ начинается при многократном применении формул (1) и (2) при реализации Dp , где p > k. Заключение Таким образом, при n > 3k оценки максимальных длин путей детекторов, синтезированных методом, предлагаемым в [9], оказываются меньше, чем оценки длин путей детекторов, синтезированных методом, предлагаемым в [8]. Количество ПЛБ, используемых при синтезе детектора рассматриваемыми методами, существенно не отличается.

Ключевые слова

самотестируемость, детектор, программируемые логические блоки, равновесный код, selftesting, checker, configurable logical blocks (CLB), (m, n)-code

Авторы

ФИООрганизацияДополнительноE-mail
Буторина Наталья БорисовнаТомский государственный университетстарший преподаватель кафедры программирования Института прикладной математики и компьютерных наукnnattao7@mail.ru
Пахомова Елена ГригорьевнаТомский государственный университетдоцент, кандидат физико-математических наук, доцент кафедры программирования Института прикладной математики и компьютерных наукpeg@tpu.ru
Всего: 2

Ссылки

Parag K.L. Self-Checking and Fault-Tolerant Digital Design. Morgan Kaufmann Pub., 2000. 400 p.
Anderson D.A., Metze G. Design of totally self-checking check circuits for m-out-of-n codes // IEEE Trans. Computers C-22. 1973. P. 263-269.
Marouf M.A., Friedman A.D. Efficient design of sel-checking checker for any m-out-of-n code // IEEE Trans. Computers C-27. 1978. P. 482-90.
Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-on-Chip. New York : IGI Global, 2011. 578 p.
Blanke M., Kinnaert M., Lunze J., Staroswiecki M. Diagnosis and Fault-Tolerant Control. 2nd ed. Berlin : Springer-Verlag Berlin Heidelberg, 2006. 672 p.
Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John Wiley & Sons, Inc., 2006. 720 p.
Goessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking. Ed. 1. Dordrecht : Springer Science + Business Media B. V., 2008. 182 p.
Матросова А.Ю., Никитин К.В. Синтез самотестируемого детектора (m, п)-кодов на программируемых логических блоках // Вестник Томского государственного университета. Приложение. 2003. № 6. С. 124-136.
Буторина Н.Б., Цидендоржиева С.Р. Построение самотестируемого детектора равновесных кодовых слов // Новые ин формационные технологии в исследовании сложных структур : 7-я рос. конф. с междунар. участием. Томск : Том. гос. ун-т, 2008. С. 44.
 О длинах путей самотестируемых детекторов, построенных в базе ПЛБ | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/11

О длинах путей самотестируемых детекторов, построенных в базе ПЛБ | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/11