Кодер

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

Введение

По основному своему образованию я не математик, но в связи с читаемыми мной дисциплинами в ВУЗе пришлось в ней дотошно разбираться. Долго и упорно читал классические учебники ведущих наших Университетов, пятитомную математическую энциклопедию, множество тонких популярных брошюр по отдельным вопросам, но удовлетворения не возникало. Не возникало и глубокое понимание прочитанного.

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

Этот путь привел меня к вопросу, а что я уже могу самостоятельно делать без книжных костылей, имея перед собой только чистый лист бумаги и карандаш с ластиком? Оказалось совсем немного и не совсем то, что было нужно. Пройден был сложный путь бессистемного самообразования. Вопрос был такой. Могу ли я построить и объяснить, прежде всего себе, работу кода, обнаруживающего и исправляющего ошибки, например, код Хемминга, (7, 4)-код?

Известно, что код Хемминга широко используется во многих прикладных программах в области хранения и обмена данными, особенно в RAID 2; кроме того, в памяти типа ECC и позволяет на лету исправлять однократные и обнаруживать двукратные ошибки.

Информационная безопасность. Коды, шифры, стегосообщения

Информационное взаимодействие путем обмена сообщениями его участников должно обеспечиваться защитой на разных уровнях и разнообразными средствами как аппаратными так и программными. Эти средства разрабатываются, проектируются и создаются в рамках определенных теорий (см. рис.А) и технологий, принятых международными договоренностями об OSI/ISO моделях.

Защита информации в информационных телекоммуникационных системах (ИТКС) становится практически основной проблемой при решении задач управления, как в масштабе отдельной личности пользователя, так и для фирм, объединений, ведомств и государства в целом. Из всех аспектов защиты ИТКС в этой статье будем рассматривать защиту информации при ее добывании, обработке, хранении и передаче в системах связи.

Уточняя далее предметную область, остановимся на двух возможных направлениях, в которых рассматриваются два различных подхода к защите, представлению и использованию информации: синтаксическом и семантическом. На рисунке используются сокращения: кодеккодер-декодер; шидеш шифратор-дешифратор; скриз скрыватель извлекатель.


Рисунок А Схема основных направлений и взаимосвязи теорий, направленных на решение задач защиты информационного взаимодействия

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

Семантическая (смысловая) безопасность сообщений обеспечивается методами криптологии, которая средствами криптографии позволяет защитить от овладения содержанием информации потенциальным нарушителем. Нарушитель при этом может скопировать, похитить, изменить или подменить, или даже уничтожить сообщение и его носитель, но он не сможет получить сведений о содержании и смысле передаваемого сообщения. Содержание информации в сообщении останется для нарушителя недоступным. Таким образом, предметом дальнейшего рассмотрения будет синтаксическая и семантическая защита информации в ИТКС. В этой статье ограничимся рассмотрением только синтаксического подхода в простой, но весьма важной его реализации корректирующим кодом.

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

В общем поехали. По определению, а их довольно много, понять что есть код очень даже не просто. Авторы пишут, что код это алгоритм, отображение и ещё что-то. О классификации кодов я не буду здесь писать, скажу только, что (7, 4)-код блоковый.

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

Поскольку роль сторон переменчива оба этих устройства объединяют в одно и называют сокращенно кодек (кодер/декодер), и устанавливают на обоих концах канала. Дальше, раз есть слова, есть и алфавит. Алфавит это два символа {0, 1}, в технике массово используются блоковые двоичные коды. Алфавит естественного языка (ЕЯ) множество символов букв, заменяющих при письме звуки устной речи. Здесь не будем углубляться в иероглифическую письменность в слоговое или узелковое письмо.

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

Ричард Хемминг, наверное, раньше других понял, что если избыточность не устранять, а разумно организовать, то ее можно использовать в системах связи для обнаружения ошибок и автоматического их исправления в кодовых словах передаваемого текста. Он понял, что все 128 семиразрядных двоичных слов могут использоваться для обнаружения ошибок в кодовых словах, которые образуют код подмножество из 16 семиразрядных двоичных слов. Это была гениальная догадка.

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

Построение (7, 4)-кода Хемминга

Вернемся к Хеммингу. Слова (7, 4)-кода образованы из 7 разрядов С j = , j = 0(1)15, 4-информационные и 3-проверочные символа, т.е. по существу избыточные, так как они не несут информации сообщения. Эти три проверочных разряда удалось представить линейными функциями 4-х информационных символов в каждом слове, что и обеспечило обнаружение факта ошибки и ее места в словах, чтобы внести исправление. А (7, 4)-код получил новое прилагательное и стал линейным блоковым двоичным.

Линейные функциональные зависимости (правила (*)) вычислений значений символов
имеют следующий вид:





Исправление ошибки стало очень простой операцией в ошибочном разряде определялся символ (ноль или единица) и заменялся другим противоположным 0 на 1 или 1 на 0.
Сколько же различных слов образуют код? Ответ на этот вопрос для (7, 4)-кода получается очень просто. Раз имеется лишь 4 информационных разряда, а их разнообразие при заполнении символами имеет = 16 вариантов, то других возможностей просто нет, т. е. код состоящий всего из 16 слов, обеспечивает представление этими 16-ю словами всю письменность всего языка.

Информационные части этих 16 слов получают нумерованный вид
():

