Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2

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

Описание файла

PDF-файл из архива "Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2", который расположен в категории "книги и методические указания". Всё это находится в предмете "квантовые вычисления" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 42 страницы из PDF

НИ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о утверждение в буквальном смысле.

Свежие статьи
Популярно сейчас