Математические способы кодирования информации

Кодирование для чайников, ч.1

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

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

0. Начало

Поскольку я обращаюсь к новичкам в этом вопросе, то не посчитаю зазорным обратиться к Википедии. А там, для обозначения кодирования информации, у нас есть такое определение — процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки.

Чего мне не хватало в 70-80-е, так это в школе, пусть не на информатике, а, например, на уроках математики — базовой информации по кодированию. Дело в том, что кодированием информации каждый из нас занимается ежесекундно, постоянно и в целом — не концентрируясь на самом кодировании. То есть в быту мы это делаем постоянно. Так как это происходит?

Мимика, жесты, речь, сигналы разного уровня — табличка с надписью, знак на дороге, светофоры, и для современного мира — штрих- и бар-коды, URL, хэш-тэги.

Давайте рассмотрим некоторые более подробно.

1.1 Речь, мимика, жесты

Удивительно, но всё это — коды. С помощью них мы передаём информацию о своих действиях, ощущениях, эмоциях. Самое важное, чтобы коды были понятны всем. Например, родившись в густых лесах у Амазонки и не видя современного городского человека, можно столкнуться с проблемой непонимания кода — улыбка, как демонстрация зубов, будет воспринята как угроза, а не как выражение радости.

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

Но мы всё еще будем ограничены дальностью остроты нашего зрения, и тогда — человек начинает придумывать другие способы передачи и преобразования информации, например огонь или дым.

1.2 Чередующиеся сигналы

В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы «включено/выключено». Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.

Наряду с сигнальными флажками на морских и речных судах, при появлении радио начали использовать код Морзе. И при всей кажущейся бинарности (представление кода двумя значениями), так как используются сигналы точка и тире, на самом деле это тернаный код, так как для разделения отдельных кодов-символов требуется пауза в передаче кода. То есть код Морзе кроме «точка-тире», что нам даёт букву «A» может звучать и так — «точка-пауза-тире» и тогда это уже две буквы «ET».

1.3 Контекст

Когда мы пользуемся компьютером, мы понимаем, что информация бывает разной — звук, видео, текст. Но в чем основные различия? И до того, как начать информацию кодировать, чтобы, например, передавать её по каналам связи, нужно понять, что из себя представляет информация в каждом конкретном случае, то есть обратить внимание на содержание. Звук — череда дискретных значений о звуковом сигнале, видео — череда кадров изображений, текст — череда символов текста. Если мы не будем учитывать контекст, а, например, будем использовать азбуку Морзе для передачи всех трёх видов информации, то если для текста такой способ может оказаться приемлемым, то для звука и видео время, затраченное на передачу например 1 секунды информации, может оказаться слишком долгим — час или даже пара недель.

2. Кодирование текста

От общего описания кодирования перейдём к практической части. Из условностей мы за константу примем то, что будем кодировать данные для персонального компьютера, где за единицу информации приняты — бит и байт. Бит, как атом информации, а байт — как условный блок размером в 8 бит.

Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт (в значении ноль) равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.

Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.

Тестовая фраза «ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП».

2.1 Блочное кодирование

Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа:

Источник

Математические основы кодирования и шифрования

Информационное взаимодействие абонентов в компьютерных и связных сетях подвергается возмущениям, которые приводят к возникновению ошибок и возмущений разного рода. Помимо возникновения ошибок в передаваемых сообщениях возможен несанкционированный доступ к содержанию сообщений нарушителя. Борьба с этими нежелательными явлениями ведется тысячелетиями, но с переменным успехом. Создатели Интернета задумывали его совсем не таким, каким он стал сейчас. О хакерах тогда и не думали.

Основные теоретические проблемы информационного противостояния, задачи по их решению возлагаются на теории кодологии, криптологии и стеганологии, в которых во всем мире интенсивно развиваются направления кодоанализа, криптоанализа и стегоанализа. Практические аспекты также не остаются в стороне, но замечу, что в РФ активность не очень-то высока, сказывается инертность молодых (сам я разменял уже 9-й десяток, но администрация Хабра ограничила возрастной ценз 1950 г). Мое мнение, конечно, ограничено наблюдением потомства (вплоть до правнуков) и общением в интернете, а также с обучаемыми и сотрудниками фирмы, где подрабатываю. СМИ тоже добавляют негатива. Кто из молодежи чуть поумнел, уходят за бугор. Поведение остальных видите сами.

