Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство информационных технологий и связи РФ

Кафедра: ПДСиМ

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

Техника передачи дискретных сообщений

Выполнила: студентка 3 курса

факультета АЭС

группы А-45

Караван С.Л.

Проверил: Коновалов П.А.

г. Новосибирск, 2011

Содержание

Введение

Задание на курсовую работу

1. Методы регистрации

1.1 Теоретические основы

1.2 Вывод формулы для вычисления вероятности ошибки при регистрации методом стробирования и вычисление вероятности ошибки для µ, б, у

2. Синхронизация в системах ПДС

2.1 Классификация систем синхронизации

2.2 Поэлементная синхронизация с добавлением и вычитанием импульсов (принцип действия)

2.3 Параметры системы синхронизации с добавлением и вычитанием импульсов

2.4 Расчет параметров системы синхронизации с добавлением и вычитанием импульсов

3. Кодирование в системах ПДС

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

3.2 Эффективное кодирование (код Хаффмена, арифметическое кодирование

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

3.3 Циклические коды.

3.4 Построение кодера и декодера цеклического кода

3.5 Формирование кодовой комбинации циклического кода

4.Системы ПДС с ОС

4.1 Классификация систем с ОС

4.2 Временные диаграммы для систем с обратной связью и ожиданием для неидеального обратного канала

4.3 Расчет параметров системы с ОС и ожиданием

Заключение

Используемая литература

• Ведение
• Техника передачи дискретных сообщений (ПДС) играет все большую роль в жизни человеческого общества. Без нее немыслимо созданий современных автоматизированных систем управлений для различных отраслей народного хозяйства, в том числе и для отрасли «связь». Применение техники ПДС позволяет обеспечить лучшее использование дорогостоящей высокопроизводительной вычислительной техники путем создания вычислительных сетей и сетей передачи данных. Дальнейшее развитие телеграфных сети общего пользования позволяет удовлетворить растущие потребности населения в обмене информацией, а развитие сети абонентского телеграфа и передача данных - потребности промышленных предприятий в оперативной связи.
• Сегодня в нашей стране граждане передают очень большое количество информации. Для передачи информации используются тысячи аппаратур, миллионы километров каналов, соединяющих предприятий связи через автоматические коммутационные станции.
• Большим спросом пользуется метод передачи неподвижных изображений (факсимильная связь) - создана сеть пунктов приема газетных полос, которая является самой разветвленной в мире.
• Практически ни одна организация не может функционировать без факсимильной связи, без нее невозможно создание корпоративных компьютерных сетей, которые значительно увеличивают скорость обмена информацией между подразделениями.
• Внедрение вычислительной техники привело к появлению вида электросвязи - передача данных. техника передача дискретный сообщение
• Техника передачи данных позволяет обеспечить передачу информации (данных) для обработки на ЭВМ и передачу абонентами обработанных на ЭВМ данных. Этот вид электросвязи скоростной и высокое качество передачи информации. Передача сообщений тесно вошла в нашу жизнь, практически каждый компьютер имеет модем, который является самым распространенным устройством ПДС. Практически на каждом шагу мы встречаемся с необходимостью срочно получить оперативную информацию, в осуществлении этого не последнюю роль играют средства ПДС.
• 1. Методы регистрации
• 1.1 Теоретические основы
• Сигнал, поступающий с выхода канала постоянного тока (КПТ), должен быть отождествлен на приемной стороне с «0» или «1». Необходимо также произвести запоминание значащей позиции сигнала данных. Процесс определения и запоминания значащей позиции сигнала данных называется регистрацией. Наиболее распространенными методами регистрации являются метод стробирования и интегральный. Рассмотрим эти методы.
• Метод стробирования. При регистрации методом стробирования вид принимаемого элемента («0» или «1») определяется на основании анализа знака импульса постоянного тока (сигнала на выходе КПТ) в середине единичного интервала. Любое смещение момента регистрации относительно середины единичного интервала приводит к увеличению вероятности неправильной регистрации сигнала.
• Структурная схема устройства, осуществляющего регистрацию методом стробирования, приведена на рис. 1.1.1.
• Рис. 1.1.1
• На рис. 1.1.2. показаны временные диаграммы, поясняющие принцип действия метода стробирования.
• Пусть передается последовательность 10101. На выходе входного устройства имеем импульсы постоянного тока, искаженные по длительности. Ключи открываются одновременно на время поступления стробимпульса. Поступление импульсов стробирования u₃ в моменты, соответствующие серединам единичных интервалов, обеспечивается устройством поэлементной синхронизации. При этом сигнал u₄(u₅) появляется на выходе ключей. В зависимости от этого выходное устройство фиксирует “1” или “0”. Если смещение ЗМ относительно идеального положения не превышает 0,5ф₀, то элемент сигнала регистрируется правильно. Величина, на которую допускается смещение ЗМ, не вызывающее появления ошибки, определяет исправляющую способность приемника, которая обозначается буквой м. В данном случае исправляющая способность (теоретическая) м = 0,5ф₀ или 50%. При регистрации методом стробирования все посылки исправляются по длительности.
• Рис. 1.1.2
• Интегральный метод. Сущность интегрального метода регистрации состоит в том, что во время приема на накопительном элементе происходит накопление энергии посылки в течение времени длительности неискаженной посылки ₀ и решение в виде принятого элемента выносится на основе анализа сигнала U_вых, определяемого выражением:
• где - сигнал на входе регистрирующего устройства (выходе КПТ). Этот сигнал является дискретной функцией непрерывного времени.
• Интегрирование осуществляется на интервале, соответствующем неискаженному элементу. Пусть U_вх(t) принимает на интервале анализа как значение U_вх(t)=0, так и U_вх(t)=1. Тогда решение о приеме «1» должно выносится, если U_вых?0,5. Очевидно, что ошибка при передаче «1» будет в том случае, когда U_вых?0,5.
• Интегральный метод часто реализуется на основе многократного стробирования сигнала U_вх(t) в N точках. Схема, поясняющая принцип действия такого устройства регистрации реализующего данный метод приведена на рис.1.1.3.
• Рис. 1.1.3
• Временные диаграммы, иллюстрирующие данный метод, приведены на рис. 1.1.4. Передается комбинация 1011. С выхода входного устройства элементы сигнала поступают на накопительные элементы НЭ1 или НЭ2, в которых осуществляется интегрирование. Сравнивающее устройство фиксирует “1”, если и “0”, если . Тактовые импульсы ТИ, поступающие через интервал ф_0, определяют границы интегрирования. На рис. 1.1.4 показана ситуация, когда неправильно регистрируется 3-й элемент.
• Рис. 1.1.4
• Поскольку при регистрации методом стробирования посылка регистрируется в середине, то допускается смещение любого значащего момента на величину 0,5ф₀ = м, где м - исправляющая способность приемника (теоретическая). Элемент сигнала регистрируется неправильно в том случае, если левая или правая его граница сместится во внутрь на величину, превышающую исправляющую способность приемника. Вероятности этих событий обозначим соответственно P₁ и P₂. Неправильная регистрация имеет место также и в том случае, если обе границы одновременно сместятся на величину, большую м. Вероятность этого события в предположении независимости смещения определим как P₁P₂. Тогда вероятность ошибки при регистрации методом стробирования определится следующим образом:
• Предполагается, что краевые искажения д подчиняются гауссовскому закону распределения:
• где а - математическое ожидание д, у² - дисперсия д.
• Так как элемент сигнала ограничен с обеих сторон моментами ЗМ1 и ЗМ2, то имеем:
• где W₁(д), W₂(д) - плотность распределения искажений для левого и правого ЗМ соответственно (рис.1.2.2.).
• Очевидно, что
• где
• функция Крампа,
• Определив таким образом P₁ и P₂ нетрудно определить и .
• 1.2 Вывод формулы для вычисления вероятности ошибки при регистрации методом стробирования и вычисление вероятности ошибки для заданных , а, .
• Вычислим вероятность неправильной регистрации, если заданы
• Зная Z, из таблицы значений функции Крампа находим P₁ и P₂:
• P₁ = P₂ = 0,21186;
• Далее, подставляя значения P₁ и P₂ в формулу для , получаем
• .
• 2. Синхронизация в системах ПДС
• 2.1 Классификация систем синхронизации
• Синхронизация есть процесс установления и поддержания определенных временных соотношений между двумя и более процессами. Классификация систем синхронизации приведена на рис.2.1.1.
• Рис. 2.1.1

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

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

Цикловая синхронизация обеспечивает правильное разделение циклов временного объединения элементов на приеме. Обычно задачи цикловой и групповой синхронизаций решаются одними и теми же методами.

К системам синхронизации предъявляются следующие требования:

1. Высокая точность синхронизации

2. Малое время вхождения в синхронизм, как при включении оборудования, так и после перерыва связи

3. Сохранение синхронизации при действии помех и кратковременных перерывах связи

4. Независимость точности синхронизации от статистической структуры, передаваемой последовательности

2.2 Поэлементная синхронизация с добавлением и вычитанием импульсов (принцип действия)

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

Рис. 2.2.1

Задающего генератора ЗГ (Г);

Фазового детектора ФД, в состав которого входит формирователь импульсов фронта (ФИФ);

Делителя частоты ДЧ (Д) с постоянным коэффициентом деления m;

Устройства добавления и вычитания импульсов УДВИ;

Реверсивного счетчика РС емкостью S.

ЗГ вырабатывает колебания с частотой . Фазовый детектор определяет величину расхождения по ЗМ и ТИ генератора. Если частота генератора приемника больше, чем частота генератора передатчика (приемник «спешит»), то на входе схемы появится управляющий сигнал, который, пройдя реверсивный счетчик (усредняющее устройство), поступит на вход УДВИ, которая запретит прохождение одного импульса от ЗГ, в результате чего тактовая последовательность сдвинется на величину Дt в сторону отставания (рис. 2.2.2, в). Если же частота генератора приемника частоты генератора передатчика (приемник «отстает»), то на выходе схемы появится сигнал управления, который укажет УДВИ добавить еще один импульс, в результате чего тактовая последовательность на выходе делителя сдвинется на Дt в сторону опережения (рис 2.2.2, б).

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

Реверсивный счетчик включен в схему для уменьшения влияния краевых искажений, величина которых носит случайный характер.

Он играет роль усредняющего устройства и представляет собой элемент задержки управляющих сигналов не менее, чем на S тактов, где S - емкость счетчика. При поступлении на один из входов подряд S импульсов на выходе РС появится управляющий сигнал.

Если же в процессе синхронизации на левый вход поступит (S - 1) импульс, а затем на правый вход также поступит (S - 1) импульс, то счетчик возвращается в исходное состояние. Включение РС приводит к увеличению времени синхронизации.

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

Рис. 2.2.2

а) - нормальный процесс деления (m = 4);

