Конспект лекций Киров 2010 удк 681. 332




НазваниеКонспект лекций Киров 2010 удк 681. 332
страница14/17
Дата публикации21.08.2013
Размер0.75 Mb.
ТипКонспект
zadocs.ru > Химия > Конспект
1   ...   9   10   11   12   13   14   15   16   17
^

15. Кодирование состояний автомата


Кодирование внутренних состояний автомата заключается в сопоставлении каждому состоянию автомата набора значений соответствующих состояний элементарных автоматов памяти.

, т.е. переход автомата из одного состояния в другое осуществляется за счёт изменения внутренних состояний элементов памяти.

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

1. Элементарные автоматы памяти имеют различные, хотя достаточно близкие, времена срабатывания.

2. Различные времена задержки сигналов (функции возбуждения), поступающих на входы элементов памяти.

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

В процессе перехода из состояния am в состояние as под действием входного сигнала zf автомат может оказаться в некотором промежуточном состоянии ak или al. Если затем при том же самом входном сигнале автомат из состояния ak или al перейдёт в состояние as, то такие состязания являются допустимыми или некритическими.

Если же под действием входного сигнала zf автомат перейдёт из промежуточного состояния аk в некоторое состояние аj, то правильность работы автомата будет нарушена и такие состязания называются критическими или гонками.

Существует несколько способов ликвидации гонок. Рассмотрим лишь основные из них.
^ Аппаратные способы:

Первый способ состоит в тактировании (стробировании) входных сигналов автомата импульсами определенной длительности.

Предполагается, что кроме входных каналов (x1…….xl) имеется ещё один входной канал c от генератора синхроимпульсов.

Таким образом, входным сигналом при переходе из am в as будет не zf , а zf&c



Если длительность импульса c меньше самого короткого пути прохождения сигналов обратной связи, то к моменту перехода в промежуточное состояние аk входной сигнал с=0, следовательно, переход не может осуществиться.

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

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

^

15.1. Метод противогоночного кодирования состояний автомата


Пусть существуют две пары двоичных кодов и . Пары называют развязанными, если i-ый разряд кода принимает одно значение в паре и противоположное в паре , иначе пары называются связными.

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

Алгоритм противогоночного кодирования заключается в последовательном развязывании пар переходов.
Алгоритм:

Пусть имеются состояния автомата - (am,as), (ak,al)

Значение i-го разряда в данных состояниях - , , i=1,I.

Присвоить i:=1.

  1. Если при некотором i значение i-ого разряда кодов образуют набор соответственно 0011 или 1100,то переходим к пункту 8, иначе к пункту 3.

  2. Если при некотором i значение i-ого разряда образуют один из наборов *011, 0*11, 00*1, 001*, *01*, **11, 0**1, 00**, *0*1, 0*1*, ***1, 0***, *0**, **1*, ****, то переходим к пункту 4, иначе к пункту 5.

  3. Доопределить неопределённые значения i-ого разряда до набора 0011, перейти к пункту 8.

  4. Если значения i-ого разряда образуют один из наборов *100, 1*00, 110*, …, то перейти к пункту 6. Иначе к пункту 7.

  5. Доопределить неопределённые значения i-ого разряда до набора 1100 и перейти к пункту 8.

  6. Дополнить коды состояния автомата одним неопределённым разрядом и перейти к пункту 2.

8. Пары переходов (am,as), (ak,al) развязаны.

ПРИМЕР:




a1

a2

a3

a4

a5

a6

a7

Z1

a2

a2

a4

а4

a6

a6

-

Z2

a1

a3

a3

а1

a3

-

-

Z3

-

a5

a7

-

a5

-

a7

Z1: (a1,a2) (a2,a2) (a3,a4) (a4,a4) (a5,a6) (a6,a6)

(а1,а2) (а2,а2) – Состязания некритические

(а1,а2) (а3,а4) – Состязания критические

Рассмотрим всевозможные пары Z1.

Вводим код длиной 1.




1

2

3

4

a1

0

1

1

-

a2

0

0

0

0

a3

1

0

0

1

a4

1

0

1

-

a5

1

1

0

0

a6

1

1

-

-

a7

-

-

-

1

Сейчас все пары развязаны для z1.

Аналогично проверяем все пары Z2, Z3.

Z2=(a1,a1) (a2,a3) (a3,a3) (a4,a1) (a5,a3)

Z3=(a2,a5) (a3,a7) (a5,a5) (a7,a7)
Длина кода, полученная в результате применения алгоритма противогоночного кодирования, в большинстве случаев оказывается не минимальной, поскольку при введении нового разрядного кода могут развязаться пары переходов, которые уже были развязаны ранее. В связи с этим необходимо минимизировать длину получаемых кодов. Для этого исключается один из разрядов кодов, в результате чего некоторые пары могут оказаться связанными, поэтому применим алгоритм развязывания переходов и пробуем исключить еще один разряд и т.д. до тех пор, пока изменить длину кода возможно.




1

2

3

4

5

a1

0

1

1

-

0

a2

0

0

0

0

0

a3

1

0

0

1

-

a4

1

0

1

-

-

a5

1

1

0

0

1

a6

1

1

-

-

1

a7

-

0

-

1

-


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

1   ...   9   10   11   12   13   14   15   16   17

Похожие:

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине "инвестирование"
Конспект лекций по дисциплине «Инвестирование» для студентов экономических специальностей всех форм обучения Сост.: В. М. Гридасов...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине “Каналообразующие устройства”, 2010 Перечень лекций
Тема №1 (4 часа) Назначение, основные параметры и состав каналообразующих устройств 5

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Витебск 2010 министерство образования республики...
Конспект предназначен для самостоятельного изучения, подготовки к практическим занятиям и экзамену по экономической теории

Конспект лекций Киров 2010 удк 681. 332 iconЭтика курс лекций (на основе книги: Этика (конспект лекций)
Этика (конспект лекций). – М.: «Приор-издат», 2002. Автор-составитель Аристотель. Никомахова этика. Сочинения: в 4-х т. Т. М.: Мысль,...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов направления 070104 «Морской и речной транспорт»
Конспект лекций рассмотрены и одобрены на заседании кафедры «Судовождение» кгмту

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по патологической анатомии инфекционных болезней. Киров, 2003
Вирусные инфекции представляют собой одну из многочисленных групп инфекционных заболеваний разнообразных по клиническому течению...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Утверждено Редакционно-издательским советом в качестве...
Чижов М. И., Юров А. Н. Информатика и информационные системы: Конспект лекций. Воронеж: Воронеж гос техн ун-т, 2003. 148 с

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине «Безопасность жизнедеятельности»
Безопасность в чрезвычайных ситуациях и гражданская оборона. Конспект лекций. Рубцов Б. Н. М. Миит, 2001

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций
Цифровые системы управления и обработки информации. Конспект лекций. Модуль 1: Организация и программирование систем чпу. (для студентов...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов сектора второго высшего образования...
Конспект лекций разработан кандидатом экономических наук, доцентом кафедры «Экономическая теория и кибернетика» Одесского государственного...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов