Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 44

Пусть имеется канал связи, характери.зуемый набо­ромp(ylx ),и определеннос распределение вероятностей Х = { х, р(х)} :цявходящих букв. Мы посылаем строки изnбукв и прсююлаr·аем, что каналдействует на каждую букву независимо. (О действующем таким образом ка­нале говорят как о ((Канаде без памятю>.) Конечно, как только заданы р(у)з:)иХ~ {х,р(х)}, так сразу определены p(xly) и У= {у,р(у) }.Чтобы установить достижимое быстродействие, вновь рассмотримусреднение по случайным кодам, где кодоные слова выбираются с anpu~орпой вероятностью, определяемой ансамблем хп.

Таким образом, с вы­сокой вероятностью они будут выбраны из типичноm набора строк букв,содержащего около 2nH(X) таких типичных строк.Дня тиnичного, nрина;I,Jiежащсгоyn,получаемого сообщения суще­ствует окоJю 2r~н(Xf}"") сообщений, которые моши бы быть nосланы. Мыможем декодировать IIОлученное сообщение, сопоставляя ему <<сферу>>, сtl­,,ержащую zn[H(X[Y)+J] возможных входов.

ЕС.1И ВН)'lрИ этой сферы име­ется единственное кодовое слово, то им декодируется полученнос сооб~щение.Как и раньше, маловероятно, что инутри сферы не окажется ни о;щогокодового слова, однако мы )(0.1ЖIIЫ ИСКJIЮЧ"ить возможность того, что ихтам больше одного. Каждая сфера декодирования содержит долюzn[H(X\')Hiz ~n[H(X)--ff(XY)~о:znH(X)= z-u[l(X;Y)-o](5.30)от общего числа типичных вxO.rtOR. Если имеется 2нn кодовых слов, товероятность того, что одно и3 них с;1учайно окажется внутри сферы деко~дирования, равна(5.31)Поскольку 6 может быть выбрана ско:ть у1·одно ма."Iой, то R можно взятьнастолько бJш.зким к I (но все же меньшим, чем I), насколько ~то необходи­мо, чтобы пероятнос1ъ ошибки деi«щирования оставанась :жспоненциалыюмалой приn~ оо.5.1.

lliEHHOH ДЛЯ <<ЧАЙНИКОВ»225Зто дока.1ателъство показывает, чrо, когда мы усредняем по случайнымко;щм и по кодовы~ словам~ вероятность ошибки остается малой при лю­бом бысiродейстпииR < f.Тогда те же самые рассуждения, чю и выше,11оказывают существование особого кода с вероятностью ошибки<g длякаждого кодового слова. Это приемлсмый результат~ поскольку он сопшсу­ется с пашей интерпретацией1,как информации, которую мы приобретаемо входящем Х, получая сигнал У.

То есть J представляет собой отнесен­ную к одной букве информацию, которую мы можем послать по данномуканалу связи.D·•аимная информациЯ 1(Х; У) зависит не только от условных веро­ятностей p(yix), характеризующих капал связи, но также и от анриорныхвероятностей р(х) появления букв. Привсl\енное выше доказатеJн.ство слу­чайного кодирования применимо при любом выборе вероятностей р(х),следова·а~:Jьпо, мы показали, что безоШибочная передача возможна ври :Iю­бом: быстроnсйСТIJИИ R, меньшем чемс~ шах{р(х))l(X;Y).(5.32)С на.1ывается емкостью канала или пропусююй способностью каиала и за­висит только от усновных вероятностей, определяющих данный канал.Мы показали, что ?J:ОСтижимо любое быстродействие Нжет :шR<С, но мо­аревзойти С (при условии, что по-прежнему вероятность ошибкистремится к нулю приn----+ оо )'?Доказательство1oro,что С является верх­ней границей быстродействия, в общем случае может по казаться более щн­ким, чем для двоичного симме1ричноrо канала-вероятности ошибок дляра·шых букв ра.wичны, и мы свободны в использовании этого при созданиикода.