0=0000; 4= 0100; 8 = 1000; 12=1100;
1=0001; 5= 0101; 9 = 1001; 13=1101;
1=0010; 6= 0110; 10=1010; 14=1110;
3=0011; 7= 0111; 11=1011; 15=1111.

Каждому из этих 4-разрядных слов необходимо вычислить и добавить справа по 3 проверочных разряда, которые вычисляются по правилам (*). Например, для информационного слова 6 равного 0110 имеем и вычисления проверочных символов дают для этого слова такой результат:






Шестое кодовое слово при этом приобретает вид: Таким же образом необходимо вычислить проверочные символы для всех 16-и кодовых слов. Подготовим для слов кода 16-строчную таблицу К и последовательно будем заполнять ее клетки (читателю рекомендую проделать это с карандашом в руках).

Таблица К кодовые слова Сj, j = 0(1)15, (7, 4) кода Хемминга

Описание таблицы: 16 строк кодовые слова; 10 колонок: порядковый номер, десятичное представление кодового слова, 4 информационных символа, 3 проверочных символа, W-вес кодового слова равен числу ненулевых разрядов ( 0). Заливкой выделены 4 кодовых слова-строки это базис векторного подпространства. Собственно, на этом все код построен.

Таким образом, в таблице получены все слова (7, 4) кода Хемминга. Как видите это было не очень сложно. Далее речь пойдет о том, какие идеи привели Хемминга к такому построению кода. Мы все знакомы с кодом Морзе, с флотским семафорным алфавитом и др. системами построенными на разных эвристических принципах, но здесь в (7, 4)-коде используются впервые строгие математические принципы и методы. Рассказ будет как раз о них.

Математические основы кода. Высшая алгебра

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

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

Создатели кодов, долго не могли додуматься до кода, обнаруживающего и исправляющего две ошибки. Идеи, использованные Хеммингом, там не срабатывали. Пришлось искать, и нашлись новые идеи. Очень интересно! Захватывает. Для поиска новых идей потребовалось около 10 лет и только после этого произошел прорыв. Коды, обнаруживающие произвольное число ошибок, были получены сравнительно быстро.

Векторные пространства, поля и группы. Полученный (7, 4)-код (Таблица К) представляет множество кодовых слов, являющихся элементами векторного подпространства (порядка 16, с размерностью 4), т.е. частью векторного пространства размерности 7 с порядком Из 128 слов в код включены лишь 16, но они попали в состав кода не просто так.

Во-первых, они являются подпространством со всеми вытекающими отсюда свойствами и особенностями, во-вторых, кодовые слова являются подгруппой большой группы порядка 128, даже более того, аддитивной подгруппой конечного расширенного поля Галуа GF() степени расширения n = 7 и характеристики 2. Эта большая подгруппа раскладывается в смежные классы по меньшей подгруппе, что хорошо иллюстрируется следующей таблицей Г. Таблица разделена на две части: верхняя и нижняя, но читать следует как одну длинную. Каждый смежный класс (строка таблицы) элемент факторгруппы по эквивалентности составляющих.

Таблица Г Разложение аддитивной группы поля Галуа GF () в смежные классы (строки таблицы Г) по подгруппе 16 порядка.

Столбцы таблицы это сферы радиуса 1. Левый столбец (повторяется) синдром слова (7, 4)-кода Хемминга, следующий столбец лидеры смежного класса. Раскроем двоичное представление одного из элементов (25-го выделен заливкой) факторгруппы и его десятичное представление:



Техника получение строк таблицы Г. Элемент из столбца лидеров класса суммируется с каждым элементом из заголовка столбца таблицы Г (суммирование выполняется для строки лидера в двоичном виде по mod2). Поскольку все лидеры классов имеют вес W=1, то все суммы отличаются от слова в заголовке столбца только в одной позиции (одной и той же для всей строки, но разных для столбца). Таблица Г имеет замечательную геометрическую интерпретацию. Все 16 кодовых слов представляются центрами сфер в 7-мерном векторном пространстве. Все слова в столбце от верхнего слова отличаются в одной позиции, т. е. лежат на поверхности сферы с радиусом r =1.

В этой интерпретации скрывается идея обнаружения одной ошибки в любом кодовом слове. Работа идет со сферами. Первое условие обнаружения ошибки сферы радиуса 1 не должны касаться или пересекаться. Это означает, что центры сфер удалены друг от друга на расстояние 3 или более. При этом сферы не только не пересекаются, но и не касаются одна другой. Это требование для однозначности решения: какой сфере отнести полученное на приемной стороне декодером ошибочное (не кодовое одно из 128 -16 = 112) слово.

Второе все множество 7-разрядных двоичных слов из 128 слов равномерно распределено по 16 сферам. Декодер может получить слово лишь из этого множества 128-ми известных слов с ошибкой или без нее. Третье приемная сторона может получить слово без ошибки или с искажением, но всегда принадлежащее одной из 16-и сфер, которая легко определяется декодером. В последней ситуации принимается решение о том, что послано было кодовое слово центр определенной декодером сферы, который нашел позицию (пересечение строки и столбца) слова в таблице Г, т. е номера столбца и строки.

