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


НазваниеКонспект лекций Киров 2010 удк 681. 332
страница14/17
Дата публикации06.04.2013
Размер0.73 Mb.
ТипКонспект
userdocs.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 удк 681. 332 iconКонспект лекций/В. Н. Уляков. Чебоксары: Изд-во Чебоксарского политехнического...
Экономическая безопасность: конспект лекций/В. Н. Уляков. Чебоксары: Изд-во Чебоксарского политехнического института (филиал) мгоу,...
Конспект лекций Киров 2010 удк 681. 332 iconКонспекты лекций для специальностей «Бухгалтерский учет, анализ и...
Введение. Современное состояние информационных ресурсов и информатизации общества
Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Москва, 2011 ббк 63. 3 Удк 94 (100) «654»
Составители: проф., д и н. Бодрова Е. В., доц., к и н. Гусарова М. Н., к и н доц. Захаров В. Ю
Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов направления 070104 «Морской и речной транспорт»
Конспект лекций рассмотрены и одобрены на заседании кафедры «Судовождение» кгмту
Конспект лекций Киров 2010 удк 681. 332 iconКраткий конспект лекций для студентов дневного и заочного отделения...
Психология труда. Краткий конспект лекций /Сост. М. Д. Лапина – Мариуполь, 2004, 34 с
Конспект лекций Киров 2010 удк 681. 332 iconКомпьютерная графика и web дизайн Конспект лекций Днепропетровск
Конспект лекций по дисциплине “Компьютерная графика и web дизайн” содержит теоретические сведения для подготовки к зачету. В конспекте...
Конспект лекций Киров 2010 удк 681. 332 iconИстория науки и техники конспект лекций Омск
Конспект лекций предназначен для студентов специальности 070601 «Дизайн», 032401 «Реклама» очной, заочной и дистанционной формы обучения....
Конспект лекций Киров 2010 удк 681. 332 iconС. П. Филин Концепции современного естествознания: конспект лекций
Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования РФ и...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


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