М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 155
Текст из файла (страница 155)
«История и дополнительная литература» в конце главы. Расширим понятие типичных последовательностей за рамки двоичного случая. Пусть Х|, Х|ь Хз,... — стационарный источник информации. Обычно частота появления данной буквы х в последовательности на выходе источника 12.2. Сжатие данных 655 близка к вероятности р(х) этой буквы. Имея это в виду, мы дадим следующее строгое определение понятия типичной последовательности. Задавая в > О, мы говорим, что строка символов хм хм..., х„источника в-типичная, если 2-п(Н(Х)+в) < ( х ) < 2-в(Н(Х)-э) (12.26) и обозначаем набор всех таких в-типичных последовательностей длины и как Т(и, в).
Это определение может быть переформулировано в следующем эквивалентном виде (12.27) ! 1 1 -1ой — н(х) < и р(хм...,х„) Используя закон больших чисел (сформулированный и доказанный во вставке 12.3), мы можем доказать теорему о тиипчиэю последовательностях, которая строго выражает идею о том, что в пределе больших и большинство последовательностей на выходе источника информаций являются типичными. Теорема 12.2 (теорема о типичных последовательностях). 1. Пусть в > О. Тогда для любого б > 0 при достаточно больших и вероят- ность того, что последовательность в-типичная, не меньше, чем 1 — б.
2. Для любого фиксированного в > 0 и б > 0 при достаточно больших и число (Т(и,в)( в-типичных последовательностей удовлетворяет неравенствам (1 б)2э(Н(х)-е) < )Т(и в)/ < 2в(н(х)+в) 3, Пусть Я(и) — набор не более, чем 2"и последовательностей длины и с выхода источника, где В < Н(х) — фиксированное число.
Тогда для любых б > 0 и достаточно больших и р(х) < б. (12.29) жев(в) р ~ ' — Е( — 1обр(Х)) < в > 1 — б. (12.30) ) — !оп р(Х;) Но Е(1ояр(Х)) = — Н(Х) и ~„". 1ояр(Х;) = 1ой(р(Хм...,Х„)). Таким образом, р(~ — 1об(р(Хм...,Х„))/и — Н(Х)~ < в) > 1 — б, (12.31) т. е. вероятность того, что последовательность в-типичная, не меньше, чем 1 — б. Локазателъстео. Часть 1. Непосредственное применение закона больших чисел. Заметим, что 1обр(Х;) — независимые, одинаково распределенные случайные величины. Согласно закону больших чисел, для любого в > 0 и б > 0 при достаточно больших и имеем 656 Глава 12. Квантовая теория информации Часть 2.
Следует из определения типичности и наблюдения, что сумма вероятностей типичных последовательностей должна лежать в интервале от 1 — д (из части 1) до 1 (поскольку сумма вероятностей не может быть больше 1). Поэтому > ~ 2-п(™(Х)+х) )Т(п Е))2-п(~(Х)+с) хЕТ(п,«) хЕТ(п,х) откуда получаем (Т(и, е)) < 2п(н(х)+'), и (12.32) б < )-' р(з) < ~~, 2-п(™(Х)+х) (Т(я е))2-п(н(х)+х) (Г2 33) хЕТ(п,х) хЕТ(п,х) так что !Т(п, е)! > (1 — Ц2п(н(х)-х). Часть 3. Идея заключается в разделении последовательностей в Я(п) на типичные и нетипичные последовательности.
Нетипичные последовательности имеют малую вероятность в пределе больших п. Число типичных последовательностей в Я(п), очевидно, не больше, чем общее число последовательностей в Я(п), которое не превышает 2пл, и каждая типичная последовательность имеет вероятность приблизительно 2пн(х). Полная вероятность типичных последовательностей в Я(п) порядка 2"(и н(х)) и стремится к нулю при Н < Н(х). Более строго, выберем е так, чтобы Я < Н(х) — б и 0 < е < б/2. Разделим последовательности в Я(п) на е-типичные и е-нетипичные последовательности.
Из части 1 следует, что для достаточно больших и полную вероятность нетипичных последовательностей можно сделать меньше д/2. В Я(п) иыеется не более 2пл типичных последовательностей, каждая с вероятностью не более 2 "(~(~) ' л), так что вероятность типичных последовательностей не более 2п(~(~) ') и стремится к нулю при и — » со. Таким образом, полная вероятность последовательностей в Я(п) меньше, чем б, для достаточно больших и. Теорема Шеннона о кодировании для канала без шума является простым примером применения теоремы о типичных последовательностях. Мы приводим здесь очень простую версию теоремы о кодирования для канала без шума.
Более сложные версии оставим для упражнений (см. также рвзд. «История и дополнительная литература» в конце главы). Предположим, что Хм Хз,...— стационарный классический источник информации, определенный на некотором конечном алфавите, содержащем 4 символов. Схема сжатия в 1/Я рэз ( — скорость передачи) отображает последовательности х = (хы..., хп) в битовые строки длины пН, которые мы обозначим как С" (я) = С" (зы...,хп). (Заметим, что пВ может и не быть целым. Мы упростим обозначения, считая, что в данном случае пЯ = (иВ) .) Соответствующая схема развертывания отображает пй сжатых битов обратно в строку из и букв алфавита Р" (Сп(х) ).
Схема сжатия-развертывания (С",.Рп) является надежной, если вероятность того, что Р" (Сп(х)) = я, стремится к единице, когда и стремится к бесконечности. Теорема Шеннона о кодировании для канала без шума определяет, для каких значений скорости передачи В существует надежная схема сжатия, обнаруживая замечательную интерпретацию энтропии Н(Х) как минимального 12.2. Сжатие данных 657 количества физических ресурсов, необходимого и достаточного для надежного хранения данных, создаваемых источником. Теорема 12.3 (теорема Шеннона о кодировании для канала без шума). Пусть (Х ) — стационарный источник информации с энтропией Н(Х).
Предположим, что В > Н(Х). Тогда для этого источника информации существует надежная схема сжатия в 1/В раз. В противном случае, когда В < Н(Х), любая схема сжатия не является надежной. Довазагиельсгиво. Предположим, что В > Н(Х). Выберем е > О, так что Н(Х)+е < В.
Рассмотрим набор е-типичньгх последовательностей Т(и, е). Для любых б > О и достаточно больших и существует не больше 2"<л(х>+4 < 2"я таких последовательностей, и вероятность того, что источник создает одну из таких последовательностей, не меньше, чем 1 — б. Следовательно, прежде, чем производить сжатие, нужно определить, являются ли выходные данных источника е-типичной последовательностью. Если выходные данные не являются такой последовательностью, сжимаем их до некоторой фиксированной иВ-битовой строки, которая указывает на сбой.
Операция развертывания этой строки дает на выходе случайную последовательность хм..., х„как предположение об информации, выданной источником. В этом случае нам не удалось сжать данные. Если выходные данные источника тиричвые, мы сжимаем выходную информацию, сохраняя иВ-битовый номер, соответствующий этой типичной последовательности, что позволяет потом очевидным образом восстановить данные. Пусть В < Н(Х).
Комбинированная операция сжатия-развертывания обладает не более, чем 2"л возможными выходными наборами данных, так что не больше, чем 2"и последовательностей на выходе источника могут быть подвергнуты операциям сжатия и развертывания без ошибки. Из теоремы о типичных последовательностях следует, что для достаточно больших и вероятность того, что последовательность на выходе источника принадлежит подмножеству 2"и последовательностей, стремится к нулю при В < Н(х). Таким образом, любая такая схема сжатия не может быть надежной. Вставка 12.3. Закон больших чисел Предположим, что мы повторяем эксперимент много раз, каждый раз измеряя значение некоторого параметра Х. Обозначим результаты экспериментов как Хм Хю....
Допуская, что результаты экспериментов независимы, мы интуитивно ожидаем, что значение оценки ߄— : 2 ~, Х;/и среднего Е(Х) должно стремиться к Е(Х) при и — ~ оо. Закон больших чисел — строгое подтверждение нашего интуитивного предположения.
Теорема 12.4 (закон больших чисел) . Пусть Хм Хю... — независимые случайные величины, имеющие такое же распределение, что и случайная величина Х с конечными первым и вторым моментами: Е(Х) < оо и Е(Хэ) < оо. Тогда для любых е > О имеем р(߄— Е(Х) > е) — ~ О при и — ~ со. 658 Глава 12. Квантовая теория информации Доказаиге.аэсигво. Предположим сначала, что Е(Х) = О, а в конце дока- зательства теоремы обсудим, что происходит, когда Е(Х) ф О.
Поскольку случайные величины независимы и их среднее значение равно нулю, то Е(Х;Х ) = Е(Х;)Е(Х ) = О при г ф. г и, следовательно, Е,"учм Е(Х;Х,) ~ "., Е(Х,.') Е(Х') (12.34) где последнее равенство следует нз того факта, что Хм..., Х„распреде- лены так же, как Х. Из определения математического ожидания имеем ЕФ') = «Р Н„'~ (12.35) где г1Р— мера вероятности.
Ясно, что либо ф„~ < с, либо )Я„! > с, так что можно разделить интеграл на две части, а затем отбросить одну из них, поскольку она неотрицательна, Е(Нг) = / 4РНг+ / аРНг > / а Нг. (12.36) Р)з ~к<э 1)з ~)я /)з ()е В области интегрирования Яэг > сг, и, следовательно, Е(~г) > / йР г (~Н ~ > )з ~)е (12.37) Сравнивая это неравенство с (12.34), мы видим, что р(~Н.~> ) < Е(Хг) (12.38) Положив п -+ оо, завершим доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