Экскурс по публикациям

Разработка (синтез) технических устройств требует от разработчика определенных знаний, умений ими пользоваться и других навыков подобного рода. Существенная составляющая таких знаний — математическая. Это, как правило, алгебра, дискретная математика, геометрия, физика, математическая логика и др. Здесь в статье будем рассматривать алгебраические структуры не совсем в классическом изложении, но с достаточными уровнем строгости и точностью. Главной моей задачей является обеспечение доступности и понятности изложения вещей, которые я использую в своих текстах и изысканиях.

Например, здесь используется поле расширения GF (2 8 ) и, если обойтись без него, ничего стоящего изложить не удается. Мои критерии оценки просты. Каждый семестр 2, а то и 3 экзамена и зачеты в разных учебных группах. Там слышу и вижу, что я излагал, выносил на практику, и что мне возвращают в ответах по экзаменационным билетам. Очень полезен анализ экзаменационных ответов, вижу, что следовало бы излагать кое-что по-другому, лучше.

А здесь свойства Z_N конечного числового кольца вычетов по составному модулю N =pq используются для поиска решения задачи факторизации больших чисел в рамках нового оригинального подхода. Понятно, что в каждой из последующих публикаций переносить часть стандартных математических средств было бы неразумно, посему принято решение собрать все в одном месте и при необходимости адресовать сюда читателей.

Здесь же рассматривается и используется группа точек эллиптической кривой на плоскости. Операция суммирования в группе очень специального вида, вызывающая недоуменные вопросы, типа как это Вам удается складывать точки кривой, даже от членов ГЭК.

Группы

Предварительно введем ряд необходимых определений.

Определение. Конечное множество А-набор, совокупность любых n объектов , перечисляемых в любом порядке, но среди которых нет повторяющихся. Множества бывают структурированные, над элементами которых задана одна (или более) операция и отношений и неструктурированные, когда операции не заданы.

Ниже, как напоминание, приводится таблица действий (операций) с конечными дискретными множествами, а на диаграммах для наглядности показаны и непрерывные множества А и В.

Таблица операций с множествами

Определение. Операцией называется отображение А×А→А или, например, а·b=с; a,b,c ∊ A. Операции в алгебраических структурах другие нежели в арифметике, рассматриваются: унарные (например, обращение b -1 ), бинарные, тернарные, . n-арные (по числу мест для операндов), или умножение перестановок, модулярные (взятие результата по (mod R)) и др. Говорят, что элементы а и b перестановочны или коммутируют, если ab = ba.

Определение. Группа — это множество G элементов (любой природы), над которыми задана единственная операция, но она может быть сложением (+) и группа называется аддитивной, ее нейтральный элемент (0) или умножением (◦) — называется мультипликативной, ее нейтральный элемент (1), но как правило, операции эти не обычные арифметические, а специальные. Обозначается группа часто символом (G,◦), среди всех групп важное место отводится симметрическим группам перестановок степени n.

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

Группа G, удовлетворяющая коммутативному закону ba =ab для всех a,b ∊ G называется в честь математика Абеля (1802 -1829) абелевой.

Примером аддитивной группы является набор слов кода Хемминга (см.здесь). Операция в этой группе 16 порядка — суммирование слов по (mod2). С этой группой выполнялась операция разложения в смежные классы группы из 128 слов по подгруппе кода, а также строилась таблица Кели, элементы группы используются в кодере (базис пространства размерности 4) и декодере. Одним словом этот пример наглядно демонстрирует как может использоваться даже маленькая группа для решения очень важной практической задачи (связь).

Очень важными в теории групп являются симметрические группы подстановок (перестановок). Эта важность определяется теоремой, в которой говорится, что для любой группы, возникающей в произвольной предметной области, существует изоморфная ей симметрическая группа (подгруппа) на перестановках. Тогда исследователю новой открытой группы задача ее изучения упрощается. Почти все свойства изоморфной группы перестановок имеют место и в новой группе.

