О наилучших алгоритмах помехоустойчивого кодирования

Введение

Клод Шеннон (1916–2001)

Для беспроводных технологий и других современных средств связи оптимальны простые высокоскоростные кодеры и декодеры (кодеки) помехоустойчивого кодирования с помехоустойчивостью, близкой к пределу Шеннона — пропускной способности канала (ПСК). Длина кода из-за роста скоростей не является важным ограничением. В [1, 2, 3] отмечены преимущества кодеков с малой плотностью проверок на четность (МПЧ) — Low Density Parity Check Codes (LDPC) на базе совершенных разностных множеств (СРМ), реализуемых на микросхемах. Отмечены недостатки часто рекламируемых кодеков алгоритмов Витерби (АВ), турбокодов (ТК) и кодов Рида — Соломона (КРС). У кодеков АВ, ТК и КРС скорости, энергопотребление и надежность более чем в 50 раз хуже, чем у рекомендованных в [1, 2, 3], при худшей помехозащите. С ростом скоростей передачи и энергозатрат растет интенсивность отказов, пропорциональная потребляемой энергии, которая является мерой старения аппаратуры [3]. Поэтому преимуществами высокой надежности обладают простые кодеки, реализованные на микросхемах. Однако до сих пор кодеки помехозащиты обычно реализуют на процессорах с надежностью в 20–30 раз худшей, и реже — на программируемых логических интегральных схемах (ПЛИС) с надежностью, худшей в четыре-пять раз, чем при реализации на специализированных микросхемах — Application Specified Integrated Circuit (ASIC). Цель этой работы — содействовать разработкам на микросхемах простейших и надежных кодеков с помехозащитой, близкой к ПСК (пределу Шеннона).

Первые оптимизированные пороговые кодеки (ОПД)

Впервые пороговые кодеки (ПК) сверточных кодов с МПЧ на двоичных регистрах сдвига (РС) с помехоустойчивостью, близкой к ПСК, были описаны в [4, 5, 6]. Их генераторные полиномы (ГП) с МПЧ, обладающие свойством «не более одного совпадения» (НБОС) позиций ненулевых членов ГП, подбирали «вручную». Поэтому ГП этих кодеков не были наилучшими. Решение в кодеках [4, 5, 6] формировали несколько итераций (ступеней) декодирования. Последовательно работали несколько анализаторов синдрома (АС) с увеличенными порогами в первых АС, снижающими вероятность ошибочных коррекций. Каждый следующий АС вносил поправки в решения предыдущих АС о коррекции информационных символов, приближая решение ПК к решению оптимального декодера (ОД). Были испытаны несколько таких оптимизированных пороговых декодеров (ОПД) с малыми кодовыми расстояниями d и длинами ГП кодов М. Поиск длинных ГП с кодами НБОС для реализации больших d был очень трудным, так как у ГП с НБОС длина М пропорциональна d2.

В [4] описаны ОПД с вероятностями ошибок канала (ВОК) — порогами, близкими к ПСК. Четыре кодека с кодовой скоростью R = 1/2 имели пять итераций (d = 7, 9, 11, 15 и M = 58, 107, 148, 201). Кодек с R = 3/4, d = 9 и М = 202 имел порог ВОК около 0,1. Кодек с R = 1/3, d = 13 и М = 202 имел шесть итераций и порог ВОК около 0,01. Наибольший эффект дают вторая и третья ступени АС. Обработка в ОПД квантованного решения улучшала энергетический выигрыш кодирования (ЭВК) на 1 дБ, но значительно усложняла ОПД. В [4] отмечены преимущества простоты и помехоустойчивости ОПД в сравнении с кодеками других видов.

