Лекция: Теорема Шеннона для дискретного канала с шумом

Данная теорема является фундаментальным положением Теории Информации и называется так же основной теоремой кодирования Шеннона. Она может быть сформулирована следующим образом: если производительность источника сообщений Hў (U) меньше пропускной способности канала С т.е. Hў(U)< C то существует такая система кодирования которая обеспечивает возможность передачи сообщений источника со сколь угодно малой вероятностью ошибки (или со сколь угодно малой ненадежностью).
Если Hў(U) > C, то можно закодировать сообщение таким образом, что ненадежность в единицу времени будет меньше чем Hў(U)-C+ e, где e ®0 (прямая теорема).
Не существует способа кодирования обеспечивающего ненадежность в единицу времени меньшую, чем Hў(U)-C (обратная теорема).
В такой формулировке эта теорема была дана самим Шенноном. В литературе часто вторая часть прямой теоремы и обратная теорема объединяются в виде обратной теоремы сформулированной так: если Hў(U) > C, то такого способа кодирования не существует. Для доказательства первой части прямой теоремы воспользуемся результатами рассмотрения (см. п.2.2) множества длинных последовательностей элементарных дискретных сообщений источника, распадающегося как показано в п.2.2 на подмножества высоко вероятных или типичных и мало вероятных или нетипичных последовательностей. Пусть при некотором ансамбле входных сигналов дискретного канала Z обеспечивается пропускная способность канала C=Iў(Z,Z*)=H(Z)-H ў(Z/Z*) (2.16).
В соответствии с равенством (2.4) число типичных последовательностей входных сигналов канала достаточно большой длительности Т (содержащих большое число символов К) равно K1(Z)=2KЧ H(Z) (2.17)
Поскольку Hў(Z)=u kЧ H(Z), где uk — количество символов кода Z переданных в единицу времени Т=К/uk, то, поэтому равенство (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)) классу возможных систем кодирования. Это равносильно вычислению вероятности ошибок при случайном связывании типичных последовательностей источника сообщений и канальных сигналов. Очевидно, что число возможных кодов М равно числу размещений из K1(Z) числу элементов по K1(U). Для того, чтобы оценить среднюю вероятность ошибки отметим следующее. Пройдя через канал каждая из типичных последовательностей канала может в следствии воздействия помех преобразоваться в такое количество типичных последовательностей выхода (образованием маловероятных нетипичных последовательностей выхода будем пренебрегать). В свою очередь в следствии ненадежности канала H(Z/Z*) каждая типичная выходная последовательность может быть обусловлена одной из (2.23) типичных входных канальных последовательностей. Данная ситуация иллюстрируется на рисунке 2.2. Предположим, что наблюдается некоторая входная последовательность Z* которая могла быть образована K1(Z/Z*) типичными входными последовательностями канала. Если среди этой совокупности входных последовательностей канала содержится только одна из числа использованных при кодированных источника сообщений, то очевидно она и передавалась, и следовательно соответствующая ей последовательность сообщений может быть принята верно. Ошибочный прием типичной последовательности передаваемых сообщений неизбежен лишь тогда, когда среди количества K1(Z/Z*) последовательностей сигналов имеются две или более использованные при кодировании. Средняя вероятность правильного приема типичной последовательности равна вероятности того, что среди количества K1(Z/Z*) входных последовательностей канала K1(Z/Z*)-1 не использовано при кодировании, а одна использована. Вероятность того, что какая-то одна типичная последовательность канальных сигналов использована при кодировании, в силу равно вероятности выбора равна (2.24), а вероятность того, что она не использована, определяется как, поскольку вероятность того, что один из канальных сигналов выбран, при кодировании равна единице. Следовательно средняя вероятность того, что при кодировании не использована K1(Z/Z*)-1 входных последовательностей. Полагая K1(Z/Z*) > > 1 (что справедливо при большом Т) можно записать (2.25). Разлагая (2.25) в бином Ньютона и с учетом условия (2.24), ограничиваясь двумя первыми членами разложения, можно записать (2.26). Средняя вероятность ошибочного приема типичной последовательности при достаточно больших Т или с учетом (2.21, 2.17, 2.23, 2.16). (2.27). Результирующая средней вероятности ошибки с учетом возможности появления и нетипичных последовательностей с суммарной вероятностью d она равна (2.28). Поскольку по условию теоремы (2.15) C-Hў(U) > 0, то как следует из (2.27 и 2.28) с ростом Т, так как при этом стремятся к нулю как (см.2.27) так и d (см. п.2.2). Следовательно, при любом заданном e > 0 можно выбрать столь большое Т, что будем иметь, но если среднее некоторого множества чисел не больше чем e, то в этом множестве должно существовать по крайней мере одно число меньше e. Поэтому среди всех возможных М кодов обеспечивающих среднее значение обязательно существует хотя бы один у которого вероятность ошибки не превышает. Таким образом первая часть теоремы Шеннона доказана.
Вторую часть прямой теоремы легко доказать исходя из того, что можно просто передавать С бит в секунду от источника сообщений совсем пренебрегая остатком создаваемой информации. В приемнике это не учитываемая часть создаст ненадежность в секунду времени Hў(U)-C, а передаваемая часть в соответствии с доказанным выше добавит e.
Доказательство обратной теоремы произведем методом от противного. Рассмотрим сначала ее формулировки предложенные Шенноном. Предположим, что производительность источника сообщений равна Hў(U)=C+а, где а> 0. По условию теоремы минимально достижимое в этом случаезначение ненадежности. Мы же будем считать, что существует способ кодирования, обеспечивающий значение, где e > 0. Однако при этом оказывается реализованной скорость передачи информации, это противоречит определению пропускной способности как максимальной скорости передачи информации по каналу, что и доказывает теорему.
Рассмотрим вторую формулировку обратной теоремы. Положим, что источник сообщений имеет производительность Hў (U)=C+e > C, где e > 0. И с помощью некоторого способа кодирования достигается ненадежность равная Hў (U/U*)=e /2. Опять же это эквивалентно реализации скорости передачи информации превышающей пропускную способность, что невозможно. Это противоречие доказывает теорему.
Физический смысл эффекта повышения вероятности при увеличении длительности кодируемых сообщений вытекающего из доказательства прямой теоремы заключается в том, что с ростом Т увеличивается степень усреднения шума действующего в канале и, следовательно, уменьшается степень его мешающего воздействия. Кодирование сообщений длительности Т способом предполагаемым при доказательстве теоремы Шеннона может начаться лишь тогда, когда сообщение целиком поступило на кодирующее устройство. Декодирование же может начаться, когда вся принятая последовательность поступила на декодирующее устройство. Поэтому задержка сообщений во времени между пунктами связи tзад=2T+t0, где t0 — время затрачиваемое на кодирование. Декодирование и прохождение по каналу. При большом Т можно принять, что tзад=2Т. Из (2.27) следует важный результат: верность связи тем выше (меньше вероятность ошибки), чем длиннее блок кодированной последовательности (т.е. тем больше разность С-Hў(U) определяющей запас пропускной способности канала). Итак, следует принципиальная возможность обмена между вероятностью, задержкой и скоростью передачи информации. На практике сложность кодирования и декодирования существенно возрастают с ростом Т поэтому в современных условиях чаще предпочитают иметь умеренное значение Т и добиваться увеличения вероятности за счет менее полного использования пропускной способности канала.

