МНОГОКАНАЛЬНЫЙ СИГНАТУРНЫЙ АНАЛИЗАТОР Российский патент 1997 года по МПК G06F11/00 

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

Известен многоканальный сигнатурный анализатор, содержащий n сумматоров по модулю два (при к=1) и n регистров, разрядность каждого регистра N определяется степенью образующего многочлена Ф(х). Характер обратных связей с разрядных выходов регистров сдвига на входы сумматоров по модулю два определяется ненулевыми коэффициентами Ф(х) [1]
Данное устройство обладает недостаточной достоверностью контроля и низким быстродействием при верификации файлов.

Известен многоканальный сигнатурный анализатор, содержащий n регистров разрядностью N, где N степень образующего многочлена, коэффициенты которого принадлежит полю GF(2ⁿ), блоки сложения, деления и умножения в поле GF(2ⁿ). Блок сложения реализован на n сумматорах по модулю два. Характер обратных связей в устройстве определяется видом образующего многочлена. n регистров разрядностью N можно рассматривать как N регистров разрядностью n, выполняющих функцию задержки на один такт [2]
Данное устройство имеет сложную структуру и обладает низким быстродействием при верификации файлов из-за наличия разрядных логических операций.

Известен многоканальный сигнатурный анализатор, содержащий N регистров, блок сложения по модулю L, где L простое число, блок деления по модулю L, блоки умножения по модулю L. Характер обратных связей в устройстве определяется видом образующего многочлена Ф(х) степени N, коэффициенты которого принадлежат множеству0,1,L-1} [3]
Данное устройство требует больших затрат на релизацию, обладает низким быстродействием при верификации файлов из-за наличия операций по модулю L, не обладает свойствами наращивания разрядности.

Наиболее близким по технической сущности и по достигаемому эффекту к предлагаемому является устройство, содержащее N регистров разрядности n, где N степень образующего многочлена Ф(х), n число входов анализатора, при этом каждый регистр выполняет функцию задержки на один такт. В состав устройства входят также блоки сложения, умножения и деления в поле GF(2ⁿ). Число блоков сложения и умножения определяется числом ненулевых коэффициентов образующего многочлена, коэффициенты которого принадлежат полю GF(2ⁿ) [4]
Данное устройство имеет сложную структуру, обладает низким быстродействием при верификации файлов из-за наличия разрядных операций по модулю два в блоках умножения и деления, не обладает свойством наращивания разрядности.

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

В многоканальный сигнатурный анализатор, содержащий N регистров, где N - степень образующего многочлена Ф(х)=х^N + х^K + 1, коэффициенты которого принадлежат множеству 0,1} причем группа информационных входов j-го регистра (при к>1) подключена к группе разрядных выходов (j-1)-го регистра, группа информационных входов i-го регистра (при к<N-1) подключена к группе разрядных выходов (i-1)-го регистра, где , тактовые входы всех регистров объединены и образуют тактовый вход устройства, разрядные выходы регистров образуют группу информационных выходов устройства, дополнительно введены два сумматора, причем первая группа информационных входов первого сумматора образует группу информационных входов устройства, вторая группа информационных входов первого сумматора объединена с первой группой входов второго сумматора и подключена к группе разрядных выходов N-го регистра, вторая группа информационных входов второго сумматора подключена к группе разрядных выходов к-го регистра группа информационных выходов первого сумматора подключена к группе информационных входов первого регистра, группа информационных выходов второго сумматора подключена к группе информационных входов (к+1)-го регистра.

Использование в составе устройства двух комбинационных полных сумматоров позволяет принципиально изменить логику работы анализатора. Лежащий в основе работы известных сигнатурных анализаторов математический аппарат теория конечных полей или полей Галуа. Сумматоры в предлагаемом устройстве выполняют функцию сложения по модулю 2ⁿ, а из теории конечных полей известно, что множество 0,1,L-1} где операция сложения выполняется по модулю L, а L - не простое число, не может быть полем.

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

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

Замена блоков сложения, умножения и деления в поле GF(L) на два сумматора упрощает структуру устройства и делает ее регулярной, что облегчает интегральное исполнение анализатора.

Многоканальный сигнатурный анализатор (МСА) (фиг.1) имеет первый 1.1 и второй 1.2 входы наращивания разрядности, группу 2 информационных входов, тактовый 3 вход, содержит первый 4.1 и второй 4.2 сумматоры, первый 5.1, второй 5.2 и третий 5.3 регистры. Число регистров 5 равно степени образующегося многочлена, примитивного над GF(2). Разрядность регистров 5 равна числу n информационных входов в группе 2. МСА имеет также первый 6.1 и второй 6.2 выходы наращивания разрядности, а также группу информационных выходов, которую образуют разрядные выходы регистров 5.

