2 страница. Вопрос 19: Задача согласования дискретного источника с дискретным каналом с шумом. Р

Вопрос 19: Задача согласования дискретного источника с дискретным каналом с шумом.

Р

ассмотрим теперь ситуацию, когда в процессе передачи сигнал искажается шумом, т.е. некоторым случайным процес­сом. Предположим, что в соответствии с обозначениями (рисунок 2.1), что Z - ансамбль сигналов на входе дискретного канала, а Z* - ансамбль сигналов на его выходе. Наличие в канале шума приводит к тому, что по сигналу Z* нельзя од­нозначно определить сигнал Z. С точки зрения теории информации этот эффект характеризуется наличием потерь ин­формации или ненадежностью канала H(Z/Z*)>0 и описывается соотношением I (Z,Z*) = H(Z) – H(Z/Z*), где I(Z,Z*) - информация переданная по каналу, H(Z)-энтропия или собственная информация ансамбля сигналов на входе канала. Переходя к информационным характеристикам, отнесенным к единице времени последнее выражение можно перепи­сать в виде I* (Z,Z*)=H *(Z)-H(Z/Z*) (2.13), где I(Z,Z*)-скорость передачи информации по каналу, H (Z)-производи­тельность ансамбля на входе канала, H (Z/Z*)-потери информации в единицу времени. При этом пропускная способ­ность канала С хоть и уменьшается по сравнению со случаем канала без шума см.(1.25б), но в общем случае принимает конечное значение (за исключением не принимаемого здесь во внимание экстремального случая обрыва канала). Поло­жим далее, что имеется некоторый дискретный источник с производительностью H(U) C сообщения которого необхо­димо передать по каналу. Для решения этой задачи по-прежнему воспользуемся системой передачи изображенной на рисунке 2.1. Функции выполняемые кодером и декодером в этом случае будут ясны из дальнейших рассуждений.

Поскольку H(U) C возможна передача информации I(Z,Z*) по каналу со скоростью I* (Z,Z*)=H* (U) (2.14), т.к. по определению С – максимально возможная скорость передачи информации по каналу. Приравнивая правые части неравенств (2.13-14), приходим к соотношению H* (Z)-H*(Z/Z*)=H *(U). Из которого следует, что H(Z)=H(U)+H (Z/Z*) H (U). Последнее неравенство означает, что производительность ансамбля сигналов Z (назовем его кодом) на входе ка­нала должна быть выше производительности источника сообщений U, и, следовательно, Z, кроме информации об U должен содержать дополнительную собственную информацию. При этом если бы удалось ввести дополнительную ин­формацию таким образом, чтобы при прохождении сигнала Z по каналу с шумом вследствие ненадежности канала теря­лась бы именно она, а не полезная информация о сообщении U, то оказалось бы возможным обеспечить безошибочную передачу сообщений U по каналу с шумом с конечной скоростью H (U) C. Таким образом, задачей кодера в данной си­туации является согласование источника с каналом, заключается во внесении в сообщение источника избыточности, обладающей описанной выше свойством. Однако не тривиальным является вопрос, а возможно ли в принципе построе­ние такого кодера. Идея борьбы с мешающим влиянием шума за счет введения избыточности, при кодировании дис­кретных сообщений, существовала и до появления Теории Информации и трактовалась следующим образом: предпола­галось сообщение двоичного источника U₁ =0 и U₂ =1 передавать по симметричному двоичному каналу (см. п 1.6) с вероятностями ошибок Р 0,5 двумя кодовыми комбинациями, содержащими соответственно n единиц или n нулей. ; . Если в месте приема регистрировать 1 или 0 по большинству принятых знаков в комбина­ции т.е. принимать так называемое мажоритарное декодирование, то ясно, что ошибка произойдет при условии, если в кодовой комбинации не верно будет принято n/2 или более символов. Согласно закону больших чисел вероятность ук­лонения числа ошибок m в кодовой комбинации длины n от их математического ожидания np (см. задачу 1.11) стре­мится к 0 при n→ ∞, т.е.

