Проектирование системы защиты от ошибок канального уровня

Постановка задачи проектирования СЗО

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

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

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

скоростью передачи;

вероятностью ошибки при получении сообщения источника не более Pош. доп;

вероятностью потери (выпадения) сообщения не более Рвып. доп;

вероятностью выдачи дубликата (вставки сообщения) не более Рвст. доп;

вероятностью стирания сообщения не более Рст. доп;

задержкой сообщения не более з.доп.

Исходные данные для проектирования Рис. 1

Характеристики СЗО

На вход СЗО поступают сообщения в виде двоичных последовательностей длины L=37 бит (разрядов) со скоростью M=12,5 сообщений в секунду;

Допустимая вероятность ошибки в сообщении Рош. доп = 5*10−9 ;

Допустимая вероятность выпадения сообщения Рвып. доп = 10−6;

Допустимая вероятность вставки сообщения Рвст. доп = 10−7;

Допустимая вероятность стирания сообщения Рст. доп = 10−9 ;

Допустимое время задержки сообщенияз. доп= 1,5 с;

Оценка сложности проектируемого СЗО производится по сложности технической реализации кодера и декодера, алгоритма обработки сигналов обратной связи (ОС) и объема накопителей на передаче и приеме.

Характеристики дискретного канала прямого направления (ДКпр):

Максимальная скорость передачи по каналу В = 600 Бод;

Модель ошибок в ДК задается распределением вероятности Pn (1) возникновения хотя бы одной ошибки на длине n последовательности двоичных символов в зависимости от nи распределением вероятности Pn (t) возникновения ошибок кратности t и более на длине n последовательности символов в зависимости от t:

П — произведение значений функции при i, изменяющимся от 2 до t.

pe — вероятность ошибки в двоичном символе, pe = 7*10−4,

— коэффициент группирования ошибок, = 0,5;

Время распространения в дискретном канале tр = 10 мс.

Характеристики дискретного канала обратного направления (ДКобр):

Скорость передачи В1 = 100 Бод;

Модель ошибок в дискретном канале обратного направления (обратной связи): pe — вероятность ошибки в двоичном символе, pe = 10−3, — коэффициент группирования ошибок, = 0,5;

Время распространения в дискретном канале обратной связи tр' = 70 мс.

Выбор корректирующего кода в системе с РОС

Согласно исходным данным для проектирования, приведенным в пункте 1, построим зависимость Wн = f (n). Она проиллюстрирована на рис. 1. Там же показано значение Wдоп, вычисленное по формуле

Wдоп = (B-Bист) / B, где

Bист = L*M, бит/с — скорость выдачи информации источником Рис. 2 — Зависимость необходимой избыточности от длины кода Как видно на рис. 1, nmin = 89.

Длина сообщений L = 37, найдем из таблицы подходящий циклический код (127, 106). У этого кода n=127, а k=106. То есть n>nmin, но k на 32 единицы больше требуемого значения. Так как желательно иметь код, длина информационной последовательности которого кратна длине сообщения источника L = 37, укоротим выбранный код на 32 разряда. Получим код (95, 74). Этот код обладает избыточностью Wk = 0,221, что удовлетворяет соотношению WнWkWдоп. Найдем образующий полином выбранного кода g (х) и кодовое расстояние d. Из таблицы циклических кодов, приведенной в приложении, имеем fj (х)= 235+217+211. Соответствующий образующий полином будет

g (x)=x21+x18+x17+x15+x14+x12+x11+x8+x7+x6+x5+x1+1, d=7.

Уточним значение вероятности не обнаруживаемой кодом ошибки.

Рис. 3

Pн.о. = 1,038*10−9, что меньше значения Pош.доп., то есть Pн.о.

ш. доп.

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

= 6,8*10−3,

тогда вероятность правильного приема будет равна:

Q = 1- = 0,9932

Выбор алгоритма работы проектируемой системы

Так как рассчитанное значение Wдоп< 0.7, следует проектировать систему РОС с непрерывной передачей и блокировкой приемника. Функциональная схема такой системы показана на рис. 2.

Рис. 4 — Функциональная схема системы РОСнпбл

Расчет внешних характеристик Рвст, и Рвып

Расчет вероятностей Рвып и Рвст Вероятности выпадений и вставок зависят в первую очередь от вероятностей искажения сигналов ОС (р0 и р?).В системе со специальным обратным каналом в качестве сигналов ОС могут быть выбраны две двоичные последовательности длины m бит с максимально возможным расстоянием Хемминга t=m.

Рассмотрим методику расчета вероятностей р0 и р? для различных алгоритмов принятия решения приемником сигналов обратной связи (ПРМ СОС).

Когда прием сигналов ОС (ПРМ СОС на станции А) осуществляется в соответствии с принципом максимального правдоподобия (мажоритарный прием), сигнал «подтверждение» будет воспринят как «запрос» и наоборот сигнал «запрос» воспринимается как «подтверждение», если в последовательности, передаваемой по обратному каналу ДКобр, исказится больше половины бит. Например, передавалось «подтверждение» — 000, а приемник ПРМ СОС регистрирует — 101 и интерпретирует принятую последовательность, как «запрос». Тогда вероятность искажения сигнала «подтверждение» (р0) равна вероятности искажения сигнала «запрос» (р?) и равна вероятности того, что на длине последовательности m двоичных символов исказится больше половины, то есть больше m/2 символов.

Так как ПРМ СОС воспринимает в качестве сигнала подтверждения только m нулевых бит (немажоритарный прием), то вероятность р0 определяется по формуле, а вероятность р? определяется по формуле .

где 0 и 1 -длительности единичных элементов сигналов в каналах ДКпр и ДКобр соответственно, а В и В1 — скорость передачи в каналах ДКпр и ДКобр соответственно.

m? 15.8, примем m=15, тогда t0 ?1, а t?=15. Рассчитаем вероятности р0 и р?:

Рис. 5

р0 = Pm (?1) = 3,87*10−3

p? = Pm (m) = 5,77*10−5

В системе РОС с непрерывной передачей и блокировкой приемника необходимо определить размер окна h.

h 1 +] tож/(n0), где

n = 95 — длина кодового слова;

tож = tp + tp +tc+ ta.k. + ta. c ;

tp' = 7*10−2 и tp = 10−2- время распространения сигналов в дискретных каналах ДКобр и ДКпр соответственно;

tс= m*1 = 15*0,01 = 0,15 — длительность сигналов обратной связи — подтверждение и запрос;

ta.k — время анализа кодового слова;

tа.с — время анализа сигнала обратной связи;

В реальных системах taktactp. Поэтому, можно принять ta. k= ta. c = 0;

tож = 7*10−2+10−2+15*10−2 = 23*10−2с.

