Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Минимизация числа переключений элементов памяти.
Расстояние между кодами по Хеминингу – это число разрядов, в которых эти коды различаются между собой. Алгоритм кодирования: 1) Определяем множество пар состояний, между которыми существует переход M. 2) Выбирается любая пара состояний, между которыми есть переход, один из них кодируется всеми нулями, а другой нулями и одной единицей.(00…01) 3) Из множества M удаляются пары состояний, которые уже закодированы M\(Si Sj), если станет равным 0, то процесс завершается. 4) Берем любую пару в которой одно состояние уже закодировано, а другое нет (*, Sq) Sq - незакодированное состояние, * - состояние закодировано. Далее кодируем это состояние. 5) Выбираем множество пар из M куда входит Sq (Mq) 6) Из Mq выбираем все закодированные состояния (Bq) 7) Строим множество кодов, имеющих расстояние d, с каждым кодом из состояния Bq 8) Для каждого кода из всех множеств Cdq определяется сумма расстояний по Хеммингу с каждым кодом из Bq Выбирается код, имеющий минимальную сумму и этот код приписывается Cq Деле возврат к пункту 3.
Пример:
1) Пары состояний M = {(1,2),(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)} 2) {1,2} => S1 = 000 S2 = 001
3) M = {(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)} 4) {2,4} q=4 5) Mq = {(2,4),(3,4),(4,5)} 6) Bq = {2} 7) C14 = {101,011} 8) 101 + 001 = 100 d =1 011 + 001 = 010 d =1 S4 = 101 3) M = {(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)} 4) {2,5} q=5 5) Mq = {(2,5),(1,5),(4,5)} 6) Bq = {2,4,1} 7) C15 = {011} C15 = {(111),(100)} C15 = {(100),(010)} 8) 011 + 001 = 010 011 + 101 = 110 011 + 000 = 110 111 + 001 = 110 111 + 101 = 010 111 + 000 = 111 100 + 001 = 101 100 + 101 = 001 100 + 000 = 100 010 + 001 = 011 010 + 101 = 111 010 + 000 = 010 S5 = 100 3) M = {(2,3,(3,4) } 4) {2,3} q=3 5) Mq = {(2,3),(3,4)} 6) Bq = {2,4} 7) C15 = {011} C15 = {(111)} C15 = {(100),(010)} 8) 011 + 001 = 010 011 + 101 = 110 111 + 001 = 110 111 + 101 = 010 S3 = 011 3) M = {0 } – конец цикла.
При кодировании мы не получили однозначное решение, т.е. можно было состоянию приписать разные коды в процессе алгоритма, чтобы получить следовательно можно одновременно постараться учесть соседей первого и второго рода и тем самым упростить схему.
Универсальный способ кодирования (для синхронного автомата). При данном способе кодирования используется унитарный код (1 из N), который содержит 1 единицу, а остальные 0. В этом случае число разрядов совпадает с числом состояний автомата. В данном способе кодирования число разрядов максимально возможно, большее число разрядов бессмыслимо, следовательно это приводит к большему числу триггеров. С другой стороны может значительно упроститься комбинационный узел формирующий функции возбуждения и его функционирование можно описать прямо по графу без минимизации булевых функций.
Для D триггера: D2 = q1⌐q2q3⌐x1 – любой код D2 = q1⌐x1 - унитарный код Для унитарного кода опущены ⌐q2⌐q3, так как если q1 = 1, то это однозначно подразумевает q2 = q3 = 0. Более того q1 = 1 невозможно ни для одного из оставшихся состояний автомата.
Пример:
0à1 0à1 D1 = q5x v q3x 5à1 3à1
0à1 D2 = q1⌐x 1à2
0à1 0à1 0à1 D3 = q1x v q2x v q4x 1à3 2à3 4à3
0à1 1à1 D4 = q2⌐x v q4⌐x 2à4 2à4
0à1 D5 = q3⌐x 3à5
Выражения могут быть еще несколько упрощено. Предположим, что в качестве элементов памяти используется RS триггер. R = 1, когда 1à0 обязательно R = 1, когда 0à0 можно S = 1, когда 0à1 обязательно S = 1, когда 1à1 возможно Для RS триггера сначала записываются функции обязательные, а там где возможно чтобы функция была равна 1 дописывают лишь в случае упрощения.
RS *0 0 à 0 01 0 à 1 10 1 à 0 0* 1 à 1 1à0 1à0 R1 = q1⌐X v q1X = q1 1à2 1à3 0à1 0à1 S1 = q5X v q3X = X(q1 v q3) 5à1 3à1 В функции R1, S1 входит обязательная конъюнкция, обеспечивающая переход 1à0 для R1 и 0à1 для S1. В R1 можно добавить конъюнкции переходов из 0à0, т.к. при этом R=* и может быть доопределено до 1. Упростить R=q - можно добавить только ⌐q1, однако при унитарном кодировании инверсное значение ⌐q не используется, а следовательно переходы 0à0 добавленные в R1 только усложнят функцию. Аналогично для S1 можно добавить конъюнкции соответствующие переходу 1à1, такой переход возможен, только если присутствует петля вокруг S1, в примере ее нет, значит получим окончательное значение R1 S1. 1à0 1à0 R2 = q2⌐X v q2X = q2 2à4 2à3
0à1 S2 = q1⌐X 1à2
1à0 R3 = q3 3à1 3à5
0à1 0à1 0à1 S3 = q1X v q2X v q4X = X(q1 v q2 v q4)
1à3 2à3 4à3
1à0 R4 = q4X 4à3
0à1 1à1 S4 = q2⌐X v q4⌐X = q2 2à4 4à4
R5 = q5X
S5 = q3⌐X
Автомат с дешифратором.
Схема имеет минимальное число элементов памяти и обладает положительными свойствами, характерными для унитарного кодирования. Каждому состоянию соответствует два кода с минимальным и максимальным числом разрядов, недостаток схемы – дополнительные затраты виде дешифратора. Два кода, предписанных одному состоянию, связаны между собой функцией дешифратора.
При кодировании состояний предполагаем наличие дешифратора. В данном случае 2à4 (2 входа, 4 выхода) Каждому состоянию соответствует два входа. При записи функции возбуждения в данном случае аргументами являются Yi и Xi, а переходы триггера 0à0; 0à1; 1à0; 1à1 рассматриваются относительно qi/ Рассмотрим D и RS триггера: В качестве элемента памяти используется 2 D триггера. На D подаем 1 при переходе 0à1; 1à1
0à1 0à1 1à1 0à1 1à1 D1 = Y0⌐X v Y0X v Y1⌐X v Y2⌐X v Y3⌐X = Y0 v ⌐X (Y1 v Y2 v Y3) 1à2 1à4 2à4 3à2 4à4
0à1 0à1 1à1 1à1 D2 = Y1X v Y1⌐X v Y3X v Y3⌐X = Y1 v Y3 2à3 2à4 4à3 4à4
Далее RS триггер (R1 – сброс 1 разряда)
1à0 1à0 0à0 R1 = Y1X v Y3X v Y2X 2à3 4à3 3à1
0à1 0à1 1à1 1à1 0à1 S1 = Y0⌐X v Y2⌐X v Y1⌐X v Y3⌐X v Y0X = ⌐X (Y0 v Y2) v Y0X 1à2 3à2 2à4 4à4 1à4
1à0 1à0 0à0 R2 = Y2X v Y2⌐X v Y0⌐X = Y2 3à1 3à2 1à2
0à1 0à1 0à1 1à1 1à1 S2 = Y0X v Y1⌐X v Y1X v Y3X v Y3⌐X = Y0X v Y1 1à4 2à4 2à3 4à3 4à4
Асинхронные автоматы.
Ранее рассматривались:
т.е.раньше неявно присутствовал синхроимпульс. Наличие синхроимпульса позволяло осуществлять переход, при отсутствии его автомат остается в текущем состоянии. По существу синхроимпульс является дополнительным входным сигналом. Входные сигналы можно разделить в зависимости от наличия синхроимпульса:
С – синхроимпульс Пример:
Разновидностью данного сигнала является импульсный сигнал
Новое входное значение появляется после изменений предыдущего значения, т.е. длительности 0 и 1 могут быть разными.
Асинхронным автоматом называется автомат, изменение состояния которого могут происходить в произвольные моменты времени, и эти моменты времени определяются сменой входного сигнала. Тип автомата определяется типом входного сигнала. Если входной сигнал потенциален, то автомат асинхронный, в противном случае – синхронный. При асинхронной реализации автомата для обеспечения устойчивой его работы все его состояния должны быть устойчивыми (аналогично петли СИ в синхронном автомате). Состояние Si называется устойчивым, если при переходе в это состояние под воздействием входного сигнала Pk автомат остается в этом состоянии до тех пор, пока входной сигнал не станет отличаться от Pk.
Автомат будет асинхронным, если уже на абстрактном уровне все его состояния - устойчивы. Пример асинхронного автомата: Составим таблицу переходов:
0 – устойчивое состояние (петля) Проверка устойчивости: S1 à S3 (двигаемся по строке, а потом по столбцу) Для проверки является ли автомат асинхронным (по таблице переходов) вначале выделяем переходы соответствующие петлям вокруг состояний. В каждой строке с номером I обводим состояние Si, затем проверяется устойчивость переходов из каждого состояния. Например переход S1 à S3 проверяется следующим образом: 1) Смотрится в строке с текущем состоянием под воздействием входного сигнала в какое состояние он должен перейти (горизонтальное движение стрелки) 2) Затем в столбце соответствующим данному сигналу ищется состояние, в которое переходит автомат, но отмеченное кружком (движение вертикальное). 3) Если все переходы попадают в отмеченное состояние, то все состояния устойчивы и автомат может быть асинхронным.
|
|||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-12-15; просмотров: 36; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.224.0.25 (0.043 с.) |