Поскольку np < 0,5n при n→ ∞ вход обеспечит безошибочный прием. Однако передачу одного символа необ­ходимо будет осуществлять бесконечно долго, т.е. скорость передачи информации по каналу будет стремится к 0. Таким образом, на основании приведенных ранее рассуждений полагалось, что безошибочная передача информации в канале с шумом возможна лишь в пределе при нулевой скорости передачи. Поэтому положительные решения сформулирован­ного выше вопроса позволяют существенно изменить представление о потенциальных возможностях систем передачи дискретной информации и имеет принципиальное значение в развитии теории и практики связи. Ответ на данный во­прос содержится в теореме Шеннона для дискретного канала с шумом.

Вопрос 20: Прямая теорема Шеннона для канала с шумом (первая часть).

Д

анная теорема является фундаментальным положением Теории Информации и называется так же основной теоремой кодирования Шеннона. Она может быть сформулирована следующим образом: если производительность источника сообщений H(U) меньше пропускной способности канала С т.е. H(U) < C, то существует такая система кодирования которая обеспечивает возможность передачи сообщений источника со сколь угодно малой вероятностью ошибки (или со сколь угодно малой ненадежностью). Если H(U) > C, то можно закодировать сообщение таким образом, что нена­дежность в единицу времени будет меньше, чем H(U) – C+ ε, то H’(U / U*) < H’(U) – C+ ε (прямая теорема).
Не существует способа кодирования обеспечивающего ненадежность в единицу времени меньшую, чем H(U)-C (обрат­ная теорема).

В такой формулировке эта теорема была дана самим Шенноном. В литературе часто вторая часть прямой тео­ремы и обратная теорема объединяются в виде обратной теоремы сформулированной так: если H(U) > C, то такого способа кодирования не существует. Для доказательства первой части прямой теоремы воспользуемся результатами рассмотрения (см. п.2.2) множества длинных последовательностей элементарных дискретных сообщений источника, распадающегося как показано в п.2.2 на подмножества высоко вероятных или типичных и мало вероятных или нетипич­ных последовательностей. Пусть при некотором ансамбле входных сигналов дискретного канала Z обеспечивается пропускная способность канала C = I(Z,Z*)=H(Z) – H (Z/Z*) (2.16).

В соответствии с равенством (2.4) число типичных последовательностей входных сигналов канала достаточно большой длительности Т (содержащих большое число символов К) равно K₁(Z)=2^{K H(Z)} (2.17).

Поскольку H’(Z)= V_k H(Z), где V_k количество символов кода Z переданных в единицу времени Т=К/V_k, то

,

поэтому равенство (2.17) можно записать в виде

(2.18).

Передаче подлежат сообщения выдаваемые дискретным источником U с производительностью меньше H’(U)< C= H’(Z) – H’ (Z/Z*), откуда следует

H’(U)+H’ (Z/Z*)< H’(Z) (2.19).

Поскольку H’(Z/Z*) > 0 из (2.19) вытекает, что H’(U)< H’(Z) (2.20). При этом число типичных последователь­ностей источника достаточно большой длительности Т, аналогично (2.18) можно определить так

(2.21).

Вследствие условия (2.20) число типичных последовательностей канала значительно превосходит типичное число последовательностей источника

(2.22).

Осуществим кодирование типичных последовательностей источника. В процессе кодирования каждой типич­ной последовательности источника поставим в соответствие одну из типичных последовательностей канальных сигна­лов. Нетипичные последовательности сообщений длительности Т (если источник все же выдаст одну из них) передавать не будет, соглашаясь с тем, что каждая такая последовательность будет принята ошибочно. Выполним указанное коди­рование всеми возможными способами и усредним вероятность ошибок по всему этому большому (вследствие (2.22)) классу возможных систем кодирования. Это равносильно вычислению вероятности ошибок при случайном связывании типичных последовательностей источника сообщений и канальных сигналов. Очевидно, что число возможных кодов М равно числу размещений из K1(Z) числу элементов по K1(U) . Для того, чтобы оценить среднюю вероят­ность ошибки отметим следующее. Пройдя через канал каждая из типичных последовательностей канала может в след­ствии воздействия помех преобразоваться в такое количество типичных последовательно­стей выхода (образованием маловероятных нетипичных последовательностей выхода будем пренебрегать). В свою оче­редь в следствии ненадежности канала H(Z/Z*) каждая типичная выходная последовательность может быть обусловлена одной из (2.23) типичных входных канальных последовательностей. Данная ситуация иллюст­рируется на рисунке 2.2. Предположим, что наблюдается некоторая входная последовательность Z* которая могла быть образована K₁(Z/Z*) типичными входными последовательностями канала. Если среди этой совокупности входных последовательностей канала содержится только одна из числа использованных при кодированных источника сообщений, то очевидно она и передавалась, и следовательно соответствующая ей последовательность сообщений мо­жет быть принята верно. Ошибочный прием типичной последовательности передаваемых сообщений неизбежен лишь тогда, когда среди количества K₁(Z/Z*) последовательностей сигналов имеются две или более использованные при ко­дировании. Средняя вероятность правильного приема типичной последовательности равна вероятности того, что среди количества K₁(Z/Z*) входных последовательностей канала K₁(Z/Z*) – 1 не использовано при кодировании, а одна использована. Вероятность того, что какая-то одна типичная последовательность канальных сигналов использована при кодировании, в силу равно вероятности выбора равна

