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

Для того, чтобы от­правитель мог ВОС(..'11!Нонить посылаемую им с1року изnбукв Х, он должен получать попара.rтельному каналу без шума информацию о каждой букве выходящего сообщенш Уи по нему же отправлять исправления, если произошла ощибка nередачи. [См. С.Shannon,mathemathical theory of communication, ВеН System Techn. J., 27, .N"~ 3, 379 423; N!!4, 623656 (1948). Русский перевод: К. Шеннон, Математическая теориИ" связи, в kНиге К. Шеннон,Работы по теории ин.формации и кибернетике, ИЛ, Москва (1063), стр. 243-332.] Скорееусо10вную энтропию Jl(XIY) следует интерпретировать как :количество информации, теряе­Амой при передаче сообщения Х через канал с шумом.Кроме этого, обратим внимание на то, что ви(5.19),(5.15),а такжt': в уравнеRШiх(5.16), (5.17)уrлоные сJ<:Обки обозначают усреднение по совмесrному распределению вероятно­сrей р(х, у).

Следовательно все 'JТИ величины определяют информационные характеристикипе J<Ошq:юmых n-буквенных строк, а всего совместого ансамбля входящих и выходящих со­обшений.-Прим. ред.ГЛАВА 5220и аналогичноH(YIX)=(-logp(yfx))=р(х,у))j\ -log р(х)~H(X,Y)-II(X).(5.17)Таким образом, Н(Х[}') можно интсрпретироnать как коJrичество дополни­тельных бишв на одну букву, необходимых ДJШ полного онределения:rи упри известном у. Очевидно, что эта величина не может быть отрицатель­ной.Информапия об Х, приобретаемая при знакомстве с У, измеряется тем,насколько сокращается отнесенное к одной букве количество битов, необ­ходимое ;uш иденшфикации Х при известном У. Таким образом:Т(Х; У)= Н(Х)- H(XIY)~ Н(Х)+ Н(У) -Н(Х, У) == Н(У)- Н(У[Х).I(X; У)(5.18)называется взаимной информацией.

Она, очевидно, симметричнаотносителыю перестапопки Х и У; количество информации об Х, нолу­чаемое при знакомстве с У, равно количеству информации об У, получае­мому при знакомстве с Х. Знакомство с У не может у.,.,еньшить мое зна­ние об Х, следовательно, J(X; У) очевидно неотрицательна. (НеравенстнаН(Х) ;? Н(Х[У) ;? О легко докащваются с учешм свойства ньшуклости.1оrарифмической функции 1 .)Конечно, ес.·ш Х и У IЮJJНостью некорре;шрованы, то мы имеемр(х.у) =р(х)р(у) и1 (Х; У)=( logр(х,у) )( . ( )р х)р У= О;(5.19)естественно, чrо, знакомяс1~ с У, мы ничего не можем у:шатт.

об Х, еслимежлуними нет коррсляпии!5.1.3.Теорема о кодировв11ни для ка11ала с шумомEc.ilи мы хотим установить связf.. через канал с шумом, то мы, оче­видно, можем повысить надежность передачи посредством и~-~быточности1Soнs,См., например, Т. М. Co\'er, and J. А. Thomas, Element.~ о[ Injunnation Тheory, J.

Wiley &New York, 1991.5.1. illЫIHOH /1;ЛЯ «ЧАЙНИКUВ»221информации. Например, я м01у мноi'Ократно посылать каждый бю~ а по­:тучатсm>--присJJушиваться к голосу большинства, чтобы его декодиро­вать.Но всегда ли д."""IЯ данного капала можно найти :кол, гарантирующийсколь угодно высокую надежность (при п ~ оо)? Л что можно сказатьо быстродействии таких кодов; сколько битов nотребуется для каждой бук­вы сообщения?Фактически Шеинон показал, ч·то любой канал может быть использо­ван для сколь угодно надежной связи с конечной (ненулевой) скоростью,нока существует хоть КilКая-нибудь корреляция между его входом и выхо­лом.

Бо;Jсе того, оп паше.1 полезное выражение для оптимальной скоростикоммуникации, которая может быть ,r~остигнута. Эти резу;[ьтаты составляютсо~~ержание <<теоремы о кодировании для канала связи с шумом».Прещюложим для определенности, что мы пользуемся двоичным ал­фшштом, каждая буква которою (О иl) появляется с априорной Rероятпо­1/2. Предположим также, что канал янляется «двоичным симметрич­стьюным кана.~юм»- он J\сйствует на каждый бит нсзависимо, с вероятнос1ъю риннсртируя его значение и оставляя невредимым с вероятнос1ъю1-р.

Тосс1ъ условные вероятности равныp(OIO) = 1- р,p(JIO)= р,p(OI1) ~- р,p(lll). 1- р.(5.20)Мы хотим построить семейство кодов растущего блочного разме­раnпритакого, чтобы всроятноС'П> ошибки декодирования стремилась к нулюn~ оо. Если количество закодированных в блоке битов равноk,то код,~ак..mчается в выборе2k «кодовых С.1ОВ» из 2n возможных п-битовыхбыстродействие кода R (число битов информации, при­строк.

Определимходящихся на один передаваемый бит) как(5.21)Нам нужно разработать такой.1<011, чтобы кодовые строки находюиськак можно щщ.1ьще друr от друга>>. 1\ругими словами, щ1я дшшого быстро­.:\ейсттшяRмы хотим максимизировать количество битов, которые должныип.вертироватъся, ч1обы о;~но кодовое с;юво заменилось J\ругим (это коли­чество называется «расстоянием Хэмминга» между двумя кодовыми слова­ми).71J1я любой вхолящей с1роки дmпюйnбитов, ошибки, как правило,бут~ут вызывать инвертирование примерно пр битов-следоватеш.но, вход222ГЛАВА 5обычно рассеивается в одну из примерно 2nH (р) типичных выходящихс1рок (заполняющих «сферу радиуса Хэмминrю> пр, окружающую вхо­дящую строку).

Для надежного декодврования, входящие кодовые словас.гrедует выбирать таким образом, чтобы было маловсрояпrым перекрытиесфер ошибок двух разных кодовых слов. В противном случае два ра.1ныхвхода иногда будут давать один и тот же выход, чrо с неизбежностью при­ведет к опrnбкам декодирования.

Если мы хотим избавиться от таких дву­смысленностей декодирования, полное число строк, содержащихся во всех2nR сферах ошибок, не должно лревышать поJшого количества битов 2nв выходящем сообщении; мы требуем выполнения(5.22)ШIИR ":; 1- Н(р)=С(р).(5.23)Если надежность nередачи достаrочно высока, мы не можем ожидать, чrобыстродействие кода лревзойлет С(р ).

Но достижимо ли на самом делебыстродействие R = С(р) (асимптотически)?Фактически возможна передача с R, сколь угодно близким к С(р)и сколь угодно малой верояпюстью ошибки. По-видимому, самой остро­умной из идей Шеинона бьmа демонстрация того, что С(р) может бытьдостигнуто учетом среднего по «случайным кодам». [Очевидно, ч-ю слу­чайный выбор кода-не самый разумный способ, но, возможно зто по­кажется удивительным, оказывается, что случайное кодирование достигаеттакого же высокого быстродействия (асимптотически при большихn),каки шобая друтая схема кодирования.] Поскольку С nредставляет собой оп­тимальное быстродействие при надежной передаче даннЫх по каналу с шу­мом, она называется емкпстью канала С6ЯЗИ ЮIИ пропускной способностьюкапала связи.Предположим.

ЧТО znR кодовых слов представляют собой С.l}'Чайнуювыборку из а.нсамбпя Х". Сообщение (одно из коrювых слов) послано.Чтобы его декодировать, изобразим вокруг нопученного сообщения <<сферуХэмминrю>, содержащую(5.24)строк. Сообщение декодируется содержащимся в этой сфере кодовым сло­вом в предположении, что оно существует и единственно. Если такое ко­довое слово не существует ИШ1 оно не единственно, то будем считать, чтопроизошла ошибка декодврования.Насколько вероятна ошибка декодврования? Мы выбрали сферу деко­дирования достаточно большой, так чrо отсутствие достоверного кодового5.1.

ШЕИНОН ДЛЯ «ЧАЙНИКОВ)>223слова внуrри сферы атипично, следовательно, мы должны беспокоитьсялишь о том. что ее займуr более одного достоверного кодового слова. По­скольку всего имеетсявозможных строк, 10 окружающая выходящуюznстроку сфера Хэммипга содержит дото2n[H(p)+дin= 2-n[С(р)-д](5.25)2от общего количества строк. Таким образом, пероятиость того, что одноиз 2nR случайно выбранных кодовых слов «ПО несчастью» займет зrу сфе­ру, равна(5.26)А так как6мы можем выбрать сколь угодно малым,ro Rможно взятьнастолько бJШзкнм к С(р) [но все же меньшим, чем С(р)], насколько этонеобходимо) чтобы вероятность такой ошибки оставалась Эf\:споненциальномалой приn.........).оо.Пока мы показаJШ, что мала средliЯЯ верояnюсть ошибки, которуюмы усреi\НЯем по выбору снучайного кода, а для каждого конкреnюто ко­да-еще и по всем кодовым словам.

Таким образом) должен существоватьодин частиый код со средней (усредненной по кодовым словам) аероятио­стью ошибки, меньшей чем Е. Но нам хотелось бы иметь более сильныйрезультат-пероятиость ошибки мала дl\Я каждого КОI\Ового слова.Чтобы установить зтот более сильный результат, обозначим черезР, верояnюеп, ошибки декодирования i-го пославною кодового спова.Мы продемонстрировали существование кода такого, что2""_J_~p <Е.2nR L..,;(5.27)ti=1ПустьN 2Eобозначает количество кодовых слов сPi> 2Е.Тогда мы прихо­дим к выводу, что(5.28)то сеть можно отбросить максимум половину кодовых слов, чтобы добить­сяPi <2Е д.-;:~я каждого кодового с:rова. Быстродействие сконструирован­ного нами новmu кода равноRate = Rчто стремится кRприn ___,.ос.1n'(5.29)ГЛАВА224Таким образом, С(р) =1-5П(р) пре11стаюяет собой максимальноебыстродействие, которое может быть достигнуто а сим нтотически со скольугодно малой вероятностью ошибки.Рассмотрим теперь, как обобщить эти доказательства на бо:1ее общиеалфавюы и каналы.