WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Реалізація ідеї арифметичного кодування - Реферат

Реалізація ідеї арифметичного кодування - Реферат

де range = high – low + 1, (1)

(остання нерівність виразу (1) походить від того факту, що cum_freq[symbol - 1] повинне бути цілим). Потім ми хочемо показати, що low'  value  high', де low' i high' є оновлені значення для low i high як це визначено нижче.

(а) low' :

З виразу (1) маємо: ,

тому low'  value, тому що і value, i low, i cum_freq [0] > 0.

(а) high:

З виразу (1) маємо:

.

Додаток 2. Робочий код для адаптивного арифметичного стискання.

Arithmetic_coding.h

/*Оголошення, необхідні для арифметичного*/

/*кодування та декодування*/

/*Інтервал значень арифметичного коду*/

#define Code_value_bits 16

typedef long code_value;

#define Top_value (((long) 1 << Code_value_bits) - 1)

/*Вказівники на середину і четверті інтервала значення коду*/

#define First_qtr (Top_value/4 + 1)

#define Half (2*First_qtr)

#define Third_qtr (3*First_qtr)

model.h

/* Інтерфейс з моделлю */

/* Множина кодуємих символів */

#define No_of_chars 256

#define EOF_symbol (No_of_chars + 1)

#define No_of_symbols (No_of_chars + 1)

/* Таблиці перекодування початкових та робочих символів */

int char_to_index[No_of_chars];

unsigned char index_to_char[No_of_symbols + 1];

/* Таблиця накопичених частот */

#define Max_frequency 16383

int cum_freq[No_of_symbols+1];

encode.c

/* Головна процедура кодування */

#include

#include "model.h"

main()

{ start_model();

start_outputing_bits();

start_encoding();

for (;;) {

int ch; int symbol;

ch = getc(stdin);

if (ch==EOF) break;

symbol = char_to_index[ch];

encode_symbol(symbol,cum_freq);

update_model(symbol);

}

encode_symbol(EOF_symbol,cum_freq);

done_encoding();

done_outputing_bits();

exit(0);

}

Arithmetic_encode.c

/* Алгоритм арифметичного кодування */

#include "arithmetic_encoding.h"

static void bit_plus_follow();

/* Поточний стан кодування */

static code_value low, high;

static long bits_to_follow;

/* Початок кодування потока символів */

start_encoding()

{ low = 0;

high = Top_value;

bits_to_follow = 0;

}

/* Кодування символу */

encode_symbol(symbol,cum_freq)

int symbol;

int cum_freq[];