(2.24),

а вероятность того, что она не использована, определяется как

,

поскольку вероятность того, что один из канальных сигналов выбран, при кодировании равна единице. Следо­вательно средняя вероятность того, что при кодировании не использована K1(Z/Z*)-1 входных последовательностей . Полагая K₁(Z/Z*) >> 1 (что справедливо при большом Т) можно записать

(2.25).

Разлагая (2.25) в бином Ньютона и с учетом условия (2.24), ограничиваясь двумя первыми членами разложе­ния, можно записать

(2.26).

Средняя вероятность ошибочного приема типичной последовательности при достаточно больших Т или с учетом (2.21, 2.17, 2.23, 2.16).

(2.27).

Результирующая средней вероятности ошибки с учетом возможности появления и нетипичных последователь­ностей с суммарной вероятностью δ она равна

(2.28).

Поскольку по условию теоремы (2.15) C–H’(U) > 0, то как следует из (2.27 и 2.28) с ростом Т , так как при этом стремятся к нулю как (см.2.27) так и δ (см. п.2.2). Следовательно, при любом заданном ε₀ > 0 можно выбрать столь большое Т, что будем иметь , но если среднее некоторого множества чисел не больше чем ε₀, то в этом множестве должно существовать по крайней мере одно число меньше ε₀. Поэтому среди всех возможных М кодов обеспечивающих среднее значение обязательно существует хотя бы один у которого вероятность ошибки не превы­шает . Таким образом первая часть теоремы Шеннона доказана.

Вопрос 21: Доказательство второй части прямой теоремы Шеннона для канала с шумом и обратной тео­ремы.

В

литературе часто вторая часть прямой теоремы и обратная теорема объединяются в виде обратной теоремы сформули­рованной так: если H(U) > C, то такого способа кодирования не существует.

Вторую часть прямой теоремы легко доказать исходя из того, что можно просто передавать С бит в секунду от источника сообщений совсем пренебрегая остатком создаваемой информации. В приемнике это не учитываемая часть создаст ненадежность в секунду времени H’(U)-C, а передаваемая часть в соответствии с доказанным выше добавит ε.
Доказательство обратной теоремы произведем методом от противного. Рассмотрим сначала ее формулировки предложен­ные Шенноном. Предположим, что производительность источника сообщений равна H’(U)=C+а, где а > 0. По условию теоремы минимально достижимое в этом случае значение ненадежности

.

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

,

это противоречит определению пропускной способности как максимальной скорости передачи информации по ка­налу, что и доказывает теорему.
Рассмотрим вторую формулировку обратной теоремы. Положим, что источник сообщений имеет производительность H’ (U)=C+ ε > C, где ε > 0. И с помощью некоторого способа кодирования достигается ненадежность равная H’ (U/U*)= ε /2. Опять же это эквивалентно реализации скорости передачи информации

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

