Помехоустойчивое кодирование. 
Разработка программы стеганографического сокрытия информации в видеофайлах формата MPEG

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

Двоичные циклические коды.

Двоичные систематические циклические коды входят во множества различных типов кодов, благодаря которым процессы кодирования и декодирования легко описать и не сложно реализовать:

· Линейные коды.

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

· Блоковые коды.

Коды данного множества являются кодами фиксированной длины. При кодировании информационное слово длины преобразуется в кодовое слово длины .

· Двоичные коды.

Коды данного множества используют модулярную арифметику по модулю 2, которая оперирует символами 0 и 1.

· Систематические коды.

Кодовые слова данного множества можно разделить на две части: информационное (исходное) слово и проверочное (добавочное) слово.

· Циклические коды.

Циклический сдвиг каждого кодового слова данного подмножества также является кодовым словом.

Определяя конкретный двоичный циклический код, используют три параметра:

• · - длина кодового слова;
• · - длина информационного (исходного) слова;
• · - порождающий многочлен кода.

где — порождающий многочленкода,.

.

.

— обозначение места соответствующей компоненты в кодовом слове (векторе),.

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

Кодирование с помощью двоичного циклическогокода с порождающим многочленом происходит по следующим шагам:

• 1) Берётся информационное слово длины (), которое можно записать в виде многочлена .
• 2) Информационный многочлен умножается, где. В представлении двоичного слова данная операция является сдвигом влево на разрядов (.

Вычисляется остаток от деления многочлена, полученного на шаге 2, на порождающий многочлен. Этот остаток записывается в нулевые разряды, полученные после сдвига, формируя кодовый многочлен .

Ниже представлен пример кодирования информационного слова (1010) с помощью двоичного циклического (7,4)-кода с порождающим многочленом .

• 1) Записываем слово в виде многочлена:
• 2) Умножаем информационный многочлен на .
• 3) Находим остаток от деления с помощью алгоритма деления Евклида.
• 4) Записываем остаток в нулевые разряды после сдвига и получаем кодовое слово (1 010 011) и соответствующий кодовый многочлен.

Построение таблицы синдромов ошибок.

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

где — количество исправляемых ошибок,.

— минимальное кодовое расстояние.

Минимальное кодовое расстояние для двоичного циклическогокода рассчитывается как минимальный вес среди его всех ненулевых кодовых слов. Весом кодового слова является количество единичных бит в этом слове. Для двоичного циклического (7,4)-кода существует всего 2 кодовых слов (табл. 1). Для этого кода минимальное кодовое расстояние. Подставляя это значение в формулу (1.3), получаем что, двоичный циклический (7,4)-код исправляет одну ошибку.

Таблица 1.1. Кодовые слова двоичного циклического (7,4)-кода ().

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

Таблица 1.2. Синдромы однократных ошибок двоичного циклического (7,4)-кода с порождающим многочленом.

Декодирование и исправление ошибок.

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

• 1) Вычисляется синдром ошибки с помощью алгоритма деления Евклида.
• 2) Если синдром нулевой, то кодовое слово не содержит ошибок. Если синдром ненулевой, то определятся ошибочный бит с помощью таблицы синдромов и исправляется.
• 3) Так как кодирование систематическое, то можно просто отсечь проверочную часть длины и получить декодированное информационное слово.

Ниже представлен пример декодирования кодового слова (10 011) с помощью двоичного циклического (7,4)-кода с порождающим многочленом .

• 1) Находим остаток от деления (синдром ошибки) с помощью алгоритма деления Евклида.
• 2) Синдром не равен нулю, поэтому находим синдром в таблице синдромов (табл. 1.2) и соответствующий ему ошибочный бит (1 000 000).
• 3) Исправляем ошибочный бит и получаем правильное кодовое слово (1 010 011). Отсекаем проверочную часть и получаем информационное слово (1010).