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

1. Определение полинома локации ошибок.

Это может быть сделано с помощью алгоритма Berlekamp-Massey или алгоритма Эвклида. Алгоритм Эвклида используется чаще на практике, так как его легче реализовать, однако алгоритм Berlekamp-Massey позволяет получить более эффективную реализацию оборудования и программ.

2. Нахождение корней этого полинома. Это делается с привлечением алгоритма поиска Chien.

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

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

Существует несколько коммерческих аппаратных реализаций. Имеется много разработанных интегральных схем, предназначенных для кодирования и декодирования кодов Рида-Соломона. Эти ИС допускают определенный уровень программирования (например RS(255, k), где t может принимать значения от 1 до 16).

Заключение

В ходе курсовой работы мне удалось выяснить:

1. Каким образом применяется кодировка Рида-Соломона, для чего она нужна. Что представляют собой поля Гаусса. Какова Архитектура процессов кодирования и декодирования.

2. Как работает кодировщик и декодер Рида-Соломона, их программная реализация.

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

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

книги:

1) James Plank "A tutorial on Reed-Solomon Coding for fault-tolerance in RAID-like systems" 

2) Tom Moore "REED-SOLOMON PACKAGE" 

3) James S. Plank GFLIB "C Procedures for Galois Field Arithmetic and Reed-Solomon Coding" (библиотека кодов)
 

4) Блейхут Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986.

сайты:

http://www.insidepro.com/kk/027/027r.shtml

http://www.deltann.ru/10/d-072007/p-32

Приложение

Программная реализация кодировки Рида-Соломона, представленная на языке Си. Кодируемые данные передаются через массив data[i], где i = 0...(k - 1), а сгенерированные символы четности заносятся в массив b[0]...b[2 * t - 1]. Исходные и результирующие данные должны быть представлены в полиномиальной форме (т.е. в обычной форме машинного представления данных). Кодирование производится с использованием сдвигового feedback-регистра, заполненного соответствующими элементами массива g[] с порожденным полиномом внутри, сгенерированное кодовое слово описывается следующей формулой:

с(x) = data(x) * x ^ (n - k) + b(x), где ^ означает возведение в степень
на основе исходных текстов.

Код программы:

encode_rs()
{
       int i, j;
       int feedback;

       // инициализируем поле бит четности нулями
       for (i = 0; i < n - k; i++) b[i] = 0;

       // обрабатываем все символы
       // исходных данных справа налево
       for (i = k - 1; i >= 0; i--)
       {
              // готовим (data[i] + b[n - k - 1]) к умножению на g[i]
              // т.е. складываем очередной "захваченный" символ исходных
              // данных с младшим символом битов четности (соответствующего
              // "регистру" b2t-1, см. рис. 2) и переводим его в индексную
              // форму, сохраняя результат в регистре feedback;
              // как мы уже говорили, сумма двух индексов есть произведение
              // полиномов
              feedback = index_of[data[i] ^ b[n - k - 1]];

// есть еще символы для обработки?
              if (feedback != -1)
              {
                     // осуществляем сдвиг цепи bx-регистров
                     for (j = n - k - 1; j > 0; j--)
                            // если текущий коэффициент g - это действительный
                            // (т.е. ненулевой коэффициент, то
                            // умножаем feedback на соответствующий g-коэффициент
                            // и складываем его со следующим элементов цепочки
                            if (g[j] != -1) b[j] = b[j - 1] ^ alpha_to[(g[j] + feedback) % n];
                     else
                            // если текущий коэффициент g - это нулевой коэффициент,
                            // выполняем один лишь сдвиг без умножения, перемещая
                            // символ из одного m-регистра в другой
                            b[j] = b[j - 1];

                     // закольцовываем выходящий символ в крайний левый b0-регистр
                     b[0] = alpha_to[(g[0] + feedback) % n];
              }
              else
              {
                     // деление завершено,
                     // осуществляем последний сдвиг регистра,
                     // на выходе регистра будет частное, которое теряется,
                     // а в самом регистре - искомый остаток
                     for (j = n - k - 1; j > 0; j--) b[j] = b[j - 1]; b[0] = 0;
              }
       }
}