Теоремы Шеннона для канала с шумом

Теория информации
Собственная информация Информационная энтропия Дифференциальная энтропия Условная энтропия Энтропия объединения Взаимная информация Условная взаимная информация Относительная энтропия Энтропийная скорость
Избыточность информации Скорость передачи информации Пропускная способность канала
Теорема Шеннона для канала без шума Теоремы Шеннона для канала с шумом Теорема Шеннона — Хартли

Теоремы Шеннона для канала с шумами — теоремы, которые определяют максимальную скорость создания информации в канале связи c шумом, при которой можно передавать информацию со сколь угодно малой вероятностью ошибок^[1].

Дискретным каналом связи называется канал, на входе и выходе которого сигналы дискретны (имеют цифровую форму). Дискретный канал находится между входом модулятора (выходом кодера) передатчика и выходом демодулятора (входом декодера) приёмника.

В статье Клода Шеннона «Математическая теория связи», опубликованная в 1848 году, теорема для дискретного канала с шумом сформулирована следующим образом^[2]:

Пусть дискретный канал обладает пропускной способностью ${\displaystyle C}$, а дискретный источник — энтропией в секунду ${\displaystyle H'(A)}$. Если ${\displaystyle H'(A)\leq C}$, то существует такая система кодирования, что сообщения (символы) источника могут быть переданы по каналу с произвольно малой частотой ошибок (или со сколь угодной малой ненадёжностью).

Если ${\displaystyle H'(A)>C}$, то можно закодировать источник таким образом, что ненадежность в секунду будет меньше чем ${\displaystyle H'(A)-C+\epsilon }$, где ${\displaystyle \epsilon }$ сколь угодно мало.

