Решение FizzBuzz на FPGA с генерацией видео

Эта статья рассказывает, как сгенерировать видеосигнал на FPGA, используя в качестве примера игру FizzBuzz. Генерировать видео оказалась проще, чем я ожидал — проще, чем предыдущая задача с последовательным выводом FizzBuzz на FPGA ^[1]. Я немного увлёкся проектом, поэтому добавил анимацию, разноцветный текст и гигантские прыгающие слова на экране.

FizzBuzz на плате FPGA. Плата генерирует прямой видеосигнал VGA с анимацией слов “Fizz” и “Buzz”

Если Вы не знакомы с задачей FizzBuzz ^[2], то она заключается в написании программы, которая печатает числа от 1 до 100, где кратные трём заменяются словом Fizz, кратные пяти — словом Buzz, а кратные пятнадцати — FizzBuzz. Поскольку FizzBuzz реализуется в нескольких строчках кода, эту задачу дают на собеседованиях ^[3], чтобы отсеять совсем не умеющих программировать. Но на FPGA решение гораздо сложнее.

FPGA (программируемая пользователем вентильная матрица ^[4]) — интересная микросхема. Она программируется на выполнение произвольной цифровой логики. Можно сконструировать сложную схему, не прокладывая физические каналы между отдельными вентилями и триггерами. Микросхема способна превратиться во что угодно, от логического анализатора до микропроцессора и видеогенератора. Для этого проекта я использовал плату Mojo FPGA ^[5] (на фото).

^[6]
Плата Mojo FPGA. Большой чип на плате — это Spartan 6 FPGA

Генерация сигнала VGA

Для FPGA существует определённая кривая обучаемости, потому что здесь вы разрабатываете схемы, а не пишете программное обеспечение, которое работает на процессоре. Но если вы с помощью FPGA можете заставить мигать пять светодиодов, то в целом готовы реализовать выдачу видеосигнала VGA. Формат видео VGA намного проще, чем я ожидал: всего три сигнала для пикселей (красный, зелёный и синий) и два сигнала для горизонтальной и вертикальной синхронизации.

Основная идея в том, чтобы использовать два счётчика: один для пикселей по горизонтали, а второй для вертикальных линий. В каждой точке экрана по этим координатам генерируется нужный цвет пикселя. Кроме того, генерируются импульсы горизонтальной и вертикальной синхронизации, когда счётчики находятся в соответствующей позиции. Я использовал базовое разрешение VGA 640×480^{2 [7]1 [8]11 [9]}. По горизонтали в каждой линии 800 пикселей: 640 видимых, 16 пустых, 96 на горизонтальную синхронизацию и ещё 48 пустых пикселей. (Такие странные параметры используются по историческим причинам). Между тем, вертикальный счётчик должен отсчитывать 525 линий: 480 линий изображения, 10 пустых, 2 линии вертикальной синхронизации и ещё 33 пустые.

Собрав всё вместе, я разработал модуль vga (исходный код ^[10]) для генерации сигналов 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 нужно выйти из последовательного программного мышления ^[11] и думать о базовых схемах.

Возвращаясь к модулю 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 [12]} (вопросительный знак является тернарным условным оператором, как в 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 [13]5 [14]}

Моя первая программа VGA генерирует произвольные цветные блоки на экране. Не очень осмысленно, зато всё работает нормально

Вывод символов на экран

Следующий шаг — отображение текстовых символов на экране. Я реализовал модуль генерации пикселей для символов 8×8. Вместо поддержки полного набора символов ASCII здесь только символы, необходимые для FizzBuzz: от 0 до 9, “B”, “F”, “i”, “u”, “z” и пробел. Удобно, что весь набор уместился в 16 символов, то есть в четырёхбитное значение.

Таким образом, модуль получает четырёхбитный код символа и трёхбитный номер строки (для восьми строк на каждый символ) — и выводит восемь пикселей для данной строки символа. Весь код (ниже его фрагмент, а полный код здесь ^[15]) — это просто большой оператор case для вывода соответствующих битов.^{6 [16]} По сути этот код компилируется в ПЗУ, которое реализуется в 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], так что здесь приведу только основные моменты.

Преобразование чисел от 1 до 100 в символы тривиально реализовать на микропроцессоре, но сложнее в цифровой логике, потому что здесь нет встроенной операции деления. Деление на 10 и 100 требует много логических элементов. Я решил использовать двоично-десятичный счетчик (BCD) с отдельными четырёхбитными счётчиками для каждого из разрядов.

Следующая задача — проверить кратность 3 и 5. Как и простое деление, деление с остатком легко реализовать на микропроцессоре, но трудно в цифровой логике. Вместо вычисления значений я сделал счётчики для остатков от деления на 3 и на 5. Например, деление с остатком на три просто отсчитывает 0, 1, 2, 0, 1, 2… (другие варианты см. в примечаниях^{7 [17]}).

Строка выдачи FizzBuzz содержит до восьми символов. Модуль “fizzbuzz” (исходный код ^[18]) выводит соответствующие восемь четырёхбитных символов в виде 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 ^[19]). Для этого я изменил начальные позиции символов в соответствии со счётчиком. Для эффекта радуги на символах выбраны цвета по номерам строк (поэтому каждая строка символа может быть разного цвета) и добавлен радужный след.

Конечный результат крупным планом

