Вернер М. Основы кодирования (2004), страница 40

Итеративный алгоритм для нахождения а{Х)Статическийрегистр Я ,Регистрсдвига Я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. Lin, D. J. Costello: Error control coding: Fundamentals andApplications, Englewood Cliffs, NJ,: Prentice- Hall Inc., 1983[8] F. J. MacWilliams, N.

J. Sloane: The Theory of Error-Correcting jCodes. Amsterdam: North-Holland, 1977, (Имеется перевод: МакВильямс Ф. Д ж . , Слоэн Н. Д ж . А. Теория кодов исправляющихошибки. -М.: Связь, 1979)[9] N. Wiener: Cybernetics or Control and Communication in theAnimal and the Mashine. Paris: Hermann, 1948V282Литература[10] R.

G. Gallager: Information Theory and Reliable Communication.New York: John Willey and Sons Inc. 1968, (Имеется перевод: Галагер Р. Теория информации и надежная связь.-М.: Сов. радио,1974)[11] W. W. Peterson, E. J. Weldon: Error- Correcting Codes. 2nd ed.-Cambrige (Mass.): MIT Press, 1971 (Имеется перевод: ПитерсенУ., Уэлдон Э.

Коды, исправляющие ошибки. -М.: Мир, 1976)[12] G. Ungerbock: Channel Coding with Multilevel/phase Signals.IEEE Trans. Inform. Theory, IT-28,1982, S.55-67.[13] J. G.Proakis: Digital Communications. New York: McGraw-Hill,2000.Литература, добавленная при переводе[14] I. Chisar, J. Кёгпег: Information theory, Coding theorems for discrete memory less systems.

Akademiai Budapest, 1981 (Имеетсяперевод: Чисар И., Кернер Я. Теория информации, теоремыкодирования для дискретных систем без памяти. -М.: Мир,1985)[15] W. Feller: An introduction to probabilistic theory and its application. John Willey & Sons, NY, 1970 (Имеется перевод: ФеллерВ. Введение в теорию вероятностей и ее приложения. -М.: Мир,1984)[16] J. M.

Wozencraft, I. Jacobs: Principles of communication engineering. John Willey & Sons, NY, 1965 (Имеется перевод:Возенкрафт Дж., Джекобе И. Теоретические основы техникисвязи. -М.: Мир, 1969)[17] J. J. Stiffler: Theory of synchronous communications. NJ: Prentice Hall Inc., 1971, (Имеется перевод: Стиффлер Дж. Теориясинхронной связи. -М.: Связь, 1978)[18] G.

С. Klark, J. В. Cain: Error correction coding for digital communication, Plenum press, 1982 (Имеется перевод: Кларк Дж., КейнДж. Кодирование с исправлением ошибок в системах цифровойсвязи. -М.: Радио и связь, 1987)[19] Д. Сэломон: Практическое руководство по методам сжатияданных. М.: Техносфера, 2003[20] Е. R. Berlekamp: Algebraic Coding Theory. NY, McGraw-Hill, 1968(Имеется перевод: Берлекэмп Э. Алгебраическая теория кодирования. -М.: Мир, 1971)[21] G.

D. Jr. Forney: Concatenated Codes, Cambrige, Mass., MHTPress,1963 (Имеется перевод: Форни Д. Каскадные коды. -М.:Мир, 1970)Предметный указательАБГШ, 115Алгоритм Витерби, 245деления Евклида, 171Алфавит, 12Аналоговый источник, 44Апостериорная вероятность, 36Арифметическое кодированиие, 77Векторное пространство, 138,141Вероятностьнеобнаружимойошибки, 145ошибки, 128Взаимная информация, 36Витерби алгоритм, 245Входные последовательности,221Выходные последовательности,221Гауссовское распределение, 113Гомогенная цепь Маркова, 52,53, 55Граница Хэмминга. 145Шеннона, 117Двоичный симметричный канал (ДСК), 85Декодер Меггитта, 193максимального правдоподобия, 248с вылавливанием ошибок, 198Диаграмма канала, 95Дискретный во времени стохастический процесс, 44источник, 44источник без памяти, 12источник с памятью, 44Длина кодового ограничения,224кодового слова, средняя, 32Избыточность, 20, 75Избыточность относительная,20Импульсный отклик, 221Информационнаяпоследовательность, 221Информационное слово, 131Информационные символы, 135Информация, 15, 111несущественная, 75Код CRC, 198Абрамсона, 198Голлея, 198Файера, 200Хэмминга, 148Хэмминга циклический, 196без запятой, 29дуальный, 175катастрофический, 241линейный двоичный блоковый, 133префиксный, 24, 25систематический, 134, 243циклический, 163циклическийукороченный,200Кода скорость, 224Кодер, 133Предметный указательКодирование Хаффмана, 68, 76арифметическое, 77избыточное j 133источника, 68энтропийное, 77Кодоваяпоследовательность,221Кодовое слово, 131, 134, 163Кодовый многочлен, 165Колмогорова - Чэпмена уравнение, 51Корректирующая способность,144Крафта неравенство, 25Память, 58кодера, 224Переходные вероятности, 50Порождающая матрица, 134,172Порождающий многочлен, 167Последовательное декодирование, 245Предельная матрица, 55Префиксный код, 29Принятое слово, 132Проверочные символы, 135Пропускная способность, 100,115Лагранжа метод, 100Логарифмическаяфункцияправдоподобия, 249Распределение предельное, 55стационарное, 55Расстояние Хэмминга, 143Расширенный код Хэмминга,152Регистр сдвига, 163Мак-Миллана утверждение, 26Марковский источник, 58стационарный, 62процесс, 51Математическое-ожидание, 16Матрица переходных вероятностей, 52порождающая, 138проверочная, 138, 175Метрика, 249Минимальное кодовое расстояние, 143Многочлен кодовый, 226неприводимый, 158, 196порождающий ,225примитивный, 1598, 196Невозможное событие, 15Неопределенность, 12Ошибка декодирования, 132Ошибки необнаружимые, 140Свободное расстояние, 240Сжатие данных, 75Синдром, 136, 184Скорость кода, 133Случайные события, 12Собственный вектор, 54Совершенные коды, 144Совместная энтропия, 38, 45Состояние, 50Спектральная плотность мощности, 118Стационарная цепь Маркова,54Стационарный источник, 45Степень сжатия, 76Стохастическая матрица, 52Предметный указательТеорема Шеннона, 108кодирования, 48, 108кодирования источников, 67Условная информация, 37Условная энтропия, 39, 46Фактор сжатия, 32Цепь Маркова регулярная, 55,56Циклический сдвиг, 163Энергетический выигрыштда, 148Энергия, 118' Энтропия, 6, 15, 16, 62, 99,двоичного источника, 21дифференциальная, 112Эргодичность, 16Эффективность кода, 32.,.