WikiDer > Турбо код
В теория информации, турбокоды (первоначально на французском Турбокоды) являются классом высокопроизводительных упреждающее исправление ошибок (FEC) коды, разработанные в период с 1990 по 1991 год, но впервые опубликованные в 1993 году. Они были первыми практическими кодами, которые приблизились к максимальной пропускной способности канала или Предел Шеннона, теоретический максимум для кодовая скорость при котором надежная связь все еще возможна при определенном уровне шума. Турбокоды используются в 3G/4G мобильная связь (например, в UMTS и LTE) И в (Глубокий космос) спутник коммуникации а также другие приложения, в которых разработчики стремятся обеспечить надежную передачу информации по каналам связи с ограниченной полосой пропускания или задержкой при наличии искажающего данные шума. Турбо-коды конкурируют с Коды LDPC («проверка четности с низкой плотностью»), которые обеспечивают аналогичную производительность.
Название «турбо-код» возникло из-за контура обратной связи, используемого во время обычного декодирования турбокода, который был аналогичен обратной связи выхлопных газов, используемой для двигателя. турбонаддув. Hagenauer утверждал, что термин турбо-код является неправильным, поскольку в процессе кодирования нет обратной связи.[1]
История
Заявка на фундаментальный патент на турбокоды была подана 23 апреля 1991 г. В патентной заявке перечислены Клод Берру как единственный изобретатель турбокодов. Подача патента привела к получению нескольких патентов, в том числе Патент США 5,446,747, срок действия которого истек 29 августа 2013 года.
Первой публичной статьей по турбо-кодам была "Кодирование и декодирование с исправлением ошибок, близкое к пределу Шеннона: турбо-коды".[2] Этот документ был опубликован в 1993 г. в материалах Международной конференции по коммуникациям IEEE. Документ 1993 года был сформирован из трех отдельных документов, которые были объединены из-за нехватки места. В результате слияния газета перечислила трех авторов: Берроу, Glavieux, и Thitimajshima (от Télécom Bretagne, бывшего ENST Бретань, Франция). Однако из первоначальной заявки на патент ясно, что Берроу является единственным изобретателем турбо-кодов и что другие авторы статьи предоставили материал, отличный от основных концепций.
Турбокоды были настолько революционными на момент своего появления, что многие эксперты в области кодирования не поверили полученным результатам. Когда производительность была подтверждена, в мире кодирования произошла небольшая революция, которая привела к исследованию многих других типов итеративной обработки сигналов.
Первым классом турбокода был параллельный каскадный сверточный код (PCCC). С момента появления оригинальных параллельных турбокодов в 1993 году было обнаружено множество других классов турбокодов, включая серийные версии. последовательные конкатенированные сверточные коды и коды повторного накопления. Методы итеративного турбодекодирования также применялись к более традиционным системам FEC, включая сверточные коды с коррекцией Рида-Соломона, хотя эти системы слишком сложны для практической реализации итерационных декодеров. Турбо-эквализация также вытекала из концепции турбо-кодирования.
В дополнение к турбокодам Берроу также изобрел рекурсивные систематические сверточные коды (RSC), которые используются в примерной реализации турбокодов, описанных в патенте. Турбокоды, которые используют коды RSC, кажутся более эффективными, чем турбокоды, которые не используют коды RSC.
До турбокодов лучшие конструкции были серийными. составные коды на основе внешнего Исправление ошибок Рида-Соломона код в сочетании с внутренним Витерби-декодированный короткая длина ограничения сверточный код, также известные как коды RSV.
В более поздней статье Берроу отнесся к интуиции «Дж. Баттейла, Дж. Хагенауэр и П. Хоэхер, который в конце 80-х подчеркнул интерес к вероятностной обработке. "Он добавляет".Р. Галлагер и М. Таннер уже придумал методы кодирования и декодирования, общие принципы которых тесно связаны, «хотя необходимые вычисления в то время были непрактичными.[3]
Пример кодировщика
Существует множество различных экземпляров турбокодов, использующих различные кодирующие компоненты, соотношения ввода / вывода, перемежители и шаблоны прокалывания. Этот пример реализации кодера описывает классический турбокодер и демонстрирует общую конструкцию параллельных турбокодов.
Эта реализация кодировщика отправляет три подблока битов. Первый подблок - это м-битовый блок данных полезной нагрузки. Второй подблок п / 2 биты четности для данных полезной нагрузки, вычисленные с использованием рекурсивного систематического сверточный код (Код RSC). Третий подблок - п / 2 биты четности для известного перестановка данных полезной нагрузки, снова вычисленных с использованием кода RSC. Таким образом, с полезной нагрузкой отправляются два избыточных, но разных подблока битов четности. Полный блок имеет м + п биты данных с кодовой скоростью м/(м + п). В перестановка данных полезной нагрузки выполняется устройством, называемым перемежитель.
Аппаратно этот турбокодер состоит из двух одинаковых кодеров RSC, С1 и C2, как показано на рисунке, которые соединены друг с другом с помощью схемы конкатенации, называемые параллельная конкатенация:
На рисунке M это регистр памяти. Входные биты линии задержки и силы перемежителя dk появляться в разных последовательностях. На первой итерации входная последовательность dk появляется на обоих выходах энкодера, Иксk и у1к или же у2k из-за систематичности кодировщика. Если кодировщики C1 и C2 используются в п1 и п2 итераций, их скорости соответственно равны
Декодер
Декодер построен аналогично вышеуказанному кодировщику. Два элементарных декодера соединены между собой, но последовательно, а не параллельно. В декодер работает на более низкой скорости (т.е. ), таким образом, он предназначен для кодировщик и это для соответственно. дает мягкое решение что приводит к задерживать. Такая же задержка вызвана линией задержки в кодировщике. В причины операции задерживать.
Перемежитель, установленный между двумя декодерами, используется здесь для рассеивания пакетов ошибок, исходящих от выход. DI block - это модуль демультиплексирования и вставки. Он работает как переключатель, перенаправляя входные биты на в один момент и чтобы в другом. В выключенном состоянии он питает оба и входы с битами заполнения (нулями).
Считайте без памяти AWGN канал, и предположим, что при k-й итерации декодер получает пару случайных величин:
куда и независимые компоненты шума, имеющие одинаковую дисперсию . это k-й бит от выход энкодера.
Избыточная информация демультиплексируется и отправляется через DI к (когда ) и (когда ).
дает мягкое решение; то есть:
и доставляет его . называется логарифм отношения правдоподобия (LLR). это апостериорная вероятность (APP) бит данных, который показывает вероятность интерпретации полученного немного как . Принимая LLR в учетную запись, дает трудное решение; то есть декодированный бит.
Известно, что Алгоритм Витерби не может рассчитать приложение, поэтому его нельзя использовать в . Вместо этого модифицированный Алгоритм BCJR используется. За , то Алгоритм Витерби подходящий.
Однако изображенная структура не является оптимальной, поскольку использует только надлежащую часть доступной избыточной информации. Для улучшения конструкции используется петля обратной связи (см. Пунктирную линию на рисунке).
Подход мягких решений
Интерфейс декодера выдает целое число для каждого бита в потоке данных. Это целое число является мерой того, насколько вероятно, что бит равен 0 или 1, и также называется мягкий бит. Целое число может быть взято из диапазона [-127, 127], где:
- −127 означает «конечно 0»
- −100 означает «очень вероятно 0»
- 0 означает «это может быть либо 0, либо 1»
- 100 означает "очень вероятно 1"
- 127 означает "конечно 1"
Это вводит вероятностный аспект в поток данных от внешнего интерфейса, но он передает больше информации о каждом бите, чем просто 0 или 1.
Например, для каждого бита внешний интерфейс традиционного беспроводного приемника должен решить, находится ли внутреннее аналоговое напряжение выше или ниже заданного порогового уровня напряжения. Для декодера турбокода внешний интерфейс будет обеспечивать целочисленную меру того, насколько далеко внутреннее напряжение от заданного порога.
Чтобы расшифровать м + п-битовый блок данных, интерфейс декодера создает блок мер правдоподобия с одной мерой правдоподобия для каждого бита в потоке данных. Есть два параллельных декодера, по одному для каждого изп⁄2субблоки -битной четности. Оба декодера используют подблок м вероятности для данных полезной нагрузки. Декодер, работающий над вторым субблоком четности, знает перестановку, которую кодер использовал для этого субблока.
Решение гипотез для поиска битов
Ключевым нововведением турбокодов является то, как они используют данные вероятности для согласования различий между двумя декодерами. Каждый из двух сверточных декодеров генерирует гипотезу (с производными вероятностями) для шаблона м биты в подблоке полезной нагрузки. Битовые комбинации гипотез сравниваются, и, если они отличаются, декодеры обмениваются полученными вероятностями, которые они имеют для каждого бита в гипотезах. Каждый декодер включает в себя оценки правдоподобия, полученные от другого декодера, чтобы сформировать новую гипотезу для битов в полезной нагрузке. Затем они сравнивают эти новые гипотезы. Этот итеративный процесс продолжается до тех пор, пока два декодера не придут к одной и той же гипотезе для м-битовый шаблон полезной нагрузки, обычно от 15 до 18 циклов.
Можно провести аналогию между этим процессом и решением таких головоломок, как кроссворд или же судоку. Рассмотрим частично завершенный, возможно, искаженный кроссворд. Два решателя головоломки (декодера) пытаются решить эту задачу: у одного есть только «нисходящие» ключи (биты четности), а у другого - только «поперечные» ключи. Для начала оба решателя угадывают ответы (гипотезы) на свои подсказки, отмечая, насколько они уверены в каждой букве (бит полезной нагрузки). Затем они сравнивают записи, обмениваясь ответами и рейтингами доверия друг с другом, замечая, где и чем они отличаются. Основываясь на этих новых знаниях, они оба придумывают обновленные ответы и рейтинги уверенности, повторяя весь процесс, пока не придут к одному и тому же решению.
Спектакль
Турбокоды работают хорошо благодаря привлекательной комбинации случайного появления кода в канале вместе с физически реализуемой структурой декодирования. На турбо-коды влияет этаж ошибок.
Практические приложения с использованием турбокодов
Телекоммуникации:
- Турбокоды широко используются в 3G и 4G стандарты мобильной телефонии; например, в HSPA, EV-DO и LTE.
- MediaFLO, система наземного мобильного телевидения от Qualcomm.
- В канал взаимодействия из спутниковая связь системы, такие как DVB-RCS[4] и DVB-RCS2.
- Недавний НАСА миссии, такие как Марсианский разведывательный орбитальный аппарат использовать турбо-коды как альтернативу RS-Витерби коды.
- IEEE 802.16 (WiMAX), стандарт беспроводной городской сети, использует блочное турбо-кодирование и сверточное турбо-кодирование.
Байесовская формулировка
Из искусственный интеллект точки зрения, турбокоды можно рассматривать как пример зацикленного распространение веры в Байесовские сети.[5]
Смотрите также
- Сверточный код
- Алгоритм Витерби
- Декодирование с мягким решением
- Перемежитель
- Алгоритм BCJR
- Код проверки на четность с низкой плотностью
- Последовательные каскадные сверточные коды
- Турбо эквалайзер
- Прямое исправление ошибок
Рекомендации
- ^ Иоахим Хагенауэр, Иоахим; и другие. «Итеративное декодирование двоичного блока и сверточных кодов» (PDF). Архивировано из оригинал (PDF) 11 июня 2013 г.. Получено 20 марта 2014.
- ^ Берру, Клод; Главье, Ален; Thitimajshima, Punya, Ошибка предела Шеннона - исправление, получено 11 февраля 2010
- ^ Берру, Клод, Турбокоды десятилетней давности вводятся в эксплуатацию, Бретань, Франция, получено 11 февраля 2010
- ^ Цифровое видеовещание (DVB); Канал взаимодействия для спутниковых распределительных систем, ETSI EN 301 790, V1.5.1, май 2009 г.
- ^ МакЭлис, Роберт Дж.; Маккей, Дэвид Дж. С.; Ченг, Чжун-фу (1998), "Турбо-декодирование как пример алгоритма" распространения убеждений "Перла" (PDF), Журнал IEEE по избранным областям коммуникаций, 16 (2): 140–152, Дои:10.1109/49.661103, ISSN 0733-8716.
внешняя ссылка
- "Завершение идеального кода", IEEE Spectrum, март 2004 г.
- «Турбо-код UMTS и эффективная реализация декодера, подходящая для программно-определяемых радиостанций» (Международный журнал беспроводных информационных сетей)
- Дана Маккензи (2005), «Доведи до предела», Новый ученый, 187 (2507): 38–41, ISSN 0262-4079. (предварительный просмотр, копировать)
- «Нажимая предел», а Новости науки статья о развитии и генезисе турбокодов
- Международный симпозиум по турбо-кодам
- Библиотека кодированной модуляции, библиотека с открытым исходным кодом для моделирования турбо-кодов в Matlab
- «Турбо-уравнение: принципы и новые результаты», Транзакции IEEE по коммуникациям статья об использовании сверточных кодов совместно с канальной коррекцией.
- Домашняя страница IT ++ В IT ++ это мощная библиотека C ++, которая, в частности, поддерживает турбо-коды
- Публикации турбо-кодов Дэвида Маккея
- Домашняя страница AFF3CT (A Fast Forward Error Correction Toolbox) для моделирования высокоскоростных турбо-кодов в программном обеспечении
- Турбо код доктора Сильви Керуэдан и Доктор Клод Берру (scholarpedia.org).
- Эталонный дизайн 3GPP LTE Turbo.
- Оцените производительность BER турбокода в AWGN (MatLab).
- Параллельное каскадное сверточное кодирование: турбо-коды (MatLab Simulink)
дальнейшее чтение
Публикации
- Баттейл, Жерар. «Концептуальная основа для понимания турбокодов». Журнал IEEE по избранным областям коммуникаций 16.2 (1998): 245–254.
- Брейза, Мэтью Ф. и др. «20 лет турбокодирования и принципов энергосбережения для беспроводных приложений с ограниченным энергопотреблением». IEEE Communications Surveys & Tutorials 18.1 (2016): 8–28.
- Гарсон-Бохоркес, Рональд, Шарбель Абдель Нур и Катрин Дуйяр. «Улучшение турбокодов для 5G с помощью перемежителей с ограничением четности». Турбокоды и итерационная обработка информации (МНТЦ), 9-й Международный симпозиум 2016 г. IEEE, 2016.