Турбокод

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

Название «турбокод» возникло из-за контура обратной связи, используемого во время обычного декодирования турбокода, который был аналогичен обратной связи по выхлопным газам, используемой для турбонаддува двигателя . Хагенауэр утверждает, что термин «турбокод» является неправильным, поскольку в процессе кодирования нет обратной связи.

История

Основная заявка на патент на турбокоды была подана 23 апреля 1991 года. В патентной заявке Клод Берру указан как единственный изобретатель турбокодов. В результате подачи заявки на патент было получено несколько патентов, включая патент США № 5 446 747 , срок действия которого истек 29 августа 2013 года.

Первой публичной статьей о турбокодах была « Кодирование и декодирование с коррекцией ошибок, близких к пределу Шеннона: турбокоды ». Эта статья была опубликована в 1993 году в Трудах Международной конференции по связи IEEE. Статья 1993 года была составлена ​​из трех отдельных материалов, которые были объединены из-за нехватки места. В результате слияния в газете были указаны три автора: Берру, Главье и Титимайшима (из Télécom Bretagne, бывшего ENST Bretagne , Франция). Однако из оригинальной патентной заявки ясно, что Берру является единственным изобретателем турбокодов и что другие авторы статьи предоставили материал, отличный от основных концепций.

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

Первым классом турбокода был параллельный каскадный сверточный код (PCCC). С момента появления оригинальных параллельных турбокодов в 1993 году было обнаружено множество других классов турбокодов, включая последовательные каскадные сверточные коды и коды с повторением-накоплением . Итеративные методы турбодекодирования также применялись к более традиционным системам FEC, включая сверточные коды с коррекцией Рида-Соломона, хотя эти системы слишком сложны для практической реализации итеративных декодеров. Турбо-эквализация также вытекает из концепции турбокодирования.

В дополнение к турбокодам Берру также изобрел рекурсивные систематические сверточные (RSC) коды, которые используются в примере реализации турбокодов, описанном в патенте. Турбокоды, использующие коды RSC, по-видимому, работают лучше, чем турбокоды, которые не используют коды RSC.

До турбокодов лучшими конструкциями были последовательные каскадные коды, основанные на внешнем коде исправления ошибок Рида-Соломона в сочетании с внутренним , декодированным по Витерби с короткой длиной ограничения сверточным кодом , также известным как коды RSV.

В более поздней статье Берру отдал должное интуиции «Г. Баттейла, Дж. Хагенауэра и П. Хёхера, которые в конце 80-х годов подчеркнули интерес к вероятностной обработке». Он добавляет: « Р. Галлагер и М. Таннер уже придумали методы кодирования и декодирования, общие принципы которых тесно связаны», хотя необходимые расчеты в то время были непрактичны.

Пример кодировщика

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

Эта реализация кодера отправляет три подблока битов. Первый подблок представляет собой m -битовый блок полезных данных. Второй подблок представляет собой n/2 бита четности для данных полезной нагрузки, вычисляемых с использованием рекурсивного систематического сверточного кода (код RSC). Третий подблок представляет собой n/2 бита четности для известной перестановки данных полезной нагрузки, снова вычисляемой с использованием кода RSC. Таким образом, вместе с полезной нагрузкой отправляются два избыточных, но разных подблока битов четности. Полный блок имеет m + n бит данных со скоростью кода m /( m + n ) . Перестановка называемым полезных данных осуществляется устройством, перемежителем .

Аппаратно этот кодер турбокода состоит из двух идентичных кодеров RSC, и _: C2 , _{конкатенацией} как изображено на рисунке, которые соединены друг с другом с помощью схемы конкатенации, называемой параллельной C1

На рисунке M — регистр памяти. Линия задержки и перемежитель заставляют входные биты d _k появляться в разных последовательностях.При первой итерации входная последовательность d _k появляется на обоих выходах кодера x _k и y _1k или y _2k из-за систематического характера кодера. Если энкодеры C ₁ и C ₂ используются в n ₁ и n ₂ итерациях, их скорости соответственно равны

${\begin{aligned}~R_{1}&={\frac {n_{1}+n_{2}}{2n_{1}+n_{2}}}\\~R_{2}&={\frac {n_{1}+n_{2}}{n_{1}+2n_{2}}}\end{aligned}}$

Декодер

