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

2) возможность адаптивного изменения модели

3) высокая скорость работы

Пусть имеется алфавит из 3 сообщений:

а₁ > Р(а₁)=0,5; а₂ > Р(а₂)=0,2; а₃ > Р(а₃)=0,3. .

Допустим, кодируемый блок а₁ а₃ а₂ (рис. 13)

Разбиваем единичный отрезок на отрезки, равные сообщениям.

Шаг 1

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

В общем виде:

нижняя граница ,

где j - номер сообщение в кодируемом блоке,

i - номер сообщение в исходном алфавите,

д - ширина предыдущего участка;

верхняя граница ,

ширина участка .

Шаг 2 Выбираем участок, соответствующий а₃. Разбиваем его пропорционально. Кодируем а_2. Находим нижнюю и верхнюю границы, ширину а_2.

Получаем число-архив: .

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



Рис.13.

Недостатки метода Хаффмана:

1. Сложно реализуется адаптация;

2. Длины кодовых комбинаций выражаются только целыми числами (минимальная длина - 1 элемент).

Плюсы арифметического кодирования:

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

2. Возможность адаптивного изменения модели или вероятностей.

3. Высокая скорость работы.

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х^n-1+a_n-2x^n-2+...+ а₀х⁰, где х-основание системы счисления, a_n-1,...,a₀ - цифры этой системы, то переход от двоичного числа к записи в виде многочлена осуществляется следующим образом: 11011 1x⁴ + 1х³ +0х²+1x¹ +1x⁰=x⁴+x³+x+1

Отсюда видно, что кодовая комбинация длиной п (п=5) описывается многочленом степени п--1. Однако запись кодовой комбинации в виде многочлена не всегда определяет длину кодовой комбинации п. Например, при п=5 многочлену х²+1 соответствует кодовая комбинация 00101. Поэтому при переходе к записи в виде кодовой комбинации необходимо дописывать нулевые старшие разряды.

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

В циклических кодах разрешенными кодовыми комбинациями являются те, которые имеют нулевой вычет по модулю P_v(x), т. е. делятся на образующий полином без остатка. Из всех возможных полиномов степени п (2^п) только 2^к полиномов (к = п--r ) имеют нулевой вычет по модулю Р_г(х). Они и образуют множество разрешенных кодовых комбинаций циклического кода.

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

Обнаружение ошибок в циклическом коде производится делением принятой кодовой комбинации на кодовую комбинацию образующего полинома (вид его должен быть известен на приеме). Остаток от деления R(x) играет роль синдрома. Если R(x) Ф0, то считается, что произошли ошибки. Если R(x)=0, то комбинация принята правильно.

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

Пусть задан полином P(x)=a_r-1x^r+a_r-2 x^r-1 +...+1, определяющий исправляющую способность кода, и задан исходный простой код, который требуется преобразовать в корректирующий циклический.

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

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

Q(x) * х^r = G(x) * Р(х) + R(x) => G(x) * Р(х) = Q(x) * x^r + R(x)

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

1-Исходный позиционный полином умножают на образующий полином. Данный способ приводит к получению неразделимого кода.

2-Исходный полином умножают на х^г, затем путем деления на Р(х) получают остаток R(x), который необходимо прибавить к Q(x)x^r. Данный способ позволяет получить разделимый код, в котором исходная кодовая комбинация является одной из разрешенных.

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

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

Правило формирования проверочной группы (ФПГ):

Число ячеек памяти равно степени образующего полинома.

2. Число сумматоров на единицу меньше веса образующего полинома.

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

В циклических кодах формирование проверочной группы элементов кодовой комбинации происходит делением полинома Q(x)x^r на образующий полином Рг(х). Так как операция деления в двоичном коде состоит из операций сдвига и сложения по модулю 2, то схемы кодирования содержат типовые элементы двоичной логики. Деление осуществляется схемами, которые называются регистрами с обратными логическими связями, или многократными линейными фильтрами. Принцип построения такого устройства рассмотрим на примере кода (9.5) с образующим полиномом Р(х)=х⁴+х+1. Пусть кодируется группа, информационный полином которой имеет вид Q(x)= x⁴+ х²+ х+ 1. Поскольку операция умножения на х^r означает добавление к соответствующей кодовой комбинации r нулей, то никакого специального устройства не требуется, а сдвиг на г=4 разряда осуществляется обычным регистром задержки. В данном примере регистр задержки имеет четыре ячейки. Деление производится в многотактном фильтре. Элементы информационной группы подаются на вход первой ячейки регистра, начиная со старшего разряда. Через четыре такта элемент старшего разряда появится на выходе регистра. С пятым тактом выходная ячейка будет свободна от поступления элементов информационной группы и в регистр вводится группа проверочных элементов, представляющая остаток от деления R(x).

Формирователь проверочной группы представляет собой сдвигающий регистр с обратными связями между ячейками. Эти связи реализуются через сумматоры по модулю 2. Указанная схема выполняет деление Q(x)x^r на Рг(х). Делимое в виде кодовой группы, представляющей полиномом Q(x)x^r, подаётся на вход сдвигающего регистра, а полином Рг(х) вводится в регистр в виде соответствующей подобранной структуры обратных связей через сумматоры. Проверочная группа элементов последовательно формируется на выходе регистра.

Число ячеек сдвигающего регистра выбирается равным степени образующего полинома, а число сумматоров по модулю 2 на единицу меньше его веса. В рассматриваемом примере вес полинома =3, следовательно, должно быть два сумматора.

Рис.3.1. Пример кодера циклического кода

В схеме РЗ - регистр задержки, обеспечивающий сдвиг информационной группы на четыре такта; ФПГ (формирователь проверочной группы) включает в себя регистры сдвига и сумматоры по модулю 2 в цепях обратной связи. В схеме имеются также два ключа К1 и К2, обеспечивающие необходимую последовательность работы схемы.. Исходное положение ключей: К1 - к ФПГ, К2 - разомкнут.

Принцип работы:

Первые 4 такта идёт одновременное заполнение регистра задержки и ФПГ. После 4-го такта ключи меняют своё положение. Следующие 5 тактов информационные разряды покидают кодер, одновременно с этим в ФПГ идёт процесс деления на образующий полином. После 9-го такта ключи вновь меняют своё положение. Вслед за информационными уходят проверочные разряды, одновременно с этим идёт заполнение ячеек регистров информационными разрядами следующей информационной комбинацией.

Другой вариант кодера для данного кода:

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

Рис.3.2.Пример другой схемы кодера циклического кода (9,5)

Ячейки в начале работы должны быть обнулены. Исходное положение ключей: К1 соединяет вход с выходом.

Принцип работы:

Первые 5 тактов информационные разряды уходят на выход, тем временем в ячейках кодера формируются проверочные процессы. После 5-го такта ключи меняют своё положение и вслед за информационными кодер покидают проверочные разряды.



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

Рис.3.3.Декодер с обнаружением ошибок.

Если информация пришла без ошибки то на выходе схемы или будет 0, если же на выходе будет 1, то произошла ошибка. Содержимое ячеек обнуляется, и переспрашивается.

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

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

Запишем комбинацию в виде полинома:

Далее действуем по алгоритму, описанному в п. 3.3.

1.

2. Делим на образующий полином.

3. Полученный остаток прибавляем к : , что в двоичном виде соответствует комбинации 1001110.

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

Рис 3.2 Схема кодера.

Таблица состояний кодера.

Такт	Регистр	ФПГ	выход
	1	2	3	1	2	3
1	0	1		1
2	1	0	1	0	1
3	0	1	0	1	0	1
4		0	1	1	0	0	1
5			0	0	1	0	01
6				0	0	1	101
7				1	1	0	0101

В начальный момент времени ключ K1 вниз, ключ K2 разомкнут. Три такта идёт заполнение обеих регистров. После третьего такта ключи меняют своё положение, информационные элементы уходят в канал, а в ФПГ идёт деление на образующий полином. На 7 такте деление закончилось, ключи меняют своё положение. После 7 такта проверочные символы уходят в канал, а в это время можно начинать передавать следующую информационную комбинацию.

Процесс декодирования аналогичен процессу кодирования. Схема декодера.

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

Рис 3.3 Схема декодера.

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

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

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

,

где,

- вероятность безошибочного приёма блока;

- вероятность приёма блока с одной ошибкой;

и найдём, используя схему Бернулли:

,

,

где и - число сочетаний из 7 по 1 и из 7 по 0, соответственно.

