Анализ алгоритма кодирования

19

Оглавление

Введение……………………………………………………………………….....3

Глава 1. Коды Рида-Соломона и их свойства.………………………………....5

Глава 2. Ошибки в символах. Декодирование. Преимущества кодирования.……………………………………………………………………..7

Глава 3. Арифметика конечного поля Галуа. Образующий полином….…….9

Глава 4. Архитектура кодировщика и декодера. Вычисление синдрома.…..10

Глава 5. Реализация кодировщика и декодера Рида-Соломона. Аппаратная реализация. Программная реализация……………………………………...…12

Заключение………………………………………………………………...……14

Список использованной литературы…………………………………………..15

Приложение…………………………………………………………………..…18
Введение

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

Хотя существующие на данный момент системы передачи данных отвечают всем основным стандартам и требованиям, они все же не являются совершенными. Причин тому влияние помех в канале связи. При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Естественный язык обладает большой избыточностью (в европейских языках -- до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством. Избыточность могла бы быть использована и при передаче кодированных сообщений в технических системах. Например, каждый фрагмент текста («предложение») передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, больная избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Впервые теоретическое исследование эффективного кодирования предпринял К. Шеннон.

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

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

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

Объект: процесс формирования цифровых сигналов

Предмет: кодирование информации

Цель исследования: проанализировать алгоритм кодирования.

Задачи:

1) Проанализировать теоретические основы задач кодов Рида-Соломона.

2) Программно реализовать код Рида-Соломона на ЯВУ.

Глава 1. Коды Рида-Соломона и их свойства

Коды Рида-Соломона были предложены в 1960 году Ирвином Ридом и Густавом Соломоном, являвшимися сотрудниками Линкольнской лаборатории МТИ. Ключом к использованию этой технологии стало изобретение эффективного алгоритма декодирования Элвином Беликамфом, профессором Калифорнийского университета (Беркли).

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

Они применяются для исправления ошибок во многих системах:

        устройствах памяти (включая магнитные ленты, CD, DVD, штриховые коды, и т.д.);

        беспроводных или мобильных коммуникациях (включая сотовые телефоны, микроволновые каналы и т.д.);

        спутниковых коммуникациях;

        цифровом телевидении / DVB (digital video broadcast);

        скоростных модемах, таких как ADSL, xDSL и т.д.

На рис. 1 показаны практические приложения (дальние космические проекты) коррекции ошибок с использованием различных алгоритмов (Хэмминга, кодов свертки, Рида-Соломона и пр.).

Рис. 1.  Несовершенство кода, как функция размера информационного блока для разных задач и алгоритмов

Типовая система представлена ниже (Рис. 2)

Рис. 2.  Схема коррекции ошибок Рида-Соломона

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

Коды Рида-Соломона являются субнабором кодов BCH и представляют собой линейные блочные коды. Код Рида-Соломона специфицируются как RS(n,k) s-битных символов.

Это означает, что кодировщик воспринимает k информационных символов по s битов каждый и добавляет символы четности для формирования n символьного кодового слова. Имеется nk символов четности по s битов каждый. Декодер Рида-Соломона может корректировать до t символов, которые содержат ошибки в кодовом слове, где 2t = n–k.

Диаграмма, представленная ниже, показывает типовое кодовое слово Рида-Соломона (Рис. 3):

Рис. 3.  Структура кодового слова R-S

Пример. Популярным кодом Рида-Соломона является RS(255, 223) с 8-битными символами. Каждое кодовое слово содержит 255 байт, из которых 223 являются информационными и 32 байтами четности. Для этого кода

n = 255, k = 223, s = 8

2t = 32, t = 16

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

При размере символа s, максимальная длина кодового слова (n) для кода Рида-Соломона равна n = 2s – 1.

Например, максимальная длина кода с 8-битными символами (s = 8) равна 255 байтам.

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

Пример. Код (255, 223), описанный выше, может быть укорочен до (200, 168). Кодировщик будет работать с блоком данных 168 байт, добавит 55 нулевых байт, сформирует кодовое слово (255, 223) и передаст только 168 информационных байт и 32 байта четности.

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

Глава 2. Ошибки в символах. Декодирование. Преимущество