б) - добавление импульса;

в) - исключение импульса

2.3 Параметры системы синхронизации с добавлением и вычитанием импульсов

1. Шаг коррекции (Дц) - смещение фазы ТИ в долях единичного интервала (ф₀) на выходе делителя частоты (ДЧ) при добавлении или вычитании одного корректирующего импульса.

Рис. 2.3.1 определение шага коррекции

,

где m - коэффициент деления делителя частоты.

2. Интервал времени между двумя подстройками . Минимальный интервал времени между двумя подстройками равен если передается последовательность вида 10101010… и отсутствует усредняющее устройство (реверсивный счетчик), т.е. S = 1. Если есть реверсивный счетчик, то этот интервал равен . В общем случае интервал времени между двумя подстройками определяется как

,

где - среднее число принимаемых подряд элементов одного знака, определяющее период корректирования.

3. Время вхождения в синхронизм (время синхронизации) . Это время зависит от первоначального расхождения по фазе тактовой последовательности, вырабатываемой на приеме, и принимаемой последовательности ЗМ. Рассмотрим случай, когда сдвиг по фазе максимален, и ТИ сдвинуты относительно идеального положения на 0,5 (рис. 2.3.2.).

Рис. 2.3.2

Подстройка производится шагами, при каждом шаге ТИ смещаются на время Дt. Тогда число шагов, необходимое для подстройки, будет равно

Если подстройка осуществляется через интервал , то время, необходимое для вхождения в синхронизм, определится как

Учитывая увеличение интервала между подстройками за счет реверсивного счетчика, окончательно получаем:

,

где

.

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

,

где _.- допустимая величина смещения ТИ в долях единичного интервала.

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

.

Тогда

.

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

5. Погрешность синхронизации. Погрешность синхронизации целесообразно рассматривать как сумму двух погрешностей:

-статической погрешности синхронизации , определяемой нестабильностью задающего генератора и шагом коррекции;

-динамической погрешности _., вызываемой краевыми искажениями единичных элементов:

_..

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

,

где - шаг коррекции;

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

- емкость реверсивного счетчика;

- среднее число принимаемых элементов одного знака, определяющее период корректирования.

Динамическая погрешность , является случайной величиной и подчиняется гауссовому закону с плотностью вероятности

.

Среднеквадратическое значение _. можно рассчитать по следующей формуле:

,

где - среднеквадратическое значение краевых искажений единичных элементов.

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

.

Общее выражение для оценки погрешности синхронизации имеет вид:

.

6. Вероятность срыва синхронизации по элементам Р_сс. - это вероятность того, что фаза синхроимпульсов под действием помех сместится на величину ±0,5. Такой сдвиг фазы нарушает работу устройств синхронизации и приводит к сбою групповой синхронизации. Уменьшить величину Р_сс можно путем увеличения времени усреднения сигналов корректирования, т.е. уменьшить емкость реверсивного счетчика S. Однако время синхронизации будет также расти пропорционально S, а период корректирования уменьшаться. Следовательно, необходимо решать и другую оптимизационную задачу - выбора параметров с учетом конкретных условий передачи для обеспечения минимума.