Не существует способа кодирования, обеспечивающего ненадежность в секунду, меньшую чем ${\displaystyle H'(A)-C}$.

В передатчике при кодировании множество символов источника ${\displaystyle A}$ переводится в множество кодовых символов ${\displaystyle X}$ (входных символов канала). В приёмнике при декодировании множество принятых кодовых символов ${\displaystyle Y}$ (выходных символов канала) переводится в множество декодированных символов источника ${\displaystyle B}$. Различие символов ${\displaystyle X}$ от ${\displaystyle Y}$ и, следовательно, ${\displaystyle A}$ от ${\displaystyle B}$ связано с шумом.

В теореме использованы следующие термины:

• Пропускная способность канала ${\displaystyle C}$ равна максимальной скорости передачи информации по каналу связи, где максимум ищется по всевозможным распределениям вероятностей входных символов канала ${\displaystyle X}$.

• Энтропия источника в секунду ${\displaystyle H'(A)}$ называется производительностью источника (скоростью создания информации) и равна произведению средней скорости передачи символов источника ${\displaystyle \nu _{s}=1/T_{s}}$ на энтропию источника ${\displaystyle H(A)}$: ${\displaystyle H'(A)=\nu _{s}H(A)}$, ${\displaystyle T_{s}}$ — средняя длительность символа источника^[3].

• Частота ошибок — это вероятность ошибочного приема символа, равная отношению числа ошибочно принятых символов источника к общему числу переданных символов источника, при числе переданных символов, стремящихся к бесконечности.

• Ненадежность в секунду равна произведению средней скорости передачи кодовых символов ${\displaystyle \nu _{c}=1/T_{c}}$ на ненадежность ${\displaystyle H(X|Y)}$:

${\displaystyle H'(X|Y)=\nu _{c}H(X|Y)}$, где ${\displaystyle T_{c}}$ — длительность кодового символа, ненадежность ${\displaystyle H(X|Y)}$ является условной энтропией и представляет собой среднее количество информации, теряемой при её передаче по каналу связи и являющейся мерой неопределённости принятых кодовых символов ${\displaystyle Y}$ (выходных символов канала)^[4][5]. Ненадежность зависит от вероятности ошибочного приема кодовых символов^[6]. Чем меньше вероятность ошибочного приема, тем меньше ненадёжность. В канале без шума вероятность ошибочного приема равна нулю, поэтому ненадежность также равна нулю.

В случае кодирования символов источника независимыми кодовыми символами с основанием алфавита ${\displaystyle D}$ и их передачи по дискретному ${\displaystyle D}$-ичному симметричному каналу, то есть для которого алфавиты на входе и выходе канала одинаковы, априорные вероятности входных и выходных символов канала одинаковы и вероятности перехода из входного символа ${\displaystyle x_{i}}$ в выходной символ ${\displaystyle y_{j}}$ определяются как: ${\displaystyle p(x_{j}|y_{i})={\begin{cases}{\frac {p_{\text{ош}}}{D-1}},i\neq j\\1-p_{\text{ош}},i=j\\\end{cases}}}$, ненадежность равна:

${\displaystyle H(X|Y)=-(1-p_{\text{ош}})\log _{2}(1-p_{\text{ош}})-p_{\text{ош}}\log _{2}{\frac {p_{\text{ош}}}{D-1}}.}$

где ${\displaystyle p_{\text{ош}}}$ — вероятность ошибочного приёма кодового символа^[7].

Следовательно, для ${\displaystyle D}$-ого симметричного канала пропускная способность ${\displaystyle C=\nu _{c}\max\{H(X)-H(X|Y)\}}$ равна^[8]:

${\displaystyle C={\frac {1}{T_{c}}}(\log _{2}(D)+(1-p_{\text{ош}})\log _{2}(1-p_{\text{ош}})+p_{\text{ош}}\log _{2}{\frac {p_{\text{ош}}}{D-1}}),}$

так как ${\displaystyle \max\{H(X)\}=\log _{2}(D)}$.

В случае, когда символы источника независимы и равновероятны и имеют основание алфавита равное ${\displaystyle M}$, производительность источника равна своему максимальному значению: ${\displaystyle H'(A)=\nu _{s}H(A)={\frac {1}{T_{s}}}\log _{2}(M)}$.

Таким образом, отношение длительности кодового символа к длительности символа источника равно:

${\displaystyle {\frac {T_{c}}{T_{s}}}={\frac {\log _{2}(D)+(1-p_{\text{ош}})\log _{2}(1-p_{\text{ош}})+p_{\text{ош}}\log _{2}{\frac {p_{\text{ош}}}{D-1}}}{\log _{2}(M)}}{\frac {H'(A)}{C}}.}$

Следовательно, из теоремы кодирования для дискретного канала с шумом условие достижения сколь угодно малого значения вероятности ошибочного декодирования приобретает вид:

${\displaystyle {\frac {T_{c}}{T_{s}}}\leq {\frac {\log _{2}(D)+(1-p_{\text{ош}})\log _{2}(1-p_{\text{ош}})+p_{\text{ош}}\log _{2}{\frac {p_{\text{ош}}}{D-1}}}{\log _{2}(M)}}.}$

Для двоичных алфавитов источника и канала (${\displaystyle M=D=2}$) имеем^[9]:

${\displaystyle {\frac {T_{c}}{T_{s}}}\leq 1+(1-p_{\text{ош}})\log _{2}(1-p_{\text{ош}})+p_{\text{ош}}\log _{2}{p_{\text{ош}}}.}$

Так как ${\displaystyle (1-p_{\text{ош}})\log _{2}(1-p_{\text{ош}})+p_{\text{ош}}\log _{2}{p_{\text{ош}}}}$ всегда меньше нуля при наличии шума (${\displaystyle p_{\text{ош}}>0}$), то получаем:

${\displaystyle {\frac {T_{c}}{T_{s}}}<1.}$

Это условие означает, что скорость поступления кодовых символов в канал ${\displaystyle \nu _{c}}$ должна быть выше скорости поступления символов источника в кодер ${\displaystyle \nu _{s}}$. Таким образом, на один бит источника кодер канала в среднем должен сформировать ${\displaystyle {\frac {T_{s}}{T_{c}}}>1}$ кодовых битов. Это означает необходимость введения кодером избыточности. Такое преобразование символов кодером, предполагающее введение избыточности, является главным принципом помехоустойчивого канального кодирования^[10].

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

Однако теорема кодирования для дискретного канала с шумом не указывает конкретного способа кодирования. Приближение производительности источника к значению пропускной способности канала связано с увеличением длины кодовых комбинаций и, как следствие, усложнением методов кодирования и декодирования^[10].

Непрерывным каналом связи называется канал, на входе и выходе которого сигналы непрерывны (имеют аналоговую форму). Непрерывный канал находится между выходом модулятора передатчика и входом демодулятора приёмника.

В статье Клода Шеннона «Математическая теория связи», опубликованная в 1848 году, теорема для непрерывного канала с шумом сформулирована следующим образом^[11]:

Если источник при заданной оценке ${\displaystyle v}$ имеет скорость создания сообщений ${\displaystyle R}$, то можно закодировать сообщения на выходе источника и передавать их по каналу с пропускной способностью ${\displaystyle C}$ при точности воспроизведения, как угодно близкой к ${\displaystyle v}$, если только ${\displaystyle R\leq C}$. Это невозможно, если ${\displaystyle R>C.}$

В качестве оценки ${\displaystyle v}$ можно использовать среднеквадратичный критерий^[12]:

${\displaystyle v={\frac {1}{T}}\int \limits _{0}^{T}(y(t)-x(t))^{2}dt,}$

где ${\displaystyle x(t)}$ — передаваемый сигнал (сигнал на входе канала), ${\displaystyle y(t)}$ — принятый сигнал (сигнал на выходе канала), ${\displaystyle T}$ — длительность сигналов.

Достижение такого результата предполагает кодирование достаточно длинных последовательностей символов источника соответствующими сигналами^[13].

Теорема кодирования для непрерывного канала с шумом может быть также сформулирована следующим образом^[13]:

Дискретные сообщения источника с производительностью ${\displaystyle H'(A)}$ могут быть переданы по каналу с пропускной способностью ${\displaystyle C}$ с вероятностью ошибки, сколь угодно близкой к нулю, если ${\displaystyle H'(A)<C}$. Если же ${\displaystyle H'(A)>C}$, то такая передача невозможна.

Пропускная способность дискретного канала с шумом не может превышать пропускную способность соответствующего непрерывного канала^[13].

Пропускная способность непрерывного канала с полосой частот ${\displaystyle \Delta F}$, по которому передаётся сигнал со средней мощностью ${\displaystyle P_{s}}$ и в котором имеется аддитивный белый гауссовский шум (АБГШ) с мощностью ${\displaystyle P_{n}}$ определяется по формуле Шеннона-Хартли^[14]:

${\displaystyle C=\Delta F\log _{2}(1+{\frac {P_{s}}{P_{n}}}).}$

Формулу для пропускной способности непрерывного канала с АБГШ можно переписать в виде, получив формулу, называемую границей Шеннона^[15]:

${\displaystyle \beta _{E}=(2^{1/\beta _{F}}-1)\beta _{F}}$,

где ${\displaystyle \beta _{E}={\frac {E_{b}}{N_{0}}}={\frac {P_{s}}{P_{n}}}{\frac {\Delta F}{R}}}$ — удельные энергетические затраты, ${\displaystyle E_{b}}$ — энергия сигнала, затрачиваемая на передачу одного бита информации, ${\displaystyle N_{0}}$ — спектральная плотность мощности шума,

${\displaystyle \beta _{F}={\frac {\Delta F}{C}}}$ — удельные затраты полосы частот.

Так как по условию теоремы для безошибочного воспроизведения сообщений необходимо выполнение условия ${\displaystyle R<C}$, то удельные энергетические затраты должны удовлетворять следующему неравенству:

${\displaystyle \beta _{E}>(2^{1/\beta _{F}}-1)\beta _{F},}$

то есть величина ${\displaystyle \beta _{E}}$ должна быть выше границы Шеннона^[15].

При величине ${\displaystyle \beta _{F}\rightarrow \infty }$ минимально возможное значение ${\displaystyle \beta _{E}=\ln(2)=0.693}$, называемое пределом Шеннона^[16]. Таким образом, величина удельных энергетических затрат для канала с АБГШ, даже при ${\displaystyle \beta _{F}\rightarrow \infty }$, должна превосходить значение ${\displaystyle \ln(2)}$^[17].

• Габидулин Э. М., Пилипчук Н. И. Лекции по теории информации — МФТИ, 2007. — 214 с. — ISBN 978-5-7417-0197-3
• Варгаузин, В.А., Цикин, И.А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи - СПб.: БХВ-Петербург, 2013 - 352 с. - ISBN 978-5-9775-0878-0