М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 130
Текст из файла (страница 130)
(Напомним, что (а, Ь,..., х) — более короткое обозначение для вектора-столбца). Назовем код, кодирующий й битов информации и битами [и, й]-кодом. Наш пример, таким образом, является [3, Ц-кодом. Несколько более сложный пример — кодирование двух битов тройным повторение каждого из них — [6, 2]-код. Образующая матрица для такого кода 1 0 1 0 1 0 0 1 0 1 0 1 (10.54) Действительно, С(0,0) =(0,0,0,0,0,0), С(0,1) =(0,0,0,1,1,1), (10.55) С(1,0) =(1,1,1,0,0,0), С(1,1) =(1,1,1,1,1,1). (10.56) Множество возможных кодовых слов является линейной оболочкой столбцов матрицы С, поэтому, чтобы все сообщения кодировались единственным способом, мы должны потребовать, чтобы столбцы С были линейно независимы.
Других ограничений на С мы не накладываем. Упражнение 10.14. Приведите выражение для образующей матрицы, которая преобразует каждый из й битов в г его копий. Это линейный [гй, й]-код, его порождающая матрица должна иметь размер гй х й 10.4. Построение квантовых кодов 549 'Упражнение 10.15. Покажите, что прибавление одного столбца С к другому даст порождающую матрипу для того же кода.
Большим преимуществом линейных кодов по сравнению с другими кодами является их компактная запись. Чтобы задать произвольный код, кодирующий /с битов и битами, потребуется 2» кодовых слов, каждое длиной п. Такой код полностью описывается п2«битами информации. Для линейного кода необходимо задать только вп битов образующей матрицы. Таким образом мы имеем экспоненциалъную экономию объема памяти! Компактное описание обеспечивает простоту кодирования и декодирования. Это очень важное свойство классических линейных кодов, а также их квантовых аналогов — симплектических кодов.
Мы видим, что кодирование линейным кодом заключается в умножении в-битового сообщения на порождающую матрипу и х в. Эта процедура может быть выполнена с помощью 0(ив) операций. Описание линейных кодов с помощью порождающей матрицы позволяет легко производить кодирование. Процесс исправления ошибки не так очевиден. Однако, он становится легко понятным при другом (эквивалентном) описании линейных кодов с помощью проверочной матрицы. По определению, )п, в)-код состоит из всех и-элементных векторов я в пространстве Ею таких, что (10.57) Нх = О, где матрица Н с элементами 0 или 1 имеет размер (и — и) х и и называется проверочной матрицей.
То же самое, но более кратко: код является ядром матрицы Н. Код, кодирующий в битов, имеет 2«возможных кодовых слов, поэтому ядро Н должно быть и-мерным и, следовательно, мы должны потребовать линейную независимость строк Н. Упражнение 10.16. Покажите, что прибавление одной строки проверочной матрицы Н к другой не изменит код. Используя метод исключения Гаусса и перестановки битов, можно привести проверочную матрицу к стандартному виду )АД «], где А — матрица (и — к) х в.
Чтобы установить взаимосвязь между описаниями линейных кодов через порождающую матрицу и через проверочную матрицу, нужно разработать процедуру преобразования матрицы проверки на четность Н в образующую матрицу С и обратно. Чтобы перейти от проверочной матрицы к порождающей матрице, выберем Й линейно независимых векторов ум ..., у«, для которых ядро Н является линейной оболочкой. Матрицу С составим из столбцов уп..., у«.
Чтобы перейти от порождающей матрицы к проверочной матрице, возьмем и — Й линейно независимых векторов (ум...,у„«), ортогональных столбцам С, и составим матрипу Н из строк (у~т,..., у1 «). (Под ортогональностью мы понимаем равенство нулю скалярного произведения по модулю 2.) В качестве примера рассмотрим [3, 1)-код с повторением, заданный порождающей матрицей (10.53). Чтобы построить Н, возьмем 3 — 1 = 2 линейно независимых вектора, ортогональных столбцам С, например (1,1,0) и (0,1,1) и определим проверочную матрицу как 550 Глава 10.
Исправление квантовых ошибок (10.58) Легко проверить, что Нх = 0 только для кодовых слов х = (О, О, 0) и х = 1, 1, 1. 'Упражнение 10.1Т. Найдите проверочную матрицу для (6,2]-кода с повторением, заданного порождающей матрнцей (10.54). Упражнение 10.18. Покажите, что проверочная матрица н порождающая матрица для одного н того же кода удовлетворяют условию НС = О.
Упражнение 10.19. Пусть линейный [п, 1]-код С имеет проверочную вида Н = (А~1„ь), где А — некоторая матрица размера (и — й) х lс. Покажите, что соответствующая порождающая матрица (10.59) (Можно заметить, что А = — А, так как мы работаем в пространстве Ез. Однако, это равенство справедливо для линейных кодов не только в пространстве Ею но и в более общем случае.) Проверочная матрица делает достаточно очевидным процесс обнаружения и исправления ошибки. Пусть мы кодируем сообщение х сообщением д = Сх, но нз-за шума возникает ошибка е, преобразующая закодированное сообщение в у' = у + е. (Здесь + обозначает побитовое сложение по модулю 2.) Так как Ну = 0 для любого закодированного сообщения, Ну' = Не.
Мы назовем Ну' синдромом ошибки. Его роль похожа на роль синдрома в исправлении квантовых ошибок; он является функцией испорченного ошибкой состояния у' подобно квантовому синдрому, который определяется результатом измерения испорченного квантового состояния. В соответствии с соотношением Ну' = Не синдром содержит информацию об ошибке, что позволяет восстановить исходное закодированное сообщение у.
Чтобы увццеть, как это может быть сделано, предположим, что ошибка произошла не более. чем в одном бите. Синдром Ну' равен нулю в случае отсутствия ошибки и равен Неэч если ошибка произошла в ~-ом бите. Здесь еэ — вектор с единственным ненулевым ~-ом элементом равным 1. Если предположить, что ошибка произошла не более чем в одном бите, то можно исправить ошибку. Вычислив синдром Ну' и сравнив его с различными возможными значениями Не, мы определим, в каком бите произошла ошибка (это возможно при Не ф Неь для 1 ф к.
— Ред.). Вопрос о том, как можно исправлять ошибки с помощью линейного кода, с более общих позиций можно рассмотреть с использованием мешрики. Пусть х и у — и-битовые сообщения. Метирика (Хэмминга) д(х, у) длн х и д вводится, как число различающихся позиций в х и д. Например, Ы((1, 1, О, О), (О, 1, О, 1)) = 2. Весом (Хэмминэа) для сообщения х называется расстояние в метрике Хэммннга от х до сообщения, состоящего нз одних нулей эх(х) ш д(х, 0), т. е.
число ненулевых битов в х. Обратите внимание, что д(х, д) = нФ(х + д). Предположим, что мы кодируем х сообщением у = Сх с помощью линейного кода. 10.4. Построение квантовых кодов 551 Под действием шума в закодированном сообщении возникает ошибка, преобразующая сообщение в д' = д + е. Если вероятность изменения бита меньше 1/2, то кодовое слово вероятнее всего таково, что число измененных битов в д' по сравнению с д минимально, т.
е. д такое, что нС(е) = в(д, д') минимально. В принципе исправление ошибки может быть произведено просто заменой д' на такой д. На практике, однако, это может быть довольно неэффективно, так как определение минимального расстояния 6(д, д') в общем случае требует перебора 2" возможных кодовых слов д. Важной задачей классической теории кодирования является построение кодов специального вида, позволяющих исправлять ошибки более эффективно.
Мы не рассматриваем такие построения в этой книге. Общие свойства кодов также могут быть описаны с помощью метрики Хэмминга. Определим кодовое расстояние как минимальное расстояние между двумя кодовыми словами: (10.60) Но И(х, д) = нс(х + д). Если х и д — кодовые слова, то из линейности кода следует, что х + д — также кодовое слово. Отсюда получаем, что 6(С) = ппп аз(х). тес,я~с (10.61) О 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 О 1 0 1 (10.62) Вводя обозначение д = И(С), мы говорим, что код С является (п, в, в)-кодом. Важность кодового расстояния состоит в том, что код с кодовым расстоянием, не меньшем 2$ + 1 для некоторого положительного $, может исправлять ошибки в не большее, чем 8 битах просто заменяя испорченное состояние д' единственным кодовым словом д, таким, что П(д, д') < $.
Упражнение 10.20. Пусть Н вЂ” проверочная матрица такая, что любые ее 4 — 1 столбцы линейно независимы, но существует набор из линейно 6 зависимых столбцов. Покажите, что код, заданный матрицей Н, имеет кодовое расстояние в'. Упражнение 10.21 (граннца Синглтона). Покажите, что (п, й, о)-код должен удовлетворять неравенству п — Й > д — 1. Хорошим примером класса линейных кодов, исправляющих ошибки, являются коды Хэмминга. Пусть г > 2 и Н вЂ” матрица с 2" — 1 столбцами битов длины г, не равными тождественно нулю.
Такая проверочная матрица определяет линейный [2" — 1, 2" — г — Ц-код, который называется кодом Хэмминга. Особенно важен для исправления квантовых ошибок случай т = 3, ~7,4]-код с проверочной матрицей 552 Глава 10. Исправление квантовых ошибок Любые два столбца Н различны и, следовательно, линейно независимы.
Первые три столбца линейно зависимы, поэтому из упр. 10.20 следует, что кодовое расстояние для такого кода равно 3. Таким образом, код может исправлять ошибку в одном бите. Процедура исправления ошибки очень простая. Пусть ошибка возникла в ~-ом бите. Из матрицы (10.62) видно, что синдром ошибки Нез — это просто двоичное представление ), показывающее, какой бит нужно изменить, чтобы исправить ошибку. 'Упражнение 10.22.
Покажите, что все коды Хэмминга имеют кодовое расстояние 3 и, следовательно, могут исправлять ошибку в одном бите. Т. е. коды Хэммига — (2' — 1, 2" — г — 1, 3]-кодьь Что можно сказать относительно общих свойств линейных кодов? В частности, нам хотелось бы получить условия существования кодов с заданными параметрами. Не удивительно, что существует много методов для получения таких условий. Один такой набор условий называется ~аницей Варшамоеа1Ълъберпю: для больших и существует [и, Й)-код, исправляющий ошибки в $ битах, для некоторого х, такого, что п $ — ) 1 — Н( — ), (10.63) и' где Н(х) и -х 1оя(х) — (1 — х)!ой(1 — х) — двоичная шенноновская энтропия, которая будет подробно рассмотрена в гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
