Синтез цифрового автомата по заданному алгоритму

                                КОЛЛЕДЖ ТЕЛЕКОММУНИКАЦИЙ

            Московского технического университета  связи и информатики 
 
 
 
 

Отделение____________________________________________________________ 

Специальность________________________________________________________ 
 

                                               Курсовая работа 

По дисциплине_________________________________________________________ 

На тему_______________________________________________________________ 
 

                                                                                  Выполнил ____________________

                                                                                  _____________________________

                                                                                  Руководитель_________________

                                                                                  _____________________________

                                                                                  «____»_________________20__г.

                                 СОДЕРЖАНИЕ                                                             

Введение…………………………………………………………………………….

1. Принцип постоения процессорных устройств………………………………

2. Принцип разработки  цифровых автоматов…………………………………

3. Разработка цифрового  автомата по алгоритму функционирования…...

3.1. Опредиление состояний  управляющего устройства……………………

3.2. Построение графа  функционирования цифрового автомата………….

3.3. Построение таблицы  функционироваеия цифрового автомата……….

3.4. Составление логических  уравнений………………………………………..

4. Выбор микросхем  по заданному базису……………………………………...

5. исследование работы  цифрового автомата…………………………………

Заключение…………………………………………………………………………...

Список  литературы……………………………………………………………….. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                                   ВВЕДЕНИЕ 

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

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

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

                       1.Принцип построения процессорных устройств.

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

         В зависимости от используемого  метода обработки используют  два типа аппаратуры: аналоговая, в которой используется аналоговый метод обработки, и цифровая, в которой применяется цифровой метод обработки. В цифровой аппаратуре основным устройством, в котором непосредственно выполняется обработка, является процессорное устройство.

         Процессорное устройство(как и  всякое сложное цифровое устройство) синтезируется в виде соединения  двух устройств: операционного и управляющего(рис.1).

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

                                                                          Вход данных

                                                                          Выход данных 

                       Рис.1 Структура процессорного автомата

