Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 95

приложение). В частности, одним полезнымсвойством самодуальных РМ-кодов является их «двойная четность»- всекодовые слова имеют кратный четырем вес.Конечно, применяя КШС-конструкцию к РМ-кодам, мы также можемпостроить квантовые коды с k> 1. Например,R(3, 6) с параметрамиn =2m= 64,d = 2m-r = 8,k = 1+( ~) + ( ~) + ( ~)дуален по отношению кR(2, 6)= 1 +6+ 15 + 20 =42(7.231)с параметрамиn =2m= 64,d = 2m-r = 16,k= 1 + (~) + (~)=1 + 6 + 15= 22,(7.232)и, следовательно, КШС-конструкция дает КККО с параметрами[[64, 20, 8]].(7.233)Известны многие другие слабо самодуальные коды, которые можно исполь­зовать таким же образом.82ГЛАВА7.15.4.7Код ГолеяС точки зрения чистой математики, самым интересным из когда-либооткрытых корректирующих ошибки кодов (классических или квантовых)является код Голея, который был еще и одним из первых, описанныхв открытой печати. Здесь мы кратко опишем его, поскольку с помощьюКШС-конструкции этот код тоже может трансформироваться в хорошийКККО.

(Возможно, этот КККО на самом деле не настолько важен, чтобыпосвящать ему раздел в этой главе; и все же он достаточно занятный, такчто я включил его сюда.)Код Голея (расширенный) представляет собой самодуальный класси­ческий код [24, 12, 8]. Если мы выколем его (удалим любой из его 24-х би­тов), то получим код Голея [23, 12, 7], который может исправить три ошиб­ки. Этот код на самом деле является совершенным, так как он насыщаетграницу упаковки сфер:(7.234)На самом деле, совершенные коды, исправляющие больше одной ошиб­1ки, - невероятпая редкость.

Можно по казать, что способными исправитьбольше одной ошибки совершенными кодами (линейными или нелинейны­ми) над любым конечным полем являются всего лишь два: код [23, 12, 7]и еще один открытый Голеем двоичный код с параметрами [11, 6, 5].Код Голея [24, 12, 8] имеет очень сложную симметрию. Она характери­зуется своей группой автоморфизмов-группой перестановак 24-х битов,преобразующих одни кодовые слова в другие. Это группа Матье М24 , от­крытая в122XIX веке спорадическая простая группа порядка 244 823 040.4096 кодовых слов имеют распределение весов (в очевидном=обозначении)(7.235)Отметим, в частности, что каждый вес кратен четырем (код имеет двойнуючетность).

Каков смысл числа759 ( = 3 · 11 · 23)?На самом деле оно равно(7.236)1См. § 6.1 О в книге Е. 1. MacWilliams. N. 1. А. Sloane, Тhе Тheory of Error-Correcting Codes,North Holland PuЬ!ishing Company, Amsterdam, New York, Oxford (1977); перевод: Ф. Дж. Мак­Вильяме, Н. Дж. Слоэн, Теория кодов, исправляющих ошибки.

- М.: Связь, 1979.7.15.НЕКОТОРЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ МНОГОКРАТНЫЕ ОШИБКИ83и возникает по комбинаторной причине: каждое кодовое слово с весом во­семь характеризуется своим носителем- 8-элементным множеством («ок­тадой» ). Последние выбираются таким образом, чтобы каждое 5-элемент­ное подмножество 24-х битов содержалось (целиком) в одной и только од­ной такой октаде (отражение высокой симметрии кода).Что придает коду Голея математическую значимость? Его открытиев1949 году привело в движение последовательность событий, которые при­мерно к 1980 году завершились полной классификацией конечных простыхгрупп. Эта классификация является одним из величайших достижений ма­тематики ХХ века.(Группа является простой, если она не содержит ни одной нетривиаль­ной нормальной подгруппы. Конечные простые группы можно рассматри­вать как строительные блоки всех конечных групп в том смысле, что длялюбой конечной группыGсуществует однозначное разложение вида(7.237)где каждая Gн 1 представляет собой нормальную подгруппуGj,а каж­дая фактор-группа Gj/Gн 1 является простой.

Конечные простые группыможно систематизировать в разные бесконечные семейства, плюс26до­полнительных не поддающихся классификации «спорадических» простыхгрупп.)В1964году код Голея привел Лича к открытию чрезвычайно плотнойукладки шаров в 24-х измерениях, известной как решетка Лича А. Узлырешетки (центры сфер) представляют собой 24-компонентные целочислен­ные векторы со следующими свойствами: чтобы определить, содержитсялих= (х 1 ,х 2 , ... х 24 ) в А, запишем каждую компоненту xj в двоичномпредставлении(7.238)Тогда х Е А, если 1(i)(ii)все Xjo либо нули, либо единицы;х j2 представляют собой четную 24-битовую строку, если все х jo равнынулю, и1Некоторые-нечетную 24-битовую строку, если все х jo равны единице;альтернативныеопределениярешеткиЛичаможнонайтивкнигеJ.

