Метод кодирования смежными классами

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Метод кодирования смежными классами

Прудников И.М.

Изучается новый метод кодирования смежными классами по подгруппе произвольной группы, пригодный как для засекречивания информации, так и для ее передачи.

A method of coding with help of co-sets. Proudnikov I.M.

A method of coding with help of co-sets on subgroup of any group suitable for transmitting codes and classifying them as secret is studied.

Основными задачами кодирования являются

· кодирование с целью засекречивания информации, используемое в разведке,

· кодирование с целью передачи информации, используемое в коммуникационных сетях,

· кодирование с целью сжатия информации, используемое в криптографии.

Будем изучать первые две задачи.

При кодировании кодируемое слово (вектор) преобразуется по определенному правилу в кодовое слово. Наибольшее распространение получили линейные коды. Правило кодирования для линейных кодов очень простое. Надо умножить кодируемый вектор размерности [1m] на порождающую матрицу L[mn]:

xL=y, (1)

где x-кодируемое слово, y- кодовое слово. В результате получаем кодовое слово длины n. Множество кодовых слов при линейном кодировании образует линейное пространство L_n.

В каналах связи часто возникают сбои, в результате чего появляются ошибки при передаче информации. Истинный нуль принимается как ложная единица, а истинная единица - как ложный нуль. Важно уметь исправлять ошибки. При линейном кодировании для этих целей служит проверочная матрица P[r n] с k проверочными соотношениями вида

Py=0. (2)

Способы задания кодов (1) и (2) эквивалентны друг другу, так как система уравнений (2) определяет в L_n подпространство L_m L_n размерности m. Базис этого подпространства обозначим через b₁,b₂,…b_m. Любой вектор y L_m удовлетворяет (2), а, следовательно, является кодовым словом. Вектор y можно записать в виде

y=y₁ b₁+y₂ b₂+…+y_m b_m,

где y_i, i 1:m, - координаты вектора y=(y₁,y₂,…,y_m) в базисе b₁,b₂,…b_m. Строки матрицы L[m n] составлены из координат векторов b₁,b₂,…b_m. Матрицы L и P связаны соотношением

LP^t=0,

где t - знак транспонирования матрицы.

Линейные коды просты в реализации, но непригодны для засекречивания информации, так как сегодняшний уровень развития вычислительной техники позволяет легко сделать расшифровку такого метода кодирования. Интересно предложить метод кодирования, который был бы также прост в реализации и мог быть использован для засекречивания информации.

Рассмотрим теперь произвольные, не обязательно линейные коды. Обозначим множество кодируемых слов через W, а |W| - число таких слов. Пусть G - некоторая группа с групповой операцией *, которую условно будем называть умножением, и H- ее подгруппа. Известно, что левые (правые) смежные классы G/H определяют разбиение G на классы эквивалентности: два элемента a,bG принадлежат одному классу эквивалентности или одному левому (правому) смежному классу, если

a*H=b*H = {a*h | hH} = {b*h | hH} (левые классы),

H*a=H*b = {h*a | hH} = {h*b | hH} (правые классы),

или существуют h₁,h₂ H, что a*h₁ =b*h₂ для левых классов и h₁*a= =h₂*b для правых классов. Отсюда имеем

b^-1 *aH или a^-1 *b H (для левых классов),

a *b^-1H или b* a^-1H (для правых классов).

Левые (правые) классы смежности не пересекаются [2].

Пусть мы кодируем элементы множества W произвольными элементами левых смежных классов G/H, т.е. любому wW ставим в соответствие целый смежный класс. С одинаковым успехом можно кодировать правыми смежными классами. Далее для определенности будем кодировать левыми смежными классами.

Как производить декодирование? Для однозначного декодирования требуется по кодовому слову а однозначно определить смежный класс, которому принадлежит элемент а. Для этого образуем множество a*H={a*h | hH}. Если число смежных классов конечно, но не меньше |W|, то, перебрав все левые смежные классы и сравнив их с множеством a*H, можно однозначно определить смежный класс, которому принадлежит кодовое слово а, а значит и однозначно произвести декодирование, т.е. определить тот элемент w W, которому класс a*H соответствует.

Отметим, что если Н ? нормальная подгруппа, то множества правых и левых смежных классов совпадают и образуют группу G=G/H с групповой операцией *, определенной в G. Единицей в G служит сама подгруппа H: если АG/H - смежный класс, то A*H=H*A. Произведение любых двух смежных классов A,BG/H есть снова смежный класс, т.е. A*B=CG/H. Последнее дает дополнительные по сравнению со случаем, когда Н не является нормальной подгруппой, соотношения для проверки принадлежности кодового слова a классу А, например, следующее: a*B=CG/H.

Важной проблемой в теории кодирования является проблема исправления ошибки при передаче информации. В цифровых сетях информация передается в виде набора нулей и единиц. Нас будут интересовать способы исправления любых s ошибочных символов типа 01 или 10.

Пусть элементы группы G отожествляются с числами, т.е., иначе говоря, существует изоморфизм группы G в бесконечное неограниченное множество чисел MR. Причем каждому классу H₁G/H соответствует свое бесконечное неограниченное подмножество чисел M₁M. Если G есть бесконечная неограниченная числовая группа, то уже есть естественный изоморфизм между G и бесконечным множеством чисел, указанных выше. Естественно, что если Н конечная подгруппа, то поскольку все классы равномощны, то любой класс H_i состоит из бесконечного множества элементов. Легко привести примеры, когда группа G, подгруппа H и классы H_i состоят из бесконечного множества элементов.

