Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
о
1
1
Uz-%-
U3-CCg-
ай~ а0-as~ а7-
CC^i-
щ-
Ugr
Рис. 25.
строки матрицы H дают следующие проверки для первого символа Gc0-'
«0 = «!+»!!+««, ао=аз+ав+аі2> а0=а6+а7+а16, а0=а4+а8+а18.
Ортогональность этих соотношений, как можно убедиться, как раз и объясняется свойством ортогональности исходных матриц. При этом число таких соотношений для каждого символа всегда равно числу матриц, используемых для построения, т.е. /'+2. А значит, кодовое расстояние не может быть меньше, чем г+3; в нашем примере оно не меньше пяти.
,106 На рис. 25 мы приводим часть декодирующей схемы, предназначенную для декодирования символа ал (буквой М, как и раньше, обозначен мажоритарный элемент).
20. МАТРИЦЫ АДАМАРА И КОДИРОВАНИЕ
Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века *). Сравнительно недавно (в 1960 г.) было замечено, что эти матрицы могут быть использованы для построения кодов
с большим кодовым расстоянием ^ J^] ) '
Квадратная матрица H порядка п с элементами ±1 называется матрицей Адамара, если выполняется условие
HW = nEn. Вот несколько примеров матриц Адамара:
(I J).
п=1 л=2
л = 8
Рассмотрим произвольную матрицу Адамара
H =
'hu ftla . ., hin'
H21 Л22 • hin . hU = ± 1
Ki hn2 • Kni
Из определения следует, что для любой пары строк с номерами і и / (й?/) верно равенство:
Л/ift/i + А/Л-2 + • • • + hiJh-n=
О)
*) Жак Адамар (1865—1963) — один из крупнейших французских математиков конца XIX и первой половины XX века, автор ряда основополагающих работ в области теории чисел, алгебры и математического анализа.
,07 Таким образом, различные строки матрицы Адамара попарно ортогональны. Далее, число слагаемых в (1), равных + 1, должно совпадать с числом слагаемых, равных —1. Следовательно, п четно и любые две строки совпадают ровно в и/2 позициях и различаются в остальных.
Пусть теперь А — двоичная матрица, получающаяся из матрицы H заменой элемента +1 на 0 —1 на 1. Множество векторов-строк матрицы А образует тогда код с расстоянием Хемминга между любыми кодовыми словами, равным п!2. Так, из матрицы Адамара порядка 8 получаем матрицу А, задающую код длины 8 с кодовым расстоянием 4:
Не меняя кодового расстояния, можно уменьшить длину кода, если отбросить первый (нулевой) символ каждого слова.
Указанным образом из всякой матрицы Адамара порядка п можно получить двоичный код Адамара типа (п—І, п, я/2) (п—1 —длина кодового слова, п — число слов кода, п/2 — кодовое расстояние). Это, как правило, код, не являющийся линейным.
С матрицей А связаны еще два кода, которые тоже называют кодами Адамара.
Первый из_них получается так. Перейдем от матрицы А к матрице А, заменив все элементы матрицы А их дополнениями (т. е. заменив единицы нулями, а нули — единицами). Тогда строки матриц А и А в совокупности образуют код типа (п, 2п, /г/2), что легко проверяется с помощью равенства (1).
Другой код Адамара получается из предыдущего отбрасыванием первого символа в каждом кодовом слове.
Например, из матрицы (2) можно получить таким способом коды Адамара типов (8,16, 4) и (7, 16, 3).
Коды Адамара, как видно из их определения, обладают интересной особенностью: расстояние между любыми двумя кодовыми словами одинаково и совпадает поэтому с кодо-
A =
/0 0 0 0 0 0 0 0'
0 10 10 10 1
0 0 1 1 0 0 1 1
0 110 0 110
0 0 0 0 1 1 1 1
0 10 110 10
0 0 1 1 0 0 1 1
0 110 10 0 1,
(2)
Это будет код типа
,108 вым расстоянием. Подобные коды называют эквидистантными, и в некоторых случаях их использование дает особые преимущества.
Коды Адамара, обладая большим кодовым расстоянием, позволяют соответственно исправить и большое количество ошибок (первые два из них исправляют ошибки примерно в четверти позиций кодового слова). Достигается это, конечно, ценой высокой избыточности.
Для построения и реализации кода Адамара той или иной длины необходимо построить сначала матрицу Адамара соответствующего порядка. Надо сказать, что такое построение является совсем нелегким делом, и этому вопросу посвящен внушительный раздел современной комбинаторики. Некоторые методы построения будут рассмотрены ниже в разделе «Задачи и дополнения» (см. также [4]).
С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок п матрицы Адамара при гС^3 может быть лишь четным. Более того, нетрудно доказать, что при п^4 порядок обязан делиться на 4 (см. дополнение 3). До настоящего времени остается открытым вопрос: для любого ли п, кратного 4, существует матрица Адамара порядка п? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).
Задачи и дополнения
1. Укажем наиболее простой способ построения матриц Адамара сколь угодно больших порядков. Пусть Hn- матрица Адамара порядка п и —Hn — матрица с противоположными элементами. Составим из них матрицу порядка 2п следующим образом:
