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

Федеральное агентство связи Сибирский Государственный Университет Телекоммуникаций и информатики ГОУ ВПО СибГУТИ Курсовая работа По предмету «Основы построения телекоммуникационных систем и сетей»

Выполнила: ст. гр. ЗБ-82

Макаричева Н.Н.

Вариант 33

Проверил: Мелентьев О.Г.

Новосибирск 2010

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

1.1 Структурная схема системы передачи дискретных сообщений и назначение основных блоков схемы

1.2 Определение скорости передачи информации для дискретного и расширенного дискретного каналов

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

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

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

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

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

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

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

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

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

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

4. Системы ПДС с обратной связью

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

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

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

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

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

1.1 Структурная схема системы передачи дискретных сообщений и назначение основных блоков схемы

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

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

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

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

Каналы.

Непрерывный канал — это канал связи предназначенный для передачи непрерывных (аналоговых) сигналов. Например, абонентская телефонная линия, канал ТЧ.

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

Расширенный дискретный канал. Дискретный канал в совокупности с кодером и декодером канала (УЗО) называется расширенным дискретным каналом (РДК).

Применительно к дискретному каналу, рассматривается передача единичных элементов, принимающих значение «0» или «1». Алфавит «источника», работающего на дискретный канал, можно считать равным 2. Применительно к расширенному дискретному каналу рассматривается передача кодовых комбинаций длиной n элементов. Следовательно, алфавит «источника», работающего на расширенный дискретный канал, можно считать равным — отсюда и название «расширенный» .

В технике передачи данных РДК называют каналом передачи данных.

Полунепрерывный канал (дискретный канал непрерывного времени). В системе ПДС иногда выделяют дискретный канал непрерывного времени.

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

1.2 Определение скорости передачи информации для дискретного и расширенного дискретного каналов

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

.

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

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

бит/с.

На основании формулы имеем

или ,

где H(x) производительность источника;

H(x/y) ненадёжность «канала (потери) в единицу времени;

H(y) энтропия выходного сообщения в единицу времени;

H(y/x)=H'(n) -энтропия помех (шума) в единицу времени.

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

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

В канале без помех C=max H(x), так как H(x/y)=0. При использовании равномерного кода с основанием k, состоящего из n элементов длительностью _э, в канале без помех

при k=2

бит/c.

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

1-ая теорема (для канала связи без помех):

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

К.Шеннон предложил и метод такого кодирования, который получил название статистического или оптимального кодирования. В дальнейшем идея такого кодирования была развита в работах Фано и Хаффмена и в настоящее время широко используется на практике для «cжатия сообщений».

2-ая теорема (для каналов связи с помехами):

Если пропускная способность канала равна C, а производительность источника H'(x)<C, то путём соответствующего кодирования можно передавать информацию по каналу связи со скоростью, сколь угодно к C и с вероятностью ошибки, сколь угодно близкой к нулю. Если же H'(x)>C, то можно закодировать источник таким образом, что ненадёжность будет меньше, чем H'(x) —C+, где . — сколь угодно малая величина.

Не существует способа кодирования, обеспечивающего ненадёжность, меньшую, чем H'(x) —C.

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

Очевидно, что p_э 0, когда n_э, и следовательно, имеет место «обмен» верности передачи на скорость и задержку передачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Интервал времени между двумя подстройками. Минимальный интервал времени между двумя подстройками равен ф₀, если передается последовательность вида 10 101 010… и отсутствует усредняющее устройство (реверсивный счетчик), т. е. S = 1. Если есть реверсивный счетчик, то этот интервал равен Sф₀. В общем случае интервал времени между двумя подстройками определяется как, где — среднее число принимаемых подряд элементов одного знака, определяющее период корректирования.

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

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

.

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

где .

Для случая передачи текста (= 3) время синхронизации равно

.

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

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

.

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

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

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

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

е = е_ст.+ е_дин..

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

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

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

.

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

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

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

.

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

.

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

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

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

k ? (м — е)/(2Bt_п.с).

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

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

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

Задача 1.

Коэффициент нестабильности задающего генератора устройства синхронизации K = 10^-6. Исправляющая способность приемника м = 40%. Краевые искажения отсутствуют. Постройте зависимость времени нормальной работы (без ошибок) приемника от скорости телеграфирования после выхода из строя фазового детектора устройства синхронизации. Будут ли возникать ошибки, спустя минуту после отказа фазового детектора, если скорость телеграфирования В = 9600 Бод?

Решение.

Время поддержания синхронизма определяется следующим образом:

;

— время в течении которого фаза синхроимпульсов не выйдет за допустимые пределы при прекращении работы УС.

Так как краевые искажения отсутствуют, то е_доп==0.4

Зависимость t_п.с от скорости передачи:

График зависимости t_п.с от скорости передачи

T_п.с =20,83 < 1 минуты, значит спустя минуту после выхода из строя ФД в УС будут возникать ошибки.

Задача 2.

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

В = 1000 + 10N; Дц = 0,01 + 0,003N,

где N — номер варианта.

N = 9;

В = 1000 + 10•9 = 1090 Бод;

Дц = 0,01 + 0,003•9 = 0,037.

Решение.

Коэффициент деления делителя:

m связан с числом ячеек делителя n следующим равенством:

m=2ⁿ

Таким образом, количество ячеек делителя:

n=log₂m=log₂27,03=4,76

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

m=2ⁿ=2⁵=32

Частота задающего генератора:

f_з.г.=m*B=32*1090=34 880 Гц.

Задача 3.

Рассчитать параметры устройства синхронизации без непосредственного воздействия на частоту задающего генератора со следующими характеристиками: время синхронизации не более 1 c, время поддержания синфазности не менее 10 c, погрешность синхронизации не более 10% единичного интервала ф₀, среднеквадратическое значение краевых искажений равно 10%ф₀, исправляющая способность м = 45%, коэффициент нестабильности генераторов k = 10^-6. Скорость модуляции В = 600 + 10N, где N — номер варианта. Будет ли реализуемо устройство синхронизации без непосредственного воздействия на частоту задающего генератора, обеспечивающее погрешность синхронизации е = 0,5N% единичного интервала при данных условиях.

е = 0,5*9=4,5%

B = 600+10*9 = 690 Бод.

Решение.

Необходимо рассчитать частоту задающего генератора f_з.г., коэффициент деления делителя m, емкость реверсивного счетчика S.

S и m найдем из следующих равенств:

где t_с — время синхронизации;

где е — погрешность синхронизации.

Из уравнения (1) выразим m и подставим в уравнение (2) и выразим S:

Коэффициент деления делителя:

Частота задающего генератора:

f_з.г. = m*B=15*690=10 350 Гц.

Для того чтобы определить возможность реализации данного устройства, рассчитаем емкость счетчика при е =4,5%.

Данное устройство синхронизации реализуемо.

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

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

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

Эффективное кодирование — это процедуры направленные на устранение избыточности. К нему относится метод Хаффмана, арифметическое кодирование, метод Шеннона-Фано, равномерное по выходу кодирование.

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

Корректирующее кодирование.

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

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

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

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

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

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

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

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

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

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

Если требуется закодировать сообщение, записанное с помощью букв некоторого алфавита А={a_1.. a_k}, содержащего К букв; т. е. указать правило, которое сопоставляет каждой букве алфавита последовательность из символов «0» и «1». Выбранный код, во-первых, должен обеспечить возможность однозначного декодирования, т. е. позволить по принятой последовательности символов «0» и «1» однозначно восстановить переданное сообщение (букву). Во-вторых, на передачу сообщения в среднем должно быть затрачено минимальное число «0» и «1», что позволит передать за единицу времени максимальное число сообщений.

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

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

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

Метод Хаффмена.

Если имеется дискретный источник, объёмом алфавита К и заданны вероятности А{a_1.. a_k}, P (a₁)… P (a_k).

Алгоритм:

1)сообщения сортируются в порядке убывания вероятностей

2)два самых маловероятных сообщения объединяются Р= ;

3)шаги (1) и (2) повторяются до получения единственного сообщения с Р=1;

4)строится дерево и проставляются комбинации.

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

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

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

Эти свойства используются при построении кодов, кодирующих и декодирующих устройств, а также при обнаружении и исправлении ошибок.

Представление кодовой комбинации в виде многочлена.

Описание циклических кодов и их построение удобно проводить с помощью многочленов (или полиномов).

В теории циклических кодов кодовые комбинации обычно представляются в виде полинома. Так, n-элементную кодовую комбинацию можно описать полиномом (n-1) степени, в виде

где a_i={0,1}, причем a_i=0 соответствуют нулевым элементам комбинации, а a_i= 1 — ненулевым.

Запишем полиномы для конкретных 4-элементных комбинаций:

.

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

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

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

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

.

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

. (*)

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

. (**)

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

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

2. Путем деления Q(x)х^r на производящий полином P(x) и приписывания к Q(x)х^r остатка от деления R(x).

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

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

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

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

— информационную группу из k кодовых элементов, сформированную старшим разрядом справа, сдвинуть слева направо на r элементов;

— представленный таким образом полином G (x)*x^r следует разделить на образующий полином P (x) степени r и определить остаток от деления R (x), имеющий степень не более r-1 ;

— двоичное число, представляющее полином R (x) и состоящее из r элементов, записать за сдвинутой вперед информационной группой, состоящей из k элементов. Записать старшим разрядом справа.