Физический смысл эффекта повышения вероятности при увеличении длительности кодируемых сообщений вытекающего из доказательства прямой теоремы заключается в том, что с ростом Т увеличивается степень усреднения шума действующего в канале и, следовательно, уменьшается степень его мешающего воздействия. Кодирование сообще­ний длительности Т способом предполагаемым при доказательстве теоремы Шеннона может начаться лишь то­гда, когда сообщение целиком поступило на кодирующее устройство. Декодирование же может начаться, когда вся приня­тая последовательность поступила на декодирующее устройство. Поэтому задержка сообщений во времени между пунктами связи t_связи=2T+t₀, где t₀ - время затрачиваемое на кодирование. Декодирование и прохождение по каналу. При большом Т можно принять, что t_связи=2Т. Из (2.27) следует важный результат: верность связи тем выше (меньше вероят­ность ошибки), чем длиннее блок кодированной последовательности (т.е. тем больше разность С-H’(U) определяющей запас пропускной способности канала). Итак, следует принципиальная возможность обмена между вероятностью, за­держкой и скоростью передачи информации. На практике сложность кодирования и декодирования существенно воз­растают с ростом Т поэтому в современных условиях чаще предпочитают иметь умеренное значение Т и добиваться увеличения вероятности за счет менее полного использования пропускной способности канала.

Вопрос 22: Методика построения помехоустойчивых кодов и информационные пределы избыточности.

К

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

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

Рассмотрим принцип построения помехоустойчивых блочных кодов. Избыточность обуславливающая коррек­тирующие свойства равномерного блочного кода обычно вводится за счет выполнения неравенства mⁿ > M (2.29), где m-основание кода т.е. объем алфавита используемых кодовых символов, n-длина или количество разрядов кодовой комби­нации, М-количество сообщений подлежащих кодированию. Выполнение этого неравенства означает, что для передачи знаков сообщения используют лишь часть М возможных кодовых комбинаций. Используемые кодовые комбинации называют разрешенными. Неиспользуемые mⁿ – M комбинации являются запрещенными. На вход канала подаются только разрешенные комбинации. Если вследствие помех один или несколько символов приняты ошибочно, то на вы­ходе канала появляется запрещенная комбинация, что и говорит о наличии ошибки. Для того, чтобы обеспечить выпол­нение (2.29) необходимо выбирать n  K, где К-минимальное целое, удовлетворяющее неравенству m^K M (2.30). Число К обычно называют количеством информационных разрядов кодовой комбинации, поскольку именно столько разрядов должна содержать комбинация кода с основанием m, чтобы число разных кодовых комбинаций было не меньше числа сообщений М подлежащих передаче. r =n – K разрядов кодовой комбинации необходимых для передачи полезной информации называются проверочными. Количество их и определяет избыточность помехоустойчивого кода. При использовании помехоустойчивого кода возможно декодирование с обнаружением и исправлением ошибок. В пер­вом случае на основе анализа принятой комбинации выясняется, является ли она разрешенной или запрещенной. После этого запрещенная комбинация либо отбрасывается, либо уточняется путем посылки запроса на повторение переданной информации. Во втором случае при приеме запрещенной комбинации определенным способом выявляются и исправля­ются содержащиеся в ней ошибки. Максимальные числа ошибок в кодовой комбинации q и S которые могут быть обна­ружены (q) или исправлены (S) с помощью данного кода называются соответственно обнаруживающей или исправляю­щей способностью кода. В значении q и S определяются величиной d_min минимальным кодовым расстоянием между ближайшими разрешенными комбинациями. Под кодовым расстоянием понимают количество неодинаковых разрядов в кодовых комбинациях. Величина d_min в помехоустойчивом коде зависит от соотношения n и К т.е. от числа r провероч­ных разрядов кода.

Рассмотрим информационный (т.е. базирующий на идеях Теории Информации) подход позволяющий оценить необходимую минимальную избыточность, выраженную в количестве проверочных разрядов r_min блочного помехо­устойчивого кода длиной n с заданной исправляющей способностью S. Пусть имеется код с основанием m и с исправ­ляющей способностью S. И используется декодирование с исправлением ошибок. На приеме при использовании такого кода возможно две ситуации: правильный прием сообщения и неправильный. Осуществление с вероятностью PH. Не­правильный прием может произойти в том случае, когда из-за превышения числом ошибок пришедшей из канала кодо­вой комбинации значение S она может превратиться в одну из других разрешенных кодовых комбинаций. В свою оче­редь правильный прием осуществляется либо в том случае, когда в принимаемой комбинации отсутствуют ошибки (обозначим вероятность такого сообщения Р₀), либо N_прав в случаях когда в принятой комбинации присутствуют ошибки которые могут быть исправлены рассмотренным кодом. Вероятности таких случаев обозначим через P_j, где j=1.. Nправ. Для решения поставленной задачи определим минимальное количество информации, которой может быть описана совокуп­ность событий, включающая появление одной из конкретных ошибок и отсутствие ошибок или появление не­корректных ошибок. Зная эту величину и максимальное количество информации которое может содержать один прове­рочный символ кода можно определить минимальное число проверочных символов.