Структура устройства однозначно определяется видом образующего многочлена х^N + х^K + 1. На фиг.2 рассмотрен случай, когда этот многочлен имеет вид Ф(х)= х³ + Х + 1, поэтому второй 4.2 сумматор расположен между первым 5.1 и вторым 5.2 регистрами, общее число регистров равно трем.

Группа 2 информационных входов устройства подключена к первой группе информационных входов первого сумматора, вторая группа информационных входов которого объединена с первой группой информационных входов второго 4.2 сумматора и подключена к группе разрядных выходов третьего 5.3 регистра. Вторая группа информационных входов второго 4.2 сумматора подключена к группе разрядных выходов первого 5.1 регистра, группа информационных входов которого подключена к группе информационных выходов первого 4.1 сумматора. Группа информационных входов второго 5.2 регистра, группа разрядных выходов которого соединена с группой информационных входов третьего 5.3 регистра. Тактовые входы всех регистров 5 объединены и образуют тактовый 3 вход устройства.

Устройство работает следующим образом. Анализируемые двоичные последовательности, которые являются реакциями объекта контроля на входные тестовые воздействия, подаются на входы 2 МСА, сопровождающие тактовые импульсы на вход 3 МСА. После окончания окна измерения в регистрах 5 образуется сигнатура, которая сравнивается затем с кодовым эталоном, полученным заранее с работоспособной схемы. По результатам этого сравнения делается вывод о техническом состоянии ОК, так как наличие в нем неисправностей проявляется в виде искажений его выходных последовательностей.

Входным анализируемым последовательностям
a_i a_i1 a_ij a_im,
где m длина анализируемых последовательностей, , a_ij ∈ 0,1} можно поставить в соответствие многочлен А(х) степени (m-1)
A(x) A₁x^m-1 + + A_jx^m-j + + A_m,
коэффициенты которого определяются видом соответствующего двоичного набора a_1j a_2j a_ij a_nj, . Процесс получения сигнатуры будет заключаться в делении по модулю 2ⁿ многочлена А(х) на многочлен Φ(x)=x^N + (2ⁿ 1)x^K + (2ⁿ 1). Код, получающийся в регистрах 5, т.е. сигнатура, будет равен остатку от этого деления.

Анализируемый вектор A=(A₁.A_j.A_m) можно представить как сумму векторов последовательностей без ошибок B=(B₁.B_j.B_m) и вектора ошибок C=(C₁.C_j.C_m), причем для любых A_j, B_j, C_j справедливо A_j=B_j + C_j, , где сложение выполняется по модулю 2ⁿ.

Согласно принципу суперпозиции S_A=S_B + S_C, где S_A, S_B, S_C сигнатуры соответственно последовательностей А, В и С. Отсюда следует, что для обнаружения искажений в анализируемых последовательностях необходимо и достаточно, чтобы многочлен последовательности ошибок С(х) не делился нацело многочленом Φ(x).

Очевидно, что сигнатура последовательности ошибок при m ≅ N не может быть нулевой, так как первый отличный от нуля символ последовательности С, попавший в МСА, не успевает выйти из него до конца формирования сигнатуры. Для m= N + 1 существует только (2ⁿ-1) необнаруживаемых последовательностей ошибок, соответствующие им многочлены имеют вид Φ(x)•1, Φ(x)•2, ..., Φ(x)•(2ⁿ-1) Для m=N+2 существует уже (2ⁿ)²-1 необнаруженных последовательностей ошибок и т.д. В общем случае число необнаруженных ошибок
N_HO=(2ⁿ)^m-N-1,
а доля обнаруженных ошибок в последовательностях длиной m > N

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

Пример. Пусть n=2, N=3, Φ(x)x³+3x+3, а входные последовательности имеют вид
1 0 1 0 1 0 1 0
0 1 1 0 0 1 1 1
В этом случае B=12301232, B(x)=x⁷+2x⁶+3x⁵+x³+2. Выполним деление B(x) на Φ(x) (фиг.4). Частное от деления Q=12033, остаток R=111.

