А.С. Холево - Введение в квантовую теорию информации, страница 9

Обратно, любой код, использующий двоичныепоследовательности длины n(H(X) − δ), имеет асимптотически неисчезающую вероятность ошибки, стремящуюся к единице при n → ∞ (задача 15 ).Поcкольку эффективное кодирование требует асимптотическиN ∼ 2nH(X) слов, энтропия H(X) может быть интерпретирована как мера количества информации (в битах на передаваемый символ) в случайномисточнике. Ясно, что для равномерного распределения px = 1/|X | энтропияH(X) = Hmax (X) = log |X | и сжатие невозможно.4.1.

КЛАССИЧЕСКАЯ ТЕОРИЯ ИНФОРМАЦИИ4.1.247Пропускная способностьканала с шумомКанал связи с шумом описывается вероятностями переходов p(y|x) из входного алфавита X в выходной алфавит Y, т. е. условными вероятностями того, что принят символ y ∈ Y, при условии, что был послан символ x ∈ X . Соответствующее уменьшение информационного содержания источника описывается шенноновским количеством информации:I(X; Y ) = H(X) − H(X|Y ),(4.6)Pгде H(X) = − x px log px энтропия источника (входа), а H(X|Y ) условная энтропия входа относительно выхода Y , которая описывает потерюинформации в канале связи:PPP px,ypx,ypy H(X|Y = y) = − y py xlog=pypyPP= − x,y px,y log px,y + y py log py = H(X, Y ) − H(Y ).H(X|Y ) =yЗдесь H(X, Y ) совместная энтропия пары случайных величин (X, Y ), соответствующая совместному распределению px,y = p(y|x)px . Подставляяэту формулу в определение шенноновского количества информации (4.6),мы видим, что оно симметрично по X и Y , и поэтому может быть такженазвано взаимной информациейI(X; Y ) = H(X) + H(Y ) − H(X, Y ) = H(Y ) − H(Y |X),(4.7)где в последней формуле уже H(Y ) может быть интерпретирована, как информационное содержание выхода, а H(Y |X) как его бесполезная составляющая, обусловленная шумом.

Взаимная информация всегда неотрицательна: тот факт, что H(X) ≥ H(X|Y ) легко вытекает из вогнутости функции−x log x (задача 16 ). Отсюда также вытекает свойство субаддитивности энтропии: H(XY ) ≤ H(X) + H(Y ). Далее, I(X; Y ) = 0 тогда и только тогда,когда X и Y независимые случайные величины: px,y = px · py .Если посылается последовательность букв, и канал p(y|x) действует независимо на каждую посланную букву, то он называется каналом без памяти.Пропускная способность такого канала определяется какC = max I(X; Y ),{px }(4.8)где максимум берется по всевозможным распределениям на входе {px }.X1 q@@Yq1p¡¡@¡ (1 − p)¡@¡@q@q 00 ¡pРис. 4.1: Двоичныйсимметричный каналВ качестве примера рассмотрим двоичный симметричный канал.

В этом случае X и Y состоят издвух букв 0, 1, которые передаются без ошибки свероятностью p. Вводя двоичную энтропиюh(p) = −p log p − (1 − p) log(1 − p),(4.9)48Глава 4. КЛАССИЧЕСКИ-КВАНТОВЫЕ КАНАЛЫвзаимную информацию можно записать как I(X; Y ) =H(X) − h(p). Максимум этой величины, равныйC = 1 − h(p),(4.10)достигается на равномерном входном распределении: p0 = p1 = 1/2.Применяя блочное кодирование для канала без памяти, когда канал используется для посылки n букв, получаемx1 −→ y1 x2 −→ y2 nx == yn.....  .xn −→ ynгде p(y n |xn ) = p(y1 |x1 )·.

. .·p(yn |xn ). Пусть Y n обозначает выход дискретногоканала без памяти со входом X n . Очевидно, что последовательность Cn =maxX n I(X n ; Y n ) супераддитивна: Cn+m ≥ Cn + Cm . Более того, можнодоказать, что она аддитивна, используя следующую лемму:Л е м м а 2.I(X n ; Y n ) ≤nXI(Xi ; Yi ).(4.11)i=1Доказательство. Имеет место цепное правило для условной энтропии:H(X1 , . . . , Xn ) =nXH(Xi |X1 , . .

. , Xi−1 ),(4.12)i=1которое легко доказать по индукции, используя формулу:H(X, Y ) = H(X) + H(Y |X).(4.13)Тогда взаимная информацияI(X n ; Y n ) = H(Y n ) − H(Y n |X n ) =nX= H(Y n ) −H(Yi |Y1 , . . . , Yi−1 , X n ) =i=1= H(Y n ) −nXH(Yi |Xi ),i=1поскольку для канала без памяти Yi зависит только от Xi и, таким образом,nnI(X ; Y ) ≤nXi=1(H(Yi ) − H(Yi |Xi )) =nXi=1I(Xi ; Yi ).4.1. КЛАССИЧЕСКАЯ ТЕОРИЯ ИНФОРМАЦИИ49Беря максимум выражения (4.11), получаем аддитивность, в частности,Cn = nC.О п р е д е л е н и е . Кодом (W, V ) размера N для канала p(y|x)называется совокупность N слов w(1) , . . .

, w(N ) длины n вместе сразбиением множества Y n на N непересекающихся подмножествV (0) , V (1) , . . . , V (N ) ⊂ Y n . Подмножества V (1) , . . . , V (N ) интерпретируютсякак облaсти принятия решения: если на выходе принято значение y n ∈V (j) ; j = 1, . . . , N , то принимается решение, что было послано слово w(j) ;если же принято y n ∈ V (0) , то никакого определенного решения не принимается.

