Автор работы: Пользователь скрыл имя, 15 Февраля 2013 в 12:40, курсовая работа
Целью курсовой работы является разработка лабораторного практикума по теории кодирования.
Для достижения поставленной цели были определены следующие задачи:
- углубленное изучение теоретического материала по теории кодирования;
- разработка заданий для проведения лабораторного практикума по теории кодирования;
- реализация решения задач по теории кодирования на языке программирования Pascal.
Введение
Теоретическая часть
1. История теории кодирования
2. Основные понятия теории кодирования
3. Системы счисления как способ кодирования информации
3.1 Позиционные системы счисления
3.2 Смешанные системы счисления
3.3 Двоичная система счисления
4. Современные способы кодирования
4.1 Алфавитное кодирование
5. Кодирование и обработка чисел компьютером
6.Эффективное кодирование
6.1 Основная теорема Шеннона о кодировании для канала без помех
Практическая часть
Заключение
Приложение1
Приложение2
Список летиратуры
Program kluch;
uses crt;
var a,b,t,f:string;
i,j,n,m:integer;
begin clrscr;
writeln(‘введите ключевую фразу’);
readln(а);
writeln(‘’введите слово);
readln(b);
n:=length(a);
m:=length(b);
t:=’’;
for i:=1 to m do
begin
j:=1;
f:=’*’;
repeat
if b[i]=a[i] then str(j,f);
j:=j+1
until (f<>’*’) or (j>n);
t:=t+f;
end;
writeln(‘Результат’);
writeln(t);
readln
end.
Ответ:
Введите ключевую фразу
светит солнце
введите слово
сон
Результат
1911
Задачи для самостоятельного решения.
Кодирование с использованием ключевой фразы:
- если фраза содержит одинаковые буквы, то берется код последней буквы,
- фраза не должна содержать одинаковые буквы,
- букве присваивается код в два раза превышающий номер буквы в ключевой фразе.
Задача 4. Кодировка русского алфавита. Написать программу кодирования букв русского алфавита последовательностью из четырех цифр (от 0 до 9), в которой первые и последние цифры одинаковые.
Решение:
Program kodirovka;
uses crt;
var s,t:string;
i:integer;
begin clrscr;
writeln(‘vvedite tekst’);
read(s);
for i:=1 to length(s) do
begin
t:=copy(s,I,1);
if t=’a’ then write(‘1231’)
else if t=’б’ then write(‘1341’)
else if t=’в’ then write(‘1451’)
else if t=’г’ then write(‘1561’)
else if t=’д’ then write(‘1671’)
else if t=’е’ then write(‘1781’)
else if t=’ж’ then write(‘1891’)
else if t=’з’ then write(‘2232’)
else if t=’и’ then write(‘2342’)
else if t=’й’ then write(‘2452’)
else if t=’к’ then write(‘2562’)
else if t=’л’ then write(‘2672’)
else if t=’м’ then write(‘2782’)
else if t=’н’ then write(‘2892’)
else if t=’о’ then write(‘3233’)
else if t=’п’ then write(‘3343’)
else if t=’р’ then write(‘3453’)
else if t=’с’ then write(‘3563’)
else if t=’т’ then write(‘3673’)
else if t=’у’ then write(‘3783’)
else if t=’ф’ then write(‘3893’)
else if t=’х’ then write(‘4234’)
else if t=’ц’ then write(‘4344’)
else if t=’ч’ then write(‘4454’)
else if t=’ш’ then write(‘4564’)
else if t=’щ’ then write(‘4674’)
else if t=’ъ’ then write(‘4784’)
else if t=’ы’ then write(‘4894’)
else if t=’ю’ then write(‘5455’)
else if t=’я’ then write(‘5565’)
else if t=’’ then write(‘//’);
end;
readkey;
end.
Ответ:
vvedite tekst
Арсланова Ильнара
345335632672123128923323314511
Задача 5. Метод Хаффмана
Решение:
Program Xaffman;
uses crt;
var m:array[1..100,1..100]of real;
i,j,N:integer;
b:real;
begin clrscr;
write('Количество символов -> ');
readln(N);
for i:=1 to N do
begin
write('P(Z',i,') -> ');
readln(m[i,1]);
end;
for i:=N downto1 do
for j:=1 to i-1 do if m[j,1] < m[j+1,1] then
begin
b:=m[j,1];
m[j,1] := m[j+1,1];
m[j+1,1] := b;
end;
for j:=2 to N do m[N-j+1,j] := m[N-j+1,j-1] + m[N-j+1,j-1];
writeln('Треугольник');
for i:=1 to N do
begin
for j:=1 to N-i+1 do write(m[i,j]:3:3);
writeln;
end;
readln;
end.
Задача 6. Используя код Хаффмана, закодировать следующий текст, состоящий из 29 знаков:
WENEEDMORESNOWFORBETTERSKIING
Используя табл. 5, закодируем строку:
011101 100 1100 100 100 11011 00011 1110 1011 100 0110 1100 1110 011101 01001 1110 1011 011100 100 001 001 100 1011 0110 110100011 1010 1010 1100 00001
После размещения этого кода в памяти побайтно он примет вид:
01110110 01100100 10011011 00011111 01011100 01101100 11100111 01010011 11010110 11100100 00100110 01011011 01101000 11101010 10110000 001
В шестнадцатеричной форме он запишется так:
76 64 9B 1F 5C 6C E7 53 D6 E4 26 5B 68 EA B0 20.
Задачи для самостоятельного решения.
1. Написать программу кодирования букв русского алфавита последовательностью из четырех цифр (от 0 до 9), в которой
- цифры расположены строго по возрастанию;
- цифры расположены строго по убыванию;
- первые и последние цифры не одинаковые.
2. Закодировать с помощью кодов Хаффмана следующий текст:
HAPPYNEWYEAR. Вычислите коэффициент сжатия.
Заключение
Исследования в области
теории кодирования, имеют важное значение
для развития большого числа направлений
в различных областях науки, техники
и информационных технологий. Развитие
систем кодирования отражается на возможностях
реализованных в таких
Как информационные системы,
сетевые технологии, базы и банки
данных телекоммуникационные системы
и системы защиты. Поэтому, можно
сказать, что теория кодирования
постоянно развивающееся
В ходе выполнения курсовой работы были решены все поставленные задачи. Цель курсовой работы достигнута.
Приложение 1
Задание 1. Записать число в десятичной системе счисления:
а). 12345 = 1·53+2·52+3·5+4 = 1·125+2·25+3·5+4 = 194
б). 1011012 = 1·25+1·23+1·22+1 = 32+8+4+1 = 45
в). 332,415 = 3·52+3·51+2·50+4·5-1+1·5-2 = 3·25+3·5+2·1+4·0,2+1·0,04 = 92,84
Задание 2. Перевести число 243 в пятеричную систему, q=5.
243:5 = 48 (ост.3), 48 >5
48:5 = 9 (ост.4), 9>5
9:5 = 1 (ост.4), 1 < 5. Процесс деления окончен.
Ответ: 14435 – искомая запись числа.
Задание 3. Составить систему счисления с основанием q =16, q=10 0
1 2 3 4 5 6 7 8 9 10 11 12
13 14 15
q=16 0 1 2 3 4 5 6 7 8 9 А
В С D E F
q=16 0 1 2 3 4 5 6 7 8 9 α β
Решение. Числа (цифры) от 0 до 9 берутся из десятичной системы счисления. Для чисел от 10 до 15 вводятся специальные знаки или буквы латинского, греческого или иного алфавита, которые при записи чисел, считаются цифрами в системе q=16. Один из вариантов цифр шестнадцатеричной системы предложен в таблице.
Задание 4. Записать числа:
а). 1,2,4,8,16,…в двоичной системе;
б). 1,3,27,81,…в троичной системе;
в). 1,5,25,125,…в пятеричной системе
Установить закономерность в записи таких чисел
Ответ с комментариями. Не трудно заметить, что числа в задании есть степени основания системы, поэтому все числа изображаются единицей с последующими нулями, число которых равно показателю степени. Например: 16=24=100002, 27=33=10003, kn=100…0 – k нулей.
Задание 5. Выполнить действия в указанных системах счисления:
а) 23426-5556 б) 2457*237 в) 42315-4445 г) 349*24
д) 23578:268 е) 1000:101 ж) 10013:113
Ответы:а-1343, б-6331, в-3232, г-14112, д-66, е-11(ост), ж-21
Задание 6. Перевести число Х из двоичной системы в восьмеричную систему. Х=10101101110012
Решение: Х=1 010 110 111 1012. Группе 1 соответствуют цифра 1. Группе 010 – цифра 2. Группе 111 – цифра 7. Группе 101 – цифра 5
Ответ: 10101101110012 = 12758
Перевод записи числа из двоичной системы счисления в шестнадцатеричную систему. Учитывая, что 16=24 число, записанное в двоичной системе счисления, разбивается справа налево на группы по четыре знака (4-показатель степени) в каждой из них. Каждая группа отдельно переводится в восьмеричную систему счисления с учетом не значащих нулей.
Задание 7. Перевести число Х из двоичной системы в шестнадцатеричную систему. Х=10101101111112
Решение: Х= 1 0101 1011 11112. Группе 1 соответствует цифра 1. Группе 0101 – цифра 5. Группе – 1011 – цифра В. Группе 1001 – цифра F.
Ответ: 10101101111112 = 15ВF
Задание 8. Перевести числа из одной системы счисления в другую
а). 23458=Х2
Решение: Цифре 2 соответствует набор знаков: 10 добавляем его до трех знаков 010. Цифре 3 – набор 11, или 011. Цифре 4 – набор 100. Цифре 5 - набор 101.2458 = 010 011 100 1012. Ответ: 10 011 100 1012
Правила взаимно перевода числа в рамках двоичной, восьмеричной и шестнадцатеричной систем распространяются на перевод чисел в рамках систем, основания которых находятся в зависимости : q, где n и k – натуральные числа.
Приложение 2.
Перевод записи числа из одной системы счисления в другую.
Число раскладывается по степеням основания системы счисления, в которой оно записано и находится значение получившегося полинома (числового выражения). Полученный результат – есть число, записанное в десятичной системе счисления.
Правило перевода основано на последовательном деление с остатком, на число q – основание системы.
Число делится на q и находится первый остаток и первое частное.
Если первое частное больше или равно q, то это частное делится на q, находятся второй остаток и второе частное.
Процесс деления и сравнения очередного частного с q продолжается до тех пор, пока последующее частное не станет меньше q. Если где – то произошло деление «на цело», то остаток считается равным нулю.
Выписав последнее частное, затем, приписав к нему остатки в обратном порядке по отношению к их появлению, с учетом нулевых остатков, получается число, записанное в системе счисления с основанием q.
Целая часть дроби переводится по правилу перевода целых чисел. Перевод дробной части основан на последовательном умножении на основание иной системы q.
получившегося первого произведения – есть первая цифра, которая следует после целой части числа в новой записи числа (первая цифра справа от знака, отделяющегося целую часть этого числа от его дробной части);
умножается на q. Целая часть получившегося второго произведения – есть вторая цифра, которая следует после целой части числа в новой записи числа (вторая цифра справа от знака, отделяющегося целую часть этого числа от его дробной части );
пор, пока не будет достигнута заданной точность или пока дробная часть очередного произведения не станет нулевой.
тельно приписываются, в
порядке появления цифры
Арифметические действия над числами, представленными в различных системах счисления.
Как было сказано выше, правила выполнения арифметических действий над числами, записанными в любой системе счисления, не отличаются от правил, которые применяются при выполнении таковых действий в десятичной системе счисления.
Компоненты арифметических действий переводятся в десятичную систему счисления. В ней выполняются необходимые арифметические действия. Полученный результат переводится в первоначальную систему счисления.
Список литературы