Кодирование сообщений

Размещено на http://www.allbest.ru/

Цель работы: ознакомиться с алгоритмом кодирования/декодирования сообщений при помощи кодов Рида-Соломона. Получить практические навыки путем кодирования/декодирования произвольного текста, используя программу RSCODEC.

Теоретическая часть

Коды Рида -- Соломона (Reed-Solomon codes) -- недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида -- Соломона, работающие с байтами (октетами).

Код Рида -- Соломона является частным случаем БЧХ-кода.

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

Коды Рида -- Соломона являются важным частным случаем БЧХ-кода, корни порождающего полинома которого лежат в том же поле, над которым строится код (). Пусть -- элемент поля порядка . Если -- примитивный элемент, то его порядок равен , то есть . Тогда нормированный полином минимальной степени над полем , корнями которого являются подряд идущих степеней элемента , является порождающим полиномом кода Рида -- Соломона над полем :

где -- некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается . Степень многочлена равна .

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

Кодовый полином может быть получен из информационного полинома , , путем перемножения и :

рид соломон декодирование

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

Теорема (граница Рейгера). Каждый линейный блоковый код, исправляющий все пакеты длиной и менее, должен содержать, по меньшей мере, проверочных символов.

Код, двойственный коду Рида -- Соломона, есть также код Рида-Соломона. Двойственным кодом для циклического кода называется код, порожденный его проверочным многочленом.

Матрица порождает код Рида -- Соломона тогда и только тогда когда любой минор матрицы отличен от нуля.

При выкалывании или укорочении кода Рида-Соломона снова получается код Рида -- Соломона. Выкалывание -- операция, состоящая в удалении одного проверочного символа. Длина кода уменьшается на единицу, размерность сохраняется. Расстояние кода должно уменьшиться на единицу, ибо в противном случае удаленный символ был бы бесполезен. Укорочение - фиксируем произвольный столбец кода и выбираем только те векторы, которые в данном столбце содержат 0. Это множество векторов образует подпространство.

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

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

Кодирование с помощью кода Рида -- Соломона может быть реализовано двумя способами: систематическим и несистематическим.

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

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

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

К исходному слову приписываются нулей, получается полином .

Этот полином делится на порождающий полином , находится остаток

, ,

где -- частное.

Этот остаток и будет корректирующим кодом Рида -- Соломона, он приписывается к исходному блоку символов. Полученное кодовое слово

.

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

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

Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия:

Вычисляет синдром ошибки

Строит полином ошибки

Находит корни данного полинома

Определяет характер ошибки

Исправляет ошибки

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

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

По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Однако для кодов РС существует более простой способ отыскания характера ошибок. Для кодов РС с произвольным множеством последовательных нулей

где формальная производная по многочлена локаторов ошибок ,а

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

Сразу после появления (60-е годы 20-го века) коды Рида - Соломона стали применяться в качестве внешних кодов в каскадных конструкциях, использующихся в спутниковой связи. В подобных конструкциях - ые символы РС (их может быть несколько) кодируются внутренними сверточными кодами. На приемном конце эти символы декодируются мягким алгоритмом Витерби (эффективный в каналах с АБГШ). Такой декодер будет исправлять одиночные ошибки в q - ичных символах, когда же возникнут пакетные ошибки и некоторые пакеты q - ичных символов будут декодированы неправильно, тогда внешний декодер Рида - Соломона исправит пакеты этих ошибок. Таким образом будет достигнута требуемая надежность передачи информации.

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

Код Рида -- Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски. Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида -- Соломона позволяют восстановить большую часть потерянной информации. Также используется при записи на такие носители, как магнитные ленты и штрих коды.

Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Также ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность примерно 25 % от исходной информации.

При записи на аудиокомпакт - диски используется стандарт Red Book. Коррекция ошибок происходит на двух уровнях C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования осуществляется также перемешивание (перемежение) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа соответственно). Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символов является фатальной ошибкой и не может быть исправлено.

Ход работы

Введем некоторое исходное информационное сообщение в соответствующее поле редактирования информационного блока на стороне кодера