Напоследок я добавил ещё один эффект — гигантские слова “Fizz” и “Buzz”, отскакивающие от краёв экрана. Эффект основан на отскакивании невидимого контура (как у FPGA Pong ^[20]), внутри которого находится слово^{8 [21]}опубликован на GitHub ^[22]. Окончательный результат — в видеоролике.

Детали аппаратной реализации

В этом проекте я использовал простую плату разработки Mojo V3 ^[5] FPGA для начинающих. На ней установлен FPGA семейства Xilinx Spartan 6. Хотя это один из самых маленьких FPGA, но у него 9000 логических ячеек и 11 000 триггеров — так что малыш на многое способен. (Для других вариантов см. список дешёвых плат FPGA ^[23]).

^[24]
Подключение платы FPGA к VGA почти тривиально: всего три резистора 270Ω. Макетная плата просто прикрепляет кабель к колодке контактов

Если хотите использовать VGA, проще взять плату разработки с разъёмом VGA. Но если его нет (например, как у Mojo), всё равно подключить VGA не станет проблемой. Просто разместите резисторы 270Ω между красным, зелёным и голубым выходными контактами FPGA и соединением VGA. Сигналы горизонтальной и вертикальной синхронизации можно получать напрямую с FPGA.^{9 [25]}

Для написания и синтеза кода Verilog я использовал среду разработки Xilinx (называется ISE). Подробные сведения о написании кода и его загрузке на плату FPGA см. в моей предыдущей статье ^[1]. Для указания конкретных физических контактов FPGA я добавил несколько строк в конфигурационный файл mojo.ucf [26]. Здесь красный вывод 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 ^[20], 24-битный цвет с чипа DAC ^[27], плата Basys 3 ^[28] и вывод изображений ^[29]. Если нужна схема, см. эту страницу ^[30]. В книге «Программирование FPGA» ^[31] данной теме посвящена целая глава.

Понимание формата VGA

Формат VGA может показаться немного странным, но если посмотреть на историю телевидения и ЭЛТ (электронно-лучевая трубка ^[32]), то всё становится понятно. В ЭЛТ пучок электронов проходит по экрану, подсвечивая люминофорное покрытие для отображения картинки. Сканирование проходит в растровом массиве: луч сканирует экран слева направо, а затем импульс горизонтальной синхронизации заставляет его быстро переместиться влево для горизонтального обратного хода развёртки. Процесс повторяется построчно до тех пор, пока в нижней части экрана импульс вертикальной синхронизации на запустит вертикальный обратный ход развёртки — и луч возвращается вверх. При горизонтальном и вертикальном ходе развёртки луч заглушается, поэтому обратный ход не рисует линии на экране. На схеме ниже показан шаблон растрового сканирования.

Шаблон растрового сканирования в ЭЛТ (Википедия ^[33])

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

В 1953 году появился стандарт цветного телевидения NTSC.^{10 [34]11 [9]}

След осциллографа ниже показывает сигнал VGA для двух строк. Импульсы горизонтальной синхронизации (жёлтым) указывают на начало каждой строки. Короткие красные, зелёные и синие импульсы в начале строки — это белые пиксели из числа FizzBuzz. Красный сигнал посередине линии — плавающее красное слово “Buzz”.

След осциллографа сигналов VGA показывает красный, зелёный и голубой сигналы, а также горизонтальную синхронизацию

Заключение

Вывод с FPGA на VGA оказалась намного проще, чем я ожидал, но меня определённо не возьмут на работу, если зададут задачу FizzBuzz на собеседовании по FPGA! Если интересуют FPGA, настоятельно рекомендую поиграться с видеовыходом. Это не намного сложнее, чем мигание светодиодом, зато гораздо полезнее. Генерация видеосигнала также намного интереснее, чем отладка на осциллографе — вы сразу видите результат на экране. И даже если что-то идёт не так, всё равно результат часто выходит весёлый.

Примечания и ссылки

[вернуться] ^[35]

здесь ^[36]. На стр. 17 указано разрешение 640×480 60 Гц, которое я использовал. [вернуться] ^[37]

[вернуться] ^[38]

[вернуться] ^[39]

[вернуться] ^[40]

программу на Питоне ^[41] для генерации кода Verilog из файла шрифта. Оригинальный шрифт здесь ^[42]. [вернуться] ^[43]

[вернуться] ^[44]

исходный код ^[45]) связывает воедино части и объединяет всё на экране: текст, радужный след, гигантское слово “Fizz” (в радужном узоре) и гигантское “Buzz” (красным). [вернуться] ^[46]

проекта для чтения данных с монитора при помощи I2C ^[47]. Лучше не применяйте такой подход: малюсенькие проводки сложно припаять и они легко ломаются. Лучше используйте обычный разъём VGA. Интерфейс — это просто три резистора 270Ω, получающие правильное напряжение для красного, зелёного и синего сигнала. Можете использовать больше резисторов для дополнительных цветов. Так вы по сути сконструируете двухбитные (или больше) конвертеры ЦАП. [вернуться] ^[48]

кодировании цвета ^[49] фазой и квадратурой с цветным поднесущими и сигналом цветовой синхронизации. Здесь кодирование намного сложнее, чем у VGA, потому что NTSC совмещает цвет и синхронизацию в одном канале передачи. [вернуться] ^[50]

этом видео ^[51] и в Википедии ^[49]. [вернуться] ^[52]

Автор: m1rko

Источник ^[53]