Турбокоды: Высокоэффективные коды коррекции ошибок

Введение

Высокопроизводительные коды прямой коррекции ошибок

В теории информации коды турбо (первоначально Turbocodes на французском языке) представляют собой класс высокопроизводительных кодов прямой коррекции ошибок (FEC), разработанных примерно в 1990–1991 годах, но впервые опубликованных в 1993 году. Они стали первыми практическими кодами, которые близко приблизились к максимальной пропускной способности канала или пределу Шеннона – теоретическому максимуму скорости передачи данных, при котором возможна надежная связь при заданном уровне шума. Коды турбо используются в мобильной связи 3G/4G (например, в UMTS и LTE) и в спутниковой связи (в том числе для связи в дальнем космосе), а также в других приложениях, где разработчики стремятся обеспечить надежную передачу информации по каналам связи с ограниченной пропускной способностью или задержкой в условиях наличия шума, вызывающего искажение данных. Коды турбо конкурируют с кодами с низкой плотностью проверки на четность (LDPC), которые обеспечивают сопоставимую производительность (но не запатентованы). Название "турбокод" возникло из-за контура обратной связи, используемого при обычном декодировании турбокода, который был аналогичен обратной связи выхлопных газов, применяемой для турбонаддува двигателей. Хагенауэр утверждает, что термин "турбокод" является неточным, поскольку обратной связи в процессе кодирования нет.

История

Основная заявка на патент для турбо-кодов была подана 23 апреля 1991 года. В патентной заявке Клод Берру указан как единственный изобретатель турбо-кодов. Подача патентной заявки привела к выдаче нескольких патентов, включая патент США № 5 446 747, срок действия которого истек 29 августа 2013 года. Первая публичная статья о турбо-кодах называлась "Near Shannon Limit Error correcting Coding and Decoding: Turbo codes" ("Кодирование и декодирование с исправлением ошибок близко к пределу Шеннона: турбо-коды"). Эта статья была опубликована в 1993 году в Proceedings of IEEE International Communications Conference. Статья 1993 года была сформирована из трех отдельных представленных материалов, объединенных из-за ограничений по объему. В результате объединения авторами статьи стали: Берру, Главье и Титимаджима (из Télécom Bretagne, бывшая ENST Bretagne, Франция). Однако из первоначальной патентной заявки ясно, что Берру является единственным изобретателем турбо-кодов, а другие авторы статьи внесли вклад в материалы, отличные от основных концепций. Турбо-коды были настолько революционными в момент их появления, что многие эксперты в области кодирования не поверили в заявленные результаты. После подтверждения производительности произошла небольшая революция в мире кодирования, которая привела к исследованию многих других типов итеративной обработки сигналов. Первым классом турбо-кодов был параллельно-конкатенированный сверточный код (PCCC). С момента представления оригинальных параллельных турбо-кодов в 1993 году было открыто множество других классов турбо-кодов, включая последовательные версии, последовательно-конкатенированные сверточные коды и коды повторения и накопления. Итеративные методы декодирования турбо-кодов также применялись к более традиционным системам FEC, включая сверточные коды с коррекцией ошибок Рида — Соломона, хотя эти системы слишком сложны для практической реализации итеративных декодеров. Турбо-эквалайзер также возник на основе концепции турбо-кодирования. Помимо турбо-кодов, Берру также изобрел рекурсивные систематические сверточные (RSC) коды, которые используются в примере реализации турбо-кодов, описанном в патенте. Турбо-коды, использующие RSC-коды, показывают лучшую производительность, чем турбо-коды, не использующие RSC-коды. До появления турбо-кодов лучшими конструкциями были последовательно-конкатенированные коды, основанные на внешнем коде коррекции ошибок Рида — Соломона в сочетании с внутренним сверточным кодом с коротким ограничением длины, декодированным алгоритмом Витерби, также известным как коды RSV. В более поздней статье Берру отдал должное интуиции "Г. Баттайля, Дж. Хагенауэра и П. Хёэра, которые в конце 80-х годов подчеркнули интерес к вероятностной обработке". Он добавляет, что "Р. Галлагер и М. Таннер уже представили методы кодирования и декодирования, общие принципы которых тесно связаны", хотя необходимые вычисления в то время были непрактичными.

