Процесс передачи информации

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

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

Модель дискретного канала связи. Дискретный канал связи имеет на входе множество символов кода Х с энтропией источника Н(Х), а на выходе - множество символов Y с энтропией H(Y). Если формируемые символы из множества Х и вы­являемые из множества Y расположить в узлах графа, соединив эти узлы дугами, отображающими вероятности перехода одного сим­вола в другой, то получим модель дискретного канала связи. Множество символов Х конечно и определя­ется основанием системы счисления кода Kx на входе канала. Систе­ма счисления по выявляемым символам также конечна и составляет Ky. Вероятности переходов, связывающих входные и выходные сим­волы, могут быть записаны в виде матрицы P, у которой j-й строкой является Pj = ||P(y1/xj) ... P(yKy/xj)||; j=1...Kx.

В этой матрице i-й столбец определяет вероятность выявления на выходе дискретного канала связи символа yi. Вероятности, расположенные на главной диагонали, называются вероятностями прохождения символов, остальные вероятности есть вероятности трансформации. Анализ модели дискретного канала связи возмо­жен, если известна статистика появления символов на входе канала. Тогда может быть определена энтропия Н(Х). Если известна стати­стика символов на выходе канала, то нетрудно установить энт­ропию H(Y). Потери информации могут быть вызваны действием помех, которые отображаются в дискретном канале в виде некото­рого потока ошибок. Поток ошибок задается с помощью опреде­ленной модели ошибок, на основании которой может быть установ­лена матрица P. Зная эту матрицу, находят условную энтропию H(Y/X), которая, как выше показано, отображает потери инфор­мации при прохождении ее по каналу связи. В данном случае H(Y/X) - это потери информации из-за действия ошибок в диск­ретном канале связи. Исходя из модели дискретного канала связи, можно выполнить классификацию дискретных каналов.

По основанию системы счисления - коды на входе ДКС различают двоичные, троичные, четверичные каналы связи и дру­гие.

По соотношению системы счисления - коды на выходе и на входе ДКС выделяют каналы со стиранием, если Ky>Kx, и каналы без стирания, если Ky=Kx.

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

При определенных соотношениях между вероятностями перехо­дов, входящих в матрицу P, выделяют симметричные каналы по входу, для которых вероятности, входящие в строку матрицы, являются перестановками одних и тех же чисел; симметричные каналы по выходу, для которых это относится к вероятностям, входящим в столбцы; симметричные каналы по входу и по выходу при соблюдении обоих условий. На основе представленной клас­сификации матрица двоичного симметричного канала P имеет компоненты: P11=1-P; P12=P; P21=P; P22=1-P; где Р - вероятность искажения символа.

Соответственно матрица двоичного симметричного канала со стиранием: P11=1-P-q; P12=P; P13=q; P21=P; P22=1-P-q; P23=q; где Р - вероятность трансформации; 1-P-q - вероятность про­хождения символа; q - вероятность стирания символа.

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

Основной характеристикой дискретного канала является про­пускная способность. Под ней понимают верхний предел количества информации, которую можно передать через канал связи, отоб­ражаемый заданной моделью. Оценим пропускную способность дискретного канала связи. Количество взаимной информации, связывающей множества символов X, Y, составит: I(Х, Y) = I = H(Y)-H(Y/X). Пропускная способность C=Imax=Hmax(Y)-Hmin(Y/X). Раскроем данное выражение для отдельных вариантов дискретного канала связи.

Пропускная способность дискретного канала связи без шума. При отсутствии шума потерь информации в канале нет, и поэтому H(Y/X)=0, тогда C=Imax=Hmax(Y). Как известно, мак­симум энтропии для дискретных событий достигается при их равновероятности. Учитывая, что на выходе канала связи может появиться Ky символов, получим, что Hmax=log2Ky. Отсюда C=log2Ky.

Таким образом, пропускная способность дискретного канала без шума зависит только от основания кода. Чем оно больше, тем выше информативность каждого символа, тем больше пропускная способность. Пропускная способность измеряется в двоичных еди­ницах на символ и не связана в данном представлении со временем. При переходе от двоичного кода к четверичному пропускная спо­собность ДКС без шума увеличивается в два раза.