Убедимся, что сигнатура правильной последовательности В действительно равна S_B= 111. Процесс получения сигнатуры последовательности B=12301232 отражен в табл.1. Предположим, что вместо правильной последовательности В на вход 2 МСА приходит последовательность с ошибками A₁=12311122. Соответствующая последовательность ошибок имеет вид C₁=00010330, C(x)=x⁴+3x²+3x= Φ(x)•x делится нацело на Φ(x) т.е. данная ошибка должна быть пропущена. Убедимся в этом. Процесс получения сигнатуры последовательности A₁=12311122 отражен в табл.2. Действительно, сигнатура последовательности с ошибками равна сигнатуре правильной последовательности, т.е. данная ошибка будет пропущена. В табл. 3 отражен процесс получения сигнатуры последовательности C₁= 00010330. Предположим, что вместо правильной последовательности В на вход 2 МСА приходит последовательность с ошибками A₂=11321202. Соответствующая последовательность ошибок имеет вид C₂=03020010, C(x)=3x⁶+2x⁴+x не делится нацело на Φ(x) следовательно, данная ошибка должна быть обнаружена. Убедимся в этом. Процесс получения сигнатуры последовательности A₂=11321202 отражен в табл. 4. Начальное состояние всех регистров 5 устройства нулевое. Цепи установки в исходное состояние на фиг.1 не показаны.

Сравним аппаратные затраты на реализацию предлагаемого устройства и устройства, реализующего деление многочленов над полем GF(L). Если L простое число, преимущества предлагаемого устройства очевидны: два сумматора значительно проще блоков сложения, умножения и деления по модулю L. Если L=2Mⁿ, где n натуральное, то блок сложения в поле GF(2ⁿ) осуществляет поразрядное сложение по модулю 2, т.е. с точки зрения аппаратных затрат, эквивалентен двум сумматорам предлагаемого устройства. Однако помимо блока сложения в поле GF(2ⁿ) в прототипе имеются блоки умножения и деления в поле GF(2ⁿ). В каждой конкретной ситуации существует как минимум один из этих блоков. Таким образом, и в этом случае предлагаемое устройство проще.

Еще больший эффект достигается при использовании данного устройства для верификации файлов. Программная реализация устройства очень проста: алгоритм работы МСА в каждом такте содержит лишь операторы присваивания и сложения, нет необходимости ни в выполнении операций по модулю простого числа, ни в поразрядных действиях, которые требуются в устройстве-прототипе. Так, например, для случая, показанного на фиг.2, указанный алгоритм имеет вид
P3:P2,
P2:P1 + P30,
P1:P30 + SRC,
P30:P3,
где P1, P2, P3 новое содержимое регистров, P30 старое содержимое третьего регистра, SRC анализируемый двоичный набор.

Таким образом, при верификации файлов помимо упрощения устройства достигается еще один эффект повышение быстродействия. Использование в составе МСА полных сумматоров 4.1 и 4.2 позволяет получить дополнительно такое ценное свойство, как возможность наращивания разрядности. На фиг.3 показан пример утроения разрядности МСА.

Изобретение относится к вычислительной технике и может использоваться для верификации файлов, для контроля аппаратных средств ЭВМ. Анализатор содержит группу 2 информационных входов, тактовый вход 3, N регистров 5 разрядностью n, где n - число информационных входов, N - степень образующего многочлена Ф(х)= Х^N + Х^K + 1. В устройство введены два полных сумматора 4, два входа и два выхода наращивания разрядности соответственно 1.1, 1.2 и 6.1, 6.2. Устройство имеет дополнительное свойство - возможность наращивания разрядности. 4 ил., 4 табл.

Многоканальный сигнатурный анализатор, содержащий N регистров, где N - степень образующего многочлена
Ф(х) x^N + x^k + 1,
причем группа информационных входов j-го регистра (при k > 1) подключена к группе разрядных выходов (j 1) регистра, группа информационных входов i-го регистра (при k < N 1) подключена к группе разрядных выходов (i 1)-го регистра, где тактовые входы всех регистров объединены и образуют вход сумматора, разрядные выходы регистров образуют группу информационных выходов устройства, отличающийся тем, что он дополнительно сдержит два сумматора, причем первая группа информационных входов первого сумматора образует группу информационных входов устройства, вторая группа информационных входов первого сумматора объединена с первой группой информационных входов второго сумматора и подключена к группе разрядных выходов N-го регистра, вторая группа информационных входов второго сумматора подключена к группе разрядных выходов К-го регистра, группа информационных выходов второго сумматора подключена к группе информационных входов (К + 1)-го регистра, входы переноса первого и второго сумматоров образуют первый и второй входы наращивания разрядности устройства соответственно, выходы переноса первого и второго сумматоров образуют первый и второй выходы наращивания разрядности устройства соответственно.