У. Питерсон - Коды, исправляющие ошибки (1267328), страница 58
Текст из файла (страница 58)
Эти коды описываются приведенной ниже теоремои; определения примитивных БЧХ-кодов прн та= 1 и примитивных обобщенных кодов Рида — Маллера показывают, что такие коды относятся к этому классу кодов. Пусть 1 — положительное целое число, которое меньше д"'. Тогда это число можно записать в системе исчисления по основанию р, где р — характеристика поля и д = р'. Для любого заданного 1 обозначим через ((1) совокупность всех ненулевых целых чисел 1, таких, что 1= ~', о1р, ~-о (8.35) где О~о~(Ь! при О(1~(т1 — 1. 8; = ~~ УлХл= О.
л-1 Пусть Т вЂ” некоторый элемент аффинной группы перестановок н параметры Т равны а и Ь. Тогда для любого кодового вектора ч из С, вектор ч'= Тч имеет ненулевую компоненту Ул в разряде аХл + Ь, где 1 ( Ь ( гв. Поэтому ч' принадлежит С, тогда и только тогда, когда для любого 1 Я;= Х У„(аХ„+Ь)'=О. (8.36) По формуле биномиального разложения получаем 8 (аХ + Ь)' = ~' С(а Ь' ~Х~. 1-О Таким образом, множество Щ содержит число 1 и все его потоь|ки (равд. 3.5). Пусть сх — примитивный элемент поля 6Е(д ).
Рассмотрим д-ичный циклический код С длины д™ вЂ” 1 с символами из 6Г(д), порожденный многочленом д(Х). По коду С можно построить код С„присоединив проверку на четкость по всем символам С и выбрав получаюшуюся сумму в качестве первого символа нового кода. Далее, пронумеруем компоненты кодового вектора кода С, следуюшим образом: первой компоненте припишем номер О, второй компоненте — номер 1, 1-й компоненте при 1) 2 — номер а' з.
Теорема 8.16. Расширенный код С, инвариантен относительно аффинной группы перестановок тогда и только тогда, когда для любого элемента а~, который является корнем порождающего многочлена д(Х), и для любого 1 из множества Х(1) элемент а1 также является корнем д(Х), и д(1) =~ О. Доказательство. Пусть Хь Хь ..., Х вЂ” номера разрядов, в которых расположены ненулевые компоненты вектора ч, а Уь Ум ... ..., У вЂ” значения этих ненулевых компонент, где Хле= 6Г(д ) и Ул — элемент из 6Г(д).
Тогда ч является кодовым вектором, если и только если для любого корня а' многочлена д(Х) Люкас (189) показал, что ~и 1 — ! С;= ~ Са,'(пюд р), ь=а где 8~ и ос определяются равенствами (8.33) и (8.35). Доказательство этого факта включено в книгу Берлекэмпа (2!$ Это произведение отлично от нуля тогда и только тогда, когда каждый сомножитель отличен от нуля„а это будет так тогда и только тогда, когда ог -6, для каждого 1. (По этому поводу см.
лемму !0.2.) Следовательно, С; ныл тогда и только тогда, когда 1 принадлежит 7(1). Теперь равенство (8.36) можно записать в виде Я( = ~ ~', УьК~а Ь' ~Х~ь= ~'„К~а Ь ~Ям (8.37) й-1ры(п тн> где все оставшиеся в сумме Ку =С~ отличны от нуля. Обозначим через И число элементов множества У(1), а сами элементы этого множества обозначим через 1ь 1м ..., 1н. Поскольку )у ( л — 1, то можно выбрать У различных ненулевых элементов из поля 6Г(д ): аь ам ..., ан. Затем из вектора ч образуем вектор ть применяя к ч аффинную перестановку Ть в результате которой символ разряда Х переводится в символ разряда а~Х+ 1, где 1 (1( Ж.
Пусть через Я,' (1) обозначено значение Я для вектора ть Тогда в соответствии с равенствами (8.37) В Я,'(1) = ~' Кг,а~'Я~,. (8.38) Равенство (8.38) можно записать в матричной форме: Ъ 1 ан 2 3 1~ / 1 ! а'а~. 2 2 а 'а ' . з з Я;(1) Я,' (2) Я', (3) К Я( К( Я( К( Я( Я;. (У) а,аД...ащ КгЯ;, /~!, /н Матрица ~аД является матрицей Вандермонда и, следовательно, г гП невыРождена. (См. равд. 9.2.) Поэтому Я((1)=0 при 1(1<0 тогда и только тогда, когда К~ Яг =0 при 1(1--У.
Так как величины Ку, отличны от нуля, то отсюда вытекает„что Я((1) =0 при 1(~1~~Ф тогда и только тогда, когда Я. =0 для 1, из Х(1). 1, Это означает, что Я1 = 0 тогда и только тогда, когда Яу = 0 для ( 8.12. Произведение циклических кодов Пусть С! и Сз — циклические коды длины и, и пз соответственно с символами из Ог (д). Тогда двумерная таблица символов ° ° ° ао«л,— и ° ° ° ««! !»ч — и аоо ао! а«о ««и (8.39) а«п.,— «!о а«,— и ! ° ° а«з» — и«м-и является кодовым словом произведения кодов, если каждая строка является кодовым вектором из С«, а каждый столбец — кодовым вектором из Сь В этом разделе будет показано, что векторы, задаваемые диагональными элементами матриц вида (8.39), образуют циклический код.
(Образующий многочлен для этого кода характеризуется теоремой 8.!9.) Теорема 8.18. Пусть (а«»1 — кодовое слово из произведения двух циклических кодов над 6г(«7)„длинь«которых и! и пз взаимно просты. Пусть «! — вычет по модулю и! числа «, а 1з — вычет по модулю и, числа «при 1=0, 1, ..., п«пз — 1. Тогда векторы [Ь«) длины и = п,п,, где 6! = а«,а;„образуют циклический код.
Способ образования вектора (Ь«1 продемонстрируем на следующем примере. Пусть и, = 5, по = 3, а аоо а„аьз ам аы (а««) = а«о ап а„а«з ам азо аз! азз азз ам тогда «Ь«! (а«й» ап а22 ««оз» а«4 аз! ао! «««2» азз» ао« «««о аз! ««оз ац а24) Доказательство. Если (пь пз) = 1, то соответствие 1а«!) и (Ь!) является взаимно однозначным. Далее, из равенства ~Ь«1 =~Ь~1 нз У(1). Итак, для любого вектора т из С, и любого преобразования Т вектор Тт приначлежнт С, тогда и только тогда, когда 8« — — О для «из У(«).
Но 3« — — О для любого вектора ч нз С„откуда следуст, что а~ — корень многочлена д(Х). Ч. т. д. Теорема 8.17, Если код С длины и = «7 инвариантен от«юсительно дваждь«транзитивной аффинной группы перестановок, то код С', получаемый из С отбрасыванием первого символа, является циклическим. Это утверждение следует из того факта, что преобразование Х'= аХ не влияет на первый символ расширенного кода, а на остальные символы воздействует как циклическая перестановка. Результаты этого раздела будут полезны при определении истинных минимальных расстояний для БХЧ-кодов (разд. 9.3).
следует, что 1,=1,' и 1з= 1'. Произведем циклический сдвиг каждой строки таблицы на единицу вправо и каждого столбца на единицу вниз. Другими словами, пусть 1( = г, + 1 пюд и„ 1з = 1з + 1 пюб п,. Из определения 1~ и 1з следует, что 1( = (1 + 1) пюб ли 1а (1 + 1) пюб и т, е.
в результате циклического сдвига строк и столбцов происходит циклический сдвиг вектора (Ьг) длины а на единицу вправо. Отсюда вытекает, что векторы (ЬД образуют циклический код. Ч. т. д. Известно, что в теории циклических кодов удобны обозначения, использутощис мпогочлены. Двумерная структура произведения циклических кодов наводит на мысль рассматривать кодовые слова как многочлены от двух независимых переменных (75). Рассмотрим многочлен й -! ж-1 1(Х, у)= ~., ~'., амХ'ут. (8.40) Пусть а, и аз — элементы порядков п~ и пт соответственно.
Введем также многочлен Л(г, У) = Х', 1(а,, У) г", (8.41) Применяя к коэффициентам при У~ для каждого 1 следствие из теоремы 8.2, получаем г(Х, у)=и;! К 8(п, Г)Х', (8.42) если (пь Р) = 1, где р — характеристика поля 6г(д). Аналогично пусть л,-1 р(Х, йу) = К Ю(Х, 9яГ1. (8.43) и-а Тогда, применяя это следствие к коэффициентам при Х' для каждого ю', получаем З(г,у)=а Х г(г, х )у', (8 44) У-0 если (пм Р) = 1. После подстановки выражения (8,41) в соотвоше- ние (8.43) имеем л,-! л,-! (8.46) Г(Х, )р)= Х Х ца1, 1)Х!(р1. а подстановка равенства (8,44) в соотношение (8.42) дает л,-! л,— 1 )(Х, У)=п ! ~ ~„Р(а ', а '1)Хоу! 1-о 1-о где и = п,п,.
Поскольку предполагается, что п, и пз взаимно простые, поря- дОК ЭЛЕМЕНта а = а!С!1 раВЕН П, И ВСЕ ЭЛЕМЕНТЫ 1, а, ао, ..., ал-! различны. Они представляют собой просто перестановку элементов вида а',а1„0(~1(~п! — 1, 0~(1~ п — 1. Действительно, а'=аа', причем показатель а! может быть приведен по модулю пь так как а",' = 1, и аналогично показатель ио может быть приведен по мо- дулю по. Далее рассмотрим вектор (Ьо, Ь1, ..., Ь„!) с компонен- тами Ь, = и !Р (а, ', а, ') (8.47) и соответствующий многочлен л-1 Ь(Х) =и ' Х Р(а, ', а ') Х'.
(8.48) 1-0 В соответствии с равенством (8.46) коэффициенты Ьо представ- ляют собой просто некоторую перестановку всех символов мат- рицы (8.39) и, следовательно, являются, в частности, элементами 6Г(д). Посмотрим теперь„ является ли циклический сдвиг вектора (Ьо, Ьь ..., Ь„ !) кодовым словом первоначального произведения кодов С, и С,. Предположим, что все строки матрицы (8.39) сдви- нуты циклически на один символ вправо, а все столбцы одновре- менно сдвинуты циклически на один символ вниз. Обозначим эле- менты получившейся матрицы через а,'.. Тогда 1'(Х, у)= Е Х а!1Х'у1= л;1 л,— ! д Хл' — 1 Х!+!у/+1 1-о 1-о ' Шеб 1'"' — 11 1 гпо11 Х"' — 1 ! =ХУ1(Х, У)~ „).
(8.491 гпоо) У": — 1 Таким образом, л.-1 л,-! Р'(у, М7) = 2 ~ 1' (а'„а1) 715'1= 1-о 1-о л,-! л;! ~', 1 (а11, а1) а'а~1Я~11'! = Е(а Е, аоИ~). (8.50) з-О1О Наконец, Ью — Р (~ аг ) = Г(а ~+~, о, г+1) — Ь Таким образом, в результате циклического сдвига элементов матрицы (8.39) на один символ вправо и одновременно на один символ вниз вектор Ь; сдвигается циклически на один символ. Отсюда следует, что векторы Ь; образуют циклический код длины и. Теорема 8.19 характеризует порождающий многочлен кода в случае, когда (п,р) = 1. Теорема 8.19. Предположим, что С~ и Сз — циклические коды, дли ы которых п~ и пг взаимно простые, а порождающие много- члены обозначены через д,(Х) и дз(Х).
Пусть С вЂ” циклический код длины и с порождающим многочленом д(Х), являющийся произведением этих циклических кодов. Предположим, что (и, р) = 1. Тогда а*' является корнем д(Х) тогда и только тогда, когда либо а', является корнем йц(Х), либо а,' является корнем пт(Х), либо оба. эти факта имеют место одновременно. Доказательство. Из равенств (8.46) и (8.48) вытекает, что Ь(Х) = 1(Х,Х), и поэтому Ь(а')=7(а, а). Так как строки матрицы (8.39) являются кодовыми векторами кода С„то 7(а', У)=О при любом У, если а' — корень и,(Х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
