ПОЛИНОМИАЛЬНЫЙ МОДУЛЯРНЫЙ ВЫЧИСЛИТЕЛЬ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ С ОБНАРУЖЕНИЕМ ОШИБОК

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

Известен самопроверяемый модулярный вычислитель систем логических функций [1], содержащий блок конъюнкций, входы которого являются входами устройства для подачи n булевых переменных, выходы которого подключены к первому блоку памяти, предназначенному для хранения коэффициентов первого полинома избыточной модулярной числовой нормальной формы, первый сумматор, второй блок памяти, входы которого соединены с выходами блока конъюнкций, при этом второй блок памяти предназначен для хранения коэффициентов второго полинома избыточной модулярной числовой нормальной формы, выходы первого блока памяти подключены к входам первого сумматора, выходы которого подключены к (s+1)-му, (s+2)-му, …, (d+s)-му входам (d - количество реализуемых булевых функций, составляющих информационные разряды разделимого AN-кода, s - количество избыточных булевых функций, соответствующих избыточным разрядам разделимого AN-кода) блока вычисления остатка по модулю и информационным входам регистра памяти, выходы которого являются выходами устройства выдачи значений d булевых функций, выходы второго блока памяти подключены к входам второго сумматора, выходы которого подключены к 1-му, 2-му, …, s-му входам блока вычисления остатка по модулю, выходы которого подключены к входам логического элемента ИЛИ-НЕ, выход которого подключен к первому входу элемента И, второй вход которого соединен с входом подачи синхроимпульсов устройства, а выход подключен к синхровходу регистра памяти.

Наиболее близкое по сущности технического решения заявленному устройству является самопроверяемый специализированный вычислитель систем булевых функций [2], содержащий блоки памяти, предназначенные для хранения коэффициентов полиномов избыточной числовой нормальной формы, входы которых являются входами устройства, к которым подключена шина подачи n булевых переменных, выходы которых соединены со входами многоместных сумматоров, выходы которых соединены с информационными входами многоканальных мультиплексоров, выходы первого мультиплексора подключены к (s+1)-му, (s+2)-му, …, (d+s)-му входам (d - количество реализуемых булевых функций, составляющие информационные разряды разделенного AN-кода, s - количество избыточных булевых функций, соответствующих избыточным разрядам разделенного AN-кода) блока вычисления остатка по модулю и информационным входам регистра памяти, выходы которого являются выходами устройства выдачи значений d булевых функций, выходы второго мультиплексора подключены к 1-му, 2-му, …, s-му входам блока вычисления остатка по модулю, выходы которого подключены к входам элемента ИЛИ-НЕ, выход которого подключен к первому входу элемента И, второй вход которого подключен к входу подачи синхроимпульсов устройства, а выход подключен к синхровходу регистра памяти, шина подачи коэффициентов полиномов избыточной числовой нормальной формы, подключенная к входам блоков памяти, многоканальные мультиплексоры выделения информационных разрядов реализуемых и избыточных булевых функций, блок памяти хранения адресов информационных разрядов, к входу которого подключена шина адреса, выходы которого подключены к адресным входам мультиплексоров.

Недостаток - низкая достоверность функционирования устройства.

Цель - повышение достоверности функционирования устройства.

