Кто-то делал, и какие соображения по этому поводу...главный вопрос побыстрее и функция записи во внешнюю SPI память значений не выыровненых по границе байта длиной от 2 до 13 бит

Я планировал. Но мне необходимо было "на лету". Моделировал. Необходимо около 8К озу только на это. Думаю и так всё на пределе. Распаковку сделать - ещё успеешь, а со сжатием ??? Я бы внешнее озу поставил паралельное.

А зачем для Хафмана с фиксированой таблицей 8К ОЗУ? Там вроде сдвиговый регистр на 8+13байт нужен, и все. Несколько десятков тактов на бит должно получиться без ухищрений.

Не буду утверждать, но по-моему, фиксированная таблица - это только начало. А потом она точно также пополняется-модифицируется. Насколько я понимаю, это сделано чтобы изначально не формировать таблицу и этим сэкономить на первоначальном этапе. Можно конечно и с полностью не модифицируемой таблицой, но это если данные передаются практически одни и теже. Сначала формируется таблица, потом устанавливается на оба конца и только потом работает. Для произвольных данных такой метод не даст желаемого коэффициента сжатия. Если таблица будет модифицируема, то средний коэффициен сжатия - 2. Я проверял на файлах.

Фиксированая таблица она и есть фиксированая не дополняется ее составили на основе експерументов с факсовыми изображениями и там каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до 13 бит дело в том что сжиматься будут только черно-белые изображения текстовых документов

Хм.. А обязательно Хаффманом кодировать?
IMHO если нет привязки к стандарту, то какой-нибудь модифицированный PCX сжимал бы куда лучше. Суть в том, что для графики лучше применять графические форматы.

Хм.. А обязательно Хаффманом кодировать?
IMHO если нет привязки к стандарту, то какой-нибудь модифицированный PCX сжимал бы куда лучше. Суть в том, что для графики лучше применять графические форматы.
[/quote]

дык взялся за Хаффман а если не трудно тыкните в модифицированный PCX

Просмотрел что я делал. Метод Хаффмана. Т.е. всё правильно. Правда для модема, а не для факса. Возможно в Вашем CCIT... есть отличия. Привожу выдержку из "Руководства ..." по модему USRobotics Courier. "Если модемы успешно уст. соедин., то они договариваются о сжатии (V.42bis). .... Они договариваются о размере словаря ... 9бит - 512, 10 - 1024, 11 - 2048 .... Сжатие V.42bis более эффективно, т.к. этот протокол динамически удаляет неиспользуемые более строки. Кроме этого, он работает лучше с файлами, которые заранее сжаты."

В принципе я это макетировал. (Писал на Паскале) По-моему это у меня где-то есть. Это также есть в книге которую я отправлял на FTP.

Да, кстати, сжатие обеспечивается не за счёт "там каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до 13 бит". Метод словарей немного интересней работает. И ещё: Все модемы идут с предустановленными словарями. Найти его мне не удалось. Без этого совместимости не будет. Начинать надо с одинаковыми словарями.

Именно так каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до XX бит".
//-----------------------
So how do the Group 3 and Group 4 compression mechanisms work?

Both schemes encode the source image on a horizontal scanline-by-scanline basis, corresponding to the way in which documents are scanned and printed on a facsimile machine. The difference lies in the way the two standards handle successive scanlines - in Group 3, each scanline is encoded independently, whereas in Group 4, scanlines are encoded with reference to the previous one, resulting in improved compression ratios.

In Group 3, a scanline is encoded as a set of runs, each representing a number of white or black pixels, with white runs alternating with black runs. Every run is encoded using a variable number of bits, which can be uniquely identified upon decoding. This means that frequently occurring lengths of run may be encoded very efficiently, at the expense of the infrequent ones. For example, a black run of 2 or 3 pixels is encoded using just 2 bits, whereas one of 1000 pixels is encoded in 25.
//-------------------------------

Если нужно кодировать именно факсовые данный (black& white), то
Вы вероятно не найдете варианта дающего существенно большую
компрессию ( конечно если у Вас там не сплошные картинки в black& white )
А скорость будет максимальной.

Я говорю что разбирался и делал прогу, а Вы мне приводите выдержку из статьи. Ещё раз повторяю: немного не так. Последовательность действительно кодируется. Часто используемая - меньшим колличеством бит, редко использующаяся - большим. Но причём здесь картинка??? Какая разница чёрно-белая или цветная или вообще файл программы??? Методу по барабану какую инфу сжимать если словарь образуется в процессе сжатия. Коэффициент сжатия отределяется хаотичностью передаваемых данных. Но если словарь фиксированный, то коэффициент сжатия будет меньше. Я не слышал о фиксированном. Я слышал о предустановленном. Это не одно и тоже.

