Теория информационных процессов и систем

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

Канал без обратной связи

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

Число бит n в кадре (размер кадра) всегда равно 63. Количество информационных (k) и контрольных (n-k) разрядов зависит от генераторного многочлена циклического кода. В таблице 1 представлены параметры, циклических кодов полученных с помощью перечисленных выше генераторных многочленов.

Таблица 1

Номер многочлена	0	1	2	3	4	5	6
Минимальное кодовое расстояние, d	1	2	3	4	5	6	7
Число информационных разрядов k	63	62	57	56	51	50	45
Число контрольных разрядов n-k	0	1	6	7	12	13	18

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

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

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

Принимающая сторона может работать в одном из следующих режимов декодирования:

· обнаружения ошибок;

· обнаружения и исправления ошибок;

· исправления ошибок.

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

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

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

3. стертое состояние кадра, когда ошибки обнаружены, но принимающая сторона не пытается их исправить.

Режим обнаружения ошибок

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

t = d - 1 (1)

Вероятность правильного приема кадра Q вычисляется по формуле:

Q = (1 - p)n, (2)

где р - вероятность ошибочного приема одного бита,

n - число разрядов в кадре.

Вероятность ошибочного приема кадра Po можно оценить с помощью приближенной формулы:

(3)

где t - максимальное число обнаруживаемых ошибок.

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

Вероятность стирания кадра Рs вычисляется по формуле:

Рs = 1 - Q - Po (4)

В таблице 2 приведены параметры исследуемых кодов для режима обнаружения ошибок.

Таблица 2

Номер многочлена	0	1	2	3	4	5	6
Кодовое расстояние	1	2	3	4	5	6	7
Количество обнаруживаемых ошибок	0	1	1,2	1,2,3	1,2,3,4	1,2,3, 4,5	1,2,3, 4,5,6

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

Режим обнаружения и исправления ошибок

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

Максимальные числа гарантированно исправляемых и обнаруживаемых ошибок связаны с кодовым расстоянием зависимостью:

+ t = d - 1, (5)

где - число исправляемых ошибок,

t - число обнаруживаемых ошибок.

Формула (5) справедлива, если выполняется условие: t>.

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

Таблица 3

Номер многочлена	0	1	2	3	4	5	6
Число исправляемых ошибок	0	0	0	1	1	1,2	1,2
Число обнаруживаемых ошибок	0	1	2	2	2,3	3	3,4

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

Следует отметить, что могут быть обнаружены также ошибки, число которых превышает значение параметра t, так как любое искажение кадра в канале, вызывающее нарушение правила кодирования, всегда будет обнаружено по наличию ненулевого остатка от деления на генераторный многочлен. Многочлены 0,1,2 не позволяют реализовать режим обнаружения и исправления ошибок.

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

(6)

где - максимальное число исправляемых ошибок,

Вероятность ошибочного приема кадра:

(7)

Вероятность стирания кадра:

Рs = 1 - Q - Po (8)

Режим исправления ошибок. В таблице 4 приведены параметры исследуемых кодов в режиме исправления ошибок. Максимальное число исправляемых ошибок определяется как целое из выражения:

 = int((d - 1)/2) (9)

Таблица 4

Номер многочлена	0	1	2	3	4	5	6
Число исправляемых ошибок	0	0	1	1	1,2	1,2	1,2,3

Вероятность правильного приема кадра вычисляется как сумма вероятностей появления не более ошибок:

, (10)

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

Вероятность ошибочного приема кадра:

Po = 1 - Q (11)

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

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

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

Состояние стирания кадра в данном режиме отсутствует!

Канал с обратной связью

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

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

· эхоконтроль (информационная обратная связь);

· автоматический запрос на повторение (решающая обратная связь).

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

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

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

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

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

· стандартный или передача с остановкой и ожиданием (SAW - Stop And Wait), часто называемый блочным методом передачи;

· с возвращением на N кадров (GDB - Go Back N), называемый потоковым методом передачи;

· выборочного (селективного) повторения (SR - Selective Repeat), называемый методом с адресным переспросом.

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

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

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

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

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

Процедура SR. Согласно этой процедуре повторная передача осуществляется только для кадра, на который поступило отрицательное подтверждение либо истекло время тайм-аута подтверждения.

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

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

Расчет параметров СПД с обратной связью

Процедура SAW. Для оценки эффективной скорости передачи информации V в канале с обратной связью можно применить формулу:

(бит/с), (12)

где к - число информационных разрядов,

