Звоните! 
 (926)274-88-54 
 Бесплатная доставка. 
 Бесплатная сборка. 
Ассортимент тканей

График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
Читальный зал -->  Программные средства foundation 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 [ 91 ] 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359

обсуждаются в Обзоре литературы. В примере на рис. 4.40(c) мы видим, что существует терм-произведение, который покрывает остающиеся клетки, содержащие 1, в F и G одновременно.

X Y I I

Z\ 00 01 11 10

F = X-Y + ...

- 10

г

х-Y-Z-

Y F-G

G = X-Y + ...

fffl

X Y Z

F = X-Y + X-Y-Z

X Y 2 u.

G = X-Y + X-Y-Z

Рис. 4.40. Карты Карно для совокупности, состоящей издвух функций: (а) карты Л/1Я функций F и G; (Ь) карта для 2-произведения F - G; (с) редуцированные карты для F и G после исключения существенных простых импликант и покрываемых ими единиц

*4.4. Программные методы минимизации

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

Вы знаете, что в случае функций небольшого числа переменных минимизацию можно осуществить визуально, используя карты Карно. В этом параграфе мы покажем, что те же самые операции можно производить (по крайней мере, в принципе) в случае функций со сколь угодно большим числом переменных, используя табличный метод, называемый алгоритмом Куина-Мак-Класки (Quine-McClusky algorithm). Подобно другим алгоритмам, алгоритм Куина-Мак-Класки можно представить в виде программы для компьютера. Как и в методе, основанном на картах Карно, алгоритм выполняется в два шага: (а) нахождение всех простых импликант функции и (Ь) выбор минимального набора простых импликант, который покрывает функцию.

Алгоритм Куина-Мак-Класки часто описывают в терминах заполняемых вручную таблиц и выполняемых вручную проверок. Поскольку, однако, никто никогда не делает этого вручную, для нас более естественно описать данный алгоритм в терминах структур данных и функций на языке профаммирования высокого уровня. Цель этого параграфа заключается в том, чтобы дать представление о сложно-



сти вычислений, производимых при решении большой задачи минимизации. Мы рассматриваем только полностью определенные функции для логических схем с одним выходом; задачи с безразличными комбинациями переменных и со многими выходами решаются на основе алгоритмов, являющихся непосредственной модификацией алгоритма, применяемого в случае схем с одним выходом (см. Обзор литературы).

*4.4.1. Представление термов-произведений

Отправным моментом в алгоритме минимизации Куина-Мак-Класки служит таблица истинности или эквивалентный ей список минтермов для рассматриваемой функции. Если функция задана иначе, то сначала ее необходимо преобразовать в одну из упомянутых форм. Например, в произвольном логическом выражении с п переменными можно разнести множители по слагаемым (возможно, применяя по ходу дела теорему Де Моргана), чтобы придти к выражению вида сумма произведений . Когда такое выражение получено, каждый терм-произведение с р переменными порождает 2 минтермов в списке минтермов.

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

1 - переменная входит в терм-произведение непосредственно; О - переменная входит в терм-произведение в виде дополнения; X - переменная отсутствует в терме-произведении.

Строка из и таких символов служит представлением терма-произведения в виде куба {cube representation). Если, например, число переменных в терме-произведении может доходить до 8 (Х7, Х6.....XI, ХО), то запись термов-произведений в виде

кубов имеет вид:

Х7Х6Х5Х4ХЗХ2Х1 ХО =01101110, ХЗХ2Х1 ХО =хххх1110, Х7 Х5 Х4 ХЗ Х2 XI s 1x01 lOIx, Х6 =х1хххххх.

Заметьте, что, ради удобства, мы назвали переменные именно так, как бывают указаны разряды в и-разрядном двоичном целом числе.

Согласно терминологии параграфа 2.14, где были введены и-мерные кубы и /я-мерные подкубы, строка 1x01101 х представляет собой 2-мерный подкуб 8-мерного куба, а строка 01101110 - 0-мерный подкуб 8-мерного куба. Однако в литературе по минимизации обычно подразумевается, что максимальная размерность куба или подкуба равна и, и поэтому /я-мерный подкуб просто называют /я-мерным кубом или, для краткости, кубом ; в данном параграфе мы будем следовать этой традиции.



Чтобы задать терм-произведение в компьютерной программе, можно воспользоваться структурой данных с п элементами, каждый из которых принимает одно из трех возможных значений. На языке С терм-произведение можно описать следующими объявлениями:

typedef enum {complemented, uncomplemented, doesntappear> TRIT; typedef TRIT[16] CUBE; /* Represents a single product

term with up to 16 variables */

Однако эти объявления не приводят к сколько-нибудь эффективному внутреннему представлению кубов. Как мы увидим дальше, с кубами легче манипулировать, используя обычные компьютерные операторы, если терм-произведение с и переменными представлен в программе двумя и-разрядными словами, как это предлагается сделать в следующем примере:

#define MAX VARS 16 /* Max # of variables in a product term */ typedef unsigned short WORD; /* Use 16-bit words */ struct cube {

WORD t; /* Bits 1 for uncomplemented variables. */ WORD f; /* Bits 1 for complemented variables. */

>;

typedef struct cube CUBE;

CUBE PI, P2, P3; /* Allocate three cubes for use by program. */

Здесь слово WORD - это 16-разрядное двоичное целое; терм-произведение с 16 переменными представлен двумя словами WORD, как показано на рис. 4.41(a). В первом слове в структуре CUBE битом 1 отмечается каждая переменная, входящая в терм-произведение непосредственно [символ t - от trae (истина)]; во втором слове битом 1 отмечается каждая переменная, входящая в терм-произведение в виде дополнения [символ f - от false (ложь)]. Если в каком-то определенном разряде стоит О в обоих словах WORD, то соответствующая переменная отсутствует; наличие 1 в одном и том же разряде в обоих словах WORD не предусматривается. Таким образом, программная переменная Р1 нарис. 4.41(b) представляет собой терм-произведение Р1 =Х15 Х12 Х10 - Х9 Х4 XI ХО. При желании представить логическую функцию F с числом переменных до 16, содержащую не более 100 термов-произведений, мы могли бы объявить массив из 100 структур CUBE:

CUBE F[1003; /* Storage for a logic function

with up to 100 product terms. */

Воспользовавшись описанным представлением куба, можно на языке С кратко и эффективно записать функции, оперирующие термами-произведениями обычным образом. В табл. 4.8 приведены несколько таких функций. В соответствии с двумя из этих функций на рис. 4.42 показано, как можно сравнить два куба и объединить их, если это возможно, согласно теореме Т10: term X + term X = term. Эта теорема говорит о том, что два терма-произведения можно объединить, если они различаются только в одной переменной, которая в один из термов входит в виде дополнения, а в другой - непосредственно. Объе линнно и ,



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 [ 91 ] 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359



ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку.



Звоните! Ежедневно!
 (926)274-88-54 
Продажа и изготовление мебели.


Копирование контента сайта запрещено.
Авторские права защищаются адвокатской коллегией г. Москвы
.