Генераторы нелинейных последовательностей.

Помимо рассмотренных линейных генераторов при компактной диагностике используются генераторы на регистрах сдвига с нелинейной функцией обратной связи. Эти генераторы порождают нелинейные рекуррентные последовательности, которые по своим диагностическим свойствам отличаются от линейных. В частности, в n-разрядном нелинейном генераторе достаточно просто порождается двоичная последовательность де Брейна. Она представляет собой нелинейную двоичную последовательность {x_i} периода T=2ⁿ , в которой всевозможные векторы (x_j x _j+1… x _j+n-1) длины n при любом j встречается только один раз. Исключение запрещенного нулевого состояния всех триггеров генератора позволяет увеличить период формируемой последовательности и сделать его максимально возможным, равным 2^m, повысить ее качество, так как вероятности появления 0 и 1 становятся равными 0,5. Последовательности длиной 2^m называются последовательностями де Брейна. Алгоритм построения генератора де Брейна:

Записываем уравнения в общем виде работы линейного генератора

где

Если последовательность состояний РС представить как последовательность m—мерных векторов А = (a₁,a₂,…a_m), где α_n€{0,1}, n=1,m то преобразование, осуществляемое схемой в некотором к – м такте работы, можно записать в матричной форме:

Далее изменяем запись для следующим образом;

(1.12)

Следующие состояния – обычный сдвиг.

Пример:

Для построения одноканального генератора М-последовательности получим систему логических уравнений:

(1.13)

На рис. 1.5 изображена схема гене­ратора М-последовательности для полинома в соответствии с системой логических уравнений (1.13),а в табл. 1.2 представлена последовательность смены состояний регистров сдвига при начальном состоянии A(0)=1000. Регистр сдвига реализован на D-триггерах, состояния которых изменяются по приходу на С-входы тактовых импульсов .

Рис. 1.5

Таблица 1.2

№ такта					Выход

Из табл.1.2 следует, что длина формируемой последовательности равна 8, т.е. через 8 тактов регистр устанавливается в начальное состояние

Глава 2.

Сигнатурный анализ

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

Одноканальный сигнатурный анализатор.

Построить сигнатурный анализатор можно двумя способами:

метод свёртки;

метод деления полиномов.

Структурная типовая схема сигнатурного анализатора, использующая метод свертки, состоит из регистра сдвига RG и сумматора по модулю 2 M2, на входы которого подключены выходы разрядов регистра сдвига в соответствии с порождающим полиномом φ(x) (рис.2.1).

Рис.2.1

Управляющими сигналами сигнатурного анализатора являются СТАРТ, СТОП и СДВИГ. Сигналы СТАРТ и СТОП формируют временной интервал, в течение которого осуществляется процедура сжатия информации на анализаторе. Под действием сигнала СТАРТ элементы памяти регистра сдвига устанавливаются в исходное состояние, как правило, нулевое, а сам регистр начинает выполнять функцию сдвига на один разряд вправо под действием синхронизирующих сигналов СДВИГ. По приходу каждого синхронизирующего импульса в первый разряд регистра сдвига записывается информация, соответствующая выражению:

(2.1) В этом выражении - k-й символ сжимаемой последовательности {y(k)}, , где l-длина сжимаемой последовательности, - коэффициенты порождающего полинома - содержимое i-го элемента памяти регистра сдвига в k-1-й такт. Процедура сдвига информации в регистре описывается отношением , .

Таким образом, полное математическое описание функционирования сигнатурного анализатора имеет следующий вид:

, , , , (2.2) причем l-длина сжимаемой последовательности, как правило, принимается равной или меньше величины 2^m-1. По истечении l тактов функционирования сигнатурного анализатора на его элементах памяти фиксируется двоичный код, который представляет собой сигнатуру.

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

, (2.3)

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

Пример формирования сигнатуры для потока данных 11110101, описываемого полиномом , и делителя приведен на рис.2.2.

Аппаратурная реализация сигнатурного анализатора приведена на рис.2.2

Рис.2.2

Здесь а₁, а₂ , а₃ элементы памяти (D-триггеры),

Пример формирования сигнатуры для потока данных 11110101, описываемого полиномом χ(х)=х⁷+х⁶+x⁵+х⁴+x²+1, и делителя φ(х)=х³+x²+1 приведен на рис.2.3.

q(x)= (10111)₂ =x⁴+x²+x+1 S(x)=(110)=x²+x

Рис 2.3

Таким образом, показано, что остаток от деления χ(х) на φ(х) есть сигнатура, полученная на анализаторе в результате сжатия последовательности χ(х), ;

Для реализации сигнатурного анализатора, описываемого полиномом φ(х)=х³+x²+1 (рис.2.2), существует альтернативная структура, которая является более предпочтительной с точки зрения аппаратурного построения и называется методом свертки. При реализации метода свертки используются внешние сумматоры по модулю два. Для построения сигнатурного анализатора используется обратный полином В нашем случае . Аппаратурная реализация такого анализатора представлена на рис. 2.4.

Рис.2.4

Однако, результат с(х), получаемый при свертке последовательности р(х) на сигнатурном анализаторе с внешними сумматорами по модулю два не совпадает с остатком от деления, т. е. с(х) ≠s(х). В нашем случае С(х)=(100)₂ . В то же время между с(х) и s(x) существует однозначная связь, которая в общем случае определяется выражением

S(x)= (2.4)

Здесь с(х) - результат свертки на сигнатурном анализаторе, описываемом полиномом ψ(х); s(x) остаток от деления многочлена χ(х) на полином φ(х), коэффициенты α принадлежат полиному φ(х). Для частного случая, представленного на рис.2.2 и 2.4

S(x)= , S(x)=(110)₂ (2.5)

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

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