Пропускная способность дискретного симметричного канала связи с шумом. Рассмотрим канал без стирания, для которого Kx=Ky=K. При наличии шума в ДКС входной символ xj переводят в символ yi с вероятностью Р(yi/xj). Вероятность трансформации символа составит: Р=Si=1KР(yi/xj) при i ¹ j. Если ка­нал симметричен, то вероятности, входящие в данную сумму, оди­наковы, а поэтому Р(yi/xj)=Р(K-1)-1 при i ¹ j. Вероятность прохож­дения символа 1-P=Р(yi/xi) при i=j. Пропускная способность рассматриваемого канала C=Imax=Hmax(Y)-Hmin(Y/X). Ранее показано, что Hmax(Y)=log2K,

Hmax(Y/X)= - Sj=1KSi=1 K Р(хj)Р(уij) log2Р(уij).

Принимая, что на входе ДКС символы равновероятны, т.е. Р(хj)=K-1, находим

Hmax(Y/X)=(1-P)log2(1-P)-Plog2(P(K-1)-1).

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

C=log2K+(1-P)log2(1-P)+Plog2(P(K-1)-1).

В случае двоичного симметричного канала с шумом пропускная способность может быть найдена при K=2, т.е. C=1+(1-P)log2(1-P)+Plog2P.

Видно, что она увеличивается с ростом основания кода и с уменьшением вероятности трансформации символа.

Пропускная способность непрерывного канала связи. В непрерывном канале связи входной сигнал x(t) преобразуется из-за нали­чия помехи в выходной сигнал y(t). Учитывая, что сигнал име­ет случайную природу, он определя­ется плотностью распределения вероятностей своих значений на входе W(x), а на выходе W(y). Количество взаимной информации, связывающей входной и выходной сиг­налы, соответствует выражению I(х, у)=I=Н(у)-Н(у/х), где Н(у) - энтропия на выходе непрерывного канала; Н(у/х) - условная энтропия, отображающая потери при передаче через непрерывный канал связи. Под пропускной способностью непрерывного канала связи пони­мают, как и ранее, верхний предел скорости передачи информации, т.е. C=Imax=Hmax(y)-Hmin(y/x).

Пропускная способность непрерывного канала без шума. Для канала без шума Н(у/х)=0, C=Imax=Hmax(y).

Учитывая, что p(yj)=W(yj)Dy:

Н(у)=-Sj=-¥j=¥ p(yj)log2[p(yj)]= -ò-¥¥W(y) log2[W(y)Dy] dy,

максимум энтропии для некоторого оптимального рас­пределения:

Wопт(y)=(2ps)-0,5 e-y2/2s2,

что соответствует нормальному закону. Тогда

C=Imax=Hmax(y)=log2(s(2pe)0,5/Dx),

где Dx=Dy - шаг квантования на передающей стороне с учетом требуемой точности воспроизведения непрерывной функции.

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

I=Н(у)-Н(у/х)=-ò-¥¥ò-¥¥W(x)W(y/x)log2[W(y)Dy]dxdy+ò-¥¥ò-¥¥W(x)W(y/x)log2[W(y/x)Dy]dxdy,

с учетом p(yj)= Si=-¥i=¥p(xi)p(yj/xi)= ò-¥¥(W(x)W(yj/x)Dy)dx.

Так какН(у/х) ¹ 0, то при наличии помех количество передава­емой информации через канал снижается. Обозначим W(x)W(y/x)=W(y, х), тогда нетрудно установить, что

I=ò-¥¥ò-¥¥ W(y, x)log2[W(y, x) W-1(x) W-1(y)]dxdy.

Пропускная способность есть максимум данного выражения, который определяется по распределениям значений функции x(t) на входе непрерывного канала связи. Отметим, что если W(y, х)= W(x)W(y), что соответствует стати­стически независимым распределениям на входе и на выходе непрерывного канала связи, то C=0. Это означает, что уровень помех в канале достиг та­кой величины, при которой никакой зависимости между выходным и вход­ным сигналами не остается. Статисти­ческая независимость распределений W(x) и W(y) подтверждает, что сигнал полностью подавлен помехой, полезная информация не передается, т.е. I=0. Это соответствует и нулевой пропускной способности. Заметим, что и в дискретном канале связи при определенном значе­нии вероятности искажения символа пропускная способность сни­жается до нуля. Очевидно, что такое состояние канала связи являет­ся нерабочим и ориентироваться на него не нужно.

