УСТРОЙСТВО ФОРМИРОВАНИЯ ТРИПЛЕКСНЫХ ЧИСЕЛ Российский патент 2024 года по МПК G06F7/49 G06F7/57 

Область техники, к которой относится изобретение

Изобретение относится к вычислительной технике и может быть использовано для повышения эффективности средств электронной вычислительной техники (таких характеристик как производительность, надежность, объем памяти и др.).

Уровень техники

а) Описание аналогов

Известно, что для построения псевдослучайной последовательности длины n=2^r-1 необходим примитивный многочлен V(z) степени r.

Для примера рассмотрим многочлен

где r=4. Многочлену (1) соответствует регистр сдвига с обратной связью, ([MacWilliams F., Sloane N. Pseudo-random sequences and arrays, Proc. IEEE, 64, pp. 1715-1729, 1976; Lidl R., Niederreiter H. Introduction to finite fields and their applications, Cambridge: Cambridge Univ. Press, 1987]), представленный на фигуре 1.

Регистр сдвига состоит из r ячеек (запоминающих элементов, триггеров), каждая из которых в процессе работы устройства может содержать 0 или 1. В момент времени t (момент времени определяется некоторой тактовой частотой) содержимое всех ячеек сдвигается на одну ячейку (перемещается на один разряд) вправо. Здесь содержимое ячеек, соответствующих членам многочлена V(z), суммируется и поступает в крайнюю левую ячейку. Сумма вычисляется по модулю 2 и реализуется сумматором по модулю 2, (логическим элементом «ИСКЛЮЧАЮЩЕЕ ИЛИ»), выход которого определен условиями

В качестве примера рассмотрим регистр сдвига с обратной связью (фиг. 1), который в момент времени t содержит числа

соответственно в момент времени t+1 в нем будут находится числа (фиг. 2)

Таким образом, регистр сдвига с обратной связью генерирует бесконечную последовательность а₀, а₁, а₂, …, a_t, …, удовлетворяющую рекурсивному соотношению

где t=0, 1, …,; знак «+» - сложение по модулю 2. Для запуска процесса функционирования регистра сдвига с обратной связью необходимо задать начальное заполнение а₀, а₁, а₂, …, a_r-1. Однако недостатком данного устройства является отсутствие возможности реализации вычислений, при которых осуществляется формирование триплексных чисел.

б) Описание ближайшего аналога(прототипа)

Наиболее близким по своей технической сущности к заявленному техническому решению и принятым за прототип является устройство, описанное в [М.А. Ivanov, B.V. Kliuchnikova, Е.А. Salikov, A.V. Starikovskii. New class of non-binary pseudorandom number generators. - Proceeding of Intelligent Technologies in Robotics, Moscow, Russia, 2019, pp. 255-262; Патент РФ №2740339 публ. 13.01.2021].

Рассматриваемое устройство получения псевдослучайных последовательностей (генератор псевдослучайных чисел, функционирующий в конечном поле GF(q), где q - простое число), состоящий из r регистров разрядности ([log₂q]), r-1 блоков сложения в GF(q), r блоков умножения в GF(q), причем величина, на которую происходит умножение в (i+1)-M блоке умножения, равна коэффициенту ρ_i∈GF(q), характеристического многочлена

где i=0, 1, 2, …, r-1, P(z) - многочлен степени г, примитивный над GF(q), в котором выходы г-го регистра соединены со входами всех блоков умножение, выходы j-x блоков умножения соединены с первыми входами j-x регистров, где j=0, 1, 2, …, r, вторые входы всех блоков сложения образуют r групп управляющих входов генератора, выходы k-х регистров соединены с третьими входами (k+1)-х блоков сложения, выходы которых соединены со входами (j+1)-x регистров, где k=0,1, 2, …, r.

Структурная схема устройства-прототипа представлена на фиг. 3 для случая r=3,

где ρ_i∈GF(q), здесь 1 - тактовый вход генератора, 2.1, 2.2, 2.3 - [log₂q] - разрядные регистры, 3.1 и 3.2 - блоки сложения в поле GF(q), 4.1, 4.2 и 4.3 - блоки умножения на ρ₀, ρ₁ и ρ₂ в поле GF(q).

Недостаток известного устройства - отсутствие возможности реализации вычислений, при которых осуществляется формирование триплексных чисел.

Раскрытие изобретения

а) Технический результат, на достижение которого направлено изобретение

Целью заявляемого технического решения является реализация процесса вычисления триплексных чисел.

б) Совокупность существенных признаков

Технический результат изобретения достигается тем, что:

Поставленная цель достигается тем, что в устройство формирования триплексных чисел, состоящее из r регистров разрядности ([log₂q]), r-1 блоков сложения в GF(q), r блоков умножения в GF(q), причем величина, на которую происходит умножение в (i+1)-M блоке умножения, равна коэффициенту ρ_i∈GF(q), характеристического многочлена

где i=0, 1, 2, …, r-1, P{z) - многочлен степени г, примитивный над GF(q), в котором выходы r-го регистра соединены со входами всех блоков умножения, выходы j-x блоков умножения соединены с первыми входами j-x блоков сложения, выходы которых соединены со входами j-x регистров, где j=0, 1, 2, …, r, вторые выходы всех блоков сложения образуют r группу управляющих выходов генератора, выходы k-х регистров соединены с третьими входами (k+1)-х блоков сложения, выходы которых соединены со входами (j+1)-x регистров, где k=1, 2, …, r, введены генератор псевдослучайных чисел, функционирующих в конечном поле GF(q), где q - простое число, состоящее из r регистров разрядности ([log₂ q]), r-1 блоков сложения в GF(q), r блоков умножения в GF(q), причем величина, на которую происходит умножение в (i+1)-M блоке умножения, равна коэффициенту ρ_i∈GF(q), характеристического многочлена

где i=0,1, 2, …, r-1, G(z) - многочлена степени г, примитивный над GF(q), в котором выходы г-го регистра соединены со входами всех блоков умножения, выходы j-x блоков умножения соединены с первыми входами j-x блоков сложения, выходы которых соединены со входами j-x регистров, где j=0, 1, 2, …, r, вторые выходы всех блоков сложения образуют r группу образующих входов генератора, выходы k-х регистров соединены со входами (j+1)-x регистров, где k=1, 2, …, r; генератор псевдослучайных чисел, функционирующих в конечном поле GF(q), где q-простое число, состоящее из r регистров разрядности ([log₂q]), r-1 блоков сложения в GF(q), r блоков умножения в GF(q), причем величина, на которую происходит умножение в (i+1)-M блоке умножения, равна коэффициенту l_i∈GF(q), характеристического многочлена

где i=0, 1, 2, …, r-1, L(z) - многочлена степени г, примитивный над GF(q), в котором выходы г-го регистра соединены со входами всех блоков умножения, выходы j-x блоков умножения соединены с первыми входами j-x блоков сложения, выходы которых соединены со входами j-x регистров, где j=0, 1, 2, …, r, вторые выходы всех блоков сложения образуют r группу образующих входов генератора, выходы k-х регистров соединены со входами (j+1)-x регистров, где k=1, 2, …. r, блок формирования триплексного числа, содержащий первый блок умножения на мнимую единицу «i», второй блок умножения на мнимую единицу «j», третий блок умножения на мнимую единицу «k», блок сложения, причем выходы первого, второго и третьего генераторов псевдослучайных последовательностей подключены соответственно к первому, второму и третьему входам блоков формирования триплексного числа; первый вход блока умножения на мнимую единицу «j», выход которого подключен к первому входу блока сложения; второй вход блока умножения на мнимую единицу «k», выход которого подключен к второму входу блока сложения; третий вход блока умножения на мнимую единицу «к», выход которого подключен к третьему входу блока сложения; выход блока сложения является выходом блока формирования триплексного числа, выдающего значения

в) Причинно-следственная связь между признаками и техническим результатом

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

Доказательства соответствия заявленного изобретения условиям патентоспособности «новизна» и «изобретательский уровень»

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

Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта показали, что они не следуют явными из уровня техники. Из уровня техники также не выявлена известность отличительных существенных признаков, обуславливающих тот же технический результат, который достигнут в заявленном способе. Следовательно, заявленное изобретение соответствует уровню патентоспособности «изобретательский уровень».

Краткое описание чертежей

Заявленное устройство поясняется чертежами, на которых показано:

- на фиг. 1 - структурная схема регистра сдвига с обратной связью, соответствующего многочлена (1);

- на фиг. 2 - структурная схема регистра сдвига с обратной связью, определяющего рекурсивное соотношение;

- на фиг. 3 - структурная схема устройства прототипа;

- на фиг. 4 - структурная схема предлагаемого устройства;

- на фиг. 5 - схема блока формирования триплексного числа.

Осуществление изобретения

Предлагаемое устройство содержит первый генератор псевдослучайных чисел над GF(q) (регистр сдвига с обратной связью, q-PPC), второй генератор псевдослучайных чисел над GF(q), третий генератор псевдослучайных чисел над GF(q), блок формирования триплексного числа, включающий блок умножения на мнимую единицу «i», блок умножения на мнимую единицу «j», блок умножения на мнимую единицу «k», блок сложения.

