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

Омский государственный технический университет

Сравнительный анализ полноразмерных и укороченных кодов Рида-Соломона

УДК 519.725.2

Седунов Д.П.

E-mail: pokki122@mail.ru

Аннотации

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

Ключевые слова: коды Рида-Соломона, укороченные коды Рида-Соломона, быстродействие.

Comparative analysis of full-dimensional and short-term Rida-Solomon codes

Sedunov D.P.

There are considered, described and compared the Reed-Solomon codes. The methods of encoding and decoding of Reed-Solomon codes are reviewed. A overview of the methods of encoding and decoding of Reed-Solomon codes. Considered an algorithm for decoding the truncated Reed-Solomon codes.

Keywords: Reed-Solomon codes, truncated Reed-Solomon codes, performance.

Введение

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

Способы кодирования информации бывают различные и зависят они, в первую очередь, от целей кодирования. Наиболее распространенными из них являются: - экономность (достигается сокращением записи); - удобство обработки или восприятия.

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

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

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

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

Актуальность работы заключается в том, что несмотря на распространение в настоящее время более эффективных турбо кодов и кодов с малой плотностью проверок на четность (LDPC кодов), укороченные коды Рида-Соломона широко используют в системах, где имеются ограничения на вычислительную сложность или требуется высокая пропускная способность [2, 3, 4].

1. Укороченные коды Рида-Соломона

Коды Рида-Соломона (Reed-Solomon code, R-S code, РС) -- это недвоичные циклические коды, символы которых представляют собой m-битовые последовательности, где m -- положительное целое число, большее 2 [5].

Код Рида-Соломона можно выразить через n и k, где n - длина кода, k - количество информационных символов. Длину кода (n) можно рассчитать по формуле:

?? = 2^?? ? 1, (1)

где m - число битов в символе.

Количество информационных символов (k) можно рассчитать по формуле:

?? = 2^?? ? 1 ? 2 • ??, (2)

где t- способность кода к коррекции ошибок в символах.

Коды Рида-Соломона относятся к классу циклических кодов. Из любого (n, k) циклического кода можно получить (n-i, k-i) укороченный код, где i<k - параметр укорачивания. Иными словами, укорачивание происходит за счет сокращения числа информационных элементов. Кодовое расстояние укороченного кода остается в точности тем же, что у исходного кода. В общем случае укороченный код Рида-Соломона в отличие от исходного кода не является циклическим. Из теории кодов Рида-Соломона следует, что если символом кода является байт, то полная длина кодового слова должна составлять 255 байт (239 информационных и 16 проверочных) [6, 7]. Однако, на практике часто необходимо согласовывать размер пакета с параметрами кода, в следствии чего перед кодированием в начало каждого транспортного пакета добавляют i нулей информационных байт, которые кодером не передаются в канал связи. Недостатком такого способа декодирования является несогласованность скоростей передачи кодером кодового слова (длина такого слова n-i, поскольку нули не передаются) и обработки декодером принятого дополненного нулями кодового слова длины n. Кроме того, для формирования синдрома в этом случае необходимо n тактов работы декодера, в то время как при применении альтернативного способа декодирования для этого достаточно n-i тактов. Идея такого декодирования заключается в том, что, в отличие от декодера кода максимальной длины, который для формирования синдрома выполняет операции умножения принятого слова на полином X^p и деления на порождающий полином, декодер укороченного кода умножает на полином, равный остатку от деления полинома X^p+i на порождающий полином, и полученное произведение делит на порождающий полином. Примеры такого декодирования широко освещены для двоичных кодов [4], чего нельзя сказать для укороченных кодов РидаСоломона, в особенности их аппаратной реализации. Кодирующие устройства для укороченных кодов ничем не отличаются от кодеров кодов максимальной длины.

В дальнейшем промоделируем в среде MATLAB описанные выше подходы кодирования и результаты их декодирования, сравним временные затраты на декодирование каждого из методов.

2. Разработка алгоритма декодирования укороченных кодов Рида-Соломона

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

Диаграмма, представленная на рисунке 1, показывает типовое кодовое слово Рида-Соломона.

Рисунок 1 - Структура кодового слова РС

Блок «Декодер Рида-Соломона» выполняет декодирование одного блока бинарного кода.

Выходной кодовый символ строится следующим образом: a₁,a₂ ,a_3, ,...a_k ®b₁,b₂ ,b₃,...b_l ,a₁,a₂ ,a₃,...a_k где ?? - отсчёты исходного сигнала, ?? - контрольные отсчёты.

Значения отсчётов ?? получаются как остаток от полиноминального деления входной последовательности, сдвинутой на l символов, на генератор кода. Каждый отсчёт получается из m последовательных битов.

При кодировании и декодировании используется арифметика в полях Галуа, задаваемая массивом констант.

