Автоматика и телемеханика, № 2, 2022

Оптимизация, системный анализ

и исследование операций

(Белорусский государственный университет

информатики и радиоэлектроники, Минск, Беларусь),

Н.А. ШЕВЧЕНКО, (nik.sh.de@gmail.com)

(Гимназия имени Лихтенберга, Дармштадт, Германия)

СИНТЕЗ ТЕСТОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ЗАДАННОЙ

ПЕРЕКЛЮЧАТЕЛЬНОЙ АКТИВНОСТЬЮ

Обсуждается актуальность применения тестовых последовательностей

с заданной переключательной активностью. В качестве математической

модели для генерирования тестов используется модификация метода Ан-

тонова и Салеева для формирования последовательностей Соболя, осно-

ванная на применении порождающих матриц максимального ранга, вид

которых определяет основные свойства последовательностей. Показыва-

ется, что построение порождающей матрицы сводится к задаче разбие-

ния целого числа на слагаемые, и предлагается алгоритм разбиения на

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

целого числа на слагаемые и коррекции значения переключательной ак-

тивности. Формулируются три задачи синтеза генераторов тестовых по-

следовательностей с заданной переключательной активностью. Рассмат-

риваются примеры использования предлагаемых методик и результаты

экспериментов.

Ключевые слова: тестовая последовательность, самотестирование вычис-

лительных систем, переключательная активность.

DOI: 10.31857/S00052310220200118

1. Введение

Эффективность тестовых последовательностей для современных вычисли-

тельных систем во многом определяется свойствами объектов тестирования

[1, 2]. Важным является компактное представление тестов в виде алгорит-

мов либо аппаратных структур для их генерирования при реализации само-

тестирования встроенных систем (Embedded Systems), систем на кристалле

(Systems-on-a-Chip), сетей на кристалле (Nets-on-a-Chip) [2, 3] и, в первую

очередь, для самотестирования их запоминающих устройств, удельный вес

которых достигает 90% занимаемой системой площади кристалла [3, 4]. Су-

щественную роль для тестовых последовательностей играет переключатель-

ная активность (Switching Activity), которая влияет на переключательную ак-

тивность тестируемых цифровых устройств. Набор тестовых последователь-

ностей в применяемых архитектурах самотестирования включает последова-

154

тельности с различной переключательной активностью [5, 6]. Множество та-

ких последовательностей включает: пересчетные (Linear Counting Sequences)

последовательности; последовательности Грея (Gray Code Sequences); по-

следовательности с максимальной переключательной активностью (Address

Complement Sequences); последовательности с расстоянием Хэмминга, рав-

ным единице для всех пар адресов (2ⁱ Counting Sequences); ряд других после-

довательностей [3, 5, 6].

Определяющее значение переключательная активность имеет в области

проектирования цифровых устройств с низким потреблением энергии [7], в

том числе при разработке и применении средств их тестирования и самотести-

рования [8, 9]. Большое количество исследований в данной области направ-

лено на получение оценок значений переключательной активности полюсов

проектируемых устройств, которые позволяют прогнозировать их энергопо-

требление [8, 10].

Средние значения переключательной активности можно интерпретиро-

вать как средние значения расстояния Хэмминга, которые широко приме-

няются для построения управляемых вероятностных тестовых последова-

тельностей [11-15]. Изменения величин указанных характеристик позволяют

строить управляемые вероятностные тесты с заданными значениями расстоя-

ния Хэмминга.

Следует отметить, что исследование вопросов синтеза различного рода

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

стирования вычислительных систем находится лишь в начальной стадии.

В частности, методы синтеза генераторов адресных последовательностей,

рассмотренные в ряде источников [6, 16-18], позволяют строить подобные

устройства, описываемые фиксированными значениями переключательной

активности. Задача синтеза устройств для генерирования тестовых после-

довательностей с заданной переключательной активностью и формирования

управляемых вероятностных тестовых последовательностей остается практи-

чески открытой.

В предлагаемой статье приведено решение задачи синтеза генераторов те-

стовых последовательностей максимальной длины, состоящих из 2^m m-раз-

рядных наборов, называемых адресными последовательностями с заданной

переключательной активностью как отдельных разрядов тестовых наборов,

так и с суммарной переключательной активностью их последовательностей.

2. Математическая модель

В [19] была рассмотрена математическая модель универсального генера-

тора последовательностей, состоящих из 2^m m-разрядных наборов, называ-

емых адресными последовательностями. Под адресной последовательностью

понимают последовательность A(n) = a_m-1a_m-2 . . . a₂a₁a₀, n ∈ {0, 1, 2, . . . ,

2m - 1}, где a_i ∈ {0, 1} для i ∈ {0, 1, 2, . . . , m - 1}, состоящую из всех возмож-

ных 2^m m-разрядных двоичных векторов a_m-1a_m-2 . . . a₂a₁a₀, генерируемых

в произвольном порядке, причем каждый вектор формируется только один

155

раз [2, 6, 19]. Например, пересчетная адресная последовательность для m = 4

состоит из 16 4-разрядных двоичных векторов: 0000, 0001, 0010, 0011, . . . ,

1111, каждый из которых формируется только один раз [6]. В качестве ос-

новы математической модели используется модифицированный метод фор-

мирования последовательностей Соболя [20-22]. Согласно указанной модели

