Устройство для сжатия чисел и вычисления полинома
Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях. Цель изобретения состоит в расширении области применения за счет дополнительной возможности сжатия чисел. Устройство содержит два регистра, два коммутатора, две группы элементов задержки, сумматор, сумматор произведений, группу умножителей. Сущность изобретения состоит в реализации возможности производить сжатие исходных чисел за счет уменьшения количества значащих двоичных разрядов, требуемых для представления сжатых чисел в сравнении с исходными, при этом устройство осуществляет сжатие на основе соотношения (макс(а|)+ 1)(макс(аО+ + 1) ... + ап, сжатое число; а - цифры числа; ai 1,n; сжатое число при необходимости восстанавливается поэлементно в исходное последовательным его делением на макс(а) + 1, остатки от деления справа налево, начиная с последнего частного, и составляет исходное число. 1 ил., 1 табл. (Л С
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
1725218 А1 (я)з G 06 F 7/544
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ, СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ,ЬЭ
IQl Ы
1
i@)
)>
/ ъ (21) 4768991/24 (22) 11.12.89 (46) 07.04.92. Бюл. М 13 (72) Э.Н.Король, Ю.Ю. Милонов, А.В.Товарницкий и Ю.И.Скорин (53) 681.325 (088.8) (56) Авторское свидетельство СССР
М 885997, кл. G 06 F 7/544, 1979.
Авторское свидетельство СССР
М 1464156, кл. G 06 F 7/544, 1987. (54) УСТРОЙСТВО ДЛЯ СЖАТИЯ ЧИСЕЛ И
ВЫЧИСЛЕНИЯ ПОЛИНОМА (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях, Цель изобретения состоит в расширении области применения за счет дополнительной возможности сжатия чисел. Устройство содерИзобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях, Известно устройство для вычисления полинома и-й степени, содержащее сумматор, линии задержки, регистр.
Недостаток устройства — ограниченная область применения, так как оно не позволяет сжимать цифровые данные, поступающие на вход устройства, его сложность.
Известно также устройство для вычисления полинома и-й степени, содержащее сумматор, группу элементов задержки,,регистр.
Недостаток устройства — ограниченная область применения, так как оно не позвожит два регистра, два коммутатора, две группы элементов задержки, сумматор, сумматор произведений, группу умножителей.
Сущность изобретения состоит в реализации возможности производить сжатие исходных чисел за счет уменьшения количества значащих двоичных разрядов, требуемых для представления сжатых чисел в сравнении с исходными, при этом устройство осуществляет сжатие на основе соотношения Y= а1(ма кс(а )+ 1)" + а2 (ма кс(а )+
+ 1) 2+ ... + ап, где Y — сжатое число; а— цифры числа; а = 1,п; сжатое число при необходимости восстанавливается поэлементно в исходное последовательным его делением на макс(а) + 1, остатки от деления справа налево, начиная с последнего частного, и составляет исходное число. 1 ил., 1 табл. ляет сжимать цифровые данные, поступающие на вход устройства.
Цель изобретения — расширение области применения за счет введения дополнительной возможности сжатия чисел.
Поставленная цель достигается тем, что в устройство для сжатия чисел и вычисления полинома, содержащее первый регистр, сумматор и первую группу последовательно соединенных элементов задержки, дополнительно введены блок сравнения, два коммутатора, второй регистр, сумматор произведений, группа умножителей и вторая группа элементов задержки, причем устройство содержит соединенные по входам блок сравнения и через информационные входы первый коммутатор, выход блока
1725218
30
50 сравнения соединен с адресным входом первого коммутатора, первый и второй информационные входы второго коммутатора, адресные входы которого соединены с входом задания режима устройства, вход стробирования устройства соединен с входом стробирования второго коммутатора, выход второго коммутатора соединен с входом второго сомножителя первого умножителя груп и ы умножителей, последовательно соединенных посредством входа первого сомножителя, и входом первого элемента задержки, последовательно соединенной второй группы элементов задержки, вход логической единицы устройства соединен с первым входом второго регистра и входом первого сомножителя первого умножителя группы, выходы элементов задержки второй группы с первого по (n — 2)-й элемент, где и— количество цифр в сжимаемом числе, соединены с входами вторых сомножителей соответствующих умножителей с второго по (и — 1)-й группы, выходы умножителей с первого по(п — 1)-й группы соединены соответственно с входами с второго по и-й второго регистра, вход стробирования второго регистра соединен с входом стробирования сумматора произведений, входы второго операнда которого соединены с выходом второго регистра, выход сумматора произведений, выход основания сжимаемого числа устройства.
Первый коммутатор служит для реализации логической функции с целью передачи на вход сумматора числа, соответствующего макс(а ), где а — одноразрядная цифра сжимаемого числа, i = 1,п, является стандартным элементом и И-ИЛИ.
Второй коммутатор служит для реализации логического управления с целью разрешения режима сжатия чисел или вычисления полинома, является стандартным элементом 2 И вЂ” ИЛИ, второй вход.,первого элемента И которого инверсный.
Сумматор произведений служит для вычисления сумм произведений с целью получения сжатого числа или полинома
il é степени, является известным элементом.
Блок сравнения служит для реализации логической функции "Больше" с целью сравнить а -числа, поступающие на его вход, и разрешить передачу на выход перво о коммутатора числа, равного макс(а ), является стандартным элементом.
Группа умножителей служит для умножения поступающих на информационные входы данных с целью получения элементов степенного ряда, они являются стандартными последовательно соединенными посредством первого сомножителя элементами.
Второй регистр служит для накопления асинхронно поступающих на его информационные входы данных с целью последующей одновременной подачи данных при поступлении стробирующего импульса на входы первого и второго операндов сумматора произведений, является стандартным элементом.
Вторая группа элементов задержки служит для задержки прохождения числа на один такт через каждый элемент, они являются стандартными последовательно соединенными элементами.
Сущность изобретения состоит в расширении области применения, что достигается путем реализации возможности производить сжатие исходных чисел за счет уменьшения количества значащих двоичных разрядов, требуемых для представления сжатых чисел в сравнении с исходными, при этом сжатое число А получаем из следующего соотношения
А = а1 (макс(а ) + 1)" +
+ а2 (макс(а ) + 1) + ... + an, где i = 1,п.
Сжатое число при необходимости восстанавливается поэлементно s исходное последовательным его делением на макс(а)+ 1, остатки от деления слева направо и составят исходное число.
На чертеже изображена блок-схема предлагаемого устройства, Устройство содержит вход 1 сжимаемого числа устройства, первый регистр 2, сумматор 3 произведений, второй регистр 4, коммутатор 5, вторую группу 6 элементов задержки, вход 7 задания режима работы устройства, вход 8 основания полинома устройства, выход 9 основания сжимаемого числа устройства, выход 10 сжатого кода числа устройства, блок 11 сравнения, коммутатор 12, сумматор 13, вход 14 логической единицы устройства, вход 15 стробирования устройства, первая группа 16 элементов задержки, группа 17 умножителей, причем вход 1 сжимаемого числа устройства соединен с информационным входом первого регистра 2 блока 11 сравнения и информационным входом первого коммутатора 12, выход блока 11 сравнения соединен с адресным входом первого коммутатора 12, выход которого соединен с входом первого слагаемого сумматора 13, вход второго слагаемого которого соединен входом 14 логической единицы устройства, выход
1725218
30
40
55 сумматора 13 — с первым информационным входом второго коммутатора 5, второй информационный вход и адресные входы которого соединены соответственно с входом
8 основания полинома устройства и входом
7 задания режима устройства, вход 15 стробирования устройства соединен с входами стробирования сумматора 13, второго коммутатора 5; первого элемента задержки первой последовательно соединенной группы 16 и первого умножителя последовательно соединенной посредством первых суммирующих входов группы 17 умножителей, выход второго коммутатора 5 соединен с входом второго сомножителя первого умножителя группы 17 и входом первого элемента 6 задержки второй последовательно соединенной группы, вход 14 логической единицы устройства соединен с первым входом второго регистра 4 и входом первого сомножителя первого умножителя группы
17, выходы с первого по (п — 2)-й элементов 6 задержки второй группы, где n — количество цифр в сжимаемом числе, соединены соответственно с входами вторых сомножителей умножителей с второго по (п-1)-й группы 17, входы стробирования, начиная с второго умножителя группы 17, соединены соответственно с выходами элементов 16 соответственно с первого по (n-2)-й задержки первой группы, выходы умножителей 17 с первого по (и — 1)-й группы соединены соответственно с входами с второго по и-й второго регистра 4, выход (п-1)-го элемента 16 задержки первой группы соединен с входом стробирования второго регистра 4, первого регистра 2 и сумматора 3 произведений, входы первого и второго операндов которого соединены с выходами соответственно первого 2 и второго 4 регистров, выход сумматора 3 произведений соединен с выходом
10 сжатого кода числа устройства, выход 9 основания сжимаемого числа устройства соединен с выходом сумматора 13.
Устройство работает следующим образом.
С началом работы устройства с входа 15 стробирования устройства стробирующий импульс задает напрямую и через первую группу 16 элементов задержки последовательность работы стробируемых элементов (сумматор 13, коммутатор 5, группа 17 умножителей, второй регистр 4, сумматор 13 и роизведений, первый регистр 2), на вход 7 задания режима устройства подан логический "0", что соответствует выбору режима сжатия числа, при этом второй коммутатор
5 запрещает прохождение аргумента многочлена с входа 8 основания полинома устройства на свой выход и разрешает прохождение числа, соответствующего выражению макс(а )+ 1 с выхода сумматора 13, сжимаемого число с входа 1 сжимаемого числа устройства подается (каждая m-разрядная цифра числа — с соответствующего входа), на первый регистр 2, где сжимаемое число хранится до поступления стробирующего импульса.
Цифры сжимаемого числа с входа 1 сжимаемого числа устройства также поступают на блок 11 сравнения, который, используя признак "Больше", устанавливает логическую единицу по адресному
i-му входу первого 12 коммутатора, через информационный i-й вход которого на его выход поступила большая цифра, соответствующая макс(а ), далее следующая на первый суммирующий вход сумматора 13, с входа 14 логической единицы устройства через второй суммирующий вход сумматора
13 к макс(а ) добавляется единица, в результате получаем число, соответствующее выражению макс(а)+ 1, следующее на выход 9 основания устройства, которое через первый информационный вход второго коммутатора 5 поступает на первый вход первого умножителя группы 17 и далее через первую группу элементов 16 задержки на первые входы сомножителей остальных (n — 2)-х умножителей группы 17, соединение группы
17 умножителей и подача с входа 14 логической единицы позволяет последовательно, с прохождением стробирующего импульса, возводить цифру, соответствующую макс(а ) + 1 в степень от 0 до (п-1) (так, с входа 14 логической единицы получаем
"1", а на соответствующих выходах группы
17 умножителей х 1, х.х, ..., х" ), и по мере поступления данных накапливаются полученные величины степенного ряда с основанием, соответствующим макс(а ) + 1 на втором регистре 4, с появлением стробирующего импульса, по времени совпадающим с окончанием вычисления на (n — 1)-м умножителе группы 17.
Благодаря наличию второй группы 6 элементов задержки одновременно с второго регистра 4 первого регистра 2 данные поступают на входы первого и второго операндов сумматора 3 произведений, перемножаются соответственно первый операнд с первым, второй с вторым и т.д., полученные произведения суммируются и результат выдается через выход сумматора 3 произведений на выход 10 сжатого кода числа устройства, следующий стробирующий импульс с входа 15 стробирования следует через время, равное Лт(п — 1)+ Т, где
Л с — такт работы одного умножителя 17
1725218
55 группы, и — количество коэффициентов (а ), Т вЂ” время работы сумматора 3 произведений.
В режиме вычисления полинома и-й степени с входа 7 задания режима устройства на адресные входы второго 5 коммутатора подается логическая единица, открывающая его второй информационный вход, импульс с входа 15 стробирования через первую 16 группу элементов задержки задает порядок работы элементов устройства, число, задающее основание полинома с входа 8 основания полинома устройства через второй информационный вход второго 5 коммутатора последовательно поступает на вход второго сомножителя первого умножителя 17 группы и через элементы 6 задержки второй группы на вход второго сомножителя остальных умножителей 17 группы, которые последовательно возводят число х в степень от 1 до (п-1) и накапливают полученные величины степенного ряда íà BTQром 4 регистре, с входа 14 логической единицы устройства число "1" поступает на вход первого сомножителя первого умножителя 17 группы и первый вход второго 4 регистра, данные с первого 2 регистра и с второго 4 регистра, при подаче на их входы стробирования импульса с выхода последнего элемента 16 задержки группы, поступают на соответственно на первый и второй входы операндов сумматора 3 произведений, который перемножает первый операнд первого входа на первый операнд второго входа, второй на вторым и т.д., здесь же полученные произведения суммируются и результат выдается на выход 10 сжатого кода числа устройства, следующий стробирующий импульс со входа 15 стробирования следуетчерез время равное Лтр(п — 1)+Т, где
Лс — такт работы одного умножителя группы
17, n — количество коэффициентов (а), Т— время работы сумматора 3 произведений.
Оценим технико-экономическую эффективность изобретения. Например, если на вход 1 сжимаемого числа устройства поступило число "130524", на сумматоре 13 получаем число 6, степенной ряд которого после возведения в степень группой 17 умножителей имеет вид 1, 6, 6, 6, 6, 6, 4 3 5 сумматор 3 произведений выполняет следующие действия
7776+ 3 ° 1296+ 0:216+ 5 36+ 2 - 6+ 4
Результат вычислений — число 11860, в двоичном представлении которому выделяется 14 разрядов против 17 разрядов исходного числа, т,е. выигрыш равен трем
50 разрядам, и далее с увеличением количества чисел, поступающих на вход устройства, количество выигранных разрядов будет возрастать, что и подтверждается данными приводимой ниже таблицы оценки эффективности сжатия чисел для возможных вариантов чисел, которые могут поступать на вход устройства, в которой приведены граничные числовые данные до сжатия и после с учетом увеличения количества разрядов и макс(а ) + 1 с указанием количества значащих двоичных разрядов для представления каждого граничного варианта, а также граничное выигранное количество двоичных разрядов в результате сжатия. Из таблицы следует, что при работе устройства в режиме сжатия чисел выигрыш в двоичных разрядах подтверждает эффективность изобретения.
Таким образом, техническое преимущество заявляемого изобретения по сравнению с. известным состоит в расширении области применения путем сжатия исходного числа, что позволяет сократить количество значащих двоичных разрядов, необходимых для его представления, Положительный эффект изобретения состоит в том, что при расширении области применения обеспечивается сжатие в
П и ,, ак 10 /,>, а (макс(а)+ 1) раз, что к=0 к=0 позволяет получать на выходе устройства числа, которые требуют меньшего количества значащих двоичных разрядов для своего представления, Устройство может использоваться в специализированных вычислителях.
Формула изобретения
Устройство для сжатия чисел и вычисления полинома, содержащее первый регистр, сумматор и первую группу последовательно соединенных элементов задержки, о т л ич а ю щ е е с я тем, что, с целью расширения области применения путем обеспечения дополнительной возможности сжатия чисел, в него введены блок сравнения, два коммута- тора, второй регистр, сумматор произведений, группа умножителей и вторая группа элементов задержки, причем вход сжимаемого числа устройства соединен с информационными входами первого регистра и первого коммутатора и входом блока сравнения, выход которого соединен с адресным входом коммутатора, выход которого соединен с входом первого слагаемого сумматора, вход младшего разряда второго слагаемого которого соединен с входом логической единицы устройства, входом млад10
1725218
Макс (a)+1
РазРяд
Макс и йин возможные числа до и . после сжатия
Кол, двоич. разр.
Выигрыш
Кол. двоич. разр.
Выигрыш
Кол. двоич. рвзр
Выигрыш
Макс и мин возможные числа ло и после сжатия
Кол. двоич. разр.
Выигрыш
Макс и мин
Макс и мин возможные числа до и после сжатия возножные до и после сжатия
4
3
2-1
44
14
24
4
4
1-0
7
5
4
3
2-1
4
1
2-3
7
2
4-5
13
22
12
11
2 10
444
104
124
9
6
3-2
333
103
63
222
102
26
111
100
3333
1003
255
3
6-7
14
14
4
9-10
17
17
5
ll-1Z
4444
1004
624
129
10
4-3
14
6-5
2222
1002
29
1111
4 1000
44444
10004
3124
629
33333
10003
1023
259
22222
10002
242
11111
5 10000
16
444444
100004
15624
3129
19
17
12
11
7-5
222222
100002
728
245
333333
100003
1027
111111
6 100000
1111111
7 1000000
127
4444444
1000004
78124
15629
2222222
1000002
2186
731
22
14
13
8-7
3333333
1000003
16383
4099
21
6
44444444
10000004
390624
78129
24 22222222 25
24 10000002 24
8 6561 13
7 2189 12
16-17 12
27 222222222 29
27 100000002 27
9 19682 15
8 6564 13
I8""19 ° 14
30 2222222222 31
30 1000000002 30
10 59048 16
9 19685 15
20-21 15
24
16
29
27
l8
17
1110
33333333
10000003
16387
1 111 1 i 11
8 10000000
128
444444444
100000004
1953124
390629
333333333
100000003
262143
65539
111111111
9 100000000
511
256
3333333333
1000000003
262147
32
19
1211
1111111111
10 1000000000
1023
512 шего разряда первого сомножителя первого умножителя группы и входом младшего разряда первой группы входов второго регистра, выход сумматора соединен с первым информационным входом второго коммутатора, второй информационный вход и адресный вход которого соединены соответственно с входом основания устройства и входом задания режима устройства, тактовый вход которого соединен с входами стробирования сумматора, второго коммутатора, первого элемента задержки первой группы и первого умножителя группы, выход второго коммутатора соединен с входом второго сомножителя первого умножителя группы и входом первого элемента задержки второй группы, выходы с первого по (n — 2)-й элементов задержки второй группы, где n — количество цифр в сжи12
5
14
18
10
8-9
20
10
10 маемом числе, соединены с входами вторых сомножителей соответственно с второго по (п-1)-й умножителей группы, входы стробирования которых соединены с выходами со5 ответственно с первого по(п-2)-й элементов задержки первой группы, выходы умножителей с первого по (и-1)-й группы соединены с входами соответственно с второй по и-к3 групп разрядов сумматора произведений, 10 выход (и — 1)-го элемента задержки первой группы соединен с входами стробирования второго регистра, первого регистра и сумматора произведений, входы первого и второго операндов которого соединены с
15 выходами соответственно первого и второго регистров, выход сумматора произведений соединен с выходом сжатого кода числа устройства, выход основания которого соединен с выходом сумматора.
13
3-2
16
l4
12
19
17
Il
12
5 23
17
14
6.
26
24
19
17
29
27
21 .19
4444444444 33
1000000004 30
9765624 24
1953129 21
1725218
Накс (а)+1 раз"
Ряд
Кол. двоич. разр.
Выигрыш
Кол.
Кол.
Накс и мин возможные числа до и после сжатия
Колич. двоич. разр.
Выигрыж
Накс и мин возможные числа до и после сжатия макс и мин возможные числа до и после сжатия
Накс и мин возможные числа до и после сжатия двоим, раар.
Выигрыж
° « двоич. разр.
Выигрыж вв
18
66
16
48
2 55 I5
11
4
4
1-0
77
17
63
7
6
4 .1
555
3 105
215
666
106
342
55 ввв
108
728
10
3
10
1
777
107
511
10
1-0
6666
1006
349 вввв
1008
737
7777
1007
519
5555
4 1005
1295
221
13
12
1-0
17
14
I5
13
2-1
66666
10006
16806
2407
88888
10008
59048
6569
55555
5 10005
7775
1301
77777
10007
32767
i03
666666
100006
117648
16813
8888888
1000008
59057. 555555
6 100005
46655
7781
17
38
16
2-1
777777
100007
262143
32775
6666666
1000006
823542
117655
7777777
1000007
2097153
262151
88888888
10000008
4782968
531449
5555555
7 1000005
270935
46661
23
21
19
16
4-5
26
24
21
19
27
24
21
23
21
21
19
66666666
10000006
823549 ввввввввв
100000008
4782977
55555555
8 10000005
1679616
279941
77777777
10000007
2097159
27
24
24
22
3-2
27
27
3-2
33
2В
3-2
666666666
100000006
40353606
5764807
555555555
9 100000005
10077695
1679621
777777777
100000007
134217ЕОВ
16777223 бббббббббб
1000000006
282475242
40353613
33
26
24
7-6
7777777777
1000000007
307374Е09
134217Е08
50
1О 1000000005
60466175 ! оо777о1
4
4
О
8
2
i3
Е8
16
14
13
11
17
16
13
17
14
\2
17
17
3-2
23
17
26
24
23
3-4
29
27
26
23
3-4
33
29
26
12
Продолжение таблицы
5
7. 5
О .10
О
14
13
1-0
17 .14 16
13
1 .20 17
16
0-1
24
21
23
20 .1
27
24
26
23
27
29
26
8888888888 34
1оооооооов 3о
348678Е09 32
348742Е08 29
2-1
1725218
50
Составитель Э.Король
Техред M.Ìîðãåíòàë Корректор
Редактор В.Данко
Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101
Заказ 1177 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб„4/5
