Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2 (1156795), страница 42
Текст из файла (страница 42)
НИJlЬСен, И. Чанr, Квинтовые вычисления и кваюповаяииформация, М.: Мир,2006.- Пpu.'\t.реа.5.1. НIЕННОН ДЛЯ <{ЧАЙ!ШКОВ>>5.1.215Шеинон для «чайников»Прежде чем мы сможем: понять энчюпию фон Неймэна и ее значениедля квантовой информации, мы должны обсудить энтропию Шеииона и еезначение д.Jiя информации классической.В своей основополагающей стаiЪе1948 г.Клод Шеинон установил дваосновных результата теории классической информации.
Им были решеныдве центральных пробл<:><ы.(1) Насколько можно сжать сообщение, то есть насконько избыточна информация? («Теорема кодирования без помех>>).(2)С какой скоростью мы можем 1Iаде-ж1ю передавать сообщения по каналу с помехами; то есть насколько избыточным должно бып. содержание сообщения, чтобы быть защищенным от ошибок? (<<Теорема кодирования для капала с помехами (шумом)>>.)Оба вопроса касаются избыточности-насколько, в среднем, неожидаина С."'едующая буква сообщения.
Сопшсно одной из кточевых идейШеннона, удобную количественную меру избыточности предоставляет энтропия.Я назвал эrот раздел «Шеннон для чайников», поскольку я попьпаюсьбыстро объяснить основные идеи Шеинона с минимальным ко.шчествомЕ-ов и д. Таким образом, я смогу втиснуть теорию классической информации примерно в 1\ВСнадцать страниц.5.1.1.Энтропия Шеинона и сжатие данныхСообщеннем называется строка нз букв, выбранных из содержащегоkбукв алфавита(5.1)Предположим. что буквыахв сообщении статистически независимыи каждая из них появляется с заданной а priori вероятностью р( ах), гдеI:~~ 1 р( ах)=(где О,;; р,;;1).1. нростейшим пр им ером служит двоичный алфавит, в1 - р, а 1 - с вероятностью ркотором О появляется с вероятностью»Рассмо1рим длинные, содержащие n букв (n1), сообщения. Насинтересует, можно ли сжать сообщение до более короткой строки, несущей,по существу, ту же информацию?ГЛАВА2165Соr.1асно закону больших чисел при очень больших n типичные строки содержат (в двоичном случае) примерно n(J - р) нулей и нримсрно прединиц.
Ко;mчество различных строк такого типа (типичных строк) по порядку величины равно биномиальному коэффициенту ( ,;'р) и из формулыСтирлингаlogn! = nlogn- n+ O(logп)п'мы нонучаем~log ( n) = log ( , )'[)]' ) - nlogn- ппр\пр .n(1-p .[nplognp- пр+ п(1- р) logn(1- р)- n(1- р)] =пН(р),(5.2)щеН(р) =--plogp- (l- р) log(1- р)(5.3)функция, называемая энтропией. С:~едонательно, ко.JJичество типичныхстрок имеет порядок znH(p) (Лоrарифмы здесь понимаются по основаниюдва, если не оговаривается иное.)Чтобы передюъ, по существу, всю информацию, переносимую строкой И3nбитов, достаrочно выбрать блоковый код, приспаивающий ноложительнос целое число каждой типичной строке.
Этот блоковый код имеетоколо 2nH(p) слов (появляющихся с а priori одинаковой вероятностью). такчто любое из них мы можем идентифицировать, используя двокчную строку длиной nH(p). Поско;lькуО.;:Н(р)(\п:риО ( р ( 1 и Н(р) = 1 толькопри р =О и11/2,блоковый код сокращает сообщение при любом pf 1/2 (когдане равновероятны).
')то результат Шеннона. Главная идея за:кшочается в том, что нам не нужно кодовое с;юво для каждой последовательности букв, а только для типичных последовательностей. ВеJЮятность то1о,что действительное сообщение атипично, асимптотwiески (то есть в пределеn-)о оо) мала.Это рассуждение очеви;щым образом обобщается на случайkбукв,коща буква х появляется с вероятностью р( х) 1 В строке, содержащей nбукв, х обычно возникает приблкзительно np(x) раз, а количество типичных строк имеет порядокn!~ znH(X)П, (пр(х))! '1(5.4)Ансамбль, в котором каждая из n бylffi извлекается из распределенш Х, будет обозиачаrься как Х ч.5.1.IНrшнон для «ЧАйникоВ>)217где мы вновь воспользовааись асимпwrnческой формулой Стирrошга, аН(Х) =- L:>(x)logp(x)(5.5)хJнmponuя Пlеннона (или просто эшропия) апсамбо'Я Х = {х,р(х)}.
Выбирая б.:юковьтй код, присваинающий целые чис.1а типичным последовательностям, можно сжать до nH(X) битов информацию, содержащуюсяв строке из n букв. В этом смысле выбранная из анса"бля буква х несетв среднем Н(Х) битов информации.Это рассуждение полезно переформулировать на несколько ином языке. Оrдельное п-буквснное сообщение(5.6)возникает с вероятностыо, аpn·oriравной(5.7)logP(x 1 х 2...xn)="Llogp(x,).(5.8)i=1Применяя к этой сумме центральную предельную теорему, мы приходимк nыооду, что для «большинства последовательностей)>1-де угловые скобки обозначают среднее значение по распределению вероятностей, упраиляющему с;rучайпой переменной х.Конечно, на языке t-ов и д можно дать точную формулировку этогоутвержденЮI.
Для любых Е: б>О и для достаточно большихnкаждая<<Типичная последовательность» имеет вероятность Р, удовлетворяющуюнеравенствуlf(X)- б<1-пlog Р(х 1 х 2...xn) < Н(Х) 1 б,(5.10)а суммарная вероятность всех типичных последователr.ностей превышает11 ~ s . И.Тiи, другими словами, каждая из последовательностей букв, возникающих с превосходящей 1 - Е суммарной вероятностью («типичныеlФактически это один из варианwв закооо больших •щсел.
Его с1]Х>rую математическую форму:IИроtнсу можно найш н любом У'Iсбнике110теории верокrностей или н книtсЛ. С. Хо."'ево, Введение в кванmоfl)!ю теорию инфорJКацuи, МЦНМО, М.:2002. -Прим. ред.ГЛАВА2185последовательности»), появляется с вероятностью Р такой, что2 - n(H+J) ":; рИз уравнениястваN(E,(5.11)":;2 -n(H-o)(5.11)можно вывести верхнюю н нижнюю грани для количеб) типичных последовательностей (так как сумма вероятностейвсех типичных последовательностей должна лежать между1-Е и единицей):( 1 - e)2n(H-o) ":;N(t:, J) ":;С помощью блокового кода дпиной2 n(HH)_n( Н t J)(5.12)битов мы можем закодировать все типичные последовательности. Тогда, независимо от того, какзакодированы атипичные последовательности, вероятность ошибки (декодирования) будет меньше, чем е:.И наоборо1~ если мы попытаемен сжать сообщение до меньшего,чем Н -!51, количества битов на одну букву, w не сможем добиться малойчастоты опmбок вриn _..оо, так как будем не в состоянии олнозначно присвоитъ кодовые слова всем типичным последовательностям.
Вероятностьуспешного декодирования сообщения Psuccess будет ограничена сверху(5.13)Мы можем корректно декодировать только 2n(H -О') типичных сообщений,каждое из которых возникает с вероя11ЮС1ъю, меньшей чем 2--n(H-O) (с:'добавлена, чwбы учесть вероятностьwro,чw нам удается корректно декодировать атипичные сообщения). А так как о может быть выбрана скозьуrодно малой, то нриn ----...оо мадой становится и эта вероятность успеха.Таким образом, оптимальный код асимптотически сжимает каждуюбукву до Н(Х) биwв. Эw и есть теорема Шеинона о кодировании в отсутствии щума.5.1.2.Взаимная информацияЭюропия Шеинона Н(Х) количественно онределяет, ско.тько в среднем информации нередается буквой, извлеченной из ансамбля Х.
То естьсообщает, сколько (асимптотически приn----4оо, 1дсn-количество извлеченных букв) необходимо битов, чwбы закодировать эту информацию.Взаимная информацияI(X; У)количественно определяет степень корреляции двух сообщений. Как много мы узнаем о сообщении, извлеченномизxn, проiШтав сообщеiШе, извлеченное из уп7ДопуС'IИм, например, что мы хотим послать сообщение от отправителя к получателю.
Однако в канале связи имеется шум, так чrо полученное5.1. ШЕИНОН ДЛЯ «ЧАЙНИКОВ))219сообщение (у) может отличаться от посланного (х). Канал с шумом можно характеризовать условной вероятностью p(yjx) ·- верояшостью того,что будет получено у, если послано х. Предположим, что буква х посылается с аprioriизвесшой вероятностью р( х). Мы хотим количественноопределить, что мы узнаем об х, получив у; какой объем информации мыприобретаем?Как уже говорнлось, зюропия Н(Х) дает отнесенную к одной буквеколичественную меру моего априорного незнаиия сообщения до его получения; то есть вам необходимо передать мне (без искажений) nH битов, чтобы (аснмнтотическн) точно определить конкретное сообщение изnбукв.
Но после ознакомления с сообщением у, я мо1у использовать теоремуБейеса, чтобы скорректировать распределение вероятностей для х:р ( х 1у )__p(yjx)p(x)--р(у)(5.14).[Мне известны p(yjx), если я знаком со свойствами канала, и р(х), если я знаю априорные вероятности появления букв; таким образом, я могувычислить р(у) = l:p(yjx)p(x).] Благодаря приобретенному новому зна.тнию я стал бо.пее осведомлен относительно х, чем ранее. С нолученнымимной у-ми, используя оптимальный код, вы можете полностью определитьконкретную строку изnбукв, посылая мнеll(XJY)оо(-Jogp(xjy)}(5.15)битов на каждую букву'. H(XJY) называется <<условной энтропией».Из p(xjy) = р(х, y)jp(y) мы видим, чтоН(ХIУ) = (-!ogp(x,y)= ll(X,-----:-------У)-+logp(y)}Н(У)(5.16)1Вряд ли следуст поняматъ эrо утверждение в буквальном смысле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