Первый q-PPC построен на основе примитивного, неприводимого (характеристического) многочлена (2), где ρ_i∈GF(q), и включает 1.1 - тактовый вход генератора, 1.2.1, 1.2.2, …, 1.2.r - ([log₂q]) - разрядные регистры, 1.3.1, 1.3.2, …, 1.3.r - блоки сложения в поле GF(q), 1.4.1, 1.4.2, …, 1.4.r - соответственно блоки умножения на ρ₀, ρ₁, …, ρ_r-1 в поле GF(q), второй q-PPC построен на основе примитивного, неприводимого (характеристического) многочлена (3), где ρ_i∈GF(q), и включает 2.1 -тактовый вход генератора, 2.2.1, 2.2.2, …, 2.2.r - ([log₂q]) - разрядные регистры, 2.3.1, 2.3.2, …, 2.3.r блоки сложения в поле GF(q), 2.4.1, 2.4.2, …, 2.4.г - соответственно блоки умножения на ρ₀, ρ₁, …, ρ_r-1 в поле GF(q), третий q-PPC построен на основе примитивного, неприводимого (характеристического) многочлена (4), где l_i∈GF(q), и включает 3.1 - тактовый вход генератора, 3.2.1, 3.2.2, …, 3.2.r - ([log₂q])- разрядные регистры, 3.3.1, 3.3.2, …, 3.3.r-блоки сложения в поле GF(q), 3.4.1, 3.4.2, …, 3.4.r - соответственно блоки умножения на l₀, l₁, …, l_r-1 в поле GF(q); блок 4 формирования триплексного числа (фиг. 5), содержащий первый блок 4.1 умножения на мнимую единицу «i», второй блок 4.2 умножения на мнимую единицу «j», третий блок 4.3 умножения на мнимую единицу «k», блок 4.4 сложения, причем выходы первого, второго и третьего генераторов псевдослучайных последовательностей подключены соответственно к первому, второму и третьему входам блоков формирования 4.1, 4.2, 4.3 триплексного числа; первый вход блока 4.1 умножения на мнимую единицу «i», выход которого подключен к первому входу блока 4.4 сложения; второй вход блока 4.2 умножения на мнимую единицу «j», выход которого подключен к второму входу блока 4.4 сложения; третий вход блока 4.3 умножения на мнимую единицу «к», выход которого подключен к третьему входу блока 4.4 сложения; выход блока сложения является выходом блока 4 формирования триплексного числа, выдающего значения

Рассмотри алгоритм работы устройства.

Построение первого q-PPC осуществляется по заданному примитивному, неприводимому (характеристическому) многочлену (2), и построенному в соответствии с ним однородному рекуррентному уравнению:

или

где n=0, 1, 2, …; - символ сложения по mod q.

В общем случае после первого такта работы первый q - РРС содержит заполнение: . В целом q-PPC генерирует бесконечную выходную q-значную последовательность с периодом q^r-1 (при ненулевом исходном состоянии), причем каждое ненулевое состояние появляется один раз в период. Сформированный сегмент выходной последовательности длины q^r-1 является псевдослучайной последовательностью (ПСП) над GF(q).

В терминах линейной алгебры очередной элемент ПСП получаемый с помощью (5) вычисляется в соответствии с выражением

где Т - символ транспонирования.

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

примитивному, непримитивному (характеристическому) многочлену (3), и построенному в соответствии с ним однородному рекуррентному уравнению:

или

где n=0, 1, 2, …; - символ сложения по mod q.

После первого такта работы второй q - PPC содержит заполнение При этом второй q-PPC генерирует бесконечную выходную q -значную последовательность с периодом q^r-1 (при ненулевом исходном состоянии), причем каждое ненулевое состояние появляется один раз в период. Сформированный сегмент выходной последовательности длины q^r-1 является псевдослучайной последовательностью (ПСП) над GF(q).

В терминах линейной алгебры очередной элемент ПСП полученный с помощью (6) также может быть получен в соответствии с выражением:

где Т - символ транспонирования.

Построение третьего q-PPC осуществляется также по заданному примитивному, непримитивному (характеристическому) многочлену (4), и построенному в соответствии с ним однородному рекуррентному уравнению:

или

где n=0, 1, 2, …; - символ сложения по mod q.

После первого такта работы второй q-PPC содержит заполнение При этом третий q-PPC генерирует бесконечную выходную g-значную последовательность с периодом q^r-1 (при ненулевом исходном состоянии), причем каждое ненулевое состояние появляется один раз в период. Сформированный сегмент выходной последовательности длины q^r-1 является псевдослучайной последовательностью (ПСП) над GF(q).