Здесь возникает требование к словам кода и к коду в целом: расстояние между любыми двумя кодовыми словами должно быть не менее трех, т. е. разность для пары кодовых слов, например, Сi = 85==1010101; Сj = 25== 0011001 должна быть не менее 3; 85 25 = 1010101 0011001 =1001100 = 76, вес слова-разности W(76) = 3. (табл. Д заменяет вычисления разностей и сумм). Здесь под расстоянием между двоичными словами-векторами понимается количество не совпадающих позиций в двух словах. Это расстояние Хемминга, которое стало повсеместно использоваться в теории, и на практике, так как удовлетворяет всем аксиомам расстояния.

Замечание. (7, 4)-код не только линейный блоковый двоичный, но он еще и групповой, т. е. слова кода образуют алгебраическую группу по сложению. Это означает, что любые два кодовых слова при суммировании снова дают одно из кодовых слов. Только это не обычная операция суммирования, выполняется сложение по модулю два.

Таблица Д Сумма элементов группы (кодовых слов), используемой для построения кода Хемминга

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

Применение кода. Кодер

Кодер размещается на передающей стороне канала и им пользуется отправитель сообщения. Отправитель сообщения (автор) формирует сообщение в алфавите естественного языка и представляет его в цифровом виде. (Имя символа в ASCII-соде и в двоичном виде).
Тексты удобно формировать в файлах для ПК с использованием стандартной клавиатуры (ASCII кодов). Каждому символу (букве алфавита) соответствует в этой кодировке октет бит (восемь разрядов). Для (7, 4)- кода Хемминга, в словах которого только 4 информационных символа, при кодировании символа клавиатуры на букву требуется два кодовых слова, т.е. октет буквы разбивается на два информационных слова естественного языка (ЕЯ) вида
.

Пример 1. Необходимо передать слово цифра в ЕЯ. Входим в таблицу ASCII-кодов, буквам соответствуют: ц 11110110, и 11101000, ф 11110100, р 11110000, а 11100000 октеты. Или иначе в ASCII кодах слово цифра = 1111 0110 1110 1000 1111 0100 1111 0000 1110 0000

с разбивкой на тетрады (по 4 разряда). Таким образом, кодирование слова цифра ЕЯ требует 10 кодовых слов (7, 4)-кода Хемминга. Тетрады представляют информационные разряды слов сообщения. Эти информационные слова (тетрады) преобразуются в слова кода (по 7 разрядов) перед отправкой в канал сети связи. Выполняется это путем векторно-матричного умножения: информационного слова на порождающую матрицу. Плата за удобства получается весьма дорого и длинно, но все работает автоматически и главное сообщение защищается от ошибок.
Порождающая матрица (7, 4)-кода Хемминга или генератор слов кода получается выписыванием базисных векторов кода и объединением их в матрицу. Это следует из теоремы линейной алгебры: любой вектор пространства (подпространства) является линейной комбинацией базисных векторов, т.е. линейно независимых в этом пространстве. Это как раз и требуется порождать любые векторы (7-разрядные кодовые слова) из информационных 4-разрядных.

Порождающая матрица (7, 4, 3)-кода Хемминга или генератор слов кода имеет вид:


Справа указаны десятичные представления кодовых слов Базиса подпространства и их порядковые номера в таблице К
i строки матрицы это слова кода, являющиеся базисом векторного подпространства.

Пример кодирования слов информационных сообщений (порождающая матрица кода выстраивается из базисных векторов и соответствует части таблицы К). В таблице ASCII-кода берем букву ц = <1111 0110>.

Информационные слова сообщения имеют вид:

.

Это половины символа (ц). Для (7, 4)-кода, определенного ранее, требуется найти кодовые слова, соответствующее информационному слову-сообщению (ц) из 8-и символов в виде:

.

Чтобы превратить эту буквусообщение (ц) в кодовые слова u, каждую половинку буквы-сообщения i умножают на порождающую матрицу G[k, n] кода (матрица для таблицы К):



Получили два кодовых слова с порядковыми номерами 15 и 6.

Покажем детальное формирование нижнего результата 6 кодового слова (умножение строки информационного слова на столбцы порождающей матрицы); суммирование по (mod2)

<0110> <1000> = 01 +10 + 10 + 00 = 0(mod2);
<0110> <0100> = 00 +11 + 10 + 00 = 1(mod2);
<0110> <0010> = 00 +10 + 11 + 00 = 1(mod2);
<0110> <0001> = 00 +10 + 10 + 01 = 0(mod2);
<0110> <0111> = 00 +11 + 11 + 01 = 0(mod2);
<0110> <1011> = 01 +10 + 11 + 01 = 1(mod2);
<0110> <1101> = 01 +11 + 10 + 01 = 1(mod2).

Получили в результате перемножения пятнадцатое и шестое слова из таблицы К. Первые четыре разряда в этих кодовых словах (результатах умножения) представляют информационные слова. Они имеют вид: , (в таблице ASCII это только половины буквы ц). Для кодирующей матрицы выбраны в качестве базисных векторов в таблице К совокупности слов с номерами: 1, 2, 4, 8. В таблице они выделены заливкой. Тогда для этой таблицы К кодирующая матрица получит вид G[k,n].

В результате перемножения получили 15 и 6 слова таблицы К кода.

Применение кода. Декодер

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

Основной задачей декодера является проверка того, является ли полученное слово (7 разрядов) тем, которое было отправлено на передающей стороне, не содержит ли слово ошибок. Для решения этой задачи для каждого полученного слова декодером путем умножения его на проверочную матрицу Н[n-k, n] вычисляется короткий вектор-синдром S (3 разряда).