Лекция 13.Методы сжатия информации с потерями, методы сжатия без потерь.Криптографическое кодирование. Помехоустойчивое кодирование. Линейные групповые коды. Тривиальные систематические коды.

Кодирование с помощью которого можно устранять ошибки обусловленные наличием шума в канале называется помехоустойчивым. Коды способные исправлять и обнаруживать ошибки называется помехоустойчивым кодом. К сожалению основная теорема кодирования Шеннона не конструктивна, она не указывает способ построения конкретного оптимальногопомехоустойчивого кода, обеспечивающего предельное согласование сигнала с каналом, существование которого доказывает. Вместе с тем обосновав принципиальную возможность построения помехоустойчивых кодов, обеспечивающих идеальную передачу. Теория Шеннона мобилизовала усилия ученых на разработку конкретных кодов. В результате в настоящее время теория помехоустойчивого кодирования превратилась в самостоятельную науку в развитии которой достигнуты большие успехи.
Рассмотрим основополагающие принципы заложенные в основу построения помехоустойчивых кодов. Как следует из доказательства основной теоремы Шеннона неприменимым свойством помехоустойчивых кодов является наличие избыточности. При этом необходима не просто любая избыточность, а специфическая, определяемая свойствами канала и правилом построения кода. И позволяющая с минимальными затратами повысить вероятность передачи. В ситуации когда источник сообщений обладает собственной существенной избыточностью, которая в принципе тоже в определенной степени повышает достоверность передачи информации, но не так эффектно как это возможно. Поступают следующим образом: сначала с помощью эффективного кодирования до минимума уменьшают избыточность источника сообщений, а затем в процессе помехоустойчивого кодирования вносят в передаваемый сигнал избыточность, позволяющую простыми средствами поднять верность. Таким образом эффективное кодирование может сочетаться с помехоустойчивым.
Помехоустойчивые коды можно подразделить на два больших класса блочные и непрерывные. В случае блочных кодов, при кодировании, каждому дискретному сообщению ставится в соответствие отдельный блок кодовых символов называемого кодовой комбинацией. Непрерывные коды образуют последовательность символов неразделяемых на кодовые комбинации.
Рассмотрим принцип построения помехоустойчивых блочных кодов. Избыточность обуславливающая корректирующие свойства равномерного блочного кода обычно вводится за счет выполнения неравенства mn >M (2.29), где m-основание кода т.е. объем алфавита используемых кодовых символов, n-длина или количество разрядов кодовой комбинации, М-количество сообщений подлежащих кодированию. Выполнение этого неравенства означает, что для передачи знаков сообщения используют лишь часть М возможных кодовых комбинаций. Используемые кодовые комбинации называют разрешенными. Неиспользуемые mn -M комбинации являются запрещенными. На вход канала подаются только разрешенные комбинации. Если вследствие помех один или несколько символов приняты ошибочно, то на выходе канала появляется запрещенная комбинация, что и говорит о наличии ошибки. Для того, чтобы обеспечить выполнение (2.29) необходимо выбирать n > K, где К-минимальное целое, удовлетворяющее неравенству mK M (2.30). Число К обычно называют количеством информационных разрядов кодовой комбинации, поскольку именно столько разрядов должна содержать комбинация кода с основанием m, чтобы число разных кодовых комбинаций было не меньше числа сообщений М подлежащих передаче. R=n-K разрядов кодовой комбинациинеобходимых для передачи полезной информации называются проверочными. Количество их и определяет избыточность помехоустойчивого кода. При использовании помехоустойчивого кода возможно декодирование с обнаружением и исправлением ошибок. В первом случае на основе анализа принятой комбинации выясняется, является ли она разрешенной или запрещенной. После этого запрещенная комбинация либо отбрасывается, либо уточняется путем посылки запроса на повторение переданной информации. Во втором случае при приеме запрещенной комбинации определенным способом выявляются и исправляются содержащиеся в ней ошибки. Максимальные числа ошибок в кодовой комбинации q и S которые могут быть обнаружены (q) или исправлены (S) с помощью данного кода называются соответственно обнаруживающей или исправляющей способностью кода. В значении q и S определяются величиной dmin минимальным кодовым расстоянием между ближайшими разрешенными комбинациями. Под кодовым расстоянием понимают количество неодинаковых разрядов в кодовых комбинациях. Величина dmin в помехоустойчивом коде зависит от соотношения n и К т.е. от числа r проверочных разрядов кода.
Рассмотрим информационный (т.е. базирующий на идеях Теории Информации) подход позволяющий оценить необходимую минимальную избыточность, выраженную в количестве проверочных разрядов rmin блочного помехоустойчивого кода длиной n с заданной исправляющей способностью S. Пусть имеется код с основанием m и с исправляющей способностью S. И используется декодирование с исправлением ошибок. На приеме при использовании такого кода возможно две ситуации: правильный прием сообщения и неправильный. Осуществление с вероятностью PH. Неправильный прием может произойти в том случае, когда из-за превышения числом ошибок пришедшей из канала кодовой комбинации значение S она может превратиться в одну из других разрешенных кодовых комбинаций. В свою очередь правильный прием осуществляется либо в том случае, когда в принимаемой комбинации отсутствуют ошибки (обозначим вероятность такого сообщения Р0), либо Nправ в случаях когда в принятой комбинации присутствуют ошибки которые могут быть исправлены рассмотренным кодом. Вероятности таких случаев обозначим через Pj j=1 ё Nправ. Для решения поставленной задачи определим минимальное количество информации, которой может быть описана совокупность событий, включающая появление одной из конкретных ошибок и отсутствие ошибок или появление некорректных ошибок. Зная эту величину и максимальное количество информации которое может содержать один проверочный символ кода можно определить минимальное число проверочных символов.
Количество информации необходимо для описания указанных событий(2.31)(в случае отсутствия ошибки учтем включением нуля в предел суммирования). Максимальное количество информации которое может содержать символ кода с основанием m в соответствии с (1.6) равно log2m. Следовательно число проверочных разрядов в комбинации кода не может быть меньше, чем (2.32). Определенную таким образом величину rmin называют информационным пределом избыточности. Найдем значение rmin для двоичного канала с независимыми ошибками. В таком канале появление предыдущей ошибки не влечет за собой появление последующей. В этой ситуации число R(i) ошибок кратности i в кодовой комбинации длиной n равно числу сочетаний .

