7.1.3. Пороговое декодирование

Пороговое декодирование — это разработанный Месси [13] метод, позволяющий достичь выигрыша при сравнительно простой реализации. В результате значительного интереса к этому методу были получены обширные списки хороших кодов [13, 71, 72]. Пороговые декодеры позволяют легко осуществлять внутреннее перемежение аналогично тому, как это делается для декодеров с табличным поиском. В результате пороговое декодирование получило применение в ряде систем связи.

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

Оценки получаются суммированием одного или нескольких символов синдрома.

Как показано в гл. 3, мажоритарное правило декодирования состоит в том, чтобы положить если

и положить в противном случае.

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

Интерес представляют столбцы содержащие символ 1 в первой строке. Эти столбны соответствуют символам синдрома, включающим Заметим, что никакие два из таких столбцов не имеют общего символа 1 ни в одной (отличной от первой) строке Таким образом, эти четыре столбца ортогональны по Поэтому каждый из соответствующих символов синдрома можно использовать как отдельную оценку Это приводит к следующему множеству оценок:

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

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

Любой код, удовлетворяющий условию этого определения, обладает свойством, согласно которому множество ортогональных оценок для можно получить, взяв символы синдрома, соответствующие тем позициям, в которых первая строка содержит символы 1. Робинсон и Бернстейн [71] предложили метод построения самоортогональных кодов исходя из понятия разностных треугольников.

Определение. Разностным треугольником для некоторой строки называется треугольный массив, элемент которого равен разности между номерами столбцов, соответствующими символам 1 в этой строке

Для примера (7.30) разностный треугольник, соответствующий первой строке Н, имеет вид

Заметим, что все элементы этого разностного треугольника различны. Оказывается, что все элементы различны тогда, и только тогда, когда любые два столбца содержащие символ 1 в первой строке, не имеют общего символа 1 ни в одной другой строке [как матрица из (7.30)]. Таким образом, если задан разностный треугольник с различными элементами, то можно построить самоортогональный код следующим образом. С помощью элементов первой строки разностного треугольника можно определить первую строку матрицы поскольку известны разности номеров столбцов, в которых расположены символы 1. Остальные строки получаются соответствующими сдвигами первой строки. Разностный треугольник полностью определяется своей первой строкой, которая в свою очередь задает первую строку и с помощью (7.20) — порождающий многочлен кода. Таким образом.

если первая строка разностного треугольника имеет вид то порождающий многочлен кода

где

Для минимизации длины кодового ограничения при заданном числе элементов разностного треугольника нужно минимизировать сумму элементов первой строки. Их сумма равна Робинсон и Бернстейн [71] предпринимали попытки отыскать разностные треугольники с минимальным наибольшим элементом. Найденные ими разностные треугольники для некоторых значений скорости можно найти в приложении Б. В табл. Б.9 приведены треугольники, соответствующие кодам с В этой таблице содержатся только значения поскольку построенные коды имеют и могут исправлять 7/2 ошибок. Заметим, что в качестве примера, для которого записаны (7.30) и (7.31), выбран код с из этой таблицы.

Другое интересное свойство самоортогональных кодов состоит в том, что к ним применимо детерминированное декодирование. Это можно показать, рассматривая полубесконечную форму проверочной матрицы (7.30). Для каждой строки этой матрицы следует рассмотреть столбцов, соответствующих символам 1 в этой строке. В любой другой строке (как ранее, так и далее рассматриваемой) среди символов, соответствующих рассматриваемым столбцам, содержится не более одного символа 1. Это означает, что для получения множества ортогональных оценок не нужно устранять влияние предыдущих решений декодера. В отсутствие обратной связи множество оценок, аналогичных (7.31), приобретает вид

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

Аналогично можно построить коды со скоростями, отличными от 1/2. Существует, оказывается, интересная двойственность между кодами с и кодами с Используя наборы из разностных треугольников, можно построить коды как с так и с Основное необходимое свойство этих