В [5, 6] показаны преимущества внутреннего кодека ОПД в каскадных кодеках относительно других кодеков, включая кодеки самоортогональных кодов (СОК) и кодеки АВ. У ОПД с R = 1/2 ЭВК выше, чем у АВ, на 1,5 дБ при M = 360 и на 2,0 дБ при М = 1000. Отмечено, что в СОК с МПЧ, использующих проверочные матрицы, сходимость к решению ОД хуже и что появление микросхем с длинными РС существенно расширяет перспективы применения ОПД с РС на микросхемах. Отмечены преимущества прореживаний и удлинений ГП, которые снижают количество совпадающих вторых разностей и вероятность искажений синдрома ошибочными коррекциями. Удлинения ГП незначительно усложняют кодек, так как улучшают сходимость к решению ОД и позволяют снизить количество ступеней ОПД. Рассмотрено взаимодействие внутреннего кодека с модемом и показаны преимущества четырехпозиционной ФМ с неравномерной энергетикой канала (НЭК) — увеличением в два раза расстояний информационных символов, повышающим ЭВК кодека на 1 дБ. Показаны преимущества блоковых ОПД перед БЧХ и КРС в каскадных кодеках. У кодека со внутренним ОПД (R = 1/2, n = 160, М = 80, d = 7 и семь итераций) и внешним ОПД (R = 4/5, n = 880, M = 176, d = 7 и пять итераций) ЭВК больше на 2 дБ, чем у каскадных кодеков с БЧХ (28, 14, 4) и КРС (31, 25, 17) и на 0,8 дБ, чем у БЧХ (200, 100, 27) и КРС (511, 407, 105). Отмечено, что эти кодеки с БЧХ и КРС сложнее и медленнее каскадных кодеков ОПД. Очень сложные турбокоды (ТК) появились в 1993 г., и в [4–6] их сравнений с ОПД нет.

Преимущества кодеков с ОПД на базе СРМ

Совершенные разностные множества (СРМ), сохраняющие свойство НБОС при замыкании ГП «в кольцо» по модулю длины ГП, описаны в [7, 8]. Но они стали известными после окончания работ [4–6]. Если количество единиц в СРМ = N, то длина кода M = N(N–1)+1 и кодовое расстояние d = N+1. Разности позиций единиц СРМ по модулю М принимают каждое из значений последовательности 1, 2, 3, …N, N+1, …N(N–1) один раз. Особенности построения СРМ показаны в [8]. Там же приведена таблица 5.1 СРМ с N =<98 и М =<9507. В кодеках с СРМ удобно осуществлять прореживание ГП, которое снижает d, но улучшает сходимость к оптимальному решению. Коды с СРМ удобны для блоковых кодеков ОПД с несколькими циклами анализа в одной ступени решения. В них информация о каждом откорректированном в АС информационном символе — «единица коррекции» (ЕК) — поступает в память единиц коррекций (ПЕК), например в кольцевой регистр коррекций (КРК), откуда ЕК поступают в следующем цикле анализа в АС с неизменным порогом, облегчая отказ от ошибочной коррекции. Такой блоковый ОПД с КРК и одной ступенью может быть проще многоступенчатого сверточного ОПД с равной помехоустойчивостью. Отмечено, что все узлы кодеков ОПД с РС (кодер, АС, КРК) удобны для реализации на специализированной микросхеме (ASIC).

В [9] дан вывод о преимуществах блоковых кодеков ОПД для применения в пакетной связи. Отмечены преимущества НЭК. Приведена структурная схема сверточного МПЧ-кодека ОПД с R=4/5 и тремя итерациями, где каждая ступень АС высылает ЕК в ПЕК, откуда ЕК поступают в следующий АС, облегчая отказ от предыдущей коррекции. Отмечены преимущества пороговых элементов на КМОП-переключателях. Описаны несколько вариантов приближения помехоустойчивости ОПД к решению ОД. Полезно завысить порог в первом АС. Полезно из СРМ с избыточной в два-три раза длиной выбрать ГП, прореженный в два-три раза. Можно «растянуть» код СРМ в b раз (b = >N) с добавлением к каждой степени этого кода одного члена ряда 0, 1, 2, …(b–1). У таких «удлиненных» ГП меньше количество совпадающих вторых разностей, существенно снижена вероятность ошибочных коррекций, помехоустойчивость приближена к ОД. Но длина кода у таких кодеков растет почти как d3. Можно при СРМ ослабить размножение ошибок и приблизить решение кодеков ОПД к решению ОД, используя нестационарные ГП — поочередно кодируя информационные биты двумя и более разными ГП с циклическими сдвигами СРМ. У них длина растет медленнее, чем d3. В [10] также отмечены преимущества прореживания ГП и приближения решений ОПД к решению ОД и реализации всех узлов ОПД на микросхеме.

В [11] отмечены перспективы «перемешиваемых» нестационарных кодов, но они в этой работе использованы не были. Описан рекуррентный пороговый кодек ОПД, в котором из СРМ с N = 34, d = 35 и длиной М = 1123 по критерию наилучшего спектра весов вторых разностей выбран ГП с d = 13 и N = 12 на позициях: 1, 8, 60, 90, 193, 254, 399, 508, 840, 904, 935, 939. Такое прореживание (в 8,5 раза) и неравномерная энергетика канала, рекомендованные в [5], позволили получить высокую помехоустойчивость. Кодек работал в канале с АБГШ (аддитивный белый гауссовский шум) при Eb/Nо около 2,5 дБ. Количество ступеней итераций не указано. ЭВК у него выше, чем у кодека АВ, на 1,5–2,0 дБ.

Отмеченные преимущества ОПД были использованы в микросхемах кодеков, описанных в [1–3]. В [3] упомянута микросхема блокового кодека с ОПД на базе СРМ длиной M = 553, работавшая в радиоканале челнока «Буран» (1988 г.), реализованная на матричной БИС (МБИС) серии 1515 ХМ1 емкостью 3 тыс. условных вентилей (УВ) и проектной нормой (ПН) 5 мкм. У этого кодека кодовая скорость R = 1/2, N = 24 и d = 25. Использовать более длинный ГП не позволила малая емкость кристалла МБИС. Помехоустойчивость кодека с жестким решением канала на этой МБИС лучше, чем у значительно более сложного кодека АВ с мягким решением. Эта МБИС может работать в режимах кодера, АС и КРК. Благодаря СРМ блоковый ОПД с такой МБИС может использовать только одну ступень — один АС, работающий вместе с КРК.

Для Минобороны была разработана (совместно с компанией «Вигстар» и МИЭТ, Зеленоград) МБИС 5503ХМ7-158 [12] с ПН 1,5 мкм — рекуррентный (сверточный) высокоскоростной (до 15 Мбит/с) кодек на базе совершенного разностного множества (СРМ-133) с кодовой скоростью R = 1/2 на нестационарных ГП с двумя ветвями кода [12]. Его сложность — 5,0 тыс. УВ. Энергопотребление — около 20 мкДж/бит. Кодек работал с жестким решением. Он устойчив к большим помехам. Его синхронизация устойчива даже при действии плотного (до 50%) пакета ошибок длиной до 25 бит. Это преимущество представляет особенную ценность для защиты от заградительных помех [1–3]. В [13] показано, что ведущие зарубежные фирмы (Intel, Motorola, Samsung и др.) более 15 лет реализуют сверхширокополосные связи (СШПС) на микросхемах system-on-chip (SoC) — система на кристалле (СнК) собственной разработки. В [1] отмечено, что многие российские фирмы уже в 2011 г. создали аппаратуру на SoC емкостью более 10 млн УВ. Такая емкость позволяет реализовать на отечественных микросхемах кодеки с ОПД на прореженных ГП, а также на «b-преобразованных» ГП длиной более 1 млн бит с помехоустойчивостью, совпадающей практически с ОД — пропускной способностью канала.

Многопороговые декодеры самоортогональных кодов

За последние 30 лет появилось много работ по кодекам с малой плотностью проверок на четность (МПЧ), продолжающих работы по самоортогональным кодам СОК [14, 15], где описаны матричные декодеры квазициклических кодов (quasy-cyclic code) с переменными порогами. В первых строках матрицы содержат СРМ — perfect difference sets. Анализ матриц ведут с помощью графа Таннера, и преимущества СРМ не используют надлежащим образом. Среди этих работ наибольший интерес представляют исследования путей улучшения СОК на базе многопороговых декодеров (МПД), итоги которых описаны в [16–19]. В них основное внимание уделено программной реализации недвоичных МПД СОК.

В [16] упомянуты преимущества НЭК и длинных кодов (несколько тысяч бит) с 10–20 итерациями, но не упомянуты рекомендации [5]
по алгоритмам удлинений ГП и НЭК. Даны рекомендации по устаревшим алгоритмам недвоичных qСОК с q = 8, удобным для программной, но не для аппаратной реализации. Наиболее интересен блоковый кодек, выполненный подобно ОПД [4–6, 9–12] на двоичных РС. В этом кодеке один фиксированный порог и нет матриц СОК, но он ошибочно назван «многопороговым СОК». В кодеке работает кольцевой регистр коррекций (КРК) с неудачным названием «разностный регистр». В него вводят единицы коррекций (ЕК), которые в следующем цикле поступают на порог, облегчая отказы от ошибочных коррекций. В кодеке использован короткий ГП на СРМ-13 без прореживаний с R = 1/2, N= 6, d = 7, М = 13. Упоминания о СРМ нет. Этот ГП заимствован из [8], но такой ссылки нет.

В [17] дан обзор методов помехоустойчивого кодирования и отмечено, что вблизи ПСК могут работать кодеки трех типов — турбокодеки (ТК), кодеки МПЧ-LDPC и кодеки МПД СОК. Как наилучшие отмечены блоковые кодеки МПЧ-LDPC, задаваемые проверочными матрицами, у которых синдром анализируют в соответствии с графом Таннера алгоритмами sum-product или min-sum. Отмечено, что помехоустойчивость LDPC при длине кода около 106 всего на 0,1 дБ отстоит от ПСК — предела Шеннона, и что ЭВК у кодеков МПД СОК меньше, чем у кодеков LDPC. При 40 итерациях МПД СОК с кодами длиной около 40 тыс. отстоят от ПСК на 2 дБ, и не отмечено, что кодеки МПД СОК очень сложны для аппаратной реализации.

В [18] рассмотрены кодеки СОК с МПЧ, с параллельным каскадированием и проверочными матрицами с разреженной структурой. Приведен пример графа Таннера с малым количеством ребер для блокового СОК длиной 26 бит на базе СРМ-13 с ГП (0, 1, 4, 6) и одной ступенью. Описаны два кодека МПД СОК, реализованные на ПЛИС. Декодер на первой ПЛИС Spartan-II имеет сложность около 0,2 млн вентилей, задержку декодирования 10 000 бит, R = 1/2, ЭВК более 6,5 дБ и ВО декодирования около 10–5 при Eb/Nо = 2,9 дБ. Декодер на второй ПЛИС Altera сложнее. При 40 итерациях он имеет ЭВК более 7,5 дБ при ВОК (вероятности ошибок канала) декодирования около 10–5 и Eb/Nо около 1,9 дБ. Рассмотрены двоичные каскадные коды на РС, подобные описанным в [5, 6], но без этих ссылок. Описан тот же, что и в [16], блоковый кодек ОПД на РС с СРМ-13 с КРК — «разностным регистром». Для параллельного каскадирования недвоичных СОК рекомендованы декодеры с алгоритмом min-sum, без критики сложности его аппаратной реализации.

