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