СПОСОБ И УСТРОЙСТВО РАЗМЕЩЕНИЯ ГРУПП ЧИСЕЛ В ОДНОРОДНЫХ БЛОКАХ ЦИФРОВОГО РЕГИСТРА Российский патент 2016 года по МПК G06F7/72 

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

Известен способ представления чисел в модулярной системе счисления в виде упорядоченного набора вычетов по модулю, в котором применяются модули-основания (простые или взаимно простые целые числа) модулярной системе счисления и наименьшие неотрицательные вычеты по модулю. Вектор модулярного кода числа с компонентами (α₁…,α_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.

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

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

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

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

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

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

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

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

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

5. Устройство по п. 4, отличающееся тем, что в качестве блоков входного и выходного регистров содержит адресуемые ячейки памяти.

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