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

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

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

Модель дискретного канала связи. Дискретный канал связи имеет на входе множество символов кода Х с энтропией источника Н(Х), а на выходе - множество символов 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₌₁^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₌₁^KS_i₌₁^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^-^y^2/2^s²,

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

C=I_max=H_max(y)=log₂(s(2pe)⁰ ^,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_=-_¥ⁱ⁼^¥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)ⁿ^-^j;

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

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

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

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

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

Если принятое сообщение соответствует переданному, то это событие можно оценить вероятностью прохождения P_пр, т.е. Р(y₀_i/x₀_j)= 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₌₀^sP(j, n); P_тр=S_j₌_s₊₁ⁿP(j, n).

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

P(j, n)=C_n^jP^j( 1 -P)ⁿ^-^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₌₀^sC_n^j)^-1. Отсюда

I_K = -S_j₌₀^s C_n^j (S_j₌₀^sC_n^j)^-1log₂ (S_j₌₀^sC_n^j)^-1 = log₂(S_j₌₀^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₌₀^sC_n^j. Общее число элементов в коде п = m+k, т.е. k = n-m. Тогда

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

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