Сверточные коды. 4 Дисер с 15 СК и Мягкое дек с 55. Программноаппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов рида соломона в адаптивных системах обмена данными
Скачать 5.5 Mb.
|
Декодирование кодов Рида – СоломонаКоды РС были открыты в 1960 году американскими учеными Ридом и Соломоном, как частный случай недвоичных кодов Боуза - Чоудхури - Хоквингема (БЧХ). В настоящее время коды РС являются одним из наиболее востребованных видов помехоустойчивого кодирования. Связано это с тем, что коды РС эффективно справляются с исправлением группирующихся ошибок, которые возникают при воздействии на канал связи импульсной помехи. Способы декодирования кодов РС достаточно хорошо проработаны в теоретическом и реализационном плане, но, тем не менее, представляют собой довольно сложную задачу [17]. Типовая схема декодирования, получившая название авторегрессионого спектрального метода декодирования, состоит из следующих шагов [4, 19, 31]: вычисления синдрома ошибки (синдромный декодер); построения полинома локаторов ошибок, осуществляемого либо посредством высокоэффективного, но сложно реализуемого алгоритма Берлекэмпа – Месси (БМА), либо посредством простого, но медленного алгоритма Евклида; нахождения корней данного полинома, обычно решающегося полным перебором всех возможных значений (алгоритм Ченя); определения характера ошибки, сводящегося к построению битовой маски, вычисляемой на основе обращения алгоритма Форни или любого другого алгоритма обращения матрицы; исправления ошибочных символов путем наложения битовой маски на информационное слово и последовательного инвертирования всех искаженных бит с помощью операции XOR. Схема быстрого декодирования кодов РС приведена на рисунке 1.7. Здесь особого внимания и более детального рассмотрения заслуживают алгоритм по поиску локаторов искажений, а также алгоритм определения характера ошибок, предложенный Форни [23].
Алгоритм Форни Предположим, что в приемник аппаратуры передачи данных (АПД) поступила кодовая комбинация кода РС с замешанным в нее шумом:
где u(x) – переданная передатчиком АПД кодовая комбинация, в которой в процессе передачи по каналу связи произошло v ошибок, отображаемых многочленом e(x) степени v. Каждый ненулевой компонент e(x) описывается парой элементов: Yi– величина ошибок и Xi– номер позиции ошибки (локатор ошибки). Yi, Xi– элементы GF(q), при этом элемент Xi= αi, αi GF(q). Для описания ошибок используются: Многочлен локаторов ошибок:
имеющий корни Xi-1, i = 1, …, v, взаимные к локаторам ошибок, то есть Xi∙αi= 1. Многочлен значений ошибок x:
где S(x) – синдромный многочлен бесконечной степени, для которого известны только 2t коэффициентов для поступившей комбинации РС-кода. Синдром рассчитывается согласно формуле (1.24):
S v Y X j ej j Здесь j i i i1 – элемент синдрома, α – корень порождающего многочлена РС-кода. Значения j S ej задаются проверками:
где m0 j m0 2t1 при m0 1. Равенство (1.23) определяет множество из (2t – v) уравнений и называется ключевым уравнением, так как оно представляется «ключом» решения задачи декодирования. Это становится понятным, если учесть, что степень Ω(x) не превышает (v – 1), и поэтому справедливо: n
где xn m m xm m1 xm1 ... xn . Из равенства (1.23) необходимо получить v уравнений для v неизвестных коэффициентов Λ(x). Эти уравнения являются линейными. Они могут быть решены обычными методами, либо с помощью итерационных процедур. После нахождения многочлена Λ(x) ключевое уравнение позволяет найти неизвестные компоненты вектора e(x) и по ним – выходной вектор декодера Cx ux ex [26]. Простейшим путем нахождения корней многочлена Λ(x) является метод полного перебора всех возможных значений заданного поля, известный как процедура Ченя. Эта процедура состоит в последовательном вычислении Λ(α j) для каждого j и сравнении полученных значений с нулем. Если величина Λ(α-k) равна нулю, то αkявляется взаимной к корню многочлена локаторов ошибок, и k-й элемент кодовой комбинации содержит ошибку. Наиболее простым способом вычисления значения Λ(x) в точке β является схема Горнера:
Для вычисления Λ(β) по схеме Горнера требуется только v умножений и v сложений, где v – степень Λ(x). После определения локаторов ошибок с помощью ключевого уравнения рассчитываются значения ошибок. Для этого, используя значения сомножителей, входящих в равенство для Ω(x), ключевое уравнение переписывается следующим образом:
После сворачивания выражения в квадратных скобках, получим:
Приводя выражение (1.29) по модулю x2t , получим:
После чего вычисляется многочлен значений ошибок на позиции l l : x X1.
откуда
Для l-й позиции получим:
С учетом выражения (1.32) Yl значение ошибки на позиции l примет вид:
|