формирование n-го элемента A(n) последовательности Соболя, представляю-

щего собой m-разрядный двоичный вектор a_m-1a_m-2 . . . a₀, осуществляется

в соответствии с рекуррентным соотношением

(1)

A(n) = A(n - 1) ⊕ v_i; n = 0, 2^m

− 1, i = 0, m - 1,

в котором к предыдущему элементу A(n - 1) последовательности Соболя

добавляется только одно модифицированное направляющее число v_i, i ∈

∈ {0, 1, 2, . . . , m - 1}, также представляющее собой m-разрядный двоичный

вектор [19-21]. Значение индекса i направляющего числа v_i, используемо-

го в качестве слагаемого в выражении (1), зависит от последовательности

переключений (Transition Sequence) T_m-1 отраженного кода Грея [21-23].

В коде Грея переход из предыдущего состояния кода в последующее осу-

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

тельность индексов этих разрядов и представляет собой последовательность

переключений [23]. В случае наиболее часто используемой разновидности

кода Грея, а именно отраженного кода Грея, последовательность переклю-

чений легко формируется из пересчетной последовательности [23]. Индекс

старшего изменяемого разряда пересчетной последовательности при форми-

ровании ее очередного кода и будет элементом последовательности переклю-

чений. Например, при формировании кода пересчетной последовательности

A(n) = a₃a₂a₁a₀ = 0001 из предыдущего 0000 изменяется только младший

бит, соответственно первым элементом последовательности переключений T₃

будет являться индекс 0. Для m = 4 последовательность переключений от-

раженного кода Грея имеет вид: T₃ = 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0. Эта по-

следовательность формирует последовательность индексов i ∈ {0, 1, 2, 3} при

генерировании A(n) = a₃a₂a₁a₀ для m = 4 согласно (1).

С использованием произвольного начального значения A(0) ∈ {0, 1, 2, . . . ,

2m - 1} рекуррентное соотношение (1) позволяет получить все 2^m - 1 осталь-

ные значения A(n) [19, 22].

Данная математическая модель была обобщена для случая последователь-

ностей, относящихся не только к множеству последовательностей Соболя [22].

В общем случае в качестве порождающей матрицы V направляющих чисел v_i,

i ∈ {0,1,2,... ,m - 1} может быть использована любая двоичная квадратная

матрица размерности m × m вида



β_m-1(0)

β_m-2(0)

β_m-3(0)

β₀(0)



β_m-1(1)

β_m-2(1)

β_m-3(1)

β₀(1)



(2)

V =

β_m-1(2)

β_m-2(2)

β_m-3(2)

β₀(2)



 β_m-1(m - 1) β_m-2(m - 1) β_m-3(m - 1) ... β₀(m - 1)



156

построенная из m линейно независимых двоичных векторов

v_i = β_m-1(i)β_m-2(i)... β₀(i), i = 0,m - 1.

Условие линейной независимости позволяет обеспечить формирование тесто-

вых последовательностей максимальной длины [19].

3. Переключательная активность

Для оценки свойств последовательностей Соболя A(n) = a_m-1a_m-2 . . . a₀,

используемых в качестве тестовой последовательности в [22], был введен чис-

ловой параметр F (a_j ), j ∈ {0, 1, 2, . . . , m - 1}, определяющий количество пе-

реключений (изменений) j-го разряда a_j кода последовательности A(n). Чис-

ловая характеристика F (a_j ) имеет название переключательной активности

[5, 19, 24], которая определяет переключательную активность j-го разряда a_j

тестовых наборов A(n). В общем случае, для произвольного значения j ве-

личина данной характеристики для последовательности (1) определяется по

формуле

F (a_j ) = β_j (0) · 2^m-1 + β_j(1) · 2^m-2 + . . . + β_j (m - 2) · 2¹ + β_j (m - 1) · 2⁰ =

∑

(3)

= β_j(i) · 2^m-1-i.

i=0

На основе переключательной активности F (a_j ) в [19] для последователь-

ности A(n) была введена интегральная мера переключательной активности

∑

(4)

F (A) =

β_j(i)2m-1-i =

2m-1-i

β_j

(i),

j=0 i=0

i=0

j=0

где вторая сумма равна количеству единиц в i-й строке матрицы (2) и пред-

ставляет собой вес Хэмминга w(v_i) двоичного вектора

v_i = β_m-1(i)β_m-2(i)... β₀(i), i = 0,m - 1.

Как следует из линейной независимости двоичных векторов v_i, j-й стол-

бец матрицы V не может быть нулевым, поэтому минимальное значе-

ние F (a_j ), j ∈ {0, 1, 2, . . . , m - 1}, достигается для β_j (m - 1) = 1, и β_j (i) = 0,

i ∈ {0,1,2,... ,m - 2}. Минимальное значение F(a_j) возможно для любого

j-го разряда, но только одного из них [19]. Это ограничение также следует из

линейной независимости строк порождающей матрицы V . Максимальное зна-

чение F (a_j ), j ∈ {0, 1, 2, . . . , m - 1} обеспечивается формированием j-го еди-

ничного столбца матрицы (2), т.е. для значений: β_j (i) = 1, где i = 0, m - 1.

Это влечет равенство

∑

(5)

max F (a_j ) =