Декодер построен аналогично приведенному выше кодировщику. Два элементарных декодера соединены между собой, но последовательно, а не параллельно. $\textstyle DEC_{1}$ декодер работает на меньшей скорости (т.е. $\textstyle R_{1}$), таким образом, он предназначен для $\textstyle C_{1}$ кодер и $\textstyle DEC_{2}$ для $\textstyle C_{2}$ соответственно. $\textstyle DEC_{1}$ дает мягкое решение , которое приводит к $\textstyle L_{1}$ задерживать. Такую же задержку вызывает линия задержки в кодере. $\textstyle DEC_{2}$операция вызывает $\textstyle L_{2}$ задерживать.

Здесь используется перемежитель, установленный между двумя декодерами, для рассеивания пакетов ошибок, поступающих от $\textstyle DEC_{1}$ выход. Блок DI представляет собой модуль демультиплексирования и вставки. Он работает как переключатель, перенаправляя входные биты в $\textstyle DEC_{1}$ в один момент и $\textstyle DEC_{2}$ в другом. В выключенном состоянии он питает оба $\textstyle y_{1k}$ и $\textstyle y_{2k}$ входы с битами заполнения (нули).

Рассмотрим канал AWGN без памяти и предположим, что на k -й итерации декодер получает пару случайных величин:

${\begin{aligned}~x_{k}&=(2d_{k}-1)+a_{k}\\~y_{k}&=2(Y_{k}-1)+b_{k}\end{aligned}}$

где $\textstyle a_{k}$ и $\textstyle b_{k}$ являются независимыми компонентами шума, имеющими одинаковую дисперсию $\textstyle \sigma ^{2}$. $\textstyle Y_{k}$ это k -й бит от $\textstyle y_{k}$ выход энкодера.

Избыточная информация демультиплексируется и отправляется через DI в $\textstyle DEC_{1}$ (когда $\textstyle y_{k}=y_{1k}$) и $\textstyle DEC_{2}$ (когда $\textstyle y_{k}=y_{2k}$).

$\textstyle DEC_{1}$ дает мягкое решение; то есть:

$\Lambda (d_{k})=\log {\frac {p(d_{k}=1)}{p(d_{k}=0)}}$

и доставляет его $\textstyle DEC_{2}$. $\textstyle \Lambda (d_{k})$ называется логарифмом отношения правдоподобия (LLR). $\textstyle p(d_{k}=i),\,i\in \{0,1\}$ - апостериорная вероятность (APP) $\textstyle d_{k}$ бит данных, который показывает вероятность интерпретации полученного $\textstyle d_{k}$ немного как $\textstyle i$. Принимая во внимание LLR , $\textstyle DEC_{2}$ дает трудное решение; то есть декодированный бит.

Известно, что алгоритм Витерби не способен вычислить АРР, поэтому его нельзя использовать в $\textstyle DEC_{1}$. Вместо этого модифицированный алгоритм BCJR используется . Для $\textstyle DEC_{2}$, алгоритм Витерби является подходящим.

Однако изображенная структура не является оптимальной, поскольку $\textstyle DEC_{1}$ использует только правильную часть доступной избыточной информации. Для улучшения структуры используется контур обратной связи (см. пунктир на рисунке).

Мягкий подход к принятию решений

Внешний интерфейс декодера выдает целое число для каждого бита в потоке данных. Это целое число является мерой вероятности того, что бит будет равен 0 или 1, и его также называют мягким битом . Целое число может быть взято из диапазона [-127, 127], где:

• −127 означает «конечно 0»
• −100 означает «весьма вероятно 0»
• 0 означает «это может быть либо 0, либо 1»
• 100 означает «весьма вероятно 1».
• 127 означает «конечно 1».

Это привносит вероятностный аспект в поток данных из внешнего интерфейса, но передает больше информации о каждом бите, чем просто 0 или 1.

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

Чтобы декодировать m + n -битный блок данных, внешний интерфейс декодера создает блок мер правдоподобия с одной мерой правдоподобия для каждого бита в потоке данных. Имеется два параллельных декодера, по одному на каждый из n ⁄ 2- битных подблоков четности. Оба декодера используют подблок из m вероятностей для полезных данных. Декодер, работающий со вторым субблоком четности, знает перестановку, которую кодер использовал для этого субблока.

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

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