Для слов, которые являются кодовыми, т. е. не содержат ошибок, синдром всегда принимает нулевое значение S =<000>. Для слова с ошибкой синдром не нулевой S 0. Значение синдрома позволяет обнаружить и локализовать положение ошибки с точностью до разряда в принятом на приемной стороне слове, и декодер может изменить значение этого разряда. В проверочной матрице кода декодер находит столбец, совпадающий со значением синдрома, и порядковый номер этого столбца принимает равным искаженному ошибкой разряду. После этого для двоичных кодов декодером выполняется изменение этого разряда просто замена на противоположное значение, т. е. единицу заменяют нулем, а нуль единицей.

Рассматриваемый код является систематическим, т. е. символы информационного слова размещаются подряд в старших разрядах кодового слова. Восстановление информационных слов выполняется простым отбрасыванием младших (проверочных) разрядов, число которых известно. Далее используется таблица ASCII-кодов в обратном порядке: входом являются информационные двоичные последовательности, а выходом буквы алфавита естественного языка. Итак, (7, 4)-код систематический, групповой, линейный, блочный, двоичный.

Основу декодера образует проверочная матрица Н[n-k, n], которая содержит число строк, равное числу проверочных символов, а столбцами все возможные, кроме нулевого, столбцы из трех символов . Проверочная матрица строится из слов таблицы К, они выбираются так, чтобы быть ортогональными к кодирующей матрице, т.е. их произведение нулевая матрица. Проверочная матрица получает следующий вид в операциях умножения она транспонируется. Для конкретного примера проверочная матрица Н[n-k, n] приведена ниже:





Видим, что произведение порождающей матрицы на проверочную в результате дает нулевую матрицу.

Пример 2. Декодирование слова кода Хемминга без ошибки (е<7> =<0000000>).
Пусть на приемном конце канала приняты слова 760 и 13105 из таблицы К,
u<7> + е<7> = <0 1 1 1 1 0 0 > + <0 0 0 0 0 0 0>,
где ошибка отсутствует, т. е. имеет вид е<7> = <0 0 0 0 0 0 0>.


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

Пример 3. Обнаружение одной ошибки в слове, полученном на приемном конце канала (таблица К).

А) Пусть требуется передать 7 е кодовое слово, т.е.

u<7> = <0 1 1 1 1 0 0> и в одном третьем слева разряде слова, допущена ошибка. Тогда она суммируется по mod2 с 7-м передаваемым по каналу связи кодовым словом
u<7> + е<7> = <0 1 1 1 1 0 0 > + <0 0 1 0 0 0 0> = <0 1 0 1 1 0 0>,
где ошибка имеет вид е<7> = <0 0 1 0 0 0 0>.

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

Выполним такое умножение для наших исходных (7-го вектора с ошибкой) данных.


В результате такого умножения на приемном конце канала получили вектор-синдром S<n-k>, размерность которого (nk). Если синдром S<3>= <0,0,0> нулевой, то делается вывод о том, что принятое на приемной стороне слово принадлежит коду С и передано без искажений. Если синдром не равен нулю S<3> <0,0,0>, то его значение указывает на наличие ошибки и ее место в слове. Искаженный разряд соответствует номеру позиции столбца матрицы Н[n-k, n], совпадающего с синдромом. После этого искаженный разряд исправляется, и полученное слово обрабатывается декодером далее. На практике для каждого принятого слова сразу вычисляется синдром и при наличии ошибки, она автоматически устраняется.

Итак, при вычислениях получен синдром S=<110> для обоих слов одинаковый. Смотрим на проверочную матрицу и отыскиваем в ней столбец, совпадающий с синдромом. Это третий слева столбец. Следовательно, ошибка допущена в третьем слева разряде, что совпадает с условиями примера. Этот третий разряд изменяется на противоположное значение и мы вернули принятые декодером слова к виду кодовых. Ошибка обнаружена и исправлена.

Вот собственно и все, именно так устроен и работает классический (7, 4)-код Хемминга.

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

Заключение

В работе рассмотрены основные положения и задачи информационной безопасности, названы теории, призванные решать эти задачи.

Задача защиты информационного взаимодействия субъектов и объектов от ошибок среды и от воздействий нарушителя относится к кодологии.

Рассмотрен в деталях (7, 4)-код Хемминга, положивший начало нового направлению в теории кодирования синтеза корректирующих кодов.

Показано применение строгих математических методов, используемых при синтезе кода.
Приведены примеры иллюстрирующие работоспособность кода.

Литература

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976, 594 c.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер.с англ. М.: Мир, 1986, 576 с.

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

Так, например, для определенного Рида-Соломона кода (РС-кода) необходимо установить:
длину n кодового слова (блока);
количество k информационных и N-k проверочных символов;
неприводимый многочлен р(х), задающий конечное поле GF(2^r);
примитивный элемент конечного поля;
порождающий многочлен g(x);
параметр j кода;
используемое перемежение;
последовательность передачи кодовых слов или символов в канал и еще некоторые другие.

Здесь в работе рассматривается несколько другая частная задача моделирование собственно РС-кода, являющаяся центральной основной частью названной выше задачи анализа кода.

Описание РС-кода и его характеристик