Поставленная цель достигается тем, что в полиномиальный модулярный вычислитель систем булевых функций с обнаружением ошибок вычислений, содержащий блоки памяти хранения значений коэффициентов информационного полинома, управляющие входы которых подключены к управляющим входам устройства подачи значений коэффициентов информационного полинома, многоканальный мультиплексор, управляющий вход которого подключен к управляющему вход устройства подачи значения аддитивной переменной Х, устройство вычисления остатка по модулю Р, многовходовый логический элемент ИЛИ-НЕ, выход которого подключен к первому входу двухвходового логического элемента И, второй вход которого подключен к управляющему входу устройства подачи синхроимпульсов, выход которого подключен к управляющему входу регистра памяти, выходы которого являются выходами устройства выдачи значений булевых функций, введены 2ⁿ блоков памяти хранения значений вычетов аддитивной переменной X по модулю Р, управляющие входы которых подключены к управляющему входу устройства подачи значений вычетов аддитивной переменной X по модулю Р, а выходы подключены к информационным входам многоканального мультиплексора, 2^k блоков памяти хранения значений коэффициентов контрольного полинома, управляющие входы которых подключены к управляющему входу устройства подачи значений коэффициентов контрольного полинома, 2^k-1 блоков памяти хранения значений коэффициентов полинома-остатка, управляющие входы которых подключены к управляющему входу устройства подачи значений коэффициентов полинома-остатка, 2ⁿ умножителей по модулю Ρ информационного полинома, 1-е входы которых подключены к выходам многоканального мультиплексора, а 2-е входы подключены к выходам блоков памяти хранения значений коэффициентов информационного полинома, 2^k умножителей по модулю Ρ контрольного полинома, 1-е входы которых подключены к выходам многоканального мультиплексора, а 2-е входы подключены к выходам блоков памяти хранения значений коэффициентов контрольного полинома, 2^k-1 умножителей по модулю Ρ полинома-остатка, 1-е входы которых подключены к выходам многоканального мультиплексора, а 2-е входы подключены к выходам блоков памяти хранения значений коэффициентов полинома-остатка, 3-й многовходовых сумматора по модулю Р, где входы 1-го сумматора подключены к выходам умножителей по модулю Ρ информационного полинома, а выходы подключены к 1-й группе входов устройства вычисления остатка по модулю Ρ и к входам регистра памяти, входы 2-го сумматора подключены к выходам умножителей по модулю Ρ контрольного полинома, а выходы подключены к 2-й группе входов устройства вычисления остатка по модулю Р, входы 3-го сумматора подключены к выходам умножителей по модулю Ρ полинома-остатка, s двухвходовых логических элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 1-е входы которых подключены к выходам устройства вычисления остатка по модулю Р, а 2-е входы подключены к выходам 3-го многовходового сумматора по модулю Р.

Для представления системы булевых функций (СБФ) ƒ₁, …, ƒ_d интерполяционным полиномом интерпретируем значения наборов переменных СБФ и значения функций на этих наборах как записи чисел в двоичной системе счисления и затем в десятичной:

В результате данной интерпретации получим функцию F(X), область значения и область определения которой {0, 1, …, 2ⁿ-1}.

Значения аргумента X являются равноудаленными узлами интерполирования, что обеспечивает возможность применения различных способов интерполяции к интерпретированной форме записи СБФ.

Воспользуемся методом интерполяции Лагранжа для представления F(X) степенным полиномом:

или

где a_i - коэффициенты полинома, полученные после выполнения численных операций (i=0, 1, …, 2ⁿ-1).

Известно [3], что

где Ρ - простое число,

φ(P) - функция Эйлера.

Тогда (1) примет вид:

где b_i≡a_i (modΡ), i=0, 1, …, s-1;

Ρ - простое число, Ρ>s.

Пример 1. Пример представления системы булевых функций модулярным интерполяционным полиномом, заданной таблицей истинности:

Построим методом Лагранжа интерполяционный полином вида:

.

Используя свойство (2), полученный интерполяционный полином в модулярной форме примет вид:

Вычисление полинома.

Пусть X=6, то есть х₁=1, х₂=1, х₃=0, тогда

H(Х)=7+8·6+5·6²+4·6³+6⁴+6·6⁶+9·6⁷ (mod 11)=2848411 (mod 11)=5 (mod 11)=(101)₂ (mod 11),

где соответственно старший разряд двоичного представления результата вычисления полинома соответствует ƒ₁=1, ƒ₂=0, ƒ₃=1.

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

Пусть полином (2) является информационным полиномом:

тогда

контрольный полином, соответствующий системе булевых функций, существенно зависимой от k переменных, и соответственно полином-остаток:

Пример 2. Рассмотрим построение контрольного полинома и получение полинома-остатка, для интерполяционного модулярного полинома (4), введем ошибку в вычисление информационного полинома:

К(Х)=4+Х+Х³ (mod 11),

соответствующий системе булевых функций:

тогда полином-остаток примет вид:

R(X)=7+7Х+5Х² (mod 11).

