О Н Дяченко - Компактный анализ над полем gf - страница 1

Страницы:
1  2 

компактный анализ над полем gf(3)

Дяченко О.Н.

Кафедра ЭВМ ДонНТУ don@cs.dgtu.donetsk.ua

Abstract

Dyachenko O.N. Compact analysis over field GF(3). The features signature analysis is discussed for the case of using characteristic polynomials over GF(3) for linear feedback shift registers. One of the approaches of the compact analysis - signature-syndromic testing grounded on operations of division by polynomials over a field GF(2) - is spread in area ofpolynomials over afield GF(3).

Введение

Методам компактного тестирования принадлежит значительная роль при решении задач снижения трудоёмкости контроля и диагностики сложных цифровых устройств. Среди широкого спектра различных способов компактного тестирования сигнатурный анализ обладает рядом преимуществ: простая аппаратная реализация, высокое быстродействие сигнатурных анализаторов, простая аппаратная реализация многоканальных анализаторов тестовых реакций, высокие обнаруживающие способности. Традиционный сигнатурный анализ основан на операции деления полиномов над полем GF(2), причём в качестве делимого выступает анализируемая последовательность, представленная в виде полинома над полем GF(2), в качестве делителя - порождающий полином над полем GF(2), в соответствии с ненулевыми коэффициентами которого выбираются обратные связи регистра сдвига с линейными обратными связями. Таким образом, анализируемая тестовая реакция представляется последовательностью логических нулей и единиц. Вместе с тем логические анализаторы, как правило, позволяют определять в контрольных точках не только уровни логического нуля или логической единицы, но также неопределённое состояние, которому может соответствовать либо уровень напряжения, меньший уровня логической единицы и больший уровня логического нуля, либо высокоимпедансное состояние логического элемента с тристабильными выходами, либо отсутствие контакта щупа с контрольной точкой. В этом случае анализируемую тестовую реакцию можно представить в виде последовательности трёхзначных символов, например, 0 - логический ноль, 1 - логическая единица, 2 - неопределённое состояние.

В [1] рассмотрены вопросы аппаратной реализации РСЛОС с порождающими полиномами над полем GF(3) на элементах двоичной логики. В данной работе предлагается один из подходов компактного анализа - сигнатурно-синдромное тестирование, основанное на операции деления полиномов над полем GF(3).

1. Особенности сигнатурного анализа над полем GF(3)

РСЛОС с порождающим полиномом над полем GF(3) (РСЛОС GF(3)) имеет более сложную аппаратную реализацию по сравнению с РСЛОС GF(2). Однако сигнатурный анализ на основе РСЛОС GF(3) обладает повышенными контролирующими способностями, поскольку наряду с возможными логическими нулями и единицами учитывает возможные ситуации неопределённого состояния.

Как и в случае GF(2), для РСЛОС GF(3) обратные связи целесообразно выбирать в соответствии с ненулевыми коэффициентами неприводимого примитивного порождающего полинома над полем GF(3). Полином выбирается примитивным, поскольку в этом случае можно получить максимальное количество всевозможных остатков от деления на такой полином, равное 3n, а следовательно, максимально возможное количество различных сигнатур.

Рассмотрим особенности сигнатурного анализа над полем GF(3).Аналогично полю GF(2) анализируемую тестовую реакцию троичных символов можно представить в виде полинома над полем GF(3):

f(X) = fnXn+fn-1Xn-1+ . . . + fX + fo,

где X - неопределённая (фиктивная) переменная, коэффициенты f принадлежат полю GF(3) (т.е. могут принимать значения 0, 1, 2), знак "+" обозначает операцию по модулю 3. Например, троичную последовательность 12020102 можно представить в виде полинома X7 + 2X6 + 2X4 + X2 + 2.

Как и в случае GF(2), в поле GF(3) выполняется принцип суперпозиции:

S[A(X) + B(X)] = S[A(X)] + S[B(X)], т.е. сигнатура суммы по модулю 3 двух полиномов над полем GF(3) (X) и B(X) равна посимвольной сумме по модулю три сигнатур A(X) и B(X). Сигнатуры представляют собой остаток от деления   соответствующего полинома на порождающий полином РСЛОС сигнатурного анализатора.

Обозначим: A(X) - эталонная тестовая реакция, B(X) - реальная тестовая реакция, т.е. тестовая реакция с ошибками, E(X) - полином ошибки. Тогда

A(X) - B(X) = E(X).

Следует отметить, что в отличие GF(2), в поле GF(3) операция вычитания не эквивалентна операции сложения.

Например, предположим, что эталонная тестовая реакция имеет вид 120120120, а реальная - 201012120, тогда вектор ошибки будет иметь вид 222111000, при этом символы 2 и 1 означают отличие, символ 0 - совпадение эталонной и реальной тестовых реакций. Посимвольная сумма по модулю три вектора ошибки и реальной тестовой реакции равна эталонной тестовой реакции:

201012120 + 222111000 = 120120120, или в полиномиальной форме представления:

A(X) = B(X) + E(X).

Согласно принципу суперпозиции

S[A(X) - B(X)] = S[E(X)] = S[A(X)] - S[B(X)],

S[A(X)] = S[B(X)] + S[E(X)].

Итак, для сигнатурного анализа над полем GF(3) в отличие от поля GF(2) существует два типа ошибок: 1 - появление вместо 1 - 0, вместо 2 - 1, вместо 0 - 2; 2 -появление вместо 1 - 2, вместо 2 - 0, вместо 0 - 1.

Рассмотрим структуру поля GF(3n) на примере расширения поля GF(3) по примитивному полиному над полем GF(3) X2+X+2 (см.табл.1). Следует отметить, что все ненулевые элементы можно разделить на два подмножества: a0, a1, a2, a3 и a4, a5, a6, a , где a -примитивный элемент поля. Элементы этих подмножеств являются линейно зависимыми. Во-первых, второе подмножество можно получить из первого заменой символов 1(2) на 2(1); во-вторых, посимвольная сумма по модулю три i-х элементов подмножеств равна 0. Аналогичную структуру имеет любое поле GF(3n), полученное как расширение GF(3) по примитивному полиному над полем GF(3).

Таблица 1 - Поле GF(32).

Элементы поля GF(9)

в виде степени

в виде троичных

 

символов

0

00

a0

a1 a2

a3

01 10 21 22

a4

a5 a6 a7

02 20 12 11

2. Компактный анализ над полем GF(3) в виде сигнатурно-синдромного тестирования

Рассмотрим особенности сигнатурно-синдромного тестирования над полем GF(3)- частного случая сигнатурного анализа комбинационных схем (КС). Сигнатурно-синдромного тестирование над полем GF(2) [2,3] предполагает исчерпывающее тестирование КС, применение в качестве генератора тестовых воздействий - двоичного счётчика и сигнатурно-синдромного анализатора тестовых реакций.

Достоинства сигнатурно-синдромного тестирования (ССТ) КС следующие. Во-первых, ССТ позволяет выполнять аналитический расчёт значений сигнатурных синдромов и, в частности, по известным значениям сигнатурных синдромов на независимых входах логического элемента определять значение сигнатурного синдрома на его выходе. На основе аналитического расчёта значений сигнатурных синдромов возможна комплексная оценка достоверности результатов тестового эксперимента, которая учитывает не только обнаруживающие способности анализатора тестовых реакций, но также характер тестовых воздействий и тестовых реакций в зависимости от конкретных неисправностей объекта диагностики. Например, в [4] на основе свойств сигнатурного синдрома доказано обнаружение всех неисправностей определённого класса неисправностей [4] в программируемых логических матрицах при применении анализатора в виде РСЛОС с примитивным порождающим полиномом минимальной степени

Во-вторых, при задании начального состояния РСЛОС сигнатурно-синдромного анализатора, равного эталонной сигнатуре, появляется возможность локализовать одиночную ошибку в анализируемой тестовой последовательности, т. е. указать порядковый номер искажённого символа.

Основой сигнатурно-синдромного анализатора [3,5] над полем GF(2) (ССА GF(2)) является РСЛОС с порождающим примитивным полиномом над полем GF(2) и двоичный счётчик. Принцип работы ССА GF(2) заключается в следующем. В РСЛОС производится сжатие тестовой реакции, по окончании которого РСЛОС продолжает свою работу до появления во всех его разрядах, кроме первого, нулей, т. е. до состояния РСЛОС, равного "100...0". Двоичный счётчик подсчитывает количество тактов с момента окончания сжатия тестовой реакции, и его показания определяют значение сигнатурного синдрома, если начальное состояние РСЛОС равно нулю, или номер одиночного искажённого символа, если начальное состояние РСЛОС равно эталонной сигнатуре.

2.1 Локализация одиночного ошибочного троичного символа