Для удобства и лучшего уяснения сущности устройства РС-кода и процесса кодирования вначале приведем основные понятия и термины (элементы) кода.
Рида Соломона коды (РС-код) можно интерпретировать как недвоичные коды БЧХ (Боуза Чоудхури Хоквингема), значения кодовых символов которых взяты из поля GF(2^r), т. е. r информационных символов отображаются отдельным элементом поля. Коды Рида Соломона это линейные недвоичные систематические циклические коды, символы которых представляют собой r-битовые последовательности, где r целое положительное число, большее 1.

Коды Рида Соломона (n, k) определены на r-битовых символах при всех n и k, для которых:
0 < k < n < 2^r + 2, где
k число информационных символов, подлежащих кодированию,
n число кодовых символов в кодируемом блоке.

Для большинства (n, k)-кодов Рида Соломона; (n, k) = (2^r1, 2^r12t), где
t количество ошибочных символов, которые может исправить код, а
nk = 2t число контрольных символов.

Код Рида Соломона обладает наибольшим минимальным расстоянием (числом символов, которыми отличаются последовательности), возможным для линейного кода. Для кодов Рида Соломона минимальное расстояние определяется следующим образом: dmin = nk +1.

Определение. РС-кодом над полем GF(q=р^m), с длиной блока n = q^m-1, исправляющим t ошибок, является множество всех кодовых слов u_(n) над GF(q), для которых 2t последовательных компонентов спектра с номерами равны 0.

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

Информационный многочлен Q. Задает текст сообщения, которое делится на блоки (слова) постоянной длины и оцифровывается. Это то, что подлежит передаче в системе связи.
Порождающий многочлен g(x) РС-кода многочлен, который преобразует информационные многочлены (сообщения) в кодовые слова путем перемножения Qg(x)= С =u_(n) над GF(q).

Проверочный многочлен h(x) позволяет устанавливать наличие искаженных символов в слове.
Синдромный многочлен S(z). Многочлен, содержащий компоненты соответствующие ошибочным позициям. Вычисляется для каждого принятого декодером слова.
Многочлен ошибок E. Многочлен с длиной равной кодовому слову, с нулевыми значениями во всех позициях, кроме тех, что содержат искажения символов кодового слова.

Многочлен локаторов ошибок (z) обеспечивает нахождение корней, указывающих позиции ошибок в словах, принятых приемной стороной канала связи (декодером). Корни его могут быть найдены методом проб и ошибок, т.е. путем подстановки по очереди всех элементов поля, пока (z) не станет равным нулю.
Многочлен значений ошибок (z)(z)S(z) (modz^2t) сравним по модулю z^2t с произведением многочлена локаторов ошибок на синдромный многочлен.

Неприводимый многочлен поля р(x). Конечные поля существуют не при любом числе элементов, а только в случае, если число элементов является простым числом р или степенью q=р^m простого числа. В первом случае поле называется простым (его элементы-вычеты чисел по модулю простого числа р), во втором-расширением соответствующего простого поля (его q элементов-многочленов степени m-1 и менее это вычеты многочленов по модулю неприводимого над простым полем многочлена р(x) степени m)

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

Таблица П Характеристики элементов конечного поля расширения GF(2⁴), неприводимый многочлен p(x) = x⁴+x+1, примитивный элемент =0010= 2₁₀


Пример 1. Над конечным полем GF(2⁴), задан неприводимый многочлен поля p(x) = x⁴ + x + 1, примитивный элемент =2, и задан (n, k)- код Рида-Соломона (РС-код). Кодовое расстояние этого кода равно d = n k + 1 = 7. Такой код может исправлять до трёх ошибок в блоке (кодовом слове) сообщения.

Порождающий многочлен g(z) кода имеет степень m =n-k = 15-9 = 6 (его корнями являются 6 элементов поля GF(2⁴) в десятичном представлении, а именно элементы 2, 3, 4, 5, 6, 7) и определяется соотношением, т.е. многочленом от z с коэффициентами (элементами) из GF(2⁴) в десятичном представлении при i = 1(1)6. В рассматриваемом РС-коде 2⁹ = 512 кодовых слов.

Кодирование сообщений РС-кодом

В таблице П эти корни имеют и степенное представление .
.
Здесь z- абстрактная переменная, а -примитивный элемент поля, через его степени выражены все (16) элементы поля. Многочленное представление элементов поля использует переменную х.
Вычисление порождающего многочлена g(x)=АВ РС-кода выполним частями (по три скобки):

Векторное представление (через коэффициенты g(z) элементами поля в десятичном представлении) порождающего многочлена имеет вид
g(z) = G_<7>= (1, 11, 15, 5, 7, 10, 7).

После формирования порождающего многочлена РС-кода, ориентированного на обнаружение и исправление ошибок, задается сообщение. Сообщение представляется в цифровом виде (например, ASCII- кодом), от которого переходят к многочленному или векторному представлению.

Информационный вектор (слово сообщения) имеет k компонентов из (n, k). В примере k = 9, вектор получается 9-компонентный, все компоненты это элементы поля GF(2⁴) в десятичном представлении Q_<9> = (11, 13, 9, 6, 7, 15, 14, 12, 10).

Из этого вектора формируется кодовое слово u_<15> вектор с 15 компонентами. Кодовые слова, как и сами коды, бывают систематическими и несистематическими. Несистематическое кодовое слово получают умножением информационного вектора Q на вектор, соответствующий порождающему многочлену
.

