СПОСОБ И УСТРОЙСТВО РАЗМЕЩЕНИЯ ГРУПП ЧИСЕЛ В ОДНОРОДНЫХ БЛОКАХ ЦИФРОВОГО РЕГИСТРА
METHOD AND DEVICE FOR ARRANGEMENT OF GROUPS OF NUMBERS IN HOMOGENEOUS UNITS OF DIGITAL REGISTER

Изобретение относится к области специализированной цифровой вычислительной техники для параллельной обработки цифровой информации, может быть использовано в системах связи и управления сложными объектами, предназначено для размещения в блоках цифрового регистра групп чисел или данных, представленных в модулярных форматах.
1
i
n
l
i
j
n
i
j
Известен способ представления чисел в модулярной системе счисления в виде упорядоченного набора вычетов по модулю, в котором применяются модули-основания (простые или взаимно простые целые числа) модулярной системе счисления и наименьшие неотрицательные вычеты по модулю. Вектор модулярного кода числа с компонентами (α…,α,…α) содержит вычеты по модулям {p,…p,…p,…p}. Индексы (1,…i,…,n) задают номера вычетов по модулям-основаниям модулярной системы и соответствующих двоичных блоков (независимых групп разрядов) цифрового блокового модульного регистра, предназначенные для размещения вычетов по модулям-основаниям. Для однозначного представления числа в модулярной системе вычетами по модулю необходимо выполнение условия простоты (взаимной простоты) оснований i≠j ∀i,j=1÷n (p,p)=1. Взаимно простые основания модулярной системы счисления в общем случае не являются степенями двух. Только одно из оснований может быть степенью двух. Вычеты по разным модулям изменяются в различных пределах, границы которых не кратны степеням двух. Числовые значения вычетов по модулю являются целыми числами, лежащими в пределах от нуля до значения модуля, уменьшенного на единицу. По этим причинам, в двоичных неоднородных блоках цифрового модульного регистра невозможно безизбыточное размещение вычетов в блоках цифрового регистра, т.к. для представления вычетов используются не все возможные двоичные комбинации, появляется информационная избыточность. Под неоднородностью блоков цифрового модульного регистра понимается их различная длина, выраженная в элементарных (двоичных) ячейках для размещения разрядов числового значения вычета по модулю в бинарном коде. При максимальной одинаковой длине блоков тем более возрастает информационная избыточность и невозможно использовать все возможные двоичные комбинации в цифровом блоке [Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - М.: Сов. радио, 1968. - 326 с.]. Избыточность в блоках снижает эффективность использования аппаратуры цифрового регистра.
Известный способ применен в устройствах «Устройство для деления числа в модулярном коде» (патенты РФ №2231822, №2237274), «Устройство для контроля ЭВМ» (патент РФ №2458384), «Устройство для определения знака модулярного числа» (патент РФ №2503995), содержащие в своем составе цифровые неоднородные блоковые регистры, предназначенные для функционального преобразования, хранения, сдвига, обработки, размещения вычетов модулярного кода.
Проведенный патентный поиск не обнаружил устройств преобразования группы цифр, специально предназначенных для размещения в однородных блоках цифрового регистра.
Наиболее близким, взятым за прототип, можно считать «Арифметическое устройство по модулю» по патенту РФ №2157560, содержащее входной неоднородный блоковый модульный регистр для выборки вычетов модулярного кода, над которыми выполняются функциональные преобразования в блоках шифраторов, преобразователей кода, умножения и деления и других блоках, причем результат преобразований заносится в выходной неоднородный блоковый модульный регистр.
Недостатком известного способа, устройств на его основе и прототипа, содержащих неоднородные блоковые регистры для размещения числовых значений вычетов модулярного кода являются:
- информационная избыточность блоков, т.к. используются не все возможные комбинации символов для размещения числовых значений вычетов в блоках регистра;
- наличие неоднородных блоков с различной разрядностью, имеющих информационную избыточностью, что уменьшает взаимозаменяемость блоков, и ремонтопригодность цифрового регистра вычислительной системы;
- увеличение сложности разработки и реализации микросхемы модульного регистра из неоднородных блоков различной длины.
Общим признаком известного и заявляемого способов, а также устройства на его основе является наличие цифровых блоковых модульных регистров.
Техническим результатом способа и устройства размещения данных и числовые значения вычетов по модулю в однородных блоках цифрового регистра является то, что способ реализует, а техническое устройство позволяет:
- повысить эффективность использования оборудования блоков, уменьшить или полностью устранить избыточность регистра для размещения цифровых данных, использовать все возможные комбинации символов в элементарных ячейках блоков для представления вычетов по модулю;
- повысить ремонтопригодность и надежность цифрового регистра вычислительной системы, получить взаимозаменяемость блоков;
- уменьшить сложность разработки из однородных блоков микросхемы модульного регистра.
Заявляемый способ предназначен для реализации следующих задач.
i
2
i
Для размещения в входном блочном модульном регистре модулярного кода числа в виде набора вычетов по m≥2 модулям-основаниям модулярной системы необходимо m-блоков. Для уменьшения избыточности все блоки имеют различную длину, заданную целым числом n≥]logp[, где i=1,…m указывает номер блока, т.е. содержат разное количество бинарных элементарных ячеек, предназначенных для хранения двоичных компонент вычетов по модулю.
i
2
i
i
i
2
i
2
i
i
2
i
2
i
Безызбыточное представление вычетов модулярного кода невозможно в неоднородных двоичных блоках m-модульного цифрового регистра по следующей причине. Различные числовые значения вычетов по модулю α не кратные целой степени двух должны размещаться в двоичном блоке, имеющем длину n=]log(maxα)[, где скобками обозначена целая, неменьшая часть числа. При размещении возникает избыточность оборудования для представления числовых значений вычетов по модулю в двоичных блоках цифрового регистра, т.к. для размещения вычетов используются не все возможные двоичные комбинации в блоках цифрового регистра, длиной n. Избыточность в блоке измеряется рациональным числом δ>0: δ=]log(maxα)[-log(maxα) или δ=]log(p-1)[-log(p-1).
Заявляемый способ предназначен для уменьшения избыточности представления вычетов в однородных блоках модульного регистра и содержит технологические этапы.
n
i
j
На первом этапе задается первая константа р=2. На втором этапе задается множество пар (p,p) взаимно простых модулей-оснований модулярной системы счисления, для которых выполняются условия:
2
i
n
В выходном блоковом модульном регистре содержится произвольное четное количество m≥2 блоков, равной длины n=logp, состоящих из бинарных элементарных ячеек, предназначенных для размещения двоичных компонент вычетов по модулю. Нечетным количество блоков может быть, если в множество оснований модулярной системы включен модуль p=2.
i
j
Для представления вычетов по модулю в m-двоичных блоках выходного регистра, где m≥2, без избыточности необходимо выполнение равенства  для каждой пары оснований (p,p) ∀i,j=1÷n, i≠j.
i
j
i
j
i
j
Обоснование заявляемого способа приведем на примере одной пары числовых значений вычетов по модулю (α, α) для двух взаимно простых оснований модулярной системы (p, p), p<p<p.
i
j
j
Для вычетов по модулю, являющихся компонентами модулярного кода, выполняются соотношения: , α≤p-1=p+γ-1.
i
i
j
n
Рассмотрим первый вариант соотношений. Пусть для вычетов по модулям выполняются неравенства α≤p-1, α≤p-1. Эти неравенства обнаруживают сравнением числовых значений вычетов по модулю с первой константой р=2(n≥2). В этом случае вычеты по модулю в блоках входного модульного регистра передают в соответствующие однородные блоки выходного модульного регистра.
i
j
j
j
j
j
i
Рассмотрим второй вариант соотношений. Пусть для вычета по большему модулю выполняется неравенство p-1≤α≤p+γ-1. Вычисляют вспомогательную величину α′=α-p≤γ-1, для которой выполняются неравенства 0≤α′≤γ-1, а также при  выполняется соотношение  Это позволяет число  передать в блок для вычета по модулю p<р, что обнаруживают по выполнению неравенства , т.к. выполняется соотношение:
,
i
i
где δ=(р-p) - вторая константа, являющаяся разностью между первой константой и меньшим из пары оснований модулярной системы.
Третьим технологическим этапом является вычисление, с использованием второй константы, выражения  заявляемого способа. Четвертым технологическим этапом является ротация чисел перед занесением в блоки выходного регистра:
2
j
j
i
i
- в бинарный блок длиной n=log p вместо вычета α по модулю pразмещают вычет α≤p-1<p;
2
i
i
- в бинарный модуль длиной n=logp вместо вычета α по модулю - основанию p размещают число .
2
В результате будет получено при  безубыточное, а при  компактное, почти безубыточное размещение в выходном модульном регистре чисел в однородных блоках одинаковой длины n=log р.
Для однозначного восстановления числовых значений вычетов по модулю из неоднородных блоков входного регистра выполняют обратную ротацию:
2
i
i
i
- в бинарный блок длиной n=log р для вычета по модулю - основанию p передают вычет α≤p-1<p;
j
j
2
- восстанавливают числовое значение вычета α≥р по модулю p из соотношений , которое может быть размещено в бинарном блоке длиной n+1=1+logp.
Для заявленного способа приведем числовые примеры.
1
2
3
4
5
1
5
2
4
3
5
1
4
2
2
2
8
8
8
8
8
Пример 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=logp=log2=8.
Выполнение соотношений для модулей-оснований модулярной системы позволяет заявленным способом размещать двоичные значения вычетов по пяти взаимно простым модулям в пяти однородных 8-битовых блоках выходного регистра.
4
2
4
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.
1
i
j
m
j
j
2
4
4
Опишем работу блоков устройства на примере. Заданы упорядоченное множество взаимно простых модулей-оснований модулярной системы: {p,…p, р, p,…p}={…,13, 16, 19,…}. Для пары модулей 13 и 19 выполняются соотношения: , P=2=16, p=p+γ=2+3=19; ; n=logp=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.
Заявляемое устройство выполняется в виде интегральной микросхемы или входит в микросхему в составе вычислительного устройства и предназначено для компактного размещения, хранения, представления упорядоченного набора числовых значений групп чисел или вычетов модулярного кода, используемых для параллельной обработки дискретной информации.
Возможен вариант устройства, отличающийся отсутствием отдельных блоковых входного и выходного регистров и содержащий адресуемые ячейки памяти, выполняющие функции блоков входного и выходного регистров.
Возможен вариант устройства, отличающийся отсутствием отдельных блоковых входного и выходного регистров и содержащим в качестве блоков регистров параллельные независимые каналы входного потока и выходного потоков цифровых данных соответственно.
Таким образом, совокупность технологических операций заявленного способа, а именно задание первой константы, разделение на пары вычетов по модулю, размещенных в блоках входного регистра, вычисление второй константы, выбор пары оснований модулярной системы, симметричных относительно первой константы, преобразование вычета по одному из оснований с использованием второй константы, размещение после преобразования пары чисел в однородных блоках выходного регистра, а также отличительных признаков заявленного устройства, а именно наличие для каждой пары блоков входного регистра блоков сравнения, вычитания, передачи данных и проводников управляющих сигналов, позволяет достичь заявленных технических результатов.