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

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

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

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

Переповнення.
Тепер розглянемо можливість переповнення при цілочисленому множенні. Переповнення не виникне, якщо добуток range*Max_frequency вміщується в ціле слово, бо накопичені частоти не можуть перевищувати Max_frequency. Range має найбільше значення в Top_Value + 1, тому максимально можливий добуток є 2^16*(2^14 - 1), яке менше 2^30. Для визначення code_value та range використаний тип long, щоб забезпечити 32-х бітову точність арифметичних обчислень.
7.3 Завершення кодування.
При завершені процесу кодування необхідно послати унікальний термінальний символ (EOF-символ), а потім послати достатню кількістьбітів длягарантії того, що закодований рядок потрапить в підсумковий робочий інтервал. Через те, що процедура done_encoding() може бути "впевнена", що low i high обмежені або так, що:
low < First_qtr < Half high, або
low < Half 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=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 (low0) {
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; icum; symbol++);
high = low + (range*cum_freq[symbol-1])/cum_freq[0]-1;
low = low + (range*cum_freq[symbol])/cum_freq[0];
for (;;){
if (high=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 file ");
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; ichar_to_index[i] = i+1;
index_to_char[i+1] = i;
}
for (i = 0; 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 (i0) {
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...

 
 

Цікаве