Технология разработки алгоритмически сложных цифровых систем с помощью автоматического синтеза микропрограммных автоматов

Начало статьи

4. Примеры применения

В процессе отладки и апробации разработанной системы синтеза микропрограммных автоматов были написаны микропрограммы и синтезированы схемы для большого количества устройств, некоторые из них коротко описаны ниже. Отметим, что после генерации схемы всегда осуществлялась ее симуляция в HLCCAD/IEESD, генерация синтезируемого VHDL-описания микропрограммного автомата и загрузка его в ПЛИС фирмы Altera. На всех этапах использовались тесты, подготовленные еще для микропрограммы.

4.1. Устройство для кодирования-декодирования кодов Хэмминга

Постановка задачи

Помехоустойчивый код — двоичный код, позволяющий обнаруживать и корректировать ошибки при передаче данных. Код Хэмминга обнаруживает ошибки в двух битах и позволяет корректировать один бит. Контрольные разряды занимают позиции с номерами i = 2^j (j = 0, 1, 2, …). Значения контрольных разрядов равны сумме разрядов, номера которых больше номера контрольного разряда и таких, что двоичное представление номера содержит единицу в разряде j, начиная с младших разрядов: B₂ = B₃ + B₆ + B₇ + B₁₀ + B₁₁ (если длина исходного слова 7 бит).

Если слово, полученное после подстановки контрольных разрядов, передано правильно, то выражение, полученное в результате сложения контрольных разрядов и суммы, вычисленной по вышеуказанному правилу, будет равно 0: S₂ = B₂ + B₃ + B₆ +B₇ + B₁₀ + B₁₁ (длина исходного слова 7 бит).

Если какой-то разряд исказился, некоторые значения выражений будут равны 1. Пусть исказился B_i, тогда первое значение (S₁) станет равно 1, если двоичное представление i содержит 1 в младшем разряде. Второе значение (S₂), если во втором и т.д. Величина …, S₃, S₂ , S₁ — номер искаженного разряда.

Решение задачи

Описание интерфейса проектируемого устройства:

• Ic — вход для кодирования (7 бит);
• Id — вход для декодирования (11 бит);
• Oc — закодированное слово Ic (11 бит);
• Od — декодированное слово Id (7 бит).

В случае длины слов 7 бит имеем следующие формулы для вычисления значений контрольных разрядов:

• B1 = B3 + B5 + B7 + B9 + B11;
• B2 = B3 + B6 + B7 + B10+ B11;
• B4 = B5 + B6 + B7;
• B8 = B9 + B10+ B11.

Так как процессы кодирования и декодирования должны выполняться параллельно и независимо друг от друга, то целесообразно реализовать эти процессы в виде двух МПА.

Микропрограмма для процесса кодирования:

Микропрограмма для процесса декодирования:

4.2. Устройство для распознавания кода Морзе

Постановка задачи

Необходимо спроектировать устройство, декодирующее текстовую информацию из сигналов азбуки Морзе. Каждая буква представляется в виде последовательности из точек и тире:

A .-
J .—
S …
B -…
K -.-
T —
C -.-.
L .-..
U ..-
D -..
M —
V …-
E .
N -.
W .—
F ..-.
O —
X -..-
G —.
P .—.
Y -.—
H ….
Q —.-
Z —..
I ..
R .-.

Характеристики сигналов:

• Сигналы в виде «точек» и «тире» поступают на вход DI. Значение сигнала DI считывается по переднему фронту сигнала Clk.
• Сигналы «точка» и «тире» разделяются паузами.
• Сигнал «точка» соответствует одной «1» между двумя паузами.
• Сигнал «тире» соответствует трем «1» между двумя паузами.
• Пауза соответствует значению «0» на входе DI.
• Сигналы одной и той же буквы разделяются одной паузой.
• Между двумя буквами три паузы. На выходе Code необходимо устанавливать порядковый номер символа («A» = 0, «B» = 1, т. д.) в промежутке между мeжбуквенными паузами.

DI — сигналы азбуки Морзе.

Clk — синхронизирующий сигнал (DI).

Reset — асинхронный вход инициализации («1»).

Code — код декодированного символа.

Ready — признак готовности символа («0»—готов, «1» — нет).

Решение задачи

Микропрограмма:

4.3. Управляемый делитель частоты

Постановка задачи

На вход А подается меандр (периодический сигнал с равными длительностями 0 и 1). На вход В — число — коэффициент деления частоты. На выходе С нужно получить меандр с частотой А/В. На стабилизацию отводится один период выходной частоты, после чего должен следовать нулевой полупериод. Если В = 0, на С всегда должен быть 0.

