СОДЕРЖАНИЕ
Введение ...............................................................................................................……..
3
1.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОЕКТИРОВАНИЯ ЦИФРОВЫХ УСТРОЙСТВ ..................................................................................................................
5
1.1.
Элементная база цифровых устройств и тенденции ее развития……...........
5
1.2.
Основные положения булевой алгебры……......................………………..….
15
1.3.
Функции алгебры логики и их свойства………………………………………. .......................................................................
17
1.4.
Аналитическая запись функций алгебры логики…………………………….. ........................................................
18
1.5.
Основные классы функций алгебры логики………………………………….. ...................................................……….
26
1.6.
Полные системы функций…………………………………………………….. .......................................……................................………..
29
1.7.
Способы задания функций алгебры логики………................................……..
30
1.8.
Критерии оценки сложности и быстродействия логических схем………….. …............………
31
1.9.
Основные проблемы синтеза логических схем, классификация методов синтеза…………………………………………………………………………..
32
2.
СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ МЕТОДАМИ миниМИЗАЦИИ........................
40
2.1.
Основные понятия и определения………………..…........................................
40
2.2.
Постановка задачи минимизации в классе ДНФ.....................………………..
41
2.3.
Метод Квайна--Мак-Класки.…………..………………..............................…..
43
2.4.
Минимизация неполностью определенных функций алгебры логики…….
51
2.5.
Графические методы минимизации функций алгебры логики.......................
56
2.6.
Приближенные методы минимизации функций алгебры логики...................
61
2.6.1.
Минимаксный метод...........................…………......................................
63
2.6.2.
Метод весовых коэффициентов…………………………......................
69
2.6.3.
Частотно-минимальный алгоритм покрытия......................................
72
2.6.4.
Метод конкурирующих интервалов ………….............................……..
77
2.6.5.
Метод недостаточных импликант и доопределяющих функций…….
86
2.7.
Минимизация систем функций алгебры логики.………..............................…
105
2.8.
Минимизация функций алгебры логики отдельных классов..........................
118
3.
СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ МЕТОДАМИ ДЕКОМПОЗИЦИИ…..................
124
3.1.
Классификация видов композиций.........................................................………
124
3.2.
Простые разделительные композиции.……………...............................………
128
3.3.
Многократные композиции…………………………………………………….
130
3.4.
Дизъюнктивно-конъюнктивное разложение………………………………….
143
3.5.
Декомпозиция систем функций алгебры логики……………………………..
157
3.6.
Сложные разделительные композиции.....……………...............................….
161
3.7.
Неразделительные композиции...........………………...............................…….
165
3.8.
Метод приближающих монотонных функций..................................................
170
3.8.1.
Синтез одновыходных логических схем…..........................……………
171
3.8.2.
Алгоритмы выполнения основных операций..............................……….
175
3.8.3.
Оценка трудоемкости синтеза логических схем методом приближающих монотонных функций.................................…………..
181
3.8.4.
Оценка сложности логических схем, синтезируемых методом
приближающих монотонных функций……………………………..…….
184
3.8.5
Синтез многовыходных логических схем ..............................................
185
4.
ФАКТОРИЗАЦИОННЫЕ МЕТОДЫ СИНТЕЗА ЛОГИЧЕСКИХ СХЕМ..............
209
4.1.
Основные понятия и определения....…………………...............................…...
211
4.2.
Алгоритм пошаговой факторизации...…………………...............................….
211
4.3.
Приближенные алгоритмы факторизации…………………………………….
222
4.4.
Алгоритм пошаговой факторизации системы ФАЛ.........................………….
231
5.
СПОСОБЫ УМЕНЬШЕНИЯ СЛОЖНОСТИ ЛОГИЧЕСКИХ СХЕМ......…………
240
5.1.
Способы уменьшения сложности реализации функций алгебры логики…..
242
5.1.1.
Замена переменных..............................................……………………….
242
5.1.2.
Оценка эффективности замены симметричных переменных……….
247
5.1.3.
Сокращение числа переменных................................................................
249
5.1.4.
Способы определения симметрии переменных…………………………
253
5.1.5.
Совмещение строк и столбцов двумерной таблицы истинности…..
262
5.1.6.
Использование симметрии таблицы истинности...................……….
270
5.2.
Связная реализация многовыходных логических схем......................……….
277
6.
ПРОЕКТИРОВАНИЕ ЛОГИЧЕСКИХ СХЕМ С УЧЕТОМ СВОЙСТВ ЭЛЕМЕНТНОЙ БАЗЫ…..............................................................................................
293
6.1.
Основные этапы проектирования логических схем..........................…………
293
6.2.
Учет свойств функциональных элементов при синтезе логических схем….
299
6.3.
Особенности проектирования логических схем на программируемых логических интегральных схемах.......................................................................
310
6.3.1.
Классификация и особенности программируемых логических
интегральных схем.............................…………………………………..
310
6.3.2.
Обзор методов синтеза логических схем на ПЛИС…..................……
342
6.3.3.
Тривиальная реализация логических схем...............................................
346
6.3.4.
Синтез двухуровневых логических схем......................................………
348
6.3.5.
Синтез многоуровневых логических схем .............…………………….
356
6.3.6.
Синтез логических схем на ПЛИС высокой степени интеграции…..
371
6.4.
Моделирование логических схем ……………………….............…………….
395
6.4.1.
Компилятивный способ моделирования.....................………………….
396
6.4.2.
Событийный способ моделирования………............................………..
398
6.4.3.
Моделирование на уровне логических элементов................…………..
400
7.
Методы синтеза логических схем, реализующих пороговые и симметричные функции алгебры логики.............
407
7.1.
Основные понятия и определения.................................................…………...
408
7.2.
Синтез схем симметричных функций методом декомпозиции...…………..
412
7.3.
Факторизационные методы синтеза схем пороговых равновесных функций...............….................................................…………………………..
425
7.3.1.
Первичная факторизация пороговых равновесных функций...............
425
7.3.2.
Вторичная факторизация систем пороговых равновесных функций
437
7.4.
Факторизационные методы синтеза схем элементарных симметричных функций……………...........................................................................................
450
7.5.
Быстродействие схем, реализующих симметричные функции алгебры логики..................................................................................................................
458
7.5.1.
Быстродействие схем, реализующих пороговые равновесные функции алгебры логики….......................................................................
459
7.5.2.
Быстродействие схем, реализующих элементарные симметричные функции алгебры логики.........…………....................
463
7.6.
Синтез пороговых схем методами декомпозиции и факторизации..............
467
7.7.
Синтез схем монотонных операторов............................……..........................
472
7.8.
Синтез схем пороговых равновесных функций комбинаторными методами……………………………………………………………………….
476
8.
Синтез схем симметричных функций методом промежуточного преобразования..........................................................
489
8.1.
Способы реализации параллельных счетчиков.................…..........................
489
8.2.
Синтез схем, реализующих пороговые равновесные функции алгебры логики……………………..................................................................................
494
8.3.
Синтез схем, реализующих элементарные симметричные функции алгебры логики…...............................................................................................
496
8.4.
Синтез схем пороговых равновесных функций методом частичного промежуточного преобразования...……..........................................................
499
8.5.
Синтез схем элементарных симметричных функций методом частичного промежуточного преобразования.............………............................................
504
8.6.
Синтез схем пороговых равновесных функций комбинированным методом…...........................................................................................................
509
8.7.
Синтез схем элементарных симметричных функций комбинированным методом…...........................................................................................................
513
8.8.
Быстродействие схем симметричных функций, синтезируемых методом промежуточного преобразования………….…………………………………
519
8.8.1.
Быстродействие схем, реализующих пороговые равновесные функции………………………………………………………………..
520
8.8.2.
Быстродействие схем, реализующих элементарные симметричные функции….....................................................................
522
8.9.
Синтез пороговых схем методом промежуточного преобразования …….
524
8.10.
Синтез пороговых схем методом частичного промежуточного
преобразования …..............................................................................................
533
8.11.
Синтез пороговых схем комбинированным методом....................................
536
9.
Однородные и регулярные структуры для реализации симметричных функций алгебры логики.……..................................
539
9.1.
Однородные и регулярные треугольные структуры для реализации пороговых равновесных функций....................................................................
539
9.2.
Регулярные матричные структуры для реализации пороговых равновесных функций........................................................................................
544
9.3.
Однородные симметричные древовидные структуры для реализации пороговых равновесных функций …...............................................................
546
9.4.
Комбинированные однородные симметричные структуры для реализации пороговых равновесных функций ….........................................
564
9.5.
Однородные и регулярные структуры для реализации элементарных симметричных функций …...............................................................................
570
10.
Методы синтеза логических схем модульного контроля двоичных кодов……………………………………………………………….
572
10.1.
Методы синтеза логических схем модульного контроля в унитарных позиционных двоичных кодах…......................................................................
572
10.1.1.
Основные понятия и определения…....................................................
572
10.1.2.
Декомпозиционный метод синтеза логических схем подсчета количества единиц параллельного двоичного кода по модулю К…..
574
10.1.3.
Факторизационный метод синтеза логических схем подсчета количества единиц параллельного двоичного кода по модулю К…..
582
10.1.4.
Методы синтеза логических схем формирования остатка двоичного кода по модулю К .........................................…...................
589
10.1.5.
Быстродействие логических схем модульного контроля в унитарных параллельных позиционных двоичных кодах…................
595
10.2.
Методы синтеза логических схем модульного контроля в унитарных непозиционных двоичных кодах……………………………………………..
598
10.2.1.
Основные понятия и определения....……………..........……………..
598
10.2.2.
Синтез логических схем подсчета количества единиц двоичного кода по модулю К методом декомпозиции .........................................
599
10.2.3.
Синтез логических схем подсчета количества единиц двоичного кода по модулю К методом первичной факторизации ………………
604
10.2.4.
Синтез логических схем подсчета количества единиц двоичного кода по модулю К методом вторичной факторизации……….........
612
10.2.5.
Однородные и регулярные структуры подсчета количества единиц двоичного кода по модулю К в унитарном параллельном непозиционном коде…………………………………………………..
619
10.2.6.
Методы синтеза логических схем формирования остатка двоичного кода по модулю К в унитарном параллельном непозиционном коде .................…………………………………….....
625
10.2.7.
Быстродействие логических схем модульного контроля в
унитарных параллельных непозиционных кодах…………………….....
630
10.3.
Методы синтеза логических схем модульного контроля в натуральных двоичных кодах ….............................................................................................
633
10.3.1.
Синтез логических схем формирования остатка двоичного кода по модулю К методом последовательной свертки……………………
633
10.3.1.1. Свертка равновесных разрядов кода блоками сложения по модулю два ...….........................................................................
634
10.3.1.2. Свертка равновесных разрядов кода с использованием параллельного счетчика ..............................................................
635
10.3.1.3. Свертка разрядов кода многоразрядными сумматорами ...………………………………………..........................................
637
10.3.1.4. Свертка разрядов кода блоками модульного сложения ……………………………………………………………………
637
10.3.1.5. Свертка c использованием отрицательных весов разрядов входного кода …............................................................
641
10.3.1.6. Свертка равновесных разрядов кода блоками подсчета числа единиц по модулю К …………………………………………..
652
10.3.1.7. Комбинированные способы свертки двоичных кодов по модулю К ………………………………………………………………...
653
10.3.2.
Синтез схем формирования кода остатка по модулю К .................
653
10.3.2.1. Синтез блока формирования кода остатка по модулю К методом последовательного расширения и свертки.........................
653
10.3.2.2. Синтез блока формирования кода остатка по модулю К методом прямого формирования вычетов ........................................
660
10.3.2.3. Синтез блока формирования кода остатка по модулю К с использованием отрицательных весов разрядов.............................
662
10.3.2.4. Синтез блока формирования кода остатка по модулю К комбинированными методами...............…...…………………………
663
10.3.3.
Синтез логических схем подсчета количества единиц двоичного кода по модулю К методом промежуточного преобразования……
668
10.3.4.
Оценки сложности и быстродействия схем модульного контроля в натуральных двоичных кодах….........................................................
668
11.
Методы синтеза модульных сумматоров…………………………..
673
11.1.
Синтез модульных сумматоров в унитарных позиционных двоичных кодах …...............................................................................................................
674
11.2.
Синтез модульных сумматоров в унитарных непозиционных двоичных кодах…................................................................................................................
678
11.3.
Синтез сумматоров по модулю К в натуральном двоичном коде………….
684
11.3.1.
Синтез сумматоров по модулю К методом промежуточного преобразования в унитарный параллельный позиционный код……..
685
11.3.2.
Синтез сумматоров по модулю К методом промежуточного преобразования в унитарный параллельный непозиционный код…..
690
11.3.3.
Синтез сумматоров по модулю К методом прямого формирования вычетов…......................................................................
696
11.3.4.
Синтез сумматоров по модулю К методом свертки с коррекцией……………………………………………………………..
700
11.3.5
Реализация сумматоров по модулю К на основе полиномиальных представлений…………………………………………………………
706
11.3.6.
Синтез сумматоров по модулю К методом частичной реализации таблицы сложения…………………………………………………….
708
11.3.7.
Синтез сумматоров по модулю К универсальными методами……
711
11.3.7.1. Синтез сумматоров по модулю К методом минимизации.
712
11.3.7.2. Синтез сумматоров по модулю К методом приближающих монотонных функций……………………………....
714
11.3.8.
Анализ сложности и быстродействия сумматоров по модулю К..
718
12.
Методы синтеза устройств модульного умножения….………
723
12.1.
Синтез устройств умножения по модулю К в унитарных позиционных двоичных кодах ….............................................................................................
723
12.2.
Синтез устройств умножения по модулю К в унитарных непозиционных двоичных кодах…......................…....................................................................
727
12.3.
Синтез устройств умножения по модулю К в натуральном двоичном коде
733
12.3.1.
Синтез устройств модульного умножения методом промежуточного преобразования в унитарный параллельный позиционный двоичный код…………………………………………..
733
12.3.2.
Синтез устройств модульного умножения методом промежуточного преобразования в унитарный параллельный непозиционный двоичный код…………&helli