Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
0100011. Код С, исправляющий ошибку, представляет множество слов таких,
что
и + е ф v + / Фи, v G С(и ф v) Ve, / G Е, (16)
где Е - множество векторов ошибок, которые можно исправить посредством
кода С, включая "нулевой вектор ошибки" е = 0 (соответствует случаю
отсутствия ошибки). Для использования такого кода Алисе и Бобу нужно
договориться о том, какому сообщению соответствует то или иное кодовое
слово и. После этого Алиса будет передавать по каналу только кодовые
слова. Поскольку в канале присутствуют помехи, Боб будет вместо слова и
принимать слово и + е. Однако Боб сможет однозначно выделить из слова и +
е слово и, поскольку, согласно условию (16), он не сможет принять слово и
+ е, если Алиса будет передавать какое-либо другое кодовое слово v.
Пример кода, исправляющего ошибки, представлен в правом столбце таблицы
1. Этот код в честь его автора называется кодом Хэмминга [7,4,3].
Добавление [п, k, d] означает, что всего имеется 2к кодовых слов, каждое
слово состоит из п битов и все слова отличаются друг от друга значениями
по крайней мере d битов. Из последнего свойства следует, что условие (16)
выполняется для любой ошибки, изменяющей не более одного бита. Другими
словами, множество Е исправляемых ошибок определяется как
{0000000,1000000, 0100000, 0010000, 0001000,
34
Глава 2
0000100, 0000010, 0000001}. Следует отметить, что максимальное количество
членов множества Е равно 2п~к. Отношение ? называется коэффициентом кода
(rate of the code), поскольку каждый передаваемый блок из п битов
содержит к битов информации или, другими словами, ^ битов информации
приходятся на каждый передаваемый бит.
Величина d называется "минимальным расстоянием" кода и имеет важное
значение при кодировании, когда помехи, как, например, в двоичном
симметричном канале, воздействуют независимо на каждый бит. Код с
минимальным расстоянием, равным d, исправляет все ошибки, появившиеся не
более чем в | битах передаваемого кодового слова. Кроме того, в случае с
независимыми помехами данное количество ошибок наиболее вероятно.
Фактически, вероятность того, что в слове и из п битов возникнет т
ошибок, определяется биномиальным распределением (11). Поэтому, если код
исправляет число ошибок больше среднего их количества пр, то существует
высокая вероятность того, что в целом работа кода будет успешной.
Главным выводом классической теории информации является то, что мощные
коды, исправляющие ошибки, существуют.
Теорема Шеннона. Если коэффициент кода ^ < С(р), а число битов п
достаточно большое, то существует двоичный код для передачи информации со
сколь угодно малой вероятностью ошибки.
Здесь вероятность ошибки означает вероятность появления неис-правляемой
ошибки, которая приводит к неправильному истолкованию Бобом принятого
слова. Из теоремы Шеннона следует, что вместо решения сложной и дорогой
задачи создания каналов связи с низким уровнем помех, можно снизить
уровень помех посредством кодов, исправляющих ошибки, другими словами,
посредством обработки информации. Следствия из теоремы Шеннона показаны
на рис. 5.
Распознавание кодов с большими значениями коэффициента ^ и расстояния d
является основной задачей теории кодирования. Поскольку два данных
условия несовместимы, то между ними требуется найти какой-либо
компромисс. Данная задача действительно очень сложна и не имеет общего
решения. Для того чтобы связать вышеизложенное с кодами, исправляющими
ошибки, необходимо напомнить одно очень важное понятие, а именно, понятие
матрицы с контролем по четности
2.4. Коды, исправляющие ошибки
35
1
0,9
0,8
0,7
аэ 0,6 с
03 04 0.4 0.3 0,2 0,1 0
О 0,2 0,4 0,6 0,8 1
k/П
Рис. 5. Иллюстрация к теореме Шеннона. Алиса с целью передать Бобу к
битов информации пересылает по каналу с помехами п = 100 битов. На
рисунке показана зависимость вероятности правильного интерпретирования
Бобом полученной информации от отношения к/п при вероятности ошибки на
бит: р = 0,25. Емкость канала (7 = 1- Н(0,25) ~ 0,19. Штриховая линия:
каждый передаваемый Алисой бит повторяется п/к раз. Сплошная линия: Алиса
использует наилучший вариант линейного кода, исправляющего ошибки с
коэффициентом к/п. Точечная линия определяет эффективность кодов,
исправляющих ошибки при увеличении п и наглядно иллюстрирует теорему
Шеннона
(parity-cheek matrix). Код, исправляющий ошибки, называется линейным,
если он является замкнутым по сложению, т. е. и + v ? С для любых и, V,
ЕС. Подобный код полностью определяется его матрицей с контролем по
четности Н, которая является множеством (п - к) линейно независимых го-
битовых слов, удовлетворяющих условию: Н-и = = 0 для любого и ? С.
Отметим следующее важное свойство матрицы
Н-(и + е) = (Н-и) + (Н-е)=Н-е. (17)
Из этого свойства следует, что если Боб будет определять значение Н-и'
36
Глава 2
для искаженного помехами принятого слова и' = и + е, то в результате он
получит Н ¦ е вне зависимости от того, какое слово и передала ему Алиса.