наборов состоит в том, чтобы все элементы всех треугольников были различны. Если это условие выполнено, то код как с так и с построенный с помощью данного набора, является самоортогональным. Аналогично (7.33) первая строка каждого разностного треугольника может служить для вычисления порождающего многочлена. Получим набор из многочленов Систематический самоортогональный код с получается следующим образом:

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

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

В первой строке символы 1 расположены в первом и втором столбцах, и ни одна другая строка не содержит символы 1 в

обоих этих столбцах. Таким образом, задает пару проверок, ортогональных по Аналогично четвертая строка содержит символы в первом и третьем столбцах и ни одна другая строка не содержит символы 1 в обоих этих столбцах. Поэтому задает пару проверок, ортогональных по При появлении одиночных ошибок оба символа можно оценить правильно. Усеченная проверочная матрица для кода с имеет вид

Две снндромные последовательности для кода с имеют вид

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

Другой полезный класс кодов составляют так называемые коды, полученные методом проб и ошибок (ПО-коды). Они введены Месси [13]. Эти коды отличаются от КСОК по нескольким признакам. Прежде всего, ортогональных проверочных символов, найденных для каждого кода, образованы не одиночными символами синдрома, как в случае КСОК, а суммами двух или большего числа символов синдрома. Кроме того, для достижения полной корректирующей способности эти оценки должны быть использованы в декодере с обратной связью. При детерминированном декодировании характеристики существенно ухудшаются. Преимущество ПО-кодов состоит в том, что данное значение может быть получено при меньшей длине кодового ограничения, чем в случае КСОК. В табл. Б. 16 приведены некоторые ПО-коды для

Типичным примером являтся код с Усеченная проверочная матрица этого кода имеет вид

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

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

Рис. 7.6 Пороговый леколер с жестким решением для кодов с

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

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

При пороговом декодировании можно употреблять также мягкие решения, однако сложность при этом существенно увеличивается. Оптимальным методом использования мягких решений при пороговом декодировании является метод декодирования АРР [13], рассмотренный в гл. 4. Реализация сверточных кодов аналогична в этом случае реализации блоковых кодов, рассмотренной ранее. Каждой оценке ставится в соответствие весовой коэффициент который зависит от вероятности правильности оценки

Рис. 7.7. Пороговый декодер с обратной связью и с жестким решением для кода с

Рис. 7.8. Пороговый декодер АРР для кодов с (цепь обратной связи не показана)

Правило декодирования АРР состоит в том, что тогда и только тогда, когда

Веса могут быть вычислены либо с помощью нелинейного отображения, либо с помощью приближенного метода АРР [22, 23]. Структурная схема декодера АРР показана на рис. 7.8. В данной схеме по сравнению со схемой декодера с жестким решением (см. рис. 7.6) добавлены устройство для хранения абсолютной величины и устройство, позволяющее умножать символы синдрома на соответствующие веса Кроме того, несколько усложняется вычисление суммы. Заметим, что согласно (7.42) порог должен быть переменным. Однако это неравенство можно переписать в виде

Используя (7.43) или аналогичные (с добавлением константы к обеим частям) неравенство, можно упростить реализацию.

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

ростом сравнительно медленно. Таким образом, практически разумными являются лишь небольшие значения Аналогично при фиксированном сложность растет, как для кодов с Из табл. видно, что коды с высокими скоростями требуют очень длинных регистров сдвига. При добавлении мягких решений в систему добавляются регистры для хранения абсолютных величин, а также усложняются решающие устройства. (Обычно при этом сложность увеличивается примерно в два раза.)

Тщательно выбирая код, можно получать сравнительно большой выигрыш от кодирования при умеренной сложности. Несколько лет назад была разработана система, реализующая ПО-код с В системе осуществляется приближенное декодирование АРР с четырехуровневым мягким решением при скорости Для реализации кодера и декодера требуется не больше 40 интегральных микросхем малого и среднего уровня интеграции. Такая схема системы дает выигрыш от кодирования, равный при и фазовой модуляции. Эти результаты оказываются значительно лучше результатов декодирования с табличным поиском (см. подразд. 7.1.2).

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