Н. Conway, N. J. А. Sloane, Sphere Packiпg, Lattices апd Groиps, Springer Verlag, NY, Berlin,et al. ( 1988), Chapter 4, § 11; перевод: Дж. Конвей, Н. Слоэн, Упаковки шаров, решетки и груп­пы.- М.: Мир, 1990, глава 4, § 11.- Прим. ред.84(iii)ГЛАВА7Хр представляют собой 24-битовую строку, содержащуюся в коде Го­лея.При употреблении этих правил отрицательное число представляется егодвоичным доnолнением, например,-1 = ... 1111,-2 = ... 1110,-3 = ... 1101,(7.239)и так далее.Нетрудно проверить, что Л является решеткой: она замкнута относитель­но сложения. (На остальные биты, кроме битов последних трех разрядовдвоичного разложенияxj,никаких ограничений не накладывается.)Подсчитаем число ближайших к началу координат 1 соседей (или коли­чество сфер, касающихся любой данной сферы).

Все эти точки находятсяна расстоянии (distance) 2 = 32 от начала координат27 . 759,2 12 . 24,(±2)8(0)16(±3)(=F1)23(7.240)(±4)2(0)22Таким образом существует 2 7 · 759 ближайших соседей, радиус-векторы ко­торых имеют восемь отличных от нуля компонент, равныхколичество отрицательныхжащие носителям759-±2(среди нихчетное) и заполняющих позиции, принадле­кодовых слов Голея с весом восемь. Далее, суще­ствует 212 · 24 ближайших соседей, радиус-векторы которых имеют однукомnоненту, равнуюа остальные23±3(она может находиться в любой из 24-х позиций),компоненты равнываются компонентам,=f1.При этом верхние знаки приписы­которые заполняют позиции,принадлежащие носи­телям кодовых слов Голея произвольного веса. Если, например, выбранакомnонента+3,то занимаемая ею позиция вместе с позициями всех отри­цательных компонент (то есть -1) образует носитель одного из 2 11 остав­4шихся (из 212 ) кодовых слов Голея.

Наконец, имеется 22 · е2 ) ближайшихсоседей, радиус-векторы которых имеют только две отличные от нуля ком­поненты±4,положение и знак которых ничем не ограничены. В суммекоординационное число решетки равно196 560.1 Символ (а) k ( Ь) 1 обозначает вектор решетки х Е Л, имеющийи, соответственно, Ь.-Прим. ред.k и l компонент, равных а7.16.ПРОПУСКИЛЯ СПОСОБНОСТЬ КВАНТОВОГО КАНАЛА85Решетка Лича имеет замечательную группу автоморфизмов, открытуюКонвэем в1968 году.80(24)пы вращенийЭто сохраняющая решетку конечная подгруппа груп­пространства размерностигруппы (известной как·0,24.

Порядок этой конечнойили «точка нуль») равенЕсли ее двухэлементный центр выкидывается, получается спорадическаяпростая группа·1.К моменту ее открытия,·1была самой большой из по­строенных спорадических простых групп.Решетка Лича и ее группа автоморфизмов, в конечном счете, (путем,который не будет здесь описан) в1982году привели Грисса к построениюнаиболее удивительной из всех спорадической простой группы (на суще­ствование которой ранее указывали Фишер и Грисс).

Это конечная подгруп­па группы вращений в пространстве размерности196 884, порядок которойприблизительно равен 8.08 х 10 53 . Это чудище, известное как F 1 , получилопрозвище «монстр» (хотя Грисс предпочитает называть его «дружелюбнымгигантом»). Открытая последней, она является самой большой спорадиче­ской простой группой.Таким образом, классификация конечных простых групп многим обя­зана (классической) теории кодирования и, в частности, коду Голея. Воз­можно, теория КККО также завещает математике что-нибудь значительноеи очень интересное!Во всяком случае, поскольку (расширенный) код Голея [24, 12, 8] явля­ется самодуальным, то получаемый при выкалывании код [23, 12, 7]- слабосамодуальный; дуальный ему код [23, 11, 8] является его собственным суб­кодом.

Отсюда с помощью метода КШС можно построить КККО[[23, 1, 7]].Это не самый эффективный квантовый код, который может исправить триошибки (существует код[[17, 1, 7]],насыщающий границу Рейнса), но онобладает особенно тонкими свойствами, благоприятствующими помехо­устойчивым квантовым вычислениям (см. приложение).7.16.Пропускпая способность квантового каналаКак это до сих пор формулировалось, целью построения КККО явля­ется достижение максимального значения расстояния кодадлинеnи количестве закодированных кубитовk.d,при заданныхБольшее расстояние обес­печивает лучшую защиту от ошибок, так как код с расстояниемисправитьd~1стираний или(d~1) /2dможетошибок в неизвестных позициях.Мы видели, что можно построить хорошие коды, поддерживающие конеч-86ГЛАВА 7ную скорость воспроизведенияk/nпри большомошибок, количество которых пропорциональноnи корректирующие pnn.Теперь мы обратимся к другому, но достаточно близкому вопросу обасимптотическом исполнении КККО.