Вернер М. Основы кодирования (2004) (1151882), страница 39
Текст из файла (страница 39)
Любой код Рида - Соломона является МДР кодом.Доказательство. Так как код Рида - Соломона является линейным, <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.
Итеративный алгоритм для нахождения а{Х)Статическийрегистр Я ,Регистрсдвига Я2Регистрсдвига R3Замечания: при каждом я , Я, содержит С„ (X)за исключением C B j =1Rz содержит Ы0010Я 3 содержит FfX)=X°" k "C k i | WFo = Оrf*- злемент памяти,содержащий dk^Функции управления00 . . . 0J00 • • • 010 • • • 0о -*-«;оя,«2*3/»;• -/„ * I -»- /•Поменять местамисодержимое Л , и J f 3Умножить Л , на --^J 1 Прибавить Я , к Я , исумму поместить в Л {Сдвинуть вправо Я 3 ,поместив 1 в крайнийлевый разрядПрибавитьраз R3 К Я,и результатпоместить в IСдвинуть JвправоСдвинуть Л 2вправои в негоподать $„+(я+1 - ^ - лР и с . 5.1. Алгоритм БерлекэмпаМесси [10].Глава 5.
Дискретные преобразования Фурье и коды PCподаются компоненты синдрома .so, s\,..., s<j-2- Пусть ln - итеративная длина регистра R\ на такте п, тогда на этом же такте на выходевычисляетсяdn = C"n,i.sin 4- C n , 2 s (n _i H+ Cnii,s-0и декодер стремится так скорректировать ап(Х), чтобы реализоватьпервое уравнение из системы (5.13).
Далее декодер добивается выполнения второго уравнения из (5.13) при сохранении первого и т.д.Оказывается, что процесс коррекции можно начинать прямо с первого такта, то есть с CLQ = SQ. В результате мы получим а(Х) минимальной степени, при котором выполняются все уравнения из (5.13).Контроль правильности всего процесса декодирования происходит на пятом шаге декодирования. Пусть на этом шаге вычисленкодовый вектор V . Сравнивая V с R = V + Е можно найти число исправлений. Если в канале произошло не более [^j^-J ошибок, точисло исправлений должно совпадать со степенью многочлена <г{Х).Если число канальных ошибок превышает L^i^Ji T O может произойти одно из трех событий.
Во-первых, степень многочлена о~(Х)может оказаться выше [^y^J. Тогда процесс декодирования прерывается уже на втором этапе декодирования. Во-вторых, число исправлений может не совпадать со степенью а{Х), такая ошибка обнаруживается в конце декодирования. И, наконец, вполне возможно,что число исправлений совпадает со степенью о(Х) и не превышаетL~3pJ- Здесь имеет место необнаружимая ошибка декодирования.Заметим, что для реализации этого алгоритма требуются незначительные технические затраты и в настоящее время декодеры кодовРида - Соломона работают на скоростях до 40 Гбит/сек.Литература[1] С.
Е. Shenon: A mathematical theory of communication Bell Sys.Tech. J., vol 27, 1948, S.379-423, (Имеется перевод: Шеннон К.Математическая теория связи.-В сб.: Работы по теории информации и кибернетики. -М.: ИЛ, 1963)[2] С. Berrou, A. Glavieux: "Near Optimum Error-Correcting Codingand Decoding: Turbo Codes."IEEE Trans. Commun. Vol. 44, 1996,S.1261-1270[3) C. Berrou, A. Glavieux, P.Thitimajshima: "Near Shannon LimitError-Correcting Coding and Decoding: Turbo Codes."Proc. IEEEInt. Conf. Commun., May 1993, S.
1064-1070[4) R. E. Blahut: Principles and practice of information theory, Reading,Mass.: Addison-Wesley Publishing Company,1987[5] R. E. Blahut: Principles and practice of error control coding,Addison-Wesley Publishing Company,1984 (Имеется перевод: Блейхут. Р. Теория и практика кодов, контролирующих ошибки.
-М.:Мир, 1986)[6] D. A. Huffman: "A method for the Construction of MinimumRedunduncy Codes."Proc. IRE, vol. 40,1952,S.1098-1101, (Имеется перевод: Хаффман Д . А. Методы построения кодов с минимальной избыточностью.-Кибернетический сб. вып. З.-М.: ИЛ,1961)[7] S.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
