Розкладення функції в ряд Ріда-Малера

Теоретичною основою вибору елементної бази при реалізації функції F(X1,X2,…,Xn) є подання її у вигляді розкладення Ріда-Малера. Приклад такої функції—F(X1,X2,X3), що залежить від 3-х змінних:

F(X1,X2,X3)=С0ÅС1X1ÅC2X2ÅC3X3ÅC4X1X2ÅC5X1X3ÅC6X2X3ÅC7X1X2X3,

де С0=F(0,0,0),

С1=F(0,0,0)ÅF(1,0,0),

С2=F(0,0,0)ÅF(0,1,0),

С3=F(0,0,0)ÅF(0,0,1),

С4=F(0,0,0)ÅF(1,0,0)ÅF(0,1,0)ÅF(1,1,0),

С5=F(0,0,0)ÅF(1,0,0)ÅF(0,0,1)ÅF(1,0,1),

С6=F(0,0,0)ÅF(0,0,1)ÅF(0,1,0)ÅF(0,1,1),

С7=F(0,0,0)ÅF(1,0,0)ÅF(0,1,0)ÅF(0,1,1)ÅF(1,1,0)ÅF(0,1,1)ÅF(1,0,1)ÅF(1,1,1).

Функція F(X1,X2,X3)=X1X2+X1X3+X2X3, подана у вигляді розкладення Ріда-Малера, є такою:

F(X1,X2,X3)=1ÅX2ÅX1X2ÅX1X3ÅX2X3.

Схемотехнічну реалізацію даної функції подано на рис.1.

 

 

Рис.1.

Цифрові схеми, синтезовані відповідно розкладенню Ріда-Малера, характеризуються наступними властивостями.

1. Для схеми, що реалізує функцію F(X1,X2,…,Xn), вхідні полюси якої не містять несправностей, при виявленні усіх одиночних несправностей достатньо не більше, ніж n+4 тестових наборів.

2. У випадку виявлення несправностей на усіх полюсах схеми тестова послідовність буде містити (n+4)+ne наборів, де ne—число вхідних змінних, що входять до розкладення Ріда-Малера парну кількість раз. Для даного приклада ne=2, тому що змінні Х1 та Х3 входять до розкладення функції по 2 рази.

Для виявлення одиночної несправності у послідовно з’єднаних елементах М2 необхідно подати послідовності таким чином, щоб кожен єлемент М2 був перевірений для усіх можливих комбінацій. Для розглянутого приклада такою вхідною послідовністю буде:

Z X1 X2 X3

0 0 0 0

0 1 1 1

1 0 0 0

1 1 1 1

У такому випадку структура вхідної послідовності не залежить від числа n змінних й містить тільки 4 тестових наборів. Так, для функції 5-ти змінних подвбна послідовність має вигляд:

Z X1 X2 X3 Х4 Х5

0 0 0 0 0 0

0 1 1 1 1 1

1 0 0 0 0 0

1 1 1 1 1 1

Окрім 4-х тестових наборів, що використовуються для виявлення несправностей елементів М2, необхідно використати n наборів для елементів І у випадку ne=0. Об’єднання двох множин наборів дає повну тестову послідовність.

Головний недолік розглянутого метода – зростання складності реалізаціїсхеми, а також її глибини (кількості рівней) , що впливає на технічні характеристики.