Результат интеллектуальной деятельности: СПОСОБ И УСТРОЙСТВО РАЗМЕЩЕНИЯ ГРУПП ЧИСЕЛ В ОДНОРОДНЫХ БЛОКАХ ЦИФРОВОГО РЕГИСТРА

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

Известен способ представления чисел в модулярной системе счисления в виде упорядоченного набора вычетов по модулю, в котором применяются модули-основания (простые или взаимно простые целые числа) модулярной системе счисления и наименьшие неотрицательные вычеты по модулю. Вектор модулярного кода числа с компонентами (α₁…,α_i,…α_n) содержит вычеты по модулям {p_l,…p_i,…p_j,…p_n}. Индексы (1,…i,…,n) задают номера вычетов по модулям-основаниям модулярной системы и соответствующих двоичных блоков (независимых групп разрядов) цифрового блокового модульного регистра, предназначенные для размещения вычетов по модулям-основаниям. Для однозначного представления числа в модулярной системе вычетами по модулю необходимо выполнение условия простоты (взаимной простоты) оснований i≠j ∀i,j=1÷n (p_i,p_j)=1. Взаимно простые основания модулярной системы счисления в общем случае не являются степенями двух. Только одно из оснований может быть степенью двух. Вычеты по разным модулям изменяются в различных пределах, границы которых не кратны степеням двух. Числовые значения вычетов по модулю являются целыми числами, лежащими в пределах от нуля до значения модуля, уменьшенного на единицу. По этим причинам, в двоичных неоднородных блоках цифрового модульного регистра невозможно безизбыточное размещение вычетов в блоках цифрового регистра, т.к. для представления вычетов используются не все возможные двоичные комбинации, появляется информационная избыточность. Под неоднородностью блоков цифрового модульного регистра понимается их различная длина, выраженная в элементарных (двоичных) ячейках для размещения разрядов числового значения вычета по модулю в бинарном коде. При максимальной одинаковой длине блоков тем более возрастает информационная избыточность и невозможно использовать все возможные двоичные комбинации в цифровом блоке [Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - М.: Сов. радио, 1968. - 326 с.]. Избыточность в блоках снижает эффективность использования аппаратуры цифрового регистра.

Известный способ применен в устройствах «Устройство для деления числа в модулярном коде» (патенты РФ №2231822, №2237274), «Устройство для контроля ЭВМ» (патент РФ №2458384), «Устройство для определения знака модулярного числа» (патент РФ №2503995), содержащие в своем составе цифровые неоднородные блоковые регистры, предназначенные для функционального преобразования, хранения, сдвига, обработки, размещения вычетов модулярного кода.

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

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

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

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

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

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

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

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

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

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

- уменьшить сложность разработки из однородных блоков микросхемы модульного регистра.

Заявляемый способ предназначен для реализации следующих задач.