Булем, однако, рассуждать следующим образом:Допустим, что мы выбрали 2nн строк из n букв n качестве кодовыхслов. Рассмо1рим ансамбль (обозначаемый как Х"), в котором каждое ко­;ювое слово 1юзникаст с одинаковой "сроятностью (~ 2 -nR). Тогда очевил;­нu, чтоН(Х") = nR.(5.33)Посы;шя кодовые слова через капа;I связи, мы по.'!j'Чаем ансамбль У" вы­хо;~ящих состояний.Поскольку мы прс,1полагаем, что канал действует на каж!{уЮ буквунсзависимо, условная вероятность для строки изn6уkВ факторизуется:(5.34)226ГЛАВА 5а отсюда следует, что услоnная энтроnия удометооряет услоnиюH(Y"IXn) = (-logp(ynjx")) = 2:)-logp(y,lx,)) ~i(5.35)где Х, н У;-частные (марmнальные) распределения вероятностей для i-ойбуквы, определяемые наnшм распределением по кодоным сJювам. Напом­ним, что нам также известно, что Н(Х, У),;;Н(Х)+ Н(У)нлн(5.36)Оrсюда следует, что=I;I(Y,;X,),;; пС;(537)nзаимная информация посланного и подученного сообщений ограниченасверху суммой отнесенных к каждой букве взаимных ипформаций, а вза­имная информация щrя каждой буквы ограничена сверху емкостью каналасвязи [поскольку С определяется как максимум f(X; У)].Вспоминая о симметрии взаимной информации, мы имеемI(X"; :Yn)= Н(Хп)- H(Xпi:Yn) =~ nR- H(X"IY") ,;; пс.Теперь если мы в состоянии надежно декодировать приозначает, чтовходящее кодовое слово(5.38)n -оо, то зrополностью опредеJIЯетсяполучае­мым сигналом нлн чrо условная зитроняя входа (в расчете на одну букву)должна стать малой:(539)Если безошибочность передачи возможна,_ то в преде.1ение(5.38)n .

. . . .,.оо уравне­принимает видR,;; С.(540)2275.2. ЭНТРОПИЯ ФОН НЕЙМАНАБыстродействие не может превзойти емкость канала связи. [Вспомним, ч1.оусловная энтропия, _в о-ушчие от взаимной информации,Действительно,H(YniXn)/nfleсимметрична.не становится малым, поскольку канал вно­сит неопределенность в то, какое сообщение будет получено. Но если мыможем декодировать точно, то, коль скоро сигнал получен, исчезает неопре­деленность в том, какое кодовое слово бьто послано.]Мы показа.;w, что емкость. С предст8.1lirяет собой максимальное дости­жимое быстродействие связи через канад с шумом, при котором вероят­ность ошибки декодирования стремится к нулю при с·rрсмящсмся :к беско­нечности :количестве букв в Сообщении.

В этом сосrоит теорема Шеинонао кодировании для канала связи с шумом.Конечно, использованный нами меrод (усрсдение но случайным ко­цам) доказательства того, что равенствоR= С асимптотически достижи­мо, не очень консrруктнвен. Так как случайный КOiJ. не имеет с1руюуры ютсхемы, то кодирование и декодирование будут довольно rромоздкими (намнужна экспоненциально большая книга кодов).

Тем не менее эта теоремаважна и полезна, поскольку она IОворит о том, что в принципс достижимои, более того, что недостижимо, даже в принципе. К тому же, посколькуI(X; У)является вогнутой функцией от Х ~ {х,р(х)} (при фиксирован­ном {p(yl:r)}), ro она имеет единСiвснный локальный максимум, а Г: дляинтересуемого канала связи часто может быть вычислена (по крайней меречисленно).5.2.Энтропия фон НеймаиаБ теории классичесЮJй информации мы часто рассматриваем источ­ник, который гоrовит сообщения изnбуки(n~1),причем кажl(ая букванезависимо извлекается из ансамбля Х = { х, р( х)}. Мы видели, чrо ин­формационная эmропия Пlеннона Н(Х) (асимпrотически при n --+ оо)представляет собой ко:~ичество приходящихся на одну букву несжимаемыхбитов информации.Нас также могут интересовать корреляции между сообщениями. Кор­реляции между двумя ансамблями букв Х и У харак-rеризуются условнымивероя-пюстямиp(yix).Мы видели, чrо взаимная информацияI(X; У)~ IJ(X)- H(XIY)-~ Н(У)-H(YIX)(5.41)представляет собой приходящееся на одну букву количество битов инфор­мации об Х, которую мы можем получить, читая У (и наоборот).

Еслиусловные вероятностиp(-ylx)характеризуют канал с шумом, тоI(X; У) -ГЛАВА 5228приходящсеся на одну букву кодичестно информющи, которое может бытьпередано через канал связи (нри аprioriза,цашюм раснределении вероят­ностей для Х -ов).Мы хотели бы распространить эти понятия на квaumo(J)Jю информа­IЩЮ. Представим источник, который готовит сообщения изnбукв, но тс­нсрr, каждая буква выбирается из ансамбля квантовых состояний. Алфавитсю·на:юн представляет собой множество квантовых сосrояний Рх• каждоеИ3 которых появ.:-тяется с определенной априорпой вероятностью р х.Как мы уже подробно обсуждали.

если набтодателю неи3вестно, какаябуква приготоnлена, то вероятность любого резудьтата любо1о юмерениябуквы, выбранной из зтого ансамбля, можно нолносп~ю охарактеризоватьматрицей JL'IOТIIOCТИР ,_ L:rxPx;(5.42)хJUJЯ ПОЗМ{F а} мы имеемProb(a) = tr (Fap).(5.43)11Jш этой (или любой другой) матрицы п.1отности можно определить знтро­rшю фон НейманаS(p) = -tr (plogp).(5.44)Конечно, если мы выберем ортонормированный базис {!а)}, диагонализу­щий р:(5.45)атоS(p) = П(А),г,1е Н (А)(5.46)· жтропия Шеинона аuсамб!JЯ А ~ {а, Ла}.В том случае, КОiда алфавит сигпалов состоит из взаимно ортогональ­ных чистых соС'Юяний, квантовый источник сводится к классическому; всесигнальные состояния идеально различимы иS(p) --Н(А). Более инте­ресен квантовый источник, сигна.пт~ныс состоянин которого р взаимно некоммутирукrr.

Мы докажем, что ::штропия фон Пеймана является КОilИЧе­ствеююй мерой несжимаемой информации, содержащсйся в юшн1uном ис­точнике (в том случае, когда сm·нальные состояния янляются чистыми),почти как энтропия Шеинона является количсС1венной мерой информации,содержащейся в классическом ис1ОЧIIИке.5.2. JНТРОПИЯ ФОН НЕЙМАЛА229На самом деле мы обнаружим, что знтропия фон Неймана играет двой­ственную родь. Она является количественпой мерой не rолько квантовойинформации, содержащейся в одной букве ансамбля (минимальное кошrче­ство приходящихся на одну букву кубитов, необходимое для надежнОiu ко­;щрования информации), но и содержащейся н ней классической информа­ции (максимальное ко.шrчество приходящейся на од:ну букву ипформациив битах, а не в кубитах-которое можно полуtmть с помощью наилучшегоизмерения). Мы увидим, что энтропия фон Неймана вХО!1ИТ в квантовуюинформацию еще одним, третьим способом, количественно определяя за­нутывание бинарного чистого состояния.