В терминах линейной алгебры очередной элемент ПСП полученный с помощью (7) также может быть получен в соответствии с выражением:

где Т - символ транспонирования.

Последовательность с выхода первого q - РРС поступают на первый вход блока 4 формирования триплексных чисел (фиг. 5), в частности на первый вход блока 4.1 умножения на мнимую единицу поступает на первый вход блока 4.4 сложения. Последовательность с выхода второго q-PPC поступает на второй вход блока 4.2 умножения на мнимую единицу «j», последовательность поступает на второй вход блока 4.4 сложения. Последовательность с выхода третьего q - РРС поступает на третий вход блока 4.3 умножения на мнимую единицу «А» последовательность поступает на третий вход блока 4.4 сложения. В блоке 4.4 сложения осуществляется окончательное формирование триплексного числа

На фиг. 4 показана схема предлагаемого устройства для случая r=3, первый q-PPC построен на основе где р_i∈GF(q), и включает 1.1 - тактовый вход генератора, 1.2.1, 1.2.2 и 1.2.3 -[log2 q] - разрядные регистры, 1.3.1 и 1.3.2 - блоки сложения в поле GF(q), 1.4.1, 1.4.2 и 1.4.3 - соответственно блоки умножения на ρ₀, ρ₁ и ρ₂ в поле GF(q), второй q - РРС построен на основе где р_i∈GF(q), и включает 2.1 - тактовый вход генератора, 2.2.1, 2.2.2 и 2.2.3 -[log2 q] - разрядные регистры, 2.3.1 и 2.3.2 - блоки сложения в поле GF(q), 2.4.1, 2.4.2 и 2.4.3 - соответственно блоки умножения на ρ₀, ρ₁ и ρ₂ в поле GF(q), третий q-PPC построен на основе где и включает 3.1 - тактовый вход генератора, 3.2.1, 3.2.2 и 3.2.3 - [log₂ q] - разрядные регистры, 3.3.1 и 3.3.2 - блоки сложения в поле GF(q), 3.4.1, 3.4.2 и 3.4.3 - соответственно блоки умножения на в поле GF(q), блок 4 формирования триплексного числа (фиг. 5), содержащий первый блок 4.1 умножения на мнимую единицу «i», второй блок 4.2 умножения на мнимую единицу «j», третий блок 4.3 умножения на мнимую единицу «к», блок 4.4 сложения, причем выходы первого, второго и третьего генераторов псевдослучайных последовательностей подключены соответственно к первому, второму и третьему входам блоков 4.1, 4.2, 4.3 формирования триплексного числа; первый вход блока 4.1 умножения на мнимую единицу «i», выход которого подключен к первому входу блока 4.4 сложения; второй вход блока 4.2 умножения на мнимую единицу «у», выход которого подключен к второму входу блока 4.4 сложения; третий вход блока 4.3 умножения на мнимую единицу «к», выход которого подключен к третьему входу блока 4.4 сложения; выход блока сложения является выходом блока 4 формирования триплексного числа, выдающего значения

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

Пример. Рассмотрим генератор псевдослучайных триплексных чисел. Пусть задан первый q=3 РРС, генерирующий 3-значную ПСП максимальной длины над полем GF{3). Генератор построен по примитивному многочлену

которому соответствует рекуррентное уравнение следующего вида:

Учитывая, что получим

Если в качестве исходных данных регистра (начального заполнения) записать: то на выходе генератора будет иметь место следующая ПСП:

Получаемые элемент ПСП поступают на первый вход блока 4 формирования триплексного числа, в частности на первый вход блока 4.1 умножения на мнимую единицу «i», в котором формируется следующие элементы псевдослучайного триплексного числа:

Пусть задан второй q=5PPC, генерирующий 5-значную ПСП максимальной длины над полем GF(5²). Генератор построен по примитивному многочлену

которому соответствует рекуррентное уравнение следующего вида:

Учитывая, что p₁=4, p₀=3 получим

Если в качестве исходных данных регистра (начального заполнения) записать: то на выходе генератора будет иметь место следующая ПСП:

Далее, вычисленные элементы ПСП поступают на второй вход блока

4 формирования триплексного числа, в частности на вход блока 4.2 умножения на мнимую единицу «j», в котором формируется следующие элементы псевдослучайного триплексного числа:

Пусть задан третий q=5PPC, генерирующий 5-значную ПСП максимальной длины над полем GF(5²). Генератор построен по примитивному многочлену

которому соответствует рекуррентное уравнение следующего вида:

Учитывая, что получим

Если в качестве исходных данных регистра (начального заполнения) записать: то на выходе генератора будет иметь место следующая ПСП:

Далее, вычисленные элементы ПСП поступают на третий вход блока 4 формирования триплексного числа, в частности на вход блока 4.3 умножения на мнимую единицу «k», в котором формируется следующие элементы псевдослучайного триплексного числа:

Затем элементы поступают на вход блока 4.4 сложения, в котором осуществляется окончательное формирование триплексного числа:

При этом в процессе формирования триплексного числа получаемые действительные числа удаляются

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

Настоящее техническое решение относится к области вычислительной техники. Технический результат заключается в повышении производительности вычислительного процесса за счёт реализации вычислений для формирования триплексных чисел. Технический результат достигается за счёт реализации процесса формирования триплексного числа s⁽¹⁾i+s⁽²⁾j+s⁽³⁾k. Процесс формирования триплексного числа s⁽¹⁾i+s⁽²⁾j+s⁽³⁾k основан на объединении в едином конструктивном исполнении трех q-PPC. Объединение указанных составляющих осуществляется в блоке формирования триплексного числа. 5 ил.

Устройство формирования триплексных чисел, состоящее из r регистров разрядности ([log₂ q]), r-1 блоков сложения в GF(q), r блоков умножения в GF(q), причем величина, на которую происходит умножение в (i+1)-M блоке умножения, равна коэффициенту ρ_i∈GF(q), характеристического многочлена

где i=0, 1, 2, …, r-1, P(z) - многочлен степени r, примитивный над GF(q), в котором выходы r-го регистра соединены со входами всех блоков умножения, выходы j-x блоков умножения соединены с первыми входами j-x блоков сложения, выходы которых соединены со входами j-x регистров, где j=0, 1, 2, …, r, вторые выходы всех блоков сложения образуют r группу управляющих выходов генератора, выходы k-х регистров соединены с третьими входами (k+1)-х блоков сложения, выходы которых соединены со входами (j+1)-х регистров, где k=1, 2, …, r, отличающееся тем, что введены генератор псевдослучайных чисел, функционирующих в конечном поле GF(q), где g - простое число, состоящее из r регистров разрядности ([log₂ q]), r-1 блоков сложения в GF(q), r блоков умножения в GF(q), причем величина, на которую происходит умножение в (i+1)-м блоке умножения, равна коэффициенту p_i∈GF(q), характеристического многочлена

где i=0, 1, 2, …, r-1, G(z) - многочлен степени r, примитивный над GF(q), в котором выходы r-го регистра соединены со входами всех блоков умножения, выходы j-x блоков умножения соединены с первыми входами j-x блоков сложения, выходы которых соединены со входами j-x регистров, где j=0, 1, 2, …, r, вторые выходы всех блоков сложения образуют r группу образующих входов генератора, выходы k-х регистров соединены со входами (j+1)-х регистров, где k=1, 2, …, r; генератор псевдослучайных чисел, функционирующих в конечном поле GF(q), где q - простое число, состоящее из r регистров разрядности ([log₂ q]), r-1 блоков сложения в GF(q), r блоков умножения в GF(q), причем величина, на которую происходит умножение в (i+1)-M блоке умножения, равна коэффициенту p_i∈GF(q), характеристического многочлена

где i=0, 1, 2, …, r-1, L(z) - многочлен степени r, примитивный над GF(q), в котором выходы r-го регистра соединены со входами всех блоков умножения, выходы j-x блоков умножения соединены с первыми входами j-x блоков сложения, выходы которых соединены со входами j-x регистров, где j=0, 1, 2, …, r, вторые выходы всех блоков сложения образуют r группу образующих входов генератора, выходы k-х регистров соединены со входами (j+1)-х регистров, где k=1, 2, …, r, блок формирования триплексного числа, содержащий первый блок умножения на мнимую единицу «r», второй блок умножения на мнимую единицу «j», «третий блок умножения на мнимую единицу «k», блок сложения, причем выходы первого, второго и третьего генераторов псевдослучайных последовательностей подключены соответственно к первому, второму и третьему входам блоков формирования триплексного числа; первый вход блока умножения на мнимую единицу «i», выход которого подключен к первому входу блока сложения; второй вход блока умножения на мнимую единицу «j», выход которого подключен ко второму входу блока сложения; третий вход блока умножения на мнимую единицу «k», выход которого подключен к третьему входу блока сложения; выход блока сложения является выходом блока формирования триплексного числа, выдающего значения s⁽¹⁾i+s⁽²⁾j+s⁽³⁾k.