Коды Адамара и Гоппы

«Коды Адамара и Гоппы» 1. Код Гоппы Валерий Денисович Гоппа первый в 1981году осознал связь между алгебраической геометрией и теорией кодирования. В математике и информатике двоичный код Гоппы — код коррекции ошибок, который принадлежит к классу общих кодов Гоппы. Первоначально был описан Валерием Денисовичем Гоппа. В сравнении с недвоичными вариантами, бинарная структура дает ему несколько математических преимуществ, а также лучше подходит для общего использования в компьютерах и телекоммуникациях. Двоичные коды Гоппы обладают интересными свойствами, полезными для криптографии в криптосистемах, подобных McElise и аналогичных. 1.1 Строение и свойства Двоичный код Гоппы определяется как полином g(x) в степени t над конечным полем GF(2^{m}) без конечного числа нулей, и последовательность L из n различных элементов GF(2^{m}) которые не являются корнями или полиномами. • Код определен, как пара (g,L) с минимальной длиной 2t+1, таким образом, он может исправить • ошибок в слове длиной n-mt используя ключи размером n. Он также обладает удобной матрицей контроля четности H в виде: Обратите внимание, что эта форма матрицы контроля четности состоит из определителя Вандермонда V и диагональной матрицы D, имеет форму, схожую с проверочными матрицами альтернативных кодов, таким образом, в этой форме могут использоваться альтернативные декодеры. Такие декодеры обычно обеспечивают только ограниченную возможность исправления ошибок (чаще всего t/2). Для практических целей, матрица проверки на четность двоичного кода Гоппы обычно преобразуется к более в более удобную для использования компьютером двоичную форму с помощью конструкции трассировки, которая преобразует t-на-n матрицу над GF(2^{m}) в двоичную матрицу mt-на-n разделив полиномиальные коэффициенты GF(2^{m}) на m последовательных рядов. 1.2 Декодирование Обычно, декодирование двоичного кода Гоппы производится алгоритмом Паттерсона, который способен эффективно исправлять ошибки(он исправляет все t обнаруженные ошибки), и который так же достаточно прост в реализации. Алгоритм Паттерсона преобразует синдром в вектор ошибок. Предполагается, что синдром двоичного слова с = (с{0}….с{n-1}), примет вид: Альтернативная форма матрицы контроля четности основана на формуле s(x), и может быть использована для создания такого синдрома с простым произведением матриц. Далее алгоритм производит расчет Это не удается, когда s(x)=0 ,но это тот случай, когда входное слово является ключом, поэтому исправление ошибок не требуется. Используя расширенный алгоритм Евклида v(x)сводится к полиномам Наконец, полином определяющий расположение ошибок, вычисляется как Обратите внимание, что в двоичном случае для исправления ошибок достаточно их найти, так как существует только одно отличное значение. Если исходный ключ был декодирован и двоичный вектор ошибок, то Разложение на множители или оценка всех корней Дает достаточную информацию, чтобы восстановить вектор ошибок и И исправить их. 1.3 Свойства и использование Двоичные коды Гоппы, рассматриваемые как особый случай кодов Гоппы, обладают интересным свойством — они исправляют все deg(g) ошибок, в то время как троичные и прочие коды исправляют только deg(g)/2. Асимптотически такая способность к исправлению ошибок соответствует известной границе Гильберта — Варшамова. Благодаря высокой способности исправления ошибок, с учетом высокой скорости кодирования и сложной формы матрицы проверки на четность (которую обычно трудно отличить от случайной двоичной матрицы того же ранга) двоичные коды Гоппы используются в нескольких постквантовых криптосистемах, в частности, в криптосистеме McEliece и криптосистеме Нидеррейтера. 1.4 Пример построение кода 2 Код Адамара Код Адамара является кодом коррекции ошибок имени Жака Адамар, который используется для обнаружения и исправления ошибок при передаче сообщений по очень шумным или ненадежным каналам. В 1971 году код был использован для передачи фотографий Марса на Землю из NASA космического зонда. Из - за своих уникальных математических свойств, код Адамара используется не только инженерами, но и интенсивно изучается в теории кодирования, математики и теоретической информатики. Код Адамара назван в честь французского математика Жака Адамара. Он также известен под названиями кода Уолша, семьи Уолша и Уолша-Адамара кода в знак признания американский математик Жозеф Леонард Уолш. Код Адамара является примером линейного кода над двоичным алфавитом, который отображает сообщения длиной до кодовых слов длины. Он уникален тем, что каждое ненулевой кодовое слово имеет Хэмминг вес в точности, что подразумевает, что расстояние коды также. В стандартной теории кодирования обозначений для блочных кодов, код Адамара является -код, то есть, это линейный код над двоичным алфавитом, имеет длину блока, длину сообщения (или измерение), а минимальное расстояние. Длина блока очень велико по сравнению с длиной сообщения, но с другой стороны, ошибки могут быть исправлены даже в очень шумных условиях. Проколотый код Адамара представляет собой слегка улучшенный вариант кода Адамара; это -кода, и, таким образом, имеет несколько лучшую скорость, сохраняя при этом относительное расстояние, и, таким образом, предпочтительным в практических применениях. Проколотый код Адамара такое же, как в первом порядке Рида-Мюллера кода над двоичным алфавитом. Как правило, коды Адамара основаны на конструкции Сильвестра матриц Адамара, но термин «код Адамара» также используется для обозначения кодов, построенных из произвольных матриц Адамара, которые не обязательно типа Сильвестра. В общем, такой код не является линейным. Такие коды были впервые построены RC Bose и SS Шрикханде в 1959 г. Если п является размер матрицы Адамара, код имеет параметры, то есть он является не-обязательно-линейный двоичный код с 2 п кодовых слов длины блока п и минимальное расстояние п / 2. Строительство и декодирование схема, описанная ниже, применимы для общего п, но свойство линейности и идентификации с кодами Рида-Мюллера требуют, чтобы п быть степенью 2, и что матрица Адамара будет эквивалентна матрице, построенной по методу Сильвестра. Код Адамара является локально декодируемым кодом, который дает возможность восстановить часть исходного сообщения с высокой вероятностью, в то время как только глядя на небольшую часть полученного слова. Это приводит к приложениям в теории сложности вычислений и особенно в конструкции вероятностно отмечаемых доказательств. Так как относительное расстояние кода Адамара равна 1/2, как правило, можно только надеяться, чтобы восстановить из не более чем 1/4 часть ошибки. Использование декодирования списка, однако, можно вычислить короткий список возможных сообщений кандидатов, пока меньше битов в принятом слове были повреждены В кодовом разделении множественного доступа (CDMA) связи, код Адамар упоминаются как кода Уолша, и используются для определения отдельных коммуникационных каналов. Это обычно в литературе CDMA для обозначения кодовых слов, как «коды». Каждый пользователь будет использовать другое кодовое слово, или «код», чтобы модулировать их сигнал. Поскольку кодовые слова Уолша математически ортогональные, Уолш-кодированный сигнал появляется как случайный шум к CDMA, способному мобильному терминалу, если терминал, который не использует то же кодовое слово в качестве той, которая используется для кодирования входящего сигнала. 2.1 История Код Адамара - имя, которое наиболее часто используется для этого кода в литературе. Однако, в современном использовании этих кодов коррекции ошибок называются кодами Уолша-Адамара. Для этого есть причина: Жак Адамар не изобретал сам код, но он определил матрицы Адамара около 1893 г., задолго до первой коррекции ошибок кода, в коде Хэмминга, был разработан в 1940 - х годах. Код Адамара на основе матриц Адамара, в то время как существует множество различных матриц Адамара, которые могут быть использованы здесь, как правило, только строительство Сильвестра матриц Адамара используется для получения кодовых слов кода Адамара. Джеймс Джозеф Сильвестр разработал свою конструкцию матриц Адамара в 1867 году, что на самом деле предшествует работа Адамара на матрицах Адамара. Отсюда и название Адамара код оспаривается, а иногда код называется кодом Уолша, в честь американского математика Джозеф Леонард Уолш. Код Адамар был использован в течение 1971 Mariner 9 миссии для исправления ошибок передачи изображения. Слова данных, используемые во время этой миссии, были длинные 6 бит, которые представлены 64 оттенков серого значения. Из - за ограничения качества выравнивания передатчика в то время (из - за проблемы, доплеровский Loop слежения) максимальная длина полезной информации составляла около 30 бит. Вместо того чтобы использовать код с повторение, а был использован код Адамара. Ошибки до 7 бит в слове может быть исправлено с помощью этой схемы. По сравнению с 5 - кода повторения, исправления ошибок свойства этого Адамара кода гораздо лучше, но его скорость сравнима. Эффективный алгоритм декодирования является важным фактором в решении использовать этот код. Схема используется называлась «Green Machine». Он использовал быстрое преобразование Фурье, который может увеличить скорость декодирования по три раза. Поскольку использование 1990 - х годов этого кода с помощью космических программ более или менее прекратилось, и NASA Deep Space Network не поддерживает эту схему коррекции ошибок для своих блюд, которые больше, чем 26 м. 2.2 Использование матрицы Адамара - используются в рентгеновских телескопах с пространственным кодированием апертуры. - используются при кодировании информации (коды, исправляющие ошибки, ECC). 2.3 Пример 2.4 Свойства На множестве матриц Адамара размера {\displaystyle n\times n}n x n действует группа преобразований {\displaystyle G}G, порождённая инверсиями строк и столбцов (умножением на −1), а также перестановками строк и столбцов. Две матрицы Адамара {\displaystyle H_{1}} и  {\displaystyle H_{2}} называются эквивалентными, если существует элемент {\displaystyle g\in G}g€ G такой, что = g {\displaystyle H_{2}=gH_{1}}. Таким образом, все матрицы Адамара заданного размера разбиваются на классы эквивалентности. Теорема 1. Существует алгоритм перечисления нормализованных матриц Адамара. Теорема 2. Для порядков 1, 2, 4, 8, 12, 16, 20, 24 существует соответственно 1, 1, 1, 1, 2, 118, 6520, 43966313) эквивалентных классов нормализованных матриц Адамара по отношению эквивалентности перестановок строк и столбцов. Определение. Автотопией матрицы Адамара H называется элемент {\displaystyle g\in G} g€ G  такой, что g(H) = H {\displaystyle g(H)=H}. Теорема 3. Существует алгоритм вычисления группы автотопий матрицы Адамара. Теорема 4. Существует алгоритм проверки эквивалентности двух матриц Адамара, находящий нужный элемент g€ G {\displaystyle g\in G}. Теорема 5. Существуют полиномиально вычислимые функции на матрицах Адамара, инвариантные относительно действия группы {\displaystyle G}G, и позволяющие в определённых случаях различать неэквивалентные матрицы Адамара. Теорема 6. Существует алгоритм, перечисляющий только по одной матрице из каждого эквивалентного класса, для всех матриц заданного размера (в стадии разработки).