При проектировании и расчете устройств синхронизации обычно задаются следующие параметры: погрешность синхронизации ; скорость модуляции В; среднеквадратическое значение краевых искажений ; исправляющая способность приемника ; время синхронизации t_c; время поддержания синхронизма t_пс . на основании заданных параметров рассчитываются: частота задающего генератора ; допустимый коэффициент нестабильности генератора k; емкость реверсивного счетчика S; коэффициент деления делителя m.

Коэффициент нестабильности задающего генератора определяется:

.

Емкость реверсивного счетчика S и коэффициент деления делителя определим из системы уравнений (2.3.1) и (2.3.3) относительно S и m:

Частота задающего генератора определяется как .

2.4 Расчет параметров системы синхронизации с добавлением и вычитанием импульсов (Задачи)

2.4.1 Коэффициент нестабильности задающего генератора устройства синхронизации и передатчика k=10^-4. Исправляющая способность приемника µ=52%. Краевые искажения отсутствуют. Постройте зависимость времени нормальной работы (без ошибок) приемника от скорости телеграфирования после выхода из строя устройства синхронизации. Будут ли возникать ошибки, спустя минуту после отказа фазового детектора, если скорость телеграфирования B=9600 Бод? Решение: Рассматривается устройство синхронизации без непосредственного воздействия на частоту генератора, структурная схема которого приведена на рис. 2.4.1.

Рис. 2.4.1 - Структурная схема устройства синхронизации с ДВИ.

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

,

где µ- исправляющая способность приемника,

, т.к. работа приемника происходит без ошибок, а з значит краевые искажения отсутствуют.

Рассчитаем значение для следующих значений скорости телеграфирования В:

В, бод	300	600	1200	2400	4800	9600
с	8,67	4,33	2,17	1,08	0,54	0,27

По полученным значениям построим график зависимости

:

t_пс

Рис. 2.4.2 - Зависимость времени поддержания синхронизма

Из графика видно, что с увеличением скорости телеграфирования время поддержания синхронизма системой уменьшается. Время поддержания синхронизма при скорости телеграфирования B=9600 Бод при расчете получилось =0,27 с.

2.4.2 В системе передачи данных используется устройство синхронизации без непосредственного воздействия на частоту задающего генератора. Скорость модуляции равна B=1152 бод. Шаг коррекции должен быть не более ?ц=0,0533. Определите частоту задающего генератора и число ячеек делителя частоты, если коэффициент деления каждой ячейки равен двум.

Решение: Коэффициент деления делителя m и шаг коррекции ?ц связаны соотношением:

,

.

