Основные результаты теории кодирования реферат
Обновлено: 30.06.2024
Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.
Теория кодирования — I
Рассмотрев компьютеры и принцип их работы, сейчас мы будем рассматривать вопрос представления информации: как компьютеры представляют информацию, которую мы хотим обработать. Значение любого символа может зависит от способа его обработки, у машины нет никакого определенного смысла у используемого бита. При обсуждении истории программного обеспечения 4 главе мы рассматривали некоторый синтетический язык программирования, в нём код инструкции останова совпадал с кодом других инструкций. Такая ситуация типична для большинства языков, смысл инструкции определяется соответствующей программой.
Для упрощения проблемы представления информации рассмотрим проблему передачи информации от точки к точке. Этот вопрос связан с вопросом сохранения информация. Проблемы передачи информации во времени и в пространстве идентичны. На рисунке 10.1 представлена стандартная модель передачи информации.
Рисунок 10.1
Слева на рисунке 10.1 находится источник информации. При рассмотрении модели нам неважна природа источника. Это может быть набор символов алфавита, чисел, математических формул, музыкальных нот, символов, которыми мы можем представить танцевальные движения — природа источника и значение хранящихся в нём символов не является частью модели передачи. Мы рассматриваем только источник информации, с таким ограничением получается мощная, общая теория, которую можно распространить на многие области. Она является абстракцией из многих приложений.
Кодер состоит из двух частей, первая часть называется кодер источника, точное название зависит от типа источника. Источникам разных типов данных соответствуют разные типы кодеров.
Вторая часть процесса кодирования называется кодирование канала и зависит от вида канала для передачи данных. Таким образом, вторая часть процесса кодирования согласована с типом канала передачи. Таким образом, при использовании стандартных интерфейсов данные из источника в начале кодируются согласно требованиям интерфейса, а потом согласно требованиям используемого канала передачи данных.
Фаза декодирования также состоит из двух этапов: канал — стандарт, стандарт- приемник данных. В конце передачи данных передаются потребителю. И снова мы не рассматриваем вопрос, как потребитель трактует эти данные.
Фундаментальная разница между представленной теорией и обычной теорией в физике — это предположение об отсутствии шума в источнике и приемнике. На самом деле, ошибки возникают в любом оборудовании. В квантовой механике шум возникает на любых этапах согласно принципу неопределённости, а не в качестве начального условия; в любом случае, понятие шума в теории информации не эквивалентно аналогичному понятию в квантовой механике.
Для определенности будем далее рассматривать бинарную форму представления данных в системе. Другие формы обрабатываются похожим образом, для упрощения не будем их рассматривать.
Начнем рассмотрение систем с закодированными символами переменной длины, как в классическом коде Морзе из точек и тире, в котором часто встречающиеся символы — короткие, а редкие — длинные. Такой подход позволяет достичь высокой эффективности кода, но стоит отметить, что код Морзе — тернарный, а не бинарный, так как в нём присутствует символ пробела между точками и тире. Если все символы в коде одинаковой длины, то такой код называется блочным.
Рассмотрим алфавит из небольшого числа символов, обычно алфавиты намного больше. Алфавиты языков начинается от 16 до 36 символов, включая символы в верхнем и нижнем регистре, числа знаки, препинания. Например, в таблице ASCII 128 = 2^7 символов.
Рассмотрим специальный код, состоящий из 4 символов s1, s2, s3, s4
s1 = 0; s2 = 00; s3 = 01; s4 = 11.
Как приёмник должен трактовать следующее полученное выражение
Как s1s1s4 или как s2s4?
Вы не можете однозначно дать ответ на этот вопрос, этот код однозначно нет декодируется, следовательно, он неудовлетворительный. С другой стороны, код
s1 = 0; s2 = 10; s3 = 110; s4 = 111
1101000010011011100010100110…
может быть разбита на блоки символов
110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110,…
согласно следующему правилу построения дерева декодирования:
Если вы находитесь в вершине дерева, то считываете следующий символ. Когда вы достигаете листа дерева, вы преобразовывает последовательность в символ и возвращайтесь назад на старт.
Причина существования такого дерева в том, что ни один символ не является префиксом другого, поэтому вы всегда знаете, когда необходимо вернуться в начало дерево декодирования.
Отказ от использования завершающего символа является частой ошибкой при дизайне кодов. Конечно же можно предусмотреть режим постоянного декодирования, в этом случае завершающая символ не нужен.
Рисунок 10.II
Следующий вопрос — это коды для поточного (мгновенного) декодирования. Рассмотрим код, который получается из предыдущего отображением символов
s1 = 0; s2 = 01; s3 = 011; s4 = 111.
Рассмотрим два способа кодирования одного и того же символа, Si:
s1 = 0; s2 = 10; s3 = 110; s4 = 1110, s5 = 1111,
Дерево декодирование этого способа представлено на рисунке 10.III.
Рисунок 10.III
s1 = 00; s2 = 01; s3 = 100; s4 = 110, s5 = 111,
Дерево декодирование это ухода представлены на рисунке 10.IV.
Рисунок 10.IV
Рисунок 10.V
Рассмотрим неравенство Крафта, которое определяет предельное значение длины кода символа li. По базису 2 неравенство представляется в виде
Это неравенство говорит о том, что в алфавите не может быть слишком много коротких символов, в противном случае сумма будет довольно большой.
Для доказательства неравенства Крафта для любого быстрого уникального декодируемого кода построим дерево декодирования и применим метод математической индукции. Если у дерева есть один или два листа, как показано на рисунке 10.V, тогда без сомнения неравенство верно. Далее, в случае если у дерева есть более чем два листа, то разбиваем дерево длинный m на два поддерева. Согласно принципу индукции предполагаем, что неравенство верно для каждой ветви высотой m -1 или меньше. Согласно принципу индукции, применяя неравенство к каждой ветви. Обозначим длины кодов ветвей K' и K''. При объединении двух ветвей дерева длина каждого возрастает на 1, следовательно, длина кода состоит из сумм K’/2 и K’’/2,
Рассмотрим доказательство теорема Макмиллана. Применим неравенство Крафта к непоточно декодируем кодам. Доказательство построено на том факте, что для любого числа K > 1 n-ая степень числа заведомо больше линейной функции от n, где n — довольно большое число. Возведем неравенство Крафта в n-ую степень и представим выражение в виде суммы
где Nk число символов длины k, суммирование начинаем с минимальной длины n-го представление символа и заканчиваем максимальной длины nl, где l — максимальная длина закодированного символа. Из требования уникального декодирования следует, что. Сумма представляется в виде
Если K > 1, тогда необходимо n установить довольно большим для того, чтобы неравенство стало ложным. Следовательно, k
Оптимальным статистическим (экономным) кодированием называется кодирование, при котором обеспечивается распределение времени на передачу отдельных символов алфавита в зависимости от априорных вероятностей их появления:
где Cп - пропускная способность канала; pi - априорная вероятность i –й кодовой комбинации; ti -длительность i-й кодовой комбинации.
Оптимальными неравномерными кодами (ОНК) - называются коды, в которых символы алфавита кодируются кодовыми словами минима-льной средней длины.
Принципы построения оптимальных кодов:
1. Каждая кодовая комбинация должна содержать максимальное количество информации, что обеспечивает максимальную скорость передачи данных.
При таком кодировании избыточность кода, которая вызвана неравной вероятностью символов алфавита, сводится к минимуму (практически к нулю). Оптимальные коды являются неравномерными блочными кодами, при их построении необходимо обеспечить однозначность декодирования. Префиксным (неприводимым)- называется код, в котором ни одна кодовая комбинация не является началом другой. Для обеспечения этого свойства кодовые комбинации должны записываться от корня кодового дерева.
Возможность однозначного декодирования неравномерного кода обеспечивается выполнением требования разделимости (префиксности) кодовых комбинаций.
При неравномерном кодировании производится сжатие данных. Сжатие данных используется как при хранении данных в памяти, так и при их передаче. Оптимальное кодирование можно использовать только в каналах без помех или в случае низкой требовательности к достоверности передаваемой информации.
Существует много методов оптимального, статистического кодирования. Наиболее часто используют оптимальное кодирование по методу Шеннона - Фано и Хаффмена.
2. КОД ШЕННОНА-ФАНО
Кодирование по методу Шеннона - Фано осуществляется следующим образом:
3. Всем символам верхней группы приписывается кодовый символ 1, а символам нижней - 0. Можно наоборот, т. к. для кодовой реализации безразлично 0 или 1, но с точки зрения мощности, лучше, если в кодовой комбинации меньше единиц.
4. Затем каждая подгруппа аналогичным образом разбивается на подгруппы по возможности с одинаковыми вероятностями. Разбиение осуществляется до тех пор, пока в каждой подгруппе останется по одному символу.
Пример построения кода приведен в таблице 1.
a1
Построенный код является префиксным.
Например: полученная кодовая последовательность 11100001 однозначно декодируется как:
Применяя статистическое кодирование можно получить результат, близкий к идеальному кодированию по Шеннону.
Средняя длина кодовой комбинации, при использовании двоичного кода в качестве вторичного, равна
, (2)
где li - длина i-й комбинации; N -основание первичного кода.
Эффективность ОНК максимальна при
; . (3)
Коэффициент относительной эффективности (коэффициент использования пропускной способности) равен
. (4)
. (5)
Для рассмотренного примера при длительности символа кодовой комбинации (0 или 1) равной t средняя длина и средняя длительность кодовой комбинации, соответственно равны:
Энтропия источника равна
При этом: Коэ = 1,75/1,75 = 1; Кcc = 2/1,75 = 1,14.
Скорость передачи информации
, (6)
т. е. коэффициент использования пропускной способности канала равен 1, а значит, имеет место идеальное использование канала (оптимальное статистическое кодирование).
Если подгруппы имеют не одинаковую суммарную вероятность, то коэффициент меньше 1. Для равномерного кода , при этом
.
Недостаток кода ОНК - низкая помехоустойчивость, т. к. потеря одного разряда может означать потерю символа.
Кодирование по методу Хаффмена осуществляется следующим об-разом:
1. Все подлежащие кодированию символы записываются в порядке убывания их априорных вероятностей. Если некоторые символы имеют одинаковые вероятности, то их располагают рядом в произвольном порядке.
2. Выбирают символы с минимальными вероятностями по 2 и одному приписывают 0, а другому 1.
3. Выбранные символы объединяют в промежуточные символы с суммарной вероятностью.
4. Снова находят пару символов с наименьшими вероятностями и поступают аналогично.
x1
Энтропия источника равна
Средняя длина кодовой комбинации данного кода
Длина кодовой комбинации примитивного кода определяется соотношением
(7)
Округляя до ближайшего целого в большую сторону, получим l = 3.
Эффективность ОНК максимальна, если .
Коэффициент относительной эффективности равен
.
Коэффициент статистического сжатия равен
.
Неравномерный код можно передавать блоками заданной длины, а на приемной стороне декодировать всю последовательность.
Оценить эффективность каждого кода, т. е. насколько они близки к оптимальным. Определить емкость (пропускную способность) канала связи для каждого кода, если скорость передачи двоичных символов (V = 1/t) равна 1000 симв/с, т.е. время передачи одного символа вторичного алфавита (двоичного символа) равна t = 0,001с = 1мкс.
Решение: Построим код по методу Шеннона-Фано, используя сле-дующий алгоритм:
2. Исходный ансамбль кодируемых символов разбиваем на две группы с примерно равными вероятностями (лучше, если суммарная вероятность верхней группы меньше).
3. Верхней группе присваиваем символ 1, а нижней 0.
4. Процесс деления повторяем до тех пор, пока в каждой подгруппе останется по одному символу.
Процесс построения кода приведем в таблице 3.
a5
..
Могут быть и другие варианты построения кода, но lср при этом не меняется.
+0,3126+0,2915+0,2686+0,2161+0,1129 = 2,49 бит/симв.
Оценим эффективность построенного кода, которая определяется коэффициентами относительной эффективности и статистического сжатия.
Коэффициент относительной эффективности равен
Коэффициент статистического сжатия равен
.
.
Для полученного кода она равна
С = 10 3 ×2,54 = 2,54 Кбит/с.
Построим код по методу Хаффмена, используя следующий алгоритм:
1. Символы первичного алфавита располагаем в порядке убывания их вероятностей.
2. Последние два символа объединяем в один, с суммарной вероятностью.
3. Упорядочиваем символы с учетом вновь образованных и последние два символа объединяем в один с суммарной вероятностью. Эту процедуру повторяем до тех пор, пока не останется два символа.
При построении дерева символы, в принципе, можно не упорядочивать.
Процесс построения кода приведен в таблице 4.
Коэффициент статистического сжатия равен
.
Коэффициент относительной эффективности
.
Необходимая пропускная способность канала связи
Кбит/c.
. .
Построенные коды Шеннона – Фано и Хаффмена равноценны, т. к. они имеют одинаковые показатели эффективности. Оба кода отличаются от оптимального на 2%.
Помехоустойчивость- способность системы осуществлять прием информации в условиях наличия помех в линии связи и искажений во внутри аппаратных трактах. Помехоустойчивость обеспечивает надежность и достоверность передаваемой информации (данных). Мы будем в основном рассматривать двоичные коды. Двоичные (коды) данные передаются между вычислительными терминалами, летательными аппаратами, спутниками и т. д.
Передача данных в вычислительных системах чувствительна к малой доле ошибке, т. к. одиночная ошибка может существенно нарушить процесс вычислений.
Наиболее часто ошибки появляются в УВВ, шинах, устройствах памяти. УВВ содержат большое количество элементов, ошибки обуславливаются старением элементов, ухудшением качества электрических соединений, расфазировкой сигналов. Значительная часть ошибок приходится на ОП, вследствие отказа отдельных ИС либо всей ИС, ошибок связанных с флуктуацией напряжения питания и т. д.
Увеличение мощности сигналов приводит к усложнению и удорожанию аппаратуры, кроме того, в некоторых системах передачи информации имеется ограничение на передаваемую мощность, например, спутниковая связь.
Кодовое расстояние - d определяется как количество единиц в результате суммирования по модулю два двух кодовых комбинаций. Минимальное кодовое расстояние d0 - минимальное из кодовых расстояний всех возможных кодовых комбинаций.
Для обнаружения r ошибок минимальное кодовое расстояние равно:
Для обнаружения r ошибок и исправления s ошибок минимальное кодовое расстояние равно:
Только для исправления ошибок минимальное кодовое расстояние равно:
5. ОБНАРУЖИВАЮЩИЕ КОДЫ
В символьном коде ASCII к семи битам кода добавляется восьмой бит проверки на четность - k1 .
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
Однобитовая проверка позволяет обнаружить любую единичную ошибку, две ошибки обнаружить нельзя, в общем случае обнаруживается любое нечетное количество ошибок.
Внесение избыточности за счет увеличения длины кодовой комбинации приводит к снижению скорости передачи информации.
Если скорость идеально использует канал, то
. (11)
Если кодовая комбинация длиной n содержит k информационных и m контрольных разрядов (n = k + m), то
.
Для кода ASCII n = 8 и k = 7
,
т. е. введения одного избыточного разряда приводит к уменьшению пропускной способности канала связи на 12,5%.
Чаще всего шумы (молнии, разрыв и т.д.) порождают длинные пакеты ошибок и вероятность четного и нечетного числа ошибок одинакова, а значит и однобитовая проверка не эффективна.
Проверка на четность по вертикали и горизонтали. При этом последовательность битов данных перестраивается в двухмерный массив, и вычисляются биты на четность, как для каждой строки, так и для каждого столбца.
При этом можно обнаружить несколько ошибок, если они не располагаются в одинаковых строках и столбцах.
Чаще всего используется при передаче данных кода ASCII; каждый символ можно считать строкой массива. Такая проверка может не только установить факт ошибки, но и обнаружить ее место, а значит, есть принципиальная возможность ее исправления, хотя это практически не используется.
1 0 1 1 0 1 1 1
0 1 0 0 0 1 0 0
1 0 1 0 0 1 0 1
1 1 0 0 1 0 1 0
0 0 0 1 0 1 0 0
Проверка на четность широко используется на ЭВМ, как на аппаратном, так и на программном уровне.
Например, при считывании с магнитной ленты в случае, когда условие на четность не выполняется, то производится повторное считывание, т. е. если произошла малая потеря намагниченности, то после второй попытки может быть считывание произойдет правильно.
Пример 1. Символы алфавита источника кодируются семиразрядным двоичным кодом с весом кодовых векторов (количеством единиц в кодовой комбинации) w = 3. Определить необходимую мощность кода и его избыточность.
Решение: Мощность семиразрядного кода равна N = 2 7 = 128.
Так как для кодирования используются только кодовые вектора с весом три , то количество таких векторов в семиразрядном коде равно
Избыточность кода равна R = 1 – log2 K/ log2 N = 0,265.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПб ГИТМО (ТУ), 2001;
2. Мастрюков Д. Алгоритмы сжатия информации. Ч. 1. Сжатие по Хаффмену //Монитор, 1993. – № 7 – 8 – С. 14 – 20;
3. Мастрюков Д. Алгоритмы сжатия информации. Ч. 2. Арифметическое кодирование //Монитор, 1994 – № 1 – С. 20 – 23;
4. Ф.Дж.Мак-Вильямс, Н.Дж.А.Слоэн, Теория кодов, исправляющих ошибки, Москва, “Связь”, 1979.
5. .Лидл, Г.Нидеррайтер, Конечные поля, Т. 1,2, Москва, “Мир”, 1988.
6. Т.Касами, Н.Токура, Е.Ивадари, Я.Инагаки, Теория кодирования, Москва, “Мир”, 1978.
7. У.Петерсон, Э.Уэлдон, Коды, исправляющие ошибки, Москва, “Мир”, 1976.
8. Э.Берлекэмп, Алгебраическая теория кодирования, Москва, “Мир”, 1971.
10. Лидовский В. В. Теория информации: Учебное пособие. — М.: Компания Спутник+, 2004
Содержание работы
Содержимое работы - 1 файл
Моя курсовая 2.doc
Государственное образовательное учреждение
высшего профессионального образования
«Арзамасский государственный педагогический институт
Кафедра математики, теории и методики обучения математике
Макарова К.А., студентка
З курса очного отделения
ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ
к.п.н., доцент Фомина Н.И.
§ 1. Базовые понятия теории кодирования……………………………………. 5
§ 2. Алфавитное кодирование………………………………………………… …9
§ 4. Кодирование и обработка чисел компьютером…………………………. 20
§ 5. Решение практических задач……………………………………………..25
В этой работе речь пойдет о том, без чего в настоящее время трудно представить какую-либо деятельность. Современный человек на столько
Теория кодирования представляет собой один из разделов дискретной математики, в котором рассматривается процесс представления информации в определенной стандартной форме и обратный процесс восстановления информации по этому представлению.
Дискретная математика – одна из областей математики, начала которой возникли в глубокой древности. Основной отличительной чертой её классической математики, которая в основном занимается изучением свойств объектов непрерывного характера с использованием основного понятия – предел, является дискретность, противоположность непрерывности. Предметом дискретной математики является изучение свойств произвольных структур (множеств с операциями, отношения и аксиомами), которые появляются как в самой математике, так и в области её приложений.
Дискретная математика включает в себя такие разделы как теорию чисел, алгебру, математическую логику, теорию графов и сетей, теорию кодирования, комбинаторный анализ и теорию конечных автоматов.
Особенностью дискретной математики является, наряду с задачами типа существования, имеющими общематематический характер, наличие задач, связанных с алгоритмической разрешимостью и построением конкретных решающих алгоритмов. При этом по существу впервые возникла необходимость полного исследования так называемых многоэкстремальных задач.
Прежде средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения, но с появлением компьютеров ситуация радикально изменилась. Кодирование является центральным вопросом при решении практически всех задач программирования:
- представления данных произвольной природы в памяти компьютера;
- защита информации от несанкционированного доступа;
- обеспечение помехоустойчивости при передаче данных по каналам
связи; - сжатие информации в базах данных.
Целью данной курсовой работы является рассмотрение кодирования как способа представления информации.
Задачи курсовой работы состоят в изучении учебной и научной литературы по теме исследования, в рассмотрении сущности понятия кодирования информации, в характеристике процессов кодирования и декодирования.
Работа содержит пять параграфов, в первом из которых приведены основные сведения о базовых элементах теории кодирования. Во втором параграфе описывается алфавитное кодирование и раскрывается проблема взаимной однозначности. В третьем параграфе рассматривается двоичный алфавит и коды Хемминга. Четвёртый параграф посвящен кодированию и обработке чисел компьютером. Решения практических задач приведены в пятом параграфе.
§ 1. Базовые понятия теории кодирования
1. 1. Кодирование как способ представления информации
Одни и те же сведения могут быть представлены, закодированы в нескольких разных формах и, наоборот, совершенно разные сведения могут быть представлены в похожей форме.
Чтобы передать информацию, её необходимо предварительно преобразовать.
В систему связи необходимо ввести устройства для кодирования и декодирования информации.
При передаче по каналу связи возникают ошибки, связанные с разными причинами, но все они приводят к тому, что получатель принимает искаженную информацию. Для того чтобы организовать нормальную работу информационного канала связи необходимо решить следующие проблемы:
обнаружить ошибки, если они возникают;
исправлять найденные ошибки;
защищать информацию, передающуюся по каналам связи;
ускорять передачу информации по каналу связи.
Из перечисленных проблем теория кодирования исследует первую и вторую. Третьей проблемой занимается криптография. Четвертая же является прикладной для криптографии и теории кодирования как параметр, с помощью которого определяется качество криптографии и кодирования.
1. 2. Кодирование и декодирование
Кодированием называется отображение произвольного множества А в множество конечных последовательностей в некотором алфавите В, а декодированием — обратное отображение.
Изучение различных свойств кодирования и декодирования, а так же построение кодирований (кодов), обладающих требуемыми свойствами, составляет предмет исследований теории кодирования.
Требуемые свойства связаны обычно с простотой реализации кодирования и декодирования, с обеспечением помехоустойчивости и т.д. Под помехоустойчивостью понимается возможность однозначного декодирования при отсутствии или допустимом уровне искажений в кодовых словах.
Рассмотрим некоторые примеры кодов.
1. Азбука Морзе в русском варианте ( алфавиту, составленному из алфавита русских заглавных букв и алфавита арабских цифр ставится в соответствие алфавит Морзе):
2. Код Трисиме (знакам латинского алфавита ставятся в соответствие комбинации из трех знаков: 1,2,3):
| А | 111 | H | 132 | O | 223 | V | 321 |
| В | 112 | I | 133 | P | 231 | W | 322 |
| С | 113 | J | 211 | Q | 232 | X | 323 |
| В | 121 | K | 212 | R | 233 | Y | 331 |
| D | 122 | L | 213 | S | 311 | Z | 332 |
| F | 123 | M | 221 | T | 312 | . | 333 |
| G | 131 | N | 222 | U | 313 |
Код Трисиме является примером, так называемого, равномерного кода (такого, в котором все кодовые комбинации содержат одинаковое число знаков - в данном случае три). Пример неравномерного кода - азбука Морзе.
3. Кодирование чисел знаками различных систем счисления
1. 3. Помехоустойчивое кодирование
Важная роль помехоустойчивого кодирования обусловлена недопустимостью ошибок в вычислительных системах, также использованием кодов, исправляющих или обнаруживающих ошибки на выходе вычислительных устройств. Таким образом, помехоустойчивость или исправление ошибок является функцией декодирования.
1. 4. Канал связи
Передача информации сводится к передаче по каналу связи слов, которые могут искажаться и поэтому восприниматься неверно. Рассмотрим принципиальную схему цифровой системы связи с использованием кодирования и декодирования (рис.).
В идеальном случае символы, которые появляются на выходе декодирующего устройства, должны совпадать с символами, которые поступают на вход кодирующего устройства. Но в реальных системах передачи и обработки информации появляются случайные и преднамеренные ошибки.
1. 5. Криптология
Конфиденциальной (секретной) информацией называется информация, которая по соглашению между ее отправителем и получателем не предназначена для третьих лиц.
Целью курсовой работы является разработка лабораторного практикума по теории кодирования.
Для достижения поставленной цели были определены следующие задачи:
- углубленное изучение теоретического материала по теории кодирования;
- разработка заданий для проведения лабораторного практикума по теории кодирования;
- реализация решения задач по теории кодирования на языке программирования Pascal.
Содержание
Введение
Теоретическая часть
1. История теории кодирования
2. Основные понятия теории кодирования
3. Системы счисления как способ кодирования информации
3.1 Позиционные системы счисления
3.2 Смешанные системы счисления
3.3 Двоичная система счисления
4. Современные способы кодирования
4.1 Алфавитное кодирование
5. Кодирование и обработка чисел компьютером
6.Эффективное кодирование
6.1 Основная теорема Шеннона о кодировании для канала без помех
Практическая часть
Заключение
Приложение1
Приложение2
Список летиратуры
Вложенные файлы: 1 файл
Курсовая.docx
1. История теории кодирования
2. Основные понятия теории кодирования
3. Системы счисления как способ кодирования информации
3.1 Позиционные системы счисления
3.2 Смешанные системы счисления
3.3 Двоичная система счисления
4. Современные способы кодирования
4.1 Алфавитное кодирование
5. Кодирование и обработка чисел компьютером
6.1 Основная теорема Шеннона о кодировании для канала без помех
Объектом кодирования служит как дискретная, так и непрерывная информация, которая поступает к потребителю через источник информации. Понятие кодирование означает преобразование информации в форму, удобную для передачи по определенному каналу связи.
Целью курсовой работы является разработка лабораторного практикума по теории кодирования.
Для достижения поставленной цели были определены следующие задачи:
- углубленное изучение теоретического материала по теории кодирования;
- разработка заданий для проведения лабораторного практикума по теории кодирования;
- реализация решения задач по теории кодирования на языке программирования Pascal.
1.История теории кодирования
С глубокой древности люди искали эффективные способы передачи информации:
- Движение факелов использовал древнегреческий историк Полибий
- оптический телеграф – семафор – впервые использовал Клод Шапп в 1791г.;
- Движение электромагнитной стрелки в электромагнитных телеграфных аппаратах впервые применили русский физик П.Л.Шиллинг ( 1832) и профессора Гёттенгенского университета Вебер и Гаусс (1833);
- Азбука и телеграфный аппарат Самюэла Морзе (1837);
- Международный флажковый код для передачи информации оптическими сигналами впервые ввел капитан Фредерик Марьят в 1861 г. На основе свода корабельных сигналов;
- Беспроволочный телефон, телевидение (1935), затем и ЭВМ – новые средства связи, появившиеся в XX в.,с которыми связана новая эпоха в информатизации общества.
К тайнописи – криптографии прибегал Гай Юлий Цезарь, заменяя в своих тайных записях одни буквы другими. Использовали шифрование не только древнегреческие жрецы, но и ученые Средневковья: математики итальянец Джероламо Кардано и француз Франсуа Виет, нидерландский гуманист, историк, юрист Гроций, выдающийся английский философ Фрэнсис Бэкон. Однако отцом криптографии считается архитектор Леон Баттиста Альберти (1404-1472), который ввел шифрующие коды и много алфавитные подстановки.
Первые манипуляция с символами в виде различных кодов возникли с потребностью шифровать информацию.
Знания математики нужны для того, чтоб найти простую, но надежную систему кодирования, недоступную для расшифровки посторонним лицам, а так же найти способы декодирования чужой системы тайнописи, чужих кодов.
Например, механическая замена одних букв или чисел другими – подстановки Цезаря – достаточно легко поддается дешифровке. Причем сам процесс декодирования аналогичен решению неопределенных уравнений со многими неизвестными.
Сэр Фрэнсис Бэкон (1561-1626), английский писатель и философ, лорд-канцлер елизаветинской эпохи, автор двух литерного кода, доказал в 1580 г., что для передачи информации достаточно двух знаков. Ф.Бэкон сформулировал требованию к шифру.
- Несложен, прост в работе;
- Надежен, труден для дешифровки посторонним;
- Скрытен, по возможности не должен вызывать подозрений.
Шифры Бэкона – сочетание шифрованного текста с дезинформацией в
виде нулей .Двузначные коды и шифры использовались задолго до появления ЭВМ.
Кодирование имеет значение не только в конспиративных целях для шифровки информации. Так, в математике с помощью кодирования изучение одних объектов заменяют изучением других, более доступных или уже известных. Ярким примером кодирования в математике является метод координат, введены Декартом, который дает возможность изучать геометрические объекты через их аналитическое выражение в виде чисел, букв и их комбинаций – формул [4,с.60-64].
Теория кодирования – довольно молодая наука. Исследование надежности кодов получило новый импульс после создания в 1948 г, Клодом Эльвудом Шенноном теории информации.
С появлением управляющих систем, в частности ЭВМ, роль кодирования существенно взросла и изменилась, так как без кодирования невозможна передача информации. В последнее время в связи с развитием телекоммуникационных систем и широким использованием вычислительной техники для обработки и хранения информации возникла новая область знаний – информационная безопасность.
Доступность проникновения через Интернет в экономические, политические, военные системы любой страны выявила новую мировую проблему – борьбу с компьютерными взломщиками, хакерами, и компьютерными террористами.
Криптоаналитики пользуются математическими методами при работе с информацией. Так, методы декодирования включают в себя решение различных уравнение. Разгадывание замечательных заданий, арифметических ребусов, в которых одинаковые цифры заменены одинаковыми буквами, а разные – разными, связано с решением уравнений со многими неизвестными и основано на разложение числа по степеням основания q.
2. Основные понятия теории кодирования.
Теория кодирования информации является одним из важных разделов теоретической информатики. В нем рассматриваются такие вопросы как: принципов кодирования информации и приемов, обеспечивающих надежность передачи информации по каналам связи, т.е отсутствие потерь информации.
Первая же задача – кодирование информации – касается не только передачи, но и обработки, и хранение информации, т.е охватывает широкий круг проблем; частным их решением будет представление информации в компьютере.
Кодирование предшествует передаче и хранению информации. При этом, как указывалось ранее, хранение связано с фиксацией некоторого состояния носителя информации, а передача – с изменением состояния с течением времени (т.е процессом). Эти состояния или сигналы называют элементарными сигналами – их совокупность и составляет вторичный алфавит [1,с.110-135].
Существует несколько определений понятия код, в зависимости от области применения.
Код – правило, описывающее соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторично алфавита.
Код – набор знаков вторично алфавита, используемый для представления знаков или их сочетаний первичного алфавита.
Процесс обратного преобразования слова называется декодированием. Декодирование можно рассматривать как функцию F1 – обратную функции F – кодированию.
Кодер – устройство, обеспечивающее выполнение операции кодирования.
Декодер – устройство, производящее декодирование.
Операции кодирования и декодирования называются обратными, если их последовательное применение обеспечивает возврат к исходной информации без каких – либо ее потерь [2, с. 63-66].
Примером обратимого кодирования является представление знаков в телеграфном коде и их восстановление после передачи. Примером кодирования необратимого может служить перевод с одного естественного языка на другой – обратный перевод, вообще говоря, не восстанавливает исходного текста. Безусловно, для практических задач, связанных со знаковым представителем информации, возможность восстановления информации по ее коду является необходимым условием применения кода, поэтому в дальнейшем изложении ограничим себя рассмотрением только обратимого кодирования.
Правила обработки могут быть различными:
- Поэлементное кодирование;
- Кодирование с помощью алгоритма;
- Кодирование с помощью различных видов графики и др.
Так как для любо кодирования должна выполняться операция декодирования, то отображение должно быть обратимым (биекция).
3. Системы счисления как способ кодирования информации.
Система счисления – совокупность различных знаков и правил, для записи количественного значения.
Цифра – знак, предназначенный для записи чисел.
В любой системе счисления для представления чисел выбираются некоторые символы (слова или знаки), называемые базисными числами, а все остальные числа получаются в результате каких – либо операции из базисных чисел данной системы исчисления. Символы, используемые для записи чисел, могут быть любыми, только они должны быть разными и значение каждого из них должно быть известно.
В современном мире наиболее распространенным является представление чисел посредством арабских цифр 0,1,2,3,4,5,6,7,8,9 – специальных знаков, используемых для записи чисел.
Системы счисления различаются выбором базисных чисел, которые обозначаются знаками – цифрами и правилами образования из них остальных чисел.
Системы счисления подразделяются:
Позиционные системы – каждый числовой знак в записи любого числа имеет значение, зависящее от его расположения в записи числа. Примером служит современная десятичная система счисления. Так в числе 555, первая справа цифра 5 обозначает единицы, вторая – десятки, третья – сотни. Позиционные системы счисления занимают преимущественное положение среди остальных систем. Особенности этих систем будут рассмотрены в следующем разделе данной темы.
Читайте также: