Доказательство таблицы истинности дистрибутивного закона

На рис. 1.8, а—е приведены иллюстрации к основным логи­ческим операциям и их композициям (так называемые диа­граммы Эйлера — Венна) — области истинности каждого из высказываний и их объединения (дизъюнкции), пересечения (конъюнкции) и других операций. «Первый» из законов де Мор­гана иллюстрируется рис. 1.8, д, е.

Операции над битовыми строками. В некоторых современных ЯП реализованы операции и/или функции обработки битовых строк (машинных слов, их частей или групп, которые могут со­держать числовые, символьные, мультимедийные и пр. данные). Наиболее распространенными являются побитовые операции, прямо вытекающие из рассмотренных ранее операций над логи­ческими данными (табл. 1.21).

Рис. 1.8. Некоторые примеры диаграмм Эйлера — Венна:

а — конъюнкция высказываний А и В (AND); б — дизъюнкция высказываний А и В

(or); в — исключающая дизъюнкция (xor); г — разность высказываний (А — В);

д — иллюстрация к законам де Моргана (дополнение пересечения высказываний);

е — иллюстрация к законам де Моргана (объединение дополнений)

Таблица 1.21. Операнды и результаты некоторых побитовых операций

 

X	У	х & у	X v у	X IMP y	.x EQV y	х XOR y

Логические операции.

NOT. Поразрядный оператор not (he), или дополнение, является одноместной операцией, которая выполняет логическое отрицание на каждом бите, формируя дополнение данного би­нарного значения. Биты, содержавшие бывшие «0», устанавлива­ются в «1»_{; и} наоборот. Например:

1000 = NOT 0111

Во многих языках программирования (включая С), пораз­рядный оператор not обозначается как «~» (тильда). Этот оператор не следует путать с «логическим отрицанием» («!» — восклицательный знак), который обрабатывает все значение как отдельное булевское.

OR. Побитовый оператор OR (или, «включающее или») об­рабатывает две битовые строки равной длины и создает третью (той же длины), где каждый бит является результатом опера­ции «включающее или» над каждой парой входных битов. Например:

0111 = 0101 OR 0011

В ЯП С поразрядный оператор OR обозначается символом «|» (вертикальная черта). Его булевский аналог обозначается как «||».

XOR («исключающее или») выполняет логическую операцию XOR на каждой паре соответствующих битов двух строк оди­наковой длины. Например:

0110 = 0101 XOR 0011

В ЯП С поразрядный оператор XOR обозначается как «^» («крышка»).

Ассемблерные программисты иногда используют операцию XOR как краткую команду обнуления значения регистра. Выпол­нение XOR над двумя одинаковыми значениями всегда дает нуль в результате, и во многих архитектурах эта операция требует меньшего количества циклов центрального процессора, чем по­следовательность операций, которые загружают нулевое значе­ние в регистр.

AND. Поразрядный and (и) выполняет логическую опера­цию AND на каждой паре соответствующих битов двух битовых строк. Например:

0001 = 0101 AND ООН

В ЯП С поразрядный оператор and обозначается как «&» (амперсанд). Булевский аналог записывается как «&&» (два ам-персанда).

Битовые сдвиги (bit shifts). Эти операции также осу­ществляются на битовом уровне и являются унарными. В этих операциях биты сдвигаются в регистре (влево или вправо). По­скольку регистры компьютера имеют ограниченный размер, не­которые биты будут «выдвинуты из регистра» с одной из его сто­рон, и аналогичное число бит должно быть «вдвинуто в регистр» с другой. Основное различие в операциях битовых сдвигов за­ключается в том, как именно они обрабатывают эти «вдвиги/вы-двиги».

Арифметический сдвиг. При арифметическом сдвиге аннулируются биты, которые сдвинуты из любого конца регист­ра. Однако при арифметическом сдвиге влево с правой стороны вдвигаются нули, а при сдвиге вправо знаковый разряд остается в крайнем правом разряде, сохраняя знак операнда (рис. 1.9, а, б). Арифметический сдвиг влево на п разрядов эквивалентен умно­жению на 2" (если не происходит переполнения), в то время как арифметический сдвиг вправо на п эквивалентен делению на 2".

Логический сдвиг. При логическом сдвиге аннулируют­ся биты, которые сдвинуты, и их место занимают нули (в любом конце регистра) — рис. 1.9, в, г. Поэтому, логический и арифме­тический сдвиги влево оказываются тождественными. Однако логический сдвиг вправо вставляет биты со значением «0» вместо копии знакового разряда. Следовательно, логический сдвиг является более подходящим для двоичных чисел без знака, в то время как арифметический сдвиг — для двоичных со знаком

Рис. 1.9. Битовые сдвиги:

а — арифметический сдвиг вправо; б — арифметический сдвиг влево; в — логи­ческий сдвиг вправо; г — логический сдвиг влево; д — правый циклический сдвиг (вращение); е — левый циклический сдвиг; ж — правый циклический сдвиг через перенос; з — левый циклический сдвиг через перенос

Циклический сдвиг или разрядное вращение. В этой операции биты, «выдвигаемые» из регистра в любую сторону, «вдвигаются» в регистр с другой его стороны (рис. 1.9, д, е). Эта операция используется, если необходимо сохранить все сущест­вующие биты, и часто применяется в цифровой криптографии.

Циклический сдвиг «через перенос». В отличие от обычного сдвига (или сдвига «не через перенос») здесь считает­ся, что два конца регистра отделены флажком переноса («п» на Рис. J.9, ж, з). Бит, который «вдвинут» (с любой стороны реги­стра), — старое значение флажка переноса, а бит, который «вы­двинут» (с противоположной стороны) становится новым значением флажка переноса. Единичный сдвиг через перенос может моделировать логиче­ский или арифметический сдвиг позиции, устанавливая флажок переноса заранее. Например, если флажок переноса содержит «О», то правый сдвиг через перенос соответствует логическому сдвигу вправо, а если флажок переноса содержит копию знако­вого разряда, то это арифметический сдвиг. Поэтому некоторые микроконтроллеры имеют только команды циклического сдвига. Циклический сдвиг через перенос особенно полезен, если опе­рация осуществляется над числами, большими разрядности про­цессора (двойной или более длины). Если число хранится в двух регистрах, то бит, который «выдвинут» из первого регистра, дол­жен быть «вдвинут» во второй. В данном случает этот бит сохра­няется во флажке переноса в течение первого сдвига и готов к участию во втором сдвиге без какой-либо дополнительной под­готовки.

Битовые манипуляции. Кроме перечисленных команд, существует большая группа операций, в том или ином виде реали­зованная в различных процессорах и объединяемая под общим названием «битовые манипуляции/жонглирование» (bit manipu­lation, bit twiddling, bit bashing). Эти операции связаны с задачами обнаружения и коррекции ошибок, алгоритмами шифрации дан­ных и оптимизации, обработки мультимедийных данных и пр. Например, в ЦП Motorolla 68000 — это команды bset (установка битов в «1»), BCLR (установка битов в «0») и btst (переустановка нулевых битов); в системе команд SSE4 — это popcnt («Population Count» — подсчет количества битов, например уста­новленных в «1») и т. д.

В процессорах архитектуры К10 (AMD) добавлен функцио­нальный (исполнительный) блок расширенных битовых манипуляций — Advanced Bit Manipulation (ABM) — см. рис. 3.33.

Синтез и оптимизация схем

При построении схемы, реализующей произвольную таблицу истинности, каждый выход анализируется (и строится схема) от­дельно. Для реализации таблицы истинности с помощью логиче­ских элементов «И» достаточно рассмотреть только те строки таблицы истинности, которые содержат логические «1» в выход­ном сигнале. Строки, содержащие в выходном сигнале логический «0», в построении схемы не участвуют. Каждая строка, со­держащая в выходном сигнале логическую «1», реализуется схе­мой логического «И» с количеством входов, совпадающим с количеством входных сигналов в таблице истинности. Входные сигналы, описанные в таблице истинности логической «1», пода­ются на вход этой схемы непосредственно, а входные сигналы, описанные в таблице истинности логическим «0», подаются на вход через инверторы. Объединение сигналов с выходов схем, реализующих отдельные строки таблицы истинности, произво­дится с помощью схемы логического «ИЛИ». Количество входов в этой схеме определяется количеством строк в таблице истинно­сти, в которых в выходном сигнале присутствует логическая «1». Рассмотрим конкретный пример. Пусть необходимо реализо­вать таблицу истинности, приведенную в табл. 1.22.

Для построения схемы, реализующей сигнал у₁, достаточно рассмотреть строки, выделенные светлой штриховкой. Эти стро­ки реализуются сборкой (микросхемой) S₂ на рис. 1.10. Каждая строка реализуется своей схемой «И», затем выходы этих схем объединяются. Для построения схемы, реализующей сигнал у₂, достаточно рассмотреть строки, выделенные более темной штри­ховкой. Эти строки реализуются сборкой S₃. Инвертирование входов схемы осуществляется сборкой S₁.

Преобразования логических формул. Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упроще­ния формул или приведения их к определенному виду путем использования основных законов алгебры логики.

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

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

 

Практическая работа 6 -7-8. Регистры процессора. Память.

ЦЕЛЬ РАБОТЫ

Приобретение навыков работы с регистрами процессора. и памятью.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Прочитать методические указания 1, 2
2. Разобрать приведенные примеры 1, 2
3. Выполнить задания к работе 1 и 2
4. Ответить на контрольные вопросы 1, 2