The fundamental patent application for turbo codes was filed on 23 April 1991. The patent application lists Claude Berrou as the sole inventor of turbo codes. The patent filing resulted in several patents including US Patent 5,446,747, which expired 29 August 2013. The first public paper on turbo codes was "Near Shannon Limit Error correcting Coding and Decoding: Turbo codes". This paper was published 1993 in the Proceedings of IEEE International Communications Conference. The 1993 paper was formed from three separate submissions that were combined due to space constraints. The merger caused the paper to list three authors: Berrou, Glavieux, and Thitimajshima (from Télécom Bretagne, former ENST Bretagne, France). However, it is clear from the original patent filing that Berrou is the sole inventor of turbo codes and that the other authors of the paper contributed material other than the core concepts. Turbo codes were so revolutionary at the time of their introduction that many experts in the field of coding did not believe the reported results. When the performance was confirmed a small revolution in the world of coding took place that led to the investigation of many other types of iterative signal processing. The first class of turbo code was the parallel concatenated convolutional code (PCCC). Since the introduction of the original parallel turbo codes in 1993, many other classes of turbo code have been discovered, including serial versions serial concatenated convolutional codes and repeat accumulate codes. Iterative turbo decoding methods have also been applied to more conventional FEC systems, including Reed–Solomon corrected convolutional codes, although these systems are too complex for practical implementations of iterative decoders. Turbo equalization also flowed from the concept of turbo coding. In addition to turbo codes, Berrou also invented recursive systematic convolutional (RSC) codes, which are used in the example implementation of turbo codes described in the patent. Turbo codes that use RSC codes seem to perform better than turbo codes that do not use RSC codes. Prior to turbo codes, the best constructions were serial concatenated codes based on an outer Reed–Solomon error correction code combined with an inner Viterbi decoded short constraint length convolutional code, also known as RSV codes. In a later paper, Berrou gave credit to the intuition of "G. Battail, J. Hagenauer and P. Hoeher, who, in the late 80s, highlighted the interest of probabilistic processing." He adds "R. Gallager and M. Tanner had already imagined coding and decoding techniques whose general principles are closely related," although the necessary calculations were impractical at that time.

Решение гипотез для поиска битов

Ключевое нововведение турбокодов заключается в том, как они используют данные о правдоподобии для согласования расхождений между двумя декодерами. Каждый из двух свёрточных декодеров генерирует гипотезу (с вычисленными правдоподобиями) для последовательности из m бит в подблоке полезной нагрузки. Битовые шаблоны гипотез сравниваются, и если они различаются, декодеры обмениваются вычисленными правдоподобиями для каждого бита в этих гипотезах. Каждый декодер учитывает оценки правдоподобия, полученные от другого декодера, чтобы сформировать новую гипотезу для битов полезной нагрузки. Затем они сравнивают эти новые гипотезы. Этот итеративный процесс продолжается до тех пор, пока оба декодера не придут к одной и той же гипотезе для m-битной последовательности полезной нагрузки, обычно за 15-18 циклов. Можно провести аналогию между этим процессом и решением задач, требующих перекрёстной проверки, таких как кроссворды или судоку. Представьте частично заполненную, возможно, искажённую кроссвордную головоломку. Два решателя (декодера) пытаются её решить: один располагает только подсказками по вертикали (битами чётности), а другой – только подсказками по горизонтали. Для начала оба решателя предполагают ответы (гипотезы) на свои подсказки, отмечая степень уверенности в каждой букве (бите полезной нагрузки). Затем они обмениваются информацией, делясь ответами и оценками уверенности, обращая внимание на различия. На основе этих новых данных они оба формируют обновлённые ответы и оценки уверенности, повторяя процесс до тех пор, пока не сойдутся на одном решении.

Выступление

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

Байесовская формулировка

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