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

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

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

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

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

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

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

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

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

Соответственно матрица двоичного симметричного канала со стиранием: P₁₁=1-P-q; P₁₂=P; P₁₃=q; P₂₁=P; P₂₂=1-P-q; P₂₃=q; где Р - вероятность трансформации; 1-P-q - вероятность про­хождения символа; q - вероятность стирания символа.

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

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

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

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

Пропускная способность дискретного симметричного канала связи с шумом. Рассмотрим канал без стирания, для которого K_x=K_y=K. При наличии шума в ДКС входной символ x_j переводят в символ y_i с вероятностью Р(y_i/x_j). Вероятность трансформации символа составит: Р=S_i=1^KР(y_i/x_j) при i ¹ j. Если ка­нал симметричен, то вероятности, входящие в данную сумму, оди­наковы, а поэтому Р(y_i/x_j)=Р(K-1)^-1 при i ¹ j. Вероятность прохож­дения символа 1-P=Р(y_i/x_i) при i=j. Пропускная способность рассматриваемого канала C=I_max=H_max(Y)-H_min(Y/X). Ранее показано, что H_max(Y)=log₂K,

H_max(Y/X)= - S_j=1^KS_i=1 ^K Р(х_j)Р(у_i/х_j) log₂Р(у_i/х_j).

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

H_max(Y/X)=(1-P)log₂(1-P)-Plog₂(P(K-1)^-1).

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

C=log₂K+(1-P)log₂(1-P)+Plog₂(P(K-1)^-1).

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

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

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

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

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

Н(у)=-S_j=-¥^j=¥ p(y_j)log₂[p(y_j)]= -ò_-¥^¥W(y) log₂[W(y)Dy] dy,

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

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

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

C=I_max=H_max(y)=log₂(s(2pe)^0,5/Dx),

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

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

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

с учетом p(y_j)= S_i=-¥^i=¥p(x_i)p(y_j/x_i)= ò_-¥^¥(W(x)W(y_j/x)Dy)dx.

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

I=ò_-¥^¥ò_-¥^¥ W(y, x)log₂[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)=C_n^jP^j(1-P)^n-j;

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

P(³i, n)=S_j=1ⁿ P(j, n)= S_j=1ⁿ C_n^jP^j(1-P)^n-j;

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

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

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

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

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

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

Информационный предел избыточности количественно выража­ется числом контрольных символов, введенных в код для передачи контрольной информации. При максимальной информативности элемента кода, что соответствует равновероятности передаваемых символов и энтропии источника H_max=log₂K, получим нижнюю границу избыточности k_min=I_k/log₂K, где k_min - минимальное число контрольных символов, определяемое информационным пределом избыточности. Найдем это значение для двоичного дискретного симметричного канала связи с независимыми ошибками. Пусть для передачи сообщений используется двоичный корректирующий код, для которого d=2s+1, r=s, т.е. все обнаруживаемые кодом ошиб­ки исправляются. Тогда возможны два исхода: прохождение сооб­щения с вероятностью P_пр и трансформация сообщения с вероят­ностью P_тр. Эти исходы должны описывать составляющие конт­рольной информации, поэтому I_K=I_Kпр+I_Kтр. Количество контрольной информации найдем с использованием функции энтропии. Исход в приеме сообщений зависит от числа ошибок j, попада­ющих на длину кода n, т.е. от вероятности P(j, n). Правильный прием сообщения имеет место, если число ошибок, возникающих на длине кода n, находится в пределах от 0 до s. Трансформация сообщения возможна при числе ошибок от s+1 до n. Отсюда находим P_пр=S_j=0^sP(j, n); P_тр=S_j=s+1ⁿP(j, n).

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

P(j, n)=C_n^jP^j(1-P)^n-j,

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

I_K = -S_j=0^s C_n^jP^j(1-P)^n-j log₂(P^j(1-P)^n-j).

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

I_K = -S_j=0^s C_n^j P₁ log₂ P₁ .

Учитывая, что совокупность вариантов корректируемых ошибок составляет полную группу событий, получим P₁=(S_j=0^sC_n^j)^-1. Отсюда

I_K = -S_j=0^s C_n^j (S_j=0^sC_n^j)^-1log₂ (S_j=0^sC_n^j)^-1= log₂(S_j=0^sC_n^j).

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

k ³ k_min = log₂(S_j=0^sC_n^j).

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

2^n-m³S_j=0^sC_n^j; M=2^m£ 2ⁿ(S_j=0^sC_n^j)^-1.

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