Начнем с простого примера. Заданы n элементов (обозначим их цифрами 1,2,3. n) и образуем из них перестановки, число которых n! = 1·2·3·. ·n. Ограничимся значением n=3, тогда 3! = 6.

Определение. Порядок группы — число элементов в группе называется ее порядком. В примере число 6 — это порядок группы.

В группе каждый элемент также имеет порядок, который является делителем порядка группы.
Определение. Порядок элемента группы — это наименьший показатель степени элемента в мультипликативной группе (кратности в аддитивной b+b+b+b+. b =nb = 0, порядок =n), при котором он обращается в нейтральный элемент, например () 3 =1, порядок ord() = 3.

В симметрической группе операцией является умножение перестановок. Это умножение аналогично матричному умножению, так как каждой перестановке степени n ставится в соответствие квадратная перестановочная матрица размерности n×n, в которой каждая строка и столбец содержат единственную единицу. Ниже это показано для симметрической группы.

Для удобства работы с группой и ее элементами математиком Кели предложена таблица операций группы (ограниченного размера). В клетке на пересечении строки и столбца ставится результат операции с элементами, которые их обозначают. Результат (как и обозначение строк/столбцов) в таблице представляется десятичными номерами элементов, что экономит место.

Таблица умножения элементов (перестановок) группы

Заполнение 36 клеток таблицы умножения упрощается, если воспользоваться свойствами таблицы Кели.
— Все строки и столбцы содержат элементы всей группы.
— Крайние столбцы лексикографически упорядочены и встречно направлены (1-й сверху/вниз — последний наоборот)
— На главной диагонали таблицы стоят квадраты элементов, если там стоит 1, то элемент ей соответствующий — инволюция; инволюциями в являются
— Относительно диагоналей матрицы выполняется симметрия положений элементов.
Свойства таблицы позволяют при ее заполнении ограничиться вычислениями только 13 пар элементов (выше они показаны).

Симметрическая группа

Группа имеет маленький порядок (6) и для иллюстрации свойств не очень удобна. Далее будут приводится примеры с симметрической группой 24 порядка. Все четные перестановки степени n образуют знакопеременную подгруппу в симметрической группе, обозначаемую символом А_n.

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

По таблице умножения находятся подгруппы в составе большой группы. Необходимо помнить, что порядок меньшей подгруппы должен делить порядок большей.
Построим циклическую группу с порождающим р₁₄ элементом. Входим в таблицу 2. В строке 14 находим на пересечении с р₁₄ столбцом элемент р₂₄; в строке 24 находим в клетке пересечения с 14 столбцом элемент р₁₁ и наконец в клетке строки 11 на пересечении со столбцом 14 находим элемент р₁, т.е. нейтральный элемент 1. Итак, р₁₄·р₁₄·р₁₄·р₁₄ = р₁, это элементы подгруппы 4-го порядка, значение которого нацело делит порядок 24:4 = 6. Для нее можно построить таблицу Кели и в ней не будут появляться никакие элементы кроме найденных.В этой подгруппе элементы р₁₄ и р₁₁ имеют 4-й порядок, а р₂₄ второй — это инволюция.

Морфизмы групп

Отображение f группы (G,*) в группу (G’,◦) называется гомоморфным (или гомоморфизмом), если для любых а,b ∊ G, f(a*b) = f(a)◦f(b). Обычно продолжают эти равенства так f(е) = е’,
f (a -1 ) = (f(a)) -1 . Запись справа от равенства обозначает образ и называется образом, слева — прообразом отображения f. Операции над образом и прообразом в общем случае не совпадают. Прообраз единицы (G’,◦) при гомоморфизме f называется ядром этого гомоморфизма и обозначается ker f. Хорошо известным со школьных лет примером является такое отображение
log (a◦b) = log (a) + log (b).

Элементы образа с операцией над ними (+), а в прообразе элементы связаны операцией (◦) умножения. Гомоморфный образ группы есть группа (подгруппа), т.е., если f-гомоморфизм G на G’ и G — группа, то и G’ — группа. Гомоморфизм — обобщение изоморфизма групп: если f — взаимно однозначное гомоморфное отображение G на G’, то оно изоморфно, что обозначается так G≈G’.
Две группы G и G’ с операциями (·) и (*) называются изоморфными, если существует отображение f: G → G’ такое, что (отображение f сохраняет групповую операцию) образа;

Теорема. Пусть Н — нормальная подгруппа группы G и G=G/H. Тогда отображение f группы G на G, заданное формулой f(a) =a является гомоморфизмом. Ядро этого гомоморфизма есть Н. Этот гомоморфизм часто называют естественным (каноническим).
Гомоморфизмы группы по существу исчерпываются каноническими гомоморфизмами.

Выполним разложение группы G 24-го порядка по ее подгруппе H = <1,8, 17,24>в смежные классы и построим для этого разложения факторгруппу по подгруппе Н. С этой целью выпишем в столбцы левые и правые произведения элементов подгруппы Н.

В таблице разложения группы G порядка 24 на классы смежности по подгруппе Н обозначены столбцы л1, л2, л3, л4, л5 имена левых и п1, п2, п3, п4, п5 — правых смежных классов, ведущие представители классов по одному на столбец выписаны в следующей строке.

Средний столбец Н — группа 4-го порядка (ядро гомоморфизма). Столбцы заполняются произведениями ведущих представителей классов на элементы группы Н. После заполнения столбцов выполняется сравнение классов. Если составы левых и правых классов совпадают, то говорят просто о классах смежности и обозначают Н = К0, К1, К2, К3, К4, К5. При этом подгруппа Н называется нормальной. Ведущим представителем очередного класса при заполнении таблицы выбирается наименьший элемент G, из не вошедших в уже построенные классы.

Полученные классы смежности далее рассматриваются как элементы новой группы, называемой факторгруппой группы G по подгруппе Н (обозначается факторгруппа G =G/H). Операцией в этой новой группе является умножение классов: для каждой пары классов, например, К3×К5 = К2 строится таблица 4×4, в которой строки помечаются элементами первого сомножителя, а столбцы — второго. Далее выполняют умножение как в группе G. Результат такого умножения дает 16 элементов, но все они принадлежат одному классу, в нашем случае классу К2.

Кроме отображений изоморфизмов гомоморфизмами являются эндоморфизмы и автоморфизмы. Гомоморфизм группы G в себя называется эндоморфизмом, а изоморфизм группы G на себя- автоморфизмом. Эти понятия сопоставимы с понятиями отображений неструктурированных множеств инъекцией, сюръекцией и биекцией.

Таблица 2 — Кели симметрической группы $inline$S_4 (умножение Р_k = Р_i · Р_j)$inline$

Коммутант

Каждой паре элементов а,b ∊ G сопоставим элемент, называемый коммутатором этой пары
[a, b] = a -1 b -1 ab. Подгруппа К группы G, порожденная всеми ее коммутаторами, называется коммутантом группы G или производной подгруппой.

Группа G называется разрешимой, если цепочка G ⊇ G’ ⊇ G» ⊇… ⊇ G (i) ⊇. где каждая подгруппа G (i) является коммутантом предыдущей, обрывается после конечного числа шагов на единичной подгруппе, например, G (е) = 1.
В таблице 4 знакопеременная подгруппа G’ =А₄ порядка 12 — нормальная, из G = порядка 24, так как левый и правый смежные классы по этой подгруппе совпадают (классы это одно и тоже дополнение до полной группы ). Таблица 4 при этом сворачивается в меньшую 4×4 таблицу (коммутант), содержащую элементы G» = <1,8,17,24>новой подгруппы, коммутант которой равен 1. Таблица 4 иллюстрирует разрешимость группы .

Заключение

В статье рассмотрены некоторые основные положения теории групп, которые часто используются в публикациях технического (не теоретико-математического) характера. Понимание текста таких публикаций во многом определяется владением математическим инструментарием.

Для группы приводится пример и техника гомоморфного отображения её в факторгруппу.
Числовые примеры призваны служить обеспечению доступности излагаемого материала и в большой мере помогают его пониманию и усвоению, при внимательном их разборе или даже повторении с карандашом в руках. Что в классических руководствах просто отсутствует. Часто объясняют это экономией места и времени.
Ожидаю реакции читателей, по которой станет понятно, продолжать ли в этом стиле или нет.

Источник