Коэффициент деления одной ячейки равен двум, следовательно, коэффициент деления самого делителя будет равен 2ⁿ?18,8, т.е. n= log₂18,8 = 4,23. Т.к. число ячеек - целое число, то n=5, тогда коэффициент деления делителя m=2⁵=32.

Зная m, найдем частоту задающего генератора:

.

2.4.3 Рассчитать параметры устройства синхронизации без непосредственного воздействия на частоту задающего генератора со следующими характеристиками: время синхронизации не более 1 с, время поддержания синфазности не менее 10 с, погрешность синхронизации не более , среднеквадратическое значение краевых искажений , исправляющая способность приемника , коэффициент нестабильности генераторов k = 10^-5, скорость модуляции B=820 Бод.

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

Частоту задающего генератора найдем по формуле:

,

коэффициент деления делителя частоты и емкость реверсивного счетчика найдем, решив систему уравнений:

Из второго уравнения выражаем :

.

Подставим это выражение во второе уравнение:

Выразим из полученного выражения :



Теперь рассчитаем :

И найдем частоту задающего генератора

.

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

Решение: Для того, чтоб определить, реализуемо ли устройство синхронизации, обеспечивающее при условиях предыдущей задачи, необходимо рассчитать емкость реверсивного счетчика S:

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

2.4.5 В системе передачи данных использовано устройство синхронизации без непосредственного воздействия на частоту задающего генератора с коэффициентом нестабильности k=10^-4. Коэффициент деления делителя m=12, емкость реверсивного счетчика S=15. Смещение значащих моментов подчинено нормальному закону с нулевым математическим ожиданием и среднеквадратическим отклонением, равным длительности единичного интервала. Рассчитать вероятность ошибки при регистрации элементов методом стробирования без учета и с учетом погрешности синхронизации. Исправляющая способность приемника .

Решение: Вероятность ошибочной регистрации

, где P₁ и P₂-

соответственно вероятности смещения левой и правой границ на величину больше . Если устройство синхронизации работает идеально (е = 0), то,

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

Так как плотности распределения вероятностей и описываются гауссовским законом, то вероятности P₁ и P₂ можно выразить через функцию Крампа:

где

Рассчитаем вероятность ошибочной регистрации без учета и с учетом погрешности синхронизации: Без учета погрешности синхронизации:

Из таблицы значений функции Крампа находим P₁ = P₂ = 0,03852.

С учетом погрешности синхронизации:

Рассчитаем погрешность синхронизации по формуле:



Получим:

По таблице находим P₁ = 0,002318 и P₂=0,22587;

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

3. Кодирование в системах ПДС

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

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

К нему относится метод Хаффмана.

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

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

Корректирующие коды делятся на блочные и непрерывные к блочным относятся коды, в которых каждому символу алфавита соответствует блок (кодовая комбинация) из n (i) элементов, где i - номер сообщения. Если n (i) = n, т.е. длина блока постоянна и не зависит от номера сообщения, то код

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

Корректирующие коды позволяют получить и обнаружить ошибку.

Расстояние Хемминга так же используется в корректирующих кодах.

Расстояние - это минимальное расстояние Хемминга между всеми парами разрешенных комбинаций.

Код Хемминга - групповой (n,k) код, исправляющий одиночные ошибки и обнаруживающий двукратные ошибки.

Циклические коды. Данное название происходит от основного свойства этих кодов: если некоторая кодовая комбинация а₁, а₂, … а_{n - 1}, а_n принадлежит циклическому коду, то комбинация а_n, а₁, а₂, … а_{n - 1}; а_{n - 1}, а_n, а₁ … а_{n - 2}, полученная циклической перестановкой исходной комбинации (циклическим сдвигом), также принадлежит данному коду.

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

Итеративные коды - комбинация двух линейных кодов. Такие коды борются с группирующимися ошибками.

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

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

Линейные коды. Двоичный блочный код является линейным если сумма по модулю 2 двух кодовых слов является также кодовым словом. Линейные коды также называют групповыми.

3.2 Эффективное кодирование

Эффективное кодирование - это процедуры направленные на устранение избыточности.

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

Пусть имеется источник дискретных сообщений, алфавит которого k.

