Турбокод

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

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

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

История

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

Первой общедоступной статьей о турбокодах была « Кодирование и декодирование с коррекцией ошибок, близких к пределу Шеннона: турбокоды ». ^[3] Эта статья была опубликована в 1993 году в Proceedings of IEEE International Communications Conference. Статья 1993 года была составлена ​​из трех отдельных материалов, которые были объединены из-за нехватки места. В результате слияния в газете были указаны три автора: Берру, Главье и Титимайшима (из Télécom Bretagne, бывшего ENST Bretagne , Франция). Однако из оригинальной патентной заявки ясно, что Берру является единственным изобретателем турбокодов и что другие авторы статьи предоставили материал, отличный от основных концепций. ^{[ неправильный синтез ]}

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

Декодер

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

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

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

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

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

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

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

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

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

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

Однако изображенная структура не является оптимальной, поскольку использует только правильную часть доступной избыточной информации. Для улучшения структуры используется контур обратной связи (см. пунктир на рисунке). ${\displaystyle \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 ^[6] и DVB-RCS2.
• Недавние миссии НАСА , такие как Mars Reconnaissance Orbiter, используют турбокоды в качестве альтернативы исправлению ошибок Рида – Соломона - коды декодера Витерби .
• IEEE 802.16 ( WiMAX ), стандарт беспроводной городской сети, использует блочное турбокодирование и сверточное турбокодирование.

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

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

Смотрите также

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

Рекомендации

1. Эрико Гиззо (1 марта 2004 г.). «ВЫБОР ИДЕАЛЬНОГО КОДА». IEEE-спектр .«Еще одно преимущество, возможно, самое большое, заключается в том, что срок действия патентов LDPC истек, поэтому компании могут использовать их, не платя за права интеллектуальной собственности».
2. Хагенауэр, Иоахим; Предложение, Эльке; Папке, Луис (март 1996 г.). «Итеративное декодирование двоичных блоков и сверточных кодов» (PDF) . Транзакции IEEE по теории информации . 42 (2): 429–445. дои : 10.1109/18.485714. Архивировано из оригинала (PDF) 11 июня 2013 года . Проверено 20 марта 2014 г.
3. Берру, Клод ; Главье, Ален ; Титимаджшима, Пунья (1993), «Ошибка, близкая к пределу Шеннона – исправление», Труды Международной конференции по связи IEEE , том. 2, стр. 1064–70, doi : 10.1109/ICC.1993.397441, S2CID  17770377 , получено 11 февраля 2010 г.
4. Эрико Гиззо (1 марта 2004 г.). «ВЫБОР ИДЕАЛЬНОГО КОДА». IEEE-спектр .
5. Берру, Клод, Турбокоды десятилетней давности вступают в эксплуатацию, Бретань, Франция , получено 11 февраля 2010 г.
6. Цифровое видеовещание (DVB); Канал взаимодействия для спутниковых систем распределения, ETSI EN 301 790, версия 1.5.1, май 2009 г.
7. МакЭлис, Роберт Дж .; Маккей, Дэвид Дж. К .; Ченг, Юнг-Фу (1998), «Турбо-декодирование как пример алгоритма Перла «распространения убеждений» (PDF) , Журнал IEEE по выбранным областям коммуникаций , 16 (2): 140–152, doi : 10.1109/49.661103, ISSN  0733-8716.

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

Публикации

• Баттейл, Жерар (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. doi : 10.1109/ISTC.2016.7593095.

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

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