Количество информации необходимо для описания указанных событий

(2.31)

(в случае отсутствия ошибки учтем включением нуля в предел суммирования). Максимальное количество ин­формации которое может содержать символ кода с основанием m в соответствии с (1.6) равно log2m. Следовательно, число проверочных разрядов в комбинации кода не может быть меньше, чем (2.32).

Определенную таким образом величину r_min называют информационным пределом избыточности. Найдем значение r_min для двоичного канала с независимыми ошибками. В таком канале появление предыдущей ошибки не вле­чет за собой появление последующей. В этой ситуации число R(i) ошибок кратности i в кодовой комбинации длиной n равно числу сочетаний .

(2.33).

Поскольку ошибки независимы вероятность P(i) возникновения в кодовой комбинации ошибки кратности i равна

P(i)=Pⁱ(1-P)^n-i (2.34),

где Р-вероятность ошибки в канале. Учитывая, что в данном случае N_пр=S выражение (2.31) можно записать в виде

.

Вторым слагаемым можно пренебречь поскольку, описываемая им функция не используется в процессе ис­правления ошибок. Поэтому с учетом (2.23 и 2.24) имеем

(2.35).

Рассмотрим частный случай когда возникновение конкретной ошибки любой кратности и отсутствие ошибок имеют равную вероятность, т.е. Pⁱ (1-P)^n-i=P₁ при любом i. Величину Р1 определим из условия нормировки

(2.36),

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

Следовательно, (2.37).

Поскольку под двоичной, то есть m=2 c учетом (2.37 и 2.38) имеем

.

Найденное таким образом значение r_min совпадает с оценками полученными другим методами в частности с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в па­кеты различной кратности. Полученные при этом результаты так же хорошо согласовывается с выводами полученными другими методами. Найденное таким образом значение rmin совпадает с оценками, полученными другими методами, в частности, с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточ­ности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Получаемые при этом результаты также хорошо согласуются с выводами, полученными другими методами.

Вопрос 23: Непрерывные сообщения. Квантование и дискретизация.

В

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

1) преобразование непрерывных сообщений в дискретные и передача их по дискретным каналам;

2) передача по непрерывным каналам.

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

Рассмотрим вначале непрерывное сообщение, представляющее собой процесс X (k∆t) с дискретным временем, т.е. совокупность отсчетов непрерывной случайной величины Х. Одна из возможных реализаций такого процесса пред­ставлена на рисунке 3.1. Истинные значения сигнала в каждый момент времени показаны точками.

Предположим, что все возможные (или по крайней мере наиболее вероятные) значения отсчетов процесса со­средоточены в диапазоне от x_min до x_max. Разобьем весь этот диапазон на конечное число

(3.1.а)

интервалов ∆x и границы этих интервалов х_к-1, х_к, х_к+1 и т.д. будем считать разрешенными значениями уровней отсчетов процесса. При этом число разрешенных уровней Ny=N-1. (3.1.б) Процедура округления истинного значения отсчета до значения ближайшего разрешенного уровня называется квантованием или дискретизацией по значению (уровню) (ок­ругленные значения сигнала на рисунке показаны кружочками). Очевидно, что после осуществления операции кванто­вания непрерывная случайная величина Х превращается в дискретную, т.е. имеющую конечное число возможных зна­чений, а непрерывное сообщение - в последовательность элементарных дискретных сообщений источника с объемом алфавита Nу. Из определения операции квантования следует, что ей присуща неизбежная потеря информации, обусловлен­ная наличием погрешности квантования k. Анализ этой погрешности проведем далее, здесь же отметим, что ее значение (а, следовательно, и количество теряемой из-за нее информации) является контролируемым и может быть сделано необходимо малым путем выбора достаточного количества Nу разрешенных уровней шкалы квантования (вследствие соответствующего уменьшения шага квантования). Таким образом, непрерывные сообщения, описываемые процессом с дискретным временем, с помощью квантования отсчетов процесса с контролируемой точностью могут быть преобразованы в дискретные.