При кодировании сообщений данного источника двоичным, равномерным кодом, потребуется

двоичных элементов на кодирование каждого сообщения.

Если вероятности P(a_i) появления всех сообщений источника равны, то энтропия источника (или среднее количество информации в одном сообщении) максимальна и равна

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

Если при том же объеме алфавита сообщения не равновероятны, то, как известно, энтропия источника будет

.

Если и в этом случае использовать для перевозки сообщения l_р.к. -разрядные кодовые комбинации, то на каждый двоичный элемент кодовой комбинации будет приходиться меньше чем 1 бит.

Появляется избыточность, которая может быть определена по следующей формуле:

,

где D - избыточность.

Если средняя загрузка единичного элемента так мала, встает вопрос, нельзя ли уменьшить среднее количество элементов необходимых для переноса одного сообщения и как наиболее эффективно это сделать?

Для решения этой задачи используются неравномерные коды.

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

Учитывая, что объем информации, содержащейся в сообщении, определяется вероятностью появления

,

можно перефразировать данное высказывание.

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

Таким образом, на одно сообщение будет затрачено в среднем меньшее единичных элементов

,

чем при равномерном.

Если скорость телеграфирования постоянна, то на передачу одного сообщения будет затрачено в среднем меньше времени:

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

Каково же в среднем минимальное количество единичных элементов требуется для передачи сообщений данного источника?

Ответ на этот вопрос дал Шеннон.

Шеннон показал, что

1. Нельзя закодировать сообщение двоичным кодом так, что бы средняя длина кодового слова была численно меньше величины энтропии источника сообщений.

2. Существует способ кодирования, при котором средняя длина кодового слова немногим отличается от энтропии источника

.

Остается выбрать подходящий способ кодирования.

Эффективность применения оптимальных неравномерных кодов может быть оценена:

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

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

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

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

Введем понятие кодового дерева для множества кодовых слов.

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

Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между “0” и “1” в качестве первого символа кодового слова: левая ветвь соответствует “0”, а правая - “1”. Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых слов, левая означает “0”, а правая - “1” и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.

Рис. 3.2.1

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

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

Любой код, кодовые слова которого соответствуют различным концевым вершинам некоторого двоичного кодового дерева, является префиксным, т. е. однозначно декодируемым.

Одним из часто используемых методов эффективного кодирования является так называемый код Хаффмана.

Пусть сообщения входного алфавита A{a₁,a₂,a₃…a_k} имеют соответственно вероятности их появления p₁,p₂,p₃…p_k.

Тогда алгоритм кодирования Хаффмана состоит в следующем:

1. Сообщения располагаются в столбец в порядке убывания вероятности их появления.

2. Два самых маловероятных сообщения объединяем в одно сообщение b, которое имеет вероятность, равную сумме вероятностей сообщений a_k-1, a_k т. е. p_k-1+p_k. В результате получим сообщения a₁,a₂,a₃…a_k-1,b, вероятности которых p₁, p₂, p₃…p_k-2, p_k-1+ p_k.

3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.

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

определить, приписывая правым ветвям объединения символ “1”, а левым - “0”. Впрочем, понятия “правые” и “левые” ветви в данном случае относительны (Рис. 3.2.2).

На основании полученной таблицы можно построить кодовое дерево рисунок 3.2.3:

Рис. 3.2.3

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

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

Еще одним методом кодирования является арифметическое кодирование.

Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т.к. достигается теоретическая граница степени сжатия. Предполагаемая требуемая последовательность символов, при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0,1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке. Поясним работу метода на примере.

Математически процесс описывается следующим образом:

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

1. Границы рабочего интервала d₀ и u₀ изначально равны 0 и 1 соответственно. Длина рабочего интервала у₀=1.

2. Определяем нижнюю границу рабочего интервала (т.е. границы первого закодированного сообщения):

d_i= d_i-1+ Q_i·у_i-1.

И верхнюю границу:

u_i= d_i-1+ Q_i у_i-1, где Q_i

- граница кодируемого сообщения на начальном интервале. А так же определяем длину нового рабочего интервала у_i= u_i - d_i. Далее кодируем все последующие сообщения подобным образом.

3. Определяем середину конечного рабочего интервала

,