Выберем количество контрольных байтов, равное 20. Соответственно, мы сможем гарантированно исправлять искажения кратностью вплоть до 10 байтов.

Закодируем теперь сообщение, нажав кнопку «закодировать и передать кадр в среду», получим следующий кадр:

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

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

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

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

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

Кроме того, также имеем информационный блок кадра в искаженном виде:

Декодируем кадр, нажав кнопку «принять кадр из среды и декодировать». Получаем предполагаемый вектор искажений вида:

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

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

Имеем синдром ошибок и видим, что он не равен нулю, что говорит о том, что принятый кадр содержит ошибки (подвергнут искажениям):

Также имеем найденный декодером полином локаторов ошибок:

Имеем вычисленные локаторы ошибок, заметим, что декодер сделал правильное предположение о количестве искаженных байтов (2):

Также имеем вычисленные полиномы величин ошибок и формальной производной:

Также имеем вычисленные величины ошибок:

Наконец, имеем сформированный полином ошибок

Повторим эксперимент. Кодировать будем информационное сообщение, которое было использовано в первом случае. Внесем в исходное сообщение искажение равное 26, 28, 30, 32 байтам. Отметим, что 32 байтов - не предельное количество искажений, которые могут быть исправлены при 13 контрольных байтах.

Скриншоты программы, полученные при искажении 26 информационных байтов

В результате искаженный кадр принимает следующий вид:

Информационный блок кадра в искаженном виде:

Предполагаемый вектор искажений вида:

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

Имеем синдром ошибок и видим, что он не равен нулю, что говорит о том, что принятый кадр содержит ошибки (подвергнут искажениям):

Полином локаторов ошибок:

Имеем вычисленные локаторы ошибок, заметим, что декодер сделал правильное предположение о количестве искаженных байтов (13):

Также имеем вычисленные полиномы величин ошибок и формальной производной:

Также имеем вычисленные величины ошибок:

Сформированный полином ошибок:

Скриншоты программы, полученные при искажении 28 информационных байтов

В результате искаженный кадр принимает следующий вид:

Информационный блок кадра в искаженном виде:

Предполагаемый вектор искажений вида:

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

Имеем синдром ошибок и видим, что он не равен нулю, что говорит о том, что принятый кадр содержит ошибки (подвергнут искажениям):

Полином локаторов ошибок:

Также имеем вычисленные полиномы величин ошибок и формальной производной:

Также имеем вычисленные величины ошибок:

Сформированный полином ошибок:

Скриншоты программы, полученные при искажении 30 информационных байтов

В результате искаженный кадр принимает следующий вид:

Информационный блок кадра в искаженном виде:

Предполагаемый вектор искажений вида:

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

Имеем синдром ошибок и видим, что он не равен нулю, что говорит о том, что принятый кадр содержит ошибки (подвергнут искажениям):

Полином локаторов ошибок:

Имеем вычисленные локаторы ошибок, заметим, что декодер сделал правильное предположение о количестве искаженных байтов (13):

Также имеем вычисленные полиномы величин ошибок и формальной производной:

Также имеем вычисленные величины ошибок:

Сформированный полином ошибок:

Скриншоты программы, полученные при искажении 32 информационных байтов

В результате искаженный кадр принимает следующий вид:

Информационный блок кадра в искаженном виде:

Предполагаемый вектор искажений вида:

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

Имеем синдром ошибок и видим, что он не равен нулю, что говорит о том, что принятый кадр содержит ошибки (подвергнут искажениям):

Полином локаторов ошибок:

Имеем вычисленные локаторы ошибок, заметим, что декодер сделал правильное предположение о количестве искаженных байтов (13):

Также имеем вычисленные полиномы величин ошибок и формальной производной:

Также имеем вычисленные величины ошибок:

Сформированный полином ошибок:

Вывод. Ознакомились с принципами кодирования/декодирования информации при помощи кодов Рида-Соломона. Получили практические навыки работы в программе RSCODEC, которая осуществляет кодирование текстовой информации при помощи кодов Рида-Соломона.

Размещено на Allbest.ru