Содержание

Лист

1. Введение

3

2. Элементы теории автоматов

4

3. Решение задачи

12

4. Техника безопасности

15

5 Заключение

17

7. Список литературы

18

8. Отзыв

19

Элементы теории кодирования

Лист

2

Изм.

Лист

№ докум.

Подпись

Дата

Введение

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

Объектом кодирования служит как дискретная, так и непрерывная информация, которая поступает к потребителю через источник информации. Понятие кодирование означает преобразование информации в форму, удобную для передачи по определенному каналу связи.

Обратная операция – декодирование – заключается в восстановлении принятого сообщения из закодированного вида в общепринятый, доступный для потребителя.

В теории кодирования существует ряд направлений:

1. статическое или эффективное кодирование;

2. помехоустойчивое кодирование;

3. корректирующие коды;

4. циклические коды;

5. арифметические коды.

Цель:

1. Изучить все элементы теории кодирования.

2. Разобрать все виды кодировок.

3. Решить задачу.

Элементы теории кодирования

Лист

3

Изм.

Лист

№ докум.

Подпись

Дата

Элементы теории кодирования

Необходимость кодирования информации возникла задолго до появления компьютеров. Речь, азбука и цифры – есть не что иное, как система моделирования мыслей, речевых звуков и числовой информации. В технике потребность кодирования возникла сразу после создания телеграфа, но особенно важной она стала с изобретением компьютеров. Область действия теории кодирования распространяется на передачу данных по реальным (или зашумленным) каналам, а предметом является обеспечение корректности переданной информации. Иными словами, она изучает, как лучше упаковать данные, чтобы после передачи сигнала из данных можно было надежно и просто выделить полезную информацию. Иногда теорию кодирования путают с шифрованием, но это неверно: криптография решает обратную задачу, ее цель - затруднить получение информации из данных. С необходимостью кодирования данных впервые столкнулись более полутораста лет назад, вскоре после изобретения телеграфа. Каналы были дороги и ненадежны, что сделало актуальной задачу минимизации стоимости и повышения надёжности передачи телеграмм. Проблема ещё более обострилась в связи с прокладкой трансатлантических кабелей. С 1845 вошли в употребление специальные кодовые книги; с их помощью телеграфисты вручную выполняли «компрессию» сообщений, заменяя распространенные последовательности слов более короткими кодами.. Для этого во вводимую колоду последней вкладывали специально подготовленную карту с контрольной суммой. Если устройство ввода было не слишком надежным (или колода - слишком большой), то могла возникнуть ошибка. Чтобы исправить её, процедуру ввода повторяли до тех пор, пока подсчитанная контрольная сумма не совпадала с суммой, сохраненной на карте. Эта схема неудобна, и к тому же пропускает двойные ошибки. С развитием каналов связи потребовался более эффективный механизм контроля. С появлением управляющих систем, в частности ЭВМ, роль кодирования существенно возросла и изменилась, так как без кодирования невозможна.

Элементы теории кодирования

Лист

5

Изм.

Лист

№ докум.

Подпись

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

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

Код – это правило однозначного преобразования сообщения из одной символической формы представления сообщения в другую, обычно без каких-либо потерь информации.

Под абстрактным алфавитом будем понимать упорядоченное дискретное множество символов.

Алфавитное кодирование. Алфавитное, т.е. побуквенное, кодирование можно задать таблицей кодов. Фактически кодом преобразования является некоторая подстановка .Тогда , где  алфавиту А,  множеству слов, составленных в алфавите В. Множество кодов букв называется множеством элементарных кодов. Алфавитное кодирование можно использовать для любого множества сообщений.

Компьютерная обработка данных основана на применении двоичного кода. Этот универсальный способ кодирования годится для любых данных, независимо от их происхождения и содержания.

Классификация кодов

Всё множество известных в настоящее время кодов условно делят на два направления: непомехозащищённые и помехозащищённые.

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

Двоичный код на все сочетания – кодовые комбинации этого кода соответствуют записи натурального ряда чисел в двоичной системе счисления. Общее число комбинаций этого кода равно

Элементы теории кодирования

Лист

6

Изм.

Лист

№ докум.

Подпись

Дата

N = 2n ,

где N – общее число комбинаций кода; n – длина кода.

Единично десятичный код. Каждому разряду десятичного числа соответствует определённое количество единиц. Разряды отделяются интервалами. Этот код неравномерный, но может быть преобразован в равномерный, если слева в каждом разряде дописать недостающие единицы нулями до 10 знаков.

Двоично десятичный код. Каждый разряд десятичного числа записывается в виде комбинации кодов. Существует несколько видов двоично десятичных кодов: код с весовыми коэффициентами 8.4.2.1, код с весовыми кэффициентами 2.4.2.1 (код Айкена)