Для размещения в входном блочном модульном регистре модулярного кода числа в виде набора вычетов по m≥2 модулям-основаниям модулярной системы необходимо m-блоков. Для уменьшения избыточности все блоки имеют различную длину, заданную целым числом n_i≥]log₂p_i[, где i=1,…m указывает номер блока, т.е. содержат разное количество бинарных элементарных ячеек, предназначенных для хранения двоичных компонент вычетов по модулю.

Безызбыточное представление вычетов модулярного кода невозможно в неоднородных двоичных блоках m-модульного цифрового регистра по следующей причине. Различные числовые значения вычетов по модулю α_i не кратные целой степени двух должны размещаться в двоичном блоке, имеющем длину n=]log₂(maxα_i)[, где скобками обозначена целая, неменьшая часть числа. При размещении возникает избыточность оборудования для представления числовых значений вычетов по модулю в двоичных блоках цифрового регистра, т.к. для размещения вычетов используются не все возможные двоичные комбинации в блоках цифрового регистра, длиной n. Избыточность в блоке измеряется рациональным числом δ_i>0: δ_i=]log₂(maxα_i)[-log₂(maxα_i) или δ_i=]log₂(p_i-1)[-log₂(p_i-1).

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

На первом этапе задается первая константа р=2ⁿ. На втором этапе задается множество пар (p_i,p_j) взаимно простых модулей-оснований модулярной системы счисления, для которых выполняются условия:

В выходном блоковом модульном регистре содержится произвольное четное количество m≥2 блоков, равной длины n=log₂p, состоящих из бинарных элементарных ячеек, предназначенных для размещения двоичных компонент вычетов по модулю. Нечетным количество блоков может быть, если в множество оснований модулярной системы включен модуль p_i=2ⁿ.

Для представления вычетов по модулю в m-двоичных блоках выходного регистра, где m≥2, без избыточности необходимо выполнение равенства для каждой пары оснований (p_i,p_j) ∀i,j=1÷n, i≠j.

Обоснование заявляемого способа приведем на примере одной пары числовых значений вычетов по модулю (α_i, α_j) для двух взаимно простых оснований модулярной системы (p_i, p_j), p_i<p<p_j.

Для вычетов по модулю, являющихся компонентами модулярного кода, выполняются соотношения: , α_i≤p_j-1=p+γ_j-1.

Рассмотрим первый вариант соотношений. Пусть для вычетов по модулям выполняются неравенства α_i≤p_i-1, α_j≤p-1. Эти неравенства обнаруживают сравнением числовых значений вычетов по модулю с первой константой р=2ⁿ(n≥2). В этом случае вычеты по модулю в блоках входного модульного регистра передают в соответствующие однородные блоки выходного модульного регистра.

Рассмотрим второй вариант соотношений. Пусть для вычета по большему модулю выполняется неравенство p-1≤α_i≤p+γ_j-1. Вычисляют вспомогательную величину α′=α_j-p≤γ_j-1, для которой выполняются неравенства 0≤α′_j≤γ_j-1, а также при выполняется соотношение Это позволяет число передать в блок для вычета по модулю p_i<р, что обнаруживают по выполнению неравенства , т.к. выполняется соотношение:

,

где δ_i=(р-p_i) - вторая константа, являющаяся разностью между первой константой и меньшим из пары оснований модулярной системы.

Третьим технологическим этапом является вычисление, с использованием второй константы, выражения заявляемого способа. Четвертым технологическим этапом является ротация чисел перед занесением в блоки выходного регистра:

- в бинарный блок длиной n=log₂ p вместо вычета α_j по модулю p_j размещают вычет α_i≤p_i-1<p;

- в бинарный модуль длиной n=log₂p вместо вычета α_i по модулю - основанию p_i размещают число .

В результате будет получено при безубыточное, а при компактное, почти безубыточное размещение в выходном модульном регистре чисел в однородных блоках одинаковой длины n=log₂ р.

Для однозначного восстановления числовых значений вычетов по модулю из неоднородных блоков входного регистра выполняют обратную ротацию:

- в бинарный блок длиной n=log₂ р для вычета по модулю - основанию p_i передают вычет α_i≤p_i-1<p;

- восстанавливают числовое значение вычета α_j≥р по модулю p_j из соотношений , которое может быть размещено в бинарном блоке длиной n+1=1+log₂p.

Для заявленного способа приведем числовые примеры.

Пример 1. Ориентируясь на стандартный двоичный размер байта, выберем взаимно простые модули-основания модулярной системы: {p₁,р₂,p₃,р₄,р₅}={251, 255, 256, 257, 259}. Для них выполняются следующие соотношения: модули 251, 257 - простые; для трех модулей мультипликативные канонические разложения имеют вид: 255=3.5.17; 259=7.37; 256=2⁸. Это позволяет сформировать две пары (р₁,р₅), (р₂,р₄) взаимно простых модулей, для которых выполняются соотношения: ; р=р₃=2⁸=256; р₅=p+γ₁=259=2⁸+3; ; ; p₄=p+γ₂=2⁸+1=257; ; n=log₂p=log₂2⁸=8.

Выполнение соотношений для модулей-оснований модулярной системы позволяет заявленным способом размещать двоичные значения вычетов по пяти взаимно простым модулям в пяти однородных 8-битовых блоках выходного регистра.

Пусть из блока входного регистра получен вычет α₄=2⁸=р по модулю 257, который не может быть размещен в 8-битовом блоке. Вычисляют число , которое размещают в 8-битовом блоке, предназначенном для размещения вычета по модулю р₂, который размещают в 8-битовом блоке, предназначенном для размещения вычета по модулю р₄.

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

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

Заявленный способ реализуется в заявленном устройстве.

На Фиг. 1 представлена структурная схема устройства, в которой обозначены пара неоднородных блоков 1, 2 входного регистра 3, блок сравнения 4, блоки передачи данных 5, 6, 7, блок вычитания 8, проводники передачи из блока сравнения 4 управляющих сигналов 4.1, 4.2, пара однородных блоков 9, 10 выходного регистра 11.

В устройстве выход блока 1 соединен с информационными входами блоков 5, 7; выход блока 2 соединен с информационными входами блоков 4, 6, 8; первый выход 4.1 блока 4 соединен с управляющими входами блоков 5, 6; второй выход 4.2 блока 4 соединен с управляющими входами блоков 7, 8; выход блока 5 соединен с входом блока 9; выход блока 6 соединен с входом блока 10; выход блока 7 соединен с входом блока 10; выход блока 8 соединен с входом блока 9.

Устройство, реализующее заявленный способ, работает следующим образом. Из блока 1 входного регистра 3 передают значения вычетов по модулю в параллельном бинарном коде на информационные входы блоков передачи данных 5, 7, и значения вычетов по модулю из блока 2 входного регистра 3 аналогично передают на информационные входы блоков сравнения 4, вычитания 8 и передачи данных 6. В блоке 4 выполняют сравнение вычета из блока 2 с первой константой, заданной заявленным способом. Если сравниваемый вычет меньше, то после поступления разрешающего сигнала 4.1 из блока 4 числовые значение вычетов из блоков 5, 6 передают на информационные входы блоков 9, 10 выходного регистра 11 соответственно. Если сравниваемый вычет не меньше, то после поступления разрешающего сигнала 4.2 из блока 4, из блока 7 вычет по модулю передают на информационный вход блока 10 выходного регистра 11, а в блоке 8 вычитают вторую константу, вычисленную заявленным способом, и результат передают на информационный вход блока 9 выходного регистра 11.

Опишем работу блоков устройства на примере. Заданы упорядоченное множество взаимно простых модулей-оснований модулярной системы: {p₁,…p_i, р, p_j,…p_m}={…,13, 16, 19,…}. Для пары модулей 13 и 19 выполняются соотношения: , P=2⁴=16, p_j=p+γ_j=2⁴+3=19; ; n=log₂p=4.

Вычеты по модулям 13, 19 выбирают из неоднородных блоков 2, 3 входного модульного регистра 1.

Вычеты по модулям, меньшим или равным 16 могут быть размещены в четырехбитовых двоичных блоках. Для размещения вычетов по модулю 13 нужен четырехбитовый двоичный блок 2. Числовые значения вычетов по модулю 19, большие или равные 16 могут быть размещены только в пятибитовом двоичном блоке 3 входного регистра 1.

Проиллюстрируем, как вычеты по выбранным модулям 13, 19 заявленное устройство размещает в четырехбитовых двоичных блоках 9, 10 выходного регистра 11. Пусть вычет по модулю 19 в блоке 2 регистра 1 равен 18, это больше 16, поэтому вычет не может быть размещен в четырехбитовом двоичном блоке 10.

В блоке 8 вычисляют число: . Полученное в блоке 8 число при поступлении управляющего сигнала 4.2 передают на информационный вход четырехбитового блока 9. Вычет по модулю 13, переданный в блок 7, при поступлении управляющего сигнала 4.2 передают на информационный вход блока 10 регистра 11, первоначально предназначенного для размещения вычетов по модулю 19 для числовых значений, меньших 16. О ротации числовых значений в блоках 9, 10 регистра 11 свидетельствует большее модуля 13 числовое значение 15 в четырехбитовом блоке 9. О передаче вычетов из блоков 1, 2 регистра 3 без ротации в блоки 9, 10 регистра 11 свидетельствовало бы размещенное в блоке 9 значение вычета, меньшее 13 по модулю 13.

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

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

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

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