Добрый день!
Кто нибудь делал/встречал реализации арфиметического кодирования на ФПГА ?

Если да то не могли бы вы поделиться линками на данную тему,
стандарты, описания с примерами для ПК не нужны, интересует именно реализация на ФПГА.
поиск выдает линки на IEEE статьии, но т.к. я не являюсь членом IEEE, то доступ туда закрыт

С уважением des00

Добро пожаловать в клуб. Фактически через пару недель мы тоже будем заниматься этой проблемой. Было решено заниматься двухпроходным алгоритмом, т.к. адаптивный алгоритм получается ОЧЕНЬ медленным. На данный момент отработали внутреннюю структуру и написали пару тестовых приложений на С++ для проверки идей кодирования. В первом приближении выглядит так, что на обработку каждого входного слова будет тратиться от двух до четырех тактов. Всего остального пока сказать не могу, потому как мы только собираемся этим заняться

BTW, кодирование Хаффмана получается гораздо более производительным - просто pipeline на три-четыре стадии на частоте поступающих слов, однако процедура построения дерева по данным гораздо более сложная, чем для арифметического кодера.

Спасибо, обрадовали

У меня алгоритм фиксирован это CABAC с одной моделью адаптации контекста под данные. Исходники работаюшего кода есть, нужно теперь переложить все это дело в ФПГА, естественно чем быстрее производительности тем лучше
В качестве опорной величины желательно не более 10тактов*100МГц на бит.



А что вы подразумеваете под входным словом ? какова разрядность этой величины? 2-4 такта это на одном проходе ?

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

Развитием идеи арифметического кодирования является идея интервального кодирования. Там нормализацию можно производить заметно реже, однако для ее реализации нужна 32-битная арифметика и 32-битные аппаратные умножители, что не реализуемо на FPGA на данный момент - у нас скорость входящих данных обычно составляет от 100 до 160 мегаслов в секунду - будем ставить 3-4 ядра кодирования и разбивать данные на блоки. К счастью, мы не реализовываем один из стандартных алгоритмов кодирования, потому нам легче в смысле представления данных и формы их кодирования.

О CABAC ничего не знаю По тому что будете использовать контекстную модель - выглядит как адаптивный алгоритм Адаптивный алгоритм для 8-битных входных слов потребует после получения каждого слова пересчета таблицы вероятностей и редко - масштабирования. Самым не приятным в этом случае будет необходимость реализации деления на любое число.

У нас на FTP лежит замечательная книга, правда на английском,
Mark Nelson, The Data Compression Book. В ней можно почерпнуть множество информации о компрессии данных, в том числе и арифметическим способом.

Спасибо за ответ.


Да CABAC это Context-Based Adaptive Arithmetic Coding.
Там сначла проводиться бинаризация входных данных, а затем бинарное кодирование с адаптацией конекста. Но алгоритм без деления, только сумматоры и сдвиги.



спасибо качаю

Если будут вопросы можно к вам будет обратиться мылом ?

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



Конечно, обращайтесь. Чем смогу - помогу, поскольку все равно будем работать по параллельной тематике Мыло у меня такое же как и мой ник на форуме "собака" yahoo (dot) com

Сама идея отказа от умножения/деления описанна
http://www.compression.ru/download/ar.html
Захаров М. "Об одной реализации арифметического кода"
Вариант реализации быстрого арифметического кодера, не содержащего операций умножения и деления.

А по теме того, что нужно реализовывать, я пользуюсь ref-code MPEG-4
http://iphome.hhi.de/suehring/tml/download/

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

Да, но это при условии если в FPGA нет встроенных умножителей.