Кузьмин С.З. Основы теории цифровой обработки радиолокационной информации (1974) (1186213), страница 11
Текст из файла (страница 11)
Элементы алгебры логики и синтез логических схемАлгебра логики оперирует с высказываниями. Высказыванием называется всякое утверждение, которое может быть истинным или .южным. Истинным высказываниям приписывается символ «1», а ложным —«О». Из одного или нескольких высказываний, принимаемых за простые, можно составлять сложные высказывания. В дальнейшем простые высказывания обозначаются через xlt хг, ..,, а сложные —через уи у2, .... Сложные высказывания также могут принимать только два значения в зависимости от истинности или ложности входящихв них простых высказываний.Все сложные высказывания могут быть получены с помощью трехлогических операций:— операции логического умножения (пересечения), которая обычно называется коньюнкцией или операцией И и обозначается через Дили • (точка);— операции логического сложения (объединения), которая -обыч' но называется дизъюнкцией или операцией ИЛИ и обозначается черезV или + ;— операции логического отрицания (дополнения), которая называется операцией НЕ и обозначается - (надчеркивание).В дальнейшем будем придерживаться следующих обозначений:— для конъюкции • (точка); где это возможно, знак вообще опускается;— для дизъюнкции ~ ;— для отрицания —.Коньюкцией двух простых высказываний хг и х% называется сложное высказывание χλχ2, которое ложно, когда хотя бы одно простоевысказывание ложно, и истинно, когда оба простых высказыванияистинны.
Операция конъюнкции реализуется логической схемой И(схемой совпадения).Дизъюнкцией двух простых высказываний называется сложное высказывание (χλ -f- *a)i которое истинно, если хотя бы одно из входящих внего высказываний истинно, и ложно, если оба простых высказыванияложны. Операция дизъюнкции реализуется логической схемой ИЛИ.Отрицанием высказывания называется сложное высказывание у,которое истинно, когда х ложно, и ложно, когда х истинно (например:у = х, Г = 0, б = 1). Операция отрицания реализуется схемой инвертора.В алгебре логики имеется четыре закона: переместительный, сочетательный, распределительный и инверсии.
Переместительный и сочетательный законы для операции логического сложения записываютсяв виде1ι -г * 2 = хг - - ι>χχхχхХ\ + ( г -т- *з) = ( ι + г) -г Хз-Кроме того, непосредственно из определения операции логического сложения, записываются следующие равносильности**:х + 0 = х,х -г \ ~ \х -f х — х.*' Логические выражения называются равносильными, если они равны при всехвозможных значениях аргумента,51Переместительный и сочетательный закон для операции логического умножения записываются в видех1 х2 — x2xlt(xlxz)x[i = хг (χ«χ3),а соответствующие этой операции равносильности равныAO= 0,xl •= х,хх — х.Распределительный закон соответственно для операций логического сложения и логического умножения определяется следующимисоотношениями:\Х2Xl~=Х3/Х1хг~Х1Х3<хХ1 -г Х2Х3 = (х1 - ^ ^ г ) ( л ~т~ ^з)-Закон инверсии, который в обычной алгебре отсутствует, определи-'ется соотношениями:Λι —р" Λό — Aiл ι A j -— Ai ~j" ^2'ΛΌΙНепосредственно из закона алгебры логики и записанных вышеравносильностей можно получить следующие полезные соотношения:x1-f-x1—I,x1xl = 0,λххχ'ι г ~\~ г — Х\ И" Хцχ\Xi-r х^Хг — ^1^2'хχ χ\х\ ~т χν (^ι"ΐ~ Х2) ~ χνι 2ΐ~ ι 2 — ъЗаконы алгебры логики и другие, записанные выше соотношенияпозволяют упрощать путем преобразований сложные логические функции.Логические (булевы) функции образуются из конечного числа двоичных переменных с помощью операций конъюнкции, дизъюнкции иотрицания.
Для описания логических функций используются таблицы истинности, в которых для каждой 1-й комбинации значений переменных сопоставлено значение функции у(> равное 0 или 1. Всего имеется 2т комбинаций значений т переменных. Поэтому таблицу истин'ности можно представить в виде табл. 2.1.тВ соответствии с приведенными в таблице 2 комбинациями можтно образовать систему из 2 функций /; (x m _ l t .... х0)'/о>2т\Хт-1>~IХт-2<••••>"1-1'* 1 -Хт-2'Х0>•••'~~Х1'Хт - 1Хо)—Хт~2Хт~1•••Хт-ЧХ\•••Х(><Х1Х0<каждая из которых принимает значение, равное единице только длясочетания переменных, характеризующих ΐ-ю комбинацию (i == 0 —2т — 1).
Образуем конъюнкции ft(xm-i, ..., х0) yi, которые являютсяфункциями значений у{.Тогда функция2т-\У(хт-1>Хт-г52χ χν ό)^Σft{Xm-i'xm~v~'>x»x<i)yt(2.1.1)Т а б л и ц а 2.1*»/*o«I000000Уо100001У\200.010Уз•;:•2m—211II02*—11r1112m—2У2т-\является аналитической записью логической функции, заданной таблицей истинности—(табл. 2.1).Форма записи логической функции в виде выражения (1) получиланазвание совершенной дизъюнктивной нормальной формы (СДНФ)функции. Члены ft этой функции, которым соответствует yt = 1,называются конституентами единицы.
Аналогично члены ft, которымсоответствует ух — 0, называются конституентами нуля. Обычно логическую функцию задают путем перечисления дизъюнктивных членов.Логические функции применяются для описания функционирования цифровых автоматов. Каждая такая функция подлежит в дальнейшем реализации с помощью устройств, называемых логическими элементами.
Однако прежде чем приступить к реализации, необходимопопытаться преобразовать логическую функцию с целью ее упрощения.Суть последнего состоит в нахождении какого-то другого выражения,представляющего ту же функцию, но для практической реализации которого требуется меньше оборудования, чем для первоначального варианта. Для упрощения (минимизации) логических функций используются в первую очередь основные соотношения алгебры логики.Однако существуют и специальные методы минимизации, с которымипри необходимости можно ознакомиться по многочисленной специальной литературе (см.
напр. [2]).В качестве примера произведем синтез логической схемы автомата,фиксирующего обнаружение пачки при появлении в исследуемой последовательности нулей и единиц не менее трех единиц на 5 смежныхпозициях (3 из 5).Введем следующие обозначения: х\ — логические переменные накаждой из пяти смежных позиций (логические переменные принимаюттолько два значения: 0 или 1—причем нулевые значения логических53переменных отмечаются знаком отрицания); уобп — сложное событие,определяемое согласно табл. 2.2Т а б л и ц а 2-2/123456789ЮИхь1i01I010I01Х1*31011011001101]100011110000111111I1I11111]11II1111I1111Составим таблицу истинности искомой логической функции(табл.
2.2). Из 32 возможных комбинаций в таблице приведены толькоте комбинации, которые приводят к обнаружению пачки (i/o6H = 1).Логическая функция обнаружения пачки записывается в видеХ5XiXSХ2После минимизации функции позаконам алгебры логики получим- x.xJx* •Рис. 2.54Структурная схемаавтомата.(2 1 21Из формулы (2) следует, чтодля реализации рассматриваемойлогики обнаружения потребуется 4 схемы И и 4 схемы ИЛИ.Кроме того, как видно из табл.2.2, для реализации схемы автомата потребуется также 5 элементов памяти (триггеров Т)для записи входной информациина 5 смежных позициях. Структурная схема полученного автомата представлена на рис 2.1,ϋ.ί.2.
Математическая модель конечного автоматаОсновной математической моделью конечного цифрового автомата1)является так называемый абстрактный автомат первого рода М , который задается совокупностью из шести характеристик/ ' а { Х , Y, Л, α0ι Flt Ф,},(2.1.3)где X — (xlt х2, .... хп) — конечное множество входных сигналов (алфавит входных сигналов); У = {уу, у2, .... ут) — конечное множество(алфавит) выходных сигналов автомата; А = (а0, а1у .... ам) — конечное множество внутренних состояний автомата; а0 — исходное (начальное) состояние автомата, с которого он начинает работу; F 2 —функция переходов, устанавливающая зависимость внутреннего состояния автомата в момент времени t •+• 1 от входного сигнала и внутреннего состояния в момент времени /, т.
е.а (/ + 1) = > ! [х (t), a"_{t)} при t= 0, а (/) = а0(2.1.4)Ф х — функция выходов, устанавливающая зависимость выходногосигнала автомата от входного сигнала и внутреннего состояния дляодного и то же момента времени t, т. е.* ( 0 = φ ι ί * ( 0 , α(/)].(2.1.5)Здесь и далее ί — дискретное время, принимающее целочисленные значения.Частным случаем автомата первого рода А^ является автомат второго рода М2К который описывается функцией переходовa (t + 1) = F 2 [χ (0, sa(t)}и функцией выходову (0 = Ф г (а (0).Задать- детерминированный конечный автомат — значит выразитьдля него в явном виде функции переходов и выходов.
Для этого применяются таблицы, графы и матрицы переходов.Таблица переходов (табл. 2.3) служит для непосредственного задания функции переходов автомата. Строки этой таблицы соответствуютсимволам алфавита входных сигналов, а столбцы — внутренним состояниям автомата*). В клетку таблицы переходов, находящуюся на пересечении αι столбца и х} строки, записывается состояние автомата F (XJ,С(), в которое он переходит из состояния at под воздействием входногосигнала х}.•> В рассматриваемом примере алфавит входных сигналов состоит HJ двух символов ха и xlt а число состояний автомата равно 4.55ражение (2.4) определяет, алгоритм .нерекурсивного фильтра с двукратным ЧПВ (ЧПВ-2). Для определения коэффициентов этого фильтра составим, разностные уравнения:Zcs [n] isd aZcs [n] - AZCS [я - 1 ]Следовательно, коэффициенты фильтра равны (/ιθ==/ι2= 1,h:==—2, Λΐ—0 при ΐ > 2 . Структурная схема цифровогофильтра ЧПВ с ν — 2 (для одного квадратурного канала)представлена на рис.
2.2.Аналогично можно получить коэффициенты фильтрапри значениях ν, больших 2. Так, для фильтра. ЧПВ с ν —= 3 ho—1, /ii——-3, / Ϊ 2 = 3 , / г з = ~ 1 , Л/=0 при- г > 3 , алгоритм фильтрацииΖόΛη] - Си Й - Э^Ля - 1] + ЗС„[* - 2] - C e i [ " - 3].. '". (2.6)Нерекурсивные ЦФ просты в реализаций, однако имеютпологие скаты амплитудно-частотнойхарактеристики(АЧХ), что ухудшает эффективность компенсаций пассивных помех../ ':Кроме нерекурсивных в.качестве режекторных Ц ф могут быть использованы рекурсивные РФ, реализующие; ал?горитм: •-.'' " ' ' , ,.%\п\ =2а^Лп-i]+2 ЬрсЛп-)],I"у . •'-(2.7)где'-Λι и bj-^- коэффициенты рекурсивного ЦФ.;(Методы синтеза рекурсивных. ЦФ рассмотрены в многочисленной литературе (например; [4, 7, 22, 26, 46]); Невдаваясь в подробности, отметим, что для рекурсивныхрежекторных ЦФ СДЦ наиболее подходящим считаетсясинтез по квадрату АЧХ в соответствии.со следующей,ме'тодикой [22].
Сначала на рснове,. заданных;: параметров.внешней обстановки и исходных предпосылок выбираетсяпорядок и определяется АЧХ аналогового фильтра-прототипа, а затем приближение квадрата АЧХ цифровогофильтра к квадрату АЧХ аналогового фильтра-прототипа56'.Большую наглядность обеспечивает задание автоматов с помощьюнаправленных графов. Граф автомата состоит из вершин(изображаемыхкружками или точками), соединенных стрелками. Последние называются ребрами графа. Вершины графа отождествляются с состояниямиавтомата, а стрелки — с входными сигналами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