В [19] содержатся итоги более 30 лет исследований кодеков МПД СОК. Приведены ошибочные выводы, что «задача исправлять проще, быстрее и при более высоком уровне шума еще очень далека от окончательного решения» и что характеристики кодеков невозможно приблизить к ПСК «при любом числе итераций в блоковом МПД или сколь угодно длинной цепочке в сверточном МПД». С ними нельзя согласиться. Полезно напомнить о методах ОПД, у которых есть такие возможности. Ведь МПД СОК на двоичных РС фактически утратили отличия от описанных ОПД. Описан двухступенчатый сверточный кодек с разными порогами без ПЕК, подобный ОПД [4–6], но ссылок нет. Отмечены трудности поиска хороших кодов и преимущества «чрезвычайно длинных кодов» для d =<41 и кодов с «переменными связями», но нет ссылок на [5, 6, 9, 11], где предложены удлиненные и нестационарные ГП. Рекомендаций по методам удлинения ГП нет. Упомянут кодек на ПЛИС с 40 итерациями длиной около 1 млн бит, но не описана его структура и генераторный полином. Повторено ошибочное утверждение, что распараллеливание операций упростит аппаратную реализацию МПД СОК. В действительности у параллельных архитектур сложны трассировки соединений между блоками вычислений и поэтому резко возрастает уровень потребления и интенсивность отказов кодека. Распараллеливание и сложные трассировки — это ошибки, серьезно препятствующие реализации на микросхеме. В выводах рекомендован поиск хороших длинных ГП для блоковых кодов МПД СОК без упоминания методов удлинения, описанных в [5, 6, 9, 11], удобных также для блоковых кодов.

Наибольшее внимание в [16–19] уделено кодам с МПД qСОК с синдромами на матрицах, у которых сходимость к решению ОД хуже, область оптимизации меньше, и они значительно сложнее ОПД на двоичных РС. Очевидно, что МПД с qСОК — тупиковый путь. Основным недостатком работ [16–19] является опора на программные средства реализации и игнорирование преимуществ реализации кодеков на микросхемах. Алгоритмов МПД СОК, пригодных для современных средств реализации на микросхемах, в [16–19] нет. Вряд ли кодеки МПД СОК будут реализованы на микросхемах.

Особенности матричных кодеков c МПЧ-LDPC

Коды c малой плотностью проверок на четность — low density parity check codes (LDPC) с матрицами проверок и их использование в системах передачи информации рассмотрены во многих работах. Отмечены перспективность применения МПЧ-LDPC-кодов и их преимущества в сравнении с другими кодами. Особенностью (и недостатком) этих работ являются программные средства реализации LDPC-кодов и игнорирование аппаратной реализации на микросхемах. В матричных кодеках LDPC, подобно МПД СОК, используют итеративное декодирование, а синдром формируют или в соответствии с графом Таннера, или по алгоритмам sum-product и min-sum, которые также сложны. Но характеристики у кодеков LDPC с длинными ГП лучше, чем у кодеков МПД СОК.

В [21] описаны два матричных кодека LDPC. Длинный кодек, отстоящий от ПСК на 0,0045 дБ, не описан. По-видимому, его длина более 108. Кодек с R = 1/2, d = 200 и длиной информационного блока 107 отстоит от предела Шеннона на 0,04 дБ. В нем использовано декодирование по алгоритму sum-product и более 800 итераций. В [22] описан матричный LDPC-кодек на ПЛИС и его испытания в канале с АБГШ. В нем использован алгоритм sum-product. Заверения об «экономии аппаратных ресурсов» при реализации матричных LDPC-кодеков на ПЛИС не обоснованы. В [23] дан анализ трех типов недвоичных кодеков LDPC и кодеков Рида — Соломона (КРС) разной длины и показано, что при ВОК декодирования 10–5 и близких R преимущества помехо­устойчивости LDPC перед КРС при коротких блоках — 1,6 дБ, при средних — 2,0 дБ, при длинных — 2,4 дБ.

В [24] рассмотрен выбранный в стандарте космических связей CCSDS кодек LDPC с R = 1/2, информационным блоком 1024 бит и длиной кода 2048 и исследованы алгоритмы реализации этого кодека на ПЛИС. В нем непрерывно работают два блока по 2048 бит с поочередной записью текущего блока и обработкой предыдущего. Для хранения проверочных и итоговых метрик и выполнения итераций использована память 7680+7680 бит. При обработке мягкого решения нужна еще буферная память на два блока 2048 бит каждый. Рассмотрены два алгоритма анализа матриц — сложный min-product и более простой min-sum, где работают двоичные РС и функции сравнения. Отмечено, что на ПЛИС сложны вычисления корня, тригонометрических функций, логарифмов, экспоненты и деления, легко реализуемые на сигнальных микропроцессорах, и что аппаратное декодирование таких кодов LDPC очень ресурсоемко.

Реализация кодеков LDPC на двоичных регистрах сдвига

Сложность реализации низкоплотностных кодеков с ОПД зависит от требований канала связи. Наиболее простая реализация у блоковых кодеков с R = 1/2 на двоичных регистрах сдвига (ДРС), работающих в пакетных каналах, преобладающих в беспроводной связи [1–3]. У них кодер, анализатор синдрома и кольцевой регистр коррекций можно реализовать на однотипной микросхеме ДРС. Для реализации одного разряда РС нужны пять УВ, для одного XOR — три УВ. Дать точную оценку сложности порогового узла с большим количеством входов N трудно. Оценка его сложности сверху — d. Для кода с N проверками, кодовым расстоянием d и длиной кода M сложность одного узла LDPC около 3N+d+5M УВ. Например, для блокового кодека LDPC [11] с параметрами М = 1123, N = 12 и d = 13 достаточно 6 тыс. УВ. Код СРМ с N = 98, M = 9507 [8] можно растянуть в 50 раз и затем увеличить каждую степень на 0, 1, 2, 3,…49. Длина такого удлиненного кода М почти 0,5 млн бит, и для его реализации нужны 2,5 млн УВ (10 млн транзисторов). Его помехоустойчивость всего на 0,1 дБ отстоит от ПСК — предела Шеннона. Для работы в непрерывном канале можно разработать сверточный ОПД или использовать два блоковых ОПД с поочередной обработкой блоков. В [1] отмечено, что НПК «Технологический Центр МИЭТ» (ТЦ МИЭТ) разработал библиотеки элементов микросхем, содержащие все нужные для кодеков цифровые узлы. Но для практической реализации ОПД, по-видимому, лучше выбирать более короткие двоичные LDPC с длинами не выше 40–150 тыс. бит.

Заключение

Постановление Правительства [20] требует разработок на микросхемах аппаратуры, конкурентной на мировом уровне. В нем п. 66 предусматривает освоение проектных норм микросхем, близких к зарубежным. В 2015 г. будут освоены ПН 0,045 мкм, позволяющие реализовать емкости кристалла более 20 млн УВ. Поставлена задача (п. 137) увеличить на базе ПН 0,045 мкм скорости обмена и передачи информации до 30 Гбит/с. Такая скорость доступна только для кодеков с ОПД на двоичных РС и недоступна для матричных алгоритмов, используемых в LDPC и МПД СОК. Но выбор сложных неэффективных алгоритмов помехоустойчивого кодирования нельзя объяснять некомпетентностью заказчиков и разработчиков.

Главная причина — следование зарубежным рекомендациям, что облегчало публикации, как это было с кодеками АВ, ТК и КРС. Вторая причина — следование привычным, но ошибочным критериям программной сложности. Возможно, что эта статья поможет остановить разработки кодеков на процессорах и ПЛИС и разработать на отечественных микросхемах близкие к пределу Шеннона кодеки с ОПД, конкурентные на мировом уровне. Ожидаемая сложность, энергопотребление и цена у них будут на порядок ниже, а надежность — на порядок выше, чем у рекламируемых матричных МПД СОК и матричных LDPC-кодеков.