После преобразований получаем несистематическое кодовое слово (вектор) в виде
Qg = <11, 15, 3, 9, 6, 14, 7, 5, 12, 15, 14, 3, 3, 7, 1>.
При систематическом кодировании сообщение (информационный вектор) представляют многочленом Q(z) в форме Q(z)=q(z)g(z) + R(z), где степень degR(z)<m = 6. После этого к вектору Q справа приписывается остаток R (всё в десятичном виде). Это делается так.

Многочлен Q сдвигают в сторону старших разрядов на величину m = n k, что достигается путём умножения Q(z) на Z^{n k} (в примере Z^{n k} = Z ⁶) и выполняют после сдвига деление Q(z)Z^{n k} на g(z). В результате находят остаток от деления R(z). Все операции выполняют над полем GF(2⁴)
(11, 13, 9, 6, 7, 15, 14, 12, 10, 0, 0, 0, 0, 0, 0) =
=(1, 11, 15, 5, 7, 10, 7)(11, 15, 9, 10,12,10,10,10, 3) + (1, 2, 3, 7, 13, 9) = GS + R.

Остаток при делении многочленов вычисляется обычным способом (уголком см.здесь Пример 6). Деление выполняется по образцу: Пусть Q = 26, g(z) = 7 тогда 26 = 73 +R(z), R(z)=26 -73 =26-21 = 5. Вычисление остатка R(z) от деления многочленов. Приписываем к вектору Q справа остаток R.

Получаем u_<15> кодовое слово в систематическом виде. Этот вид явно содержит информационное сообщение в k старших разрядах кодового слова
u_<15> = (11,13,9,6,7,15,14,12,10; 1, 2, 3, 7, 13, 9).
Разряды вектора нумеруются справа налево от 0(1)14. Шесть младших разрядов справа являются проверочными.

Декодирование кодов Рида-Соломона

После получения блока декодер обрабатывает каждый блок (кодовое слово) и исправляет ошибки, которые возникли во время передачи или хранения. Декодер делит полученный многочлен на порождающий многочлен кода РС. Если остаток равен нулю, то ошибок не обнаружено, в противном случае имеют место ошибки.

Типичный РС-декодер выполняет пять этапов в цикле декодирования, а именно:
1. Вычисление синдромного многочлена (его коэффициентов ), обнаруживаются ошибки.
2. Решается ключевое уравнение Падэ вычисление значений ошибок и их позиций соответствующих местоположений.
3. Реализуется процедура Ченя нахождение корней многочлена локатора ошибок.
4. Используется алгоритм Форни для вычисления значения ошибки.
5. Вносятся корректирующие поправки в искаженные кодовые слова;
завершается цикл извлечением сообщения из кодовых слов (снятие кода).

Вычисление синдрома.
Генерация синдрома из принятого кодового слова является первым этапом процесса
декодирования. Здесь вычисляются синдромы и определяется, есть ли ошибки в полученном кодовом слове или нет

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

Обнаружение искажений.

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

Вычисление синдромного многочлена
Умножение на приемной стороне кодового слова С на проверочную матрицу Н может давать в результате два исхода:
синдромный вектор S=0, что соответствует отсутствию ошибок в векторе C;
синдромный вектор S0, что означает наличие ошибок (одной или более) в компонентах вектора C.

Интерес представляет второй случай.
Кодовый вектор с ошибками представлен в виде C(E) =C + E, E вектор ошибок. Тогда
Компоненты Sj синдрома определяются либо соотношением суммирования
для n = q-1 и j = 1(1)m = n-k, либо схемой Горнера:
$inline$S_j = C_0 +^j(C_1 +^j(C_2 +...+^j(C_{n-2} +^jC_{n-1})...))$inline$

Пример 2. Пусть вектор ошибок имеет вид Е =<0 0 0 0 12 0 0 0 0 0 0 8 0 0 0>. Он искажает в кодовом векторе символы на 3-й и 10-й позициях. Значения ошибок соответственно 8 и 12 эти значения также являются элементами поля GF(2⁴) и заданы в десятичном (табл. П) представлении. В векторе Е нумерация позиций от младших справа налево, начиная с 0(1)14.

Сформируем теперь кодовый вектор с двумя ошибками в 3-ем разряде и в 10-ом со значениями 8 и 12 соответственно. Это осуществляется суммированием в поле GF(2⁴) по правилам арифметики этого поля. Суммирование элементов поля с нулем не изменяет их значения. Ненулевые значения (элементы поля) суммируются после преобразования их к многочленному представлению, как обычно суммируются многочлены, но коэффициенты при неизвестной приводятся по mod 2.

После получения результата суммирования они вновь преобразуются к десятичному представлению, пройдя предварительно через степенное представление

Ниже показано вычисление искажённых ошибками значений в 10 и 3 позициях кодового слова:
$inline$(7+12) ^6+^11 =x^3 +x^2 +x^3 +x^2 +x^1 =^1 = 2,$inline$
$inline$(3 + 8) ^2+ ^7 =x^2 +x^3 +x^1 + 1 =^{12}=13.$inline$

Декодер вычисления выполняет по общей формуле для компонентов Sj, j=1(1)m. Здесь (в модели) используем соотношение , так как E задаём (моделируем) в программе сами, то ненулевые слагаемые получаются только при i = 3 и i = 10.


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

Проверочная матрица РС кода

Как только сформулирован порождающий многочлен кода, появляется возможность построения проверочной матрицы для кодовых слов, а также определение количества исправляемых ошибок (см.здесь, декодер ). Построим вспомогательную матрицу [715], из которой могут быть получены две разные проверочные матрицы: первые шесть строк одна и последние шесть строк другая.