Вначале рассмотрим сигнатурно-синдромный анализатор над полем GF(3) (ССА GF(3)) с возможностью локализации одиночного ошибочного троичного символа при ССТ над полем GF(3) КС двоичной логики. Отличительная особенность ССА GF(3) -применение РСЛОС GF(3) вместо РСЛОС GF(2). Кроме того, учитывая, что возможны два состояния РСЛОС GF(3), при которых все его разряды, кроме первого, равны нулю: "100...0" и "200...0" (см. табл. 1), если длина анализируемой последовательности равна 3n-1, следует её ограничить до значения (3n-1)/2. И, наконец, последняя отличительная особенность - начальное состояние РСЛОС GF(3). Оно должно быть таким, чтобы по окончании сжатия тестовой реакции без ошибок состояние РСЛОС приняло нулевое значение. Тогда при сжатии тестовой реакции с ошибкой, согласно принципу суперпозиции, РСЛОС примет состояние, равное сигнатуре вектора ошибки.

В РСЛОС GF(2) с начальным состоянием, равным эталонной сигнатуре S[A(X)], определённой для длины тестовой реакции 2n-1, через 2n-1 тактов его состояние вновь станет равным S[A(X)], если на информационном входе РСЛОС GF(2) - константа ноль. Тогда при сжатии тестовой реакции без ошибок согласно принципу суперпозиции состояние РСЛОС GF(2) станет равным нулю: S[A(X)]+S[A(X)]=0, где знак означает посимвольную сумму по модулю 2.

В РСЛОС GF(3) с начальным состоянием, равным эталонной сигнатуре S[A(X)], определённой для длины тестовой реакции (3n-1)/2, через (3n-1)/2 тактов для константы ноль на информационном входе РСЛОС GF(3) станет равным S'[A(X)], где знак ' (штрих) означает замену в S[A(X)] символов 1(2) на 2(1) (см. табл. 1). Например, если эталонная сигнатура S[A(X)] равна 120, то S'[A(X)]=210. Тогда при сжатии тестовой реакции без ошибок, длина которой равна (3n-1)/2, состояние РСЛОС GF(3) также станет равным нулю: S[A(X)]+S'[A(X)]=0, где знак означает посимвольную сумму по модулю три.

Таким образом, независимо от различия операций в РСЛОС GF(2) и РСЛОС GF(3), в обоих случаях их начальное состояние следует задавать равным эталонной сигнатуре. Тогда после окончания сжатия тестовой реакции с ошибкой содержимым РСЛОС будет S[E(X)]. ССА GF(3) продолжает свою работу до тех пор, пока в РСЛОС появится комбинация "100...0" или "200...0". Если ошибка одиночная, тогда показания счётчика - её порядковый номер.

Необходимо отметить, что ССА GF(3) можно применять для локализации одиночных ошибок в тестовой реакции для любого цифрового объекта диагностики и любого генератора тестовых воздействий.

2.2 Сигнатурно-синдромный анализатор над полем GF(3) с начальным нулевым состоянием

Рассмотрим ССА GF(3) с начальным нулевым состоянием РСЛОС. При тестировании КС двоичной логики и генераторе тестовых воздействий в виде двоичного счётчика ССА GF(3) не сохраняет свойства сигнатурного синдрома над полем GF(2). Эти свойства основаны на следующем равенстве в поле GF(2): (Xi+1)2=X2i+1, где знак "+" означает сложение по модулю два. В поле GF(3) это равенство не выполняется, однако справедливо следующее равенство (Xi+1)3=X3i+1, где знак "+" означает сложение по модулю три. Действительно, (Xi+1)3 = (Xi+1)(Xi+1)(Xi+1) = (X2i+2Xi+1)(Xi+1) = X3i+2X2i+Xi+X2i+2Xi+1 = X3i+1. Поэтому свойства сигнатурного синдрома будут выполняться для генератора тестовых воздействий в виде троичного счётчика, КС трёхзначной логики и ССА GF(3).

Аналитический расчёт значений сигнатурного синдрома над полем GF(3) (SS3) рассмотрим на примере. Предположим, что функция трёхзначной логики задана таблицей 2.

Запишем функцию в сигма-пи нормальной форме и минимизируем её (знак "*" означает умножение по модулю три, знак "+" означает сложение по модулю три) [6]:

f(Vl,V2)= Ф0(У1)*Ф0(У2)+Ф1(У1)*Ф0(У2)*2+Ф1(У1)*Ф1(У2)+Ф2(У1)*Ф0(У2)*2+