Таким образом, максимальная вероятность ошибки такого кодаесть³´Pe (W, V ) = max1≤j≤N1 − p(V (j) |w(j) ) ,(4.14)где p(V (j) |w(j) ) = P(Y n ∈ V (j) |X n = w(j) ). Средняя вероятность ошибкиравнаN´1 X³P e (W, V ) =1 − p(V (j) |w(j) ) ≤ Pe (W, V ),(4.15)N i=1и, как показывает следующая лемма, с точки зрения теории информацииона асимптотически эквивалентна максимальной вероятности ошибки Pe (W, V ).Л е м м а 3. Пусть код размера 2N имеет среднюю вероятность ошибкиP e (W, V ) < ².

Тогда найдется подкод размера N , имеющий максимальнуювероятность ошибки Pe (W, V ) < 2².Доказательство. Предположим, что среди 2N слов имеется по крайнеймере N + 1 слово с вероятностью ошибки p(V (j) |w(j) ) ≥ 2², так что построить требуемый N -подкод невозможно.

Тогда средняя ошибка 2N -кода1ограничена снизу величиной P e (W, V ) ≥ 2N2²(N +1) > ², что противоречитпредположению. ¤b=Л е м м а 4 (Неравенство Фано). Пусть X, Y случайные величины и XbbX(Y ) оценка случайной величины X с вероятностью ошибки Pe = P (X(Y ) 6=X), тогдаH(X|Y ) ≤ h(pe ) + pe log(|X | − 1) ≤ 1 + pe log |X |.(4.16)Доказательство.

Пусть E индикатор ошибки оценивания,½E=0,1,b )=Xесли X(Yв противном случае.(4.17)Аналогично соотношению H(E|X) = H(E, X) − H(X) получаемH(E|X, Y ) = H(E, X|Y ) − H(X|Y ) = 0,(4.18)50Глава 4. КЛАССИЧЕСКИ-КВАНТОВЫЕ КАНАЛЫb и поэтому имеет определенное знапоскольку E является функцией (X, X),чение при фиксированных значениях (X, Y ). ПоэтомуH(X|Y ) = H(E, X|Y )H(E|Y ) + H(X|E, Y ) ≤≤ H(E) + (1 − pe )H(X|E = 0, Y ) + pe H(X|E = 1, Y ) == h(pe ) + pe log(|X | − 1) ≤ 1 + pe log |X |,где был использован тот факт, что H(X|E = 0, Y ) также равно нулю, поскольку E = 0 означает, что мы знаем X, если известно Y .Т е о р е м а 12 (Теорема кодирования для канала с шумом). Пустьpe (n, N ) = min P e (W, V )W,Vминимальная средняя ошибка для всевозможных N -кодов со словами длины n.

Тогда при n → ∞ → 0 если R < C (прямая теорема кодирования);6→ 0 если R > C (слабое обращение);pe (n, 2nR )→ 1 если R > C (сильное обращение).Величина R = lognN называется скоростью передачи и равна числу передаваемых битов на символ для данного кода.Доказательство слабого обращения. Рассмотрим произвольный код размера N со словами w(1) , .

. . , w(N ) длины n и разбиение множества Y n наN + 1 область принятия решения V (0) , V (1) , . . . , V (N ) ⊂ Y n . Обозначим Zслучайную величину, принимающую значения 1, . . . , N с равными вероятноb n ) оценка для Z, такая что Z(Yb n ) = j, если Y n ∈ V (j) .стями N1 и пусть Z(YТогда согласно неравенству ФаноnC = Cn ≥ I(Z; Y n ) = H(Z) − H(Z|Y n ) ≥b n ) 6= Z} log N.≥ log N − 1 − P {Z(Y|{z}=P e (W,V )Подставляя N = 2nR и оптимизируя по W, V , получаемnC ≥ nR − 1 − pe (n, 2nR )nR,C1≥ (1 − pe (n, 2nR )) −,RnRи в пределе n → ∞ при R > C:lim inf pe (n, 2nR ) ≥ 1 −n→∞C> 0.R4.2.

ОПТИМАЛЬНОЕ РАЗЛИЧЕНИЕ КВАНТОВЫХ СОСТОЯНИЙ 51Основная идея доказательства прямой теоремы кодирования, восходящая к работе Шеннона1 , состоит в использовании случайного кодирования.Рассмотрим N слов w(1) , . . . , w(N ) , выбираемых случайным образом независимо с распределением вероятностей P {w(j) = (x1 , .

. . , xn )} = px1 · . . . · pxn ,где однобуквенное распределение {px } выбрано так, что оно максимизирует I(X; Y ). Заметим, что имеется примерно 2nH(X) (2nH(Y ) ) типичных словна входе (на выходе), и в среднем 2nH(Y |X) типичных слов на выходе длякаждого входного слова w.Для того, чтобы ошибка различения слов на выходе стремилась к нулю,надо, чтобы множества типичных слов на выходе, соответствующие разнымсловам на входе, асимптотически не пересекались, поэтому размер кода недолжен превосходитьN≈2nH(Y )= 2n(H(Y )−H(Y |X)) = 2nI(X;Y ) .2nH(Y |X)(4.19)Таким образом, N ≈ 2nC .

Конечно, это рассуждение в высшей степениэвристично; строгое доказательство, реализующее эту идею, можно найти,например, в [10], [11].Теорема кодирования раскрывает, таким образом, операциональный смыслпонятия пропускной способности как максимальной скорости асимптотически безошибочной передачи информации через данный канал связи.4.24.2.1Оптимальное различение квантовых состоянийПостановка задачиВ этом разделе мы рассмотрим статистическую задачу, которая позволит вдальнейшем перейти к изучению квантовых каналов связи.Пусть квантовая система находится в одном из состояний Sj ,j = 1, .