М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 158
Текст из файла (страница 158)
Согласно теореме о типичных последовательностях, количество таких типичных ошибок е приблизительно равно 2пн(Р1. 668 Глава 12. Квантовая теория информации Мы рассмотрели одно кодовое слово, но, конечно, искажение информации того же типа характерно для всех кодовых слов. Можно представить себе пространство всех кодовых слов и окружающих их сфер Хэмминга (рис. 12.6). Если, как изображено на рисунке, сферы Хэмминга не перекрываются, Боб может легко декодировать данные на выходе из канала. Боб просто проверяет, находятся ли выходные данные на одной из сфер Хэмминга; если это так, Боб выбирает соответствующее кодовое слово, а если нег — значит произошла ошибка. Поскольку мы предположили, что сферы не перекрываются, велика вероятность успешного декодирования любого кодового слова.
Действительно, даже если сферы слегка перекрываются, все равно можно провести декодирование с хорошим шансом на успех, поскольку с большой вероятностью данные на выходе из канала будут принадлежать одной (а не нулю, двум или более) из сфер Хэмминга.
Когда имеет место небольшое перекрытие сфер? Чтобы ответить на этот вопрос, нужно лучше понять структуру данных на выходе из канала. Мы получили кодовые слова для нашего кода, сделав 2" л выборок из набора (Хм..., Хп) случайных величин, которые независимы и одинаково распределены, причем Х = 0 с вероятностью о и Ху = 1 с вероятностью 1 — г1.
Пусть 1гу — результат передачи Х по двоичному симметричному каналу. Теорема о типичных последовательностях утверждает, что существует приблизительно 2пл<~ 1 типичных значений (Ъ~,..., У„), где У имеет такое же распределение как каждое 1уч Более того, все значения этих типичных данных на выходе имеют приблизительно одинаковую вероятность. Пропранпв кодовых сло Рис. 12.6. Случайно выбранные кодовые слова длн двоичного симметричного канала, окруженные сферами Хамминга «типичных» данных на выходе. Крупный план длн одного кодового слова приведен на рис.
12 5. 12.3. Передача классической информации 669 Если наугад сделать сто выборок (по одному элементу) из набора размером один миллион, то маловероятно, что получатся какие-либо повторения. Даже если сделать сто тысяч выборок, количество повторений будет довольно малым. Так будет до тех пор, пока мы не сделаем около миллиона выборок, когда количество повторений начнет увеличиваться с размером выборки. Аналогично, количество перекрытий 2"и сфер Хэмминга радиуса пр не начнет увеличиваться до тех пор, пока общее число элементов во всех сферах не приблизится к размеру пространства 2"и!к>, из которого мы делали выборки.
Поскольку каждая сфера содержит приблизительно 2" и!г! элементов, мы с большой вероятностью будем иметь хороший код, исправляющий ошибки, если 2»Я х 2»н(Р! ( 2»н(г! (12.62) что соответствует следующему условию: (12.63) Я ( Н(У) — Н(р). Энтропия Н(У) зависит от априорного распределения (о,1 — д), выбранного для Ху. Чтобы сделать скорость передачи информации по каналу как можно большей, попытаемся получить максимальную энтропию Н(У). Простое вычисление показывает, что это достигается при использовании равномерного априорного распределения, соответствующего д = -', для которого Н(У) = 1, и, следовательно, возможна любая скорость передачи Я, меньшая, чем 1 — Н(р).
Мы только наметили в общих чертах доказательство возможности надежной передачи информации по двоичному симметричному каналу с любой скоростью вплоть до 1 — Н(р). Рассуждение довольно схематично, но на самом деле содержит многие из ключевых идей, необходимых для строгого рассмотрения даже в квантовом случае. Оказывается, что скорость 1 — Н(р) является также максимально возможной для передачи информации по двоичному симметричному каналу. При скорости, большей, чем 1 — Н(р), сферы Хэмминга начинают настолько перекрываться, что невозможно определить, какое кодовое слово было послано, независимо от того, как были выбраны кодовые слова! Таким образом 1 — Н(р) — пропускная способность двоичного симметричного канала.
Можно ли применять на практике случайное кодирование в качестве метода построения кодов с большой скоростью передачи для двоичного симметричного канала? Если использовать случайный код, то с большой вероятностью получим скорость, близкую к пропускной способности. К сожалению, с этой процедурой связана серьезная трудность. Чтобы произвести кодирование и декодирование, отправитель и получатель (Аписа и Боб) должны сначала договориться о стратегии выполнения этих задач. Для случайных кодов это означает, что Алиса должна послать Бобу список своих случайных кодовых слов. Осуществление этого плана может потребовать более надежной связи, чем способен обеспечить данный канал с шумом.
Несомненно, это нежелательно для многих приложений! Метод случайного кодирования — это всего лишь 670 Глава 12. Квантовая теория информации метод демонстрации существования кодов с большой скоростью передачи, а не практический метод их построения. Для широкого практического применения подошел бы метод, который обеспечивает скорости, близкие к пропускной способности канала, и не создает неприемлемые трудности коммуникации для Алисы и Боба. Следует отметить, что методы построения таких кодов даже для классических каналов с шумом были только недавно открыты после многих десятилетий напряженной работы, и интереснейший вопрос, связанный с поиском подобных конструкций для квантовых каналов с шумом, все еще оста ется открытым.
Теорема Шеннона о кодировании длл канала с шумом Теорема Шеннона о кодировании для канала с шумом обобщает результат о пропускной способности двоичного симметричного канала на случай дискретного канала бев памяти. Для такого канала заданы конечный входной алфавит Х и конечный выходной алфавит О. В случае двоичного симметричного канала Х = О = 10, Ц.
Действие канала описывается множеством усаовннх вероятностей р(у~х), где х Е Х и у Е О. Эти вероятности различных у на выходе из канала при условии, что на входе канала х удовлетворяют соотношениям р(у)х) > О, р(у~х) = 1 для всех х. (12.64) (12.65) Канал не имеет памяти в том смысле, что он действует одинаково каждый раз, когда его используют, т. е. различные обращения к каналу не влияют друг на друга. Мы будем использовать символ Л/ для обозначения классического канала с шумом. Конечно, существует много интересных каналов связи, не являющихся дискретными каналами без памяти, например, телефонная линия, которая имеет непрерывный набор входных и выходных данных.
Подобные каналы могут быть технически более сложными для понимания, чем дискретные каналы без памяти, однако, многие основополагающие-идеи для них одинаковы; список работ по данному вопросу приведен в равд. «История и дополнительная литература» в конце главы.
Рассмотрим формулировку теоремы Шеннона о копировании для канала с шумом. Мы не будем приводить детали доказательства теоремы, поскольку в следующем разделе докажем более общий результат для квантовых каналов, тем не менее, поучительно рассмотреть формулировку для классического случая. Сначала необходимо несколько уточнить понятие надежной передачи информации.
Основная идея проиллюстрирована на рис. 12.7. На первой стадии Алиса создает одно из 2"и возможных сообщений М и кодирует его, используя отображение С": (1,..., 2"и) — » 2, которое каждому возможному сообщению Алисы ставит в соответствие строку входных данных, посылаемых Бобу путем использования канала и раз. Боб декодируег данные на выходе 12.3.
Передача классической информации 671 канала, используя отображение Р": О" -ь (1,..., 2пл), которое каждой возможной строке данных на выходе из канала ставит в соответствие сообщение. Для заданной пары отображений кодирования-декодирования ееролтпность ошибки определяется как максимальная вероятность по всем сообщениям М того, что декодированные данные на выходе из канала Р(И) не совпадают с сообщением М: р(С", Р") ве так р(Р" (Я уй М~Х = С" (М)). (12.66) Мы говорим, что скорость передачи Н является достижимой, если существует такая последовательность пар отображений кодирования-декодирования (С", Р") при скорости передачи Н, для которой р(С", Р") ч 0 при и -ч оо.
Пропускная способностдь С(Л/) данного канала Л/ с шумом, по определению, является супремумом по всем скоростям, достижимым для данного канала. Данные ва Данные иа Сообщение Получатель входе канала выходе канала Рис. 12.7. Задача кодирования для классических сообщений при наличии шума. Требуется, чтобы каждое из 2"а возможных сообщений с большой вероятностью прошло по каналу без искажения Изначально вовсе не очевидно, как вычислить пропускную способность канала. Можно было бы попытаться найти супремум по очень большому (бесконечному!) классу возможных методов кодирования и декодирования, но это не слишком перспективный подход к решению задачи. Теорема Шеннона о кодирования для канала с шумем значительно упрощает вычисление пропускной способности, сводя его к простой и вполне определенной задаче оптимизации, которая может быть точно решена во многих случаях и разрешима на компьютере, деже когда точное решение невозможно.
Теорема 12.7 (теорема Шеннона о кодировании для канала с шумом). Пропускная способность для канала ЛГ с шумом определяется выражением (12.67) С(ЛГ) = тех Н(Х:У), р(х) где максимум берется по всем распределениям р(я) входных данных Х при однократном использовании канала и У вЂ” случайная величина, полученная на выходе канала. В качестве примера применения теоремы о кодировании для канала с шумом рассмотрим случай двоичного симметричного канала, изменяющего биты с вероятностью р, и распределением данных на входе р(0) = е, р(1) = 1 — о. 672 Глава 12. Квантовая теория информации Имеем (12.68) (12.69) Н(Х:У) = Н(У) — Н(У)Х) = Н(У) — ~~~ р(х)Н(У)Х = х). Но Н(У~Х = х) = Н(р) для каждого х, поэтому взаимная информация Н(У:Х) = Н(У) -Н(р) становится максимальной при с = 1/2, так что Н(У) = 1.
Согласно теореме Шеннона о кодировании для канала с шумом, С(ЛГ) = 1 — Н(р), что совпадает с полученным ранее результатом. 'Упражнение 12.9. На вход какала спшрамил подаются О или 1, а на выходе получаются О, 1 и е. С вероятностью 1 — р данные на входе совпадают с данньгми на выходе. С вероятностью р входные данные «стираются» и заменяются на е.
1. Покажите, что пропускная способность канала стирания есть 1 — р. 2. Докажите, что пропускная способность канала стирания больше пропускной способности двоичного симметричного канала. Почему этот результат интуитивно кажется правдоподобным? С(Л/э оЛ~~) < пйп(С(ЛГ~),С(Л/э)). (12.70) Приведите пример, в котором выполняется строгое неравенство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