2m-1-i = 2^m

− 1.

i=0

157

Для характеристики F (a_j ) последовательностей (1) справедливо следую-

щее

Свойство 1. Для любой последовательности A(n), заданной в (1), пере-

ключательная активность F (a_j ) принимает различные значения в диапазоне

от 1 до 2^m - 1.

Переключательная активность F (A) последовательности

A(n) = a_m-1a_m-2 . . . a₀, n ∈ {0, 1, 2, . . . , 2^m - 1}

принимает минимальное значение для последовательностей кода Грея [22].

Для матрицы, состоящей из m отличающихся строк, каждая из которых

содержит по одной единице, согласно (4) имеем min F (A) = 2^m - 1. Макси-

мальная оценка F (A) также однозначно определяется видом порождающей

матрицы [22], первая строка которой состоит из единиц, а остальные строки

содержат по одному нулевому значению и определяется как

∑

(6)

max F (A) = m2^m-1 + (m - 1)

2m-i-1 = m2^m - 2^m-1

− m + 1.

i=1

Для переключательной активности F (A), заданной в (4), справедливо сле-

дующее

Свойство 2. Переключательная активность F(A) последовательности

A(n), заданной в (1), принимает значения в диапазоне от 2^m - 1 до m2^m-

-2^m-1 - m + 1.

Для реальных значений m > 10 удобно использовать средние значения

Fav(aj ) и Fav(A) рассмотренных ранее числовых параметров переключатель-

ной активности F (a_j ) и F (A), которые показывают среднее значение пере-

ключений при формировании очередного тестового набора. Эти характери-

стики определяются как F_av(A) = F (A)/(2^m - 1) и F_av(a_j ) = F (a_j )/(2^m - 1),

а их максимальные и минимальные величины принимают значения

min F_av(a_j ) = min F (a_j )/(2^m - 1) = 1/(2^m - 1);

max F_av(a_j ) = max F (a_j )/(2^m - 1) = 1;

(7)

min F_av(A) = min F (A)/(2^m - 1) = 1;

max F_av(A) = max F (A)/(2^m - 1) = m - 1/2 + 1/(2^m+1 - 2).

Важным следствием приведенных свойств 1 и 2 является существование

множества порождающих матриц V максимального ранга [19, 22].

4. Синтез последовательностей с заданной

переключательной активностью

Для произвольного m синтез генератора последовательности A(n) (1) с за-

данной средней переключательной активностью F_av(A) и соответствующей

158

Таблица 1. Примеры разложения (8) числа 37

F (A) = w(v₀) · 2³ + w(v₁) ·

w(v₀) w(v₁) w(v₂) w(v₃)

F (A) = 37

· 2² + w(v₂) · 2¹ + w(v₃) · 2⁰

37 = 3 · 8 + 2 · 4 + 2 · 2 + 1 · 1

88844221

37 = 2 · 8 + 4 · 4 + 1 · 2 + 3 · 1

8844442111

37 = 2 · 8 + 3 · 4 + 3 · 2 + 3 · 1

88444222111

ей F (A) заключается в нахождении порождающей матрицы V . Для этого

формируется двоичная m × m матрица максимального ранга с ограничения-

ми, определяющимися величиной F (A). Первоначально величина переклю-

чательной активности F (A) представляется в виде разложения [19].

F (A) = w(v₀) · 2^m-1 + w(v₁) · 2^m-2 +

(8)

+ w(v₂) · 2^m-3 + ... + w(v_m-1) · 2⁰.

Данное разложение представляет величину F (A) в m-ной смешанной си-

стеме счисления, в которой веса разрядов представлены в виде степеней двой-

ки от 2⁰ до 2^m-1, а значения цифр w(v_i) лежат в диапазоне от 1 до m. Отме-

тим, что w(v_i) представляет собой вес Хэмминга двоичного вектора v_i иско-

мой порождающей матрицы V максимального ранга. Отсутствие нулевого

значения w(v_i) объясняется невозможностью построения квадратной мат-

рицы максимального ранга с нулевой строкой, вес Хэмминга которой ра-

вен 0. Второе ограничение на цифры w(v_i) разложения (8) заключается в

том, что только одна цифра w(v_i) может принимать значение m. В терми-

нах порождающей матрицы V максимального ранга это означает, что только

одна строка матрицы может иметь вес, равный m. Существуют и другие,

не столь очевидные, ограничения на цифры w(v_i) (веса Хэмминга) разложе-

ния (8), которые являются основой построения матрицы V максимального

ранга.

В качестве примера рассмотрим случай формирования последовательно-

сти A(n) для m = 4 и переключательной активности F (A) = 37. Величина

F (A) = 37 принадлежит диапазону от 15 до 53, определяемому свойством 2.

В табл. 1 представлены разложения (8) величины 37 для случая m = 4.

Отметим, что каждому разложению (8) можно поставить в соответ-

ствие множество матриц V , веса строк которых соответствуют значениям

цифр w(v_i) указанного разложения. Например, для разложения 37 = 3 · 8 +

+2 · 4 + 2 · 2 + 1 · 1 вес w(v₀) первой строки матрицы равен 3, второй w(v₁)

и третьей w(v₂) строк равен 2, а вес w(v₃) четвертой строки равняется 1.

Матрицы V₁ и V₂, приведенные в табл. 2, являются примерами матриц мак-