где A_n - число архив, u_n, d_n - верхняя и нижняя границы конечного рабочего интервала соответственно.

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

1. Первое закодированное сообщение «лежит» на интервале, в который входит число архив.

2. Последующие числа архивы определяются как:

, где A_j

- новое число архив, A_j-1 - предыдущее число архив, Q_j-1 - нижняя граница декодированного сообщения, P(a_i) - вероятность этого сообщения.

Графически метод арифметического кодирования представлен на рисунке 3.3.1.

Рис. 3.3.1

3.3 Циклические коды

Широкое распространение получил класс линейных кодов которые называются циклическими. Название этих кодов происходит от их основного свойства: если кодовая комбинация a₁, а₂,......, a_n-1, a_n принадлежит циклическому коду, то комбинации a_n, a₁, а₂,........, a_n-1; a_n-1, a_n, a₁, а₂,......., а_n-2 и т.д., полученные циклической перестановкой элементов, также принадлежат этому коду.

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

,

где х-основание системы счисления, a_n-1,...,a₀ - цифры этой системы, то переход от двоичного числа к записи в виде многочлена осуществляется следующим образом:

1101 1х³ +1х²+1x₀=x³+x²+1

KK ЦК описываются полиномами обладающими определенными свойствами. Последние определяются свойствами и операциями той алгебраической системы, к которой принадлежит множество полиномов. Например, в алгебраической системе, которая носит название поля Галуа (GF(x)), действие над коэффициентами полиномов (сложение, вычитание) производится по модулю два. Умножение полиномов должно производиться по модулю некоторого полинома Рr(х). Эти два условия определяют замкнутость указанных операций: их применение не приводит к кодовым комбинациям, длинна которых больше длинны заданного кода n.

Способы формирования циклических кодов.

Найдем алгоритмы построения циклического кода, удовлетворяющего перечисленным выше условиям. Задан полином

,

определяющий исправляющую способность кода, и задан исходный простой код, который требуется преобразовать в корректирующий циклический. Обозначим многочлен, соответствующий комбинации простого кода, Q(x). Возьмем произведение Q(x)хr и разделим его на P(x). В результате получим многочлен G(x) и остаток R(x)/P(x):

Умножим левую и правую части на P(x). В результате получим:

перепишем равенство ( * ) в виде

Левая часть (**) делится без остатка на , значит, без остатка делится и правая часть. Таким образом, мы получили два способа формирования кодовых комбинаций циклического кода:

1. Путем умножения многочлена исходной кодовой комбинации на производящий полином;

2. Путем деления на производящий полином и приписывания к остатка от деления .

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

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

3.4. Формирование кодовой комбинации циклического кода (Задачи)

3.4.1 Записать кодовую комбинацию циклического кода, если задан производящий полином P(х) = x³+x²+1 и кодовая комбинация, поступающая от источника сообщений Q(х) = x³. Нарисовать кодирующее и декодирующее устройство с обнаружением ошибок и "прогнать" через кодирующее устройство исходную кодовую комбинацию с целью формирования проверочных элементов.

Решение:

Степень производящего полинома определяет число проверочных элементов r=4.

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

Сумматор ставится после каждой ячейки, начиная с нулевой (которой нет), но для которой существует соответствующий член полинома. После старшего никогда не ставиться.

Рис. 3.5.1 - Кодер циклического кода

Элементы сформируются на k+r = 4+3 = 7 такте

На вход:1000

такт	вх	1	2	3
1	1	1	0	0
2	0	1	1	0
3	0	1	1	1
4	0	1	0	1
5		1	1	1
6		1	1	0
7		0	1	1

На выходе: 0110001

Рис. 3.5.2 - Декодер циклического кода

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

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

где _. - вероятность неправильного приема единичного элемента;

- длина кодовой комбинации;

_. - кратность исправляемых ошибок;

Кратность исправляемых_. ошибок определяется как

,

где - кодовое расстояние.

Для кода (7,4), заданного в задаче №5, и , т.е. данный код способен исправлять однократные ошибки.

Расчет вероятности неправильного приема без учета погрешности синхронизации: Вероятность ошибки на элемент без учета погрешности синхронизации равна

P_ош =;