Оформите отчет, который должен содержать:

- титульный лист (см. приложение);

-постановку задачи;

-формулировка варианта задания.

-размещение данных в ОЗУ.

-программа в форме таблицы

-последовательность состояний регистров ЭВМ при выполнении программы в режиме Шаг для одного значения аргумента.

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ 1

Для решения с помощью ЭВМ некоторой задачи должна быть разработана программа. Программа на языке ЭВМ представляет собой последовательФзность команд. Код каждой команды определяет выполняемую операцию, тип

адресации и адрес. Выполнение программы, записанной в памяти ЭВМ, осуществляется последовательно по командам в порядке возрастания адресов команд или в порядке, определяемом командами передачи управления.

Для того чтобы получить результат выполнения программы, пользователь должен:

□ ввести программу в память ЭВМ;

□ определить, если это необходимо, содержимое ячеек ОЗУ и РОН, содержащих исходные данные, а также регистров 1R и BR;

□ установить в PC стартовый адрес программы;

□ перевести модель в режим Работа.

Каждое из этих действий выполняется посредством интерфейса модели, описанного в главе 8. Ввод программы может осуществляться как в машинных кодах непосредственно в память модели, так и в мнемокодах в окно Текст программы с последующим ассемблированием.

Цель настоящей лабораторной работы — знакомство с интерфейсом модели ЭВМ, методами ввода и отладки программы, действиями основных классов команд и способов адресации. Для этого необходимо ввести в память ЭВМ и выполнить в режиме Шаг некоторую последовательность команд (опреде­ленную вариантом задания) и зафиксировать все изменения на уровне про­граммно-доступных объектов ЭВМ, происходящие при выполнении этих команд.

Команды в память учебной ЭВМ вводятся в виде шестиразрядных десятич­ных чисел (см. форматы команд на рис. 8.3, коды команд и способов адреса­ции в табл. 8.2—8.4).

В настоящей лабораторной работе будем программировать ЭВМ в машинных кодах.

Пример 1

Дана последовательность мнемокодов, которую необходимо преобразовать в машинные коды, занести в ОЗУ ЭВМ, выполнить в режиме Шаг и зафиксировать изменение состояний программно-доступных объектов ЭВМ (табл. 9.1).

 

					Таблица 9.1.	Команды и коды
Последовательность	Значения
Команды	RD#20	WR30	ADD	#5		WR@30		JNZ 002
Коды	21 1 020	22 0 030	23 1			22 2 030		12 0002

 

Введем полученные коды последовательно в ячейки ОЗУ, начиная с адреса 000. Выполняя команды в режиме Шаг, будем фиксировать изменения про­граммно-доступных объектов (в данном случае это Асе, PC и ячейки ОЗУ 020 и 030) в табл. 9.2.

Таблица 9.2. Содержимое регистров

 

PC	Асc	М(30)	М(20)	PC	Асc	М(30)	М(20)

Задание 1

1. Ознакомиться с архитектурой ЭВМ

2. Записать в ОЗУ "программу", состоящую из пяти команд— варианты задания выбрать из табл.. Команды разместить в последовательных ячейках памяти.

3. При необходимости установить начальное значение в устройство ввода IR.

4. Определить те программно-доступные объекты ЭВМ, которые будут изменяться при выполнении этих команд.

№	IR	Команда 1	Команда 2	Команда 3	Команда 4	Команда 5
		IN	MUL #2	WR10	wr @10	JNS 001
	X	RD #17	SUB #9	WR16	WR @16	JNS 001
		IN	ADD #16	WR8	WR @8	JS 001
	X	RD #2	MUL #6	WR 11	WR @11	JNZ 00
		IN	WR8	DIV #14	WR @8	JMP 002
	X	RD #4	WR 11	RD @11	ADD #330	JS 000
		IN	WR9	RD @9	SUB#1	JS 001
	X	RD 4	SUB #8	WR8	WR @8	JNZ 001
		IN	ADD #12	WR 10	WR @10	JS 004
	X	RD 4	ADD #15	WR 13	WR @13	JMP 001
		IN	SUB #308	WR11	WR @11	JMP 001
	X	RD #988	ADD #19	WR9	WR @9	JNZ 001
		IN	WR11	ADD 11	WR @11	JMP 002
	X	RD #5	MUL #9	WR10	WR @10	JNZ 001

5. Выполнить в режиме Шаг введенную последовательность команд, фиксируя изменения значений объектов, определенных в п. 4, в таблице (см. форму табл. 9.2).

6. Если в программе образуется цикл, необходимо просмотреть не более двух повторений каждой команды, входящей в тело цикла.

Таблица Варианты задания 1

Контрольные вопросы 1

1. Из каких основных частей состоит ЭВМ и какие из них представлены
в модели?

2. Что такое система команд ЭВМ?

3. Какие классы команд представлены в модели?

4. Какие действия выполняют команды передачи управления?

5. Какие способы адресации использованы в модели ЭВМ? В чем отличие между ними?

6. Какие ограничения накладываются на способ представления данных модели ЭВМ?

7. Какие режимы работы предусмотрены в модели и в чем отличие между ними?

8. Как записать программу в машинных кодах в память модели ЭВМ.

9. Как просмотреть содержимое регистров процессора и изменить содермое некоторых регистров?

10. Как просмотреть и, при необходимости, отредактировать содержи ячейки памяти?

11 Как запустить выполнение программы в режиме приостановки работы
после выполнения каждой команды?

12 Какие способы адресации операндов применяются в командах ЭВМ?

13 Какие команды относятся к классу передачи управления?

МЕТОДИЧЕСКИЕ УКАЗАНИЯ 2. ПРОГРАММИРОВАНИЕ РАЗВЕТВЛЯЮЩЕГОСЯ ПРОЦЕССА

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

Пример 2

В качестве примера (несколько упрощенного по сравнению с заданиями практической работы № 3) рассмотрим программу вычисления функции

причем х вводится с устройства ввода IR, результат у выводится на OR. Граф-схема алгоритма решения задачи показана на рис.

В данной практической работе используются двухсловные команды с непо­средственной адресацией, позволяющие оперировать отрицательными чис­лами и числами по модулю, превышающие 999, в качестве непосредственного операнда.

Оценив размер программы примерно в 20—25 команд, отведем для области данных ячейки ОЗУ, начиная с адреса 030. Составленная программа с комментариями представлена в виде табл. 9.4.

Таблица Пример программы

Адрес	Команда	Примечание
	Мнемокод	Код
	IN	01 0 000	Ввод х
	WR 30	22 0 030	Размещение х в ОЗУ(ОЗО)
	SUB #16	24 1016	Сравнение с границей — (х -16)
	JS 010		Переход по отрицательной разности
	RD 30	21 0 030	Вычисления по первой формуле
	SUB #11	24 1011
	WR 31	22 0 031
	MUL 31	25 0 031
	SUB #125	24 1 125
	JMP 020	10 0 020	Переход на вывод результата
	RD 30	21 0 030	Вычисления по второй формуле
	MUL 30	25 0 030
	WR 31	22 0 031
	RD 30	21 0 030
	MUL #72	25 1 072
	ADD 31	23 0 031
	ADI 106400	43 0 000
	DIVI 100168	46 0 000
	OUT	02 0 000	Вывод результата
	HLT	09 0 000	Стоп

Задание 2

1. Разработать программу вычисления и вывода значения функции:

F_i(x), при х>=а,

Fj(x) при x< а,

для вводимого из IR значения аргумента х. Функции и допустимые пре­делы изменения аргумента приведены в табл. 9.5, варианты заданий — в табл. 9.6.

2. Исходя из допустимых пределов изменения аргумента функций (табл. 9.5) и значения параметра а для своего варианта задания (табл. 9.6) выделить на числовой оси Ох области, в которых функция у вычисляется по представленной в п. 1 формуле, и недопустимые значения аргумента. На недопустимых значениях аргумента программа должна выдавать на OR максимальное отрицательное число: 199 999.

3. Ввести текст программы в окно Текст программы, при этом возможен набор и редактирование текста непосредственно в окне Текст программы

или загрузка текста из файла, подготовленного в другом редакторе.

4. Ассемблировать текст программы, при необходимости исправить синтаксические ошибки.

5. Отладить программу. Для этого:

а) записать в IR значение аргумента х > а (в области допустимых значений);

б) записать в PC стартовый адрес программы;

в) проверить правильность выполнения программы (т. е. правильность результата и адреса останова) в автоматическом режиме. В случае наличия ошибки выполнить пп. 5, г и 5, д; иначе перейти к п. 5, е;

г) записать в PC стартовый адрес программы;

д) наблюдая выполнение программы в режиме Шаг, найти команду, являющуюся причиной ошибки; исправить ее; выполнить пп. 5, а — 5, в;

е) записать в IR значение аргумента х < а (в области допустимых значений); выполнить пп. 5, б и 5, в;

ж) записать в IR недопустимое значение аргумента х и выполнить пп. 5, 6 и 5, в.

6. Для выбранного допустимого значения аргумента х наблюдать выполнение отлаженной программы в режиме Шаг и записать в форме табл. 9.2 содержимое регистров ЭВМ перед выполнением каждой команды.

Контрольные вопросы 2

1. Как работает механизм косвенной адресации?

2. Какая ячейка будет адресована в команде с косвенной адресацией через
ячейку 043, если содержимое этой ячейки равно 102 347?

3. Как работают команды передачи управления?

4. Что входит в понятие "отладка программы"?

5. Какие способы отладки программы можно реализовать в модели?