Теорема кодирования в дискретном канале с помехами.

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

Если то неравенство (6.48) при произвольном 5 не выполняется, как бы ни бьию велико по. Данная теорема, вообще говоря, справедлива для достаточно широкого класса (хотя и не для всех) каналов с памятью, но мы её докажем лишь для канала без памяти и для совпадающих входных и выходных алфавитов канала, поскольку в противном случае доказательство заметно усложняется (см., например, [16]).

Доказательство. Докажем сначала прямую часть теоремы, т.е. факт, что (6.48) выполняется при где Пусть пропускная способность канала достигается при некотором распределении вероятностей входных символов Будем тогда называть последовательность длиной , составленную из входных символов канала, -типичной, если неравенство (6.40) (с очевидной заменой на на выполняется для нее при входном распределении Аналогично будем называть последовательность выходных символов -условной типичной последовательностью для е-типичной входной последовательности, если для нее выполняется неравенство (6.45), в котором входное распределение задаётся как а переходные вероятности определяются каналом связи.

Предположим, что уже построены блочный код и решающая схема удовлетворяющие следующим условиям:

1. Все комбинации кода являются -типичными последовательностями.

2. Множества содержат все -условные типичные последовательности для каждого из которые не входят в объединение предыдущих множеств, т.е. в

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

4. Выбранный код не может быть расширен путём присоединения к нему ещё одной комбинации и множества для которых выполняется условие 1-3.

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

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

Рис. 6.4. Пояснение доказательства теоремы кодирования

1. Для любой -типичной (относительно входной последовательности

3. Р - -условная типичная выходная последовательности)

такое чтобы неравенство (6.48) выполнялось с вероятностью, большей 1—8.

Пусть любая -типичная последовательность, не входящая в код, тогда вероятность того, что при передаче на выходе появится -типичная условная последовательность которая попадает в будет не меньше 8. Действительно, если это не так, можно присоединить к коду и выбрать как множество выходных -условных типичных последовательностей для не вошедших в . В этом случае т.е. расширенный код удовлетворяет условиям 1-3, что противоречит условию 4. Если же передаётся кодовая комбинация то из условий 1-3 видно, что вероятность появления на выходе -типичной условной последовательности, попадающей в будет не менее чем таким образом, при достаточно больших (малых 8) также не менее чем 8. Следовательно, какая бы -типичная последовательность относительного входного распределения ни передавалась, вероятность того, что на выходе канала появится последовательность, принадлежащая будет не меньше

В соответствии с теоремой САР с увеличением длин блоков вероятность появления -типичной входной последовательности приближается к единице и, таким образом, начиная с некоторого становится не меньше постоянной Поэтому при достаточно больших безусловная вероятность появления на выходе последовательности, попадающей в будет не меньше чем Для выходных последовательностей будет также справедлива теорема согласно которой при достаточно больших вероятность появления определённой типичной выходной последовательности оказывается не больше чем

Множество состоит именно из -типичных выходных последовательностей, этому число элементов не меньше чем С другой стороны, -условных типичных выходных последовательностей при заданной -типичной входной последовательности не превосходит Отсюда следует, что число должно удовлетворять неравенству

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

где род вероятность ошибки декодирования блока символов. (Если условие (6 49) не выполняется, то всегда можно изменить решающую схему так, чтобы уменьшить максимальную вероятность ошибки и выполнить это условие для некоторой величины Теперь код вместе с решающей схемой можно рассматривать как расширенный с вероятностями переходов (6.49) и объёмами входного и выходного алфавитов равными Тогда количество информации передаваемой по такому каналу, не может превосходить его пропускной способности, равной Если это количество информации отнести к одному символу то оно, очевидно, не может превзойти пропускной способности С исходного канала, так

как любые преобразования не увеличивают количества информации (см. свойство 8 количества информации) Поэтому получаем неравенство

Предположим, что т.е. тогда, подставляя это значение в (6 50), получаем неравенство

Отсюда видно, что при левая часть (6.51) всегда стремится к нулю, если . Однако это невозможно, поскольку правая часть ограничена отрицательной постоянной. Итак, если где то достижение сколь угодно малой ошибки декодирования путём увеличения длин блоков и от при любом выборе кода и решающей схемы оказывается невозможным. Это и завершает доказательство обратной теоремы.

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

и по условию отсутствия задержек во времени:

где — длительности символов источника и канала, соответственно, получаем, что

Как следует из доказанной теоремы кодирования, при когда и поэтому получаем условие на максимально возможную скорость передачи символов в следующем виде:

В частном случае двоичного источника получаем из (6.52) скорость передачи символов

Предположим, что будет учитываться статистика источника сообщений, т.е. производится дополнительно и кодирование источника сообщений. Тогда, как следует из теоремы 1 о кодировании источника, средняя длина последовательности канальных символов, приходящаяся на один символ источника сообщений, будет определяться соотношением (6.46). Будем полагать, что в нашем случае символами канала являются кодовые комбинации длины число которых равно Тогда в (6.46) необходимо положить Условие отсутствия задержек во времени примет в этом случае следующий вид (в пренебрежении величиной в (6.46)):

Поскольку для обеспечения при согласно доказанной теореме с кодированием в канале с помехами необходимо обеспечить выполнение неравенства то из предыдущего выражения находим

Неравенство (6.53) составляет основную теорему Шеннона, которая формулируется следующим образом.

Теорема 2. Основная теорема Шеннона.

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

Заметим, что хотя неравенство (6.53) и является более сильным, чем (6.52), но это не означает, что всегда следует использовать как канальное кодирование, так и кодирование источника. Последнее для достижения заметного эффекта может оказаться нереализуемо сложным.

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

До сих пор в данной главе мы всюду рассматривали так называемый дискретный канал связи с помехами. В действительности таких каналов не существует и можно говорить лишь о модели отображения непрерывного каната связи в дискретный. По существу это означает, что мы в рамках рассмотрения данного дискретного канала фиксируем определённый способ модуляции и демодуляции. Если нам дополнительно известно, какой именно выбран способ модуляции и демодуляции, то может быть известна и вероятность ошибки как функция параметра уже упоминавшегося в § 6.1. Предположение о том, что при фиксированных значениях мы можем изменять длительность канальных символов что эквивалентно изменению канальной скорости передачи открывает новые возможности для оптимизации системы связи. Так можно поставить вопрос об оптимизации величины с целью обеспечения наибольшей пропускной способности канала связи в единицу времени С, что согласно теореме кодирования обеспечит наибольшую скорость передачи сообщений источника при сколь угодно высокой верности приёма. Эта задача для сводится к нахождению максимума функции:

где поскольку

Приведём (6.54) к более удобному виду для нахождения максимума

В гл. 5 было показано, что при оптимальном когерентном приёме двоичных сигналов в детерминированном канале с БГШ вероятность ошибки как функция определяется выражением

где

При оптимальном некогерентном приёме в том же самом канале мы получили в гл. 5

где

Подставляя (6.56) и (6.57) в (6.55) и находя экстремум функции обычными аналитическими и численными методами [26], получаем, что для когерентного приёма максимум достигается при и оказывается равным При некогерентном приёме максимум С достигается при и оказывается равным

Таким образом, максимум при когерентном приёме двоичных сигналов достигается при неограниченной полосе пропускания приёмника поскольку при в то время как при некогерентном приёме максимум С реализуется при ограниченной полосе частот канала связи. (Очевидно, однако, что при любой скорости передачи и одних и тех же значениях когерентный приём всегда обеспечит большее значение чем некогерентный)

Допустимость изменения длительностей канальных символов при фиксированном способе модуляции и демодуляции приводит к возможности необычной интерпретации теоремы кодирования. Предположим, что информационная скорость передачи двоичного источника бит/с задана так же, как и Возникает вопрос, можно ли при этих условиях обеспечить при каком-либо, пусть сколь угодно сложном кодировании (т.е. при ) и наилучшем выборе длительности канального символа? Как было показано раньше, максимальное значение С при оптимальном когерентном приёме двоичных сигналов достигается при и равно Поскольку согласно теореме кодирования то следовательно,

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

Если же оказалось, что для требуемой информационной скорости передачи вероятность ошибки равна или больше этой величины, то всякое кодирование с целью повышения помехоустойчивости оказывается бесполезным. (Для повышения надёжности необходимо или изменить вид модуляции, или улучшать параметры канала Проделывая аналогичные выкладки для оптимального некогерентного приёма двоичных ОФМ сигналов, можно показать, что минимальная величина оказывается равной а вероятность ошибки 0,025.

В реальных системах связи обычно задаются ограниченными значениями вероятности ошибки, не требуя выполнения условия Поэтому при

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

где мощность сигнала в системе связи без кодирования; мощность сигнала в той же системе связи, но с кодированием.

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

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

Поэтому для расчёта ЭВК при использовании кода с заданной скоростью (в том числе и в асимптотическом случае, когда соотношение (6.60) может быть представлено в следующей форме:

где отношение сигнал-шум в канале связи, обеспечивающее требуемую величину вероятности ошибочного приёма символа без кодирования; отношение сигнал-шум в канале связи, обеспечивающее требуемую величину при использовании данного кода.

Величина в этом соотношении может быть найдена как решение уравнения где вероятность ошибки для заданного способа модуляции-демодуляции и модели канала связи, как функции параметра Величина согласно теореме кодирования Шеннона может быть найдена как решение уравнения

где пропускная способность дискретного канала связи, представленная как функция параметра

В частном случае получаем уравнение

Если скорость кода не задана, то мы можем её оптимизировать, добиваясь максимизации в (6.61) при выполнении условия (6.62).

Это в свою очередь, реализуется при максимизации по величины

Как было показано раньше, эта величина при оптимальном когерентном приёме достигает максимума, когда , а следовательно при, и оказывается равной .

При оптимальном некогерентном приёме эта величина максимизируется при что соответствует оптимальному значению и "оптимальной" вероятности ошибки символа в канале связи При оптимальном значении вероятности ошибки пропускная способность становится примерно равной 0,51, что и совпадает с оптимальной скоростью кода. В этом случае, как было показано ранее, максимальное значение оказывается равным

Так, если задаться величиной то ЭВК при когерентном приёме и оптимальном выборе скорости кода составит а при оптимальном некогерентном приёме ЭВК при оптимальном выборе скорости будет равен примерно

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