Информационный предел избыточности для канала с независимыми ошибками. Процесс передачи данных в реальных системах и се­тях реализуется в условиях действия помех, поэтому возникает необходимость построения моделей функционирования системы пе­редачи данных, позволяющих оценить ее вероятностно-временные характеристики. Их удобно находить, исходя из модели передачи данных по дискретному каналу связи, вводя в модель источник ошибок. Если на вход ДКС поступает некоторая последо­вательность {х}, а источник ошибок формирует последователь­ность {е}, то на выходе канала при аддитивности процессов для двоичного кода формируется последовательность {уÅ е}. Местоположение единиц в {е} указывает ошибки выходной последовательности {у}. При передаче формируются последовательности символов длиной n, отображающие одно или несколько сообщений. Последствия воздействия ошибок на передаваемый код зависят от числа ошибок, попавших на код длины n. Обозначим вероятность попадания j ошибок на код длины n через P(j, n). Эта вероятность может быть найдена при экспериментальном исследовании путем моделирования, а также на основе аналитических расчетов. Модель дискретного симметричного канала связи позволяет оценить эту вероятность аналитическим путем для отдельных достаточно про­стых описаний потоков ошибок.

В двоичном симметричном канале связи без памяти вероятность искажения любого из передаваемых символов одинакова. Это по­зволяет применить для описания потока ошибок биномиальный закон распределения. Тогда

P(j, n)=CnjPj(1-P)n-j;

где Р - вероятность искажения символа. Отметим, что случай непопадания ошибок на код длины n возникает с вероятностью P(0, n)=(1-P)n, что соответствует n взаимонезависимым событиям прохождения символов. Из биномиального закона нетрудно получить совокупность вероятностей, определя­ющих возникновение в коде i ошибок и более:

P(³i, n)=Sj=1n P(j, n)= Sj=1n CnjPj(1-P)n-j;

Среднее число ошибок в коде длины n составляет nР. В реаль­ных абонентских каналах связи это число очень мало. Представляет интерес оценить вероятность P(j, n) при Р®0:

P(j, n)=[n(n-1)...(n-j+1)][1*2... j]Pj(1-P)n-j.

При Р£0,1 и малых значениях j находим P(j, n)=(nP)j(j!)-1e-nP. Получаемый при этом закон распределения Пуассона определяется одним парамет­ром nР, что облегчает аналитический расчет вероятностей. Зная модель потока ошибок и избыточность передаваемого кода, можно найти вероятность ошибки в приеме некоторого сообщения y0i. Как было показано выше, Р(ош/y0i)=Sj=1MР(x0j)Р(y0i/x0j) при i¹j. Веро­ятность перехода сообщения x0j в сообщение y0i назовем вероят­ностью трансформации сообщения, т.е. P(y0i/x0j)=Pтр при i¹j.

Если принятое сообщение соответствует переданному, то это событие можно оценить вероятностью прохождения Pпр, т.е. Р(y0i/x0j)= Pпр при i=j. В реальном канале связи может возникать ситуация, когда принятое сообщение не может быть отождествлено ни с одним из передаваемых. Этот исход получил название "защит­ного отказа". Он возникает при обнаружении ошибок. Обозначим вероятность защитного отказа Рзо, тогда Pпр=1-Р0, где Р0 - веро­ятность ошибки, Р0зо+ Ртр.

Пусть через дискретный канал связи передается код, облада­ющий кодовым расстоянием d, исправляющий s и обнаруживающий r ошибок. Если число ошибок, возникших в коде длины n, не превышает его корректирующей способности, то происходит правильная передача сообщения. Отсюда вероятность прохождения Pпр=Sj=0sP(j, n). Используя закон распределения Пуассона, получим: Pпр=Sj=0s(nP)j(j!)-1e-nP.