Можно провести аналогию между этим процессом и решением головоломок с перекрестными ссылками, таких как кроссворд или судоку . Рассмотрим частично заполненный, возможно, искаженный кроссворд. Два решателя головоломок (декодеры) пытаются решить ее: один обладает только подсказками «вниз» (биты четности), а другой обладает только подсказками «поперек». Для начала оба решателя угадывают ответы (гипотезы) на свои собственные подсказки, отмечая, насколько они уверены в каждой букве (бите полезной нагрузки). Затем они сравнивают записи, обмениваясь друг с другом ответами и оценками уверенности, отмечая, где и как они различаются. Основываясь на этих новых знаниях, они оба получают обновленные ответы и рейтинги достоверности, повторяя весь процесс, пока не придут к одному и тому же решению.

Производительность

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

Практическое применение с использованием турбокодов

Телекоммуникации:

• Турбокоды широко используются в 3G и 4G стандартах мобильной телефонии ; например, в HSPA , EV-DO и LTE .
• MediaFLO , система наземного мобильного телевидения от Qualcomm .
• Канал взаимодействия систем спутниковой связи , например DVB-RCS и DVB-RCS2 .
• Недавние миссии НАСА, такие как Mars Reconnaissance Orbiter, используют турбокоды в качестве альтернативы исправлению ошибок Рида – Соломона - коды декодера Витерби .
• IEEE 802.16 ( WiMAX ), стандарт беспроводной городской сети, использует блочное турбокодирование и сверточное турбокодирование.

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

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

См. также

• Алгоритм BCJR
• Сверточный код
• Прямое исправление ошибок
• Перемежитель
• Код проверки четности низкой плотности
• Последовательные составные сверточные коды
• Декодирование мягкого решения
• Турбо-эквалайзер
• Алгоритм Витерби

Дальнейшее чтение

Публикации

• Баттейл, Жерар (1998). «Концептуальная основа для понимания турбокодов». Журнал IEEE по избранным областям коммуникаций . 916 (2): 245–254. дои : 10.1109/49.661112 .
• Брейза, МФ; Ли, Л.; Маундер, Р.Г.; Аль-Хашими, Б.М.; Берроу, К.; Ханзо, Л. (2016). «20 лет турбокодирования и рекомендаций по проектированию энергосберегающих беспроводных приложений с ограниченным энергопотреблением» (PDF) . Опросы и учебные пособия IEEE по коммуникациям . 918 (1): 8–28. дои : 10.1109/COMST.2015.2448692 . S2CID   12966388 .
• Гарсон-Бохоркес, Рональд; Нур, Шарбель Абдель; Дуйяр, Кэтрин (2016). Улучшение турбокодов для 5G с помощью перемежителей с ограничением по четности (PDF) . 9-й Международный симпозиум по турбокодам и итеративной обработке информации (ISTC). стр. 151–5. дои : 10.1109/ISTC.2016.7593095 .

Внешние ссылки

• Гиззо, Эрико (март 2004 г.). «Подведение итогов к идеальному коду» . IEEE-спектр . 41 (3): 36–42. дои : 10.1109/MSPEC.2004.1270546 . S2CID   21237188 .
• «Турбокод UMTS и эффективная реализация декодера, подходящая для программно-определяемых радиостанций». Архивировано 20 октября 2016 г. в Wayback Machine ( Международный журнал беспроводных информационных сетей ).
• Маккензи, Дана (2005). «Доведите это до предела» . Новый учёный . 187 (2507): 38–41.
• «Pushing the Limit» , репортаж Science News о разработке и возникновении турбокодов.
• Международный симпозиум по турбокодам
• Coded Modulation Library — библиотека с открытым исходным кодом для моделирования турбокодов в Matlab.
• «Турбо-уравнивание: принципы и новые результаты». Архивировано 27 февраля 2009 г. в Wayback Machine , статье IEEE Transactions on Communications об использовании сверточных кодов совместно с выравниванием каналов.
• Домашняя страница IT++ IT ++ — это мощная библиотека C++, которая, в частности, поддерживает турбокоды.
• Публикации турбокодов Дэвида Маккея
• Домашняя страница AFF3CT (панель инструментов быстрого исправления ошибок) для моделирования высокоскоростных турбокодов в программном обеспечении.
• Керуэдан, Сильви; Берру, Клод (2010). «Турбокод» . Схоларпедия . 5 (4). Scholarpedia.org: 6496. Бибкод : 2010SchpJ...5.6496K . doi : 10.4249/scholarpedia.6496 .
• Эталонный проект 3GPP LTE Turbo .
• Оцените производительность BER турбокода в AWGN. Архивировано 1 февраля 2019 года в Wayback Machine (MatLab).
• Параллельное каскадное сверточное кодирование: турбокоды (MatLab Simulink)