Но в любом случае, при создании Вам придётся сначала сделать с нормальным словарём. Потом передать большое колличество информации. Таким образом получить словарь предустановленный или фиксированный. Руками или на глаз Вы его не создадите. Я бы например не взялся. Да и никто, я думаю не заполнит его.

Почитайте книгу. Там очень доступным языком описано.

[quote name='SasaVitebsk' date='Sep 7 2006, 21:13' post='152327']
Я говорю что разбирался и делал прогу, а Вы мне приводите выдержку из статьи.
[/quote]

Я тоже лет 10 назад разбирался с различными графическими форматами на
Silicon Graphics, и что удивительно, там было их много.
[quote name='SasaVitebsk' date='Sep 7 2006, 21:13' post='152327']
Но причём здесь картинка??? Какая разница чёрно-белая или цветная или вообще файл программы??? Методу по барабану какую инфу сжимать если словарь образуется в процессе сжатия.[/quote]
[/quote]

Ну тогда давайте будем .doc и .xls жать в формате PCX например,
а .bmp будем сжимать исключительно .zip, разницы то ведь нет

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

P.S.
Кстати вопрос скорости выполнения(автору нужен был реалтайм), Вы забыли ?!

Я вот тоже думаю что спор и емоции ни о чем.
По поводу словаря: Суть CCIT Group 3 сжатия такова:

На основе метода Хаффмана для конкретного вида изображений(отсканированые документы с печатным текстом и глубиной цвета 1 бит) на основе обработки огромного количества таких изображений был сформирован словарь(таблица), которая есть в стандарте.
Каждая строка кодируется отдельно для начала она преобразовывается в длины серий(RLE), а после этого длины серий сжимаються по готовой таблице(словарю) методом замены.
допустим последовательность из 8 белых бит встречается чаще всего и ей отвечает - 10 и т.д. коды готовы для значений от 0 до 63 и далее кратно 64 до 2363 бит.
Действительно применимо к данному типу документов сжатие вероятно будет наилутшим.
НО вопрос был в том не делал ли кто-то подобных вещей и КАКИЕ идеи по организации данного алгоритма, конкретно по побитной записи в память значений с переменной длиной(2-13 бит)

Что-то многовато. Даже вот такой код меньше дает.

struct TTableItem
{
char Len;
int Data;
};

__flash struct TTableItem TableItem[256]=
{//таблица Хафмана, длина, данные
};

unsigned long ShiftData=0;
char LenData=0;

inline void AddWord(char Len, int Word)
{
unsigned long temp = Word<<LenData;
ShiftData |= temp;
LenData += Len;
}

void main()
{
while(1)
{
//берем очередной байт
char a=GetByte();
//кладем в сдвиговый регистр
AddWord(TableItem[a].Len, TableItem[a].Data);
//обслуживаем выдачу
while(LenData >= 8)
{
char SendByte=(char)ShiftData;
//выдаем SendByte в SPI
ShiftData >>= 8;
LenData -= 8;
}
}
}

По примерным прикидкам тут получается порядка 150 тактов на входной байт и порядка 80 тактов на
выходной байт. А если учесть, что сдвиговый регистр можно сделать 24битным, то переписав это на асме можно сэкономить на лишних сдвигах. Думаю, 20 тактов на входной бит получить можно, сильно меньше - навряд.

Алгоритм (тот что я делал) могу привести. Я полностью согласен с Вами. Повторяю на глаз словарь не составишь и придётся передавать большое колличество инфы. Определённой инфы. Действительно если она однотипна, то после формирования словаря будет сжимать хорошо именно эти данные. В инете предустановленный словарь не нашёл. Написано что надо купить лицензию на метод.

Помню когда реализовывал проблем с хранением разнобитных данных не было. Поясню почему. Там всё байтами делается (тот что я реализовывал). Пример:
Идёт 50 нулей.
Слово 1 - 8 нулей
Слово 2 - Слово 1 + 8 нулей (16)
Слово 3 - Слово 2 + 8 нулей (24)
... 32
... 40
... 48
Слово 7 - Слово 6 + 2нуля и там 1хххх

Я конечно утрировано, но принцип такой. (В двух словах не объяснишь)