кодирования.

Одна ошибка в символе происходит, когда 1 бит символа оказывается неверным или когда все биты неверны.

Пример. Код RS(255,223) может исправить до 16 ошибок в символах. В худшем случае, могут иметь место 16 битовых ошибок в разных символах (байтах). В лучшем случае, корректируются 16 полностью неверных байт, при этом исправляется 16 x 8 = 128 битовых ошибок.

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

Алгебраические процедуры декодирования Рида-Соломона могут исправлять ошибки и потери. Потерей считается случай, когда положение неверного символа известно. Декодер может исправить до t ошибок или до 2t потерь. Данные о потере (стирании) могут быть получены от демодулятора цифровой коммуникационной системы, т.е. демодулятор помечает полученные символы, которые вероятно содержат ошибки.

Когда кодовое слово декодируется, возможны три варианта.

1.      Если 2s + r < 2t (s ошибок, r потерь), тогда исходное переданное кодовое слово всегда будет восстановлено. В противном случае

2.      Декодер детектирует ситуацию, когда он не может восстановить исходное кодовое слово. или

3.      Декодер некорректно декодирует и неверно восстановит кодовое слово без какого-либо указания на этот факт.

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

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

Пример. Пусть имеется цифровая телекоммуникационная система, работающая с BER (Bit Error Ratio), равной 10-9, т.е. не более 1 из 109 бит передается с ошибкой. Такого результата можно достичь путем увеличения мощности передатчика или применением кодов Рида-Соломона (либо другого типа коррекции ошибок). Алгоритм Рида-Соломона позволяет системе достичь требуемого уровня BER с более низкой выходной мощностью передатчика.

Кодирование и декодирование Рида-Соломона может быть выполнено аппаратно или программно.

Глава 3. Арифметика конечного поля Галуа. Образующий полином.

Коды Рида-Соломона базируются на специальном разделе математики – полях Галуа (GF) или конечных полях. Арифметические действия (+,-, x, / и т.д.) над элементами конечного поля дают результат, который также является элементом этого поля. Кодировщик или декодер Рида-Соломона должны уметь выполнять эти арифметические операции. Эти операции для своей реализации требуют специального оборудования или специализированного программного обеспечения.

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

g(x) = (x – ai)(x – ai+1)...(x – ai+2t)

а кодовое слово формируется с помощью операции

c(x) = g(x).i(x)

где g(x) является образующим полиномом, i(x) представляет собой информационный блок, c(x) – кодовое слово, называемое простым элементом поля.

Пример. Генератор для RS(255, 249)

              g(x)= (x – a0)(x – a1)(x – a2)(x – a3)(x – a4)(x – a5)

              g(x)= x6 + g5x5 + g3x3 + g2x2 + g1x1 + g0

Глава 4. Архитектура кодировщика и декодера. Вычисление синдрома.

2t символов четности в кодовом слове Рида-Соломона определяются из следующего соотношения:

Ниже показана схема реализации кодировщика для версии RS(255,249):

Рис. 4.6.  Схема кодировщика R-S

Каждый из 6 регистров содержит в себе символ (8 бит). Арифметические операторы выполняют сложение или умножение на символ как на элемент конечного поля.

Общая схема декодирования кодов Рида-Соломона показана ниже на рис. 4.7.

Рис. 4.7.  Схема работы с кодами Рида-Соломона

Обозначения:

        r(x) – Полученное кодовое слово

        Si – Синдромы

        L(x) – Полином локации ошибок

        Xi – Положения ошибок

        Yi – Значения ошибок

        c(x) – Восстановленное кодовое слово

        v – Число ошибок

Полученное кодовое слово r(x) представляет собой исходное (переданное) кодовое слово c(x) плюс ошибки:

r(x) = c(x) + e(x)

Декодер Рида-Соломона пытается определить позицию и значение ошибки для t ошибок (или 2t потерь) и исправить ошибки и потери.

Вычисление синдрома похоже на вычисление четности. Кодовое слово Рида-Соломона имеет 2t синдромов, это зависит только от ошибок (а не передаваемых кодовых слов). Синдромы могут быть вычислены путем подстановки 2tкорней образующего полинома g(x) в r(x).

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