Главная | Обратная связь | Поможем написать вашу работу!

Указания по выполнению задания 2

Стр 1 из 3Следующая ⇒

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

«Калининградский государственный технический университет»

Кафедра систем управления и вычислительной техники

Топоркова О.М.

Методические указания

Для выполнения курсовой работы

По информационным технологиям

Для студентов направлений

Информатика и вычислительная техника

Прикладная информатика

Калининград

Оглавление

Часть 1. Кодирование дискретного сигнала. 3

1.1 Кодирование кодами по образцу. 3

Задание 1. Прямые коды.. 3

Указания по выполнению задания 1. 3

Задание 2. Коды, учитывающие частоту символов. 4

Указания по выполнению задания 2. 4

Задание 3. Коды Грея. 7

Указания к выполнению задания 3. 7

1.2. Криптографическое кодирование дискретного сигнала. 9

Задание 4. Метод простой подстановки. 9

Указания по выполнению задания 4. 9

Задание 5. Метод Виженера. 10

Указания по выполнению задания 5. 10

1.3. Эффективное кодирование дискретного сигнала. 11

Задание 6. Метод Шеннона - Фано. 11

Указания по выполнению задания 6. 11

Задание 7. Метод Хаффмена. 14

Указания по выполнению задания 7. 14

1.4. Помехозащитное кодирование дискретного сигнала. 16

Задание 8. Построение кода для обнаружения ошибок. 16

Указания по выполнению задания 8. 17

Задание 9. Построение кода для исправления ошибок. 18

Указания по выполнению задания 9. 18

Часть 2. Измерение дискретного сигнала. 22

Задание 10. Анализ эффективности кодирования. 22

Указания по выполнению задания 10. 22

Часть 3. Формы представления чисел. 24

Задание 11. Сложение в обратных кодах. 24

Указания по выполнению задания 11. 24

Часть 4. Правила оформления курсовой работы.. 28

Часть 1. Кодирование дискретного сигнала

Кодирование кодами по образцу

Задание 1. Прямые коды

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

Указания по выполнению задания 1

Пусть фамилия, имя и отчество студента Петров Иван Васильевич. Тогда исходным текстом является текст

петровиванвасильевич, (1)

а алфавит А - это множество символов, {п, е, т, р, о, в, и, а, н, с, л, ь, ч}, т.е.

А = {п, е, т, р, о, в, и, а, н, с, л, ь, ч}. (2)

Для построения прямыхкодов выполним следующую последовательность действий:

1) множество А упорядочим по алфавиту (графа 1 табл.1),

2) пронумеруем символы алфавита А, начиная с нуля (графа 2 табл.1),

3) определим мощность N алфавита А (т.е. число символов алфавита):

N = 13 (3)

4) используя комбинаторный подход к измерению информации, рассчитаем требуемый размер кода, достаточный для кодирования всех символов исходного алфавита А, по формуле:

l = [ log_h N ], (4)

где h – число символов, используемых для кодирования,

скобки [ ] означают округление результата до ближайшего большего целого числа.

Для нашего примера h = 2 (поскольку строится двоичный код), поэтому

l = [ log₂ 13 ] = [3,7] = 4, (5)

5) каждый номер символа представим четырехразрядным (как следует из шага 4) двоичным числом - получим код постоянной длины (графа 3 табл.1).

Таблица 1

Символ алфавита А	Номер по порядку	Код постоянной длины

а
в
е
и
л
н
о
п
р
с
т
ч
ь

Кодирование исходного текста дает (для простоты закодируем отдельно фамилию, имя, отчество)[1]:

петров 0111 0010 1010 1000 0110 0001

иван 0011 0001 0000 0101 (6)

васильевич 0001 0000 1001 0011 0100 1100 0010 0001 0011 1011

Задание 2. Коды, учитывающие частоту символов

Построить для алфавита А, полученного в задании 1, двоичные коды, учитывающие частоту символов. Расчет частоты выполнить по исходному тексту. Закодировать полученным кодом исходный текст.

Указания по выполнению задания 2

Для построения требуемых кодов выполним следующую последовательность действий:

1) для расчета частот символов из алфавита А (графа 1 табл. 2) определим число появлений m_i каждого i-го символа алфавита А в исходном тексте (графа 2 табл. 2),

Таблица 2

Символ алфавита А	Число появлений m_i

а
в
е
и
л
н
о
п
р
с
т
ч
ь

2) для определения размера кода вновь используем формулу l = [ log_h N ] при N = 13, h = 2. Получаем:

l = [ log_h 13 ] = [3,7] = 4, (7)

3) используя комбинаторный подход к измерению информации, определим, сколько кодовых комбинаций можно получить из 4 двоичных разрядов, заполняя их нулями и единицами теми способами, которые показаны в графе 2 табл. 3. Чтобы решить эту задачу, установим, прежде всего, способ комбинирования символов двоичного алфавита (h = 2). Анализ кодов из табл. 1 показывает, что это перестановки с повторениями, для которых верно соотношение:

(Sr_i)! П(r_i!)

П^п(h) =, (8)

где П^п(h) – число перестановок из h элементов с повторениями r_i,

i – символ из множества символов, используемых для кодирования (у нас это множество {0,1}).

Теперь рассчитаем число кодовых комбинаций для каждого способа заполнения кодовых разрядов (графа 4 табл. 3).

Таблица 3

№ п/п

Способы заполнения кодовых разрядов

Обозначение в формуле (8)

Число кодовых комбинаций

все нули

r₀ = 4, r₁ = 0

(4+0)! 4! 4!*0! 4!

1 единица, 3 нуля

r₀ = 3, r₁ = 1

(1+3)! 4! 2*3*4 1!*3! 2*3 6

2 единицы, 2 нуля

r₀ = 2, r₁ = 2

(2+2)! 4! 2*3*4 2!*2! 2*2 4

3 единицы, 1 ноль

r₀ = 1, r₁ = 3

аналогично второму способу, т.е. 4

все единицы

r₀ = 0, r₁ = 4

аналогично первому способу, т.е. 1

Суммирование полученного числа кодовых комбинаций (1+4+6+4+1=16) показывает, что для кодирования символов исходного алфавита А с заданной мощностью N достаточно принятых способов заполнения разрядов кода, поскольку 16>(N =13),

4) упорядочим список символов алфавита А по убыванию частоты. Получим табл. 4 (графы 1,2),

5) назначим символам коды постоянной длины, число единиц в которых тем больше, чем меньше частота символа (графа 4 табл. 4).

Таблица 4

Символ алфавита А	Число появлений m_i	Способы заполнения кодовых разрядов	Код	Число кодовых комбинаций[2]

в		все нули
и		1 единица, 3 нуля
а		1 единица, 3 нуля
е		1 единица, 3 нуля
л		1 единица, 3 нуля
н		2 единицы, 2 нуля
о		2 единицы, 2 нуля
п		2 единицы, 2 нуля
р		2 единицы, 2 нуля
с		2 единицы, 2 нуля
т		2 единицы, 2 нуля
ч		3 единицы, 1 ноль
ь		3 единицы, 1 ноль

Кодирование исходного текста полученным кодом дает результат (отдельно закодированы фамилия, имя и отчество):

петров 0110 0100 1100 0101 1001 0000

иван 0001 0000 0010 1010 (9)

васильевич 0000 0010 0011 0001 1000 1101 0100 0000 0001 1011

Задание 3. Коды Грея

Для символов алфавита А (из задания 1) построить код Грея. Закодировать полученным кодом исходный текст.

12 3 Следующая ⇒

Воспользуйтесь поиском по сайту: