Проектирование системы защиты от ошибок канального уровня
Постановка задачи проектирования СЗО
Система защиты от ошибок на основе системы с
обратной связью (ОС) характеризуется многими параметрами. Задача ее
проектирования всегда является оптимизационной задачей, т.е. при заданных
ограничениях на ряд параметров требуется найти наилучший вариант по какому-то
критерию. В качестве критерия оптимизации выбирается одна из характеристик
системы передачи данных: верность, скорость передачи, задержка передачи или
сложность устройства.
В настоящем курсовом проекте рассматривается
вариант оптимизации СЗО по критерию сложности. При этом принимается во внимание
сложность алгоритма работы системы с ОС, алгоритма кодирования и декодирования
и объем накопителей на передаче и приеме. Таким образом, при курсовом
проектировании ставятся и решаются локальные задачи расчета СЗО, однако они
позволяют отобразить ряд важных, ключевых особенностей реальных проектов и
теоретических положений курса.
Требуется построить СЗО на основе системы с РОС,
обеспечивающую передачу информации в системе передачи данных по заданному
дискретному каналу (ДК) с заданным качеством при минимальной сложности
устройства. Качество определяется следующими параметрами:
скоростью передачи;
вероятностью ошибки при получении сообщения
источника не более Pош.доп;
вероятностью потери (выпадения) сообщения не
более Рвып.доп;
вероятностью выдачи дубликата (вставки
сообщения) не более Рвст.доп;
вероятностью стирания сообщения не более
Рст.доп;
задержкой сообщения не более tз.доп.
Исходные данные для проектирования
Рис. 1
Характеристики СЗО
На вход СЗО поступают сообщения в виде двоичных
последовательностей длины L=37 бит (разрядов) со скоростью M=12,5 сообщений в
секунду;
Допустимая вероятность ошибки в сообщении
Рош.доп = 5*10-9 ;
Допустимая вероятность выпадения сообщения
Рвып.доп = 10-6;
Допустимая вероятность вставки сообщения
Рвст.доп = 10-7;
Допустимая вероятность стирания сообщения
Рст.доп = 10-9 ;
Допустимое время задержки сообщенияtз.доп=
1,5 с;
Оценка сложности проектируемого СЗО производится
по сложности технической реализации кодера и декодера, алгоритма обработки
сигналов обратной связи (ОС) и объема накопителей на передаче и приеме.
Характеристики дискретного канала прямого
направления (ДКпр):
Максимальная скорость передачи по каналу В = 600
Бод;
Модель ошибок в ДК задается
распределением вероятности Pn(³1)
возникновения хотя бы одной ошибки на длине n последовательности двоичных
символов в зависимости от nи распределением вероятности Pn(³t)
возникновения ошибок кратности t и более на длине n последовательности символов
в зависимости от t:
П - произведение значений функции
при i, изменяющимся от 2 до t.- вероятность ошибки в двоичном символе, pe =
7*10-4,
a-
коэффициент группирования ошибок, a=
0,5;
Время распространения в дискретном
канале tр = 10 мс.
Характеристики дискретного канала
обратного направления (ДКобр):
Скорость передачи В1 = 100 Бод;
Модель ошибок в дискретном канале
обратного направления (обратной связи): pe - вероятность ошибки в двоичном
символе, pe = 10-3, a-
коэффициент группирования ошибок, a=
0,5;
Время распространения в дискретном
канале обратной связи tр’ = 70 мс.
Выбор корректирующего кода в системе
с РОС
Согласно исходным данным для
проектирования, приведенным в пункте 1, построим зависимость Wн = f(n). Она
проиллюстрирована на рис. 1. Там же показано значение Wдоп, вычисленное по
формуле
Wдоп = (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н£Wk£Wдоп.
Найдем образующий полином выбранного кода g(х) и кодовое расстояние d. Из
таблицы циклических кодов, приведенной в приложении, имеем fj(х)= 235+217+211.
Соответствующий образующий полином будет
g(x)=x21+x18+x17+x15+x14+x12+x11+x8+x7+x6+x5+x1+1,
d=7.
Уточним значение вероятности не обнаруживаемой
кодом ошибки.
Рис. 3
н.о. = 1,038*10-9, что меньше значения Pош.доп.
, то есть Pн.о.<Pош.доп.
Вероятность обнаруживаемой кодом ошибки равна:
q= 6,8*10-3,
тогда вероятность правильного приема будет
равна:
= 1-q = 0,9932
Выбор алгоритма работы проектируемой
системы
Так как рассчитанное значение Wдоп< 0.7,
следует проектировать систему РОС с непрерывной передачей и блокировкой
приемника. Функциональная схема такой системы показана на рис. 2.
Рис. 4 - Функциональная схема системы РОСнпбл
Расчет внешних характеристик Рвст, и
Рвып
Расчет вероятностей Рвып и Рвст
Вероятности выпадений и вставок зависят в первую
очередь от вероятностей искажения сигналов ОС (р0 и р?).В системе со
специальным обратным каналом в качестве сигналов ОС могут быть выбраны две
двоичные последовательности длины m бит с максимально возможным расстоянием
Хемминга t=m.
Рассмотрим методику расчета вероятностей р0 и р?
для различных алгоритмов принятия решения приемником сигналов обратной связи
(ПРМ СОС).
Когда прием сигналов ОС (ПРМ СОС на станции А)
осуществляется в соответствии с принципом максимального правдоподобия
(мажоритарный прием), сигнал «подтверждение» будет воспринят как «запрос» и
наоборот сигнал «запрос» воспринимается как «подтверждение», если в
последовательности, передаваемой по обратному каналу ДКобр, исказится больше
половины бит. Например, передавалось «подтверждение» - 000, а приемник ПРМ СОС
регистрирует - 101 и интерпретирует принятую последовательность, как «запрос».
Тогда вероятность искажения сигнала «подтверждение» (р0) равна вероятности
искажения сигнала «запрос» (р?) и равна вероятности того, что на длине
последовательности m двоичных символов исказится больше половины, то есть
больше m/2 символов.
Так как ПРМ СОС воспринимает в
качестве сигнала подтверждения только m нулевых бит (немажоритарный прием), то
вероятность р0 определяется по формуле , а вероятность р? определяется по
формуле .
где 0 и 1 -длительности единичных
элементов сигналов в каналах ДКпр и ДКобр соответственно, а В и В1 - скорость
передачи в каналах ДКпр и ДКобр соответственно.
≤ 15.8, примем m=15, тогда t0 ≥1,
а t?=15. Рассчитаем вероятности р0 и р?:
Рис. 5
р0 = Pm(≥1) = 3,87*10-3? =
Pm(m) = 5,77*10-5
В системе РОС с непрерывной передачей и
блокировкой приемника необходимо определить размер окна h.
³ 1 +] tож/(nt0), где= 95 - длина
кодового слова;
tож
= tp¢
+ tp +tc+ ta.k. + ta.c ;
tp' = 7*10-2 и tp = 10-2- время распространения
сигналов в дискретных каналах ДКобр и ДКпр соответственно;с= m*1 = 15*0,01 =
0,15 - длительность сигналов обратной связи - подтверждение и запрос;
.k - время анализа кодового слова;а.с - время
анализа сигнала обратной связи;
В реальных системах tak»tac<<tp.
Поэтому, можно принять ta.k= ta.c = 0;
Найдем вероятности вставок и выпадений.
Для системы РОСнп бл используется формулы:
Рвст = Q2*р0;
Рвып = h*q*р? ;= 0,9932;
q = 6,8*10-3;
р0 = Pm(≥1) = 3,87*10-3;
p? = Pm(m) = 5,77*10-5;= 3;
Рвст =3,82*10-3;вып =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н£Wk£Wдоп.
Условная вероятность совпадения номера кодового слова с ожидаемым при
возникновении необнаруженной ошибки составитрN=1/(h+1) = 1/(3+1) = 0,25 .
В системе РОСнп бл с нумерацией
кодовых слов Рвып и Рвст рассчитывают по формулам:
Рвст=Р*р0pN,
где pN - условная вероятность
совпадения номера принятого кодового слова с ожидаемым принимающей станцией при
условии возникновения в этом слове не обнаруживаемой кодом ошибки.
Рвып=(h+1)*q*р?
Рвст= 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 передач
каждого сообщения:
= ]lgPст доп / lgqq?
[
= 4
Расчет относительной скорости
передачи и времени задержки
Используя исходные данные и данные, полученные
при расчетах ранее, убедимся в возможности использования системы РОС с
непрерывной передачей и блокировкой приемника. Как было рассчитано, время
ожидания сигнала ОС равно tож = 0,23 с.
Средняя относительная скорость передачи в
проектируемой системе равна:
=
(74/95)*(1-3*0,00387) = 0,772н.п.бл = 1 - Rн.п.бл= 1 - 0,772 = 0,228
Так как избыточность Wн.п.бл<Wдоп=0,229 ,
система удовлетворяет требованиям по скорости передачи информации от источника
с учетом вносимой избыточности за счет помехоустойчивого кодирования и
повторных передач.
Максимальное время задержки равно:
зmax = = nt0 + tp + ( j-1)*(nt0
+ tож)= 1,3 с;зmax<tз доп = 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.