Вычисление значения полинома с контролем ошибок. Пусть ошибка произошла при записи коэффициентов (коэффициент при X⁴ равен 5) информационного полинома, X=6, тогда:

K(Х)=4+6+6³ (mod 11)=6 (mod 11),

,

R(X)=7+7·6+5·6² (mod 11)=6 (mod 11),

в результате чего - ОШИБКА.

Структурная схема предлагаемого устройства представлена на фиг. 1, которое содержит 1.1, …, 1.2ⁿ - блоки памяти хранения значений вычетов аддитивной переменной X по модулю Р, 2.1, …, 2.2ⁿ - блоки памяти хранения значений коэффициентов информационного полинома; 3.1, …, 2.2^k - блоки памяти хранения значений коэффициентов контрольного полинома; 4.1, …, 4.2^k-1 - блоки памяти хранения значений коэффициентов полинома-остатка; 5 - многоканальный мультиплексор; 6.1, …, 6.2ⁿ - умножители по модулю Ρ [4] информационного полинома; 7.1, …, 7.2^k - умножители по модулю Ρ контрольного полинома; 8.1, …, 8.2^k-1 - умножители по модулю Ρ полинома-остатка; 9.1, …, 9.3 - многовходовые сумматоры по модулю Ρ [5]; 10 - устройство вычисления остатка по модулю Ρ [6]; 11.1…11.s - двухвходовые логические элементы ИСКЛЮЧАЮЩЕЕ ИЛИ; 12 - многовходовый логический элемент ИЛИ-НЕТ; 13 - регистр памяти; 14 - двухвходовый логический элемент И; 15 - управляющий вход устройства подачи значений коэффициентов полинома-остатка; 16 - управляющий вход устройства подачи значений коэффициентов контрольного полинома; 17 - управляющий вход устройства подачи значений коэффициентов информационного полинома; 18 - управляющий вход устройства подачи значений вычетов аддитивной переменной X по модулю Р; 19 - управляющий вход устройства подачи значения аддитивной переменной X; 20 - управляющий вход устройства подачи синхроимпульсов; 21.1, …, 21.d - выходы устройства выдачи значений булевых функций.

