Устройство для сжатия чисел и вычисления полинома

Устройство для сжатия чисел и вычисления полинома

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях. Цель изобретения состоит в расширении области применения за счет дополнительной возможности сжатия чисел. Устройство содержит два регистра, два коммутатора, две группы элементов задержки, сумматор, сумматор произведений, группу умножителей. Сущность изобретения состоит в реализации возможности производить сжатие исходных чисел за счет уменьшения количества значащих двоичных разрядов, требуемых для представления сжатых чисел в сравнении с исходными, при этом устройство осуществляет сжатие на основе соотношения (макс(а|)+ 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