Реферат: Кодирование информации

Курс: Теория информации и кодирования

Тема: Кодирование


Содержание

1. Кодирование. Основные понятия и определения

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

3. Способы представления кодов

3.1 Матричное представление кодов

3.2 Представление кодов в виде кодовых деревьев

3.3 Представление кодов в виде многочленов

3.4 Геометрическое представление кодов

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


1. Кодирование. Основные понятия и определения

Рассмотрим основные понятия, связанные с кодированиеминформации. Для передачи в канал связи сообщения преобразуются в сигналы. Символы,при помощи которых создаются сообщения, образуют первичный алфавит, при этомкаждый символ характеризуется вероятностью его появления в сообщении. Каждомусообщению однозначно соответствует сигнал, представляющий определеннуюпоследовательность элементарных дискретных символов, называемых кодовымикомбинациями. Кодирование — это преобразование сообщений всигнал, т.е. преобразование сообщений в кодовые комбинации. Код — система соответствия между элементами сообщений и кодовыми комбинациями. Кодер — устройство, осуществляющее кодирование. Декодерустройство,осуществляющее обратную операцию, т.е. преобразование кодовой комбинации всообщение. Алфавит — множество возможных элементов кода, т.е. элементарныхсимволов (кодовых символов) X = {xi}, гдеi = 1, 2,..., m.Количество элементов кода — m называется его основанием.Для двоичного кода xi = {0, 1} и m = 2. Конечнаяпоследовательность символов данного алфавита называется кодовойкомбинацией (кодовым словом). Число элементов в кодовой комбинации — nназывается значностью (длиной комбинации). Число различныхкодовых комбинаций (N = mn) называется объемомили мощностью кода.

Если N0 — число сообщений источника, то N³ N0. Множествосостояний кода должно покрывать множество состояний объекта. Полный равномерныйn — значный код с основанием m содержит N = mn кодовыхкомбинаций. Такой код называетсяпримитивным.


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

Коды можно классифицировать по различным признакам:

1. По основанию (количеству символов в алфавите): бинарные(двоичные m=2) и не бинарные (m ¹2).

2. По длине кодовых комбинаций (слов):

равномерные — если все кодовые комбинацииимеют одинаковую длину;

неравномерные — если длина кодовой комбинациине постоянна.

3. По способу передачи:

последовательные и параллельные;

блочные — данные сначала помещаются в буфер, апотом передаются в канал и бинарныенепрерывные.

4. По помехоустойчивости:

простые (примитивные, полные) — для передачиинформации используют все возможные кодовые комбинации (без избыточности);

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

5. В зависимости от назначения и применения условно можновыделить следующие типы кодов:

Внутренние коды — этокоды,используемые внутри устройств. Это машинные коды, а также коды, базирующиеся наиспользовании позиционных систем счисления (двоичный, десятичный,двоично-десятичный, восьмеричный, шестнадцатеричный и др.). Наиболеераспространенным кодом в ЭВМ является двоичный код, который позволяет простореализовать аппаратно устройства для хранения, обработки и передачи данных вдвоичном коде. Он обеспечивает высокую надежность устройств и простотувыполнения операций над данными в двоичном коде. Двоичные данные, объединенныев группы по 4, образуют шестнадцатеричный код, который хорошо согласуется сархитектурой ЭВМ, работающей с данными кратными байту (8 бит).

Коды для обмена данными и их передачи поканалам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII- это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работаютс байтами, то 8-й разряд используется для синхронизации или проверки начетность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичныйкод для обмена информацией EBCDIC (Extended Binary Coded Decimal InterchangeCode).

В каналах связи широко используется телетайпный код МККТТ (международныйконсультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).

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

Коды для специальных применений — это коды,предназначенные для решения специальных задач передачи и обработки данных. Примерамитаких кодов является циклический код Грея, который широко используется в АЦПугловых и линейных перемещений. Коды Фибоначчи используются для построениябыстродействующих и помехоустойчивых АЦП.

Основное внимание в курсе уделено кодам для обмена данными иих передачи по каналам связи.

ЦЕЛИ КОДИРОВАНИЯ:

1) Повышение эффективности передачи данных, за счетдостижения максимальной скорости передачи данных.

2) Повышение помехоустойчивости при передаче данных.

В соответствии с этими целями теория кодирования развиваетсяв двух основных направлениях:

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

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

 


3. Способы представления кодов

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

 

3.1 Матричное представление кодов

Используется для представления равномерных n — значныхкодов. Для примитивного (полного и равномерного) кода матрица содержит n — столбцов и 2n — строк, т.е. код использует всесочетания. Для помехоустойчивых (корректирующих, обнаруживающих и исправляющихошибки) матрица содержит n — столбцов (n = k+m, где k-числоинформационных, а m — число проверочных разрядов) и 2k — строк (где 2k — число разрешенных кодовыхкомбинаций). При больших значениях n и k матрица будет слишкомгромоздкой, при этом код записывается в сокращенном виде. Матричноепредставление кодов используется, например, в линейных групповых кодах, кодахХэмминга и т.д.

 

3.2 Представление кодов в виде кодовых деревьев

 

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

Пример кодового дерева для полного кода приведен на рис.1.


/>


                                      1                                          0

                1                        0                                    1                           0

     1          0                  1           0                  1         0                  1               0

 111           110            101          100         011            010         001        000

Рис.1. Дерево для полного двоичного кода при n = 3

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

 

3.3 Представление кодов в виде многочленов

Представление кодов в виде полиномов основано на подобии (изоморфизме)пространства двоичных n — последовательностей и пространства полиномовстепени не выше n — 1.

Код для любой системы счисления с основанием Х можетбыть представлен в виде:

 

G (x) = an-1 xn-1+ an-2xn-2+… + a1 x+ a0 =/>,

где аi — цифры данной системы счисления (вдвоичной 0 и 1);

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

Например: Кодовая комбинация 1010110 может быть представленав виде:

G (x) =1×x6+0×x5+1×x4+0×x3+1×x2+1×x1+0×x0=x6+x4+x2+x=10101

При этом операции над кодами эквивалентны операциям надмногочленами. Представление кодов в виде полиномов используется например, вциклических кодах.

 

3.4 Геометрическое представление кодов

Любая комбинация n — разрядного двоичного кода можетбыть представлена как вершина n — мерного единичного куба, т.е. куба сдлиной ребра равной 1. Для двухэлементного кода (n = 2) кодовыекомбинации располагаются в вершинах квадрата. Для трехэлементного кода

(n = 3) — в вершинах единичного куба (рис.2).

В общем случае n мерный куб имеет 2nвершин,что соответствует набору кодовых комбинаций 2n.

/>

n = 2 n = 3

Рис.2. Геометрическая модель двоичного кода

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


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

1.        Кловский Д.Д. Теория передачи сигналов. -М.: Связь, 1984.

2.        Кудряшов Б.Д. Теория информации. Учебник для вузовИзд-во ПИТЕР, 2008. — 320с.

3.        Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметическогокодирования для источников с большими алфавитами // Проблемы передачиинформации. — 1999. — Т.35, Вып. — С.95 — 108.

4.        Семенюк В.В. Экономное кодирование дискретной информации. — СПб.: СПбГИТМО(ТУ), 2001

5.        Дмитриев В.И. Прикладная теория информации. М.: Высшая школа, 1989.

6.        Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: МАИ, 1992.

7.        Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 2006.

еще рефераты
Еще работы по информатике, программированию