Число импульсный код – единичный (унитарный), кодовые комбинации различаются числом единиц.

Код Морзе – относится к неравномерным кодам. Кодовые комбинации имеют разную длительность: точка – 1, тире – 111, интервал между точкой и тире – 0, интервал между комбинациями (буквами) – 000.

Код Бордо – равномерный пятиэлементный телеграфный код. Максимальное число комбинаций N = 25 = 32.

Код Грея (рефлексивный, отражённый). Две соседние комбинации отличаются только в соседних разрядах:

Помехозащищённые (помехоустойчивые или корректирующие) коды предназначены для обнаружения и исправления ошибок. В теореме К. Шеннона утверждается, что вероятность ошибок для дискретного канала с помехами может быть сведена к минимуму с помощью выбора соответствующего способа кодирования. В двоичных кодах каждый разряд может принимать значения 0 или 1. Количество единиц в кодовой комбинации называют весом кодовой комбинации и обозначают w. Например, кодовая комбинация 100101100 имеет длину (значность) 9 и вес w = 4. Степень отличия двух кодовых комбинаций называется кодовым расстоянием или расстоянием Хемминга, оно обозначается как d. Кодовое расстояние – это минимальное расстояние между кодовыми комбинациями, определяемое количеством (числом) отличающихся позиций или символов в кодовых комбинациях. Для вычисления кодовых расстояний используется сложение по mod 2.

Элементы теории кодирования

Лист

7

Изм.

Лист

№ докум.

Подпись

Дата

При воздействии помех в кодовой комбинации в одном или нескольких разрядах возможна трансформация 0 в 1 и 1 в 0 и получается наложенная комбинация. Ошибки, полученные в разряде кодовой комбинации, называют однократными. При 2 х, 3 х и т.д. разрядах – двукратными, трёхкратными и т.д.

Для определения мест ошибок в кодовой комбинации вводится понятие вектора ошибок. Вектор ошибок n разрядного кода – это n разрядная комбинация, единицы в которой указывают положение искажённых символов кодовой комбинации.

Вес вектора ошибки we характеризует кратность ошибки. Сумма по модулю 2 для искажённой кодовой комбинации и вектора ошибки равна исходной неискажённой комбинации.

Помехоустойчивость кодирования обеспечивается за счёт введения избыточности в кодовые комбинации. Это значит, что не все n символов кодовой комбинации используются для кодирования информации, а только какая их часть k<n. Следовательно, из всех возможных комбинаций N0 = 2n для кодирования используется Nk = 2k комбинаций, т.е. всё множество возможных кодовых комбинаций делится на две группы:

Группа Nk = 2k – разрешённых комбинаций.

Группа (N0 – Nk) = 2n – 2k – запрещённых комбинаций.

Если на приёмной стороне получена разрешённая комбинация, то считается, что искажений нет, иначе принятая комбинация искажена.

В общем случае каждая из Nk разрешённых комбинаций может трансформироваться в любую из N0 возможных комбинаций, т.е. всех возможных комбинаций может быть Nk*N0, Nk(Nk–1) переходы одних разрешённых комбинаций в другие разрешённые и Nk(N0–Nk) переходов в запрещённые комбинации.

.(3)

Для построения кода, обеспечивающего не только обнаружения ошибок, но и исправление ошибок. Множество запрещённых кодовых комбинаций разбивается на Nk непересекающихся подмножеств Nk, каждому из которых ставится в соответствие одна из разрешённых комбинаций. В этом случае, если принятая запрещённая комбинация принадлежит подмножеству Mi, то считается, что передана комбинация Аi и ошибка будет исправлена. Т.о. ошибка исправляется в (N0-Nk) случаях, равных количеству запрещённых комбинаций от общего числа обнаруженных ошибочных комбинаций определяется уравнением:

.(4)

Выбор способа разбиения на подмножества определяется типом ошибок. Допустим, необходимо построить код, обнаруживающий все ошибки кратностью t и меньше. Это значит, что из множества всех возможных комбинаций N0 необходимо выбрать Nk разрешённых комбинаций так, чтобы любая из них в сумме по модулю два с любым вектором ошибок E с весом weЈt не была равна никакой другой разрешённой комбинации. Для этого необходимо, чтобы кодовое расстояние удовлетворяло равенству:

dmin і t + 1, (5)

где dmin – наименьшее расстояние Хэмминга.

Элементы теории кодирования

Лист

9

Изм.

Лист

№ докум.

Подпись

Дата

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

Тексты – это последовательности символов, входящих некоторый алфавит. Кодирование текста сводится к двоичному кодированию алфавита, на основе которого он построен. Чаще всего применяется байтовое кодирование алфавита. В этом случае максимальная мощность алфавита составляет 256 символов. Такой алфавит может содержать два набора буквенных символов (например, русский и латинский), цифры, знаки препинания и математические знаки, пробел и небольшое число дополнительных символов. Примером такого алфавита является код ASCII.

Однако, ограниченный набор из 256 кодов символов сегодня уже не удовлетворяет возросшие потребности международного общения. Все большее распространение получает универсальная система 16-разрядного кодирования символов UNICODE.

Мощность алфавита в системе кодирования UNICODE составляет 216=65 536 разных кодов, из которых 63 484 кода соответствуют символам большинства алфавитов, а оставшиеся 2048 кодов разделены пополам и образуют таблицу размером 1024 столбцов х 1024 строк. В этой таблице более миллиона ячеек, в которых можно разместить еще более миллиона различных символов.

Это символы «мертвых» языков, а также символы, не имеющие лексического содержания, указатели, знаки и т.п. Для записи этих дополнительных символов необходима пара 16-разрядных слов (16 разрядов для номера строки и 16 разрядов для номера столбца).

Таким образом, система UNICODE является универсальной системой кодирования всех символов национальных письменных систем и обладает возможностью существенного расширения.

Элементы теории кодирования

Лист

10

Изм.

Лист

№ докум.

Подпись

Дата

Кодирование изображений

Рисунки, картинки, фотографии кодируются в растровом формате. В этом виде каждое изображение представляет собой прямоугольную таблицу, состоящую из цветовых точек. Цвет и яркость каждой отдельной точки выражаются в числовой форме, что позволяет использовать двоичный код для представления графических данных.

Черно-белые изображения принято представлять в градациях серого цвета, для этого используется модельGreyScale. Если яркость точки кодируется одним байтом, можно использовать 256 различных серых тонов. Такая точность согласуется с восприимчивостью человеческого глаза и возможностями полиграфической техники.

При кодировании цветных изображений применяют принцип декомпозиции цвета на составляющие, для этого используют модель RGB. Цветное изображение на экране получается путем смешивания трех базовых цветов : красного (Red, R), синего (Blue, B) и зеленого (Green, G).

Каждый пиксель на экране состоит из трех близко расположенных элементов, светящихся этими цветами.

Цветные дисплеи, использующие такой принцип называются RGB -мониторами.Код цвета пикселя содержит информацию о доле каждого базового цвета.Схему цветообразования Можно gосмотреть в Приложении 1

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

Элементы теории кодирования

Лист

11

Изм.

Лист

№ докум.

Подпись

Дата

— два цвета: черный или белый. Пиксель с битовой глубиной в 8 единиц имеет 28 или 256 возможных цветовых значений. Пиксель же с битовой глубиной в 24 единицы имеет 224 степени) или 16,7 миллионов возможных значений. Считается, что 24-битные изображения, содержащие 16,7 миллионов цветов, достаточно точно передают краски окружающего нас мира. Как правило, битовое разрешение задается в диапазоне от 1 до 48 бит/пиксель.

При печати на бумаге используется несколько иная цветовая модел: если монитор испускал свет, оттенок получался в результате сложения цветов, то краски - поглощают свет, цвета вычитаются. Поэтому в качестве основных используют голубую (Cyan, C), пурпурную (Magenta, M) и желтую (Yellow, Y) краски. Кроме того, из-за не идеальности красителей, к ним обычно добавляют четвертую -- черную (black, K). Для хранения информации о каждой краске и в этом случае чаще всего используется 1 байт. Такая система кодирования носит название CMYK.

Более грубое представление цвета использует меньшее число разрядов. Например, кодирование цветной графики 16-разрядными числами носит название High Color. В этом случае каждому цвету отводят пять разрядов.

Элементы теории кодирования

Лист

12

Изм.

Лист

№ докум.

Подпись

Дата

Кодирование звука и видео

Приемы работы со звуковой информацией пришли в компьютерную технику позже всего. Аналитический метод кодирования, применимый к любым звуковым сигналам основан на аналогово-цифровом преобразовании. Исходный аналоговый сигнал представляют как последовательность цифровых сигналов, записанных в двоичном коде. Разрядность преобразования определяет объем данных, соответствующих отдельному цифровому сигналу. При воспроизведении звука выполняют обратное цифро-аналоговое преобразование.

Этот метод кодирования содержит погрешность, так что воспроизводимый сигнал несколько отличается от оригинала.

Метод кодирования на основе табличного синтеза применим только к музыкальным произведением. В заранее подготовленных таблицах хранятся образцы (сэмплы) звуков различных музыкальных инструментов. Числовые коды определяют инструмент, ноту и продолжительность звучания.

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

Элементы теории кодирования

Лист

13

Изм.

Лист

№ докум.

Подпись

Дата