У. Питерсон - Коды, исправляющие ошибки (1267328), страница 17
Текст из файла (страница 17)
(См. задачу 3.5.) Матрица С является симметричной, поэтому, если умножить ее саму на себя, получится матрица, у которой все диагональные элементы равны 2х-', а все недиагональные элементы равны 2ь-з. Таким образом, Сз=2ь-в(! -1-.1), где через 1 обозначена единичная матрица, а через ! — матрица, состоящая из одних единиц.
Легко проверить, что С! = 2"-'.1. Следовательно, откуда (3.19) Таким образом, если имеется совокупность весов кодовых слов, упорядоченных так же, как кодовые слова в соотношении (3.18), го можно найти вектор модулярного представления и тем самым определить код с точностью до перестановки столбцов. Некоторая заданная совокупность чисел может быть совокупностью весов, если из этих чисел можно образовать вектор %, такой, что компоненты вектора И =%С вЂ” ' будут неотрицательными целыми числами. В качестве простейшего приложения этого принципа исследуем, при каких условиях все кодовые слова могут иметь один и тот же зес шм В этом случае возможно только одно расположение элементов вектора %.
Произведение %С вЂ ' состоит из компонент, каждая из которых равна гзз2-~"-и, так как в каждой строке матрицы С вЂ” ' число положительных элементов на единицу больше числа отрицательных элементов. Поскольку вектор 1ч' =%С вЂ” ' должен соде~жать только целые компоненты, то число шз должно делиться на 2 -', т. е.
должно иметь вид шр — — !2"-'. Тогда каждая компонента вектора в) равна ! и код состоит из ! столбцов каждого типа. Пример. Для й = 3 матрица М может быть выбрана следующим образом. 0001111 йй= 0110011 1010101 (Столбцы матрицы упорядочены так же, как двоичные числа.) Тогда 1 с 4 Для кода, использованного в предыдущих примерах, -1ОО11— О= О1О!О оо!о! %=(2,2,4,3,3,3,3).
3.7, Эквивалентность линейных блоковых кодов При изучении свойств кодов, в которых расположение столбцов несущественно, т. е. свойств, общих для эквивалентиых кодов, особенно удобно пользоваться модулярным представлением. Однако существует много различных способов выбора базиса для одного и того же кода и, следовательно, много различных порождающих матриц. Вообще говоря, различные порождающие матрицы будут приводить к различным векторам модулярного представления, и желательно знать, когда модулярные представления описывают эквивалентные коды, Существует два очевидных необходимых условия.
Если два столбца для некоторого кода совпадают, то они будут совпадать при любом выборе базиса, и поэтому если иекоторый столбец типа 1О1О1О1- О11ОО11 1!ОО!1О ООО1!!! !О!!О!О О11!!ОО 11О1ОО! ОО1О1- О1О1О о!!!! 1ОО11 1О!!О !1ОО! 11!ОО ; появляется л; раз в одном представлении, то в любом другом представлении того же самого или эквивалентного кода столбец некоторого другого типа появляется также л~ раз. Таким образом, компоненты вектора г( могут меняться местами, но не заменяться другими числами. Аналогично компоненты весового вектора % могут меняться местами, но не заменяться другими числами.
Теперь задача сводится к описанию перестановок. Пусть Ь вЂ” любая невырожденная матрица размерности й Хй. Если т, и та — векторы с й компонентами каждый, то т,К вЂ” чз8 = = (ч~ — тэ) $ есть линейная комбинация строк матрицы $, и поскольку строки матрицы $ линейно независимы, то к~8 — тай = О только тогда, когда т~ — тз = О. Поэтому если векторы т~ и тз не совпадают, то не совпадают и векторы т,8 и т~$. Поэтому все д" — 1 строк матрицы МтЬ будут различны, если М вЂ” матрица, определенная в разд. 3.6.
Так как имеется ровно ф — ! различных ненулевых векторов, то матрица МтЬ должна отличаться от матрицы Мт только расстановкой строк: Мг3 Р Мг (3.20) где Рз — некоторая матрица перестановки. Эта матрица называется А-перестановкой, соответствующей Ь. (Заметим, что матрица Рз зависит также от выбора матрицы М.) Для каждого ! среди строк матрицы Мт имеется какая-либо, скажем й-я, строка, в которой находится вектор, все компоненты которого, кроме (-й, равны единице, а 1-я компонента равна нулю. Поэтому (-я строка матрицы Б оказывается й-й строкой матрицы РзМт, и, следовательно, различные матрицы Б приводят к различным перестановкам Рз.
Далее, если 5 и Ю вЂ” невырожденные матрицы размерности й;х' ,й, то М*Я! = РзМги = РзР,Мг, (3.21) т. е. произведению Я3 соответствует перестановка РзРю Отсюда следует, что А-перестановки образуют группу, изоморфную (т. е. обладающую той же самой структурой) группе невырожденных матриц размерности й Х й. Рассмотрим теперь результат применения А-перестановки к строкам матрицы С = МтМ. Пусть () = (Б-')*. Тогда РзСРй = РзМ МРй = РзМ (РиМ ) (Мтс)(Мг(!)г Мт3()тМ МгМ Так ак как матрица перестановки является ортогональной матрицей, то Рт = Р-~ и Р С=СР (3.22) Поэто этому применение А-перестановки к строкам эквивалентно применению ению другой, но связанной с ней А-перестановки к столбцам матрицы С. Выбор нового базиса и порождающей матрицы для группового кода соответствует умножению слева порождающей матрицы на некоторую невырожденную матрицу Ь.
Ненулевые кодовые векторы для порождающей матрицы Ьб являются строками матрицы Мг(зб) =(Мгз) б =(Р М)г б = Р (Мгб), (З.2З) т. е. строками матрицы М*б, переставленными с помощью Рв. Таким образом, выбор нового базиса эквивалентен применению А-перестановки к кодовым словам. Очевидно, что эти рассуждения могут быть проведень! и в обратную сторону. Аналогично столбец типа ! матрицы Мтб, в которой перечислены все кодовые слова, совпадает с !-м столбцом матрицы С.
Поэтому в матрице Мт($6) = Рв(мтб) этот столбец совпадает с !зм столбцом матрицы РвС. Но РвС = СРс, где 0 = (Б — ')*, и поэтому столбец матрицы С, который соответствует !-му столбцу матрицы РвС, является тем самым столбцом, который матрица перестановки Рп переводит в !-й столбец. Следовательно, г г ! )зо = Рз! ) о, (3.24) где !чвс и Ыв — модуляриые представления кодов, порождающими матрицами которых являются соответственно матрицы Ьб и $. Итак, две различные порождающие матрицы приводят к модулярным представлениям, которые отличаются Л-перестановкой.
Обратное утверждение может быть доказано аналогичным образом. 3.3. Распределения весов и тождества Мак-Уильямс Обозначим через А, число кодовых слов веса ! в блоковом (и, й)-коде. Числа Л!, ! = О, 1, ..., п, задают распределение весов нли весовой спектр кода. Понятие распределения весов имеет многочисленные приложения прн исследовании кодов. Например, зная числа Аь можно вычислить вероятность необнаружения ошибки для группового кода, используемого исключительно для обнаружения ошибок в двоичном симметричном канале.
Необнаружение ошибки происходит, только если вектор-ошибка является ненулевым кодовым словом. Следовательно, (3.25) Аналогичный, ио более сложный результат может быть получен для некоторых случаев исправления ошибок (2!1 На современных цифровых машинах можно определить распределение весов кода путем простого перебора всех 2" кодовых слов при условии, что й не превышает примерно 25.
Распределение весов таких кодов может быть найдено с помощью тождеств Мак- уильямс, которые позволяют вычислить распределение весов кода на основе распределения весов нулевого пространства кода, т. е. двойственного кода. Справедлива следующая теорема: Теорема 3.14 [194]. Пусть 1'1 — блоковый (и, я)-код, а Гг— (и и — й)-код, являющийся пулевым пространством кода $'ь А~ и В, обозначают число векторов веса 1 в кодах У1 и тз соответственно.
Тогда гх Х л1(1 — Х) [1 + (д — ц Х]"- ( 1-о доказательство. Эти формулы можно записать более компактно с помощью производящих функций А (Х) = 2 А;Х', В(Х) = 2; В,Х'. В этих обозначениях формула (3.25) перепишется в виде Р,=Р"А ( 9, а равенство (3,26) — как де В (Х) = [1 + (д — Ц Х]" А ( — ] . Существует несколько различных наборов тождеств, эквивалентных равенству (3.26), и значительно проще получить один из них, чем доказывать равенство (3.26). Поэтому сначала будут выведены эквивалентные тождества, а затем проведено их доказательство.
Приравнивая коэффициенты при Х' в левой и правой частях равенства (3.26), получим явную формулу, выражающую В; через все А;: Ю п л„В,Х'=о ~ ~, Ат(1 — Х) [1+(о — ЦХ]" ~= 8-0 ю-ь в' ! ь~ =д-'Х Х 2.'А,с',( — ц'х'с„',(у — ц'х'. с с Положим з+ г = 1 и исключим 1 из этого выражения: и п ! ь-/+8 ~, В;Х'=д ~ ~ ~ 2„' А!СгС':у( — ц (д — ц 'Х в ь =у' Х Х Х А~С)С 'г( — Ц'(у — Ц 'Х'= С-ь ь о ~-о и ь = у-'2. х' Х А, Х С1с;'; ( — 1)*(у — Ц' ', 1-о 1 о ч-о Суммирование по ! от 0 до и во втором выражении вместо суммирования от ! = з до п — !+ з возможно потому, что все вводимые при этом дополнительные члены равны нулю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
