Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
"переброса бита" 1 -? 0. В противном случае, канал будет обладать
свойством "релаксации" по отношению к 0, т. е. переброс 1 -> 0 будет
иметь место, ь переброс 0 -> 1 нет. Кроме того, подобные ошибки могут
возникав независимо друг от друга от бита к биту либо внезапно. Помех':
независимо влияющие на различные биты и вызывающие как переброс 0 -> 1,
так и переброс 1 -" 0, являются наиболее важными, поскольку искажают
важные свойства многих процессов, встречающихся в реальных ситуациях. В
случае, когда ошибки 0 -* 1 и 1 -? 0 равновероятны, то канал с помехами
называется двоичным симметричным каналом. Данный канал имеет лишь один
показатель р, определяющий вероятность ошибки, приходящейся на каждый
передаваемый бит. Пусть сообщение, передаваемое Алисой по каналу, есть X,
а сообщение с помехами, принимаемое Бобом, есть Y. Таким образом, Боб
сталкивается с задачей наиболее точного выделения сообщения X из
сообщения Y. Если сообщение X состоит из бита, то Бобу придется
воспользоваться следующими условными вероятностями:
р(х = 0|у = 0) = р(х = 1|у = 1) = 1 - р,
р(х = 0|у = 1) = р(х = 1| у = 0 )=р,
которые, согласно уравнениям (2) и (3), дают: 5(Х|У) = Н(р). Таким
образом, из уравнения (6), определяющего полную информацию, получаем:
I(X :Y) = S(X)-H(p). (13)
Очевидно, наличие в канале помех ограничивает информацию о сообщении
Алисы X, находящуюся в принятом Бобом сообщении Y. Кроме того, согласно
неравенству (7) относительно обработки информации, Боб не может, оперируя
сообщением Y, увеличить объем информации о сообщении X. Однако
уравнение (13) показывает, что связь между
Алисой и Бобом станет лучше при больших значениях S(X). Общий
вывод заключается в том, что качество передаваемой информации зависит как
от ее источника, так и от свойств канала. Полезно отдельно
32
Глава 2
определить свойства канала для того, чтобы узнать его способность
передавать информацию. Одним из изменяемых свойств является пропускная
способность (емкость) канала и определяется как максимально возможное
полное количество информации I(X : Y) между входом и выходом,
максимизированное по всем возможным источникам:
емкость канала С = шах I(X : Y). (14)
М*)}
Емкость канала определяется отношением числа битов на выходе к одному
символу на входе и ее значение для двоичных каналов должно находится
между нулем и единицей.
Несмотря на данное определение, уравнение (14) не позволяет относительно
просто сравнивать каналы, поскольку требует максимизации по входным
стратегиям, которые нетривиальны. Задача определения емкости С(р)
двоичного симметричного канала является основной в теории информации,
однако ее решение достаточно простое. Из уравнений (13) и (14) видно, что
его можно представить в виде:
С(р) = 1 - Н(Р). (15)
Это условие получается при S(X) = 1 (т. е. р(х = 0) = р(х = 1) = i).
2.4. Коды, исправляющие ошибки
До настоящего момента рассматривался лишь вопрос о том, сколько
информации проходит через канал с помехами и какое ее количество
теряется. Объем посылаемой Алисой Бобу информации ограничен величиной
С(р) на каждый передаваемый символ. Однако предположим, что Боб
обезвреживает бомбу, а Алиса стоит в отдалении и кричит ему о том, какой
провод необходимо перерезать. Она не может надеяться на то, что Боб
поймет ее правильно, если произнесет фразу: "режь синий провод" лишь один
раз. Алиса будет повторять эту фразу несколько раз, а Боб будет ждать до
тех пор, пока не будет уверен, что правильно ее понял. Связь без ошибок
может быть достигнута даже при использовании канала с помехами. В данном
примере показано, что можно снизить долю ошибок путем увеличения
количества передаваемой информации. Следующий шаг в данном курсе по
изучению теории информации заключается в определении более мощных методов
борьбы с помехами (Hamming 1986; Hill 1986, Jones 1979; MacWilliams and
Sloane 1977).
2.4. Коды, исправляющие ошибки
33
В дальнейшем понадобятся следующие понятия. Множество {0, 1} определяется
как группа (поле Галуа GF(2)), в которой операции +, -, х, + выполняются
по модулю 2 (таким образом, 1 + 1 = 0). Двоичное слово, состоящее их п
битов представляется вектором, имеющим п компонент, например слово 001
может быть представлено вектором (0, 0, 1). Множество подобных векторов
образуют аддитивно замкнутое векторное пространство (образуют векторное
пространство по сложению), т. к., например, сумма двух слов: 011+101 в
векторной форме и по правилам векторного сложения равна 110, поскольку
(0, 1, 1) + + (1. 0, 1) = (0 + 1, 1 + 0, 1 + 1) = (1, 1, 0). Это действие
эквивалентно операции "исключающее ИЛИ" (XOR), выполняемой поразрядно
между двумя двоичными словами.
Воздействие помехи на слово и может быть выражено следующим образом: и ->
и' = и + е, где е обозначает вектор ошибки, который указывает на
положение переброшенного вследствие помехи бита. Например, переброс битов
в слове и = 1001101 -> и' = 1101110 может быть выражен как и' = и +