симального ранга с указанными весами строк, а матрицы V₃ и V₄ представ-

ляют собой матрицы максимального ранга для других разложений (8) ве-

личины 37. В табл. 2 также приведены примеры формирования последова-

тельностей A(n) согласно (1) для всех четырех видов матриц V . В качестве

последовательности переключений использовалась ранее приводимая в каче-

стве примера последовательность T₃.

159

Таблица 2. Примеры порождающих матриц V и последовательностей A(n)

для m = 4

V₁

V₂

V₃

V₄

β₃(0) β₂(0) β₁(0) β₀(0)

β₃(1) β₂(1) β₁(1) β₀(1)

β₃(2) β₂(2) β₁(2) β₀(2)

β₃(3) β₂(3) β₁(3) β₀(3)

A(0)

000 0

00 00

A(1) = A(0) ⊕ v₀

1110

1011

01 10

1010

A(2) = A(1) ⊕ v₁

001 0

01 11

1001

01 00

A(3) = A(2) ⊕ v₀

1100

1111

1110

A(4) = A(3) ⊕ v₂

010 1

1010

1101

1001

A(5) = A(4) ⊕ v₀

1011

00 01

1011

00 11

A(6) = A(5) ⊕ v₁

011 1

1101

01 00

1101

A(7) = A(6) ⊕ v₀

1001

01 10

00 10

01 11

A(8) = A(7) ⊕ v₃

1000

00 10

01 01

1100

A(9) = A(8) ⊕ v₀

011 0

1001

00 11

01 10

A(10) = A(9) ⊕ v₁

1010

01 01

1100

1000

A(11) = A(10) ⊕ v₀

010 0

1110

1010

00 10

A(12) = A(11) ⊕ v₂

1101

1000

01 01

A(13) = A(12) ⊕ v₀

001 1

00 11

1110

1111

A(14) = A(13) ⊕ v₁

1111

00 01

A(15) = A(14) ⊕ v₀

000 1

01 00

01 11

1011

Процедуру получения разложения (8) для произвольного целого значения

F (A) можно интерпретировать как решение задачи разбиения целого числа

на слагаемые, которыми являются целые положительные числа вида 2ⁱ, где

i ∈ {0,1,2,... ,m - 1}. В табл. 1 приведены примеры подобных разложений,

одним из которых является разложение 37 = 8 + 8 + 8 + 4 + 4 + 2 + 2 + 1,

представленное в виде последовательности 88844221 повторяющихся слагае-

мых 8, 4, 2 и 1 [25-27].

Простейшим способом генерирования всех разбиений целого числа на сла-

гаемые независимо от их порядка является разбиение в обратном лексико-

графическом порядке, начинающееся с разбиваемого целого числа ‘n’, когда

само число представляется одним слагаемым n, и заканчивающееся представ-

лением ‘111. . . 1’ этого числа в виде n слагаемых, равных единице [25].

Для целого значения F (A) = 37 и m = 4, с учетом ограничений на слагае-

мые, которыми в данном случае могут быть только 8, 4, 2 и 1, и их коли-

чество всевозможные разбиения следующие: 88844221, 888442111, 888422221,

8884222111, 884444221, 8844442111, 8844422221, 88444222111.

160

Специфика разбиения значения переключательной активности наклады-

вает ограничение на число слагаемых 2^m-1, 2^m-2, . . . , 2⁰, количество каждого

из которых не должно равняться нулю и превышать m. И только одно сла-

гаемое может входить в разбиение m раз.

Рассмотрим алгоритм разбиения целого числа, определяющего переклю-

чательную активность F (A) последовательности A(n) = a_m-1a_m-2 . . . a₀(1)

для заданного значения m. Слагаемыми разбиения могут быть только целые

числа вида 2ⁱ, где i ∈ {0, 1, 2, . . . , m - 1}, а их сумма должна принадлежать

диапазону от 2^m-1 до m2^m - 2^m-1 - m + 1 (см. свойство 2).

Алгоритм разбиения целого числа на слагаемые.

1. Первоначально определяется сумма всех слагаемых 2ⁱ, которая равня-

ется максимальному m-разрядному двоичному числу 2^m - 1.

2. Выполняется операция деления F (A) на 2^m - 1. Полученное частное w

определяет минимальное количество вхождений каждого из слагаемых 2ⁱ в

разбиение целого F (A). При равенстве нулю остатка q от операции деле-

ния частное w является числом использования каждого из слагаемых 2ⁱ,

i ∈ {0,1,2,... ,m - 1} в разбиении F(A), и на этом шаге алгоритм разбиения

завершается. В противном случае выполняется следующий шаг.

3. Остаток 0 < q < 2^m -1 от операции деления представляется в двоичном

коде q = b_m-1 · 2^m-1 + b_m-2 · 2^m-2 + · · · + b₀ · 2⁰, b_i ∈ {0, 1}.

4. Строится разбиение целого числа F (A) на слагаемые 2ⁱ, где i ∈ {0, 1,

2, . . . , m - 1}, каждое из которых входит в разбиение 0 < w + b_i ≤ m раз, где

величина w + b_i определяет значение цифры w(v_m-1-i) разложения (8).

Применив данный алгоритм для случая m = 6 и F (A) = 189, получим, что