Сама матрица формируется специальным образом. Первые две строки очевидны, третья строка и все последующие получены вычитанием из предыдущей (второй) строки отрезка чисел натурального ряда 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 по mod 15. При возникновении нулевого значения оно заменяется числом 15, отрицательные вычеты преобразуются в положительные.


Каждая матрица соответствует своему порождающему многочлену для систематического и несистематического кодирования.

Определение коэффициентов синдромного многочлена

Далее будем определять коэффициенты синдромного многочлена при j=1(1)6.
Относительно кодового слова с длиной , поступающего на вход декодера мы допускаем, что оно искажено ошибками.

Относительно вектора ошибок для его выявления необходимо знать следующее:
количество искаженных позиций у кодового слова
;
номера (положение) искаженных позиций в кодовом слове ;
значения (величины) искажений $inline$e_; e_GF(2^4)$inline$.
Как вычисляется и используется далее синдромный вектор (многочлен) S? Его роль при декодировании кодовых слов очень значительна. Покажем это с иллюстрацией на числовом примере.

Пример 3. (Вычисление компонентов синдромного вектора )

то в итоге имеем =<8,13,7,13,15,15>.

Для дальнейшего рассмотрения введем новые понятия. Величину будем называть локатором ошибок, здесь искаженный символ кодового слова на позиции , примитивный элемент поля GF(2⁴).
Множество локаторов ошибок конкретного кодового слова рассматривается далее как коэффициенты многочлена локаторов ошибок (z), корнями которого являются значения , обратные локаторам.

При этом выражения обращаются в нуль.
$inline$(z) = (1-zx_1)(1-zx_2)...(1-zx_v) =_vz^v +_{v-1}z^{v-1} +...+_1z +_0$inline$
всегда свободный член уравнения всегда свободный член уравнения .
Степень многочлена локаторов ошибок равна v количеству ошибок и не превышает величины .

Все искаженные символы находятся на разных позициях слова, следовательно, среди локаторов ,, не может быть повторяющихся элементов поля, а многочлен (z)=0 не имеет кратных корней.
Величины ошибок для удобства записи переобозначим символом . Для коэффициентов синдромного многочлена ранее рассматривались нелинейные уравнения. В нашем случае v=1 начало отсчета компонентов синдрома.


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

Преобразование к системе линейных уравнений
В уравнение многочлена локаторов ошибок подставляется значение его корней . При этом многочлен обращается в нуль. Образуется тождество, обе части которого умножаем на , получаем:
$inline$y_i(_vx_i^{j}+_{v-1}x_i^{j+1}+...+_1x_i^{j+v-1}+x_i^{j+v})=0,1iv, 1jv$inline$.

Таких равенств получаем .
Суммируем эти равенства по всем , при которых эти равенства выполняются. Так как многочлен (z) имеет v корней , раскроем скобки и перенесем коэффициенты за знак суммы:


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


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

Эта матрица не вырождена, если число ошибок в кодовом слове C(E) строго равно , т.е. способность помехоустойчивости данного кода не нарушилась.

Решение системы линейных уравнений

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

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

Над бесконечными полями известны методы решения ганкелевой системы линейных уравнений:
итеративный метод Тренча Берлекэмпа Месси (ТБМ-метод); (1)
прямой детерминированный Питерсона Горенштейна Цирлера; (ПГЦ метод); (2)
метод Сугиямы, использующий алгоритм Евклида для нахождения НОД (С-метод).(3)
Не рассматривая других методов, остановим свой выбор на ТБМ-методе. Мотивировка выбора следующая.

Метод (ПГЦ) прост и хорош, но для малого количества исправляемых ошибок, С-метод сложен для реализации на ЭВМ и ограниченно опубликован (освещен) в источниках, хотя С-метод как и ТБМ-метод по известному многочлену синдромов S(z) обеспечивает решение уравнения Падэ над полем Галуа. Это уравнение сформировано для многочлена локаторов ошибок (z) и многочлена (z), в теории кодирования называется ключевым уравнением Падэ:
.

Решением ключевого уравнения является совокупность корней многочлена (z), и соответственно локаторов , т.е. позиции ошибок. Значения (величины) ошибок определяются из формулы Форни в виде

где и значения многочленов (z) и (z) в точке , обратной корню многочлена (z);
i позиция ошибки; формальная производная многочлена (z) по z;

Формальная производная многочлена в конечном поле

Имеются различия и сходство для производной по переменной в поле вещественных чисел и формальной производной в конечном поле. Рассмотрим многочлен

это элементы поля, i = 1(1)n.
Элементы поля. Задан код над вещественным полем GF(2⁴). Производная по z имеет вид: .
В бесконечном вещественном поле операции умножить на n и суммировать n раз совпадают. Для конечных полей производная определяется иначе.
Производная по аналогии определяется соотношением:

где ((i)) = 1+1+...+1, (i) раз, суммируемых по правилам конечного поля: знак + обозначает операцию суммировать столько-то раз, т.е. элемент повторить 2 раза, элемент повторить 3 раза, элемент повторить n раз.

Ясно, что эта операция не совпадает с операции умножения в конечном поле. В частности, в полях GF(2^r) сумма четного числа одинаковых слагаемых берется по mod2 и обнуляется, а нечетного равна самому слагаемому без изменений. Следовательно, в поле GF(2^r) производная получает вид