Приведем пример построения кодера для производящего полинома Р (х) = х³+х²+1 ;

входная последовательность А (х)=x³+x²+1:

Схема кодирующего устройства (рис.) содержит: регистр задержки Р3 обеспечивающий сдвиг информационной группы на три такта: формирователь проверочной группы, включающий регистры сдвига и сумматоры по модулю два в цепях обратной связи. В схеме имеются также два ключа К1 и К2, обеспечивающие необходимую последовательность работы схемы. В положении, когда К1 замкнут, а К2 разомкнут, информационная часть кода подается на вход схемы, т. е. в первую ячейку регистра задержки и через S1 в первую ячейку регистра сдвига. По окончании трех тактов старший разряд информационной группы записывается в последние ячейки обоих регистров. Во время четвертого такта информационная группа начинает поступать на выходы кодера. С этого момента ключ К1 размыкается, а ключ К2 замыкается. Начиная с четвертого такта формируется проверочная группа. После седьмого такта К2 размыкается, К1 замыкается. Этого момента формирователь проверочной группы работает как обычный регистр сдвига, «выталкивая» на выход кодера записанные в ячейках регистра проверочные разряды. Одновременно в регистры начинают поступать новые информационные разряды.

Задача 1.

Осуществить кодирование сообщения алфавита, используя двоичный код Хаффмена. Определить значения. Рассчитать значения .

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

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». Впрочем, понятия «правые» и «левые» ветви в данном случае относительны.

В двух последних столбцах рисунка приведено число элементов N_эi в кодовой комбинации и величина произведения p(а_i)N_эi, а представляет собой число элементов, приходящееся на одну комбинацию, т. е. в данном случае На основании полученной таблицы можно построить кодовое дерево:

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

p (а₁)=p (а₂)=…=p (а_i)=1/k.

(т.е. максимальная энтропия равна логарифму от объёма алфавита).

Эффективность оценивают ОНК с помощью коэффициента статистического сжатия

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

Кроме того, используют коэффициент относительной эффективности

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

Задача 2.

Записать кодовую комбинацию циклического кода для случая, когда производящий полином имеет вид Р₄(х) = х⁴ +х+1. Нарисовать кодирующее и декодирующее устройство с обнаружением ошибок и «прогнать» через кодирующее устройство исходную кодовую комбинацию с целью формирования проверочных элементов. Кодовая комбинация, поступающая от источника сообщений, имеет K = 4 элементов и записывается в двоичном виде как число, соответствующее (N+3)=9+3=12.

Решение.

Кодовая комбинация:

Q (x) = 12₁₀ = 1100₂

Q (x)*x⁴ = 11 000 000

P₄(x) = 10 011

Разделим Q (x)*x⁴ на образующий полином:

11 000 000|10 011

10 011 |1101

10 011

10 011

Разрешенную кодовую комбинацию получим прибавлением остатка к Q (x)* x⁴:

0111

Разрешенная кодовая комбинация: 11 000 111.

Кодирующее устройство:

Прогоним через него кодовую комбинацию 1100.

Формирование проверочных элементов.

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

Декодирующее устройство с обнаружением ошибок:

Суть работы данного декодера заключается в следующем:

Когда возникает однократная ошибка (а именно ее декодер может исправить), после деления на P (x) на дешифратор поступает синдром, на который он реагирует посылкой '1' на сумматор по модулю 2 и на следующем такте происходит исправление ошибки.

Задача 3.

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

Решение.

Вероятность неправильного приема кодовой комбинации определяется следующим образом:

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

n =8 — длина кодовой комбинации;

t_и.о. =3 — кратность исправляемых ошибок;

.

Рассчитаем вероятность неправильного приема Вероятность ошибки на элемент равна р_ош.= (9/2) =0,0045;

4. Системы ПДС с обратной связью

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

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

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

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

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

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

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

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

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

Системы ОС:

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

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

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

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

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

Временная диаграмма работы системы с POC-ОЖ. Д — сигнал подтверждения (да), Н-сигнал переспроса (нет). Источник сигнала ИС выдает КК сообщения передатчику прямого канала Пкпер за время t_бл. Приемник прямого канала ПКпр принимает сигнал через время распространения t_р. Через время ожидания t_oж передатчик обратного канала ПКпер формирует сигнал «подтверждение», который подтверждает в ОКпр и информация поступает к потребителю ПС без искажений. Следующая КК выдается источником сообщений через время ожидания ответа подтверждения по обратному каналу.

t_ож=t_р+t_ан+t_ос+t_р+t_рOC+t_аОС,

где t_ос — длительность сигнала обратной связи (1 да, 1 нет).

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

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

Заключение

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

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

2. Кунегин С. В. Системы передачи информации. Курс лекций. — М., 1997 — 317 с.

3. Мелентьев О. Г. Курс лекций.