У. Питерсон - Коды, исправляющие ошибки (1267328), страница 31
Текст из файла (страница 31)
То же самое верно для следующих четырех компонент: Ьз+ Ь, + Ь, + Ьз = а24. Аналогично Ь,+ЬО+Ьп+Ь, = Ь, + Ь, + Ь, + Ь, = Итак, имеется четыре независимых соотношения для определения ам. В общем случае было бы 2 -" независимых соотношений. Ошибки могут сделать некоторые из этих соотношений несправедливыми, но каждая ошибка влияет только на одно из соотношений, и, следовательно, если выбрать а„равным величине, появляющейся наиболее часто, то прн любой комбинации из 2 — ' — 1 нли меныпего числа ошибок значение ам будет все-такн декодировано правильно. Аналогичным образом определяются азь аз„ам, а42 и а43. После того как они определены, выражение амЧ4Чз + а42ЧЗУ2 + амЧЗЧ4 + 42ззУзУЗ + аззмзЧ4 + амЧЗЧ4 может быть вычтено из полученного вектора.
Тогда, если ошибок не было, останется вектор г'=аоч + ач,+ар + атг + а,ч, =(Ьп Ь', ..., Ь'), так что следующая совокупность коэффициентов может быть определена аналогичным путем. Существует восемь уравнений, которым должен удовлетворять символ а,: а~ = Ь! + Ьх = Ьз + Ь4 = Ь,'+ Ьз = Ь', + Ь; = = Ьз+ Ью= Ьп+ Ьж=Ь!з+ Ьи — — Ьм+ Ь|~.
Аналогичные уравнения справедливы для ам аз и а4. Наконец, если предполагать, что ошибок не было, то Р г — а~ч4 — а',чз — а,чх — а,ч, = а, ч,. Этот вектор должен быть нулевым, если а, = О, и единичным, если аз = 1, поэтому а, нужно выбирать равным тому из этих двух элементов, который появляется в векторе чаще. Поскольку при такой системе декодирования могут быть исправлены все комбинации из 2 ' — 1 или меньшего числа ошибок, то минимальное расстояние должно быть равно самое меньшее 2(2 -"-' — 1) +1 = 2 ' — 1, а так как все кодовые векторы имеют четный вес, то оно должно быть равно самое меньшее 2 -".
Но вес последнего базисного вектора равен 2 -', т. е. минимальному весу. Схему для определения того, суммы каких именно символов полученного вектора должны быть равны заданному информационному символу, можно описать следующим образом. Расположим символы в каждом из первоначальных векторов чь ..., ч так, как показано на фиг. 5.1, и назовем компоненту, соответствующую 1-мУ нУлю в вектоРе чь и компонентУ, соответствУющУю 1-й единице в векторе ть парными компонентами вектора чь Тогда 2 -' сумм парных компонент ч; используются для определения аь Далее, каждая из 2 — з сумм четырех компонент, используемых для опРеделениЯ ам, обРазУетсЯ некотоРыми двУмЯ паРными компонентами вектора ч, и парными для этих уже выбранных компонент компонентами вектоРа тн Аналогично каждое соотношение, опРеделяккцее апь представляет собой сумму некоторых парных ком.
понент вектора ч; плюс сумму компонент вектора чь парных к этим компонентам, и сумму компонент вектора чм парных к уже выбранным компонентам, так что в каждой сумме получается всего 8 слагаемых. Этот процесс можно продолжить аналогичным образом. Этн коды допускают интересную геометрическую интерпретацию. Рассмотрим пространство т измерений, координатами в котоом являются элементы поля, образованного двумя элементами.
меется всего 2 точек, и каждый из столбцов на фиг. 5.1 соответ- ствует одной из этих точек '), Вектор и, содержит 1 во всех точках, 1-я координата которых Х; равна О, т. е. в каждой точке гиперплоскости Х; размерности и — !. (Это вектор инцидентности.) Вектор чзч> содержит 1 во всех точках, которые принадлежат одновременно гиперплоскостям Х, и Х, и, следовательно, соответствуют матрице инцидентности для (и — 2)-мерной гиперплоскости, проходящей через начало координат, н т. д.
Так как код порядка г является нулевым пространством для кода порядка т — г — 1, то камсдое произведение из т — г — 1 или меньшего числа векторов ч, задает проверочное соотношение. С геометрической точки зрения, если символы кода расположены в соответствующих точках т-мерного пространства, то каждое проверочное соотношение представляет собой проверку на четность символов, связанных с точками проходящей через начало координат гиперплоскости размерности г+ 1 или больше. Каждая такая гиперплоскость определяет независимое проверочное соотношение.
Метод декодирования допускает следующую геометрическую интерпретаци>о. Каждый базисный вектор кода является произведением г или меньшего числа векторов уь ..., ч . Гиперплоскость размерности г содержит 2' точек, и, следовательно, произведение г векторов че содержит 2 единиц. Через каждую из этих точек проходит перпендикулярная гиперплоскость размерности г, содержащая также 2" точек. Это и есть совокупность точек, соответствующих суммам, используемым при декодировании информационных символов. Такая совокупность точек оказывается пригодной для этой цели, если ее вектор инцидентности содержит нечетное число единиц в тех же компонентах, что и вектор, коэффициент которого надо определить, и четное число единиц в тех же компонентах, что и все л>обые другие векторы, являющиеся произведением г или меньшего числа векторов чь пбскольку при этом условии нужный коэффициент в сумме останется, а все остальные сократятся.
Рассмотренные выше совокупности точек обладают этим свойством. В самом деле, из их перпендикулярности к заданной гиперплоскости следует, что каждая совокупность пересекает эту гиперплоскость в одной точке. В то же время каждая из них или совсем не пересекает никакую другую гиперплоскость размерности г или большей, или же пересекает ее по прямой илн по некоторой гиперплоскости большей размерности, так что эти совокупности с такими гиперплоскостями имеют четное число 2> общих точек, где 1 — размерность пересечения. В гл. 10 будет показано, что коды Рида — Маллера эквивалентны двоичным эвклидово-геометрическим кодам, которые являются циклическими кодами с дополнительной проверкой на четность по всем символам.
') А именно точке е коорхинатамн, нолучакацнмнсн заменой в столбцах ! на 0 и 0 на 1. — Пршв. »ед. б.б. Коды, получаемые с помощью матриц Адамара Матрицей Адамара называется ортогональная квадратная матрица размерности и Х и, элементами которой являются действительные числа +1 и — 1.
Ортогональной называется матрица, строки которой являются взаимно ортогональными векторами (в данном случае над полем действительных чисел). Теорема бй. Если существует матрица Адамара размерности а ~~ и, то существует двоичный яод из и символов, образованный 2п векторами, с минима ьным расстоянием, равным п/2. (Это не обязательно линейнььй код.) Доказательство. Пусть Н вЂ” матрица Адамара. Код строится следующим образом. Берется совокупность из 2п векторов ть тв... ..., ъ„, — т ь — т„..., — т, где ъь ть ..., т„— строки матрицы Н. Затем в каждом из векторов все +1 заменяются на О, а — 1— на 1. Тогда получается совокупность 2п двоичных векторов длины и.
Поскольку соответствующие компоненты векторов ч; и — т, различны, то расстояние между векторами т, и — т~ равно и. Поскольку векторы 3-ч, и ~т; ортогоиальны, если 1~'1, то они должны совпадать в половине компонент и отличаться друг от друга в остальных компонентах, так что соответствующие двоич. ные векторы находится на расстоянии п/2. Ч. т. д. Теорема 5.2. Если Н вЂ” матрица Адамара размерности п Хп, то матрица является матрицей Адамара размерности 2п )( 2п. Доказательство. Очевидно, что матрица Н' является квадратной матрицей с элементами, равными +1 или — 1. Скалярное произведение 1-й и (и+1)-й строк 0 ~ ~п) равно (тт нт) ° (чп — нт) =чт ъ1+н1 ( — тт) — и п=О.
Для любых других комбинаций строк (тд и: ъ~с) ° (т1.~ т1) =в~ ' ит~тц тт= О ~ О = О. Следовательно, Н' — ортогональная матрица. Ч. т. д. Легко проверить, что матрица является матрицей Адамара и, следовательно, матрица 1 1 1 1 1 — 1 1 — 1 1 1 — 1 — 1 1 — 1 — 1 1 в соответствии с теоремой 5.2 также является матрицей Адамара. Многократно применяя теорему 5.2, можно построить матрицу Адамара Н размерности 2м;к'2~ для любого целого положительного т.
Соответствующий ей код совпадает с кодом Рида— Маллера первого порядка. Действительно, семь ненулевых кодовых слов из кода, полученного с помощью матрицы Н4, образуют в точности последние четыре столбца матрицы С, приведенной на :тр. 76, н, следовательно, код имеет модулярное представление (0,0,0,1, 1,1,1). Вообще модулярным представлением кода, полученного на основе матрицы Н, является вектор, содержащий 2 — ' — 1 нулей. за которыми следуют 2 -' единиц, если столбцы яатрицы М в соотношении (3.!7) упорядочены как двоичные числа.
Для других значений п двоичные коды, получаемые с помощью матрицы Адамара, не могут быть групповыми кодами, поскольку число их кодовых векторов не является степенью 2. Легко показать, что если а 2, то п должно быть кратно 4. Большое количество различных методов построения матриц Адамара приводится в книге Холла и Маршалла !1361, а также в недавних работах [113, 286, 3!8, 3191.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
