![[Перевод] Решение FizzBuzz на FPGA с генерацией видео](https://habrastorage.org/getpro/geektimes/post_images/e91/e9f/d54/e91e9fd5485330ead0b0588fa711493f.jpg "[Перевод] Решение FizzBuzz на FPGA с генерацией видео")
FizzBuzz на плате FPGA. Плата генерирует прямой видеосигнал VGA с анимацией слов “Fizz” и “Buzz”
Если Вы не знакомы с задачей FizzBuzz, то она заключается в написании программы, которая печатает числа от 1 до 100, где кратные трём заменяются словом Fizz, кратные пяти — словом Buzz, а кратные пятнадцати — FizzBuzz. Поскольку FizzBuzz реализуется в нескольких строчках кода, эту задачу дают на собеседованиях, чтобы отсеять совсем не умеющих программировать. Но на FPGA решение гораздо сложнее.
FPGA (программируемая пользователем вентильная матрица) — интересная микросхема. Она программируется на выполнение произвольной цифровой логики. Можно сконструировать сложную схему, не прокладывая физические каналы между отдельными вентилями и триггерами. Микросхема способна превратиться во что угодно, от логического анализатора до микропроцессора и видеогенератора. Для этого проекта я использовал плату Mojo FPGA (на фото).
Плата Mojo FPGA. Большой чип на плате — это Spartan 6 FPGA
Генерация сигнала VGA
Для FPGA существует определённая кривая обучаемости, потому что здесь вы разрабатываете схемы, а не пишете программное обеспечение, которое работает на процессоре. Но если вы с помощью FPGA можете заставить мигать пять светодиодов, то в целом готовы реализовать выдачу видеосигнала VGA. Формат видео VGA намного проще, чем я ожидал: всего три сигнала для пикселей (красный, зелёный и синий) и два сигнала для горизонтальной и вертикальной синхронизации.
Основная идея в том, чтобы использовать два счётчика: один для пикселей по горизонтали, а второй для вертикальных линий. В каждой точке экрана по этим координатам генерируется нужный цвет пикселя. Кроме того, генерируются импульсы горизонтальной и вертикальной синхронизации, когда счётчики находятся в соответствующей позиции. Я использовал базовое разрешение VGA 640×4802, где нужно вести отсчёт до 800 и 5251 11. По горизонтали в каждой линии 800 пикселей: 640 видимых, 16 пустых, 96 на горизонтальную синхронизацию и ещё 48 пустых пикселей. (Такие странные параметры используются по историческим причинам). Между тем, вертикальный счётчик должен отсчитывать 525 линий: 480 линий изображения, 10 пустых, 2 линии вертикальной синхронизации и ещё 33 пустые.
Собрав всё вместе, я разработал модуль vga (исходный код) для генерации сигналов VGA. Код написан на Verilog, это стандартный язык для FPGA. Не буду подробно объяснять Verilog: надеюсь, достаточно показать, как он работает. В приведённом ниже коде реализованы счётчики x и y. Первая строка указывает, что действие предпринято на положительном краю каждого (50 МГц) тактового сигнала. Следующая строка переключает clk25 на каждом такте, генерируя сигнал 25 МГц. (Путаница только в том, что <= указывает на присвоение, а не сравнение). Этот код увеличивает счетчик x с 0 до 799. В конце каждой строки y увеличивается с 0 до 524. Таким образом код генерирует необходимые счётчики пикселей и строк.
always @(posedge clk) begin clk25 <= ~clk25; if (clk25 == 1) begin if (x < 799) begin x <= x + 1; end else begin x <= 0; if (y < 524) begin y <= y + 1; end else begin y <= 0; end end end end Хотя язык Verilog похож на обычный язык программирования, он работает совсем иначе. Этот код не генерирует инструкции, которые последовательно выполняются процессором, а создаёт схему в чипе FPGA. Он создаёт регистры из триггеров для clk25, x и y. Для увеличения x и y генерируются двоичные сумматоры. Операторы if превращаются в логические вентили компараторов, контролирующих регистры. Вся схема работает параллельно, срабатывая на тактовые импульсы 50 МГц. Для понимания FPGA нужно выйти из последовательного программного мышления и думать о базовых схемах.
Возвращаясь к модулю vga, код ниже генерирует сигналы горизонтальной и вертикальной синхронизации по счётчикам x и y. Кроме того, флаг valid указывает на область 640×480, где должен генерироваться видеосигнал; за пределами этой области экран должен быть пустым. Как и прежде, эти операторы генерируют логические элементы для проверки условий, а не создают код.
assign hsync = x < (640 + 16) || x >= (640 + 16 + 96); assign vsync = y < (480 + 10) || y >= (480 + 10 + 2); assign valid = (x < 640) && (y < 480); «Полезная» часть сигнала VGA — это красные, зелёные и синие пиксельные сигналы, которые управляют тем, что появляется на экране. Чтобы проверить схему, я написал несколько строк для активации r, g и b в разных областях экрана, заглушив всё за пределами видимой ('valid') области3 (вопросительный знак является тернарным условным оператором, как в Java).
if (valid) begin rval = (x < 120 || x > 320) ? 1 : 0; gval = (y < 240 || y > 360) ? 1 : 0; bval = (x > 500 && (y < 120 || y > 300)) ? 1 : 0; end else begin rval = 0; gval = 0; bval = 0; endЯ запустил код на плате FPGA — и ничего не произошло. Монитор остался чёрным. Что же пошло не так? К счастью, через пару секунд4 монитор завершил нормальный цикл запуска и отобразил выдачу. Меня приятно удивило, что выдача VGA сработала с первого раза, пусть это и произвольные цветные блоки.5
Моя первая программа VGA генерирует произвольные цветные блоки на экране. Не очень осмысленно, зато всё работает нормально
Вывод символов на экран
Следующий шаг — отображение текстовых символов на экране. Я реализовал модуль генерации пикселей для символов 8×8. Вместо поддержки полного набора символов ASCII здесь только символы, необходимые для FizzBuzz: от 0 до 9, “B”, “F”, “i”, “u”, “z” и пробел. Удобно, что весь набор уместился в 16 символов, то есть в четырёхбитное значение.
Таким образом, модуль получает четырёхбитный код символа и трёхбитный номер строки (для восьми строк на каждый символ) — и выводит восемь пикселей для данной строки символа. Весь код (ниже его фрагмент, а полный код здесь) — это просто большой оператор case для вывода соответствующих битов.6 По сути этот код компилируется в ПЗУ, которое реализуется в FPGA таблицами поиска.
case ({char, rownum}) 7'b0000000: pixels = 8'b01111100; // XXXXX 7'b0000001: pixels = 8'b11000110; // XX XX 7'b0000010: pixels = 8'b11001110; // XX XXX 7'b0000011: pixels = 8'b11011110; // XX XXXX 7'b0000100: pixels = 8'b11110110; // XXXX XX 7'b0000101: pixels = 8'b11100110; // XXX XX 7'b0000110: pixels = 8'b01111100; // XXXXX 7'b0000111: pixels = 8'b00000000; // 7'b0001000: pixels = 8'b00110000; // XX 7'b0001001: pixels = 8'b01110000; // XXX 7'b0001010: pixels = 8'b00110000; // XX 7'b0001011: pixels = 8'b00110000; // XX 7'b0001100: pixels = 8'b00110000; // XX 7'b0001101: pixels = 8'b00110000; // XX 7'b0001110: pixels = 8'b11111100; // XXXXXX ... Я обновил программу верхнего уровня для использования младших бит координаты x для символа и пиксельного индекса, а также младших бит координаты y для индекса строк. Результаты показаны внизу. Текст в красном поле увеличен, чтобы можно было разглядеть символы.
Моя первая реализация текста (увеличенная область в красном контуре). Из-за ошибки все символы идут задом наперёд
Чёрт, у меня в генераторе символов бит 7 слева, а в значениях пиксельного индекса он справа, поэтому символы отображаются задом наперёд. Но это легко исправить.
Генерация строки FizzBuzz
Наладив отображение символов, нужно получить правильные символы для вывода FizzBuzz. Алгоритм такой же, как в предыдущей программе, так что здесь приведу только основные моменты.
Преобразование чисел от 1 до 100 в символы тривиально реализовать на микропроцессоре, но сложнее в цифровой логике, потому что здесь нет встроенной операции деления. Деление на 10 и 100 требует много логических элементов. Я решил использовать двоично-десятичный счетчик (BCD) с отдельными четырёхбитными счётчиками для каждого из разрядов.
Следующая задача — проверить кратность 3 и 5. Как и простое деление, деление с остатком легко реализовать на микропроцессоре, но трудно в цифровой логике. Вместо вычисления значений я сделал счётчики для остатков от деления на 3 и на 5. Например, деление с остатком на три просто отсчитывает 0, 1, 2, 0, 1, 2… (другие варианты см. в примечаниях7).
Строка выдачи FizzBuzz содержит до восьми символов. Модуль “fizzbuzz” (исходный код) выводит соответствующие восемь четырёхбитных символов в виде 32-битной переменной line. (Нормальный способ генерировать видео — хранить все символы или пиксели экрана в видеопамяти, но я решил всё генерировать динамически). Оператор if (его фрагмент приведён ниже) обновляет биты line, возвращая “Fizz“, “Buzz“, “FizzBuzz“ или число, в зависимости от обстоятельств.
if (mod3 == 0 && mod5 != 0) begin // Fizz line[3:0] <= CHAR_F; line[7:4] <= CHAR_I; line[11:8] <= CHAR_Z; line[15:12] <= CHAR_Z; end else if (mod3 != 0 && mod5 == 0) begin // Buzz line[3:0] <= CHAR_B; line[7:4] <= CHAR_U; line[11:8] <= CHAR_Z; line[15:12] <= CHAR_Z; ... Модулю FizzBuzz нужен сигнал, чтобы увеличивать счётчик до следующего числа, поэтому я изменил модуль vga для индикации начала новой строки — и использовал его как триггер перехода к следующему числу. Но тестирование кода показало очень странную выдачу с инопланетными символами. Ниже фрагмент.
Изменение символа в каждой строке выдаёт таинственные иероглифы, а не нужный результат
Ошибка в том, что я переходил к следующему значению FizzBuzz после каждой строки пикселей вместо того, чтобы ждать 8 строк отрисовки символа целиком. Таким образом, каждый отображаемый символ состоял из срезов восьми разных символов. Увеличение счетчика FizzBuzz каждые 8 строк исправляет проблему, как показано ниже. (Отладка кода VGA намного проще, чем другие задачи на FPGA, потому что проблемы сразу видны на экране. Не нужно возиться с осциллографом, пытаясь понять, что пошло не так).
Выдача FizzBuzz на мониторе VGA
Теперь на мониторе появилась выдача FizzBuzz, но статический дисплей — это скучно. Изменение цвета переднего плана и фона для каждой строки делается простым — используем некоторые биты значения y для красного, зелёного и синего цветов. Так мы получаем цветной текст в стиле 80-х.
Если цвет переднего плана и фона зависит от линии, то текст выглядит интереснее
Затем я добавил примитивную анимацию. Первым делом нужно добавить выдачу модуля vga для индикации перерисовки экрана, это новое поле для каждой 1/60 секунды. Я использовал это для динамического изменения цветов. (Совет: не меняйте цвет 60 раз в секунду, если не хотите вызвать головную боль; используйте счётчик).
Пробовать разные графические эффекты весело и захватывающе, поскольку результат сразу виден. Я запустил “Fizz” и “Buzz” с радужным следом на экране (в духе Nyan Cat). Для этого я изменил начальные позиции символов в соответствии со счётчиком. Для эффекта радуги на символах выбраны цвета по номерам строк (поэтому каждая строка символа может быть разного цвета) и добавлен радужный след.
Конечный результат крупным планом
Напоследок я добавил ещё один эффект — гигантские слова “Fizz” и “Buzz”, отскакивающие от краёв экрана. Эффект основан на отскакивании невидимого контура (как у FPGA Pong), внутри которого находится слово8. Переменная dx отслеживает направление X, а dy — направление Y. На каждом новом экране (т. е. 60 раз в секунду) координаты X и Y контура увеличиваются или уменьшаются на основе переменных направления. Если контур достигает правого или левого края, dx переключается. Аналогично, dy переключается, если контур достиг верхнего или нижнего края. Затем внутри контура рисуется большой текст с помощью другого экземпляра генератора символов, описанного ранее. Слово увеличивается в 8 раз, отбрасывая три младших бита от координаты. Вероятно, вы уже устали от кода Verilog, так что не буду здесь показывать код, но он опубликован на GitHub. Окончательный результат — в видеоролике.
Детали аппаратной реализации
В этом проекте я использовал простую плату разработки Mojo V3 FPGA для начинающих. На ней установлен FPGA семейства Xilinx Spartan 6. Хотя это один из самых маленьких FPGA, но у него 9000 логических ячеек и 11 000 триггеров — так что малыш на многое способен. (Для других вариантов см. список дешёвых плат FPGA).
Подключение платы FPGA к VGA почти тривиально: всего три резистора 270Ω. Макетная плата просто прикрепляет кабель к колодке контактов
Если хотите использовать VGA, проще взять плату разработки с разъёмом VGA. Но если его нет (например, как у Mojo), всё равно подключить VGA не станет проблемой. Просто разместите резисторы 270Ω между красным, зелёным и голубым выходными контактами FPGA и соединением VGA. Сигналы горизонтальной и вертикальной синхронизации можно получать напрямую с FPGA.9
Для написания и синтеза кода Verilog я использовал среду разработки Xilinx (называется ISE). Подробные сведения о написании кода и его загрузке на плату FPGA см. в моей предыдущей статье. Для указания конкретных физических контактов FPGA я добавил несколько строк в конфигурационный файл mojo.ucf. Здесь красный вывод pin_r соотносится со штырьковым контактом 50 и так далее.
NET "pin_r" LOC = P50 | IOSTANDARD = LVTTL; NET "pin_g" LOC = P40 | IOSTANDARD = LVTTL; NET "pin_b" LOC = P34 | IOSTANDARD = LVTTL; NET "pin_hsync" LOC = P32 | IOSTANDARD = LVTTL; NET "pin_vsync" LOC = P29 | IOSTANDARD = LVTTL;Вывод с FPGA на VGA — распространённое явление, поэтому можете найти в Сети ряд таких проектов, как FPGA Pong, 24-битный цвет с чипа DAC, плата Basys 3 и вывод изображений. Если нужна схема, см. эту страницу. В книге «Программирование FPGA» данной теме посвящена целая глава.
Понимание формата VGA
Формат VGA может показаться немного странным, но если посмотреть на историю телевидения и ЭЛТ (электронно-лучевая трубка), то всё становится понятно. В ЭЛТ пучок электронов проходит по экрану, подсвечивая люминофорное покрытие для отображения картинки. Сканирование проходит в растровом массиве: луч сканирует экран слева направо, а затем импульс горизонтальной синхронизации заставляет его быстро переместиться влево для горизонтального обратного хода развёртки. Процесс повторяется построчно до тех пор, пока в нижней части экрана импульс вертикальной синхронизации на запустит вертикальный обратный ход развёртки — и луч возвращается вверх. При горизонтальном и вертикальном ходе развёртки луч заглушается, поэтому обратный ход не рисует линии на экране. На схеме ниже показан шаблон растрового сканирования.
Шаблон растрового сканирования в ЭЛТ (Википедия)
Эти характеристики сохраняются в VGA, в том числе импульсы горизонтальной и вертикальной синхронизации, а также длинные интервалы заглушения видео.
В 1953 году появился стандарт цветного телевидения NTSC.10 Однако VGA гораздо проще, чем NTSC, так как использует пять проводов для синхронизации и сигналов цветов, а не втискивает всё в один сигнал со сложным кодированием. Одной из странных особенностей NTSC, которая переносится на VGA, — то, что частота обновления экрана не заявленные 60 герц, а в реальности 59,94 Гц.11
След осциллографа ниже показывает сигнал VGA для двух строк. Импульсы горизонтальной синхронизации (жёлтым) указывают на начало каждой строки. Короткие красные, зелёные и синие импульсы в начале строки — это белые пиксели из числа FizzBuzz. Красный сигнал посередине линии — плавающее красное слово “Buzz”.
След осциллографа сигналов VGA показывает красный, зелёный и голубой сигналы, а также горизонтальную синхронизацию
Заключение
Вывод с FPGA на VGA оказалась намного проще, чем я ожидал, но меня определённо не возьмут на работу, если зададут задачу FizzBuzz на собеседовании по FPGA! Если интересуют FPGA, настоятельно рекомендую поиграться с видеовыходом. Это не намного сложнее, чем мигание светодиодом, зато гораздо полезнее. Генерация видеосигнала также намного интереснее, чем отладка на осциллографе — вы сразу видите результат на экране. И даже если что-то идёт не так, всё равно результат часто выходит весёлый.
Примечания и ссылки
1. У сигнала VGA должна быть тактовая частота для пикселей 25,175 МГц. Вместо этого я поделил тактовую частоту платы Mojo в 50 МГц надвое, чтобы получить 25 МГц. В стандарте VGA написано, что допускается тактовая частота 25,175 МГц ± 0,5%. Частота 25 МГц отличается на 0,7%, поэтому технически немного не соответствует спецификации. Но мониторы сконструированы на обработку сигнала с дешёвых видеокарт, так что обычно покажут всё, что на них отправить. [вернуться]
2. Подробные тайминги для десятков стандартных видеоразрешений см. здесь. На стр. 17 указано разрешение 640×480 60 Гц, которое я использовал. [вернуться]
3. Когда я забыл очистить пиксели за пределами допустимой области экрана, монитор всё равно показывал изображение, но очень тусклое, потому что монитор запутался, какому напряжению соответствует наш «тёмный». Это просто на случай, если вы обнаружите, что ваш дисплей внезапно потемнел без видимых причин. [вернуться]
4. Просто удивительно, что приходится делать ЖК-дисплею, чтобы отобразить изображение VGA, предназначенное для ЭЛТ. Дисплей должен изучить входящий сигнал и «угадать», на каком разрешении идёт видео с компьютера. Затем нужно пересэмплировать видеосигнал в соответствии с разрешением ЖК-панели. Наконец, новые данные о пикселях отправляются на ЖК-дисплей. [вернуться]
5. По какой-то причине выдача смещена вниз примерно на 25 пикселей. Она отлично отображалась на другом мониторе, поэтому я не уверен, то ли что-то с выравниванием на моём мониторе, то ли у меня ошибка. Это можно было настроить, задержав импульс вертикальной синхронизации на 25 строк. [вернуться]
6. Было бы утомительно вводить весь код для генерации символов, поэтому я написал программу на Питоне для генерации кода Verilog из файла шрифта. Оригинальный шрифт здесь. [вернуться]
7. После моей прошлой статьи по FPGA FizzBuzz читатели предложили некоторые другие подходы, поэтому я попробовал их в проекте VGA. Со счётчиками остатка от деления (мой изначальный подход) весь проект занимает 276 LUT (таблиц поиска) и 277 триггеров. Один читатель предложил использовать кольцевые счетчики (т. е. с одним сдвинутым битом) вместо двоичных счётчиков для остатка деления. Это требует 277 таблиц поиска и 281 триггера, поэтому чуть хуже. Другое предложение состояло в том, чтобы сложить разряды и взять значение остатка от деления на 3. Здесь логика увеличивает количество таблиц поиска до 305, что намного хуже. Сложение остатков от деления (вместо разрядов) снижает количество таблиц поиска до 289, что по-прежнему хуже изначального метода. [вернуться]
8. Большие плавающие слова, по сути, представляют собой спрайты — растровые изображения, которые можно произвольно расположить на экране. Спрайты были популярны в видеоиграх и на компьютерах 70-х и начала 80-х годов, когда появились Pacman, Atari и Commodore 64. Спрайты позволяют выполнять анимацию на медленных процессорах. Вместо перемещения всех пикселей в памяти процессор просто обновляет координаты спрайта. Код верхнего уровня (исходный код) связывает воедино части и объединяет всё на экране: текст, радужный след, гигантское слово “Fizz” (в радужном узоре) и гигантское “Buzz” (красным). [вернуться]
9. Чтобы подключить монитор VGA, я разрезал кабель VGA пополам и подключил его провода к плате FPGA, использовав кабель из старого проекта для чтения данных с монитора при помощи I2C. Лучше не применяйте такой подход: малюсенькие проводки сложно припаять и они легко ломаются. Лучше используйте обычный разъём VGA. Интерфейс — это просто три резистора 270Ω, получающие правильное напряжение для красного, зелёного и синего сигнала. Можете использовать больше резисторов для дополнительных цветов. Так вы по сути сконструируете двухбитные (или больше) конвертеры ЦАП. [вернуться]
10. Стандарт NTSC очень умно вводит поддержку цвета, оставаясь совместимым с чёрно-белыми телевизорами. Однако его очень трудно понять. Меня напугали разговоры о кодировании цвета фазой и квадратурой с цветным поднесущими и сигналом цветовой синхронизации. Здесь кодирование намного сложнее, чем у VGA, потому что NTSC совмещает цвет и синхронизацию в одном канале передачи. [вернуться]
11. Хотя для мониторов заявляется частота обновления 60 Гц, фактическое значение составляет 59,94 Гц. Эта странная частота восходит к истокам цветного телевидения. Частоту обновления экрана 60 Гц выбрали, чтобы нивелировать помехи от линии электропередачи. Но чтобы предотвратить интерференцию несущей частоты для цвета с частотой звука, пришлось скорректировать частоты, в результате чего частоту обновления экрана установили на 59,94 Герц. Это почти похоже на нумерологию, но выбор частоты подробно объясняется в этом видео и в Википедии. [вернуться]
Источник