7.1.3.3. Анализ характеристик. Месси [13] рассмотрел методы анализа характеристик пороговых декодеров, используя подсчет ошибок, аналогичный приведенному в подразд. 7.1.1.2. Вероятность первой ошибки декодирования может быть записана в виде

Это равенство справедливо для всех вариантов порогового декодирования. Для жесткого решения с простым мажоритарным декодированием для всех

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

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

Заметим, что множество оценок при условии дополнительно к множеству оценок при условии Поэтому (7.44) можно переписать в следующем виде:

и достаточно рассматривать лишь условные распределения вероятностей при условии

Рассмотрим вначале случай жесткого решения при мажоритарном декодировании. Производящая функция случайной величины имеет вид

Каждый коэффициент производящей функции (7.47) равен вероятности того, что случайная величина принимает значение, равное показателю степени переменной Согласно этому методу вероятность первой ошибки декодирования можно записать в виде

где

Оценки характеристик принимают особенно простой вид для КСОК с детерминированным декодированием и жестким решением [73]. В этом случае все оценки имеют один и тот же объем .

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

где

Поскольку для всех можно записать в виде

Это равенство записано в предположении, что порог при четном при нечетном Оно справедливо для кодов как с так и с задаваемых табл. В случае кодов с значение приведенное в этих таблицах, совпадает со значением подставляемым в (7.51). Кроме того, объем каждой оценки, используемый в (7.50), равен В случае кодов с значение подставляемое в (7.51), получается умножением табличного значения на Рассчитанные объемы проверок на четность совпадают с табличным значением

Описанный метод был использован для расчета для кодов с Результаты вычислений (при показаны на рис. 7.9 и 7.10. Поскольку при этом предполагалось жесткое квантование сигнала на выходе демодулятора, то приведенные кривые могут служить для оценок характеристик при других выборах множества сигналов. Для этого следует лишь определить вероятность ошибки в канале, приводящую к интересующему значению Разность значений для двух выборов множества сигналов находится сравнением при значении соответствующем необходимой рабочей точке.

Анализируя приведенные кривые, можно сделать интересный вывод о том, что при увеличении быстро достигается значение, когда его дальнейший рост оказывается невыгодным. Так, рост с 6 до 12 приводит к дополнительному выигрышу, равному лишь примерно при Поскольку сложность растет пропорционально то эффективными по стоимости оказываются обычно только значения Другое интересное свойство состоит в том, что при фиксированном значении коды с большей скоростью оказываются лучше кодов с меньшей скоростью. Это объясняется меньшими потерями из-за расширения полосы. Обсудим это подробнее чуть позже.

Для того чтобы оценить параметры декодирования АРР, обычно приходится прибегать к моделированию. Типичные результаты моделирования для блоковых и сверточных кодов показывают, что

(кликните для просмотра скана)

декодер АРР с мягким решением и квантованием на восемь уровней имеет примерно на лучшие характеристики, чем декодер с жестким решением.

В случае приближенного декодирования АРР можно вывести формулу для Поскольку веса принимают лишь конечное число значений, расчет по (7.46) аналогичен расчету при жестком решении (хотя вычисления будут более громоздкими). Этот метод был использован для расчета кривых при четырехуровневом квантовании (рис. 7.11). Поскольку использованные коды были каноническими самоортогональными, то для них Уровень квантования устанавливался равным Отклонение на ±3 дБ от этого уровня вызывало ухудшение характеристик лишь на Дополнительный выигрыш, полученный в результате четырехуровневого квантования вместо двухуровневого, составляет примерно Аналогичный выигрыш получается и при кодах с большими скоростями. Оказывается, что дополнительный выигрыш, возникающий при мягком решении и приближенном декодировании АРР, убывает при росте объема каждой оценки [равного для этих кодов].

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

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

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

Рис. 7.11. Характеристики канонических самоортогональных кодов с при четырехуровневом квантовании и детерминированном декодировании

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