^ ФИЗИЧЕСКИЕ ПРОЦЕССЫ
В ЭЛЕКТРОННЫХ ПРИБОРАХ
УДК 681.3.14/21
ИЗМЕНЕНИЕ ЧИСЛА РАЗРЯДОВ КОДА ВНУТРЕННИХ СОСТОЯНИЙ ПРИ МИНИМИЗАЦИИ ПОТРЕБЛЯЕМОЙ МОЩНОСТИ КОНЕЧНЫХ АВТОМАТОВ © 2012 г. В. В. Соловьев
Высший государственный колледж связи Республика Беларусь, 220114 Минск, ул. Скорины, 8/2 Поступила в редакцию 19.09.2011 г.
Рассмотрены два эвристических метода кодирования внутренних состояний конечных автоматов для снижения потребляемой мощности: в первом подходе предполагается постоянное значение длины кода внутренних состояний, во втором подходе число разрядов кода изменяется от минимального значения до момента, когда увеличение разрядности кода не приводит к снижению потребляемой мощности. Показано, что второй подход отличается малой вычислительной мощностью, что допускает его использование для конечных автоматов с большим числом состояний. Экспериментально доказано, что первый метод позволяет снизить потребляемую мощность конечных автоматов по сравнению с алгоритмом NOVA в среднем на 39% (для отдельных примеров — на 68%); а второй метод, по сравнению с первым позволяет в отдельных случаях снизить потребляемую мощность на 34%. Даны рекомендации для практического использования каждого метода, определены перспективные направления дальнейших исследований в данной области.
ВВЕДЕНИЕ
В последнее время в связи с широким использованием переносных и бортовых встроенных систем (мобильные телефоны, плееры, навигаторы, космические системы управления) особую актуальность приобретает задача снижения потребляемой мощности цифровых систем. Имеется несколько подходов к решению данной задачи: технологические (использование энергосберегающих технологий); логические (применение специальных методов синтеза); системные (управление частотой синхронизации и напряжением питания для отдельных частей системы) и др. Одним из путей решения указанной проблемы является уменьшение потребляемой мощности конечных автоматов. Как известно, конечные автоматы широко используются в различных цифровых системах в качестве контроллеров, стандартных функциональных узлов, а также оригинальных после-довательностных схем.
Известно множество подходов к решению задачи снижения потребляемой мощности конечных автоматов, например, с помощью специального кодирования внутренних состояний [1—4], путем декомпозиции больших схем на компоненты меньшего размера [5], использованием блоков встроенной памяти программируемых логических интегральных схем (ПЛИС) [6] и др. Обзор наиболее известных алгоритмов кодирования внутренних состояний конечных автоматов для снижения потребляемой мощности приведен в [7].
В данной работе рассматриваются два эвристических метода кодирования внутренних состояний конечных автоматов с целью минимизации потребляемой мощности. В первом подходе (алгоритм 1) строится множество всех возможных кодов, из которого последовательно выбираются наиболее подходящие коды внутренних состояний. Главным отличием предлагаемого подхода от известных является то, что при выборе кода для очередного состояния учитывается значение функции активности переключения элементов памяти при переходе из данного состояния к уже закодированным состояниям. При втором подходе (алгоритм 2) множество всех возможных кодов не формируется, а наиболее подходящий код для очередного состояния строится на основании определенных условий. Последнее позволяет значительно снизить вычислительную сложность второго метода и использовать его для кодирования конечных автоматов с большим числом состояний.
1. ПОСТАНОВКА ЗАДАЧИ
Конечный автомат будем характеризовать числом М внутренних состояний множества А = {аь ..., аМ}, числом Ь входных переменных множества X = {х1, ., хЬ}, а также параметром Я — минимальным числом разрядов кода, достаточных для кодирования внутренних состояний конечного автомата, Я > тИо§2М. Пусть элементы памяти конечного автомата строятся на ^-триггерах
(наиболее часто используемый тип триггеров при реализации памяти конечных автоматов). Целью задачи кодирования внутренних состояний конечных автоматов для минимизации потребляемой мощности является такое кодирование, при котором вероятность переключения состояний элементов памяти конечного автомата будет минимальна.
Пусть выполнено некоторое кодирование внутренних состояний конечного автомата и
каждому состоянию а, I = 1, М, приписан бинарный код к I длиной Я разрядов, где Я е [тИо§2М, М]. Для выполнения условия детерминированности поведения конечного автомата все коды состояний должны быть взаимно ортогональны (иметь различные значения по крайней мере в одном разряде). Число разрядов, в которых два кода
к и к, I = 1, М,] = 1, М, имеют различные значения, определяется расстоянием Хамминга:
H (k, kj) = £ кГ © k],
r=1
(1)
где к[ — значение бита г кода к, г = 1, Л; © — логическая операция Исключающее ИЛИ.
Пусть Wy — вероятность перехода между состояниями а, и а,, а, а, е А. Теперь задачу кодирования внутренних состояний конечного автомата с целью минимизации потребляемой мощности можно сформулировать следующим образом.
Задача 1. Найти кодирование внутренних состояний конечного автомата такое, что
(2)
(3)
ним состояниям конечного автомата. Однако, в отличие от графа автомата, граф 0Р является неориентированным графом, в котором вершины соединяются не дугами, а ребрами. Каждой дуге графа 0Р, соединяющей вершины а, и а, (а,, а, е А), приписывается вес м ,,, определяемый с помощью следующего выражения:
j = P (at ^ aj) + P (aj
b ),
(4)
M M
ZZwjx H ' kj ) =min
i=l j=1
при выполнении следующих ограничений:
R
^ kr © kr > 1, при любых kj и kj, i Ф j,
r =1
i = TM, j = IM-
Выполнение условия (2) обеспечивает нахождение минимальной потребляемой мощности, а выполнение ограничений (3) — детерминированность поведения конечного автомата. В общем случае задача 1 является ^Р-полной задачей [1], в связи с чем точные методы ее решения не имеют практического применения. Поэтому, как правило, для решения задачи 1 используются различные эвристические методы.
При решении задачи кодирования внутренних состояний вместо графа автомата используется граф GP вероятностей переходов между состояниями конечного автомата [1]. Вершины графа GP, как и в графе автомата, соответствуют внутрен-
где Р(а, ^ а) и Р(а, ^ а) — вероятность перехода из состояния а, в состояние а, и из состояния а, в состояние а, соответственно.
Кроме того, граф 0Р не имеет петель, которые в графе автомата соответствуют переходам из некоторого состояния в то же самое состояние. Дело в том, что при переходе автомата из некоторого внутреннего состояния в то же самое состояние не происходит переключений элементов памяти и потребляемая мощность не рассеивается. Методика определения вероятностей переходов между состояниями конечного автомата Р(а, ^ а), а, а, е А, на основании вероятностей появления единиц (нулей) на каждом входе конечного автомата приведена в [8].
2. ПОСЛЕДОВАТЕЛЬНЫЙ алгоритм РЕШЕНИЯ ЗАДАЧИ 1
Главной идеей предлагаемого алгоритма является последовательное (за исключением первых двух состояний) назначение кодов внутренним состояниям конечного автомата. Обозначим через КЯ множество всех возможных Я-разрядных бинарных кодов; К — множество кодов, выбранных для кодирования внутренних состояний конечного автомата. В процессе кодирования состояний коды будут последовательно выбираться из множества КЯ и добавляться в множество К. Определим также два подмножества состояний: Ас — множество состояний, которым назначены коды, и Аи — множество состояний, которым коды еще не назначены, А = Ас и Аи.
Суть предлагаемого алгоритма 1 для решения задачи 1 заключается в следующем. Вначале в графе 0Р находятся два наиболее связанных состояния и им назначается два кода из множества КЯ с минимальным расстоянием Хамминга. Затем из еще не закодированных состояний множества Аи выбирается состояние а,, которое в графе 0Р наиболее сильно связано с уже закодированными состояниями множества Ас. В процессе выбора кода к, для состояния а, учитывается значение функции у(а;, к) активности переключения элементов памяти при переходе конечного автомата
R
из состояния а, к уже закодированным состояниям множества Ас:
у(а1, к) = £ к,, х Н{к,, к]), к, е Xя, (5)
а^Лс
где Wy — вес ребра графа ОР, соединяющего состояния а, и а; к; — код состояния а, а, е Ас. Состоянию а, присваивается код к, для которого значение функции у(а,,к,) минимально. Процесс кодирования внутренних состояний продолжается до тех пор, пока все состояния конечного автомата не будут закодированы.
Алгоритм 1
1. Строится граф ОР вероятностей переходов между состояниями. Формируется множество кодов К8. Полагается Аи :=А.
2. В графе ОР находятся два состояния а, и а, для которых значение веса является максимальным.
3. Для состояний а, и а, в множестве кодов К8 выбираются коды к и к, для которых И(к,, к) = 1.
4. Коды к1 и к, назначаются состояниям а, и а, соответственно. Полагается К8 := К8\{к,, к}, К := {к,, к;}, Ас := {а,,а,}, А„:= АЦ\{а, а,}.
5. Если Аи = 0, где 0 — пустое множество, то выполняется переход к пункту 9.
6. В множестве Аивыбирается состояние а,, для которого сумма весов дуг графа Ор, соединяющих состояние а с состояниями множества Ас, максимальна.
7. В множестве К8 выбирается код к,, для которого значение функции у(а ,, к,), вычисленное согласно (5), минимально.
8. Код к1 назначается состоянию а,. Полагается К8 := К8\{к,}, К := К и {к,}, Ас := Ас и {а,}, Аи := := АД{а,}. Выполняется переход к пункту 5.
9. Конец.
Пример 1. Рассмотрим использование алгоритма 1 для кодирования внутренних состояний конечного автомата, заданного графом автомата на рис. 1. Пусть вероятности появления единицы и нуля на каждом входе конечного автомата одинаковы и равны 0.5. Тогда вероятности переходов между внутренними состояниями конечного автомата, вычисленные согласно [8], имеют следующие значения: Р(а1 ^ а2) = 3/22, Р(а2 ^ а1) = Р(а2 ^ а3) = Р(а4 ^ а3) = 2/22, Р(а3 ^ а4) = 4/22, Р(а4 ^ а1) = Р(а4 ^ а2) = 1/22. На основании вероятностей переходов между состояниями согласно (4) определяются значения весов ребер
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.