Управляющий вход устройства подачи значений вычетов аддитивной переменной X по модулю Ρ 18 является управляющим входом блоков памяти хранения значений вычетов аддитивной переменной X по модулю Ρ 1.1, …, 1.2ⁿ, управляющий вход устройства подачи значений коэффициентов информационного полинома 17 является управляющим входом блоков памяти хранения значений коэффициентов информационного полинома 2.1, …, 2.2ⁿ, управляющий вход устройства подачи значений коэффициентов контрольного полинома 16 является управляющим входом блоков памяти хранения значений коэффициентов контрольного полинома 3.1, …, 3.2^k, управляющий вход устройства подачи значений коэффициентов полинома-остатка 15 является управляющим входом блоков памяти хранения значений коэффициентов полинома-остатка 4.1, …, 4.2^k-1, управляющий вход устройства подачи значения аддитивной переменной X 19 является управляющим входом многоканального мультиплексора 5, входы которого подключены к выходам блоков памяти хранения значений вычетов аддитивной переменной X по модулю Ρ 1.1, …, 1.2ⁿ, где 1-й вход многоканального мультиплексора подключен к выходу блока памяти 1.1, и так далее, и 2ⁿ-й вход многоканального мультиплексора подключен к выходу блока памяти 1.2ⁿ, умножители по модулю Ρ информационного полинома 6.1, …, 6.2ⁿ, 1-е входы которых подключены к выходам многоканального мультиплексора 5, где 1-й вход умножителя 6.1 подключен к 1-му выходу многоканального мультиплексора 5, и так далее, и 1-й вход умножителя 6.2ⁿ подключен к 2ⁿ-му выходу многоканального мультиплексора 5, а 2-е входы подключены к выходам блоков памяти 2.1, …, 2.2ⁿ, где 2-й вход умножителя 6.1 подключен к выходу бока памяти 2.1, и так далее, и 2-й вход умножителя 6.2ⁿ подключен к выходу бока памяти 2.2ⁿ, умножители по модулю Ρ контрольного полинома 7.1, …, 7.2^k, 1-е входы которых подключены к выходам многоканального мультиплексора 5, где 1-й вход умножителя 7.1 подключен к 1-му выходу многоканального мультиплексора 5, и так далее, и 1-й вход умножителя 7.2^k подключен к 2^k-му выходу многоканального мультиплексора 5, а 2-е входы подключены к выходам блоков памяти 3.1, …, 3.2^k, где 2-й вход умножителя 7.1 подключен к выходу бока памяти 3.1, и так далее, и 2-й вход умножителя 7.2^k подключен к выходу бока памяти 3.2^k, умножители по модулю Ρ полинома-остатка 8.1, …, 8.2^k-1, 1-е входы которых подключены к выходам многоканального мультиплексора 5, где 1-й вход умножителя 8.1 подключен к 1-му выходу многоканального мультиплексора 5, и так далее, и 1-й вход умножителя 8.2^k-1 подключен к 2^k-1-му выходу многоканального мультиплексора 5, а 2-е входы подключены к выходам блоков памяти 4.1, …, 4.2^k-1, где 2-й вход умножителя 8.1 подключен к выходу бока памяти 4.1, и так далее, и 2-й вход умножителя 8.2^k-1 подключен к выходу бока памяти 4.2^k-1, многовходовые сумматоры по модулю Ρ 9.1, …, 9.3, где входы сумматора 9.1 подключены к выходам умножителей по модулю Ρ информационного полинома 6.1, …, 6.2ⁿ, а выходы с 1-го по d-й подключены соответственно к входам с 1-го по d-й 2-й группы входов устройства вычисления остатка по модулю Ρ 10 и подключены соответственно к входам с 1-го по d-й регистра памяти 13, входы сумматора 9.2 подключены к выходам умножителей по модулю Ρ контрольного полинома 7.1, …, 7.2^k, а выходы с 1 по t-й подключены соответственно к входам с 1-го по t-й 2-й группы входов устройства вычисления остатка по модулю Ρ 10, входы сумматора 9.3 подключены к выходам умножителей по модулю Ρ полинома-остатка 8.1, …, 8.2^k-1, а выходы с 1-го по s-й подключены соответственно к 2-м входам логических элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 11.1, …, 11.s, первые входы которых подключены соответственно к выходам с 1-го по s-й устройства вычисления остатка по модулю Ρ 10, а выходы подключены соответственно к входам с 1-го по s-й многовходового логического элемента ИЛИ-НЕ 12, выход которого подключен к первому входу логического элемента И 14, 2-й вход которого подключен к управляющему входу устройства подачи синхроимпульсов, а выход подключен к управляющему входу регистра памяти 13, выходы которого являются выходами устройства выдачи значений булевых функций. 21.1, …, 21.d.