:

         Процесс функционирования операционного  устройства распадается на опредиленную  последовательность элементарных  действий в его узлах.Перечень  таких элементарных действий  включает в себя:

          1) Установку регистра в некоторое состояние (например, запись в регистре числа 0, обозначаемую R2          0) ;

           2) инвертирование  содержимого разрядов регистра (например, еслирегистр R2 содержал число 101101, то после инвертирования его содержимое будет 010010, такое действие обозначают R2          (R2));

           3) пересылку  содержимого одного узла в  другой узел (например, пересылку  содержимого регистра R₁,в регистр R₂ , обозначаемую R₂      (R₁));

           4) сдвиг  содержимого узла влево , вправо (например, сдвиг на один разряд  влево содержимого регистра R₁, обозначаемый R₁      C_дв Л (R₁));

           5)счет, при котором число в счетчике  возрастает или убывает на единицу (С_ч        (С_ч)   1);

           6) Сложение (например, R₂       (R₂) + (R₁));

           7) сравнение на равенство содержимого  регистра с некоторым числом,результат  сравнения лог. 1 в случае выполнения  равенства или лог. 0 в случае  невыполнения равенства;

           8) некоторые логические действия (поразрядная дизъюнкция, коньъюнкция  и т. д.) 
 
 

         Каждое такое элементарное действие, выполняемое в одном из узлов  операционног устройства в течение  одного тактового периода. Называется  микрооперацией.

         В опредиленные  тактовые периоды одновременно  могут выполнятся несколько микроопераций,  например R₂       0 ; С_ч       (С_ч) + 1. Такая совокупность одновременно выполняемых операций называется микрокомандой, а весь набор микрокоманд, предназначенный для решения опредиленной задачи, - микропрограммой.

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

           Формирование управляющих сигналов  y₁, ….., y_n (рис. 2) для выполнения опредиленных команд может зависеть от состояния узлов операционного устройства, опредиляемого сигналами x₁,…, x_s, которые передаются по опредиленным цепям с соответствующих выходов операционного устройства на входы управляющего устройства. Управляющие сигналы y₁,…, y_n могут зависеть также от внешних сигналов x_s+1,…, x_L.

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

                 2.Принцип разработки цифровых автоматов

         Существует 2 принципиально различных  подхода в проектировании микропрограмного  автомата (управляющего устройства): использование принципа схемной логики или принципа программируемой логики.

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

          Устройства, построенные по такому  принципу , способны обеспечивать  наивысшее быстродействе при  задвнном типе технологий элементов.  Недостаток этого принципа построения  процессорных устройств состоит  в трудности использования последних  достижений микроэлектроники –  интегральных схем большой и  сверхбольшой степени интеграции (БИС и СБИС). Это связано с  тем что  для разных процессорных  устройств потребуются различные  БИС. Такие БИС окажутся узкоспециализированными.  Число Бис будет большим , а  потребность  в каждом типе  БИС окажется низкой. Это приведет  к экономической нецелесообразности  выпуска их промышленностью.

           Принцип программируемой логики  предполагает построение с использованием  одной или нескольких БИС некоторого  универсального устройства, требуемое  функционриование (т.е. специализация)  которого обеспечивается заключением  в память устройства опредиленной  программы (или микропрограммы). В сзависимости от введёной  программы такое универсальное  устройство способно выполнить  самые разнообразные функции.  Число типов БИС в этом случае  оказывается небольшим, а потребность  в БИС каждого типа высокой.  Это обеспечивает целесобразность   их выпуска промышленностью. Набор  типов БИС, обеспечивающих построение  таких универсальных устройств  , образует микропроцессорный комплект (МПК). Устройства, реализуемые на МПК, - микропроцессорные устройства (МПУ).

            Цифровые автоматы – это логические  устройства, в которых помимо  логических элементов имеются  элементы памяти . Значение выходных  сигналов такого устройства зависит  не только от аргументов на  выходе в данный момент времени,  но от предидущего  состояния  автомата, которое фиксируется элементами  памяти. В качестве элементов памяти могут использоваться триггеры. Каждое внутреннее состояние цифрового автомата опредиляется исходным состоянием триггеров и последовательностью входных сигналов, действующих на входе в данный момент времени, поэтому такие устройства называются последовательностными схемами. К последователностным схемам можно отнести: триггеры, счетчики, регистры. В общем случае структурная схема цифрового автомата может быть представлена в виде набора трех узлов: комбинационной схемы формирования выходных сигналов, комбинационной схемы формирования сигналов управленя триггерами и , собственно, памяти.

         На вход комбинационной схемы  управления триггерами поступют  комбинации входных сигналов  x₁,x₂, … x_k, комбинации сигналов, отражающих состояние элементов памяти Q₁,Q₂, … Q_m. С учетом этих множеств комбинационная схема формирует серии сигналов, управляющих состоянием триггеров. Кодовые комбинации состояния триггеров образуют внутренние состояния цифрового автомата, которые принято обозначать буквой a.

         Комбинационная схема формирования  выходных сигналов создает сигналы  y₁,y₂, … y_р, которые могут использоваться для управления некоторыми узлами, для активизации прцессов в других схемах. Эти сигналы могут зависеть только от внутренних состояний: в этом случае устройство принято называть автоматом Мура. А если выходные сигналы зависят и от входных сигналов x₁,x₂, … x_k,то – автоматом мили.

         Таким образом, для задания  цифрового автомата необходимы  три множества:

          - множество входных сигналов: x₁,x₂, … x_k;

          - множество выходных сигналов: y₁,y₂, … y_p;

          - множество внутренних состояний:a₁,a₂, … a_z;

          На указанных трех множествах задают две функции: функцию переходов и функцию выходов. Для автомата Мили эти функции имеют вид:

                                             a_(t+1)=f_(a(t),x(t))

                                             y_(t)= _(a(t),x(t));

где a_(t+1) – новое состояние автомата;

a_(t) – предыдущее состояние автомата;

x_(t) – сигналы на входе в данный момент времени. 

                         Рис. 2 Управляющее устройство со схемной логикой

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

  3.Разработка цифрового автомата по алгоритму функционирования

                3.1 Опредиление сотояний  управляющего устройства

         Работа цифрового автомата опредиляется алгоритмом функционирования(рис.4)

         В алгоритме блок РЕШЕНИЕ указывает  ,какой входной сигнал (признак)  опредиляет условие перехода, блок  ПРОЦЕСС – какие выходные сигналы  при данном переходе должен  сформировать автомат: 

                                     - Символ Процесс 
 
 

                                     - Символ Решеие 
 
 

                                     - Символ начала алгоритма и  окончания алгоритма

                              Рис. 3 Опредиление состояний МПА

         Послекаждого перехода фиксируется  состояние цифрового автомата. Исходное  состояние цифрового автомата  выбрано как состояние а0, т.е.  состояние «пуск» и «останов»  на алгоритме функционирования  обозночаются как а0. Каждое слейдущее  состояние цифрового автомата  отмечается на алгоритме после  символа «процесс».