Если длина сообщения не выровнена по длине символа, лишние биты игнорируются [8-12].

Блок-схема разработанного для моделирования РС декодера представлена на рисунке 2а), а на рисунке 2б) - представлена типовая РС декодера.

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

а) б)

Рисунок 2 - Блок-схема РС декодера: а) - разрабатываемого; б) - типовая.

Рассмотрим рисунок 2 подробнее.

Как видно из рисунка 2, разрабатываемая схема отличается от типовой использованием алгоритма Massey за место алгоритма Euclidian'a. Данное изменение позволяет уменьшить число операций, необходимых для вычисления полинома ошибок. Также замена алгоритма Вандермонда (матрицы Вандермонда) на алгоритм Берликампфа позволила облегчить и ускорить расчеты, за счет сокращения числа математических операций.

Перед началом декодирования необходимо произвести операцию перевода входного сигнала из двоичной системы счисления в поле Галуа (GF), данная операция осуществляется следующим образом:

Поле Галуа GF(??) -- поле, состоящее из конечного числа элементов ??. Число элементов ?? в поле называется его порядком.

С точностью до изоморфизма конечное поле полностью определяется его порядком, который всегда является степенью какого-нибудь простого числа, то есть ?? = ??^??, где б -- простое число, а n -- любое натуральное число. При этом б будет являться характеристикой этого поля.

Для работы в поле Галуа целесообразно иметь таблицы, называемые Log tableи Antilog table, но также можно работать без таблицы, используя сразу порождающие полиномы, но это требует больше вычислений. Данные таблицы позволяют с помощью формул переводить входные бинарные данные (представленные в виде вектора) в значения, применимые в поле Галуа (Log table) и обратно, из значений поля Галуа в векторный вид (Antilog table).

ДляGF (2³) Log table и Antilog tableбудут иметь вид, представленный в таблице 1.

Таблица 1. Log tableиAntilog tableдляGF (2³)

Поле Address представляет собой значение степени 2³. Используя значения, взятые из таблицы 1, по формуле 3 произведем перевод из двоичной системы в поле Галуа:

?? = ??(??(??(??)???(??) ? ?? + 1), (3)

где A - значение из столбца Antilog table, соответствующее порядковому номеру i; L- значение из столбца Log table, соответствующее порядковому номеру i; n- показатель степени.

После перевода входного сигнала в поле Галуа начинается основной этап декодирования - вычисление синдромов[13].

Синдром -- это результат проверки четности, выполняемой над принятым полиномом поврежденного кодового слова (r), чтобы определить, принадлежит ли r набору кодовых слов. Если r является членом набора, то синдром S имеет значение, равное 0. Любое ненулевое значение S означает наличие ошибок. Точно так же, как и в двоичном случае, синдром S состоит из n-k символов, {??_??}, (?? = 1, … , ?? ? ??).

Каждый правильный полином кодового слова U(X) является кратным полиномиальному генератору g(X). Следовательно, корни g(X) также должны быть корнями U(X). Поскольку r(X) = U(X) + e(X), то r(Х), вычисляемый с каждым корнем g(X), должен давать нуль, только если r(Х) будет правильным кодовым словом. Любые ошибки приведут в итоге к ненулевому результату в одном (или более) случае. декодирование компьютерный соломон

В разрабатываемом декодере исправления 8-символьной ошибки имеется 16 неизвестных -- восемь относятся к расположению ошибки, а другие восемь касаются ошибочных значений. Необходимо знать о том - что существует важное различие между недвоичным декодированием r(Х) и двоичным. При двоичном декодировании декодеру нужно знать лишь расположение ошибки. При условии, если известно, где находится ошибка, бит нужно поменять с 1 на 0 или наоборот. Но в нашем случае недвоичные символы требуют, чтобы мы не только узнали расположение ошибки, но и определили правильное значение символа, расположенного на этой позиции. Поскольку в разрабатываемом декодере имеется 16 неизвестных - то нужно 16 уравнений, чтобы найти их [8].

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

После нахождения синдромов вычисляем полином ошибок (Алгоритм Massey).

Предположим, что в кодовом слове имеется v ошибок, расположенных на позициях ??^??1, ??^??2, … , ??^????. Тогда полином ошибок можно записать следующим образом:

??(??) = ??_??1•??^??1 + ??_??2•??^??2 + ? + ??_????•??^????, (4)

где индексы 1, 2, ..., v обозначают 1-ю, 2-ю, ..., v-ю ошибки, а индекс J -- расположение ошибки.

Для коррекции искаженного кодового слова нужно определить каждое значение ошибки ??_???? и ее расположение ??^????, где l = 1, 2, …, v. Обозначим номер локатора ошибки как ??_?? = ??^????. Далее вычисляется n - k = 2t символа синдрома, подставляя ??_?? в принятый полином при j = 1, 2, …, 2t.

Если вычислен ненулевой вектор синдрома (один или более его символов не равны нулю), это означает, что была принята ошибка. Далее нужно узнать расположение ошибки (или ошибок).

Полином локатора ошибок определяем по формуле:

??(??) = (1 + ??₁??) • (1 + ??₂??) … (1 + ??_????) = 1 + ??₁?? + ??₂??² + ? + ??_????^??, (5)

Корнями ??(??) будут ¹?в₁ , ¹?в₂ , … , ¹?в_v . Величины, обратные корням ??(??), будут представлять номера расположений ошибочной комбинации e(Х). Тогда, воспользовавшись авторегрессионной техникой моделирования, составляем из синдромов матрицу, в которой первые t синдромов будут использоваться для предсказания следующего синдрома.

Необходимо знать, что индексация номеров расположения ошибок является сугубо произвольной [8].

Далее займемся нахождением корней (Алгоритм Форни).

Алгоритм Форни - является быстрым алгоритмом в том смысле, что решает задачу нахождения решения системы из t линейных уравнений за число операций порядка ??², вместо числа ??², которое потребовалось бы для системы уравнений общего вида. Для того чтобы декодирование в целом имело место порядка ??², алгоритм Форни упрощает решение системы уравнений для нахождения значений ошибок по известным локаторам.

Общее уравнение, используемое при математическом анализе реализации алгоритма Форни, имеет вид:

Щ(??_??^?1) = ??_????_?? ?_?????(1 ? ??_????_??^?1). (6)

Данное выражение позволяет выполнить прямое вычисление значений ошибок (корней). Сложность непосредственного вычисления каждого значения пропорциональна степени многочлена, следовательно, общая сложность алгоритма имеет порядок ??².

Используя полученные результаты при вычислении синдромов, было принято решение обозначить ошибки как: ??_????, где индекс j обозначает расположение ошибки, а индекс l -- l-ю ошибку. Поскольку каждое значение ошибки связано с конкретным месторасположением, систему обозначений можно упростить, обозначив ??_???? просто как ??_??. Теперь, приготовившись к нахождению значений ошибок ??₁ и ??₂, связанных с позициями ??_?? = ??^?? , можно использовать любое из синдромных уравнений [14].

В завершении будем находить ошибочные символы в поле Галуа.

По синдрому, локации ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Для кодов РС с произвольным множеством2??_?? последовательных нулей ??^??, ??^??+1, … , ??^??+??, ?? = 2??_?? ? 1 была использована следующая формула:

, (7)

где ??^?(??) - формальная производная по x многочлена локаторов ошибок

??(x), а Л(??) = ??(??)??(??)????????^2????+1.

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

Формула, описывающая алгоритм Берлекампфа, представлена ниже:

, (8)

где l находится в интервале: 1 ? l ? v; b принимает два любых значения: 1 и 0; z(x) = 1 + (S₁+ у₁)x + (S₂+ у₁S₁+ у₂)x²+ЃEЃEЃE+(S_н+ у₁S_н?1 +ЃEЃEЃE+у_н)x^н .

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

После окончания процедуры декодирования был осуществлен перевод из GF в двоичный вид для обработки данных.

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

Заключение

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

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

Cписок литературы

1. Питерсон, У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон. - М.: Мир, 1976. - 596 с.

2. Robert H. Morelos-Zaragoza. The Art of Error Correcting Coding. First Edition, John Wiley & Sons, 2002. - 221 p.

3. R.E.Blahut. Theory and Practice of Error Control Codes. Addison-Wesley Publishing Company, Massachusetts, 1984. - 576 p.

4. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976.

5. Odenwalder J. P. Error Control Coding Handbook. Linkabit Corporation, San Diego, CA, July, 15, 1976.

6. ETSI EN 300 421 Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services. 1997. 24 p.

7. ETSI EN 301 790 Digital Video Broadcasting (DVB); Interaction channel for satellite distribution systems. 2005. 176 p.

8. Declercq D., Fossorier M. Extended minsum algorithm for decoding LDPC codes over GF(q) // IEEE International Symp. on Inf. Theory, 2005, pp.464-468.

9. Zhang F., Pfister H. List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q // In Proc. IEEE Global Telecom. Conf., Washington, DC, Nov. 2007. pp.283-287.

10. Reed I.S., Solomon G. Polynomial codes over certain finite fields // J. Soc. IndustrialAppl. Math., 1960, vol.8, PP.300-304.

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

12. Вернер М. Основы кодирования. -- Техносфера, 2004. -- 288 с.

13. Wicker, «Error Control Systems for Digital Communication and Storage», Prentice-Hall. - 1995.

14. Morelos-Zaragoza R. H. The Art of Error Correcting Coding. Second Edition - John Wiley & Sons, Ltd. - 2006. - c. 269.

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