вторая и старшие четные производные в этом поле равны нулю.

Из алгебры известно, если многочлен имеет кратные корни (кратность р ), то производная многочлена будет иметь этот же корень, но с кратностью р-1. Если р = 1, то f(z) и f '(z) не имеет общего корня. Следовательно, если многочлен и его производная имеют общий делитель, то существует кратный корень. Все корни производной f '(z) эти корни кратные в f(z).

Метод решения ключевого уравнения

ТМБ (Тренча-Берлекэмпа-Месси) метод решения ключевого уравнения.
Итеративный алгоритм обеспечивает определение многочленов (z) и (z), и решение уравнения Падэ (ключевого).

Исходные данные: коэффициенты многочлена степени n-1.
Цель. Определение в явном (аналитическом) виде многочленов (z) и (z).
В алгоритме используются обозначения: j номер шага, степень многочлена, $inline$_j(z) =_{ji}z^i +_{ji-1}z^{i-1}+...+_{j1}z+_{j0}$inline$ разложение многочлена по степеням и промежуточные переменные и функции на j-м шаге алгоритма;

Начальные условия необходимо задавать, так как здесь используется
рекурсия.
Начальные условия:


Пример 4. Выполнение итеративного алгоритма для вектора
S=(8,13,7,13,15,15). Определяются многочлены и .
Таблица 2 Расчет многочленов локаторов ошибок




Итак $inline$_j^(z)=14z^2+13z+1$inline$, $inline$_j^(z)$inline$=7z+8.
Многочлен локаторов ошибок (z) над полем GF(2⁴) с неприводимым многочленом p(x) = x⁴ + x + 1 имеет корни
и , в этом легко убедиться непосредственной проверкой, т.е. $inline$i_1= 3, i_2 =10, 13 = ^{12}, 1 =^{12}^{3}$inline$ и . Подстановка корней в
$inline$(z=13)=14(13)^2+1313+1=^{13}(^{12})^2+(^{12})^2+^0= ^{37}+^{24} +^{0}$inline$=
=;
$inline$(z = 6)=14(6)^2+136+1 = ^{13}(^{5})^2+(^{5})^2+^{0}$inline$=
=.

Взяв формальную производную от (z), получаем _2(z) =214+13 =13, так как 14z берется в сумме 2 раза и по mod 2 обращается в нуль.
С использованием формулы Форни найдем выражения для расчета величин ошибок .


Подстановкой значений i = 3 и i = 10 позиций в последнее выражение
находим
= =;
$inline$е_{10} = 10^{15-10}+11 =^{9}^{5}+^{10}=^{14}+^{10}$inline$= =.

Архитектура построения программного комплекса

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

Схема функционирования программного комплекса

Работа с комплекса начинается с загрузки цифрового потока с помощью дампа из файла. После загрузки пользователю предоставляется возможность визуального представления двоичного содержимого файла и его текстового содержимого.
В рамках данного интерфейса должны реализовываться следующие функциональные задачи:
Загрузка исходного сообщения;
Преобразование сообщения в дамп;
Кодирование сообщения;
Моделирование перехваченного сообщения
Построение спектров полученных кодовых слов с целью анализа их визуального представления;
Вывод на экран параметров кода.

Описание работы программного комплекса

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

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


Рисунок 3 Промежуточное представление результатов работы
программного комплекса

Рисунок 4. Результаты загрузки файла сообщения

Рисунок 5. Результаты кодирования файла

Рисунок 6. Вывод сообщения с внесенными в него ошибками.

Рисунок 7. Вывод результатов декодирования и сообщения с внесенными в него ошибками

Рисунок 8. Вывод декодированного сообщения.

Заключение

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

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

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

Список используемой литературы

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. 576 с.
2. Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. 744 с.
3. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971. 478 с.
4. Габидулин Э.М., Афанасьев В.Б. Кодирование в радиоэлектронике. М.: Радио и связь, 1986. 176 с., ил.
5. Вернер М. Основы кодирования. Учебник для ВУЗов. М.: Техносфера, 2004. 288 с.
6. Трифонов П.В. Адаптивное кодирование в многочастотных системах. Диссертация на соискание ученой степени кандидата технических наук. СПб: Санкт-Петербургский государственный политехнический университет, 2005. 147 с.
7. Фомичев С. М., Абилов А.В. Обзор математических моделей каналов связи и их применение в телекоммуникационных системах. Ижевск: Ижевский государственный технический университет, 2001. 60 с.
8. Касами Т., Токура Н., Ивадари Е., Инагаки Я. Теория кодирования. М.: Мир, 1978. 576 с.
9. Муттер В. М. Основы помехоустойчивой телепередачи информации. Л.: Энергоатомиздат. Ленинградское отделение, 1990. 288 с.
10. Ваулин А. Е., Смирнов С.И. Моделирование помехозащищенного канала передачи сообщения в системе связи/Сборник алгоритмов и программ типовых задач. Вып.26. под редакцией ктн доц. И.А. Кудряшова . СПб.: ВКА им А.Ф. Можайского, 2007. стр. 121-130.
11. Карпушев С.И Конспект лекций по алгебре (часть 2. Абстрактная
алгебра). ВИКУ им. А. Ф. Можайского, 2002. 97 с.
12. Зайцев И. Е. Методика определения параметров помехоустойчивого каскадного кодирования. Л.: ВИКИ, 1987 120 с.