Двоично-десятичные коды

Курсовая работа

По дисциплине «Основы сбора, передачи и обработки информации»

 

Руководитель Исполнитель

Букасов М.М. ст. Оконский И.В.

зач. книжка № ИА-7115

гр. ИА-71

«Допущен к защите»

___________________

(личная подпись руководителя)

_______________________

«____» _____________ 2009 г. (подпись исполнителя)

Защищен с оценкой «___» ____________ 2009г.

__________________________

(оценка)

«____» _____________ 2009 г.

 

Члены комиссии:

_______________________ _________________________

(Личная подпись) (Расшифровка подписи)

_______________________ _________________________

(Личная подпись) (Расшифровка подписи)

 

Киев-2009

Содержание

ВВЕДЕНИЕ. 3

ПОСТАНОВКА ЗАДАЧИ.. 5

РЕШЕНИЕ ПО РАЗДЕЛАМ.. 7

1. Исходные данные. 7

2. Простейшие коды.. 8

2.1. Двоично-десятичные коды.. 8

2.2. Код Грея. 10

3. Статическое кодирование. 14

3.1. Количество информации и энтропия. 14

3.2. Код Шеннона-Фано. 16

3.3. Код Хаффмана. 21

4. Коды, обнаруживающие ошибки. 30

4.1. Код с проверкой на чётность. 30

4.2. Код с проверкой на нечетность. 31

4.3. Инверсный код. 32

4.4. Корреляционный код. 34

4.5. Код Бергера. 35

4.6. Код на одно сочетание. 36

4.7. Код с количеством единиц, кратным трем. 38

5. Коды, обнаруживающие ошибки. 39

5.1. Код Варшамова в матричном представлении. 39

5.2. Код Хэмминга. 44

5.3. Расширенный код Хэмминга. 50

5.4. Итеративный код. 52

5.5. Коды-спутники. 54

5.6. Циклический код. 57

5.7. Код БЧХ.. 62

5.8. Рекуррентный код. 67

6. Канальные коды.. 71

6.1. Дуобинарный код. 71

6.2. Квазитроичный код. 72

6.3. Код Манчестер 2. 73

6.4. Код 4B3T. 74

7. Штриховые коды.. 77

ЗАКЛЮЧЕНИЕ. 80

Приложение А.. 81

Приложение Б. 83

ВВЕДЕНИЕ

Информация (от лат. informatio – осведомление, разъяснение, изложение) – в широком смысле абстрактное понятие, имеющее множество значений, в зависимости от контекста. В узком смысле этого слова – сведения (сообщения, данные) независимо от формы их представления. В настоящее время не существует единого определения термина информация. С точки зрения различных областей знания, данное понятие описывается своим специфическим набором признаков. Например, «информация» может трактоваться, как совокупность данных, зафиксированных на материальном носителе, сохранённых и распространённых во времени и пространстве.

Клод Шеннон подразумевает под термином информация нечто фундаментальное (нередуцируемое), то есть категорию. Интуитивно полагается, что информация имеет содержание. Информация уменьшает общую неопределённость и информационную энтропию, доступна измерению. Согласно Шеннону, «информация» – это некоторые новые для нас знания (ведения) об окружающем или внутреннем мире.

Согласно данному определению, вполне очевидно, что, как человек, так и все его творения, постоянно вовлечены в процессы поиска информации и обмена ею. В виду этого встаёт вопрос представления информации в некотором виде, пригодном и удобном для использования как человеком, так техникой, для представления информации, её хранения, передачи и сохранения в подлинном виде. Данные вопросы как раз и являются предметом такой области как «Основы хранения, передачи и обработки информации», целью которой является поиск оптимальных способов решения поставленных выше задач.

С представлением, хранением и передачей информации неразрывно связан термин «кодирование» - процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки. Этот процесс являет собой представление информации символами, знаками, взятыми из определенного алфавита по определённым правилам.

В данной работе будут кратко рассмотрены наиболее распространённые методы, применяемые для решения поставленных задач, и приведены примеры кодирования информации с использованием рассматриваемых методов.

ПОСТАНОВКА ЗАДАЧИ

I. Исходные данные: ФИО студента (ФИО – 3 первые большие буквы русского алфавита) – переводим комбинацию букв в 24 бита ASCII (таблицу брать в учебнике стр.121) → получаем ФИО в цифровом коде.

II. Простейшие коды. Кодировать и декодировать ФИО следующими кодами:

1. Двоично-десятичные (два разных кода по весам). Рассчитать избыточность

2. Код Грея. Показать уменьшение веса ошибки

III. Статистическое кодирование.

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

Закодировать полученный в п.1 алфавит кодами:

a) Шеннона-Фано

b) Хаффмана. Построить кодовое дерево

Для а) и б) доказать расчетами оптимальность кодов.

Закодировать в новых алфавитах ФИО студента и сравнить с результатом п.І.

IV. Коды, обнаруживающие ошибки с подсчетом избыточности. Показать процедуру кодирования и декодирования ФИО следующими кодами:

1. С проверкой на четность

2. С проверкой на нечетность

3. Инверсный код

4. Корелляционный код

5. Код Бергера

6. Код на одно сочетание

7. Код с количеством единиц в кодовых комбинациях, кратным трём.

V. Коды, исправляющие ошибки: закодировать, внести ошибку и исправить ее при декодировании.

1. Код Варшамова в матричном представлении

2. Код Хэмминга (2 первых буквы ФИО)

3. Расширенный код Хэмминга

4. Итеративный код

5. Коды-спутники (для 1-й буквы ФИО и d_min = 1,2)

6. Циклический код с d_min = 3

7. БЧХ (для 21 первых битов ФИО)

8. Рекуррентный

VI. Канальные коды:

1. Дуобинарный

2. Квазитроичный

3. Манчестер II

4. 4B3T

VII. Закодировать и представить в графическом виде штрих-код EAN-8 десятичного числа, содержащего последовательно: число, месяц и год рождения.

VIII. Разработать программу работы кодера или декодера для кода,согласованного с руководителем, на любом алгоритмическом языке.

РЕШЕНИЕ ПО РАЗДЕЛАМ

Исходные данные

Оконский Илья Вячеславович

ASCII-коды символов ФИО:

О – 11101111

И – 11101001

В – 11110111

Следовательно, исходная кодовая комбинация ФИО в цифровом коде:

 

Простейшие коды

Двоично-десятичные коды