On Embedding
|
Что это за зверь — «Исключающее ИЛИ»?Влад «Bill» Князев
|
| X | Y | f6 | f7 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
Как видим, эти функции отличаются между собой значением всего лишь на одном наборе. И именно нулевое значение на последнем наборе делает эту функцию «исключительной». Но в чем же заключается эта «исключительность»?
Отвечая на свой традиционный вопрос, я вспоминаю, что сам столкнулся с этой функцией еще будучи студентом, задолго до того, как впервые о ней услышал. В то время, учебный год у нас начинался с поездки в село, где все студенты в течение месяца занимались уборкой урожая овощей. Обед нам доставляли в поле на машине, и обедали мы из больших металлических тарелок. Съев первое, мы снова бежали с тарелками к машине за вторым.
В один из таких обедов, когда я съел свою порцию первого и собрался идти за вторым, ко мне обратилась девушка из нашей группы и попросила принести второе и ей. Ну разве можно отказать девушке в такой простой просьбе? Конечно же, я взял и ее тарелку, и только я снова собрался идти с двумя тарелками, как с аналогичной просьбой ко мне обратилась и другая девушка. И тут я пожалел, что у меня не было третьей руки. В одной руке я держал собственную тарелку, в другой — тарелку первой девушки. И я мог выполнить просьбу только одной из них: или только первой или только второй. Не соответствует ли это поведению функции f6?
Конечно, в то время я понятия не имел о такой функции, как «Исключающее ИЛИ», и я нашел выход из создавшегося положения. Интересно, как бы поступили вы на моем месте? И примеров подобных ситуаций из нашей повседневной жизни можно привести сколько угодно.
В самом деле, Вы собрались идти с другом или со знакомой девушкой на просмотр очень интересного фильма. Все билеты распроданы, но вы решаете «стрельнуть» лишние билетики у входа. Все в порядке, билет есть! Но он только один, а вас — двое. И на один билет сможет пройти в кинотеатр только один из вас (первый и второй наборы). Я думаю, что вы, скорее всего, выберете действие (значение), соответствующее последнему набору. Вы просто напросто не пойдете в кино, решив, что провести время вдвоем гораздо интереснее, чем смотреть, даже интересный, фильм в одиночестве.
Примеры из техники
Но это были примеры «плохого» поведения функции в нашей повседневной жизни. А мне хотелось бы рассказать именно о «хороших» ее качествах в «электронной» жизни. Для этого надо просто вспомнить свойства этой функции (операцию «Исключающее ИЛИ» мы будем обозначать символом «^»). Выражение для этой функции будет выглядеть так:
f = x ^ y
Допустим, мы зафиксировали значение переменной y. Положим, что y равно нулю. Тогда мы получим выражение f = x, т.е. элемент «Исключающее ИЛИ» может быть использован в качестве повторителя, если на один из его входов подать напряжение логического «0». Конечно, такая необходимость возникает достаточно редко, но, тем не менее, об этом не стоит забывать.
Возьмем другое фиксированное значение y равно 1, тогда мы получим:
f = x ^ y = x ^ 1 = ~x (1)
Здесь символом тильда «~» обозначена операция «НЕ». Таким образом, если на один из входов подать фиксированное напряжение, соответствующее напряжению логической «1», то мы получим инвертор, который требуется уже значительно чаще.
Наконец, если мы будем просто подавать на вход динамически изменяющееся значение сигнала, соответствующего переменной y, то по отношению к переменной x данный элемент будет вести себя как управляемый инвертор. А область применения таких схем уже достаточно обширна.
Например, подобный управляемый инвертор может быть использован в качестве простейшего фазового модулятора, с изменением фазы на 180 градусов. Или он может быть использован в качестве основы для создания более сложных фазовых модуляторов, имеющих свои специфические особенности. Можно использовать такие схемы и для построения фазовых дискриминаторов.
Кроме того, имеются схемы пересчетных устройств, коэффициент деления которых является нечетным числом, и одновременно с этим сигнал на выходе такого делителя имеет вид меандра.
Я помню, как у меня была необходимость получения из одной опорной частоты двух частот имеющих соотношение 3:2 и форма сигнала на выходах делителей должна была быть именно в виде меандра. Чтобы этого добиться, мне пришлось увеличить в два раза значение опорной частоты, чтобы иметь делители с четными коэффициентами деления: 6 и 4 соответственно. А это потребовало применения дополнительно двух триггеров. В тоже время эта задача могла быть решена и с помощью элементов «Исключающее ИЛИ».
Поскольку функция «Исключающее ИЛИ» имеет единичные значения на тех наборах, на которых ее аргументы имеют различные значения, то она получила также название «НЕРАВНОЗНАЧНОСТЬ». И это ее свойство можно использовать для создания схем обнаружения момента изменения сигнала (с «1» на «0», или с «0» на «1»). Для этого достаточно подать на один из входов сам сигнал, а на другой вход — этот же сигнал с некоторой задержкой.
Мне приходилось видеть схему, где подобное решение использовалось для реализации гальванической развязки при помощи импульсного трансформатора. Стояла задача передачи через гальваническую развязку сигналов в широком диапазоне частот, вплоть до инфранизких. В этом случае использование только трансформатора, самого по себе, становится затруднительно, а то и вовсе невозможно. Но с помощью схемы «Исключающее ИЛИ» можно сформировать короткие импульсы, фиксирующие только момент изменения значения сигнала. Такие импульсы могут быть легко пропущены импульсным трансформатором, независимо от частоты их появления. Восстановление сигнала на приемном конце (со стороны вторичной обмотки) в этом случае можно осуществить при помощи обыкновенного счетного триггера.
Могу добавить, что регистрация факта изменения входного сигнала, — как по фронту, так и по спаду — иногда требуется и в случае использования микроконтроллеров. Например, в микроконтроллере AVR можно установить момент выдачи прерывания или по фронту или по спаду сигнала на входе прерывания. Для этого в схему формирования сигнала прерывания добавлен элемент «Исключающее ИЛИ», служащий в качестве управляемого инвертора.
С другой стороны, у контроллеров семейства PIC, такой элемент используется для реализации прерываний, как по фронту, так и по спаду сигналов на входах внешних прерываний, то есть такой элемент реализует функцию «НЕРАВНОЗНАЧНОСТИ». А иногда это бывает очень удобно.
До сих пор мы рассматривали только логические свойства функции «Исключающее ИЛИ». Но если мы внимательно взглянем на ее таблицу истинности, то сможем заметить и ее «арифметические» способности. Я здесь имею в виду то, такая функция выполняет операцию суммирования аргументов, без формирования сигналов переноса. И, стало быть, эта функция имеет еще одно название — «СУММА ПО МОДУЛЮ 2».
А если присмотреться еще внимательнее , то можно заметить, что отсутствие переноса делает эквивалентными операции «Сумма» и «Разность» — эквивалентными в смысле конечного результата.
И эти арифметические свойства используются чрезвычайно широко. Трудно назвать хотя бы один алгоритм формирования различных кодов и реализации их декодеров, где бы ни использовалась данная функция. Взять хотя бы простейший контроль по четности: там тоже используется схема свертки всех разрядов числа по модулю 2. Или вспомним широко применяемый алгоритм CRC — используемый для контроля целостности передачи данных.
Другой пример — схема формирования псевдослучайного сигнала на основе регистра сдвига с обратными связями. Сумматор по модулю 2 используется и там.
Можно было бы привести еще множество других применений функции «Исключающее ИЛИ» при аппаратной реализации различных схем, но для этого потребовалось бы написать целую книгу.
Примеры из реальных программ
Наши размышления будут неполными, если мы не вспомним об использовании функции «Исключающее ИЛИ» в программировании. Не случайно инструкция, выполняющая операцию «Исключающее ИЛИ», имеется в системах команд практически всех существующих контроллеров (процессоров). Это является результатом уникальности свойств данной функции.
В некоторых случаях можно воспользоваться данной функцией для инвертирования содержимого некоторого регистра процессора, или отдельных его разрядов, особенно в тех случаях, когда специальная команда инверсии отсутствует. Это следует из ее свойства (1), о котором мы говорили ранее.
Можно рассмотреть и другое ее свойство, которое мы еще не успели рассмотреть. А именно:
f = x ^ x = 0 (2)
Другими словами данная функция равна нулю, если ее аргументы имеют одинаковое значение.
Я использовал операцию «Исключающее ИЛИ» при программировании микропроцессора I8080 для обнуления содержимого регистра аккумулятора. Конечно, для этой цели можно было использовать специальную команду пересылки с непосредственной адресацией, типа
mvi a, 0
но она занимала два байта памяти, и выполнялась медленнее, чем однобайтовая команда
xra a
Подобный прием можно использовать и во множестве других процессоров.
Наконец, данную функцию можно использовать для сравнения двух чисел на равенство (неравенство) опять же в тех случаях, когда специальная команда у данного процессора отсутствует.
И здесь мне хотелось бы рассказать о тех ее свойствах, которые мне были давно известны, но о которых я забыл. И не вспомнил бы, если бы мне не пришлось заняться программированием PIC16.
Дело в том, что в системе команд данного семейства команда сравнения двух чисел отсутствует. И чтобы выполнить сравнение, мне надо было использовать либо инструкцию вычитания sublw, либо инструкцию «Исключающее ИЛИ» xorlw. Последней инструкцией я и воспользовался.
В моей программе было множество фрагментов кода, связанных с вводом и обработкой данных от клавиатуры. На основе кода нажатой кнопки производился условный переход на соответствующий обработчик. Фрагменты кода выглядели приблизительно так:
call GetChr ; Ввод данных с клавиатуры, ; результат в регистре W ; и в переменной KeyBuf xorlw 'F' ; Выбор текущего пункта меню? bz DoItem ; Да, выполнить обработку movfw KeyBuf ; Выбор следующего пункта? xorlw '+' ; bz NextItem ; Переход, если ДА movfw KeyBuf ; Выбор предыдущего пункта? xorlw '-' ; bnz menu_loop ; Переход, если НЕТ ; все остальные кнопки игнорировать
Вроде все получается логично и достаточно просто. Но меня смущало то, что при каждом последующем сравнении необходимо было заново перезагружать рабочий регистр W. И я чувствовал, что данная перезагрузка совершенно излишня. В ее использовании нет никакой необходимости.
И я убедился в этом окончательно, после того как вспомнил необходимые мне свойства функции «Исключающее ИЛИ». Хотя честно признаюсь: не без труда. Сначала нужно было понять, что же требуется вспомнить.
Прежде всего, избежать повторной перезагрузки можно, если при последующих проверках сравнивать предыдущее значение регистра W не с тем кодом, который нам нужен, а с некоторым другим, неизвестным. Хотя почему неизвестным? Мы же на первом шаге сравниваем с известным нам кодом. Значит нужно воспользоваться этим знанием при каждом последующем сравнении.
Чтобы выявить закономерность, я попробовал «проиграть» на бумаге разные частные случаи. А потом я задумался над теоретической основой, над свойствами функции «Исключающее ИЛИ». Какие же свойства функции работают в данном случае?
Очевидно, что необходимо перед каждой последующей проверкой восстанавливать предыдущее значение содержимого регистра. Это можно сделать на основании свойства (2), а также свойства ассоциативности этой функции (т.е. для данной функции справедлив сочетательный закон):
x ^ y ^ z = (x ^ y) ^ z = x ^ (y ^ z) (3)
Если воспользоваться этим свойством и свойством (2), то можно записать
(x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x
То есть, мы получим исходное содержимое регистра W, но на это опять потребуется дополнительная инструкция. Никакого выигрыша! Тут я подумал: если воспользоваться этим же свойством ассоциативности (3), то можно совместить операцию восстановления исходного значения в регистре W и сравнение этого значения с новой константой в одной команде.
В самом деле, можно записать так:
(x ^ y) ^ y ^ z = (x ^ y) ^ (y ^ z) = x ^ (y ^ y) ^ z = x ^ z
Здесь выражение
y ^ z = z ^ y (4)
После этого мне осталось только переписать соответствующий фрагмент кода в более простом виде:
call GetChr ; Ввод данных с клавиатуры, ; результат в регистре W xorlw 'F' ;Выбор текущего пункта меню? bz DoItem ; Да, выполнить обработку xorlw '+' ^ 'F' ; Выбор следующего пункта? bz NextItem ; Переход, если ДА xorlw '-' ^ '+' ; Выбор предыдущего пункта? bnz menu_loop ; Переход, если НЕТ - ; все остальные кнопки игнорировать
Как видим, фрагмент кода сократился на две инструкции и, кроме того, освободилась ячейка памяти в регистровом файле, что тоже в ряде случаев может быть необходимо. Кроме того, в соответствии с синтаксисом ассемблера для обозначения операции «Исключающее ИЛИ» используется символ «^».
Хочу также обратить особое внимание на то, что операция «Исключающее ИЛИ» с константами выполняется ассемблером на этапе трансляции и, стало быть, не требуется их вычислять вручную.
Заключение. История с кореллометром
Вот, пожалуй, и все, что мне хотелось рассказать об этой удивительной функции «Исключающее ИЛИ». Но прежде чем закончить, я расскажу вам еще об одном случае из моей практики, некоторым образом, связанным с темой нашего размышления.
В бытность свою студентом мне потребовалось разработать и собрать коррелометр в качестве лабораторного макета по курсу «Радиоизмерения». Это была моя первая разработка, я был студентом и никакого практического опыта в то время не имел.
Естественно, первым делом я принялся копаться в книгах по радиоизмерениям и обнаружил довольно простой вариант построения подобных устройств. Сущность его заключалась в том, что вычисление автокорреляционной функции процесса сводилась к обработке знаков сигналов. То есть, попросту говоря, к двоичной арифметике. Но это я осознал уже позже.
А в то время схема подобного устройства представлялась мне довольно простой. Требовалось только сделать пороговые устройства для выделения знаков прямого и задержанного процессов. И далее, подать сигналы с выходов пороговых устройств на схему совпадения (попросту говоря — схему «И»). Значение автокорреляционной функции фиксировалось стрелочным индикатором, который подключался к выходу схемы совпадения и одновременно выполнял функцию интегратора. Вроде все просто.
Но была одна принципиальная проблема, которая мешала нам заявить, что прибор сделан. Дело было в том, что значения автокорреляционных функций никак не хотели приближаться к нулю, как того требовала теория. С увеличением задержки между процессом и его копией, значение функции стремилось к 0.5 от максимального значения показаний прибора, но никак не к нулю.
Были перепробованы несколько различных вариантов схемных решений - результат был одним и тем же. Прибор не хотел работать в соответствии с теорией, и ни мы — студенты, ни наш преподаватель не могли объяснить этот факт. Вот так моя первая разработка окончилась... ничем.
Лишь позже, когда я внимательно перечитал описание принципов его работы, я понял, что прибор на самом деле у нас работал, причем работал в соответствии с теорией. Просто мы неправильно интерпретировали показания прибора.
Оказывается, что мы измеряли совпадение только положительных знаков процесса. И в этом случае измеренное значение функции автокорреляции и должно было стремиться к 0,5, что мы и наблюдали.
Для того же, чтобы значение функции стремилось к нулю, как мы того хотели, необходимо было измерять совпадение не только положительных, но и отрицательных знаков процесса. И если бы я сразу прочитал теорию внимательно, то я, наверное, понял это гораздо раньше. Но, как говорится: «молодо — зелено».
Но самое главное заключалось прежде всего в том, что для измерения совпадения и положительных и отрицательных знаков требовалась функция «РАВНОЗНАЧНОСТИ» (инверсия функции «Исключающее ИЛИ»), а не просто схема «И». А в то время я не имел даже самых элементарных понятий об элементарных логических функциях.
Вот теперь, пожалуй, все. И если кто-нибудь, прочитав этот опус, захочет разобраться что же все-таки такое эти элементарные логические функции и еще раз откроет книгу, то я буду считать, что я достиг своей цели.
Ведь может случиться так, что он (или она) сумеет сделать свои открытия, увидеть то, чего не смог или не сумел увидеть я. И об этих открытиях он расскажет остальным, в том числе и мне. И все мы станем знать чуточку больше о тех элементарных вещах, которые нас окружают.
Приложение
Задача по программированию (язык Си).
Имеются две переменные: A и B. Напишите программу на Си, которая осуществляет перестановку значений этих двух переменных, не используя при этом третью. Т.е., в результате работы программы значение переменной A должно стать равным начальному значению переменной B. И, соответственно, значение переменной B должно стать равным начальному значению переменной A.
Для проверки работоспособности алгоритма вы можете использовать такие начальные значения:
A = 0xF3; B = 0x25;
![[Python Powered]](/i/PythonPoweredSmall.gif){kind=small} |