Решение задачи

Микропрограмма:

4.4. Стек

Постановка задачи

Требуется спроектировать 8-разрядный стек с глубиной до 255 элементов, который позволяет:

• положить элемент в стек;
• взять значение вершины стека;
• убрать элемент из стека;
• узнать количество элементов в стеке;
• контролировать ошибки (попытка взять элемент из пустого стека);
• сбросить состояние стека и признак ошибки.

Решение задачи

Описание интерфейса проектируемого стека:

• Input — значение элемента;
• Output — значение вершины стека;
• Count — количество элементов (для пустого стека — 0);
• Reset — сброс стека (сброс при 1);
• Push — положить элемент с Input в стек (по переднему фронту);
• Pop — убрать элемент со стека (по переднему фронту);
• Error — признак ошибки (1 — ошибка).

Стек представляет собой регистр длиной 25×68=2048. Вершина стека — биты 0–7. По команде Push все биты регистра сдвигаются влево на 8 позиций и на освободившееся место записывается новый элемент. По команде Pop все биты регистра сдвигаются вправо на 8 позиций.

Микропрограмма, реализующая стек:

4.5. Устройство для проверки корректности штрих-кода

Постановка задачи

Требуется спроектировать устройство для проверки 13-разрядного штрих-кода системы EAN-13.

Пусть дан штрих-код «4601546003119». Для проверки правильности штрих-кода существует следующий алгоритм:

1. Складываются цифры, стоящие на четных местах штрих-кода 6+1+4+0+3+1=15.
2. Полученная сумма умножается на три 15×3=45.
3. Складываются цифры, стоящие на нечетных местах штрих-кода (кроме последней контрольной цифры) 4+0+5+6+0+1=16.
4. Полученные два числа складываются 45+16=61.
5. Отбрасываются десятки 61–60=1.
6. Полученное в пункте 5 число вычитается из десяти 10–1=9 (если в 5 пункте получили 0 — результат 0). Результат должен совпадать с контрольной цифрой (13-й цифрой). Если это не так, то указанный «штрих-код» — грубая подделка, а качество товара скорей всего невысоко.

Примеры

«4601546003119» — штрих-код верен.
«4601546003118» — штрих-код неверен.

Решение задачи

Описание интерфейса проектируемого стека:

• Code1-Code12 — первые 12 цифр штрих-кода;
• Code13 — 13-я цифра штрих-кода (контрольная);
• Error — некорректные входные данные (1— данные некорректны);
• Status — результат проверки (1 —штрих-код неверен или некорректные входные данные).

Микропрограмма:

5. Отладка микропрограмм, настраиваемая на исполнительные устройства

Нам представляется, что в практике разработок вполне реальной является следующая ситуация. Имеется набор исполнительных устройств — независимо функционирующих компонентов операционного автомата или, в общем случае, независимо функционирующих операционных автоматов. Создание требуемой цифровой системы фактически заключается в написании и отладке микропрограммы, реализующей требуемый комплекс функций. Какие способы решения подобных проблем предлагаются нами?

При наличии определенных пользователем (или заданных ему техническим заданием) операционных устройств и формата микрокоманды можно реализовать модели имеющихся операционных устройств с помощью языка микропрограммных автоматов: блоки памяти операционных устройств определяем с помощью команд резервирования памяти REG и FLAG, а функции операционных устройств реализуем как последовательности микрокоманд на ассемблере МPA, объединенные в микропрограммы или макрокоманды, сопределяемыми пользователями именами. Далее пользователи могут отлаживать микропрограммы, управляющие имеющимися операционными устройствами. По завершению отладки всех микропрограмм (или параллельно их отладке) пользователь может разработать генератор реальных машинных кодов для отлаживаемых подпрограмм. Эта задача может быть сильно упрощена при разумном в воде пользователем имен макрокоманд и подпрограмм, обеспечивающем табличное кодирование мнемоник в соответствующие поля микрокоманд. Кроме того, для ускорения создания генератора машинных кодов микропрограмм можно использовать разработанный нами ассемблер, настраиваемый на целевую архитектуру RtASM [8].

Для отладки генератора микропрограмм можно использовать дизассемблер и симуляцию дизассемблированных кодов с целью достижения эквивалентности результатов симуляции исходного текста и его ассемблированного (дизассемблированного) представления.

6. Использование в учебном процессе