h 1 +] 23*10−2/(95*1,67*10−3)[ ;

h=3.

Найдем вероятности вставок и выпадений.

Для системы РОСнп бл используется формулы:

Рвст = Q2*р0;

Рвып = h**р? ;

Q = 0,9932;

= 6,8*10−3;

р0 = Pm (?1) = 3,87*10−3;

p? = Pm (m) = 5,77*10−5;

h = 3;

Рвст =3,82*10−3;

Pвып =0,95*10−6;

Из полученных результатов видим, что PвстPвст. доп, Pвып Рвып.доп.

Исходя из того, что Рвст превышает допустимое значение Рвст доп в проектируемой системе необходимо использовать нумерацию кодовых слов в прямом канале ДКпр. Кодовые слова в системе с непрерывной передачей и блокировкой приемников нумеруются по модулю (h+1). Это значит, что номера изменяются в цикле

…0 1 2 3 0 1 2 3…

Для организации нумерации понадобится i двоичных символов:, i? 2. При выборе циклического кода код был укорочен на 32 символа, теперь следует прибавить необходимые для нумерации 2 символа. Получаем циклический код (97, 76). Пересчитаем избыточность полученного кода. Wk = 0,216, что удовлетворяет соотношению

WнWkWдоп. Условная вероятность совпадения номера кодового слова с ожидаемым при возникновении необнаруженной ошибки составитрN=1/(h+1) = 1/(3+1) = 0,25 .

В системе РОСнп бл с нумерацией кодовых слов Рвып и Рвст рассчитывают по формулам:

Рвст=Р*р0pN,

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

Рвып=(h+1)**р?

Рвст= 1,038*10−9*3,87*10−3*0,25 = 1*10−12

Рвып=4*6,8*10−3 *5,77*10−5 = 0,74*10−6

Из полученных результатов видим, что PвстPвст. доп, Pвып Рвып.доп.

Это значит, что можно принять вариант системы с РОС с нумерацией кодовых слов по модулю 3 при сигналах решения длины m=15. В качестве сигналов решения выбираются сигналы с максимально возможным расстоянием Хемминга (t=m).

Найдем максимально допустимое число j передач каждого сообщения:

j = lgPст доп / lgq? = 4

Расчет относительной скорости передачи и времени задержки

Используя исходные данные и данные, полученные при расчетах ранее, убедимся в возможности использования системы РОС с непрерывной передачей и блокировкой приемника. Как было рассчитано, время ожидания сигнала ОС равно tож = 0,23 с.

Средняя относительная скорость передачи в проектируемой системе равна:

= (74/95)*(1−3*0,387) = 0,772

Wн.п.бл = 1 — Rн.п.бл= 1 — 0,772 = 0,228

Так как избыточность Wн.п.бл

Максимальное время задержки равно:

tзmax = = n0 + tp + (j-1)*(n0 + tож)= 1,3 с;

tзmaxtз доп = 1,5 с.

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

Выводы

По результатам расчетов из пунктов 3,4,5 и 6 система защиты от ошибок, удовлетворяющая требованиям, приведенным в пункте 1, и критерию минимальной сложности, имеет следующие характеристики:

В СЗО используется система РОС с непрерывной передачей и блокировкой приемника со специальным обратным каналом.

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

Сигнал ОС имеет длину m=15. Приемник сигналов обратной связи ОС принимает решение c помощью немажорного приема.

Максимальное число передач каждого сообщения, допустимое в системе, равно 4.

1. Яковенко Н. В., Гузеев А. В. Проектирование системы защиты от ошибок канального уровня: Учебное пособие / МТУСИ. — М., 2013. — 34 с.

Приложение 1

Реализация структурных схем кодера (рис. 6) и декодера (рис. 7) циклического кода с параметрами (95, 74) и образующим полиномом

g (x)=x21+x18+x17+x15+x14+x12+x11+x8+x7+x6+x5+x+1.

ошибка защита декодер задержка Рис. 6 — Структурная схема кодера Рис. 7 — Структурная схема декодера

Приложение 2

Рассмотрим ситуации, приведенные на диаграмме Сообщение, принятое с ошибкой, привело к блокировке окна размером h=3.

Из-за искажения сигнала «запрос» произошло выпадение h+1=4 слов.

Из-за искажения сигнала «подтверждение» происходит повторная передача окна сообщений.

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

При повторной передаче произошло искажение номера сообщения, и он стал равен номеру, ожидаемому приемником. Так как h=3, нумерация сообщений осуществляется от 0 до 3, то есть 00, 01, 10, 11. Это значит, что могут возникать одинарные и двойные ошибки. Согласно выбранному (n, k)-коду dmin = 7, то есть код может исправлять одиночные и обнаруживать двойные ошибки. Сообщение не будет выдано получателю, дублирование не произойдет.

На защиту:

Сообщение, поступающее от источника (ИС) кодируется в кодере (Кодер) помехозащитным кодом, позволяющим обнаруживать ошибки, записывается в накопитель (Нак) передающей станции, А емкостью 1 кодовая комбинация, и передается в дискретный канал прямого направления (ДК пр). На приемной станции Б сообщение декодируется в декодере (Декодер). Если последний не обнаруживает ошибок, управляющее устройство станции Б (УУ) разрешает выдачу сообщения получателю (ПС). Передатчик сигналов обратной связи (ПЕР СОС) формирует и передает в дискретный канал обратного направления (ДКобр) сигнал подтверждения. При получении сигнала подтверждения приемник сигналов обратной связи (ПРМ СОС) на станции, А выдает соответствующий сигнал в управляющее устройство (УУ). По сигналу УУ сообщение, по которому был получен сигнал подтверждения, стирается из накопителя, а от источника поступает следующее сообщение.

Рис. 8 — Функциональная схема системы РОСнп бл Системы с непрерывной передачей для упрощения алгоритма их работы строят в основном таким образом, что после обнаружения ошибки приемник (Декодер) стирает слово с ошибкой и блокируется (стирает без анализа) на прием следующих 2 слов (т.к. h-1, а h=3). Передатчик по сигналу «запрос» повторяет слово, в котором была обнаружена ошибка, и 2(т.к. h-1, а h=3) следующих за ним. Таким образом, передатчик повторяет все сообщения в текущем окне. Такие системы получили название систем РОС с непрерывной передачей и блокировкой (РОСнп бл).

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

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

*Аннулирует принятое кодовое слово с обнаруженной ошибкой и следующие (h-1) кодовое слово;

*Передает в канал ДКобр сигнал запроса (на временной диаграмме — 1) и затем (h-1) подтверждение после аннулирования (стирания) принятых кодовых комбинаций.

После этого станция В возвращается в режим приема и анализа кодовых комбинаций от станции А.

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

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