Из курса теории вероятности нам известно, что: , а .

Подставив и в , и упростив, получаем формулу для определения вероятности неправильного приёма кодовой комбинации:

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

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

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

Ответ: ;

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

4.1 Классификация в системах ПДС с ОС

В зависимости от назначения ОС различают системы: с решающей обратной связью (РОС), с информационной обратной связь (ИОС), с комбинированной обратной связью(КОС).

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

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

На данной схеме ПК_пер. - передатчик прямого канала; ПК_пр - приемник прямого канала; ОК_пр - приемник обратного канала; ОК_пер - передатчик обратного канала; РУ - решающее устройство, ИС - источник сообщения, ПС - получатель собжения.

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



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

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

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

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

4.2 Временные диаграммы для систем с ОС и ожиданием для не идеального обратного канала

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

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

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

,

где - длительность сигнала обратной связи.

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

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

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



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

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

Рассчитать скорость передачи информации для системы РОС-ОЖ. Ошибки в канале не зависимы P_ош=8.3*10^-3. Построить графики зависимости R(R₁,R₂,R₃) от длины блока. Найти оптимальную длину блока. Если время ожидания t_ош=0,6t_бл (при к=8). Блок передаваемый в канал имеет значения: к=8,16,24,32,40,48,56. Число проверочных элементов: r=4. Длина блока в канале определяется по формуле n=k_i+r.

Исходные данные:

r=4

Рассчитать скорость передачи информации для системы РОС-ОЖ. Построить графики зависимости R(R₁,R₂,R₃) длинны блока.

Скорость передачи информации для системы РОС-ОЖ определятся тремя составляющими:

где - число информационных элементов, - число проверочных элементов.

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

,

где - время ожидания, - длительность импульса, при чем

Данный параметр характеризует потери скорости за счет времени ожидания.

Для нашего случая :

, следовательно расчетная формула примет вид:

Последний коэффициент:

, где - вероятность обнаружения ошибки, - вероятность ошибки на элемент, - длинна кодовой комбинации.

Величина характеризует потери скорости за счет переспросов.

Для нашего случая будем иметь:

Общий коэффициент потери скорости будем рассчитывать по формуле:

.

Для удобства предоставления результатов, запишем их в виде таблицы:

k	8	16	24	32	40	48	56
n	12	20	28	36	44	52	60
R1	0,667	0,8	0,857	0,889	0,909	0,923	0,933
R2	0,625	0,735	0,795	0,833	0,859	0,878	0,892
R3	0,908	0,851	0,799	0,749	0,702	0,659	0,617
R	0,378	0,5	0,544	0,554	0,548	0,534	0,513

Рис.4,5 График зависимости коэффициентов скорости передачи от длинны блока.

Таким образом мы видим что при малой длине блока и большой скорость передачи убывает, это связано:

1) Для обеспечения одной и той же обнаруживающей способности кода с большей длинной блока, требуется относительно меньшее число проверочных разрядов;

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

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

Из графика можно заметить, что наибольшее значение R=0.713 будет при длине блока n= 72, следовательно, данная длина блока является оптимальной для заданного условия.

Определить вероятность неправильного приёма в системе с РОС-ОЖ в зависимости от длины блока и построить график. Ошибки в канале независимы. Вероятность ошибки на элемент .

Решение.

Рассмотрим граф возможных состояний системы РОС-ОЖ, который представлен на рисунке 4.6.

Рис. 4.6. Граф возможных состояний системы с РОС-ОЖ.

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

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

.

Вероятность не обнаружить ошибку можно найти как:

.

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

.

Подставляя в , получим:

;

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

С использованием этой формулы, и данных таблицы 4 легко посчитать вероятность неправильного приёма. Сведём полученные результаты в таблицу 5.

Таблица Результаты расчёта вероятности неправильного комбинации приёма в системе РОС-ОЖ

n	12	20	28	36	44	52	60
	0,00349	0,00533	0,00893	0,01097	0,012819	0,016236	0,003498

По данным таблицы строим график зависимости вероятности неправильного приёма от длины блока. График представлен на рисунке 26.



Рис. 4.7. зависимость вероятности неправильного приёма от длины блока в системе с ГРОС ОЖ.

Заключение

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

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

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

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

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

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