При передаче информации происходит кодирование посредством элементов группы G, которые в свою очередь отожествляют с числами из M. Для исправления любых s и меньшего числа ошибок необходимо и достаточно, чтобы кодовое расстояние между кодовыми словами было больше 2s [1] (Кодовое расстояние между двумя кодами это число различных символов в их двоичном представлении). Для выполнения последнего необходимо, чтобы модуль разности между любыми числами из разных смежных классов в их десятичном представлении, используемых при кодировании, был не меньше

кодирование смежный класс

r=2^2s+2^2s-1+…+2+1. (3)

Для десятичных чисел это утверждение не достаточно. Например, для s=2 число r=31. Если к 1 добавить 31, то получим 32. Но 1 и 32 отличаются друг от друга в двух символах в их двоичном представлении, а не в пяти. Но, если умножить число r на степень двойки вида 2^t, что означает сдвиг двоичного представления числа r влево на t символов, то всегда среди бесконечного числа неограниченных чисел каждого класса можно найти такие числа-коды, которые отличаются друг от друга на число r, а в их двоичном представлении на 2s+1 и более символов. Тогда при преобразовании чисел из М в двоичные и передаче двоичных чисел, соответствующих кодовым словам, по сети, можно при декодировании с успехом исправлять любые s ошибочных символов.

Для обеспечения кодирования достаточного количества символов необходимо, чтобы длина кодовых слов n была значительно больше по сравнению с s, т.е. n>>s, так как количество кодовых слов с s и меньшим числом ошибок равно C¹_n+C²_n+…+C^s_n.

Поэтому, если s большое, то n должно быть значительно больше s, так как общее число кодовых слов длины n равно C⁰_n +C¹_n+C²_n+…+C^s _n+ C^s+1_n+…+ C ⁿ _n=2ⁿ.

Нетрудно предложить алгоритм образования кодовых слов и сопоставления им смежных классов. Элементы из смежных классов для кодирования можно выбирать случайным образом. Если бесконечное число элементов смежных классов, то процесс раскодирования, не зная группу G и подгруппу H, весьма проблематичен. Последнее решает вопрос о засекречивании информации.

Важной проблемой является также проблема распознавания кодовых слов во множестве символов. Эту задачу можно решить путем введения некоторых специальных символов-разъединителей между кодовыми словами. Лучше всего это сделать, если элементы целого класса сделать в качестве таких символов-разделителей.

Пример. Рассмотрим множество целых чисел Z={0,1,2,…}. Разобьем Z на смежные классы. В один класс попадут числа, сравнимые по одному и тому же модулю, например, 16. Тогда H множество всех чисел, кратных 16. Каждый из смежных классов состоит из бесконечного числа чисел, дающих одинаковый остаток при делении на 16. Так

H₀ = {0, 16, …} числа, дающие при делении на 16 остаток 0,

H₁ = {1, 17, …} числа, дающие при делении на 16 остаток 1,

H₂ = {2, 18, …} числа, дающие при делении на 16 остаток 2,

…

H₁₅ = {15, 31, …} числа, дающие при делении на 16 остаток 15.

Максимальное число кодовых слов, кодируемых с помощью 16 классов, равно 16, а, следовательно, максимальная длина кодовых слов равна 4, так как 2⁴=16. Для исправления любых одиночных символов (s=1) необходимо, чтобы кодовое расстояние между кодовыми словами было не меньше 3=2*1+1. Для десятичного представления чисел последнее означает, что модуль разности двух кодовых слов их разных классов не меньше r=2²+2¹+2⁰=7. Элементы из смежных классов можно выбирать случайным образом, но так, чтобы их модуль разности был не меньше 7.

Для того чтобы в двоичном представлении числа отличались на не меньше, чем на 3 символа, достаточно сделать следующее. Надо рассмотреть числа, двоичное представление которых следующее 2^4t(2³+2²+2¹+2⁰)+остаток от деления на 16, t=0,1,2,… Изменяя t и остаток от деления на 16, можно в каждом классе найти числа, отличающиеся друг от друга в двоичном представлении на 4 символа. Взяв эти числа в каждом классе в качестве кодовых слов, мы тем самым решаем задачу об исправлении любых одиночных символов. Аналогичные действия надо сделать для исправления любого количества символов.

В качестве символов-разделителей между кодовыми словами можно использовать элементы некоторого класса. Можно, например, в качестве такого класса взять группу Н. Тогда, как это было сказано ранее, сдвиг двоичного кода влево на (p-1) символов равносильно умножению десятичного кода на степень двойки 2^p-1. Согласно малой теореме Ферма

a ^p-1-1? mod(p),

если p простое число и наибольший общий делитель (НОД) а и р равен 1. У нас а=2, а р произвольное простое число, большее двух. Тогда

2^р-1-1: р или 2^р-1 ? 1(mod p).

Последнее означает, что сдвиг двоичного кода влево на р-1 символов равносильно умножению действительного числа на 2^р-1, что не меняет его остаток от деления на р и не меняет класс эквивалентности. Прибавление к сдвинутому на р-1 позиций влево двоичному коду любого элемента из группы Н, элементы которой есть числа, кратные р, также не меняет класс эквивалентности. Таким образом, произвольные элементы группы Н можно рассматривать, во-первых, как символы-разделители между различными кодовыми словами, и, во-вторых, как информационные символы кода, с увеличенной длиной за счет этих символов.

Заметим, что предложенное кодирование можно рассматривать как кодирование с нефиксированной длиной кодового слова.

Литература

1. Питерсон У.,Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.

2. Аршинов М.Н., Садовский Л.Е. Коды и математика. М.: Наука, 1983, 144с.

Размещено на Allbest.ru