По алгоритму  функционирования определено, что цифровое устройство будет иметь 11 внутренних состояний а: а0, а1, а2, а3, а4, а5, а6, а7, а8, а9, а10. Каждое из этих состояний необходимо закодировать N-разрядными двоичными числами, для указанного количества состояний использован 4-разрядный код 8-4-2-1 (таб. 1). Следовательно, память цифрового автомата представляет собой 4-разрядный параллельный регистр, т.е. содержит 4 триггера по одному на каждый разряд числа. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  3.2. Построение графа функционирования управляющего устройства

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

         По алгоритму функционирования  составляется граф переходов  автомата.

         Графом называется непустое конечное  множество узлов (вершин) вместе  с множеством дуг (ветвей), соединяющих  пары различных узлов. Если  каждой дуге приписано направление,  то граф называется ориентированным.  Если направления не указаны,  то граф называется неоринтированным.

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

Направление стрелки указывает предыдущее состояние  и слейдущее состояние а, над  стрелкой указывает внешнее событие,савшее причиной перехода (х),

Если х=0, то над стрелкой указывают х с  инверсией.

Если х= 1, то х – без инверсии.

Если х  отсутствует – ставят прочерк (-)

Буквами У1 и  У2 ….. указывают сигналы У , которые  должны быть равны 1, приданном переходе.

Если значения У равны 0 то ставят прочерк.

         По алгоритму функционирования  определено, что цифровое устройство  будет иметь 11 внутренних состояний  а: а0, а1, а2, а3, а4, а5, а6, а7, а8, а9, а10.   

                           Рис. 5 Граф переходов автомата 

3.3 Построение таблицы  функционирования  цифрового автомата

           Составляется таблица кодирования  состаяния МП автомата (таблица  1).

Таблица 1. Кодирование  состояний микропроцессорного автомата

          По заданию на курсовую работу  используем синхронные JK-триггеры ,работа которых предаставленна в таблице 2 ,а управление переходами триггеров из одного состояния в другое предоставленно в таблице 3

Таблица 2. Таблица  работы JK-триггера

Таблица 3. Таблица  переходов JK-триггера

       Где       - предыдущее  состояние триггера,     -состояние  триггера оьратное от предидущего

“-” – любое  значение сигнала на входе

         Таблица заполнено по графу  или алгоритму функционирования.

         Количество строк в таблице  равно количеству переходов в  графе.

         В заданных таблицах представлен  переход из состояния а0 в  а1,  эти состояния закодированны  соответственно двоичными числами  0000 и 0001, которые фиксируются состоянием  триггеров  Q4,Q3,Q2,Q1, в столбцах «исходное, новое» состояние автомата. Так как значения признаков Х отсутсвуют в столбцах «условие перехода» ставятся прочерки. В столбцах «сигналы управления триггерами» указаны значения J,K из таблиц переходов. Значения сигналов У1-У6 определенны по содержанию символа «процесс» в алгоритме функционирования или в графе. Если У1=У2=У6=1, то они указаны в символе «процесс», другие значения У не указаны, следовательно они равны 0, У1=У2=У6=0. Аналогично заполняются остальные строки таблицы. Если на переходе значения Х определены, то они указываются в условиях перехода. Если на переходе отсутствует символ «процесс», то все значения У равны 0.

                        3.4 Составление логических уравнений

         По таблице функционирования комбинационного узла цифрового автомата составляются аналитические выражения в совершенной дизьюктивной форме (СДНФ) для выходных сигналов У1-У6 и для входных сигналов триггеров J,K.

         СДНФ функции столько раз содержит  коньюнкцию аргументов сколько  раз она равна 1, если аргумент  равен 0, то он записывается  с инверсией, если аргумент  равен 1, то без инверсии. Между  отдельными выражениями ставится  знак дизьюнкция.

         После записи каждого выражения  в СДНФ, выполняется его упрощение,  если это возможно, методом Квайна, который основан на последовательном  применении двух операций: опнрации  склеивания и операции поглощения

                 ДЛЯ АВТОМАТА МИЛИ  АРГУМЕНТАМИ ЯВЛЯЮТСЯ

                              исходные состояния а и признаки х

         Значения аналитических выражения  для выходных сигналов У и  сигналов управления состоянием  триггеров предоставленны в базисе  И,ИЛИ,НЕ.

         Анализируя логические элементы  серии 555 можно сделать вывод,  что строить комбинационный узел  по аналитическим выражениям, записанным  в базисе И,ИЛИ,НЕ не рационально,  так как логические элементы, выполняющие операции коньюнкции  и дизьюнкции имеют только  по два входа. Более оптимальным  является вариант построеня комбинационного  узла цифрового автомата с  использованием элементов И-НЕ, так  как в заданном базисе предоставлены  элементы Шефера, имеющие по два,  по три, по четыре, по восемь  входов.