При реализации возникают другие проблемы.
И сжатие и расжимание связано с поиском в словаре и "обратном раскручивании спирали" (в приведённом примере при расжимании извлекаешь Слово7,6...1) В примере я подряд пустил, а на самом деле структура древовидная (50 нулей и 5 единиц, 50нулей и 10100 ... и т.д). Короче возникают проблемы поиска в словаре. Иногда применяют хотябы первое вычисление по ключу. Тогда словарь близкий к симметричному. Но в этом случае он не полностью заполнен. Короче проблемы связаны с формированием и поиском. А сам алгоритм достаточно прост. Реализовать - день работы.

Я долго экспериментировал со словарём. Добился сжатия в два раза на голом словаре. Естественно с предустановленном или на графике получается до 4-5. Смотря какие данные. Короче совсем немного до ARJ не дотягивает. Но уже на этапе экспериментов понял что на меге не потяну. Мне надо было на лету (115200). Ну и забросил это дело.

Алгоритм (тот что я делал) могу привести. Я полностью согласен с Вами. Повторяю на глаз словарь не составишь и придётся передавать большое колличество инфы. Определённой инфы. Действительно если она однотипна, то после формирования словаря будет сжимать хорошо именно эти данные. В инете предустановленный словарь не нашёл. Написано что надо купить лицензию на метод.

Помню когда реализовывал проблем с хранением разнобитных данных не было. Поясню почему. Там всё байтами делается (тот что я реализовывал). Пример:
Идёт 50 нулей.
Слово 1 - 8 нулей
Слово 2 - Слово 1 + 8 нулей (16)
Слово 3 - Слово 2 + 8 нулей (24)
... 32
... 40
... 48
Слово 7 - Слово 6 + 2нуля и там 1хххх

Я конечно утрировано, но принцип такой. (В двух словах не объяснишь)

При реализации возникают другие проблемы.
И сжатие и расжимание связано с поиском в словаре и "обратном раскручивании спирали" (в приведённом примере при расжимании извлекаешь Слово7,6...1) В примере я подряд пустил, а на самом деле структура древовидная (50 нулей и 5 единиц, 50нулей и 10100 ... и т.д). Короче возникают проблемы поиска в словаре. Иногда применяют хотябы первое вычисление по ключу. Тогда словарь близкий к симметричному. Но в этом случае он не полностью заполнен. Короче проблемы связаны с формированием и поиском. А сам алгоритм достаточно прост. Реализовать - день работы.

Я долго экспериментировал со словарём. Добился сжатия в два раза на голом словаре. Естественно с предустановленном или на графике получается до 4-5. Смотря какие данные. Короче совсем немного до ARJ не дотягивает. Но уже на этапе экспериментов понял что на меге не потяну. Мне надо было на лету (115200). Ну и забросил это дело.

Алгоритм (тот что я делал) могу привести. Я полностью согласен с Вами. Повторяю на глаз словарь не составишь и придётся передавать большое колличество инфы. Определённой инфы. Действительно если она однотипна, то после формирования словаря будет сжимать хорошо именно эти данные. В инете предустановленный словарь не нашёл. Написано что надо купить лицензию на метод.

Помню когда реализовывал проблем с хранением разнобитных данных не было. Поясню почему. Там всё байтами делается (тот что я реализовывал). Пример:
Идёт 50 нулей.
Слово 1 - 8 нулей
Слово 2 - Слово 1 + 8 нулей (16)
Слово 3 - Слово 2 + 8 нулей (24)
... 32
... 40
... 48
Слово 7 - Слово 6 + 2нуля и там 1хххх

Я конечно утрировано, но принцип такой. (В двух словах не объяснишь)

При реализации возникают другие проблемы.
И сжатие и расжимание связано с поиском в словаре и "обратном раскручивании спирали" (в приведённом примере при расжимании извлекаешь Слово7,6...1) В примере я подряд пустил, а на самом деле структура древовидная (50 нулей и 5 единиц, 50нулей и 10100 ... и т.д). Короче возникают проблемы поиска в словаре. Иногда применяют хотябы первое вычисление по ключу. Тогда словарь близкий к симметричному. Но в этом случае он не полностью заполнен. Короче проблемы связаны с формированием и поиском. А сам алгоритм достаточно прост. Реализовать - день работы.

Я долго экспериментировал со словарём. Добился сжатия в два раза на голом словаре. Естественно с предустановленном или на графике получается до 4-5. Смотря какие данные. Короче совсем немного до ARJ не дотягивает. Но уже на этапе экспериментов понял что на меге не потяну. Мне надо было на лету (115200). Ну и забросил это дело.

NetPBM

Посмотрите файлы g3.h и pmbtog3.c , может быть поможет.