Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Этап 3. Кодирование состояний автомата.
1). Определяем разрядность кода L, то есть минимально необходимое количество элементарных автоматов или, иначе говоря, разрядность памяти автомата. Так как система счисления двоичная, то
где |S| – мощность множества состояний, ]…[ – ближайшее целое число сверху. В данном примере |S| = 5, получаем L = 3. Таким образом, линейка памяти автомата трехразрядная, то есть память строится на трех триггерах. 2). Определяем двоичный код каждого состояния автомата. Существует множество алгоритмов кодирования состояний, например, противогоночное, экономичное, соседнее кодирование и ряд других. В случае противогоночного кодирования стремятся к переключению в каждый дискретный момент времени только одного разряда, чтобы избежать ложных срабатываний элементов памяти из-за гонок (критических состязаний) в комбинационной схеме. Этот способ актуален для асинхронных схем. Обоснование эффективности противогоночного кодирования относится к давним разработкам – периода элементной базы малой степени интеграции. В настоящее время, когда в СБИС время срабатывания триггера мало отличается от времени задержки распространения сигнала в логическом элементе и б о льшее значение имеют задержки в линиях связи (слоях металлизации на кристалле), значительно выгоднее проектировать синхронный автомат, не заботясь о противогоночном кодировании, требующем дополнительных аппаратных затрат. Воспользуемся одним из возможных алгоритмом кодирования, сочетающим достоинства экономичного, соседнего и противогоночного методов. Шаг 1. Для состояния, вершине которого на графе инцидентно наибольшее количество входящих дуг, выбираем нулевой код. Шаг 2 – итерационный. Находим состояние, наиболее связанное с ранее закодированными. Из всех свободных кодовых комбинаций выбираем ту, для которой сумма кодовых расстояний*) с уже существующими кодами состояний, связанных с рассматриваемым, будет минимальной. Кратность связей учитываем введением поправочного коэффициента kсв. Очевидно, число итераций шага 2 равно |S| – 1.
Рассмотрим применение сформулированного алгоритма к кодированию состояний данного конкретного автомата. Шаг 1. Наибольшее количество входящих дуг на графе переходов инцидентно вершине s1. (полустепени захода: p+(s1) = 4, p+(s3) = 3, p+(s2) = p+(s4) = p+(s5) = 1). Состоянию s1 усваиваем нулевой код: s1 = 000. Шаг 2. Итерация 2.1. Вершины s2, s3, s4, s5 связаны с вершиной s1 каждое одной дугой. Не имеет значения, какое из состояний предпочесть. Выбираем s2. Очевидно, код s2 должен содержать единицу в любом разряде, обеспечивая d21 = 1. Пусть s2 = 001. Итерация 2.2. С подмножеством вершин {s1, s2} наиболее связана вершина s3 (тремя дугами: s1®s3, s2®s3, s3®s2); вершины s4 и s5 связаны с {s1, s2} одной дугой каждая. Следовательно, очередным кодируемым состоянием должно быть s3. Рассчитываем кодовые расстояния:
Поскольку вершины s2 и s3 связывают две дуги, d32 входит в сумму с поправочным коэффициентом kсв = 2. Наименьшим значением суммы кодовых расстояний обладают комбинации 011 и 101. Предпочтение можно отдать любой из них. Пусть s3 = 011. Итерация 2.3. Подмножество закодированых вершин: {s1, s2, s3}. Число связей для s4 – две, для s5 – две; выбор s4 или s5 равновероятный. Кодируем состояние s4:
Наименьшее значение суммы кодовых расстояний соответствует комбинации 010. Итак, s4 = 010. Итерация 2.4. Кодируем последнее оставшееся незакодированным состояние s5:
Имеем: s5 = 110. Сведем полученные коды состояний автомата в общую таблицу (рис. 9.2). Разряды кода обозначим Q2Q1Q0, где Q0 – младший разряд.
Рис. 9.2. Результат этапа кодирования состояний КА
|