УДК 519.6

 

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

(prudnikov.doc)

 

 

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

 

 

 

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

 

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

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

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

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

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

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

                        xL=y,                                                      (1)

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

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

                             Py=0.                                                    (2)

          Способы задания кодов (1) и (2) эквивалентны друг другу, так как система уравнений (2) определяет в Ln подпространство Lm Ì Ln размерности m. Базис этого подпространства обозначим через b1,b2,…bm. Любой вектор yÎ Lm удовлетворяет (2), а, следовательно, является кодовым словом. Вектор y можно записать в виде

y=y1 b1+y2 b2+…+ym bm,

где yi, i Î1:m, - координаты вектора y=(y1,y2,…,ym) в базисе b1,b2,…bm. Строки матрицы L[m ´n]  составлены из координат векторов b1,b2,…bm. Матрицы L и P связаны соотношением

LPt=0,

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

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

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

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

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

или существуют h1 ,h2 ÎH, что a•h1 =b•h2 для левых классов и h1•a= =h2•b для правых классов. Отсюда имеем

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

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

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

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

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

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

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

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

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

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

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

          Для обеспечения кодирования достаточного количества символов необходимо, чтобы длина кодовых слов n была значительно больше по сравнению с s, т.е. n>>s, так как количество кодовых слов с s и меньшим числом ошибок равно

C1n+C2n+…+Csn.

Поэтому, если s большое, то n должно быть значительно больше s, так как общее число кодовых слов длины n равно

                             C0n +C1n+C2n+…+Cs n+ Cs+1n+…+ C n n=2n.

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

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

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

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

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

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

…

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

 

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

          Для того чтобы в двоичном представлении числа отличались на не меньше, чем на 3 символа, достаточно сделать следующее. Надо рассмотреть числа, двоичное представление которых следующее

24t(23+22+21+20)+остаток от деления на 16,

где t=0,1,2,… Изменяя t и остаток от деления на 16, можно в каждом классе найти числа, отличающиеся друг от друга в двоичном представлении на 4 символа. Взяв эти числа в каждом классе в качестве кодовых слов, мы тем самым решаем задачу об исправлении любых одиночных символов. Аналогичные действия надо сделать для исправления любого количества символов.

          В качестве символов-разделителей между кодовыми словами можно использовать элементы некоторого класса. Можно, например, в качестве такого класса взять группу Н. Тогда, как это было сказано ранее, сдвиг двоичного кода влево на (p-1) символов равносильно умножению десятичного кода на степень двойки 2p-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с.

 

 

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.               

pim_10@hotmail.com

Смоленск

Поступила в редакцию 30.11.2006.