частное w от деления 189 на 63 равняется 3, а остаток q = 0, соответственно

разбиение числа 189 имеет вид 2⁵2⁵2⁵2⁴2⁴2⁴2³2³2³2²2²2² 2¹2¹2¹2⁰2⁰2⁰. Циф-

ры разложения (8) принимают значения w(v₀) = w(v₁) = w(v₂) = w(v₃) =

= w(v₄) = w(v₅) = 3, которые и определяют веса строк матрицы V . В случае

нахождения соответствующей полученным весам строк порождающей мат-

рицы V , применяемой для реализации соотношения (1), нахождение очеред-

ного набора последовательности A(n) всегда будет осуществляться за счет

выполнения трех переключений. В общем случае важным фактом является

существование порождающей матрицы V максимального ранга, веса строк

которой соответствуют цифрам разложения (8) [28].

При получении матрицы V с рангом, отличным от максимального, повтор-

но выполняется формирование случайным образом матрицы с фиксирован-

ными весами Хэмминга ее строк. Каждая строка этой матрицы представля-

ет собой случайный двоичный вектор с заданным весом w(v_i). Затем опять

проверяется ранг матрицы. Очевидно, что требование к весам строк матри-

цы и одновременно необходимость ее максимального ранга могут существен-

но ухудшить вероятностную оценку положительного исхода при нахождении

порождающей матрицы V [28]. Противоречивость данных требований может

приводить к невозможности нахождения подобной матрицы, что иллюстри-

рует следующий пример.

161

Диаграммы для: а - w(v₀) = w(v₁) = w(v₂) = w(v₃) = 2;

б - w(v₀) = w(v₃) = 2,w(v₁) = 1 и w(v₂) = 4.

Пример 1. Определить веса строк порождающей матрицы V для фор-

мирования последовательности A(n) = a₃a₂a₁a0 (1) с переключательной ак-

тивностью F (A) = 30.

Значение m равняется 4, соответственно F (A) = 30 принадлежит требуе-

мому диапазону от 15 до 53. Применив алгоритм, описанный выше, получим

значения цифр w(v₃) = 2, w(v₂) = 2, w(v₁) = 2 и w(v₀) = 2 разложения (8),

которому соответствует разбиение 88442211 целого числа 30. Однако попыт-

ка нахождения соответствующей матрицы максимального ранга для m = 4,

у которой все строки содержат по две единицы, не дает положительного ре-

зультата. Это связано с тем, что в данном случае требование о линейной неза-

висимости векторов v₃, v₂, v₁ и v₀ и значения их весов w(v₃), w(v₁), w(v₂) и

w(v₀) несовместимы. В то же время разбиение 884222211 числа 30 определя-

ет цифры w(v₃) = 2, w(v₂) = 4, w(v₁) = 1 и w(v₀) = 2 разложения (8) для

которого уже существуют матрицы с максимальным рангом.

Приведенный пример показывает, что получение одного разбиения цело-

го числа на слагаемые не представляется сложной задачей. В свою очередь,

генерирование порождающей матрицы V может потребовать наличия боль-

шего числа разбиений целого числа, полученных путем модификации исход-

ного. По аналогии с диаграммами Юнга [25] для формализации процедуры

модификации разбиения числа на слагаемые определим диаграмму разложе-

ния (8), которая учитывает все сформулированные ранее ограничения.

Определение 1. Диаграмма разложения (8) целого числа, принадле-

жащего диапазону от 2^m - 1 до m2^m - 2^m-1 - m + 1, представляет собой

матрицу, состоящую из m × m клеток, причем каждая заполненная клет-

ка i-й строки, i ∈ {0, 1, 2, . . . , m - 1}, соответствует целому числу 2^m-1-i.

В матрице отсутствуют незаполненные строки, выравненные по левой гра-

нице, а их заполнение соответствует разбиению целого числа.

На рисунке приведены две диаграммы разложения для случая целого чис-

ла 30.

Приведенные диаграммы свидетельствуют о том, что сумма значений за-

полненных клеток в обоих случаях равняется числу 30, а их заполнение со-

ответствует его разбиениям 88442211 и 884222211 на слагаемые 8, 4, 2 и 1.

Анализ примера показывает, что диаграмма б) может быть получена из диа-

граммы а) путем удаления одной клетки 4 и заполнения двух незаполнен-

ных клеток 2. Подобная процедура эквивалентна удалению слагаемого 4 из

162

разбиения 88442211 числа 30 и добавлению двух слагаемых, равных 2, для

получения разбиения 884222211 этого же числа, что позволяет определить

операцию модификации разложения, соответствующего определению 1.

Операция модификации. Для i-й i = 0,m - 2, строки диаграммы

разложения (8), содержащей более одной заполненной клетки, удаление за-

полненной клетки сопряжено с заполнением 2^j свободных клеток в (i + j)-й

строке, i + j = 1,m - 1, диаграммы, где j ≤ log₂(m - 1).

Данная операция симметрична относительно операций удаления и запол-

нения. Это значит, что удаление 2^j заполненных клеток в i-й, i = 1, m - 1,

строке диаграммы, содержащей более чем 2^j заполненных клеток, сопря-

жено с заполнением одной клетки в (i - j)-й строке, i - j = 0, m - 2, где

j ≤ log₂(m - 1).