Вероятность ошибки Р0=Sj=s+1nP(j, n)= Sj=s+1n(nP)j(j!)-1e-nP. Видно, что с увеличением числа исправляемых ошибок вероят­ность прохождения увеличивается, а вероятность ошибки уменьша­ется. Для кода, не исправляющего ошибки, вероятность прохожде­ния Pпр=Р(0, n)=e-nP. Соответственно вероятность ошибки Р0=1-e-nP. При nР<<1, используя разложение в ряд Тейлора, получим Р0»nР, т.е. вероятность ошибки равна сред­нему числу ошибок, возникающих на длине кода n. Отсюда следует, что при отсутствии избыточности получить малую вероятность ошибки можно лишь при очень малых значениях nР. С увеличением вероятности искажения символов необходимо ввести избыточность в передаваемый код. При введении избыточности улучшаются об­наруживающие, а при определенном ее уровне и исправляющие свойства кода. Избыточность в коде проявляется в виде контроль­ной информации Ix компенсирующей потери информации в обоб­щенном дискретном канале связи H(Y0/X0). Можно предположить, что количество контрольной информации и способ ее применения зависят от свойств потока ошибок в канале связи. Минимально необходимая избыточность, компенсирующая ошибки в заданном типе канала связи, получила название информационного предела избыточности.

Информационный предел избыточности количественно выража­ется числом контрольных символов, введенных в код для передачи контрольной информации. При максимальной информативности элемента кода, что соответствует равновероятности передаваемых символов и энтропии источника Hmax=log2K, получим нижнюю границу избыточности kmin=Ik/log2K, где kmin - минимальное число контрольных символов, определяемое информационным пределом избыточности. Найдем это значение для двоичного дискретного симметричного канала связи с независимыми ошибками. Пусть для передачи сообщений используется двоичный корректирующий код, для которого d=2s+1, r=s, т.е. все обнаруживаемые кодом ошиб­ки исправляются. Тогда возможны два исхода: прохождение сооб­щения с вероятностью Pпр и трансформация сообщения с вероят­ностью Pтр. Эти исходы должны описывать составляющие конт­рольной информации, поэтому IK=IKпр+IKтр. Количество контрольной информации найдем с использованием функции энтропии. Исход в приеме сообщений зависит от числа ошибок j, попада­ющих на длину кода n, т.е. от вероятности P(j, n). Правильный прием сообщения имеет место, если число ошибок, возникающих на длине кода n, находится в пределах от 0 до s. Трансформация сообщения возможна при числе ошибок от s+1 до n. Отсюда находим Pпр=Sj=0sP(j, n); Pтр=Sj=s+1nP(j, n).

Так как ошибки, приводящие к трансформации сообщения, ис­править невозможно, то ограничимся в структуре контрольной информации лишь той, которая необходима для исправления от нуля до s ошибок, т.е. IK= IKпр. Для канала с независимыми ошиб­ками

P(j, n)=CnjPj(1-P)n-j,

где Cnj - число сочетаний из n по j. Отсюда, используя формулу энтропии, находим

IK = -Sj=0s CnjPj(1-P)n-j log2(Pj(1-P)n-j).

Примем допущение, что возникновение любой корректируемой ошибки и отсутствие ошибок происходит с равной вероятностью P1=Pj(1-P)n-j. Тогда

IK = -Sj=0s Cnj P1 log2 P1 .

Учитывая, что совокупность вариантов корректируемых ошибок составляет полную группу событий, получим P1=(Sj=0sCnj)-1. Отсюда

IK = -Sj=0s Cnj (Sj=0sCnj)-1log2 (Sj=0sCnj)-1= log2(Sj=0sCnj).

Информационный предел избыточности составит kmin=IK/log22=IK. Если корректирующий код строится для числа пере­даваемых сообщений М=2m, где m - число информационных эле­ментов в коде, то количество контрольных элементов

k ³ kmin = log2(Sj=0sCnj).

Отсюда 2k ³ Sj=0sCnj. Общее число элементов в коде п = m+k, т.е. k = n-m. Тогда

2n-m³Sj=0sCnj; M=2m£ 2n(Sj=0sCnj)-1.

Формула справедлива для кода, исправляющего s ошибок, с чис­лом переходов d=2s+1. Рассмотренный информационный предел получил название предела Хемминга. В частном случае кода, ис­правляющего одну ошибку, т.е. s=1, d=3, получаем M£2n(n+1)-1. Таким образом, модель дискретного канала связи в определенной степени задает и модель потока ошибок. Зная модель потока оши­бок и свойства дискретного канала связи, можно найти информаци­онный предел избыточности и в соответствии с ним построить код, исправляющий ошибки. Рассмотренная модель независимых оши­бок имеет ограниченное применение и справедлива для некоммутируемых телефонных каналов абонентской сети.

Наши рекомендации