Расчет вероятности неправильного приема с учетом погрешности синхронизации:

Вероятность ошибки на элемент с учетом погрешности синхронизации равна

P_ош =;

4. Системы ПДС с ОС

4.1 Классификация систем с ОС

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

В зависимости от назначения ОС различают системы:

с решающей обратной связью (РОС)

информационной обратной связью (ИОС)

с комбинированной обратной связью (КОС)

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

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

с ограниченным числом повторений (КК повторяется не более L раз)

с неограниченным числом повторений (КК повторяется до тех пор, пока приемник или передатчик не примет решение о выдаче этой комбинации потребителю).

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

Системы с ОС являются адаптивными: темп передачи информации по каналам связи автоматически приводится в соответствие с конкретными условиями прохождения сигналов.

Наличие ошибок в каналах ОС приводит к тому, что в системах с РОС возникают специфические потери верности, состоящие в появлении лишних КК - вставок и пропадания КК - выпадений.



Рис. 4.1.1 а - с РОС; б - с ИОС

4.2 Временные диаграммы для систем с обратной связью и ожиданием для неидеального обратного канала

Рис. 4.2.1. Временная диаграмма работы системы с РОС-ОЖ

4.3 Расчет параметров систем с ОС и ожиданием

4.3.1 Построить временные диаграммы для системы с РОС-ОЖ (ошибки в канале независимы). В канал передаются кодовые комбинации 1,2,3,4,5,6. Искажена 1 кодовая комбинация. На седьмой кодовой комбинации Да > Нет (искажение сигнала с подтверждением).

Решение: Решение данной задачи приведено на рис. 4.2.1.

4.3.2 Рассчитать скорость передачи информации для системы РОС-ОЖ. Ошибки в канале независимы P_ош = 11·10^-4. Построить графики зависимости R(R1,R2,R3) от длины блока. Найти оптимальную длину блока. Если время ожидания t_ож = 0,6· t_бл (при k=8). Блок, передаваемый в канал имеет значения: = 8,16,24,32,40,48,56. Число проверочных элементов r =5. Длина блока в канале определяется по формуле

n=k_i + r.

Решение: Скорость передачи информации определяется по формуле

R = R1•R2•R3,

где R1 - потери скорости заcчет введения избыточности;

R2 - потери скорости, обусловленные ожиданием;

R3 - потери, обусловленные повторными передачами.

где: n - общее число элементов в кодовой комбинации;

k - блок, передаваемый в канал, n = k_i + r;

t_ож - время ожидания;

n·ф₀=t_бл - длина блока;

P_oo - вероятность обнаружения ошибки.

Т.к. ;

Рассчитаем значения R1, R2, R3 и R в зависимости от длины:

k	8	16	24	32	40	48	56
n	13	21	29	37	45	53	61
R1	0,615	0,762	0,828	0,865	0,889	0,906	0,918
R2	0,625	0,729	0,788	0,826	0,852	0,872	0,887
R3	0,986	0,977	0,969	0,960	0,952	0,943	0,935
R	0,379	0,543	0,632	0,686	0,721	0,745	0,761

Построим графики зависимости

Рис. 4.3.2

Оптимальная длина блока (на рассматриваемом диапазоне = 8,16,24,32,40,48,56) n=101 элементов, так как при этом достигается максимальная скорость передачи информации.

4.3.3 Определить вероятность неправильного приема в системе с РОС-ОЖ в зависимости от длины блока и построить график. Ошибки в канале считать независимыми. Вероятность ошибки на элемент P_ош = 11·10^-4.

Решение: При работе системы ПДС с РОС-ОЖ возможны следующие состояния (рис. 4.3.3).

Вероятность неправильного приема в системе с РОС-ОЖ определится следующим образом:

Рис. 4.3.2

Рассчитаем значение вероятности неправильного приема для разных значений n.

n=13

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

n=21

n=29

n=37

n=45

n=53

n=61

По полученным результатам построим график (рис. 4.3.3).

Рис. 4.3.3

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

Заключение

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

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

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

1. Шувалов В.П. Передача дискретных сообщений : М. -«Радио и связь», 2010, с.461.

2. Конспект лекций.

Размещено на Allbest.ru