Описанный в данной работе программный комплекс активно используется в учебном процессе математического факультета Гомельского государственного университета (Белоруссия). Ниже приведены примеры лабораторных и курсовых работ.

1. Разработка микропрограмм алгоритмически сложных цифровых устройств.
2. Исследования прикладных алгоритмов на выделение новых инструкций для расширения языка микропрограммных автоматов (МПА).
3. Анализ эффективности аппаратной реализации инструкций (операционных устройств) языка МПА.

7. Направление текущих разработок

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

• поддержка языка программирования С как средства описания алгоритмов функционирования устройств;
• генераторы типизированных параметрических систем;
• управляемая оптимизация генерируемых МПА.

Очевидно, что использование языка более высокого уровня, чем ассемблер, будет способствовать повышению производительности разработки микропрограмм. Для реализации этого направления в настоящее время разрабатываются язык CMPDL, в основе которого лежат конструкции языка С, которые могут быть скомпилированы в конструкции уже реализованного языка MPDL, в том числе арифметические и логические выражения, операторы условия, выбора, циклов, безусловного перехода и некоторые другие. Одновременно разрабатывается компилятор CMPDL→MPDL на базе созданного нами универсального синтаксического анализатора UniSAn.

Дальнейшим развитием такого подхода к повышению производительности разработчиков сложных алгоритмических устройств может быть создание визуальных редакторов для специализированных устройств, например, фильтров, шифраторов-дешифраторов, компрессоров-декомпрессоров, аудио- и видеокодеков и т. д. Разработчик в визуальном редакторе определяет параметры нужного ему устройства и получает исходный текст микропрограммы на CMPDL или MPDL, изкоторой по описанной выше технологии строится синтезируемое VHDL-описание микропрограммного автомата, реализующего требуемые функции.

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

Заключение

Описанные метод и средства разработки алгоритмически сложных устройств на основе автоматической генарации схем по отлаженным микропрограммам существенно сокращают сроки разработки, в то же время обеспечивая высокое быстродействие и приемлемое качество (в смысле аппаратных затрат) созданных схем. К сожалению, ввиду отстутствия реальных заказов, апробация и испытания в настоящее время проводились только на учебных примерах. Хочется надеяться, что настоящая публикация поможет нам найти разработчиков, решающих задачи соответствующей сложности.

Литература

1. Dolinsky M. S., Ziselman I. M., Harrasov A. A. Computer-Aided design of microprogrammed devices // Automatic Control and Computer Sciences. New York: Allerton Press. 1997. Vol.31. № 5.
2. Долинский М. С., Зисельман И. М., Харрасов А. Р. Автоматический синтез микропрограммных автоматов // Автоматика и вычислительная техника. Рига. 1997. № 5.
3. Долинский М. С., Харрасов А. А. Средства разработки цифровых устройств методом синтеза микропрограммных автоматов //Электоника. Минск. 1998. № 11–12.
4. Коршунов И. В. Автоматический синтез микропрограммных автоматов // Новые математические методы и компьютерные технологии в проектировании, производстве инаучных исследованиях. Материалы III Республиканской научно-технической конференции студентов и аспирантов 13–18 марта 2000 г. Гомель.
5. Коршунов И. В. Метод автоматического построения микропрограммных автоматов // Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях. Материалы IV Республиканской научно-технической конференции студентов и аспирантов 19–22 марта 2001 г. Гомель.
6. Долинский М., Литвинов В., Галатин А., Ермолаев И. HLCCAD — среда редактирования, симуляции и отладки аппаратного обеспечения. Компоненты и Технологии. 2003. № 1.
7. Долинский М., Ермолаев И., Толкачев А., Гончаренко И. WInter — среда отладки программного обеспечения мультипроцессорных систем. Компоненты и Технологии. 2003. № 2.
8. http://NewIT.gsu.unibel.by.
9. Баранов С. И. Синтез микропрограммных автоматов. Л.: Машиностроение. 1979.
10. Майоров С. А., Новиков Г. И. Структура электронных вычислительных машин. Л.: Машиностроение. 1979.
11. Каган Б. М. Электронные вычислительные машины и системы. М.: Энергия. 1979.
12. Семенов Н., Каршенбойм И. Микропрограммные автоматы на базе специализированных ИС // Chip news. 2000. № 7.
13. Лобанов В. Технический минимум пользователя САПР MAX+PLUS II // Chip news. 2001. № 1.
14. Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов. М.: Энергоатомиздат. 1989.
15. Tolkachev A., Dolinsky M. Hardware Implementation of Complex Data Processing Algorithms. EUROMICRO/DSD-2003.