Разработка устройств кодирования и декодирования кода Рида-Соломона

Министерство  образования Республики Беларусь

Белорусский Государственный Университет

Информатики и Радиоэлектроники 

Факультет телекоммуникаций

Кафедра сетей и устройств телекоммуникаций 
 
 

                                                      “К защите допускаю”

     “____”  “_________” 2003 г.

      _____________________

       (Ф.И.О.  преподавателя) 
 

Курсовой  проект на тему

“Разработка устройств кодирования и декодирования

кода  Рида-Соломона”

по курсу

“Теория кодирования” 
 
 

Выполнил :                                  Проверил:

                                                                      Конопелько В. К. 
 
 
 

Минск  2003

Содержание 

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

1. Выбор и  обоснование параметров кода………………..……………………...4

2. Разработка  и обоснование структурной   схемы кодека............……………...7

2.1. Синтез кодирующего  устройства……………………………………………7

2.2. Синтез декодирующего  устройства………………………………………..14

3.Разработка  принципиальной схемы…………………………………………..17

Заключение ………………………………………………………………………23

Литература ………………………………………………………………………24 

Введение

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

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

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

1.Выбор  обоснования кода.

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

            Причём ошибки из-за модуля  отказов, довольно часто бывают  однонаправленными, когда с “в”  разрядов ошибочного модуля постоянно  считывается слово 00…0, или 11…1 . Кроме того, из-за отказа цепей питания и в схеме электронного обрамления ЗУ наблюдается полный переход всех разрядов опрашиваемого слова в состояние 00…0 или 11…1, т.е. возникают однонаправленные словарные ошибки.

            Предложено довольно большое число конструктивных методов задания кодов. Коды в одних случаях имеют достаточно большую длину “n”,но отличаются неоднородностью при построении. Это усложняет реализацию, снижает быстродействие схем коррекции.

            В других случаях в матрицах  “и” содержится небольшое число единиц (следовательно обеспечиваются малые аппаратурные и временные затраты),достигаемое за счет увеличения числа проверочных разрядов. 
 

  Коды для обнаружения  и исправления  одиночных модулей  ошибок

            Эти коды легко построить на основе кодов с простой проверкой на чётность, объединив I-е символы каждого модуля в кодовое слово с расстоянием d=2. Проверочная матица такого кода имеет размерность b*n и состоит из единичных матриц I(b) порядка b [2]:

                                           

                                                   H = [ I(b) : I(b) : … : I(b)] . 

           Для исправления одиночных модулей  ошибок(b) код должен иметь не менее 2b проверочных символов. Наибольший интерес представляют коды с минимальной избыточностью (2b) и минимальной плотностью единиц в проверочной матрице. Последнее позволяет достичь максимального быстродействия при минимальной сложностью схем кодирования и декодирования. 
 
 
 
 
 
 

  Проверочные Н-матрицы кодов Рида-Соломона

            При построении кодов, исправляющих модуль ошибок (КИМ) длины b, каждый модуль разрядов слова рассматривают как q - значный разряд, принимающий одно из q значений от 0 до (q-1). В этом случае элементы столбцов в проверочной Н-матрице являются не (0,1), а подматрицами (0,1,hb) , значения которых определяются выражением: 

                                   hβ = [αβ+b-1, αβ+b-2, . . . , αβ+b-b] ,  

     где αβ+b-I  - столбец , соответствующий остатку от деления xβ+b-I  на порождающий многочлен степени b; β – показатель степени матрицы, 1≤ β≤2b-1 [2]. В качестве порождающего полинома используется неприводимый примитивный полином степени b, который обеспечивает максимальное число различных матриц hβ,

     равное 2b-1. 

            Н-матрица  кода Рида-Соломона, исправляющего модуль ошибок, имеет  следующий вид: 

                     

        

            В данной Н-матрице вторая строка (кроме двух последних подтаблиц)

     содержит  подматрицы b*b всех степеней.

2.1. Разработка структурной схемы кодера.

     Рассмотрим  представление столбцов Н(х) для  кодов, исправляющих пакетные ошибки длины b=tn.

     Разобьем  информационный блок кодовой последовательности или кодограммы u1u2 …. uk   на пакеты длины b=tn  двоичных символов внутри которых группируются ошибки:

      u1 …...ub                     ub+1….u 2b        ……. uk-b….uk 

          1-й                       2-й                        k/b-й

        пакет                   пакет                      пакет 

     Двоичные  разряды или двоичные символы, входящие в один пакет, рассматриваются  как g-значный  разряд. который может  принимать любое из «g» значений от «0» до «g-1». Значение «g» определяется выражением

     g=2b   или    g=  

     В нашем случае  b=tn=4 двоичных символов, то g=2b=24=16 двоичных символов.

     В качестве элементов столбцов Н(х)-матрицы   в этом случае используются не “1” и “0”, как для двоичных кодов, а матрицы вида « », значения которых определяются выражением: 

      ,                         (1)

     где - столбец. соответствующий остатку от деления    на порождающий полином P(x) степени ; - показатель степени матрицы  

     Матрицы вида  hb имеют ранг или .

     В качестве порождающего полинома P(x) используется неприводимый примитивный полином степени b=tn, котрый обеспечивает максимальное число  различных матриц вида , равное  2b-1, т.е.

     Определим количество матриц вида hB и построить их, если b=tn=4 двоичным символам.

     Решение: 

                     1) Количество матриц вида  равно N=24=16

               2) Согласно  выражению (1) матрицы     имеют следующее построение   : первый столбец матрицы определяется как остаток от      деления     =x1+4-1 ;

     

                   

     второй  столбец матрицы h1 определяется как  остаток R2(х) от деления

        /x4+x+1  т.е.  x3/x4+x+1;

     

         

     третий  столбец h1 определяется как остаток  R3(х) от деления

        т.е. 

     

                   

     четвертый столбец h1  определяется как остаток R4(х) от деления 

        т.е. 

     

                 

     По  полученным данным строим матрицу h1

     

     Аналогично  определяются столбцы матрицы h2 только при выполнении операции деления  меняются показатели степени «х», например:

 

     Аналогично  определяются столбцы остальных  матриц 

                              

                              

                              

                              

                        

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

     При умножении матриц показатели степени  суммируются по модулю 2b-1 или  ;

     При делении матриц показатель степени  матрицы-делителя вычисляется из показателя степени матрицы-делимого по модулю 2b-1 или  .

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

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