Работа полиномиального модулярного вычислителя систем булевых функций с обнаружением ошибок осуществляется следующим образом. В исходном состоянии с помощью управляющего сигнала, поступающего с управляющего входа устройства подачи значений вычетов аддитивной переменной X по модулю Ρ 18 на управляющие входы блоков памяти хранения значений вычетов аддитивной переменной X по модулю Ρ 1.1, …, 1.2ⁿ, осуществляется запись предвычисленных значений переменной X по модулю Ρ: , , …, (Χ=0, 1, …, Ρ-1), которые затем поступают на входы многоканального мультиплексора 5. С помощью управляющего сигнала, поступающего с управляющего входа устройства подачи значений коэффициентов информационного полинома 17 на управляющие входы блоков памяти хранения значений коэффициентов информационного полинома 2.1, …, 2.2ⁿ, осуществляется запись коэффициентов информационного полинома , которые затем поступают на вторые входы умножителей по модулю Ρ информационного полинома 6.1, …, 6.2ⁿ, где b₀ поступает на вход умножителя 6.1, и так далее, и поступает на вход умножителя 6.2ⁿ. С помощью управляющего сигнала, поступающего с управляющего входа устройства подачи значений коэффициентов контрольного полинома 16 на управляющие входы блоков памяти хранения значений коэффициентов контрольного полинома 3.1, …, 3.2^k, осуществляется запись коэффициентов контрольного полинома , которые затем поступают на вторые входы умножителей по модулю Ρ контрольного полинома 7.1, …, 7.2^k, где с₀ поступает на вход умножителя 7.1, и так далее, и поступает на вход умножителя 7.2ⁿ. С помощью управляющего сигнала, поступающего с управляющего входа устройства подачи значений коэффициентов полинома-остатка 15, осуществляется запись коэффициентов полинома-остатка , которые затем поступают на вторые входы умножителей по модулю Ρ контрольного полинома 8.1, …, 8.2^k-1, где r₀ поступает на вход умножителя 8.1, и так далее, и поступает на вход умножителя 8.2^k-1. В момент времени, соответствующий началу преобразования, с помощью управляющего сигнала, поступающего с управляющего входа устройства подачи значения аддитивной переменной X 19 на управляющий вход многоканального мультиплексора 5, осуществляется выбор группы вычетов аддитивной переменной X по модулю Р, где значению аддитивной переменной Х=0 соответствует группа вычетов , , …, 0⁰ (mod Ρ), и так далее, и значению переменной Х=2ⁿ-1 соответствует группа вычетов , , … (2ⁿ-1)⁰ (mod Ρ), которые поступают соответственно на 1-е входы умножителей 6.1, …, 6.2ⁿ, 7.1, …, 7.2^k, 8.1, …, 8.2^k-1, где выполняется операция умножения коэффициентов на соответствующие им степени переменных по модулю Ρ (5-7). В следующий момент времени полученные произведения коэффициентов на степени переменных поступают на входы сумматоров 91, …, 9.3, в которых выполняется вычисление полиномов, соответственно в сумматоре 9.1 - вычисление полинома (5), в сумматоре 9.2 - вычисление полинома (6), и в сумматоре 9.3 - вычисление полинома (7). Из сумматора 9.3 значение вычисления информационного полинома поступает на входы 1-й группы входов устройства вычисления остатка по модулю Ρ 10, из сумматора 9.2 значение вычисления контрольного полинома поступает на входы 2-й группы входов устройства вычисления остатка по модулю Ρ 10, которое обеспечивает вычисление остатка от деления полинома (5) на полином (6) по модулю Р, далее полученный остаток поразрядно подается на 1-е входы двухвходовых логических элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 11.1, …, 11.s, а из сумматора 9.3 результат вычисления полинома-остатка (7) поразрядно подается на 2-е входы двухвходовых логических элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 11.1, …, 11.s, где соответствующие двоичные разряды результатов вычисления остатка от деления полинома (5) на (6) и полинома (7) суммируются по модулю 2 (если значения вычисления полинома остатка (7) и значение вычисления, полученное устройством получения остатка, по модулю Ρ 10 совпадают, то на выходе каждого логического элемента ИСКЛЮЧАЮЩЕЕ ИЛИ будет логический 0, в обратном случае (если ОШИБКА) будет хотя бы одно значение логической 1) и подаются на входы логического элемента ИЛИ-НЕ, где в случае ОШИБКИ на выходе будет логический 0, обеспечивающий запрет записи результата вычисления информационного полинома, подаваемого из сумматора 9.1 на входы регистра памяти 13, путем логического умножения на значение синхроимпульса, подаваемого с управляющего входа устройства подачи синхроимпульсов 20 на второй вход логического элемента И 14, и соответственно в случае отсутствия ошибки будет логическая 1. В случае записи результата вычисления полинома (7) в регистр памяти 13 значения вычисления булевых функций ƒ₁, …, ƒ_d подаются соответственно на выходы устройства выдачи значений булевых функций 21.1, …, 21.d.

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

Литература

1. RU, №2417405, 2010.

2. RU, №2485575, 2013.

3. Финько О.А. Модулярная арифметика параллельных логических вычислений: Монография / Финько О.А.; Под ред. В.Д. Малюгина. - М.: Ин-т проблем управления им. В.А. Трапезникова РАН; Краснодар: Краснодарский воен. ин-т, 2003. - С 103-104. http://elibrary.ru/item.asp?id=23447304

4. RU, №1820377, 1993.

5. RU, №2299461, 2007.

6. RU, №2421781, 2011.