+ Ф2(У1) *Ф1<У2) *2+Ф2<У1) *Ф2<У2)*2=Ф0<У1)*Ф0<У2)+Ф1<У1) *Ф0(У2) *2+ + Ф1(У1)*Ф1(У2) + Ф2(У2) *2.

Предположим, что ГТП реализуется на основе n-разрядного вычитающего троичного счётчика с начальным состоянием "22...2", длина тестовых воздействий равна 3n, АТР - в виде ССА GF(3), РСЛОС которого прекращает работу при появлении состояния "100...0" или "000...0". Показания счётчика определяют значение сигнатурного синдрома над полем GF(3).

Таблица 2 - Функция трёхзначной логики.

V1 V2

f(V1,V2)

V1 V2

f(V1,V2)

0 0

1

1 2

0

0 1

0

2 0

2

0 2

0

2 1

2

1 0

2

2 2

2

1 1

1

 

 

Приведём без доказательства некоторые свойства SS3.

1. Сигнатурный синдром конъюнкции Фі(Уі) равен XY, где Y=i*3(n-j)+a(3k1-1 + 3k2-1 + 3k3-1 + . . . + 3ki-1), причём k1, k2,...ki,- индексы отсутствующих аргументов Vi; a - характеристическое число порождающего полинома РСЛОС:

SS3(X2+X+1)=Xa ; знак "*" и "+" в выражении для Y означает арифметическое умножение и сложение.

2. Сигнатурный синдром конъюнкции Фі1(У1)*Фі2(У2)*...Фіп(Уп) равен XY, где Y=i1*3(n-1)+i2*3(n-2)+ . . .+in.

3. Умножение на константу 2 соответствует умножению на X-Y, где Y=(3n-1)/2.

4. SS3(XY+1)=0, где Y=(3n-1)/2.

5. Если SS3(XZ+1)=Xl, то SS3(X3Z+1)=X3t.

Для рассматриваемого примера предположим, что порождающий полином РСЛОС GF(3) равен X2+X+2. Определим соответствующие ему табличные значения логарифмов, аналогичные логарифмам Зеча в поле GF(2) (SS3(XZ+1)=Xt):

Z=1, t=7; Z=2, t=3; Z=3, t=1*3=3; Z=5, t=2; Z=6, t=3*3mod8=1; Z=7, t=6.

2

Характеристическое число a полинома X+X+2 равно 4, поскольку SS3(X2+X+1)=X4.

Первый вариант аналитического расчёта SS3[f(V1,V2)]. Определим значения Фі(Уі) согласно первому свойству SS3:

Ф0(У2) = X4: y = (00)3 + 4*(10)3 = 4*3 = 12-8 = 4; Ф1(У2) =     y = (01)3 + 4*(ю)3 = 1+12 = 13-8 = 5; Ф2(У2) = X6: y = (02)3 + 4*(ю)3 = 2+12 = 14-8 = 6; Ф0(У1) = Xі*: y = (00)3 + 4*(01)3 = 4; Ф1(У2) = X7: y = (10)3 + 4*(01)3 = 3+4=7; Ф2(У2) = X2: y = (20)3 + 4*(01)3 = 6+4 = 10-8 = 2; SS3[f(V1,V2)] = X4X4+X7X4X-4+X5X7+X2X-4 = X0+X7+X12+X-2 = = X7+X6+X4+1 = X7+X6 = X6(X+1) = X7X6 = X13-8 = X5.

Второй вариант аналитического расчёта SS3[f(V1,V2)] основан на применении второго свойства SS3:

SS3[f(V1,V2)] = X(00) +X(10)*X-4+X(11)+X2X-4 = X0+X3-4+X4+X-2 =

= 1+X-1+8+X4+X6 = X7+X6+X4+1 = X7+X6 = X7X6 = X13-8 = X5, (в данном случае скобки в степени означают троичную систему счисления).

В таблице 3 представлена проверка полученного результата: рассчитанный аналитически и табличный сигнатурные синдромы равны SS3[f(V1,V2)] = X5.

Таблица 3 - Определение сигнатурного синдрома SS3[f(V1,V2)]

ГТП V1 V2

f(V1,V2)

РСЛОС ССА GF(3)

СТ

ССА GF(3)

2 2

2

2 0

 

2 1

Страницы:
1  2 


Похожие статьи

О Н Дяченко - Компактный анализ над полем gf

О Н Дяченко - Сигнатурно-синдромный анализатор

О Н Дяченко - Эффективность псевдоисчерпывающего тестирования комбинационных схем

О Н Дяченко - Устройство для сопряжения абонента с общей магистралью