5. Задачи синтеза последовательностей с заданной

переключательной активностью

Учитывая широкий спектр применения тестовых последовательно-

стей A(n) [19, 21, 22, 29, 30], сформулируем задачи синтеза генераторов та-

ких последовательностей. Результатом синтеза, как указывалось ранее, бу-

дет являться порождающая матрица V , которая обеспечивает значения пе-

реключательной активности F_av(A) и F_av(a_j ) последовательности A(n) =

= a_m-1 a_m-2 ...a₀, a_i ∈ {0,1}, i ∈ {0,1,2,... ,m-1} и n ∈ {0,1,2,... ,2^m-1}.

Задача 1. Синтезировать устройство, формирующее последователь-

ность A(n) для заданного значения m и требуемой величины F_av(A).

Примерoм подобной задачи может быть задача формирования последо-

вательности двойного Грея, т.е. такой последовательности, для которой при

переходе от текущего тестового набора к последующему выполняется толь-

ко два переключения. Решение задачи 1 будет заключаться в: (i) получении

F (A) = int [F_av(A) × (2^m - 1)], где int означает операцию получения целой

части от числа, представленного в скобках; (ii) разбиении целого числа F (A)

на слагаемые; (iii) получении значений весов строк w(v_i) искомой порож-

дающей матрицы V и нахождении матрицы максимального ранга с весами

строк w(v_i). В случае невозможности получения требуемой матрицы в силу

противоречивости сформулированных к ней требований первоначально при-

меняется операция модификации разбиения целого числа, описанная ранее.

Следующим и финальным этапом является коррекция значения F (A).

В общем случае операция коррекции применяется для обеспечения за-

данного значения F_av(A) с минимальной погрешностью. Для этого перво-

начально изменяется (корректируется) значение F (A) на минимальную ве-

личину (+1 или -1) и осуществляется поиск соответствующей порождаю-

щей матрицы V (2). В случае отрицательного исхода по результатам поис-

ка требуемой матрицы значение отклонения величины F (A) от требуемого

значения int [F_av(A) · (2^m - 1)] увеличивается. Следует отметить, что коррек-

ция величины F (A) на единицу вносит несущественную погрешность, кото-

163

рая для реальных значений m в процентном исчислении определяется как

(1/(2^m - 1)) × 100%.

Задача 2. Синтезировать устройство, формирующее последователь-

ность A(n) для заданного значения m, в которой для k ≤ m ее разря-

дов a_α1,a_α2,... ,a_αk, αi ∈ {0,1,2,... ,m - 1}, i = 1,k, определены конкретные

значения переключательной активности F_av(a_α1), F_av (a_α2), . . . , F_av(a_αk).

Также как и в случае задачи 1, средние значения F_av(a_α1), F_av(a_α2),

..., F_av(a_αk) переключательных активностей представляются в виде сум-

марных величин количества F (a_α1), F (a_α2), . . . , F (a_αk) переключений разря-

дов a_α1, a_α2, . . . , a_αk последовательности A(n). Далее F (a_αi) преобразуются в

m-разрядный двоичный код, F (a_αi)₍₁₀₎ = F (a_αc)₍₂₎ = β_αi(0) · 2^m-1 + β_αi(1) ·

·2^m-2+. . .+β_αi(m-1)·2⁰. Отметим, что β_αi(0) представляет собой старший бит

полученного двоичного кода, а сам код β_αi(0)β_αi(1) . . . β_αi(m - 1) однознач-

но определяет значения αi-го столбца порождающей матрицы V (2). Таким

образом вычисляются значения всех k ≤ m столбцов матрицы V , которые

определяют переключательные активности F_av(a_α1), F_av (a_α2), . . . , F_av(a_αk).

В случае невыполнения необходимого условия к F (a_α1), F (a_α2), . . . ,

F (a_αk), сформулированного в виде свойства 1, применяется операция кор-

рекции.

Следующим шагом решения задачи 2 является проверка выполнения

достаточного условия к значениям переключательных активностей F (a_α1),

F (a_α2), . . . , F (a_αk), представляющими собой двоичные коды столбцов матри-

цы V , которым является линейная независимость столбцов порождающей

матрицы, невыполнение которого влечет применение операций коррекции.

Далее случайным образом (равновероятно и независимо) генерируются

остальные столбцы двоичной матрицы V , в которой столбцы α1, α2, . . . , αk

принимают заданные значения. Определяется ранг полученной матрицы.

В случае максимального ранга данная матрица является искомой и исполь-

зуется для построения генератора последовательности A(n). При получении

матрицы с рангом, отличным от максимального значения, равного m, по-

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

матрицы V .

Задача 3. Синтезировать устройство, формирующее последователь-

ность A(n) для заданного значения m, в которой для k ≤ m ее разря-

дов a_α1,a_α2,... ,a_αk, αi ∈ {0,1,2,... ,m - 1}, i = 1,k, определены конкретные

значения переключательной активности F_av(a_α1), F_av (a_α2), . . . , F_av(a_αk), а

переключательная активность A(n) равняется F_av(A).

Корректная постановка задачи 3 предполагает, что F_av(a_α1) + F_av(a_α2) +

+ ··· + F_av(a_αk) < F_av(A) ≤ m - 1/2 + 1/(2^m+1 - 2). На начальной стадии

