Новая теория кодирования. Что такое теория кодирования?
жүктеу/скачать 289.49 Kb.
|
|
Новая теория кодирования. Что такое теория кодирования? «Кодирование» - одно из наиболее распространенных понятий в современной информатике. Что же такое «кодирование»? Под «кодированием» понимается операция отождествления символов или групп символов одного кода с символами или группами символов другого кода. Необходимость кодирования возникает прежде всего из потребности приспособить форму сообщения к данному «каналу связи» или какому-либо устройству, предназначенному для преобразования или хранения информации. «Теория кодирования» имеет длительную историю. Системы счисления, о которых я рассказывал раньше, и были первыми кодами, предназначенными для представления чисел. Следующее древнее направление в теории кодирования – это криптография или секретное кодирование. Криптография берет свое начало в Египетской науке и ее возникновение относится к тому периоду (2-е тысячелетие до н.э.), когда Египтяне использовали иероглифический код для надписей на могилах. Развитие современной теории кодирования стимулировалось прогрессом систем связи. В середине 20-го столетия американский ученый Клод Шеннон разработал теорию эффективных кодов, основанных на понятии энтропии. Эта теория нашла широкое применение в современных компьютерах для сжатия информации. Потребность защитить информацию и системы связи от вредного влияния шумов и помех, разрушающих информацию, способствовали развитию теории избыточных кодов. Код Хемминга, циклические коды – это хорошо известные специалистам примеры избыточных кодов. Таким образом, современная теория кодирования – это совокупность, по крайней мере, четырех различных направлений: ( 1) Теория систем счисления; ( 2) Теория криптографии; ( 3) Теория эффективных кодов; ( 4) Теория избыточных кодов. Для решения задач кодирования широко используется различный математический аппарат. Например, в теории алгебраических кодов широко используется аппарат теории групп, в современной криптографии основным математическим аппаратом является теория чисел. Как я пришел к новой теории кодирования? С сентября 1998 года я начал работать на кафедре математики информатики Университета Эдуардо Мондлане (Мапуту, Мозамбик). Очень важным достоинством кафедры было наличие в ней прекрасной библиотеки, в которой была собран хорошая коллекция книг по математике и информатике. Библиотека стала одним из мест моего частого времяпровождения в период работы в этом знаменитом африканском университете. И там меня однажды сфотографировали для кафедрального сайта. 300 Фото в библиотеке кафедры математики и информатики Университета Эдуардо Мондлане (Мапуту, Мозамбик, 1999 г.) Однажды мне попалась на глаза книга “Computer security management” (автор Dennis van Tassel), опубликованная издательством “Prentice-Hall”, New Jersey, 1972. В этой книге я обнаружил описание так называемого «матричного» метода кодирования информации. Суть кодирования состояла в представлении исходного сообщения в виде квадратной матрицы с последующим умножении такой матрицы на специальную кодирующую матрицу того же порядка. Декодирование состояло в умножении «кодовой матрицы» на «инверсную» матрицу. Прочитав описанный метод, у меня мгновенно созрела идея использования разработанных мною Qp-матриц для кодирования информации. Суть метода кодирования состоит в представлении исходного сообщения в виде квадратной матрицы М и последующем ее умножением на кодирующую матрицу, в качестве которой выбирается матрица типа n Qp . Ясно, что размер исходной матрицы М должен быть таким же, как и размер кодирующей матрицы n Qp . В результате такой операции образуется «кодовая матрица» Е, элементы которой направляются в «канал связи». Декодирование состоит в умножении кодовой матрицы Е на матрицу n Qp − , инверсную к матрице n Qp , то есть, такую, что n Qp × n Qp − = I. Таблица ниже демонстрирует общую идею «фибоначчиевого» алгоритма кодирования-декодирования. Кодирование Декодирование M× n Qp = E E× n Qp − = M А теперь установим некоторые свойства сформулированного выше метода «фибоначчиевого» кодирования-декодирования, основанного на применении Qp-матриц. Прежде всего установим, как связаны между собой детерминанты исходной матрицы М и кодовой матрицы Е. Поскольку кодовая матрица Е вычисляется на путем умножения исходной матрицы М на кодирующую матрицу n Qp , то есть, Е = M× n Qp , (1) то детерминант матрицы (1) может быть вычислен следующим образом: Det E = (Det M)×(Det n Qp ). (2) Но выше мы установили, что Det n Qp = (-1)pn . (3) Подставляя выражение (3) в (4), мы получим очень важное соотношение, связывающее детерминанты матриц Е и М: 301 Det E = (Det M)×(-1)pn . (4) Обнаружение ошибок Как упоминалось, одна из целей теории «избыточного кодирования» состоит в обнаружении и коррекции ошибок, возникающих в кодовом сообщении E под влиянием «помех» в «канале». Покажем сейчас, как обнаруживать ошибки в кодовом сообщении Е, используя «фибоначчиевое» кодирование. Главная идея состоит в использовании свойства (4), связывающего детерминанты исходной матрицы М и кодовой матрицы Е. Для того, чтобы обнаруживать ошибки в элементах кодовой матрицы Е, достаточно передать по «каналу связи» значение детерминанта исходного сообщения М. И тогда, получив элементы кодовой матрицы Е, мы можем проверить выполнение фундаментального соотношения (4), связывающего детерминанты матриц М и Е. Нарушение равенства (4) и является признаком ошибки в элементах матрицы Е. Исправление ошибок Но обнаружить ошибку в сообщении – это только первый шаг в повышении достоверности передаваемого сообщения. Надо теперь эту ошибку исправить. И оказалось, что рассмотренное выше фундаментальное свойство (4) позволяет не только обнаруживать, но и исправлять ошибки в элементах кодовой матрицы Е. Продемонстрируем эту возможность на простейшем примере, когда мы используем для кодирования простейшую «фибоначчиевую» Q-матрицу. Для этого случая исходное сообщение может быть представлено в виде квадратной матрицы 2-го порядка: = 3 4 1 2 m m m m M . (5) Детерминант такой матрицы равен: Det M = m1m4 - m2m3. (6) Пусть в качестве кодирующей выбрана «фибоначчинвая» матрица = 5 3 8 5 5 Q . Тогда в соответствии с правилами матричного умножения кодовая матрица E принимает следующий вид: E= = + + + + = × × = ' 4 ' 3 ' 2 ' 1 4 3 3 5 4 5 3 8 2 3 1 5 2 5 1 8 5 3 8 5 3 4 5 1 2 m m m m m m m m m m m m m m m m M Q . (7) В «канал связи» посылаются элементы кодовой матрицы (7) и вслед за ними детерминант исходной матрицы, вычисленный по формуле (6). Предположим, что в процессе передачи произошло искажение первого элемента кодового сообщения ' 1 m , то есть ' 1 m =x. Тогда мы можем представить «разрушенное» кодовое сообщение в следующем виде: = ' 4 ' 3 ' ' 2 m m x m E (8) где x есть «разрушенный» элемент кодового сообщения E, а остальные элементы матрицы должны быть корректными и равными следующим значениям: 4 3 3 5 ' 4 ; 4 5 3 8 ' 3 ; 2 3 1 5 ' 2 m m m m m m m m m = + = + = + (9) 302 Тогда согласно свойствам «фибоначчиевого» кодирования для случая кодирующей матрицы Q 5 детерминант матрицы М' должен быть равным детерминанту (6), взятым с противоположным знаком. Тогда мы можем записать следующее уравнение для вычисления «разрушенного» элемента x: ) 4 5 3 )(8 2 3 1 ) 5( 4 3 3 5( ' 3 ' 2 ' 4 xm − m m = x m + m − m + m m + m = - m1m4 + m2m3 (10) И после выполнения элементарных математических преобразований над уравнением (10) мы можем получить решение уравнения (10) в виде: x = 8m1 + 5m2 (11) Сравнивая вычисленное значение (11) с элементом ' 1 m кодовой матрицы E, задаваемой (7), мы можем сделать следующее важное заключение: x = ' m1 . Таким образом, мы восстановили кодовое сообщение E, используя свойства детерминанта «фибоначчиевой» матрицы Q! Я не буду утомлять моего читателя дополнительными довольно сложными рассуждениями и отсылаю наиболее любопытных к моей книге «Introduction into Fibonacci Coding and Cryptography”, опубликованной в 1999 г. «Фибоначчиевая» криптография В упомянутой выше книге изложена идея применения рассмотренного выше «фибоначчиевого» метода кодирования-декодирования для криптографической шифрации- дешифрации информации. Что такое «криптографическое кодирование»? Это – очень важное направление современной информатики. С помощью «криптографического кодирования» мы осуществляем преобразование исходного сообщения М в некоторое зашифрованное сообщение Е; при этом его дешифрация может быть осуществлена только пользователем, знающим «криптографический ключ». Рассмотрим теперь «фибоначчиевое» кодирование-декодирование, основанное на применении «фибоначчиевой» матрицы n Qp . В данном случае числа р и n, задающие матрицу n Qp , могут принимать значение из множеств {p=0, 1, 2, 3, …}и {n = 1, 2, 3, …}. Это означает, что теоретически существует бесконечное количество способов «фибоначчиевого» кодирования-декодирования. И это обстоятельство мы можем использовать для «криптографического кодирования». Действительно, каждый пользователь Internet может получить в свое распоряжение только свои, известные только ему «ключевые» числа p и n и тогда его общение через Intenet с другими пользователями может осуществляться с помощью «фибоначчинвого» кодирования, основанного на «своей» матрице типа n Qp . С помощью такого метода можно легко зашифровать некоторую важную информацию в собственном компьютере или некоторой «базе данных». То есть, можно найти много различных приложений предложенного метода, если только захотеть. При этом не надо забывать, что наш «криптографический метод» позволяет еще и обнаруживать и исправлять ошибки в засекреченном сообщении! И сейчас мы подведем итог нашему рассмотрению нового метода кодирования, основанного на «фибоначчиевых» матрицах типа n Qp . Во-первых, мы рассмотрели весьма необычный метод избыточного кодирования и «криптографической шифрации» информации! В нашем методе объектами обнаружения и исправления ошибок являются элементы матрицы E! Мы корректируем не отдельные биты или их комбинации в двоичных кодах, как это принято в классической теории кодирования, а числа, являющиеся элементами матриц. И наконец, мы используем необычный математический аппарат для нашей теории кодирования, а именно теорию матриц и теорию р-чисел Фибоначчи. Министерство образования и науки Республики Казахстан Южно-Казахстанский Государственный Университет им М.Ауезова Выполнила: студентка гр.Ип-15-3р Жумадуллаева К.Ж. Приняла: Бердалиева Г.А. Шымкент 2017 жүктеу/скачать 289.49 Kb. Достарыңызбен бөлісу:
|