Устройство для перебора перестановок

Устройство для перебора перестановок

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

<о748416 (61) Дополнительное к авт. саид-ву— (22) Заявлено 090678 (21) 2630419/18-24 (51)м, кл.2 с присоединением заявки ¹

G 06 F 15/20

Государственный комитет

СССР по делам изобретений и открытий (23) Приоритет

Опубликовано 150780, Бюллетень ¹ 26

Дата опубликования описания 1507.80 (53) УДК 681. 327 (088 ° 8) (72) Авторы изобретения

С. Н. Борисов, О. В. Викторов, Л. Н. Минина и A. М. Романкевич

Киевский ордена Ленина политехнический институт имени 50-летия Великой Октябрьской социалистической еволю ии (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА IIEPECTAHOBOK

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

Известно устройство для перебора перестановок, содержащее счетчики, схемы ИЛИ и И (1).

Недостатком его является большая сложность.

Наиболее близким по своей технической сущности к данному изобрете- 15 нию является устройство для перебора сочетаний, содержащее в каждом из и разрядов регистр, элементы И, ИЛИ, элемент задержки, причем вход первого элемента И соединен с тактовым 20 входом устройства, а выход его подключен к тактовому входу регистра того же разряда, информационный вход которого соединен с первым входом второго элемента И того же разряда 25 и с выходом элемента ИЛИ следующего разряда, выход регистра каждого разряда соединен с первым входом третьего элемента И того же разряда, выход которого соединен с первым входом 30

2 элемента ИЛИ того же разряда, второй вход которого подключен к выходу второго элемента И того же разряда, устройство содержит, кроме того, дополнительный регистр, тактовый вход которого является тактовым входом устройства, информационный вход которого подключен к выходу элемента ИЛИ первого разряда, а выход дополнительного регистра соединен с первым входом второго элемента И последнего разряда (21 .

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

Целью изобретения является повышение быстродействия.

Цель достигается тем, что каждый

-тый (= 1,... n ) разряд устройства содержит счетчик по модулю i + 2 и четвертый элемент И, первый и второй инверсные входы которого соединены с выходами счетчика соответственно последующего и предыдущего разрядов, третий выход четвертого элемента И каждого разряда через соответствующий элемент задержки подклюиен к тактовому входу устройства,высод счетчика каждого разряда соединен

748416 со вторым инверсным входом первого и третьего элементов И и со вторым входом второго элемента И того же разряда, причем выходы счетчиков первого и последнего разрядов и разрядные выходы регистров являются выходами устройства.

На чертеже представлено устройствб для перебора перестановок (дляп=4)

Устройство содержит регистр 1, элемент И 2, элемент ИЛИ 3, элемент И 4, счетчик 5, элемент И б, тактовый вход 7, элемент 8 задерж ки, элемент И 9, разрядные выходы 10 регистров, выходы 11 счетчика последнего разряда, выход 12 счетчика первого разряда, вспомогательный регистр 13.

Устройство работает следующим образом.

Перед началом работы но все пять регистров 1 заносятся коды переставля емых величин, счетчики 5 сбрасываются н состояние О, вследствие чего открываются элементы И 2 и И б, запираются элементы И 4 и выходы регистров 1 подключаются ко входам соседних слева регистров 1, причем выходы первого регистра 1 подключаются ко входам пятого регистра 1, запираются элементы И 9 и на нходы счетчиков по модулю 5, 4, 3 тактойые импульсы не поступают.

Работа устройства начинается с подачей на вход 7 серии тактовых сигналов.

Величины задержек элементон задержки, подключенных соответственно к счетчикам 5 по модулю б, 5, 4, выбираются таким образом, чтобы они удовлетворяли соотношению: т > VOÌ: >т.

Б 4

)-, О, вследствие чего на счетчик 5 по модулю б тактовые импульсы начинают поступать с запаздыванием на С =в (где: m (f, ® — длительность тактового импульса)

При поступлении тактовых сигналон на регистры 1 коды, записанные н них через элементы И 2 и ИЛИ 3, сдвигаются в соседние слева регистры 1, причем из первого регистра 1 сдвиг происходит н пятый регистр.

После поступления на счетчик 5 по модулю 5 пяти тактовых импульсов на его выходе появляется единичный сигнал, который запрещает считывание кодов из регистра 1, откры- вает элемент И 9 и на его счетчик 5 пб модулю 5 проходит 1 тактовый им-! пульс, запирает соответствующие элементы И 2 и И б, отпирает соответствующие элементы И 4, вследствие чего цепь из пяти регистров замыкается в обход пятого""регистра i.

С приходом шестого тактово о имйульса йа счетчик 5 по модулю б, если нет запрета с выхода счетчика 5 по модулю 5, счетчик сбрасынается в состоявшие О, закрывая при этом элемент И 9, подключенный ко входу счетчика 5 по модулю 5.

Когда на вход счетчика 5 по Мо дулю 5 поступит 4 тактовых импульса, на выходе этого счетчика .появится единичный сигнал. Этот сигнал запрещает подачу следующего тактового сигнала на счетчик 5 по модулю б, запирая схему И 9, подключенную к его входу, разрешает подачу следующего тактового сигнала на счетчик 5 по модулю 4, элемент И 9, подключенный к его входу, открывает, запирает соответствующие элементы И 2 и.И б, отпирает соответствующие элементы

И 4, вследствие чего цепь из пяти

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

2О С приходом следующего тактового импульса на счетчик 5 по модулю 5, если нет запрета с выхода счетчика 5 по модулю 4, счетчик сбрасывается в состояние О, открывая при этом элемент И 9, подключенный ко входу счетчика 5 по модулю б, и счетчик 5 по модулю б сбрасывается .в состояние О. .После поступления на счетчик 5 по модулю 4 трех тактовых импульсов на его выходе появляется единичный сигнал. Этот сигнал запрещает подачу следующего тактового импульса на счетчик 5 по модулю 5, 3S запирая элемент И 9, подключенный к его входу, разрешает подачу следующего тактового сигнала на счетчик

5 по модулю З,открывая элемент И 9, подключенный к его входу, запирает соответствующие элемента И 2 и И 6, Щ отпирает соответствующие элементы

И 4, вследствие чего цепь иэ пяти реристров 1 замыкается н обход пятого, четвертого и третьего регистров 1, выходной сигнал со счетчика 5 по мо45 дулю 6 запрещает считывание кодов иэ регистров 1.

С приходом следующего тактового импульса на счетчик 5 по модулю 4, если нет запрета с выхода счетчика по модулю 3, он сбрасывается в состояние

О, открывая элемент И 9, подклюЧенный ко нходу счЕтчика 5 по модулю 5. После этого сбрасываются в состояние

О счетчик 5 по модулю 5 и счетчик 5 по модулю б.

После поступления двух тактовых импульсов на вход счетчика 5 по модулю З,на его выходе появляется единичный сигнал. Этот сигнал запрещает подачу следующего тактового сигнала на

I. счетчик 5 по модулю 4,запирая элемент

И 9, подключенный к его входу, запирает соответствующие элементы И 2, отпирает соответствующий элемент И 4

1 I( вследстние чего коды с выходов перво748416

2 1 О

1 О

2 О

2 1 1 О

2 1 2 О

2 1 3

2 1 4

2 1 5

2 2 О

2 2 1

2 2 2

2 2 3

О О

2 2 4

2 2 5 1

2 3 О О

2 3

2 3 2

2 3 3

2 3 4

2 3 5

2 4 5

Э 4 5

О О О

О 0 1

О О 2

О О 3

О О 4

0 О 5

4 1

5 1

5 1

О 1 О

О 1 1

О 1 2

О 1 3

О 1 4

О 1 5

О 2 0

0 2 1

О 2 2

О 2 3

О 2 4

0 2 5

О 3 О

О 3 1

1 . 1

1

1

О 3 2

О 3 3

О 3 4

О 3 5

О 4 5

1 О О

1 О 1

1 О 2

1 О 3

1 0 4

1 О 5

1 1 О

1 1 1

1 1 2

1 1 3

1 1 4

1 1 5

1 2 О

1 2 1

1 2 2

1 2 3

О

О

О

О

О

О

О

О

О

О

1 2 4

1 2 5

1 3 О

1 3 1

1 3 2

1 3 3

1 3 4

ro регистра 1 передаются на их же входы.

Кроме того, сигнал с выхода счетчика 5 по модулю 3 поступает на выход 12.

Работа устройства поясняется приме- 5 ром перестановки пяти кодов.

Ниже даны состояния соответственно первого, второго... пятого регистров

1, счетчиков 5 по модулям 3, 4, 5, б, выхода 11, запрещающего считывание )0 кодов из регистров на каждом такте.

О 1 2 3 4 5 О О О О О

1 2 3 4 5 1 О О О 1 О

2 3 4 5 1 2 О О О 2 О

3 4 5 1. 2 3 О О О 3 0

4 5 1 2 3 4 О О О 4 О

5 1 2 3 4 5 О О О 5 1 б 2 3 4 1 5 О О 1 О О

7 3 4 1 5 2 О О 1 1 О

8 4 1 5 2 3 О О 1 2 О

9 1 5 2 3 4 О О 1 3 О 2О

10 5 2 3 4 1 О О 1 4 О

11 2 3 4 1 5 О О 1 5 1

12 3 4 1 2 5 О О 2 О О

17 3 4 1 2 5 О О 2 5 1

19 1 2 3 5 4 О О 3 1 О 30

20 2 3 5 4 1 О О 3 2 О

21 3 5 4 1 2 О О 3 3 О

22 5 4 1 2 3 О О 3 4 О

23 4 1 2 3 5 О О 3 5 1

24 1 2 3 4 5 О О 4 5 1 - 35

25 2 3 1 4 5 О 1 0 О О

29 5 2 3 1 4 О 1 0 4 О

30 2 3 1 4 5 О 1 О 5 1

31 31 4 2 5 О 1 1 О О

32 1 4 2 5 3 0 1 1 1 О

33 4 2 5 3 1 О 1 1 2 О

34 2 5 3 1 4 0 1 1 3 О

35 5 3 1 4 2 О 1 1 4 О

36 31 4 2 5 О 1 1 5 1

38 4 2 3 5 1 О 1 2 1 О

39 2 3 5 1 4 0 1 2 2 0

40 3 5 1 4 2 О 1 2 3 0

41 5 1 4 2 3 О. 1 2 4 О

42 1 4 2 3 5 О 1 2 5 1

44 2 3 1 5 4 0 1 3 1 О

45 31 5 4 2 0 1 3 2 О

46 1 5 4 2 3 О 1 3 3 О

47 5 4 2 3 1 О 1 3 4 О

48 4 2 3 1 5 О 1 3 5 1

49 2 3 1 4 5 О 1 4 5 1

50 3 1 2 4 5 О 2 О О О, 60

51 1 2 4 5 3 О 2 О 1 О

52 2 4 5 3 1 О 2 О 2 О

53 4 5 3 1 2 О 2 О 3 О

54 5 3 1 2 4 О 2 О 4 О

55 3 1 2 4 5 О 2 О 5 1 65

56 1,2

57 2 4

58 4 3

59 3 5

60 51

61 1 2

62 24

63 4 3

64 31

65 1 5

66 5 2

67 2 4

68 4 3

69 31

70 1 2

71 25

72 5 4

73 4 3

74 3 1

75 1 2

76 21

77 1 3

78 3 4

79 4 5

80 5 2

81 21

82 1 3

83 3 4

84 4 2

85 25

86 51

87 1 3

88 34

89 4 2

90 2 1

91 1 5

92 5 3

93 34

94 4 2

95 21

96 1 3

97 3 5

98 5 4

Р9 4 2

100 2 1

101 1 Э

102 3 2

103 2 4

104 4 5

105 5 1

106 1 3

107 3 2

108 2 4

109 4 1

110 1 5

111 5 3

112 3 2

113 2 4

114 4 1

115 1 3

116 3 5

f17 5 2

118 2 4

119 4 1

120 1 3

121 3 2

122 2 5.

123 5 4

4 3

3 5

5 1

1 2

2 4

4 3

3 1

1 5

5 2

2 4

4 3

3 1

1 2

2 5

5 4

4 3

3 1

1 2

2 4

3 4

3 4

4 5

5 2

2 1

1 3

3 4

4 2

2 5

5 1

1 3

3 4

4 2

2 1

1 5

5 3

3 4

4 2

2 1

1 3

3 5

5 4

4 2

2 .1

1 3

3 4

2 4.

4 5

5 1

1 3

3 2

2 4

4 1

1 5

5 3

3 2

2 4

4 1

1 3

3 5

5 2

2 4

4 1

1 3

3 2

2 5

5 4

4 1

1 3

748416

Прототип предлагаемого изобретения обеспечивает перебор всех и! перестановок из и кодов за * тактов (в случае для 5 чисел — 3125 тактов).

По сравнению с прототипом, предлагаемое устройство обеспечивает перебор всех и! перестановок из и кодов за

f Ятактов (в случае для 5 чисел — 153 такта).

Формула изобретения

Устройство для перебора перестановок, содержащее вспомогательный регистр, и также в каждом из и разрядов регистр, элементы И, ИЛИ, элемент

124 4

125 1

126 3

127 2

128 1

129 4

130 5

131 3

132 2

133

134 4

135 3

136 5

137 . 2

138

139 4

140 3 141 2

142 5

143 1

144 4

145 3

146 2

147 1

148 5

149 4

150 3

151 2

152 1

153 1

1 3

3 2 г

1 4

4 5

5 3

3 2

2 1

1 4

4 3

3 5

5 2

2 1

1 4

4 3

3 2

2 5

5 1

1 4

4 3

3 2

2 1

1 5

5 4

4 3

3 2

2 1

2 3

2 3

2 5 1 1

4 5 1 1

4 5 1 2

5 3 1 2

3 2 1 2

2 1 1 2

1 4 1 2

4 5 1 2

3 5 i

5 2 1 2

2 1 1 2

1 4 1 2

4 3 1 2

3 5 1 2

2 5 1 2

5 1 1 2

1 4 1 2

4 3 1 2

3 2 1 2

2 5 1 2

1 5 1 2

5 4 1 2

4 3 1 2

3 2 1 2

2 1 1 2

1 5 1 2

4 5 1 2

4 5 1 3

4 5 2 3

4 5 0 0

3 5 1

4 5 1

0 0 0

0 1 0

0 2 0

0 3 0

0 4 0

0 5 1

0 0

1 2 0

3 0

l 4 0

1 5 1

2 0 0

2 1 0

2 2 0

2 3 0

2 4 0

2 5 1

3 0 0

3 1 0

3 2 0

3 3 0

3 4 0

3 5 1.

4 5 1

4 5 1

4 5 1

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

20 входом второго элемента И последнего разряда, отличающийся тем, что, с целью повышения быстродействия, каждый i -тый (i = 1,...>) разряд устройства содержит счетчик по модулю + 2, четвертый элемент И, первый и второй инверсные входы которого соединены с выходами счетчика соответственно последующего и предыдущего разрядов, третий выход четвертого элемента Й каждого разряда через соответствующий элемент задержки подключен к тактовому входу устройства, выход счетчика каждого раз)ряда соединен со вторым инверсным входом первого и третьего элементов

И и со вторым вЛ дом второго элемента И того же разряда, причем выходы счетчиков первого и последнего разрядов и разрядные выходы регистров являются выходами устройства.

Источники информации, принятые во внимание при экспертизе . 1. Авторское свидетельство СССР

Ф 374606, кл. G 06 F .7/00, 1970.

2. Авторское свидетельство СССР

9 446057, кл. 6 06 Р 7/38,от 2211,72.

74841б

Составитель E.,Ïóïûðåâ

Редактор Т. Лошкарева Техред A.Ùåïàíñêàÿ

Корректор М. Коста

Заказ 4241/37 Тираж 751

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Х-35, Раушская наб., д. 4/5

Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4