решение задачи 3 повторяет решение задачи 2. Далее выполняются шаги

процедуры решения задачи 1. Отличием будет являться разбиение целого

числа

F^∗(A) = int[F_av(A) × (2^m - 1)] - int [F_av(a_α1) × (2^m - 1)] -

- int [F_av(a_α2) × (2^m - 1)] - · · · - int [F_av(a_αk) × (2^m - 1)]

164

на слагаемые, а не числа F (A). Кроме того, при получении значений весов

строк w(v_i) искомой порождающей матрицы V необходимо учитывать веса

строк ранее сгенерированных k столбцов.

В случае невозможности получения требуемой матрицы в силу противо-

речивости сформулированных к ней требований первоначально применяется

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

коррекция значений F^∗(A) и, в последнюю очередь коррекция переключа-

тельных активностей F (a_α1), F (a_α2), . . . , F (a_αk) начиная с их максимальных

значений. В качестве примера рассмотрим решение задачи 3 для конкретного

случая.

Пример 2. Синтезировать устройство, формирующее последователь-

ность A(n) = a₅a₄a₃a₂a₁a₀ для m = 6, в которой для разрядов a₁ и a₃ опре-

делена их переключательная активность F_av(a₁) = 1, F_av(a₃) = 1/63, а также

значение F_av(A) = 2.

Выполнение неравенства F_av(a₁) + F_av(a₃) = 1 + 1/63 < F_av(A) = 2 ≤ m -

- 1/2 + 1/(2^m+1 - 2) = 5,5079 свидетельствует о возможности построения

устройства с заданными переключательными активностями. На основании

средних значений переключательных активностей F_av(a₁), F_av(a₃) и F_av(A)

получим F (a₁) = 63, F (a₃) = 1 и F (A) = 126.

Значения F (a₁) и F (a₃) представляются в виде F (a₁) = 63₍₁₀₎ = 111111₍₂₎

и F(a₃) = 1₍₁₀₎ = 000001₍₂₎. Соответственно, значения первого и третьего

столбцов матрицы V примут вид β₁(0)β₁(1)β₁(2)β₁(3)β₁(4)β₁(5) = 111111

и β₃(0)β₃(1)β₃(2)β₃(3)β₃(4)β₃(5) = 000001. Вычисляется значение F^∗(A) =

= F(A) - F(a₁) - F(a₃) = 126 - 63 - 1 = 62.

Далее, используя описанный выше алгоритм разбиения целого числа

F^∗(A) = 62 на слагаемые, получим w = 0, а q = 62₍₁₀₎ = 111110₍₂₎. Таким об-

разом, b₅b₄b₃b₂b₁b₀ = 111110.

Строится разбиение целого числа F^∗(A) на слагаемые 2ⁱ, где i = 0, 5, каж-

дое из которых входит в разбиение w + b_i = 1 + b_i раз. Так как q = 111110,

слагаемые 2⁵, 2⁴, 2³, 2² и 2¹ входят в разбиение числа 62 по одному разу,

а слагаемое 1 не входит, так как только b₀ = 0. Величина w + b_i определяет

значение цифры w(v_m-1-i) разложения (8) числа F^∗(A), что в данном слу-

чае является весом Хэмминга строк искомой матрицы V , состоящей из шести

строк и шести столбцов, исключая первый и третий столбец, и, в силу этого,

допускающее нулевые значения цифр разложения.

Далее случайным образом формируются значения шести четырехраз-

рядных двоичных векторов с весами Хэмминга, равными w(v₀) = w(v₁) =

= w(v₂) = w(v₃) = w(v₄) = 1 и w(v₅) = 0, которые и будут определять значе-

ния остальных столбцов (кроме первого и третьего) искомой матрицы. Для

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

В случае положительного исхода матрица является основой для формиро-

вания последовательностей A(n) (1) с заданными в условии примера 3 пе-

реключательными активностями. Если ранг матрицы не равен 6, процедура

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

шесть четырехразрядных векторов, определяющие значения разрядов a₅, a₄,

165

a₂ и a₀ последовательности A(n) = a₅a₄a₃a₂a₁a₀. В случае, когда в результате

определенного количества итераций искомая матрица максимального ранга

не находится, последовательно применяются операции модификации и кор-

рекции. Решением примера задачи 3 может быть следующая матрица:



β₅(0) β₄(0) β₃(0) β₂(0) β₁(0) β₀(0)



β₅(1) β₅(1) β₃(1) β₂(1) β₁(1) β₀(1)



β₅(2) β₅(2) β₅(2) β₂(2) β₁(2) β₀(2)



V =



β₅(3) β₅(3) β₃(3) β₂(3) β₁(3) β₀(3)



β₅(4) β₅(4) β₃(4) β₂(4) β₁(4) β₀(4)



 β₅(5) β₅(5) β₃(5) β₂(5) β₁(5) β₀(5)

Этот результат был получен путем последовательного применения опера-

ций модификации и коррекции.

6. Заключение

Предлагается методика синтеза генераторов тестовых последовательно-

стей с заданной переключательной активностью. Приведены определения

операций модификации и коррекции для нахождения порождающей матри-

цы генератора тестов. Сформулированы задачи синтеза тестовых последо-

вательностей с заданной переключательной активностью, показаны пути их

