Часть 1 - что это вообще за зверь?
Часть 2 - наша первая схема!
Часть 3 - кнопочки и лампочки
Часть 4 - делитель частоты
Часть 5 - подавление дребезга кнопки
Часть 6 - заканчиваем кнопочки и лампочки
Часть 7 - счетчики и жаба
Часть 8 - передатчик UART
Часть 9 - Hello, wolf!
Часть 'hA - приёмник UART
Часть 'hB - UART и жаба
Часть 'hC - полудуплексный UART.
Часть 'hD - МКО (МКИО, Mil-Std 1553) для бедных, введение.
Часть 'hE - приёмопередатчик МКО "из подручных материалов" (в процессе)
Часть 'hF - модуль передатчика МКО
Часть 'h10 - передатчик сообщений МКО
Часть 'h20 - работа с АЦП ADC124s051
Часть 'h21 - преобразование двоичного кода в двоично-десятичный (BCD)
Часть 'h22 - Bin2Bcd с последовательной выдачей данных
Часть 'h23 - перемножитель беззнаковых чисел с округлением
Часть 'h24 - перемножитель беззнаковых чисел, реализация
Часть 'h25 - передаём показания АЦП на компьютер
Часть 'h26 - работа над ошибками (быстрый UART)
Часть 'h27 - PNG и коды коррекции ошибок CRC32
Часть 'h28 - передатчик изображения PNG
Часть 'h29 - принимаем с ПЛИС изображение PNG
Часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 'h2B - ускоряем Adler32
Часть 'h2C - формирователь потока Zlib
Часть 'h2D - передаём сгенерированное PNG-изображение
Часть 'h2E - делим отрезок на равные части
Часть 'h2F - знаковые умножители, тысячи их!
Часть 'h30 - вычислитель множества Мандельброта
Часть 'h31 - ускоренные сумматоры
Часть 'h32 - ускоренные счётчики (делаем часы)
Часть 'h33 - ускоряем ВСЁ
Часть 'h34 - ускоренные перемножители
Часть 'h35 - умножители совсем просто
Часть 'h36 - уравновешенный четверичный умножитель
Очередная завиральная идея - научиться формировать корректное изображение PNG на ПЛИС и передавать его на компьютер.
Заголовки мы можем заранее записать в память, сжатие изображения лучше всего производить по мере оцифровки, и в память заносить уже сжатый поток (а на первых порах можно обойтись и без него, с использованием несжатых блоков zlib), а вот 4-байтные CRC-коды, которыми должен заканчиваться каждый блок (chunk) PNG, удобнее всего посчитать непосредственно во время отправки этого изображения ("файла") по UART или какому-нибудь ещё интерфейсу.
Аппаратное вычисление CRC - на удивление простая штука, и была бы ещё проще, если бы не постоянные танцы с бубном вокруг порядка битов и байтов.
Но сначала небольшое пояснение, зачем это вообще надо...
Давно уже пора заняться оцифровкой видео и обработкой изображений на ПЛИС. Для этого у меня на макетке стоит быстродействующая 8-битная АЦП, способная давать до 100 млн. выборок в секунду, а также селектор синхроимпульсов LM1881. Возможно, в итоге удастся обойтись и без него (у нас же есть АЦП, так оцифруем сигнал "сплошняком" и напишем на верилоге функциональный аналог LM1881!), но для этого надо очень хорошо закопаться в телевидение, и даже в этом случае есть небольшая проблемка с уровнями сигналов. Хотя размах композитного видеосигнала - 1 вольт, и диапазон входных напряжений АЦП - тоже 1 вольт, это вовсе не означает, что сигнал "поместится". Постоянная составляющая на входе имеет право быть какой угодно, её рекомендуется "выкинуть" с помощью разделительного конденсатора. И тут-то и оказывается: если у нас довольно "светлый" кадр, наши синхроимпульсы выйдут за входной диапазон АЦП. Либо надо неким хитрым образом "восстанавливать" постоянную составляющую (так это делается в видеоусилителях старых добрых кинескопных телевизоров), либо просто чуть ослабить сигнал, чтобы при всех возможных вариациях яркости мы не теряли синхроимпульсы, но при 8 битах делать этого ой как не хочется...
Про это всё непременно напишем. Но вот в чём трудность - мы вполне могли проверить работоспособность АЦП, подав двоичный код на 8 светодиодиков. Мигают как положено, когда крутишь переменный резистор - всё хорошо. Можно проверить работу селектора синхроимпульсов, сосчитав количество кадров в секунду и число строк в кадре.
А вот чтобы уже убедиться, что мы правильно оцифровываем картинку, очень хочется эту картинку перетащить на компьютер, и там открыть и тщательно изучить!
У меня сейчас небольшой бзик - не люблю каждый раз писать программу на компьютере для обработки поступивших данных - выходит в итоге, что нужно и её начать отлаживать, находить, где у нас начинаются проблемы - со стороны ПЛИС или со стороны программы обработки, поэтому всё равно придётся вернуться к "сырым данным", открыть hex-редактор и уйти глубоко в отладку.
Почему бы всё-таки не "обернуть" наши данные в какой-нибудь формат уже со стороны ПЛИС, передать, сохранить в файл, поменять ему расширение - и спокойненько открыть? Заодно потренироваться в построении сколько-нибудь сложных "конструкций" в Верилоге и Quartus'е. (Благо, задачи вполне типовые - CRC очень много где надо считать, и именно его использование в связке с передатчиком кажется наиболее предпочтительным.)
Остаётся выбрать формат. Вроде бы напрашивается BMP, но, во-первых, в нём отсутствует сжатие как класс (какие-то вариации есть, но не шибко используются), и в своём классическом виде он хранит картинку "вверх ногами" - первой идёт нижняя строка, затем предпоследняя, и так далее. Согласно документации, если указать высоту изображения со знаком "минус", можно будет записать её "сверху вниз", но я не проверял, все ли понимают такую вариацию.
JPEG - убейте на месте, штука ужасающе хитрая, ну и сжимает с потерями. (да, есть lossless режим, но он ПРИНЦИПИАЛЬНО ДРУГОЙ, и тоже далеко не все его понимают)
Мой выбор - PNG, я с ним в своё время очень долго провозился, когда хотел написать свой собственный обработчик сканов книг (эх, когда-нибудь я его всё-таки доделаю!), поэтому знаю его как облупленного.
При том стандарт довольно-таки последовательный, не шибко перемудрёный, и сжимает БЕЗ ПОТЕРЬ. В случае фотографий или сканов, сжатие получается где-то в 2 раза - это не так впечатляет, как JPEG, но всё-таки подспорье. Но главное - ты знаешь, что данные были сохранены "как есть".
Начинается файл PNG с 8-байтного заголовка (signature):
89 50 4e 47 0d 0a 1a 0a
(если в виде символов, то
\211 P N G \r \n \032 \n
)
Увидев этот заголовок, мы можем понять, что имеем дело с форматом PNG, а также убедиться, что никто не попытался "сменить ему кодировку" или преобразовать его в UTF-8 (о чём будет свидетельствовать 1-й байт, который не входит в стандартный ASCII), или преобразовать CR-LF в LF (или назад), о чём будут свидетельствовать 5-й, 6-й и 8-й байты. 7-й байт должен остановить вывод текста под "командной строкой", ибо дальше он совсем нечитаемый!
Далее у нас идёт набор блоков (Chunks). Их должно быть хотя бы 3: IHDR (Image HeaDeR), IDAT (Image DATa) и IEND (Image END), обязательно именно в таком порядке. Блоков IDAT может быть сколько угодно, следующих друг за другом, именно в них хранятся пиксели изображения в виде непрерывной строки байтов, ужатых с помощью ZLIB.
В начале каждого блока идёт 4 байта - беззнаковое целое число, указывающее размер этого блока в байтах, без учёта самих этих 4 байт, а также 4 байт имени блока и 4 байт CRC. К примеру, размер блока IEND - ровно 0 байт. Байты в этом числе идут от старшего к младшему. К примеру, длина 13 байт блока IHDR записывается так:
00 00 00 0d
Затем идёт 4 байта - имя блока. Собственно, IHDR, IDAT, IEND, есть и другие.
После этого начинаются полезные данные, хранящиеся в этом блоке и, наконец, 4 байта CRC.
CRC вычисляется для 4 байт имени блока и для полезных данных. Длина блока в вычисление CRC не попадает.
Модуль для вычисления CRC может "не догадываться" о существовании байтов, он имеет дело с последовательностью битов. Так вот, в стандарте PNG прописано подавать биты от младшего к старшему. Для нас это удобно - в UART тоже принято начинать с младших битов и заканчивать старшими, так что мы можем "прицепить" вход CRC прямо к выходу передатчика UART!
32-битный регистр CRC согласно того же стандарта надо инициализировать всеми единицами. Мотивация в том, что тогда мы сможем отличить последовательности нулей разной длины друг от друга, иначе мы можем случайно "пропустить ноль" и не заметить этого. Не уверен, что это шибко помогает, поскольку у нас в самом начале идёт заведомо ненулевая последовательность, например IDAT, но так уж повелось.
Наконец, полином, использующийся в CRC в формате PNG, таков:
x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1
По сути, вычислитель CRC находит остаток от деления гигантского полинома, каковым являются наши данные, на этот полином (многочлен). Т.е наши 32 бита - это коэффициенты при x^31, x^30, ... , 1.
Но взять и записать результат было бы слишком просто - дальше его нужно инвертировать (честно говоря, не вполне понимаю мотивацию. Типа, отыграть назад те единицы, которыми мы это дело инициализировали) и выдать МЛАДШИМ БИТОМ (выражающим коэф. при 1) ВПЕРЁД!
Выглядит это всё страшно, но, как оказалось, есть несколько сайтов, которые генерируют verilog'овский модуль для CRC для заданного полинома и для заданной ширины входных данных. Например, вот:
http://outputlogic.com/?page_id=321
Поскольку мы уже "сериализуем" входные данные, отправляя их через UART по одному биту за раз, мы выбираем Data width = 1 (именно это даёт нам самый компактный код. Не самый быстрый, но при UART'е спешить нам вообще некуда!).
Polynomial width выбираем 32 (это имеется в виду количество коэффициентов полинома остатка. Тот полином, что мы привели выше, имеет ширину 33, но самый старший коэффициент всегда единичный, и о нём принятно забывать!).
Жмём apply и переходим к шагу 2. Ставим галочки напротив нужных нам степеней и не волнуемся, что тут нет x^32 - он по умолчанию присутствует, иначе остаток от деления получится совсем "жиденьким". Наконец, жмём generate verilog - и получаем такую штуку:
//----------------------------------------------------------------------------- // Copyright (C) 2009 OutputLogic.com // This source file may be used and distributed without restriction // provided that this copyright statement is not removed from the file // and that any derivative work contains the original copyright notice // and the associated disclaimer. // // THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS // OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED // WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. //----------------------------------------------------------------------------- // CRC module for data[0:0] , crc[31:0]=1+x^1+x^2+x^4+x^5+x^7+x^8+x^10+x^11+x^12+x^16+x^22+x^23+x^26+x^32; //----------------------------------------------------------------------------- module crc( input [0:0] data_in, input crc_en, output [31:0] crc_out, input rst, input clk); reg [31:0] lfsr_q,lfsr_c; assign crc_out = lfsr_q; always @(*) begin lfsr_c[0] = lfsr_q[31] ^ data_in[0]; lfsr_c[1] = lfsr_q[0] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[2] = lfsr_q[1] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[3] = lfsr_q[2]; lfsr_c[4] = lfsr_q[3] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[5] = lfsr_q[4] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[6] = lfsr_q[5]; lfsr_c[7] = lfsr_q[6] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[8] = lfsr_q[7] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[9] = lfsr_q[8]; lfsr_c[10] = lfsr_q[9] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[11] = lfsr_q[10] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[12] = lfsr_q[11] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[13] = lfsr_q[12]; lfsr_c[14] = lfsr_q[13]; lfsr_c[15] = lfsr_q[14]; lfsr_c[16] = lfsr_q[15] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[17] = lfsr_q[16]; lfsr_c[18] = lfsr_q[17]; lfsr_c[19] = lfsr_q[18]; lfsr_c[20] = lfsr_q[19]; lfsr_c[21] = lfsr_q[20]; lfsr_c[22] = lfsr_q[21] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[23] = lfsr_q[22] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[24] = lfsr_q[23]; lfsr_c[25] = lfsr_q[24]; lfsr_c[26] = lfsr_q[25] ^ lfsr_q[31] ^ data_in[0]; lfsr_c[27] = lfsr_q[26]; lfsr_c[28] = lfsr_q[27]; lfsr_c[29] = lfsr_q[28]; lfsr_c[30] = lfsr_q[29]; lfsr_c[31] = lfsr_q[30]; end // always always @(posedge clk, posedge rst) begin if(rst) begin lfsr_q <= {32{1'b1}}; end else begin lfsr_q <= crc_en ? lfsr_c : lfsr_q; end end // always endmodule // crc
Если приглядеться, это почти что регистр циклического сдвига, но с дополнительными "обратными связями". Синтезируется очень здорово всего в 32 ЛЭ - меньше попросту невозможно! Также мы замечаем, что наш регистр инициализируется всеми единицами - ровно это нам и надо.
Но вот сброс здесь использован асинхронный - мне как-то спокойнее жить с синхронными, из-за панического страха метастабильности.
И снова у нас "параллельный" выход шириной 32 бита - куда же мы их денем???
Нет, у нас вход UART-передатчика имеет ширину 8 бит, именно по 8 бит за раз мы и хотим получать. Разумеется, можно было бы поставить сдвиговый регистр или мультиплексор "снаружи", но ведь CRC - это УЖЕ регистр циклического сдвига! Надо только напомнить ему об этом:
//----------------------------------------------------------------------------- // Copyright (C) 2009 OutputLogic.com // This source file may be used and distributed without restriction // provided that this copyright statement is not removed from the file // and that any derivative work contains the original copyright notice // and the associated disclaimer. // // THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS // OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED // WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. //----------------------------------------------------------------------------- // CRC module for data[0:0] , crc[31:0]=1+x^1+x^2+x^4+x^5+x^7+x^8+x^10+x^11+x^12+x^16+x^22+x^23+x^26+x^32; //----------------------------------------------------------------------------- module CRC32_by_output_logic( input data_in, input crc_en, input just_shift, output [7:0] CRC_byte, input rst, input clk); wire d = (~just_shift) & (data_in ^ CRC[31]); reg [31:0] CRC; assign CRC_byte = CRC[7:0]; always @(posedge clk) begin if (rst) begin CRC <= {32{1'b1}}; end else if (crc_en | just_shift) begin CRC[0] <= CRC[31] ^ (data_in & (~just_shift)); CRC[1] <= CRC[0] ^ d; CRC[2] <= CRC[1] ^ d; CRC[3] <= CRC[2]; CRC[4] <= CRC[3] ^ d; CRC[5] <= CRC[4] ^ d; CRC[6] <= CRC[5]; CRC[7] <= CRC[6] ^ d; CRC[8] <= CRC[7] ^ d; CRC[9] <= CRC[8]; CRC[10] <= CRC[9] ^ d; CRC[11] <= CRC[10] ^ d; CRC[12] <= CRC[11] ^ d; CRC[13] <= CRC[12]; CRC[14] <= CRC[13]; CRC[15] <= CRC[14]; CRC[16] <= CRC[15] ^ d; CRC[17] <= CRC[16]; CRC[18] <= CRC[17]; CRC[19] <= CRC[18]; CRC[20] <= CRC[19]; CRC[21] <= CRC[20]; CRC[22] <= CRC[21] ^ d; CRC[23] <= CRC[22] ^ d; CRC[24] <= CRC[23]; CRC[25] <= CRC[24]; CRC[26] <= CRC[25] ^ d; CRC[27] <= CRC[26]; CRC[28] <= CRC[27]; CRC[29] <= CRC[28]; CRC[30] <= CRC[29]; CRC[31] <= CRC[30]; end end // always endmodule // crc
Здесь у нас синхронный сброс, а ещё появился вход just_shift - когда он задействован, модуль перестаёт вычислять CRC, вместо этого он "катает данные на карусели" - сдвигает их циклически влево на 1 шаг за каждый такт clk (вход crc_en в этом режиме игнорируется). При этом задействованные ресурсы практически не поменялись - теперь модуль занимает 35 ЛЭ.
Увы, стандарт PNG подложил нам небольшую свинку - правило выдавать данные "младшим битом вперёд" означает - нам следовало бы сдвигать данные вправо, а наш регистр умеет работать только влево. Добавить в него функцию сдвига вправо будет означать удвоение ЛЭ, тогда уж проще поставить внешний сдвиговый регистр.
Но можно не беспокоится - циклический сдвиг влево на 24 позиции - это то же самое, что сдвиг вправо на 8 позиций. В прямом смысле "через задницу", но работает.
На этом свинья не заканчивается - этот младший байт нам нужно "зеркально отразить", и с этим в verilog'e, как ни странно, есть проблемы. Мне казалось, что я могу написать что-то типа
assign CRC_byte = CRC[0:7];
оказалось - не могу, ругается на обратное направление. Так что переправлять надо либо ручками, либо чуточку это "автоматизировать" с помощью цикла for (он работает только внутри always-блока) либо, для комбинаторной логики - с помощью generate / genvar / endgenerate.
Для 8 бит мне было проще (и нагляднее) сделать инверсию "ручками":
//module for transmitting PNG images over UART or another serial protocol. //To be sensible to series of zeros, it was decided to first initialize CRC with all ones, //then invert final value once again. //that's what we do here. Seems like most 'comfortable' place for this operation. //not to 'overload' CRC module. module Data_or_CRC_MUX (input [7:0] Data, input [7:0] CRC, input ChooseCRC, output [7:0] Q); wire [7:0] CRCrev; assign CRCrev[0] = CRC[7]; assign CRCrev[1] = CRC[6]; assign CRCrev[2] = CRC[5]; assign CRCrev[3] = CRC[4]; assign CRCrev[4] = CRC[3]; assign CRCrev[5] = CRC[2]; assign CRCrev[6] = CRC[1]; assign CRCrev[7] = CRC[0]; assign Q = ChooseCRC? ~CRCrev : Data; endmodule
Как видно, всё через одно место - нужно и отрицание сделать, и поменять порядок следования битов. Эти операции мы запихнули в мультиплексор, который позволяет передавать через UART как байты из памяти, так и только что "на лету" сгенерированный CRC. Этот модуль совсем маленький: всего 8 ЛЭ.
Очень сумбурный пост получился - после нескольких дней мучений у меня наконец-то стали сходиться эти значения, не мог не поделиться радостью.
В следующий раз соберём передатчик PNG-изображений.