n - общее число разрядов в кадре,

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

B - пропускная способность прямого канала ,

Ps - вероятность обнаружения ошибок в принятом кадре.

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

, (13)

где Q - вероятность правильного приема кадра в канале без обратной связи,

Ps - вероятность стирания кадра в канале без обратной связи с учетом режима декодирования.

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

, (14)

где Ро - вероятность ошибочного приема кадра в канале без обратной связи.

Анализируя формулу (12), можно оценить влияние параметров канала и кадра на скорость передачи. Прежде всего на скорость влияет время ожидания сигнала подтверждения Tw, которое в основном состоит из следующих слагаемых:

· времени передачи сигнала обратной связи;

· времени распространения сигнала в прямом и обратном направлениях;

· времени приема и обработки кадра.

При расчете скорости передачи V следует брать параметры n и к из таблицы 1, принимая во внимание выбранный генераторный многочлен. Вероятность стирания кадра Ps зависит от выбранного многочлена и режима декодирования.

Пропускная способность B в формуле (12) равна количеству битов, которое может передать в секунду прямой канал при отсутствии помех. В расчетах следует брать B = 1200 бит/с.

Процедура GBN. Помехоустойчивость СПД в этом режиме можно оценить с помощью приведенных выше формул (13) и (14). Однако эффективная скорость передачи информации будет отличаться от скорости передачи в режиме SAW.

Во-первых, передача информации идет непрерывно без ожидания прихода сигнала подтверждения .

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

Если первое увеличивает скорость передачи по сравнению с протоколом SAW, то второе - уменьшает.

Формула для расчета эффективной скорости передачи в режиме GBN имеет вид:

, (15)

где h - количество кадров, участвующих при повторной передаче.

Процедура SR. Вероятности правильного и ошибочного приема кадра можно оценить, используя приведенные выше формулы (13), (14).

Эффективная скорость в канале рассчитывается по формуле:

. (16)

Анализируя формулы (12), (15), (16), можно сделать заключение, что процедура SR обеспечивает при равных условиях наибольшую скорость передачи.

g4=1+x3+x4+x5+x8+x10+x12

Без обратной связи, режим обнаружения ошибок

		0,016	0,008	0,004	0,002	0,001
g4	Q	0,3627	0,6035	0,7765	0,8812	0,9395
	Po	0,0000	0,0000	0,0000	0,0000	0,0000
	Ps	0,6373	0,3964	0,2235	0,1188	0,0605

Расчеты

		0,016	0,008	0,004	0,002	0,001
g4	Q	0,3627	0,6035	0,7765	0,8812	0,9395
	Po	0,0000	0,0000	0,0000	0,0000	0,0000
	Ps	0,8627	0,5942	0,2959	0,1347	0,0743

Без обратной связи, обнаружение и исправление ошибок

		0,016	0,008	0,004	0,002	0,001
g4	Q	0,7323	0,9091	0,9736	0,9926	0,9981
	Po	0,0000	0,0000	0,0000	0,0000	0,0000
	Ps	0,2676	0,0909	0,0264	0,0072	0,0019

Расчеты

		0,016	0,008	0,004	0,002	0,001
g4	Q	0,7323	0,9091	0,9736	0,9926	0,9981
	Po	0,0000	0,0000	0,0000	0,0000	0,0000
	Ps	0,3329	0,0984	0,0687	0,0169	0,0023

Режим SAW. Обнаружение ошибок

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	87,06	144,57	185,98	211,02	225,1

Расчеты

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	191,45	357,23	392,72	402,67	416,34

Исправление ошибок

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	175,89	217,96	233,64	238,25	236,53

Расчеты

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	254,91	262,17	245,83	239,17	236,62

Режим GBN. Обнаружение ошибок

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	98,72	226,98	398,84	579,43	730,56

Расчеты

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	112,64	201,26	422,08	639,25	873,29

Исправление ошибок

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	344,64	648,13	855,14	937,86	796,73

Расчеты

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	488,76	698,84	872,41	937,97	796,77

Режим SR. Обнаружение ошибок

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	352,05	585,09	755,08	856,97	912,56

Расчеты

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	495,86	482,36	841,13	913,57	995,87

Исправление ошибок

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	712,07	883,29	945,72	964,40	969,60

защита информация кадр ошибка

Расчеты

		0,016	0,008	0,004	0,002	0,001
g4	Poc	0	0	0	0	0
	Qoc	1	1	1	1	1
	V	842,34	933,53	951,67	965,04	969,67

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