решения и существующие ограничения.

СПИСОК ЛИТЕРАТУРЫ

1. Jha N.K., Gupta S. Testing of Digital Systems. Cambridge, UK: Cambridge Univer-

sity Press, 2003.

2. Ярмолик В.Н. Контроль и диагностика вычислительных систем. Минск: Бест-

принт, 2019.

3. Bushnell M.L., Agrawal V.D. Essentials of Electronic Testing for Digital, Memory

& M ixed-Signal VLSI Circuits. N.Y.: Kluwer Academic Publishers, 2000.

4. Sharma A.K. Semiconductor Memories: Technology, Testing, and Reliability. Lon-

don: John Wiley & Sons, 2002.

5. Wang S., Gupta S.K. An automatic test pattern generator for minimizing switching

activity during scan testing activity // IEEE Trans. Comp. Aided Des. Int. Circ.

Syst. 2002. Vol. 21. No. 8. P. 954-968.

6. Goor A.J., Kukner H., Hamdioui S. Optimizing memory BIST Address Generator

implementations // Proc.

6th Int. Conf. on Design & Tech. Integr. Syst. in

Nanoscale Era (DTIS). 2011. P. 572-576.

7. Pedram M. Power minimization in IC design: principles and applications // ACM

Tran. Design Aut. Elect. Syst. 1996. Vol. 1. P. 3-56.

8. Мурашко И.А., Ярмолик В.Н. Встроенное самотестирование. Методы миними-

зации энергопотребления. Минск: Бестпринт, 2008.

166

Girard P., Guiller L., Landrault C., et al. A test vector ordering technique for

switching activity reduction during test operation // Proc. Ninth Great Lakes Symp.

VLSI. 1999. P. 24-27.

10.

Bellaouar A., Elmasry M. Low-Power Digital VLSI Design Circuits and Systems.

US: Springer,1996.

11.

Huang R., Sun W., Xu Y. et al. A Survey on Adaptive Random Testing // IEEE

Trans. Soft. Eng. 2015. Vol. 14. No. 8. P. 1-36.

12.

Mrozek I., Yarmolik V.N. Iterative antirandom testing // J. Elect. Test: Theory

Appl. 2012. Vol. 9. No. 3. P. 251-266.

13.

Chen T.Y., Kuo F.C., Merkel R.G. et al. Adaptive Random Testing: The ART of

test case diversity // J. Syst. Soft. 2010. Vol. 83. No. 1. P. 60-66.

14.

Mrozek I., Yarmolik V.N. Antirandom test vectors for BIST in Hardware / Software

systems // Fundamenta Informaticae. 2012. No. 119. P. 1-23.

15.

Ярмолик С.В., Ярмолик В.Н. Управляемые вероятностные тесты // АиТ. 2012.

№ 10. С. 142-155.

Yarmolik S.V., Yarmolik V.N. Controlled Random Tests // Autom. Remote Control.

2012. Vol. 73. No. 10. P. 1704-1714.

16.

Du X., Mukherjee N., Cheng W.T. et al. Full-speed field-programmable memory

BIST architecture // Proc. IEEE Intern. Test Conf. 2005. P. 1173-1182.

17.

Aswin A.M., Ganesh S.S. Implementation and validation of memory built in self-test

(MBIST) - survey // Int. J. Mech. Eng. Tech. 2019. Vol. 10. No. 3. P. 153-160.

18.

Ярмолик С.В., Ярмолик В.Н. Многократные неразрушающие маршевые тесты

с изменяемыми адресными последовательностями // АиТ. 2007. № 4. С. 126-137.

Yarmolik V.N., Yarmolik S.V. The Repeated Nondestructive March Tests with Vari-

able Address Sequences // Autom. Remote Control.

2007. Vol.

68. No. 4.

P. 126-137.

19.

Ярмолик В.Н., Шевченко Н.А. Формирование адресных последовательностей с

заданной переключательной активностью // Информатика. 2020. Т. 17. № 1.

С. 7-23.

20.

Соболь И.М. Точки, равномерно заполняющие многомерный куб. М.: Знание,

1985.

21.

Антонов И.А., Салеев В.М. Экономичный способ вычисления ЛП-последова-

тельностей // Журн. вычисл. матем. и матем. физ. 1979. Т. 19. No. 1. С. 243-245.

22.

Ярмолик С.В., Ярмолик В.Н. Квазислучайное тестирование вычислительных

систем // Информатика. 2013. No. 3(39). С. 65-81.

23.

Savage C. A survey of combinatorial Gray code // SIAM Review. 1997. Vol. 39.

No. 4. P. 605-629.

24.

Pomeranz I. An adjacent switching activity metric under functional broadside tests /

I. Pomeranz // IEEE Trans. Comput. 2013. Vol. 62. No. 4. P. 404-410.

25.

Кнут Д. Искусство программирования. Т. 4А. Комбинаторные алгоритмы. Ч. 1.

М.: Вильямс, 2013.

26.

McKay J.K.S. Algorithm 371: Partitions in natural order [A1] // Commun. ACM.

1970. Vol. 13. No. 1. P. 52.

27.

Stojmenović I, Zoghbi A. Fast algorithms for generating integer partitions // Int. J.

Comp. Math. 1998. Vol. 70. No. 2. P. 319-332.

167