Поскольку ошибки независимы вероятность P(i) возникновения в кодовой комбинации ошибки кратности i равна P(i)=PiЧ(1-P)n-i (2.34), где Р-вероятность ошибки в канале. Учитывая, что в данном случае Nпр=S выражение (2.31) можно записать в виде. Вторым слагаемым можно пренебречь поскольку, описываемая им функция не используется в процессе исправления ошибок. Поэтому с учетом (2.23 и 2.24) имеем (2.35). Рассмотрим частный случай когда возникновение конкретной ошибки любой кратности и отсутствие ошибок имеют равную вероятность, т.е. PiЧ(1-P)n-i=P1 при любом i. Величину Р1 определим из условия нормировки (2.36), отражающего тот факт, что вероятность появления ошибки какой-либо кратности, включения и нулевую равна единице. Из (2.36) имеем следовательно (2.37). Поскольку под двоичной, то есть m=2 c учетом (2.37 и 2.38) имеем. Найденное таким образом значение rmin совпадает с оценками полученными другим методами в частности с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Полученные при этом результаты так же хорошо согласовывается с выводами полученными другими методами. Найденное таким образом значение rmin совпадает с оценками, полученными другими методами, в частности, с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Получаемые при этом результаты также хорошо согласуются с выводами, полученными другими методами.