Вернер М. Основы кодирования (2004) (1151849), страница 39
Текст из файла (страница 39)
Эти разряды могут содержать самое большее qk~i различныхg-ичных чисел. Следовательно, во всем множестве кодовых слов ввыделенных к—1 разрядах имеет место по крайней мере qk—qk~1 совпадений. Рассмотрим любые два кодовых слова, совпадающие между собой в к — 1 разрядах.
Так как эти слова могут иметь различиетолько в п - Н 1 компонентах, расстояние между ними не можетпревышать величины п — к + 1. •Определение. Любой код с минимальным расстоянием, удовлетворяющим равенствуdmin = П — к + 1называется кодом с максимальным расстоянием.Определение. Код, который может быть приведен к систематическому виду путем операций, не изменяющих дистанционный профиль кодовых слов, называется разделимым.Так как линейный код может быть приведен к систематическому виду элементарными преобразованиями порождающей матрицы, любой линейный код является разделимым.Определение.
Разделимый код с максимальным расстоянием называется МДР кодом (разделимым кодом с максимальным расстоянием).Теперь вернемся к кодам Рида - Соломона.Определение. Кодом Рида Соломона называется линейный циклический (п,п- d+ 1)-код над GF(q), где q = рт, длины п = q - 1,порождающий многочлен которого д(Х) имеет своими корнями d — 1последовательных степеней примитивного элемента а из поля GF(q).Глава 5. Дискретные преобразования Фурье и коды PCВ качестве порождающего многочлена кода Ридавыбрать, напримерд(Х) = (Х- а){Х -а2)---(Х-Соломона можноа"-1).Замечание. Так как мы ограничиваемся только полями характеристики 2, то будем в дальнейшем вместо операций вычитанияиспользовать операцию сложения.В теории помехоустойчивого кодирования доказывается, что свойства (п, &)-кода Рида Соломона с символами из GF(q) и параметрами п — q — I, k = п — d + 1 не зависят от метода его построенияи определяются только выбранными значениями q и d.
Наиболеепросто код Рида - Соломона, а так же алгоритм его декодирования реализуется на основе дискретных преобразований Фурье, рассмотренных нами в предыдущем разделе. Процедуры кодированияи декодирования такого кода могут быть значительно ускорены спомощью техники быстрых преобразований Фурье (БПФ).Выберем и зафиксируем некоторое поле Галуа GF(q) с q = 2 m ,примитивный элемент а £ GF(q) и параметр d. Рассмотрим информационный вектор и = (мо, ui,..., Wfc-i) длины к = п — d+ I = q — d скомпонентами из GF(q). Поставим в соответствие вектору и вектордлины п = q - 1, у которого первые к компонент совпадают с компонентами вектора и, а остальные компоненты - нулевые. Рассмотримпрямое преобразование Фурье вектора v в вектор V, определяемое(5.1) и удовлетворяющее теореме 5.2.1.
Тогда справедлива следующая теорема:Теорема 5.3.2. Множество q векторов V в частотной области образует (п, к)-код Рида Соломона.Доказательство. Представим векторы v и V в виде многочленовv(X) =vo + v1X--- + vk-iXk-1+ 0 • Xk + 0 • Xk+1+ • • • + 0 • Хп~1Так как г-ые временные компоненты вектора v равны нулю прик < г < п — 1, то, согласно теореме 5.2, многочлен V(X) имеет корниa~k = ad~l, a~(fc+1> = ad~2,... ,а~(п~1'> = а. Таким образом, много-5.4- Декодирование кодов Рида - Соломона 275Jчлены V(X) образуют (п, к)-код Рида - Соломона с порождающиммногочленомд(Х) = {Х + а){Х + а2) • • • (XСпектральный подход позволяет легко доказать следующую теорему.Теорема 5.3.3. Любой код Рида - Соломона является МДР кодом.Доказательство. Так как код Рида - Соломона является линейным, <imin равно минимальному весу кодового слова.
Любое кодовоеслово V = (Vo, Vi,.. .Vj,.. •, Ki-i) является прямым преобразованием Фурье некоторого вектораn-kВ силу теоремы 5.2.2, j'-ая частотная компонента равна нулю тогдаи только тогда, когда а? является корнем многочлена v(X) = VQ +v\X +h Vfc-iX*-1. Согласно основной теореме алгебры, котораясправедлива и для конечных полей Галуа, многочлен v(X) степениА; —1 может иметь в поле GF(q) не более А; —1 корней. Следовательно,вес любого слова (п, к)-код& Рида - Соломона не может быть меньше,чем п—(к— 1) = п—к+1 и, в силу границы Синглтона d m j n = п—к+1,то есть код обладает максимальным расстоянием. Так как коды Рида- Соломона линейны, они являются МДР кодами.
•Спектральный подход позволяет также достаточно просто интерпретировать процедуру декодирования кодов Рида - Соломона.5.4. Декодирование кодов Рида - СоломонаНе трудно заметить, что при образовании кодов Рида - Соломонаинформационные символы можно размещать в любых к рядом стоящих разрядах вектора v. Из методических соображений отведем подинформацию старшие компоненты V. В этом случае многочлен v(X)будет иметь, видv(X) = Vn-iXn-l+vn-2Xn~2+-• •+vn^kX"-k+0-Xn-k~1+-• -+0-Х0,а порождающий многочлен соответствующего крда Рида - Соломонаимеет видд{Х) = (Х + ак+1)(Х+ ак+2)• • • (X + а").Глава 5.
Дискретные преобразования Фурье и коды PCКак уже отмечалось ранее, слова рассматриваемого кода Рида Соломона являются прямым преобразованием Фурье множества векторов V, то есть v т± V. В канале кодовому слову V добавляетсявектор ошибки Е кратности I < d — \.Рассмотрим обратное преобразование Фурье принятого из каналасловаR = V + Е,(5.8)В силу свойства линейности обратного преобразования Фурье имеем(« n _i +e n _i,...,w n _fc + en_fc,en_fc_i,en_ifc_2,...,eo) ^ V + Е, (5.9)где v = (vn-k,vn-k-\,• • • ,vn-\) - информационный вектор, лежащийво временной области, е = (eo,ei,...
,e n _i) - обратное преобразование вектора ошибок. Так как п — к правых компонент вектора обратного преобразования Фурье от V + E не зависят от кодового слова V,эти компоненты образуют синдром ошибок. Запишем этот синдромв видеS d - 2 , S d - l , - - . ,Si,S0,(5.10)где so = eo,Si = e i , . . . ,Sd-2 = en_fc_i. Заметим, что Синдром является некоторым «окном», через которое можно наблюдать обратноепреоразование Фурье вектора ошибки Е.Обозначим индексы I ненулевых компонент вектора Е черезJitJ2, • • • ,ji- Определим вектор во временной области, прямое преобразование Фурье которого содержит нулевые компоненты для всехчастот j, для которых Ej ф 0. Проще всего такой вектор задать ввиде многочлена локаторов ошибок... + atXl.(5.11)Покомпонентное произведение прямого преобразования Фурье отмногочлена сг(Х) на вектор ошибки Е в частотной области равно нулю, следовательно циклическая свертка во временной областивектора а с векторм е также равна нулю'<г*е = О.(5.12)Из (5.9) и (5.10) следует, что для определения компонент (Ti,<T2, • • • ,<ri5.4- Декодированиекодов РидаСоломона(согласно (5.11) <т0 = 1), используя (5.12), мы можем составить систему d — 1 — I линейных уравнений с 2 неизвестными<TiS;_i + .
. . + ffiso = О= 0(5.13)-2-l= 0.Сложность, возникающая при решении системы уравнений (5.13) состоит в том, что кратность ошибки I нам заранее не известна. Такимобразом, в процессе решения должна еще осуществляться и минимизация значения /, при котором возможно выполнение всех d — 1 — /уравнений из (5.13). Такой простой и эффективный алгоритм былнайден Берлекэмиом в 1967 г. Без преувеличения молено сказать, чтоэтот алгоритм произвел настоящую революцию в теории и практикепомехоустойчивого кодирования. Он будет рассмотрен в следующемразделе этой главы.Предположим, что все коэффициенты многочлена а{Х) определены. В этом случае остальные к компонент вектора е, то есть компоненты еп-к, e n _fc+i,..., e n _i во временной области, могут быть рекурентно определены, исходя из (5.12).Для определения компоненты e^-i нам достаточно решить уравнениеd_i_j= 0относительно e^-i, так как все остальные компоненты уже определены.На'втором шаге мы уже можем составить уравнение для определения efc_2- Это уравнение имеет видa o e n _ f c + i + О\еп-к+ <?2Sd-2+ ••• + <?iSd-l= 0.Рекурентно продолжая описанную процедуру, мы найдем все оставшихся компоненты вектора е.Для определения информационного вектора v нам достаточно вычесть найденные компоненты en_fc,en_fc+i,...
,e n _i из полученных обратным преобразованием Фурье от R значений vn-k +en-k,vn-k+i +e n _fc+i,... ,vn-i + e n _ i .Самое замечательное в рассмотренном алгоритме состоит в том,что при его реализации не приходится находить ни корни многочленаа(Х) (локаторы ошибок), ни значения ошибок.Теперь общая картина процедуры декодирования ясна и ее можносформулировать в виде пяти шагов.i 278Глава 5. Дискретные преобразования Фурье и коды PCШаг 1. Вычислить обратное преобразование Фурье принятого вектора R = V + Е. Выделить SQ, . .
. , s^-2 во временной областии зангумлениые компоненты информационного вектора v;Шаг 2. Найти а(Х) из (5.13);Шаг 3. С помощью рекурентной процедуры вычислить компоненты e n _ f c ,e n _fc + b ..., e n _i;Шаг 4. Найти информационный вектор v;Замечание. Рассмотренный алгоритм всегда исправляет \^jr\ uменее ошибок. В следующем разделе будет рассмотрен также случай, когда число канальных ошибок превышает L^pJ •Для контроля правильности декодирования часто проводитсяследующий шаг.Шаг 5. Вычислить прямое преобразование Фурье вектора v, получив при этом кодовай вектор V (не всегда совнадаяющий с V).5.5.
Итеративный алгоритм для нахождения а(Х)Будем руководствоваться блок-схемой алгоритма, приведенной нарис. 5.1 ([10] стр. 271). Отметим, что эта блок-схема содержит всюнеобходимую информацию для программной или схемной реализации алгоритма. Если число ошибок не превышает величины [^pj> т 0алгоритм находит многочлен о~(Х) минимальной степени I, при котором выполняется система уравнений (5.13). Доказательству этогофакта в [10] посвящено несколько довольно сложных теорем и заинтересованному читателю мы советуем обратится к [10].
Ограничимсяописанием основных принципов работы алгоритма.В работе алгоритма используются три регистра. В регистре динамических связей fti на каждом такте декодирования содержится очередное итеративное значение ап(Х). Компоненты многочленао-п(Х) на n-ом такте декодирования С п д, С„,2, • • •, Cnj, где j - степень многочлена.Рассмотрим процесс вычисления сгп(Х) более подробно. В регистр сдвига Дг последовательно, на каждом такте декодирования5.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