{ long range;

range = (long)(high-low)+1;

high = low + (range*cum_freq[symbol-1])/cum_freq[0]-1;

low = low + (range*cum_freq[symbol])/cum_freq[0];

for (;;) {

if (high

bit_plus_follow(0);

}

else if (low>=Half) {

bit_plus_follow(1);

low -= Half;

high -= Half;

}

else if (low>=First_qtr && high

{ bits_to_follow +=1;

low -= First_qtr;

high -= First_qtr;

}

else break;

low = 2*low;

high = 2*high+1;

}

}

/* Завершення кодування потоку */

done_encoding()

{ bits_to_follow += 1;

if (low

else bit_plus_follow(1);

}

/* вивод біта разом з наступними за ним, оберненими до нього */

static void bit_plus_follow(bit)

int bit;

{ output_bit(bit);

while (bits_to_follow>0) {

output_bit(!bit);

bits_to_follow -= 1;

}

}

decode.c

/* Головна процедура для декодування */

#include

#include "model.h"

main()

{ start_model();

start_inputing_bits();

start_decoding();

for (;;) {

int ch; int symbol;

symbol = decode_symbol(cum_freq);

if (symbol == EOF_symbol) break;

ch = index_to_char[symbol];

putc(ch,stdout);

update_model(symbol);

}

exit(0);

}

arithmetic_decode.c

/* Алгоритм арифметичного декодування */

#include "arithmetic_coding.h"

/* Потоковий стан декодування */

static code_value value;

static code_value low, high;

/* Початок декодування потока символів */

start_decoding();

{ int i;

value = 0;

for (i = 1; i<=Code_value_bits; i++) {

value = 2*value+input_bit();

}

low = 0;

high = Top_value;

}

/* Декодування наступного символа */

int decode_symbol(cum_freq)

int cum_freq[];

long range;

int cum;

int symbol;

range = (long)(high - low)+1;

cum = (((long) (value - low)+1)*cum_freq[0]-1)/range;

for (symbol = 1; cum_freq[symbol]>cum; symbol++);

high = low + (range*cum_freq[symbol-1])/cum_freq[0]-1;

low = low + (range*cum_freq[symbol])/cum_freq[0];

for (;;){

if (high

else if (low>=Half)

{

value -= Half;

low -= Half;

high -= Half;

}

else if (low>=First_qtr && high

{

value -= First_qtr;

low -= First_qtr;

high -= First_qtr;

}

else break;

low = 2*low;

high = 2*high+1;

}

return symbol;

}

bit_input.c

/* Процедури вводу бітів */

#include

#include "arithmetic_coding"

/* Бітовий буфер */

static int buffer;

static int bits_to_go;

static int garbage_bits;

/* Ініціацізація побітового вводу */

start_inputing_bits();

{ bits_to_go = 0;

garbage_bits = 0;

}

/* Ввод біта */

int input_bit();

{ int t;

if (bits_to_go==0) {

buffer = getc(stdin);

if (buffer==EOF) {

garbage_bits +=1;

if (garbage_bits>Code_value_bits-2) {

fprintf(stderr,"Bad input filen");

exit(-1);

}

}

bits_to_go = 8;

}

t = buffer&1;

buffer >>= 1;

bits_to_go -= 1;

return t;

}

bit_output.c

/* Процедура виводу бітів */

#include

/* Бітовий буфер */

static int buffer;

static int bits_to_go;

/* Ініціалізація бітового буфера */

start_outputing_bits()

{ buffer = 0;

bits_to_go = 8;

}

/* Вивід біта */

output_bit(bit)

int bit;

{ buffer >>=1;

if (bit) buffer |= 0x80;

bits_to_go -= 1;

if (bits_to_go==0) {

putc(buffer,stdout);

bits_to_go = 8;

}

}

/* Вимивання останніх бітів */

done_outputing_bits()

{ putc(buffer>>bits_to_go,stdout);

}

adaptive_model.c

/* Модель з адаптивним джерелом */

#include "model.h"

int freq[No_of_symbols+1];

/* Ініціалізація моделі */

start_model()

{ int i;

for (i = 0; i

char_to_index[i] = i+1;

index_to_char[i+1] = i;

}

for (i = 0; i

freq[i] = 1;

cum_freq[i] = No_of_symbols - i;

}

freq[0] = 0;

/* Оновлення моделі у відповідності з новим символом */

update_model(symbol)

int symbol;

{ int i;

if (cum_freq[0]==Max_frequency) {

int cum;

cum = 0;

for (i = No_of_symbols; i>=0; i--) {

freq[i] = (freq[i]+1)/2;

cum_freq[i] = cum;

cum += freq[i];

}

}

for (i = symbol; freq[i]==freq[i-1];i-- );

if (i

int ch_i, ch_symbol;

ch_i = index_to_char[i];

ch_symbol = index_to_char[symbol];

index_to_char[i] = ch_symbol;

index_to_char[symbol] = ch_i;

char_to_index[ch_i] = symbol;

char_to_index[ch_symbol] = i;

}

freq[i] += 1;

while (i>0) {

i -= 1;

cum_freq[i] += 1;

}

}

Література.

Rubin F. Arithmetic stream coding using fixed precision registers, IEEE Transactions IT-25, #6, Nov79, pp. 672 – 675.

Кричевский Р. Е. Сжатие и поиск информации., Москва, 1989 г.

Кохманюк Д. Сжатие информации: как это делаеться., IndexPRO, Киев, №№1,2.

Loading...

 
 

Цікаве