У. Питерсон - Коды, исправляющие ошибки (1267328), страница 57
Текст из файла (страница 57)
Наконец, обозначим через 6 группу перестановок Р, обладающих тем свойством, что если ъ — вектор нз р'ь то для любой перестановки Р из 6 вектор вР также принадлежит рь Говорят, что код к'г инвариантеи относиТельно группы перестановок ег, Пример. Если Р— перестановка и символов, в результате которой компоненты вектора циклически перемешаются на одно место вправо, то перестановки 1, Р, Рз, ..., Р"-' образуют группу, относительно которой инвариантен любой циклический (п, к) -код.
Однако довольно часто коды могут обладать ббльшими группами симметрии — например, можно показать, что двоичный (23, 12)-код Голеи инвариантен слева относительно группы Матье [2451. Теорема 8.11. Если код Р, инвариантен относительно группы 6 перестановок Р, то нулевое пространство те кода $'~ также инвариантно относительно группы 6. Доказательство. Заметим, что для любых двух векторов ч~ и тт и для любой перестановки Р ч, ° чт = (ч, Р) ° (ч,Р). (8.28) В самом деле, в каждой части этого равенства стоит сумма произведений соответствующих компонент векторов ч~ и чь Правая часть отличается от левой только перестановкой слагаемых, задаваемой перестановкой Р, отчего, очевидно, сумма не может изме- виться; следовательно, равенство справедливо. Пусть че — вектор, принадлежащий Рм а ч~ — любой вектор из Уь Тогда в соответствии с равенством (8.28) (чтР) ° ч,=в,р (ч,р 'Р)=чт ° (ч,Р '), но перестановка Р-' принадлежит 6, поскольку 6 — группа.
Следовательно, вектор ч~р-' принадлежит Уь а так как вектор чт принадлежит нулевому пространству кода т'„то (чзР) ' ч~ = те (я~р ) = О Таким образом, вектор чар ортогонален любому вектору ч~ из Рь откуда следует, что вектор ч,р принадлежит Рв Ч. т. д. Теорема 8.12. Если У вЂ” некоторый смежный класс кода Уь инвариантного слева относительно перестановки Р, то множество УР всех векторов, получаемых при применении перестановки Р к векторам из О, также является смежным классом для кода Уь Доказательство. Пусть п~ и пе — любые два вектора из К Тогда множество УР является смежным классом тогда н только тогда, когда вектор п~Р— пер принадлежит коду, т. е.
является вектором из 1~ь Но н,Р— п,р=(н, — ат)Р, (8.29) и поскольку У вЂ” смежный класс, то вектор н~ — па и, следовательно„вектор (п~ — пт)Р принадлежат коду. Справедливость равенства (8.29) можно доказать, если заметить, что безразлично, будет ли сначала произведена перестановка компонент векторов, а датем вычитание или наоборот. С другой стороны, если переста- нонка записана в виде матрицы, то равенство (8.29) следует из дистрибутивного закона для матричного умножения. Ч. т.
д. Группа б перестановок п символов разбивает пространство Р всех векторов длины п на классы. Два вектора и! и чт принадлежат одному и тому же классу, если существует перестановка Р в группе б, для которой ч,р = от Если код Р! инвариантен слева относительно группы б, то этот код Р! должен состоять нз некоторого числа полных классов пространства й'. Согласно теореме 8 11, нулевое пространство кода и'! также состоит из некоторого числа полных классов пространства. При заданном коде Р, два смежных класса У, н Ут эквивалентны, если существует перестановка Р из б, такая, что У,Р = = Уз.
Таким образом, совокупность смежных классов также разбивается на классы, причем У, и ба принадлежат одному классу тогда и только тогда, когда они эквивалентны. Если смежные классы У> н бт эквивалентны, то некоторая перестановка элемента минимального веса из У, принадлежит Ут, и наоборот; следовательно, (У, и Ут обладают одним и тем же минимальным весом.
Пример. Рассмотрим совокупность всех 7-компонентных векторов над полем бг"(2) и группу 1, Р, Рт, ..., Ре циклических перестановок. 128 векторов этой совокупности разбиваются на 20 классов. В табл. 8.1 представлено по одному вектору из каждого класса. Остальные векторы в каждом классе получаются как циклические сдвиги выделенного представителя этого класса. Векторы, состоящие из одних единиц или из одних нулей, порождают классы, содержащие один элемент.
В остальных классах имеется по 7 векторов — 7 циклических сдвигов заданного вектора. циклический (7,4)-код, приведенный в примере равд. 8.1, включает классы Л, б, 7. и Р, всего 16 векторов. Нулевое пространство состоит только из нулевого вектора и класса 7., всего из восьми векторов. Смежные классы разбиваются только на два класса: один из пих образуется самим кодом, а второй состоит из семи смежных классов, образуюп1ими которых являются элементы класса В.
Вообще всегда число классов, содержащихся в нулевом пространстве, совпадает с числом классов, на которые разбивается совокупность смежных классов. Доказательство этого приводится в книге Питерсона 1234!. Таблица 0.1. Классы 7-компоиеитиык двоичных векторов А0000000 Р1110000 К0001 111 Р1111 ! 11 В1000000 61101000 Е0010111 00111111 С 1100000 Н !100100 М0011011 11001111! й!010000 !1100010 Л~001!101 оп!011!! Е1001000 71010100 00101011 70110111 Теорема 8.13. Если (и, д) = 1, то любой циклический код длины п инвариантен относительно перестановки Р, которая для каждого ! перемещает символ из 1-го разряда вектора в разряд с номером ф по модулю п.
Доказательство. Если 1(Х) — многочлен из кода, то в результате перестановки Р слагаемых многочлен !(Х) превращается в многочлен 1(Хч) по модулю Х" — 1. По 1(Хч)=(!(Х))ч. Если д(Х) — порождающий многочлен кода, то !(Х) и Х" — 1 делятся на д(Х). Следовательно, многочлен !(Хч) по модулю Х" — ! также делится на д(Х) и является, таким образом, кодовым вектором. Ч.
т. д. Группа перестановок называется транзитивной, если для любых двух символов кодового вектора существует перестановка, в результате которой эти символы меняются местами, причем возможно, что при этом происходит перегруппировка других символов. Обозначим через А; число кодовых слов веса 1 в коде Рь Теорема 8.14. Если код инвариантен относительно транзитивной группы перестановок, то (Л; полностью делится на и.
Доказательство. Расположим все кодовые векторы веса ! в столбец. Затем применим ко всем этим кодовым векторам перестановку„в результате которой меняются местами первый и !чй столбцы. После этой перестановки вес векторов ! не меняется, и все векторы по-прежнему различны. Таким образом„в целом эта совокупность векторов совпадает с первоначальной, может измениться только порядок векторов.
Это, однако, не влияет на число ненулевых компонент в первом столбце, а число ненулевых компонент в 1-м столбце должно совпадать с числом ненулевых компонент в первом столбце. Обозначим вес этого столбца через аь Тогда общее число ненулевых компонент во всей совокупности равно весу столбца, умноженному на и, или весу строки, умноженному на Л;, Итак, (8.30) па, = 1Лн Ч. т. д. Теорема 8.15. Пусть У вЂ” некоторый (и, й)-код, образованный отбрасыванием первого символа из (п+ 1, й)-кода т'ь инвариантного относительно трапзитивной группы и не содержащего векторов веса ! — 1. Тогда, если через В; обозначено число кодовых векторов веса 1 из Р, то 1В; = (и+ ! — 1) В.; ~ для, четных Е Доказательство. Если через Л; обозначено число кодовых векторов веса ! в первоначальном коде, то, как доказано в теореме 8Л4, (8.31) (и + 1) В;, = (А„ поскольку число кодовых векторов веса ! — 1 в г' должно совпа- дать с числом кодовых векторов веса 1, первый элемент которых отличен от нуля.
Далее, (8.32) Подставляя это выражение для А; в равенство (8.31), получаем желаемый результат. Ч. т. д. 1= Х Ьср и-а (8.33) где О~(бг-".р — 1 прн 0- 1~(в1 — 1. (8.34) Многие циклические коды длины п могут быть образованы путем отбрасывания первого символа каждого кодового слова из кода длины и+ 1, инвариантного относительно дважды транзитивной группы перестановок. (Группа перестановок называется дважды транзитизной, если для любых различных целых положительных чисел 1, 1, й, 1, пе превосходящих а, существует перестановка, в результате которой одновременно меняются местами символы с номерами 1 и 1 и символы с номерами й и 1.) Это верно для кода Голея, всех квадратично-вычетных кодов (236) и для всех примитивных БЧХ-кодов (равд.
9.3) и примитивных циклических кодов Рида — Маллера (равд. 10.2). Ко всем этим кодам применимы теоремы 8.14 и 8.15. Существует большой класс циклических кодов длины д"' — 1, которые в результате расширения их путем присоединения дополнительного проверочного символа, равного проверке на четность по всем символам кода, становятся инвариантными относительно дважды транзитивной аффинной группы. Аффинныл преобразованием с параметрами а и Ь, где а ~ 0 и а и Ь являются элементами поля ОГ(ц"), называется преобразование, которое переводит символ Х в символ аХ+Ь. Код называется инзариантным относительно аффинной еруппы, если любое аффинное преобразование переводит любое кодовое слово в некоторое другое кодовое слово.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
