Курсовая работа по «Основам сбора, передачи и обработки информации»

Автор: Пользователь скрыл имя, 12 Июня 2013 в 12:45, курсовая работа

Краткое описание

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

Оглавление

ВВЕДЕНИЕ 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

Скачать в ZIP (259.95 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

Kursa4_TIK.doc

— 1.17 Мб (Скачать)

Министерство образования и  науки Украины

Национальный технический университет  Украины

«Киевский Политехнический Институт»

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

 

 

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

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

 

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

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

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

гр. ИА-71

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

___________________

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

                        _______________________

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

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

__________________________

          (оценка)

«____» _____________ 2009 г.

 

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

_______________________                      _________________________

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

_______________________                      _________________________

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

                                           

Киев-2009

Содержание

 

ВВЕДЕНИЕ

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

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

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

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

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

 

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

  1. Исходные данные: ФИО студента (ФИО – 3 первые большие буквы русского алфавита) – переводим комбинацию букв в 24 бита ASCII  (таблицу брать в учебнике стр.121) → получаем ФИО в цифровом коде.
  2. Простейшие коды. Кодировать и декодировать ФИО следующими кодами:
    1. Двоично-десятичные (два разных кода по весам). Рассчитать избыточность
    1. Код Грея. Показать уменьшение веса ошибки
  1. Статистическое кодирование.

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

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

    1. Шеннона-Фано
    2. Хаффмана. Построить кодовое дерево

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

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

  1. Коды, обнаруживающие ошибки с подсчетом избыточности. Показать процедуру кодирования и декодирования ФИО следующими кодами:
  1. С проверкой на четность
  1. С проверкой на нечетность
  2. Инверсный код
  3. Корелляционный код
  4. Код Бергера
  5. Код на одно сочетание
    1. Код с количеством единиц в кодовых комбинациях, кратным трём.
  1. Коды, исправляющие ошибки: закодировать, внести ошибку и исправить ее при декодировании.
  1. Код Варшамова в матричном представлении
  1. Код Хэмминга (2 первых буквы ФИО)
  2. Расширенный код Хэмминга
  3. Итеративный код
  4. Коды-спутники (для 1-й буквы ФИО и dmin = 1,2)
  5. Циклический код с dmin = 3
  6. БЧХ (для 21 первых битов ФИО)
  7. Рекуррентный
  1. Канальные коды:
  1. Дуобинарный
  2. Квазитроичный
  3. Манчестер II
  4. 4B3T
  1. Закодировать и представить в графическом виде штрих-код EAN-8 десятичного числа, содержащего последовательно: число, месяц и год рождения.
  1. Разработать программу работы кодера или декодера для кода, согласованного с руководителем, на любом алгоритмическом языке.

 

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

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

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

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

О – 11101111

И – 11101001

В – 11110111

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

111011111110100111110111

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Краткие теоретические сведения

В двоично-десятичном коде (ДДК) каждая десятичная цифра представляется группой цифр, состоящей из 4-х  двухпозиционных символов. Данная группа позволяет сформировать N = 24 = 16 кодовых комбинаций. Так как в десятичной системе используется лишь десять цифр, шесть комбинаций являются избыточными. Поэтому выбор десяти используемых для построения ДДК комбинаций имеет 16! · 6! = 2.9 · 1010 вариантов. Использование, например, первых четырех степеней цифры 2 (20 = 1; 21 = 2; 22 = 4; 23 = 8) приводит к одному из возможных кодов 8-4-2-1.

Каждый разряд ДДК  имеет постоянный вес. ДДК строятся с учетом следующих условий:

  1. Вес наименьшей значащей цифры q1 равен 1.
  2. Вес второй по минимальному значению цифры q2 составляет 1 или 2.
  3. Веса, соответствующие двум оставшимся цифрам кода, подбирают так, чтобы их сумма была больше или равна 6 (если q2=2), или 7 (если q2 = 1).

В соответствии с этим можно получить 17 видов кодов:

8-4-2-1,

7-4-2-1,

6-4-2-1,

5-4-2-1,

4-4-2-1,

7-3-2-1,

6-3-2-1,

5-3-2-1,

4-3-2-1,

3-3-2-1,

6-2-2-1,

5-2-2-1,

4-2-2-1,

6-3-1-1,

5-3-1-1,

4-3-1-1,

5-2-1-1.

      

Для перевода одной десятичной цифры в двоично-десятичный код, необходимо, начиная со старшего двоичного  разряда, проверить, не больше ли вес  текущей (двоичной) цифры остатка числа; если меньше или равен – то в выходной код записать 1 и вычесть вес двоичной цифры из остатка числа, иначе в выходной код записать 0.

 

Кодирование

Исходная кодовая комбинация, которую необходимо закодировать:

111011111110100111110111,

представим её в десятичном виде:

15 722 999.

Выберем две комбинации ДДК:  7-4-2-1,  4-3-1-1.

 

7-4-2-1

4-3-1-1

1

0·7+0·4+0·2+1·1

0·4+0·3+1·1+0·1

5

0·7+1·4+0·2+1·1

1·4+0·3+1·1+0·1

7

1·7+0·4+0·2+0·1

1·4+1·3+0·1+0·1

2

0·7+0·4+1·2+0·1

0·4+0·3+1·1+1·1

2

0·7+0·4+1·2+0·1

0·4+0·3+1·1+1·1

9

1·7+0·4+1·2+0·1

1·4+1·3+1·1+1·1

9

1·7+0·4+1·2+0·1

1·4+1·3+1·1+1·1

9

1·7+0·4+1·2+0·1

1·4+1·3+1·1+1·1


Закодированное число  будет иметь вид:

ДДК

Закодированное число

7-4-2-1

0001 0101 1000 0010 0010 1010 1010 1010

4-3-1-1

0010 1010 1100 0011 0011 1111 1111 1111


 

Декодирование

Декодируем полученные кодовые комбинации:

0001 0101 1000 0010 0010 1010 1010 1010

0010 1010 1100 0011 0011 1111 1111 1111

зная, что они закодированы в  двоично-десятичных кодах 7-4-2-1 и 4-3-1-1 соответственно.

 

7-4-2-1

  

4-3-1-1

  

0·7+0·4+0·2+1·1=

1

0·4+0·3+1·1+0·1=

1

0·7+1·4+0·2+1·1=

5

1·4+0·3+1·1+0·1=

5

0·7+1·4+0·2+1·1=

7

1·4+1·3+0·1+0·1=

7

0·7+0·4+1·2+0·1=

2

0·4+0·3+1·1+1·1=

2

0·7+0·4+1·2+0·1=

2

0·4+0·3+1·1+1·1=

2

1·7+0·4+1·2+0·1=

9

1·4+1·3+1·1+1·1=

9

1·7+0·4+1·2+0·1=

9

1·4+1·3+1·1+1·1=

9

1·7+0·4+1·2+0·1=

9

1·4+1·3+1·1+1·1=

9




Декодированное число:

15 722 999.

Избыточность

Избыточность рассчитывается по формуле

, (1)

где r – количество избыточных данных,

n – длина кодовой комбинации.

В нашем случае:

(длина кодовой комбинации, закодированной  двоично-десятичным кодом),

(k – количество символов в исходной комбинации),

следовательно, избыточность:

2.2. Код Грея

Краткие теоретические сведения

Отражённые (рефлексные) коды строятся таким образом, что  соседние кодовые комбинации, в отличие  от простых двоичных кодов, различаются  цифрой только в одном разряде, т.е. кодовое расстояние между соседними кодовыми комбинациями такого кода равно единице. Из отражённых кодов наибольшее распространение получил код Грея.

Преобразование простого двоичного кода в код Грея производится по алгоритму: Yn = Xn; Yi = Xi xor Xi+1 , (xor – суммирование по модулю 2), где Yi – значение i-го разряда кода Грея; Xi, Xi+1 – соответствующие значения разрядов двоичного числа (i = 1, 2, ..., n, считая разряд с i = 1 – младшим, i = n - старшим). Т.е., для всех разрядов, кроме младшего, значение кода Грея равно сумме по модулю 2 соответствующего и следующего более старшего разрядов двоичного кода. Самый старший разряд сохраняется.

Декодирование (обратное преобразование) кода Грея в двоичный код осуществляют по следующей формуле: Xn = Yn; Xi = Xi+1 xor Yi, где Xn и Yn – значения старшего разряда двоичного кода и кода Грея соответственно (i = n-1, n-2, ..., 1, считая разряд с i = 1 – младшим, i = n – старшим).

  1. Старший разряд переносится в декодированную последовательность без изменений.
  2. Следующий разряд получаются суммированием по модулю 2 соответствующего и всех более старших разрядов закодированного сообщения – при 8-ми разрядном сообщении для декодирования 4-го разряда необходимо сложить по модулю 2 разряды 4, 5, 6, 7 и 8 кодовой комбинации.

Кодирование

Кодовая комбинация, которую необходимо закодировать:

111011111110100111110111.

Y24 = X24 = 1 Y12 = X12 xor X13 = 1

Y23 = X23 xor X24 = 0 Y11 = X11 xor X12 = 1

Y22 = X22 xor X23 = 0 Y10 = X10 xor X11 = 0

Y21 = X21 xor X22 = 1 Y9 = X9 xor X10 = 1

Y20 = X20 xor X21 = 1 Y8 = X8 xor X9 = 0

Y19 = X19 xor X20 = 0 Y7 = X7 xor X8 = 0

Информация о работе Курсовая работа по «Основам сбора, передачи и обработки информации»